Curious About Cryptographic Boolean Functions?

In order to have a good understanding of cryptographic Boolean functions, let's get started from scratch, that's, having a look at the very basic concepts. To begin with, all modern computers are composed of very basic logic circuits using very basic gates, called operators which only apply to binary numbers, in other words, 0 and 1. Each type of gate implements a Boolean operation. The finite field ${\mathbb F}_{2}=\{0,1\}$ is also called binary field, and it is of special interest because it is particularly efficient for implementation in hardware or on a binary computer. Using these gates, the rules of Boolean algebra may be applied to design circuits that perform a variety of tasks. For example, integrated circuits. Then, these circuits are all put together to build into more powerful modern computers. 

The logic gate exclusive-OR

Primarily, the minimum units of electronic devices are called cells. Each cell can have two status: high voltage and low voltage. High voltage stands for TRUE Boolean value and is represented by binary value 1, whereas low voltage stands for FALSE Boolean value and is represented by binary value 0. There are three fundamental logic gates or operations on binary numbers such as OR, AND and NOT, to connect the cells in terms of their assigned values and to create different sorts of logic circuits. Composite logic gates can be built and expressed in terms of the above-mentioned ones, and in this sense, there is a very particular composite logic gate that is heavily used in cryptography, this is the logic gate exclusive-or (XOR for short), denoted by $\oplus$, which is expressed as $A\oplus B=(A\lor B)\land(\bar{A} \lor \bar{B})$. 

Interestingly, the final outcome of $A \oplus B$ coincides with the modulo $2$ addition of the binary values of $A$ and $B$, over the finite field ${\mathbb F}_{2}=\{0,1\}$. Also, the logic gate OR also coincides with the multiplication operation over the finite field ${\mathbb F}_{2}$. Note that the basic logic gates $OR$ and $NOT$ can also be represented using the logic gates $XOR$ and $AND$, i.e., $A \lor B=A \oplus B \oplus (A \land B)$; $\bar{A}=A \oplus 1$. As a result, all these facts lead us to work using functions of logic circuits expressed in terms of $XOR$ and $AND$ operations, called Boolean functions, and the logic cells are represented by something called Boolean variables. Also, these two Boolean operations can be treated as operations over the binary field ${\mathbb F}_{2}$ and many of the results from finite fields can be used. 

Boolean functions are widely used in cryptography and cryptanalysis, as well as in many other areas. Particularly, Boolean functions are a core component in many stream ciphers, and any potential threat or attack to one of such models will often lead to the attacks to other models. For instance, they are used to develop pseudo-random generators in stream ciphers, S-boxes in block ciphers, and also to build error-correcting codes like Reed-Muller codes and Kerdock codes.

What exactly is a Boolean function?

Definition. A Boolean function $f$ in $n$ variables is a map from ${\mathbb F}_{2}^{n}$ to ${\mathbb F}_{2}$. The $(0,1)-sequence$ defined by $(f(x_0 ),f(x_1 ),… ,f(x_(2^n-1) )) $ is called the truth table of  $f$, where $x_0= (0,…,0,0),x_1  = (0,…,0,1),…,x_{2^n-1}  = (1,…,1,1)$, ordered by lexicographical order. The algebra of all Boolean functions on ${\mathbb F}_2^n$ will be denoted by $B_n$ (Stanica 2017).

\end{definition}

The function $f:{\mathbb F}_2^n\rightarrow {\mathbb F}_2$ is called a Boolean function in $n$ variables, where ${\mathbb F}_2^n$ is the n-dimensional vector space over the binary field ${\mathbb F}_2$. The function $f$ is written as $f(x)=f(x_1,x_2,x_3,…,x_n )$, that is, $x$ is a vector $(x_1,x_2,x_3,…,x_n )$. The vector made of all the outputs of $f(x)$ is called the truth table of $f(x)$, which has dimension $2^n$.

The possible values in ${\mathbb F}_2^n$ for the binary vector $x$ can be ordered as the binary representation of an integer, in other words, $x=(x_1,x_2,x_3,…,x_n )=\sum_{i=1}^{n} x_i 2^{n-1}$, the integer goes from $0$ to $2^n-1$, making the corresponding vector goes through all the elements in ${\mathbb F}_2^n$. Note that Boolean variables $x=(x_1,x_2,x_3,…,x_n )$ can be treated as probabilistic variables which take random values from ${\mathbb F}_2^n$ equally likely with uniform probability distribution. As a result, each $x_i$ is an independent variable over $\{0,1\}$, and a Boolean function $f(x)$ is also treated as a function in random variables.

There are arithmetical operations on Boolean functions such as the addition of $f(x)\oplus g(x)$ which is the XOR operation of their corresponding outputs, and also the multiplication $f(x)g(x)$ which is the multiplication of their corresponding outputs.

The function $f(x)$ is called an affine function if there exist $a_0,a_1,…,a_n \in {\mathbb F}_2^n$ such that $f(x)=a_0\oplus a_1 x_1\oplus …\oplus a_n x_n$, where $\oplus$ means modulo $2$ addition. Particularly, if $a_0  = 0$, it is called a linear function. If the set of all Boolean functions in $n$ variables is denoted by $B_n$, the set of linear ones by $L_n$, and $A_n$ is the set of affine ones, then we say that $L_n\subset A_n \subset B_n$.

That's all for the time being, stay tuned!