×

zbMATH — the first resource for mathematics

Boolean functions for cryptography and error-correcting codes. (English) Zbl 1209.94035
Crama, Yves (ed.) et al., Boolean models and methods in mathematics, computer science, and engineering. Cambridge: Cambridge University Press (ISBN 978-0-521-84752-0/hbk). Encyclopedia of Mathematics and its Applications 134, 257-397 (2010).
From the introduction: In both cryptographic and error correcting coding activities, Boolean functions (that is, functions from the vector space \(\mathbb F_2^n\) of all binary vectors of length \(n\), to the finite field with two elements \(\mathbb F_2\)) play roles:
\(\bullet\)
Every code of length \(2^n\), for some positive integer \(n\), can be interpreted as a set of Boolean functions, because every \(n\)-variable Boolean function can be represented by its truth table (an ordering of the set of binary vectors of length \(n\) being first chosen) and thus associated with a binary word of length \(2^n\), and vice verse. Important codes (Reed-Muller, Kerdock codes) can be defined this way as sets of Boolean functions.
\(\bullet\)
The role of Boolean functions in conventional cryptography is even more important: cryptographic transformations (pseudorandom generators in stream ciphers, S-boxes in block ciphers) can be designed by appropriate composition of nonlinear Boolean functions.
Despite the fact that Boolean functions are currently used in cryptography and coding with low numbers of variables, determining and studying those Boolean functions satisfying the desired conditions is not feasible through an exhaustive computer investigation: the number \(|{\mathcal{BF}}_n|= 2^{2^n}\) of \(n\)-variable Boolean functions is tool large when \(n\geq 6\). In Table 8.1, we give the values of this number for \(n\) ranging between 4 and 8.
The study of Boolean functions for constructing or studying codes or ciphers is essentially mathematical. But clever computer investigation is very useful to imagine or to test conjectures, and sometimes to generate interesting functions.
For the entire collection see [Zbl 1196.06001].

MSC:
94A60 Cryptography
PDF BibTeX XML Cite