Breaking symmetric cryptosystems using quantum period finding
From MaRDI portal
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 queries in the classical setting, but when collisions happen with some hidden periodicity, they can be found with only 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.
Recommendations
Cites work
- A construction of a cipher from a single pseudorandom permutation.
- Adavanced slide attacks
- Breaking symmetric cryptosystems using quantum period finding
- CLOC: authenticated encryption for short input
- Computational Security of Quantum Encryption
- Efficient Instantiations of Tweakable Blockciphers and Refinements to Modes OCB and PMAC
- Fast software encryption. 21st international workshop, FSE 2014, London, UK, March 3--5, 2014. Revised selected papers
- How to Construct Pseudorandom Permutations from Pseudorandom Functions
- scientific article; zbMATH DE number 6492475 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 1759779 (Why is no real title available?)
- scientific article; zbMATH DE number 2086719 (Why is no real title available?)
- scientific article; zbMATH DE number 1418257 (Why is no real title available?)
- Introduction to post-quantum cryptography
- Merkle puzzles in a quantum world
- Non-interactive zero-knowledge proofs in the quantum random oracle model
- OMAC: one-key CBC MAC.
- OMD: a compression function mode of operation for authenticated encryption
- On the Power of Quantum Computation
- Parallelizable and authenticated online ciphers
- Parallelizable Rate-1 Authenticated Encryption from Pseudorandom Functions
- Pipelineable on-line encryption
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Post-quantum security of the CBC, CFB, OFB, CTR, and XTS modes of operation
- Probability distributions of correlation and differentials in block ciphers
- Progress in Cryptology - INDOCRYPT 2004
- Quantum Homomorphic Encryption for Circuits of Low T-gate Complexity
- Quantum-secure message authentication codes
- Random oracles in a quantum world
- Reinventing the travois: encryption/MAC in 30 ROM bytes
- Robust authenticated-encryption AEZ and the problem that it solves
- Secure signatures and chosen ciphertext security in a quantum computing world
- Semantic security and indistinguishability in the quantum world
- Superposition attacks on cryptographic protocols
- The security of the cipher block chaining message authentication code
- The software performance of authenticated-encryption modes
- Tweakable block ciphers
- Universal classes of hash functions
Cited in
(only showing first 100 items - show all)- Quantum algorithms for the \(k\)-XOR problem
- Hidden shift quantum cryptanalysis and implications
- Quantum reversible circuit of AES-128
- An efficient quantum collision search algorithm and implications on symmetric cryptography
- Quantum algorithm design: techniques and applications
- Quantum key-recovery on full AEZ
- Quantum key search with side channel advice
- On quantum related-key attacks on iterated Even-Mansour ciphers
- Breaking LWC candidates: sESTATE and Elephant in quantum setting
- Breaking tweakable enciphering schemes using Simon's algorithm
- Query complexity of generalized Simon's problem
- Quantum-access-secure message authentication via blind-unforgeability
- Quantum algorithms for learning Walsh spectra of multi-output Boolean functions
- Quantum cryptographic property testing of multi-output Boolean functions
- Quantum generic attacks on key-alternating Feistel ciphers for shorter keys
- A new post-quantum voting protocol based on physical laws
- Quantum zero correlation linear cryptanalysis
- A cluster-based networking approach for large-scale and wide-area quantum key agreement
- Improved BV-based quantum attack on block ciphers
- Attacks on beyond-birthday-bound MACs in the quantum setting
- Quantum indistinguishability for public key encryption
- Quantum Demiric-Selcuk meet-in-the-middle attacks on reduced-round AES
- Finding hash collisions with quantum computers by using differential trails with smaller probability than birthday bound
- On tight quantum security of HMAC and NMAC in the quantum random oracle model
- Tight bounds for Simon's algorithm
- Towards quantum large-scale password guessing on real-world distributions
- Quantum cryptanalysis on contracting Feistel structures and observation on related-key settings
- Evaluation of quantum cryptanalysis on SPECK
- Pholkos -- efficient large-state tweakable block ciphers from the AES round function
- Beyond quadratic speedups in quantum attacks on symmetric schemes
- Post-quantum security of the Even-Mansour cipher
- General linear group action on tensors: a candidate for post-quantum cryptography
- Efficient quantum algorithms related to autocorrelation spectrum
- Quantum attacks against type-1 generalized Feistel ciphers and applications to CAST-256
- Quantum attacks without superposition queries: the offline Simon's algorithm
- Quantum attacks on some Feistel block ciphers
- Quantum attacks on sum of Even-Mansour pseudorandom functions
- Quantum spin half algebra and generalized Megrelishvili protocol for confidentiality of digital images
- Cryptanalysis against symmetric-key schemes with online classical queries and offline quantum computations
- Efficient slide attacks
- Using Bernstein-Vazirani algorithm to attack block ciphers
- Using frequency analysis and Grover's algorithm to implement known ciphertext attack on symmetric ciphers
- Block encryption of quantum messages
- Complete analysis of Simon's quantum algorithm with additional collisions
- A quantum related-key attack based on the Bernstein-Vazirani algorithm
- Grover on \(SIMON\)
- Quantum algorithms for the Goldreich-Levin learning problem
- A quantum distinguisher for 7/8-round SMS4 block cipher
- Quantum key-recovery attack on Feistel constructions: Bernstein-Vazirani meet Grover algorithm
- Quantum attacks against BBB secure PRFs or MACs built from public random permutations
- Applications of Simon's algorithm in quantum attacks on Feistel variants
- Quantum search for scaled hash function preimages
- Quantum forgery attacks on COPA, AES-COPA and marble authenticated encryption algorithms
- Quantum collision attacks on AES-like hashing with low quantum random access memories
- Quantum key-length extension
- Relationships between quantum IND-CPA notions
- Breaking symmetric cryptosystems using quantum period finding
- Semantic security and indistinguishability in the quantum world
- Simon algorithm key-recovery attack on SIMON
- On Quantum Distinguishers for Type-3 Generalized Feistel Network Based on Separability
- Quantum differential and linear cryptanalysis
- On Quantum Chosen-Ciphertext Attacks and Learning with Errors
- Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts
- Простейшие надгруппы регулярных представлений неабелевых 2-групп с циклической подгруппой индекса 2
- Dispelling myths on superposition attacks: formal security model and attack analyses
- Quantum security analysis of Rocca
- New results on quantum boomerang attacks
- Quantum meet-in-the-middle attack on Feistel construction
- Breaking symmetric cryptosystems using the offline distributed Grover-Meets-Simon algorithm
- Quantum key recovery attacks on tweakable Even-Mansour ciphers
- QCB is blindly unforgeable
- Improved attacks against reduced-round Whirlwind
- Quantum circuit implementation and resource analysis of LBlock and LiCi
- Finding many collisions via reusable quantum walks. Application to lattice sieving
- Triangulating rebound attack on AES-like hashing
- Post-quantum security on the Lai-Massey scheme
- Quantum cryptanalysis of Farfalle and (generalised) key-alternating Feistel networks
- Quantum impossible differential attacks: applications to AES and SKINNY
- Optimizing the depth of quantum implementations of linear layers
- Synthesizing quantum circuits of AES with lower \(T\)-depth and less qubits
- Comments on ``Efficient classical simulation of the Deutsch-Jozsa and Simon's algorithms
- Automatic classical and quantum rebound attacks on AES-like hashing by exploiting related-key differentials
- Quantum linearization attacks
- QCB: efficient quantum-secure authenticated encryption
- Quantum resource estimation for FSR based symmetric ciphers and related Grover's attacks
- Simon's algorithm and symmetric crypto: generalizations and automatized applications
- Quantum attacks on Lai-Massey structure
- Sponge-based authenticated encryption: security against quantum attackers
- On quantum ciphertext indistinguishability, recoverability, and OAEP
- Quantum attacks on beyond-birthday-bound MACs
- Quantum attacks on PRFs based on public random permutations
- On security notions for encryption in a quantum world
- Related-key differential cryptanalysis of GMiMC used in post-quantum signatures
- On the post-quantum security of classical authenticated encryption schemes
- Quantum linear key-recovery attacks using the QFT
- Quantum Key Recovery Attacks on 3-Round Feistel-2 Structure Without Quantum Encryption Oracles
- Characterizing the qIND-qCPA (In)security of the CBC, CFB, OFB and CTR Modes of Operation
- Breaking the Quadratic Barrier: Quantum Cryptanalysis of Milenage, Telecommunications’ Cryptographic Backbone
- New Demiric–Selçuk meet-in-the-middle attacks on Misty and Feistel schemes
- Ghidle: efficient large-state block ciphers for post-quantum security
This page was built for publication: Breaking symmetric cryptosystems using quantum period finding
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2829216)
