Linear structures in blockciphers
A blockcipher is a mapping \(F\colon \mathbb{F}^m_2\times \mathbb{F}^k_2\to \mathbb{F}^m_2\) (where \(\mathbb{F}^m_2\) and \(\mathbb{F}^k_2\) are called the message space and key space, respectively), such that for every \(\underbar{k}\) in \(\mathbb{F}^k_2\), the mapping \(F_{\underline{k}}(\cdot,\underline{k})\colon \mathbb{F}^m_2\to \mathbb{F}^m_2\) is one-to-one. A well-known example of a blockcipher is the Data Encryption Standard (DES) with message space \(\mathbb{F}_2^{64}\) and key space \(\mathbb{F}_2^{56}\). A blockcipher \(F\) can be used as a conventional cryptosystem only if it can not be broken by a fast known- or chosen plaintext attack, that means that for every plaintext \(\underbar{p}\) and corresponding ciphertext \(\underbar{c}\), it should be infeasible to solve the unknown key \(\underbar{k}\) from \(F\((\underbar{p},\underbar{k})=\underline{c}\), even if \(\underbar{p}\) is chosen in a special way. In the paper, the notion of a linear structure in a blockcipher is introduced. A blockcipher has a linear structure if there are subsets \(P\), \(K\) and \(C\) of plaintext bits, key bits and ciphertext bits of this blockcipher, respectively, with the following property: either for each plaintext and each key, a simultaneous change of all plaintext bits in \(P\) and key bits in \(K\) leaves the exclusive-or sum of the ciphertext bits in \(C\) unchanged; or for each plaintext and key, simultaneously changing all plaintext bits in \(P\) and all key bits in \(K\) causes a change of the exclusive-or sum of the ciphertext bits in \(C\). The class of linear structures includes, among other things, the complementation property of DES and structures previously introduced by \textit{J. A. Reeds} and \textit{J. L. Manferdelli} [Lect. Notes Comput. Sci. 196, 377--389 (1985; Zbl 1359.94620)] and \textit{D. Chaum} and the author [Crypto 1985, Lect. Notes Comput. Sci. 218, 199--211 (1986; Zbl 0592.94009)]. It is proved that for blockciphers with linear structures there exists known- and chosen plaintext attacks faster than the trivial attack of trying all keys. Further, linear structures in product ciphers (these are compositions of easily breakable blockciphers, so-called rounds) are investigated. A method is described to construct linear structures in the whole product cipher from linear structures in the separate rounds; linear structures in the product cipher that can be constructed in this way are called recursive over its rounds. It is proved that the product cipher DES has no other recursive linear structure than its complementation property. [For the entire collection see Zbl 0635.00022.]
- The enumeration of certain sets of block maps
- Algebraic nonlinearity and its applications to cryptography
- Linear frameworks for block ciphers
- Aperiodic propagation criteria for Boolean functions
- Structural cryptanalysis of SASAS
- Mathematical analysis for a dynamic cipher
- Pseudorandom Permutation Families over Abelian Groups
- scientific article; zbMATH DE number 3952651 (Why is no real title available?)
- CHOSEN-KEY ATTACKS ON A BLOCK CIPHER
- scientific article; zbMATH DE number 4079314 (Why is no real title available?)
- Complexity Theoretic Issues Concerning Block Ciphers Related to D.E.S.
- On the provable security of BEAR and LION schemes
- scientific article; zbMATH DE number 731849 (Why is no real title available?)
- Linear approximation of block ciphers
- A chosen plaintext linear attack on block cipher CIKS-1
- Block ciphers -- A survey
- The interpolation attack on block ciphers
- A family of trapdoor ciphers
- On the conjecture about the linear structures of rotation symmetric Boolean functions
- scientific article; zbMATH DE number 2154504 (Why is no real title available?)
- Information leakage of VGF2 structure
- On mixing linear transforms for block ciphers
- Factor structures of transformations
- A note on an infeasible linearization of some block ciphers
- On some properties of the curvature and nondegeneracy of Boolean functions
- scientific article; zbMATH DE number 7301720 (Why is no real title available?)
- From cryptanalysis to cryptographic property of a Boolean function
- SUBSTITUTION BLOCK CIPHERS WITH FUNCTIONAL KEYS
- On derivatives of polynomials over finite fields through integration
- Feistel schemes and bi-linear cryptanalysis (extended abstract)
- Non-linear Cryptanalysis Revisited: Heuristic Search for Approximations to S-Boxes
- Flaws of hypercube-like ciphers
- Generic framework for key-guessing improvements
- When does \(G(x)+\gamma \, \text{Tr}(H(x))\) permute \(\mathbb F_{p^n}\)?
- The linear structures and fast points of rotation symmetric Boolean functions
- Comment on ``Bounds on the number of functions satisfying the Strict Avalanche Criterion
- Searching hidden linear structures with quantum computer
- Distinguishing properties and applications of higher order derivatives of Boolean functions
- On self-equivalence encodings in white-box implementations
- The structured design of cryptographically good s-boxes
This page was built for publication: Linear structures in blockciphers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3809719)