Hello. Today we start with bent functions. This is a special class of Cryptographic Boolean Functions, that is one of the most mysterious, because of a lot of open problems are still open related to this class. Bent functions were introduced in '60s of 20th-century in relation to cryptographic applications. Let us see several definitions. Here you see the definition of the vector space over the field of these two elements, zero and one, and the Boolean function is a function from the set of all binary vectors of length n to the set with two elements, and the way the distance between two Boolean functions, we understand the hamming distance between their vectors of values. It means that we should count the number of coordinates in which they differ. Here you see x is a binary vector with n components and x, y in brackets, these are standard inner product modulo 2, and using it, it is easy to define affine Boolean function. You see of the definition under a bent function is the Boolean function in n variables, where n is even such that it is on the maximum possible distance from the class of all affine Boolean functions in n variables. It is interesting that if n is even, then such a maximal distance we know, you see this video. On the picture, but if n is odd, nobody knows this exact value of this maximal possible distance. So it is an open problem to find such a distance. We use standard as a notation, A_n and B_n for the class of affine functions and the class of bent functions. Some history in bent functions. As I've mentioned before, bent functions were introduced in '60s of 20th century by Oscar Rathaus. He was a mathematician in National Security Agency, and he was one of the most important teachers of cryptology to mathematicians and mathematics to cryptologists. He introduced bent functions in 1966, but his paper was published only in 1976. Here you see there're very rare pictures of Oscar Rathaus, and in Soviet Union, bent functions were also introduced in '60s. It was done by Eliseev and Stepchenkov and it was done in Charms of minimal functions. Because of bent function can be defined using Walsh-Hadamard coefficients and namely bent functions are exactly those Boolean functions with Walsh-Hadamard coefficients being the same in absolute value. That's why the notion of minimal functions was introduced by Eliseev and Stepchenkov, and in 1962, several results related to bent functions were approved by them before Oscar Rathaus and independently of him. But up to now the papers are still classified, but their names are known. Here you see the pictures of Eliseev and Stepchenkov. These pictures are more rare also. When you speak about figures in bent functions of course we should mention Robert MacFarland and John Dillon. They were pioneers in this areas and they obtained well-known classical results in this area and published well-known service on this topic. Bent functions have a lot of applications in different areas. Some of them are theoretical, some of them are practical. If you speak about theoretical applications, we need to mention Hadamard matrices. The problem of classification of all bent functions in n variables, it is equivalent to the problem of classification of Hadamard matrices with n rows with some restrictions. So we know that it is very difficult problem in combinatorics. You can try to solve it in terms of bent functions. Also bent functions are connected to differential sets in group theory and to orthogonal spreads in finite geometry. Also, it is possible to construct codes such as optimal non-linear codes Kerdock codes. They can be constructed using bent functions. When we speak about practical applications, we need to say lots about S-box constructions. You know that symmetric ciphers have such non-linear components as S-boxes and the resistance of all the cipher depends directly on the resistance of those S-boxes. So if you want to make your cipher to be resistant to linear cryptanalysis, then you need to use highly non-linear S-boxes and it's possible to construct such S-boxes using bent functions. We remember that linear cryptanalysis it is one of two most known statistical method of cryptanalysis. So we need to defend our cipher. Also, it's interesting to say that linear cryptanalysis, the papers on linear cryptanalysis appeared in 1993, in 1994, but bent functions was started 30 years before these papers. So we understand that special services, knew about these methods before, you understand. Also bent functions can be used to construct authentications schemes and hash functions and thus a pseudo-random generators. Here, you see the example for instance, this is a round function of the symmetric cipher cast, this as a Canadian cipher and here you see four S-boxes and each S-box has eight bits as input and 32 bits as output. If you'll consider such S-box as the union of 32 Boolean functions in eight variables, then we can say that every such component function is bent. Moreover, if you consider the sum of these two bent functions, then you obtain a Boolean function in eight variables that also has good nonlinear properties. It is not bent, but it has good nonlinear property. This property is very important to make the cipher CAST be resistant to linear cryptanalysis. In bent functions there were a lot of open problems, and one of the most important is to find the asymptotic value of the number of them. Or maybe at least to find good lower and upper bounds on the number of bent functions. You see on the picture, the known lower and upper bounds and you see that there is a big gap between these two bounds. How to make them closer, it's a problem. Also there is a problem to classify bent functions somehow to find the affine classification on some other classification. For instance, using bent rectangles and something like this, it is a problem. Also, there is a problem to find new constructions of bent functions. It is nice that all known constructions cover only the small part of all bent functions. We cannot say nothing about the rest. Another open problem is to reach a tradeoff between high non-linearity of bent functions and the other cryptography properties, because of if we use some Boolean function in cryptographic application, then we need to have different cryptography properties in it. So not only high non-linearity, and that's why we need to combine them and also there are different directions. How to study bent functions. It's possible to study their properties such as degree, rank, other properties. It's possible to find their equivalent representations in terms of Hadamard matrices and in other terms and also to find classifications of bent functions. For now, bent functions are classified only up to eight variables. So we know bent functions in two, four, six, and eight variables and that's all. How to do it in 10 variables, that's a big problem. Also to find some relations to other cryptography properties, to introduce new constructions of bent functions and thus to find new bounds on the number of bent functions and to study generalizations of bent functions to consider quaternary bent functions, quality bent functions. So bent function on different algebraic structure. Up to now there are more than 25 different generalizations and we need to study them also in connection to cryptographic applications.
