Using Bernstein-Vazirani algorithm to attack block ciphers
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 177030 (Why is no real title available?)
- scientific article; zbMATH DE number 1394295 (Why is no real title available?)
- scientific article; zbMATH DE number 1418246 (Why is no real title available?)
- A construction of a cipher from a single pseudorandom permutation.
- A quantum algorithm to approximate the linear structures of Boolean functions
- Breaking symmetric cryptosystems using quantum period finding
- Characterization of linear structures
- How to Construct Pseudorandom Permutations from Pseudorandom Functions
- On the Power of Quantum Computation
- Quantum Complexity Theory
- Quantum algorithms for testing and learning Boolean functions
- Quantum cryptography: public key distribution and coin tossing
- Quantum differential cryptanalysis
- Secure signatures and chosen ciphertext security in a quantum computing world
- Semantic security and indistinguishability in the quantum world
- Superposition attacks on cryptographic protocols
Cited in
(23)- A quantum related-key attack based on the Bernstein-Vazirani algorithm
- Quantum differential and linear cryptanalysis
- Quantum impossible differential attacks: applications to AES and SKINNY
- Quantum meet-in-the-middle attack on Feistel construction
- Breaking permutation-based pseudorandom cryptographic schemes using distributed exact quantum algorithms
- Models in quantum computing: a systematic review
- Zero-correlation linear analysis for block ciphers based on the Bernstein-Vazirani and Grover algorithms
- Simon's algorithm and symmetric crypto: generalizations and automatized applications
- Quantum forgery attacks on COPA, AES-COPA and marble authenticated encryption algorithms
- Quantum speed-up for multidimensional (zero correlation) linear distinguishers
- Improved BV-based quantum attack on block ciphers
- Homomorphic encryption of the \(k = 2\) Bernstein-Vazirani algorithm
- Quantum differential cryptanalysis
- Quantum circuit implementation and resource analysis of LBlock and LiCi
- Efficient detection of high probability statistical properties of cryptosystems via surrogate differentiation
- Post-quantum cryptosystems: open problems and solutions. Lattice-based cryptosystems
- A new post-quantum voting protocol based on physical laws
- Quantum algorithms for learning the algebraic normal form of quadratic Boolean functions
- Quantum key-recovery attack on Feistel constructions: Bernstein-Vazirani meet Grover algorithm
- Quantum security of grain-128/grain-128a stream cipher against HHL algorithm
- Quantum key recovery attacks on tweakable Even-Mansour ciphers
- Quantum algorithm for finding impossible differentials and zero-correlation linear hulls of symmetric ciphers
- Quantum attacks on beyond-birthday-bound MACs
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)
