zbMATH — the first resource for mathematics

Algebraic attacks and decomposition of Boolean functions. (English) Zbl 1122.94041
Cachin, Christian (ed.) et al., Advances in cryptology – EUROCRYPT 2004. International conference on the theory and applications of cryptographic techniques, Interlaken, Switzerland, May 2–6, 2004. Proceedings. Berlin: Springer (ISBN 3-540-21935-8/pbk). Lecture Notes in Computer Science 3027, 474-491 (2004).
Summary: Algebraic attacks on LFSR-based stream ciphers recover the secret key by solving an overdefined system of multivariate algebraic equations. They exploit multivariate relations involving key bits and output bits and become very efficient if such relations of low degrees may be found. Low degree relations have been shown to exist for several well known constructions of stream ciphers immune to all previously known attacks. Such relations may be derived by multiplying the output function of a stream cipher by a well chosen low degree function such that the product function is again of low degree. In view of algebraic attacks, low degree multiples of Boolean functions are a basic concern in the design of stream ciphers as well as of block ciphers.
This paper investigates the existence of low degree multiples of Boolean functions in several directions: The known scenarios under which low degree multiples exist are reduced and simplified to two scenarios, that are treated differently in algebraic attacks. A new algorithm is proposed that allows to successfully decide whether a Boolean function has low degree multiples. This represents a significant step towards provable security against algebraic attacks. Furthermore, it is shown that a recently introduced class of degree optimized Maiorana-McFarland functions immanently has low degree multiples. Finally, the probability that a random Boolean function has a low degree multiple is estimated.
For the entire collection see [Zbl 1051.94003].

94A60 Cryptography
Full Text: DOI