Quantum attacks against iterated block ciphers
From MaRDI portal
Abstract: We study the amplification of security against quantum attacks provided by iteration of block ciphers. In the classical case, the Meet-in-the-middle attack is a generic attack against those constructions. This attack reduces the time required to break double iterations to only twice the time it takes to attack a single block cipher, given that the attacker has access to a large amount of memory. More abstractly, it shows that security by composition does not achieve exact multiplicative amplification. We present a quantized version of this attack based on an optimal quantum algorithm for the Element Distinctness problem. We then use the generalized adversary method to prove the optimality of the attack. An interesting corollary is that the time-space tradeoff for quantum attacks is very different from what classical attacks allow. This first result seems to indicate that composition resists better to quantum attacks than to classical ones because it prevents the quadratic speedup achieved by quantizing an exhaustive search. We investigate security amplification by composition further by examining the case of four iterations. We quantize a recent technique called the dissection attack using the framework of quantum walks. Surprisingly, this leads to better gains over classical attacks than for double iterations, which seems to indicate that when the number of iterations grows, the resistance against quantum attacks decreases.
Recommendations
Cites work
- Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems
- Grover vs. McEliece
- scientific article; zbMATH DE number 5485488 (Why is no real title available?)
- Merkle puzzles in a quantum world
- Quantum Algorithms for Element Distinctness
- Quantum cryptanalysis of hash and claw-free functions
- Quantum lower bounds for the collision and the element distinctness problems
- Quantum Query Complexity of State Conversion
- Quantum Walk Algorithm for Element Distinctness
- Quantum Walk Based Search Algorithms
- Search via Quantum Walk
Cited in
(17)- Building quantum-one-way functions from block ciphers: Davies-Meyer and Merkle-Damgård constructions
- Element distinctness revisited
- Improved BV-based quantum attack on block ciphers
- Optimal merging in quantum k-xor and k-sum algorithms
- Evaluation of quantum cryptanalysis on SPECK
- Quantum attacks on some Feistel block ciphers
- Grover on \(SIMON\)
- Quantum key-recovery attack on Feistel constructions: Bernstein-Vazirani meet Grover algorithm
- Quantum search for scaled hash function preimages
- Quantum key-length extension
- Post-quantum security of the CBC, CFB, OFB, CTR, and XTS modes of operation
- Breaking symmetric cryptosystems using the offline distributed Grover-Meets-Simon algorithm
- Quantum circuit implementation and resource analysis of LBlock and LiCi
- Quantum impossible differential attacks: applications to AES and SKINNY
- Quantum resource estimation for FSR based symmetric ciphers and related Grover's attacks
- Quantum circuit implementations of SM4 block cipher based on different gate sets
- Improvements to quantum search techniques for block-ciphers, with applications to AES
This page was built for publication: Quantum attacks against iterated block ciphers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3381825)
