Using Bernstein-Vazirani algorithm to attack block ciphers (Q2414939)

A series of block cipher attacks is introduced based on the quantum algorithm of Bernstein and Vazirani. In the style of Deutsch algorithm, given a linear map \(\phi: \mathrm{GF}_2^n\to\mathrm{GF}_2^n\), where \(\mbox{GF}_2\) is the primitive field of characteristic 2, Bernstein-Vazirani algorithm finds in an efficient way a vector \(\mathbf{x}\in\mathrm x{GF}_2^n\) such that \(\phi(\mathbf{y}) = \langle\mathbf{y}|\mathbf{x}\rangle\). As usual, \(\mathrm{GF}_2\) can be represented by the set of bits \(Q=\{0,1\}\). For a Boolean map \(f: Q^n\to Q\), a ``linear structure'' is a point \(\mathbf{x}\in Q^n\) such that \(\forall\mathbf{y}\in Q^n\), \(f(\mathbf{y}+\mathbf{x}) + f(\mathbf{y}) = f(\mathbf{x}) + f(\mathbf{0})\). The authors show that, by sampling a Boolean map a number of times polynomial with respect to \(n\), a linear structure is obtained using Bernstein-Vazirani algorithm. Besides, through a rather direct iteration, linear structures may be obtained for vector Boolean maps. With respect to block ciphers, given a one-to-one map \(P:Q^n\to Q^n\), the corresponding \textit{Feistel round} is the map \(Q^{2n}\to Q^{2n}\), \(\mathbf{z}_L\mathbf{z}_R\mapsto (P(\mathbf{z}_L)+\mathbf{z}_R)\mathbf{z}_L\). Given three permutations, provided by a cryptographically secure pseudorandom function, the corresponding 3-round Feistel is a secure pseudorandom permutation \(Q^{2n}\to Q^{2n}\). The authors introduce a polynomial time quantum distinguisher for 3-round Feistel maps using Bernstein-Vazirani algorithm. Indeed, given two permutations \(P_1,P_1\) a linear structure of the map \(\varepsilon\mathbf{x}\mapsto P_2(P_1(\mathbf{w}_{\varepsilon} + \mathbf{x})+\mathbf{w}_{\varepsilon})\), with \(\mathbf{w}_0\not=\mathbf{w}_1\), may allow to distinguish a 3-round Feistel involving \(P_1,P_2\). This is a different approach to a former quantum attack given by \textit{H. Kuwakado} and \textit{M. Morii} [Quantum distinguisher between the 3-round Feistel cipher and the random permutation. In: 2010 IEEE International Symposium on Information Theory Proceedings (ISIT), 2682--2685 (2010; doi:10.1109/ ISIT.2010.5513654]. Also, by recognition of linear structures, the introduced method may recover partial keys in the Even-Mansour construction of block-ciphers. Finally, the authors use thier method to render efficient differential cryptanalysis attacks, illustrating indeed the strength of quantum computing attacks. The paper is very well structured but the chosen pseudocode style used by the authors is hard to read.