The DOI matches its Crossref record; 43 of the 43 references it cites were found in a registry or an index.
Breaking Symmetric Cryptosystems Using Quantum Period Finding
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
On the Power of Quantum Computation
Simon, D. R. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796298637 · Cited by 1,295
Hacking commercial quantum cryptography systems by tailored bright illumination
Lydersen, L., Wiechers, C., Wittmann, C., Elser, D., Skaar, J., & Makarov, V. (2010) · Nature Photonics · doi:10.1038/nphoton.2010.214 · Cited by 1,005
How to Construct Pseudorandom Permutations from Pseudorandom Functions
Luby, M., & Rackoff, C. (1988) · SIAM Journal on Computing · doi:10.1137/0217022 · Cited by 938
The Security of the Cipher Block Chaining Message Authentication Code
Bellare, M., Kilian, J., & Rogaway, P. (2000) · Journal of Computer and System Sciences · doi:10.1006/jcss.1999.1694 · Cited by 596
The Security and Performance of the Galois/Counter Mode (GCM) of Operation
McGrew, D. A., & Viega, J. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30556-9_27 · Cited by 522
Zhao, Y., Fung, C.-H. F., Qi, B., Chen, C., & Lo, H.-K. (2008) · Physical Review A · doi:10.1103/physreva.78.042333 · Cited by 511
Random Oracles in a Quantum World
Boneh, D., Dagdelen, Ö., Fischlin, M., Lehmann, A., Schaffner, C., & Zhandry, M. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-25385-0_3 · Cited by 449
Cited by
Advances in quantum cryptography
Pirandola, S., Andersen, U. L., Banchi, L., Berta, M., Bunandar, D., Colbeck, R., Englund, D., Gehring, T., Lupo, C., Ottaviani, C., et al. (2020) · Advances in Optics and Photonics · doi:10.1364/aop.361502 · Cited by 2,033
An Efficient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography
Chailloux, A., Naya-Plasencia, M., & Schrottenloher, A. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-70697-9_8 · Cited by 106
Self-citationPost Quantum Cryptography: A Review of Techniques, Challenges and Standardizations
Bavdekar, R., Jayant Chopde, E., Agrawal, A., Bhatia, A., & Tiwari, K. (2023) · 2023 International Conference on Information Networking (ICOIN) · doi:10.1109/icoin56518.2023.10048976 · Cited by 108
Quantum reversible circuit of AES-128
Almazrooie, M., Samsudin, A., Abdullah, R., & Mutter, K. N. (2018) · Quantum Information Processing · doi:10.1007/s11128-018-1864-3 · Cited by 75
Metadata
- Authors
- Kaplan, M., Leurent, G., Leverrier, A., & Naya-Plasencia, M.
- Venue
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg
- Published
- 2016
- Pages
- 207-237
- ISSN
- 0302-9743 (ISSN-L)
- 1611-3349
- OpenAlex
- W2284942299
- Cited by
- 336
- References
- 43
- FWCI
- 12.16
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Breaking Symmetric Cryptosystems Using Quantum Period Finding. https://app.cochat.ai/papers/10.1007/978-3-662-53008-5_8
- The paper
- Kaplan, M., Leurent, G., Leverrier, A., & Naya-Plasencia, M. (2016). Breaking Symmetric Cryptosystems Using Quantum Period Finding. Lecture Notes in Computer Science. https://doi.org/10.1007/978-3-662-53008-5_8
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.