Using Bernstein-Vazirani algorithm to attack block ciphers

Abstract: In this paper, we study applications of Bernstein-Vazirani algorithm and present several new methods to attack block ciphers. Specifically, we first present a quantum algorithm for finding the linear structures of a function. Based on it, we propose new quantum distinguishers for the 3-round Feistel scheme and a new quantum algorithm to recover partial key of the Even-Mansour construction. Afterwards, by observing that the linear structures of a encryption function are actually high probability differentials of it, we apply our algorithm to differential analysis and impossible differential cryptanalysis respectively. We also propose a new kind of differential cryptanalysis, called quantum small probability differential cryptanalysis, based on the fact that the linear structures found by our algorithm are also the linear structure of each component function. To our knowledge, no similar method was proposed before. The efficiency and success probability of all attacks are analyzed rigorously. Since our algorithm treats the encryption function as a whole, it avoid the disadvantage of traditional differential cryptanalysis that it is difficult to extending the differential path.

Review text

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.

Recommendations

Cites work

Cited in

(27)

This page was built for publication: Using Bernstein-Vazirani algorithm to attack block ciphers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2414939)