Hello, and now we start our model that will be about almost perfect nonlinear functions or shortly APN functions. At the beginning, I would like to say that this functions are not only relevant for cryptographic applications but they are also interested for another branches of mathematic such as coding theory, sequence design, combinatorics, projective geometry, and so on. But we will focus only on cryptography perspective. In the beginning of the '90s, Biham and Shamir invent the differential cryptanalysis and applied this cryptanalysis through a well-known block cipher DES, Data Encryption Standard, and they show that this cipher has some disadvantages and it's in it as boxes. Now let us describe the main idea of this cryptanalysis. Suppose that F represents our block cipher transformations, and I would like to set here that we do not need to worry about the key in this context. Suppose that we have the number of inputs, the size of the plain text is n, and the number of outputs is m, the size of the cipher text, and then let x and y be two inputs to our plain text. Then we can encrypt them and get F of x and F of y, and this is our outputs, our ciphertexts. Then if we sum x and y and get the vector a, then we call this vector as the input difference of a cipher, and at the same time we can sum also by [inaudible] F of x plus F of y and get the vector b, and this is our output difference. Then the main idea of differential cryptanalysis is to find a pair, a and b, that occurs more often among the all pairs of input difference, output differences, and if we could find such a pair, then we can apply the differential cryptanalysis. But for cryptographies, we are interested in the situations when all these pairs have the same probability and we cannot choose only one with high probability, and how to find such a pair approved that it doesn't exist. At first, we need to concentrate our attention to the main nonlinear components of a cipher, S-boxes, and ask to them the same question, I mean the following. So let now F be a n, m function and it represents our S-box now, and we consider the same system of equations, you can see it here, and ask how many solutions has this system. So we have a given a and b and try to find how many pairs, x and y, give this particular pair, a and b. Equivalently, we can ask the question, how many solutions has this equation, F of x plus F of x plus a is equal to b. Let us consider that the best situation for us as cryptographers, when all this pair, a and b, has the same probability. We consider the function F of x plus F of x plus a for given a, and drop 2_n inputs for this functions for x. So we get 2_n values that are vectors of length m, and we know that there are 2_m possible such vectors. So the situation is the following. We want that each of these 2_m vectors among this values we have occurs equal number of time among the all this F of x plus F of x plus a. So what we had that we divide the 2_n values in the 2_m groups. Each groups correspond to the one value of length m and the cardinality of each group is 2_n minus m. Okay, and this is our best situation that we want to construct. But in general, when we consider such a property of a functions, we should consider how many solutions has this equations for any a and b. Let us denote by Delta F this number, and all this numbers for any a and b form the so-called difference distribution table of a function F. For example, you can see it here for a function that has three inputs, three outputs. You see that the all entries of this table are even numbers and they are from 0-8, and we should know that at position 0, 0, we always have the value 2_n. Then we are interested in what value in this table is the biggest, and we denote the biggest number, the maximum number as Delta big F, and then we call our function differentially Delta F uniform. This approach was considered by Nyberg and Knudsen in the beginning of '90s in connection with differential cryptanalysis. For example for our example, the biggest number is 6, since we exclude the position 0,0, it's not interesting for us. As we can see from our previous consideration that this maximum number, Delta F, is always bigger than 2_n minus m, and we are interested in functions which has the lowest possible Delta F, and this is 2_n minus m. If functions such this, then this functions are called perfect non-linear functions. But then it was proved that this functions are the same as vectorial bent functions, and it is known that this bent functions or PN functions exist only if the number of outputs is not more than a half of the number of inputs. But we are mostly interested in the case when n is equal to m because in this situation we can have a permutations that can be used in block ciphers and so on. Now we can easily understand also why PN functions do not exist in particular in this case because by definition of PN functions, we need to have that Delta F is equal to 2_n minus m and this is one. But it's easy to see that if x is a solution of this equation, then x plus a is also a solution, and so we have at least two of them. Functions for which we have at most two solutions for any a and b, we call Almost Perfect Nonlinear Functions. The almost here means that they are not perfect, but of course they are perfect and so in the sense for this particular case when n is equal to m. For example, you can see here that APN function in three variables, you can see the DDT table of this function and you see that all entries except the entry 0, 0 are filled by the numbers 0 and 2, and this is an APN function.
