Breaking Symmetric Cryptosystems Using Quantum Period Finding
From MaRDI portal
Publication:2829216
DOI10.1007/978-3-662-53008-5_8zbMATH Open1391.94766arXiv1602.05973OpenAlexW2284942299MaRDI QIDQ2829216FDOQ2829216
Marc Kaplan, Anthony Leverrier, Gaëtan Leurent, María Naya-Plasencia
Publication date: 27 October 2016
Published in: Advances in Cryptology – CRYPTO 2016 (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1602.05973
symmetric cryptographypost-quantum cryptographyblock ciphersslide attackquantum attacksmodes of operation
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Universal classes of hash functions
- Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World
- Superposition Attacks on Cryptographic Protocols
- On the Power of Quantum Computation
- A construction of a cipher from a single pseudorandom permutation.
- How to Construct Pseudorandom Permutations from Pseudorandom Functions
- Progress in Cryptology - INDOCRYPT 2004
- The security of the cipher block chaining message authentication code
- Probability distributions of correlation and differentials in block ciphers
- Parallelizable and Authenticated Online Ciphers
- CLOC: Authenticated Encryption for Short Input
- Pipelineable On-line Encryption
- The Software Performance of Authenticated-Encryption Modes
- Parallelizable Rate-1 Authenticated Encryption from Pseudorandom Functions
- Efficient Instantiations of Tweakable Blockciphers and Refinements to Modes OCB and PMAC
- Fast Software Encryption
- Introduction to post-quantum cryptography
- Tweakable block ciphers
- Random Oracles in a Quantum World
- Quantum Homomorphic Encryption for Circuits of Low T-gate Complexity
- Fast software encryption. 21st international workshop, FSE 2014, London, UK, March 3--5, 2014. Revised selected papers
- Quantum-Secure Message Authentication Codes
- Breaking Symmetric Cryptosystems Using Quantum Period Finding
- Robust Authenticated-Encryption AEZ and the Problem That It Solves
- Non-Interactive Zero-Knowledge Proofs in the Quantum Random Oracle Model
- Merkle Puzzles in a Quantum World
- Computational Security of Quantum Encryption
- Reinventing the travois: Encryption/MAC in 30 ROM bytes
- Post-Quantum Security of the CBC, CFB, OFB, CTR, and XTS Modes of Operation
- Semantic Security and Indistinguishability in the Quantum World
- OMD: A Compression Function Mode of Operation for Authenticated Encryption
Cited In (only showing first 100 items - show all)
- Quantum algorithms for the \(k\)-XOR problem
- Noisy Simon period finding
- Evaluation of quantum cryptanalysis on SPECK
- Quantum algorithms for learning Walsh spectra of multi-output Boolean functions
- Quantum cryptographic property testing of multi-output Boolean functions
- Post-quantum security on the Lai-Massey scheme
- Quantum generic attacks on key-alternating Feistel ciphers for shorter keys
- Quantum attacks against BBB secure PRFs or MACs built from public random permutations
- Efficient quantum algorithms related to autocorrelation spectrum
- Quantum attacks against type-1 generalized Feistel ciphers and applications to CAST-256
- Quantum attacks on Lai-Massey structure
- Quantum algorithm design: techniques and applications
- Block encryption of quantum messages
- Breaking Symmetric Cryptosystems Using Quantum Period Finding
- Using Bernstein-Vazirani algorithm to attack block ciphers
- Attacks on beyond-birthday-bound MACs in the quantum setting
- Quantum Demiric-Selcuk meet-in-the-middle attacks on reduced-round AES
- Hidden shift quantum cryptanalysis and implications
- Grover on \(SIMON\)
- Quantum resource estimation for FSR based symmetric ciphers and related Grover's attacks
- Quantum search for scaled hash function preimages
- Quantum key-recovery on full AEZ
- Quantum-access-secure message authentication via blind-unforgeability
- Quantum reversible circuit of AES-128
- Quantum key search with side channel advice
- Complete analysis of Simon's quantum algorithm with additional collisions
- Quantum key-length extension
- On quantum ciphertext indistinguishability, recoverability, and OAEP
- Quantum zero correlation linear cryptanalysis
- Quantum forgery attacks on COPA, AES-COPA and marble authenticated encryption algorithms
- Synthesizing quantum circuits of AES with lower \(T\)-depth and less qubits
- Improved BV-based quantum attack on block ciphers
- Quantum attacks on some Feistel block ciphers
- Quantum spin half algebra and generalized Megrelishvili protocol for confidentiality of digital images
- Efficient slide attacks
- Beyond quadratic speedups in quantum attacks on symmetric schemes
- Towards quantum large-scale password guessing on real-world distributions
- Quantum cryptanalysis on contracting Feistel structures and observation on related-key settings
- Breaking LWC candidates: sESTATE and Elephant in quantum setting
- Pholkos -- efficient large-state tweakable block ciphers from the AES round function
- Breaking tweakable enciphering schemes using Simon's algorithm
- On tight quantum security of HMAC and NMAC in the quantum random oracle model
- A quantum distinguisher for 7/8-round SMS4 block cipher
- On Quantum Distinguishers for Type-3 Generalized Feistel Network Based on Separability
- Post-quantum security of the Even-Mansour cipher
- General linear group action on tensors: a candidate for post-quantum cryptography
- Quantum attacks on sum of Even-Mansour pseudorandom functions
- Finding hash collisions with quantum computers by using differential trails with smaller probability than birthday bound
- Quantum indistinguishability for public key encryption
- On Quantum Chosen-Ciphertext Attacks and Learning with Errors
- A new post-quantum voting protocol based on physical laws
- Query complexity of generalized Simon's problem
- Tight bounds for Simon's algorithm
- Quantum collision attacks on AES-like hashing with low quantum random access memories
- Semantic Security and Indistinguishability in the Quantum World
- QCB: efficient quantum-secure authenticated encryption
- Quantum key recovery attacks on tweakable Even-Mansour ciphers
- Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts
- A cluster-based networking approach for large-scale and wide-area quantum key agreement
- Quantum attacks on beyond-birthday-bound MACs
- A quantum related-key attack based on the Bernstein-Vazirani algorithm
- Quantum differential and linear cryptanalysis
- On security notions for encryption in a quantum world
- Comments on ``Efficient classical simulation of the Deutsch-Jozsa and Simon's algorithms
- Quantum meet-in-the-middle attack on Feistel construction
- Breaking permutation-based pseudorandom cryptographic schemes using distributed exact quantum algorithms
- Quantum attacks: a view of data complexity on offline Simon's algorithm
- Dispelling myths on superposition attacks: formal security model and attack analyses
- 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 security analysis of Rocca
- Simon's algorithm and symmetric crypto: generalizations and automatized applications
- Sponge-based authenticated encryption: security against quantum attackers
- Quantum linearization attacks
- Простейшие надгруппы регулярных представлений неабелевых $2$-групп с циклической подгруппой индекса $2$
- On quantum secure compressing pseudorandom functions
- Quantum attacks on hash constructions with low quantum random access memory
- Quantum speed-up for multidimensional (zero correlation) linear distinguishers
- Breaking symmetric cryptosystems using the offline distributed Grover-Meets-Simon algorithm
- Quantum attacks on PRFs based on public random permutations
- Related-key differential cryptanalysis of GMiMC used in post-quantum signatures
- QCB is blindly unforgeable
- Finding many collisions via reusable quantum walks. Application to lattice sieving
- On the post-quantum security of classical authenticated encryption schemes
- Improved attacks against reduced-round Whirlwind
- Optimizing the depth of quantum implementations of linear layers
- New results on quantum boomerang attacks
- Quantum linear key-recovery attacks using the QFT
- Quantum circuit implementation and resource analysis of LBlock and LiCi
- Quantum cryptanalysis of OTR and OPP: attacks on confidentiality, and key-recovery
- Grover on chosen IV related key attack against GRAIN-128a
- Automatic classical and quantum rebound attacks on AES-like hashing by exploiting related-key differentials
- Triangulating rebound attack on AES-like hashing
- Post-quantum security of tweakable Even-Mansour, and applications
- Quantum Key Recovery Attacks on 3-Round Feistel-2 Structure Without Quantum Encryption Oracles
- A quantum-secure partial parallel MAC QPCBC
- 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
- New Demiric–Selçuk meet-in-the-middle attacks on Misty and Feistel schemes
- Quantum algorithms for the Goldreich-Levin learning problem
Uses Software
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)
