Breaking Symmetric Cryptosystems using Quantum Period Finding

Abstract

Due to Shor's algorithm, quantum computers are a severe threat for public key cryptography. This motivated the cryptographic community to search for quantum-safe solutions. On the other hand, the impact of quantum computing on secret key cryptography is much less understood. In this paper, we consider attacks where an adversary can query an oracle implementing a cryptographic primitive in a quantum superposition of different states. This model gives a lot of power to the adversary, but recent results show that it is nonetheless possible to build secure cryptosystems in it. We study applications of a quantum procedure called Simon's algorithm (the simplest quantum period finding algorithm) in order to attack symmetric cryptosystems in this model. Following previous works in this direction, we show that several classical attacks based on finding collisions can be dramatically sped up using Simon's algorithm: finding a collision requires $\Omega (2^{n/2})$ queries in the classical setting, but when collisions happen with some hidden periodicity, they can be found with only $O(n)$ queries in the quantum model. We obtain attacks with very strong implications. First, we show that the most widely used modes of operation for authentication and authenticated encryption e.g. CBC-MAC, PMAC, GMAC, GCM, and OCB) are completely broken in this security model. Our attacks are also applicable to many CAESAR candidates: CLOC, AEZ, COPA, OTR, POET, OMD, and Minalpher. This is quite surprising compared to the situation with encryption modes: Anand et al. show that standard modes are secure with a quantum-secure PRF. Second, we show that Simon's algorithm can also be applied to slide attacks, leading to an exponential speed-up of a classical symmetric cryptanalysis technique in the quantum model.

31 pages, 14 figures

References in corpus (3)

• Hacking commercial quantum cryptography systems by tailored bright illumination
• Quantum homomorphic encryption for circuits of low $T$-gate complexity
• Quantum attacks against iterated block ciphers

Cited by in corpus (32)

• Advances in Quantum Cryptography
• Quantum Attacks without Superposition Queries: the Offline Simon's Algorithm
• Quantum-secure message authentication via blind-unforgeability
• Learning with Errors is easy with quantum samples
• Grover on SIMON
• Semantic Security and Indistinguishability in the Quantum World
• Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts
• A brief introduction to quantum algorithms
• Quantum forgery attacks on COPA,AES-COPA and marble authenticated encryption algorithms
• A Note on Quantum-Secure PRPs
• Quantum Simulation Logic, Oracles, and the Quantum Advantage
• Quantum Searchable Encryption for Cloud Data Based on Full-Blind Quantum Computation
• Quantum All-Subkeys-Recovery Attacks on 6-round Feistel-2* Structure Based on Multi-Equations Quantum Claw Finding
• New security notions and feasibility results for authentication of quantum data
• An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition
• A Unified Framework For Quantum Unforgeability
• Information compression via hidden subgroup quantum autoencoders
• Quantum Multi-Solution Bernoulli Search with Applications to Bitcoin's Post-Quantum Security
• Quantum impossible differential and truncated differential cryptanalysis
• Quantum Technology for Military Applications
• Learning Quantum Processes with Quantum Statistical Queries
• In-place implementation of Quantum-Gimli
• A quantum related-key attack based on Bernstein-Vazirani algorithm
• Quantum-access security of the Winternitz one-time signature scheme
• Quantum Key Recovery Attack on SIMON Block Cipher
• Quantum Miss-in-the-Middle Attack
• Linear Cryptanalysis through the Lens of Clauser-Horne-Shimony-Holt Game
• Quantum Indistinguishability for Public Key Encryption
• Efficient Quantum Algorithms related to Autocorrelation Spectrum
• General Linear Group Action on Tensors: A Candidate for Post-Quantum Cryptography
• Quantum Learning Algorithms and Post-Quantum Cryptography
• Using Bernstein-Vazirani Algorithm to Attack Block Ciphers