# 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