Breaking Symmetric Cryptosystems Using Quantum Period Finding
By Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, María Naya-Plasencia. Annual International Cryptology Conference, 2016
351 citations recorded by the source corpus.
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 $$\varOmega 2^{n/2}$$ queries in the classical setting, but when collisions happen with some hidden periodicity, they can be found with only On 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.
Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition
View Paper: https://www.semanticscholar.org/paper/aab85c66215c377f658f042d3c235f571e1aecbd
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Computer Vision and Pattern Recognition
Citations in the corpus
- Quantum technology for military applications (2021, background): “Further, there is active research on cryptoanalytic attacks upon symmetric key systems based on the structure present in symmetric cryptosystems, which can offer up to super-polynomial speedup [43].”