About the Algebraic Normal Form (ANF) of S-Box in DES

Question

I've thought up a way to represent the transformation of S-Box in DES by ANF. Let $x_i\;(1\le i\le 6)$ be the input of an S-Box, $y_i\;(1\le i\le 4)$ be the output, for example, then $$y_1= 1\oplus x_1\oplus\dots\oplus x_1x_5\oplus\dots\oplus x_3x_4x_5x_6\oplus\cdots$$ Here the "$\oplus$" is "xor" operation and the operation between two continuous inputs is "and". I've omitted many terms because it's too long.

(This paragraph is in the old version)I think this is a very basic problem so it must be researched by so many people. But I can't find related papers. Can someone explain the ANF researches on S-Box of DES or provide some resources for me? Thanks a lot.

This is an explict expression because the left side is a single output and the right side is a polynomial of inputs with degree at most 6.

In algebraic cryptanalysis, reaserchers always represent the relations between inputs and outputs in an implicit way, like $$f(x_1,x_2,x_3,x_4,x_5,x_6,y_1,y_2,y_3,y_4)=0$$ What I want to know is that are there any advantages or applications of explicit form compared with the implict form?

Answer 1

Prior to answering this question, I present a preface about ways of demonstrating a "boolean function". There are two broad ways of representing namely "Boolean form" and "polynomial form".

In the boolean form representation, the boolean function is shown in one of the ways of Truth table, d.n.f, or c.n.f. On the other side, the polynomial form representation of a boolean function can be represented in the ANF (Algebraic Normal Form) or WHT(Walsh Hadamard Transformation).

For highlighting the importance of this classification, we can mention that each way exhibits and extracts unique properties of a boolean function. But why this boolean function and its properties are important? Almost all the cryptographic transformations as SBoxes, PBoxes, and even round functions are a kind of boolean functions. Moreover, the majority of cryptographic elements can be described with them, and cryptanalysis methods take advantage of the properties of these boolean functions to reveal their weaknesses, as an example, we can mention the correlation property between inputs and outputs of an SBox.

Turning to ANF, ANF representation of a boolean function can be defined as:

This means: boolean function f consists of n variables which these variables can either 1 or 0 and the result of this function, as well, can be either 0 or 1. With respect to this definition, a boolean function consisting of 3 variables in ANF form could be:

              f(x1,x2,x3) = x1x2 + x2x1 + x1x3 

which we can easily sketch in our well-known learned schematic diagrams in high school as follows:

In this scheme, the domain consists of three different variables namely, x1, x2, and x3 which any can either 0 or 1 in the function f representation.

But how this ANF rule is defined?

As I told ANF or the other name of "positive polarity reed muller", is a way of showing a boolean function in a polynomial form with xor operator. Actually, this representation is with the presence of all linear combination of monomials. A simple way of clarifying this definition is as follows:

In this representation, each "a" variable can be either 1 or 0. For instance, the global form of a 2 variable boolean function can be defined as:

For example, we can show AND function in the ANF form as follows:

Here a0, a1 and a2 are 0 and a3 is 1.

Before we want to answer the question of why this form of representation is important, we should remark that the part in this representation form that is crucial for cryptographers are coefficients of the terms. As mentioned above example in the AND function ANF representation, the three coefficients a0, a1, and a2 are 0sand the only x1x2 term coefficient is 1.

Returning for explaining the importance of this representation, showing a boolean function with n number variables needs n different number minterms, however, in ANF form, this could be shown with fewer terms and also these few terms give a complete description of that boolean function.

The most important application of ANF form is describing SBoxes with a minimum number of logic elements. The result of this representation indicates the important SBoxes properties such as algebraic order, algebraic weight, linear and affine, completeness, and many others which are widely used in cipher designing and cryptanalysis.