Breaking symmetric cryptosystems using quantum period finding
From MaRDI portal
Publication:2829216
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
- 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?)
- 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
- 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 Rate-1 Authenticated Encryption from Pseudorandom Functions
- Parallelizable and authenticated online ciphers
- 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)- On tight quantum security of HMAC and NMAC in the quantum random oracle model
- Quantum attacks against BBB secure PRFs or MACs built from public random permutations
- Quantum key recovery attacks on tweakable Even-Mansour ciphers
- General linear group action on tensors: a candidate for post-quantum cryptography
- Quantum algorithms for the \(k\)-XOR problem
- Quantum attacks on Lai-Massey structure
- Breaking symmetric cryptosystems using quantum period finding
- Quantum algorithm design: techniques and applications
- Breaking tweakable enciphering schemes using Simon's algorithm
- A quantum distinguisher for 7/8-round SMS4 block cipher
- A cluster-based networking approach for large-scale and wide-area quantum key agreement
- Efficient quantum algorithms related to autocorrelation spectrum
- A new post-quantum voting protocol based on physical laws
- Synthesizing quantum circuits of AES with lower \(T\)-depth and less qubits
- Attacks on beyond-birthday-bound MACs in the quantum setting
- Quantum Demiric-Selcuk meet-in-the-middle attacks on reduced-round AES
- Quantum key-recovery on full AEZ
- On quantum slide attacks
- Breaking LWC candidates: sESTATE and Elephant in quantum setting
- QCB: efficient quantum-secure authenticated encryption
- Quantum reversible circuit of AES-128
- Evaluation of quantum cryptanalysis on SPECK
- On quantum ciphertext indistinguishability, recoverability, and OAEP
- Noisy Simon period finding
- Hidden shift quantum cryptanalysis and implications
- Tight bounds for Simon's algorithm
- Quantum collision attacks on AES-like hashing with low quantum random access memories
- Pholkos -- efficient large-state tweakable block ciphers from the AES round function
- Quantum attacks against type-1 generalized Feistel ciphers and applications to CAST-256
- Grover on \(SIMON\)
- Quantum attacks on some Feistel block ciphers
- Quantum resource estimation for FSR based symmetric ciphers and related Grover's attacks
- Quantum algorithms for learning Walsh spectra of multi-output Boolean functions
- Quantum cryptographic property testing of multi-output Boolean functions
- Using Bernstein-Vazirani algorithm to attack block ciphers
- Efficient slide attacks
- Quantum zero correlation linear cryptanalysis
- Beyond quadratic speedups in quantum attacks on symmetric schemes
- Quantum search for scaled hash function preimages
- Cryptanalysis against symmetric-key schemes with online classical queries and offline quantum computations
- Query complexity of generalized Simon's problem
- Quantum attacks on sum of Even-Mansour pseudorandom functions
- Post-quantum security on the Lai-Massey scheme
- Block encryption of quantum messages
- Quantum indistinguishability for public key encryption
- Quantum attacks without superposition queries: the offline Simon's algorithm
- A quantum related-key attack based on the Bernstein-Vazirani algorithm
- Quantum attacks on beyond-birthday-bound MACs
- Quantum key search with side channel advice
- Quantum generic attacks on key-alternating Feistel ciphers for shorter keys
- Quantum forgery attacks on COPA, AES-COPA and marble authenticated encryption algorithms
- Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts
- On quantum related-key attacks on iterated Even-Mansour ciphers
- Quantum-access-secure message authentication via blind-unforgeability
- Improved BV-based quantum attack on block ciphers
- Semantic security and indistinguishability in the quantum world
- Quantum key-length extension
- Finding hash collisions with quantum computers by using differential trails with smaller probability than birthday bound
- On Quantum Distinguishers for Type-3 Generalized Feistel Network Based on Separability
- On Quantum Chosen-Ciphertext Attacks and Learning with Errors
- An efficient quantum collision search algorithm and implications on symmetric cryptography
- Towards quantum large-scale password guessing on real-world distributions
- Quantum spin half algebra and generalized Megrelishvili protocol for confidentiality of digital images
- Complete analysis of Simon's quantum algorithm with additional collisions
- Quantum differential and linear cryptanalysis
- Post-quantum security of the Even-Mansour cipher
- Quantum cryptanalysis on contracting Feistel structures and observation on related-key settings
- Zero-correlation linear analysis for block ciphers based on the Bernstein-Vazirani and Grover algorithms
- Quantum query lower bounds for key recovery attacks on the Even-Mansour cipher
- Quantum cryptanalysis of OTR and OPP: attacks on confidentiality, and key-recovery
- Simon's algorithm and symmetric crypto: generalizations and automatized applications
- Grover on chosen IV related key attack against GRAIN-128a
- Sponge-based authenticated encryption: security against quantum attackers
- Finding many collisions via reusable quantum walks. Application to lattice sieving
- Quantum linearization attacks
- On the post-quantum security of classical authenticated encryption schemes
- A quantum-secure partial parallel MAC QPCBC
- Quantum security analysis of Rocca
- Improved attacks against reduced-round Whirlwind
- Breaking the Quadratic Barrier: Quantum Cryptanalysis of Milenage, Telecommunications’ Cryptographic Backbone
- Characterizing the qIND-qCPA (In)security of the CBC, CFB, OFB and CTR Modes of Operation
- Простейшие надгруппы регулярных представлений неабелевых $2$-групп с циклической подгруппой индекса $2$
- Dispelling myths on superposition attacks: formal security model and attack analyses
- Quantum algorithms for the Goldreich-Levin learning problem
- Quantum key-recovery attack on Feistel constructions: Bernstein-Vazirani meet Grover algorithm
- Applications of Simon's algorithm in quantum attacks on Feistel variants
- New Demiric–Selçuk meet-in-the-middle attacks on Misty and Feistel schemes
- Quantum circuit implementations of SM4 block cipher optimizing the number of qubits
- Quantum Key Recovery Attacks on 3-Round Feistel-2 Structure Without Quantum Encryption Oracles
- Relationships between quantum IND-CPA notions
- Automatic classical and quantum rebound attacks on AES-like hashing by exploiting related-key differentials
- Related-key differential cryptanalysis of GMiMC used in post-quantum signatures
- Quantum attacks: a view of data complexity on offline Simon's algorithm
- QCB is blindly unforgeable
- Ghidle: efficient large-state block ciphers for post-quantum security
- Quantum algorithm for finding impossible differentials and zero-correlation linear hulls of symmetric ciphers
- On security notions for encryption in a quantum world
- Exact distributed quantum algorithm for generalized Simon's problem
- Triangulating rebound attack on AES-like hashing
- Optimizing the depth of quantum implementations of linear layers
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)
