Hello everyone. Today we will talk about Boolean functions and their role in cryptography. So how do we use Boolean functions in cryptography and do you use Boolean functions in some other closely related fields? Yes. So we use Boolean functions in cryptography, we use them also in sequences and coding theory. How do we use them? Well in some standard designs, we use Boolean functions to add the non-linearity to the design. So for instance, we can combine linear feedback shift registers with one or more Boolean function to obtain a stream cipher. How many Boolean functions do we have? How difficult is to find a good Boolean function, a function fulfilling all the properties we require? Well if a Boolean function has n inputs, then the total number of Boolean functions for that size is 2_2 of n. So we see already for even a small input size, the total number of Boolean functions is quite large. For instance, even if n is only for the total number of Boolean functions is 2_16. So if you want to use Boolean functions in cryptography if we only have Boolean functions with good properties, how do we calculate those properties? Well first step we need to represent Boolean functions in certain ways and the first way we represent the Boolean function is a unique representation with a truth table, where we represent every possible value from all zeros all the way to all ones and that values contains the value of the function. Next unique representation is the Walsh Hadamard transform. It's a measure of correlation between our function f and all linear functions a times x. So basically with this Walsh Hadamard transform we are getting the distance from all possible functions from our function. The third unique representation is by algebraic normal form and what is it? Well, with this representation we represent our Boolean function by means of polynomial in F2. If we have this representation, we are able to clearly see some properties that we can use later in our calculation. So we set up to now three different representations. Are there more? Yes. There are more different representations. Some of those representations are unique, some are not unique. But for the core properties we need for our Boolean functions to be used in our stream ciphers, these three representations are sufficient. So let's talk about the properties we want our Boolean functions to have. First, we want our Boolean function to be balanced. A balanced Boolean function has the same number of zeros and ones at the output. What happens if a function is not balanced? Well, then it has some bias. If it has some bias, maybe we can use that bias for attack. So that's why we want to have our Boolean functions balanced. The second property we care about is the non-linearity. It is the minimum hamming distance between a Boolean function and all affine functions, and the non-linearity of Boolean function is represented in terms of the Walsh Hadamard coefficients. There we first construct our Walsh Hadamard transform. We read the absolute value of the highest term in the Walsh Hadamard table and that value will define our non-linearity. The maximum non-linear functions are called bent functions. Unfortunately since bent functions are not balanced, we do not use them in cryptography despite they have the best possible non-linearity and we said we want our functions to have as high as possible non-linearity. The second property is the correlation immunity. So we say a Boolean function is correlation immune of order t if the output of the function is statistically independent of the combination of any t of its inputs. Next property is the algebraic degree. Algebraic degree of a Boolean function is defined as the number of variables in the largest product term of the functions algebraic normal form that has non-zero coefficient. So we see for some property like non-linearity, we used Walsh Hadamard representation for algebraic degree. Now we used algebraic normal form. This is why we need several different representations to express all the properties we require. The next property we require is algebraic immunity and we want algebraic immunity for Boolean function f is the lowest degree of non-zero function g from F2n into F2 for which f times g equals 0. So we want our function to have good value of algebraic immunity. Next, we want our function also to resist fast algebraic attacks. To resist fast algebraic attacks, we want as high as possible fast algebraic immunity. To define fast algebraic immunity, we require the previous knowledge. So we select the minimum value of either twice the algebraic immunity and the minimum of the degree of function g and of a function f times g, and here g is a function different from zero. So we see to obtain this property, we actually use the knowledge we already have of how to calculate some other properties. So we said now there is a number of properties that we care about, but why do we care about those properties? Well, each of those property will give us in a way resilience against some attack. So if we use our Boolean functions in stream ciphers in combinations with linear feedback shift registers, there are two standard types how we build those ciphers. We build them as filter generators or as combiner generators and there for filter generator, we require our function to be balanced with high non-linearity, with large algebraic degree, with larger algebraic immunity, large fast algebraic immunity, and in the case of combiner generator, we additionally want large correlation immunity. So why do we want this? Well we already said if a function is balanced, then it has the same number of zeros and ones because otherwise if there is more zeros than ones or vice-versa, the attacker would be able to distinguish a pair plain text, ciphertext or even a part of it from some other randomly chosen pair. The function needs to have large algebraic degree to resist against some attacks like Berlekamp-Massey attack. Therefore, we would ideally want the degree of our Boolean function to be close to n minus 1, where n is the size of the number of inputs for our Boolean function. If we want our Boolean function to resist fast correlation attack, well, then we also need high non-linearity. We already said the highest non-linearities for bent functions. But since bent functions are not balanced and we require balancedness, then we will select our Boolean functions to have the non-linearity as close as possible to the non-linearity of bent functions. Finally, for algebraic immunity, we would like algebraic immunity to be close to n half. If that's close to n half, we will have resilience against certain types of algebraic attacks and then we could actually see even a small difference of one between two values of algebraic immunity would actually make the algebraic attack complexity very different. If you remember we already said in the case of combining generators, we want high correlation immunity. Why? Well in that generator, we have n inputs of a linear feedback shift registers. Those are inputs and outputs of linear feedback shift register which are inputs for Boolean function and then there is a divide and conquer attack called correlation attack that forces us to have the function to be k-resilient for sufficiently large value of k. Otherwise someone could use the correlation of the values to mount the attack. So we said there is a number of properties and actually what we said now the several properties are highly important, but those properties are not the only ones. Actually there are many other properties. But even if we consider only these properties, could we obtain a Boolean function with all the properties at their maximum? Unfortunately, we cannot. For instance, let us consider Seigenthaler bound that tells us the correlation immunity must be less or equal to the size of Boolean function minus degree of Boolean function minus 1. What does this tell us? Well if we want high correlation immunity, it will mean our degree will be lower. If we went as high as possible degree, then our correlation immunity will be lower. So in the end, there is a trade-off. We need to decide what function we want to use and how can we get all the properties of course not at the optimal value, but at the values as good as possible in order to resist various attacks not just a single attack.