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

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?

• Compact representation of DES S-boxes indeed has been studied, starting (AFAIK) with Eli Biham's A fast new DES implementation in software (1997, in proceedings of the fourth FSE conference). See also Matthew Kwan's website and paper Reducing the Gate Count of Bitslice DES (2000, IACR eprint archive). I can't tell how the form in the question ranks. – fgrieu Oct 29 '14 at 7:37
• If you are interested in most compact algebraic representations of DES S-boxes (which is not stated in the question, and why I made a comment rather than an answer), the best result is reportedly in the source code of john-the-ripper, I believe buried in the macros S1..S8 in john-1.8.0.tar.gz.tar file src/x86-64.S. – fgrieu Oct 29 '14 at 8:35
• Dear @fgrieu, I've read the report about Multiplicative Complexity. And I have some questions. 1.What's the meaning from page 69 to 72? Can you explain about the abbr. KP on page 72? 2. What are XL and XSL mean on page 80 and 84? Please do me a favor, thank you very much! – JeffLee Oct 30 '14 at 7:55
• KP stands for Known Plaintext(/Ciphertext pairs); the more are available to an attacker, the easier are the attacks. $\;$ XL is eXtended Linearization as discussed here. $\;$ XLS stands for eXtended Sparse Linearization. $\;$ I can't discuss these in a comment about a largely unrelated question. – fgrieu Oct 30 '14 at 8:09
• Dear @fgrieu. With your help, I've learned so much through the materials you gave. What I'm focusing on now is whether the ANF I described in the question is a new way to represent an S-box's transformation in algebraic cryptanalysis. Because in most of the materials, the authors represent it in an implicit form. I'll modify my question so I can accept your answer. Regards. – JeffLee Oct 31 '14 at 8:01

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.

• What is "WHT(Walsh Hadamard Transformation)" form of the "polynomial form"? I know two polynomial forms: multivariate (=ANF) and univariate (i.e. poly over $GF(2^n)$). – Fractalice Dec 26 '20 at 8:11