Cryptology Fourier Analysis of Boolean Maps

a7Hzq .#5r< kÜ\as TâÆK$ ûj(Ö2 ñw%h: Úk{4R f~`z8 ¤˜Æ+Ô „&¢Dø

Contents

1. The algebraic normal form [PDF]
2. The Walsh transformation [PDF]
3. Approximation by linear relations [PDF]
4. Approximation by linear structures [PDF]
5. Characterization of bent maps [PDF]

Here is the complete text as an PDF file. Furthermore:

• a program for the Walsh transformation,
• a program for the complete Fourier analysis of a Boolean map (including forms for calling it online [*]),
• analysis of the S-Boxes S₀ and S₁ of LUCIFER, synopsis,
• analysis of the S-boxes S₁, S₂, S₃, S₄, S₅, S₆, S₇, and S₈ of DES, synopsis,
• an overview over various interpretations of a bit vector.

[*] Due to a server update the online calls are temporarily disabled.

Introduction

Boolean functions and maps are of central importance in cryptology. They are the basic building blocks of bitblock and bitstream ciphers. An essential criterion of their usefulness is nonlinearity: The S-boxes for bitblock ciphers and the combiners of linear shift registers for bitstream ciphers should be as nonlinear as possible. What does that mean, and how can we measure nonlinearity?

In the 1990s cryptologists introduced several measures that complement each other in revealing hidden linearity. If a Boolean map is close to linear by such a measure, then there is an attack on the cipher system that uses this map as a building block. The most prominent examples are linear and differential cryptanalysis of bitblock ciphers and correlation analysis of bitstream ciphers.

The most important mathematical tool for the study of hidden linearity is the Walsh (or Hadamard) transform, the characteristic 2 special case of the discrete Fourier transform. Its systematic use leads to a uniform, elegant, and efficient treatment of nonlinearity. Although it is conceptually very simple, it is surprisingly powerful for theoretical as well as for practical purposes, it almost magically reduces many bit grubbing proofs from the original papers to a few lines. And it makes computing linear and differential profiles—or linear approximation tables and difference tables—an unmitigated pleasure.

This appendix gives a short, but complete exposition of the essential parts of the theory of nonlinearity of Boolean maps. It is a short version of a tutorial in German language that contains much more material and many examples. The German version is in the web under http://www.staff.uni-mainz.de/pommeren/Kryptologie/Bitblock/A_Nonlin/. It also contains a comprehensive bibliography.