Quantum Procedures for Nested Search Problems

André Schrottenloher; Marc Stevens

doi:10.62056/aee0fhbmo

Quantum Procedures for Nested Search Problems

with Applications in Cryptanalysis

Authors

André Schrottenloher, Marc Stevens

André Schrottenloher

Univ Rennes, Inria, CNRS, IRISA, Rennes, France
andre dot schrottenloher at inria dot fr

Marc Stevens

CWI, Amsterdam, The Netherlands
marc dot stevens at cwi dot nl

Keywords: Quantum search Nested search Quantum cryptanalysis Amplitude amplification Symmetric cryptanalysis.

Abstract

In this paper we study search problems that arise very often in cryptanalysis: nested search problems, where each search layer has known degrees of freedom and/or constraints. A generic quantum solution for such problems consists of nesting Grover's quantum search algorithm or amplitude amplification (QAA) by Brassard et al., obtaining up to a square-root speedup on classical algorithms. However, the analysis of nested Grover or QAA is complex and introduces technicalities that in previous works are handled in a case-by-case manner. Moreover, straightforward nesting of l layers multiplies the complexity by a constant factor (pi/2)^l.

In this paper, we aim to remedy both these issues and introduce a generic framework and tools to transform a classical nested search into a quantum procedure. It improves the state-of-the-art in three ways: 1) our framework results in quantum procedures that are significantly simpler to describe and analyze; 2) it reduces the overhead factor from (pi/2)^l to sqrt(l); 3) it is simpler to apply and optimize, without needing manual quantum analysis. We give generic complexity formulas and show that for concrete instances, numerical optimizations enable further improvements, reducing even more the gap to an exact quadratic speedup.

We demonstrate our framework by giving a tighter analysis of quantum attacks on reduced-round AES.

References

[AA05]

Scott Aaronson and Andris Ambainis. Quantum Search of Spatial Regions. Theory Comput., 1(1):47–79, 2005. DOI: 10.4086/TOC.2005.V001A004

Google Scholar ePrint

[AAC⁺22]

Gorjan Alagic, Daniel Apon, David Cooper, Quynh Dang, Thinh Dang, John Kelsey, Jacob Lichtinger, Carl Miller, Dustin Moody, Rene Peralta, and others. Status report on the third round of the NIST post-quantum cryptography standardization process. US Department of Commerce, NIST, 2022. DOI: 10.6028/NIST.IR.8413-upd1

Google Scholar ePrint

[AKV23]

Andris Ambainis, Martins Kokainis, and Jevgenijs Vihrovs. Improved Algorithm and Lower Bound for Variable Time Quantum Search. 2023.

Google Scholar ePrint

[Amb10]

Andris Ambainis. Quantum Search with Variable Times. Theory Comput. Syst., 47(3):786–807, 2010. DOI: 10.1007/S00224-009-9219-1

Google Scholar ePrint

[Amb12]

Andris Ambainis. Variable time amplitude amplification and quantum algorithms for linear algebra problems. In STACS, volume 14 of LIPIcs, pages 636–647. 2012. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPICS.STACS.2012.636

Google Scholar ePrint

[ANS18]

Yoshinori Aono, Phong Q. Nguyen, and Yixin Shen. Quantum Lattice Enumeration and Tweaking Discrete Pruning. In ASIACRYPT (1), volume 11272 of LNCS, pages 405–434. 2018. Springer. DOI: 10.1007/978-3-030-03326-2_14

Google Scholar ePrint

[BBS05]

Eli Biham, Alex Biryukov, and Adi Shamir. Cryptanalysis of Skipjack Reduced to 31 Rounds Using Impossible Differentials. J. Cryptol., 18(4):291–311, 2005. DOI: 10.1007/S00145-005-0129-3

Google Scholar ePrint

[Ber10]

Daniel J. Bernstein. Grover vs. McEliece. In PQCrypto, volume 6061 of Lecture Notes in Computer Science, pages 73–80. 2010. Springer. DOI: 10.1007/978-3-642-12929-2_6

Google Scholar ePrint

[BHMT02]

Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53–74, 2002. DOI: 10.1090/conm/305/05215

Google Scholar ePrint

[BHN⁺19]

Xavier Bonnetain, Akinori Hosoyamada, María Naya-Plasencia, Yu Sasaki, and André Schrottenloher. Quantum Attacks Without Superposition Queries: The Offline Simon's Algorithm. In ASIACRYPT (1), volume 11921 of LNCS, pages 552–583. 2019. Springer. DOI: 10.1007/978-3-030-34578-5_20

Google Scholar ePrint

[BNS19]

Xavier Bonnetain, María Naya-Plasencia, and André Schrottenloher. Quantum Security Analysis of AES. IACR Trans. Symmetric Cryptol., 2019(2):55–93, 2019. DOI: 10.13154/TOSC.V2019.I2.55-93

Google Scholar ePrint

[CGJ19]

Shantanav Chakraborty, András Gilyén, and Stacey Jeffery. The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation. In ICALP, volume 132 of LIPIcs, pages 33:1–33:14. 2019. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPICS.ICALP.2019.33

Google Scholar ePrint

[DFJ13]

Patrick Derbez, Pierre-Alain Fouque, and Jérémy Jean. Improved Key Recovery Attacks on Reduced-Round AES in the Single-Key Setting. In EUROCRYPT, volume 7881 of Lecture Notes in Computer Science, pages 371–387. 2013. Springer. DOI: 10.1007/978-3-642-38348-9_23

Google Scholar ePrint

[DNS24]

Nicolas David, María Naya-Plasencia, and André Schrottenloher. Quantum impossible differential attacks: applications to AES and SKINNY. 2024.

Google Scholar ePrint

[DP20]

James H. Davenport and Benjamin Pring. Improvements to Quantum Search Techniques for Block-Ciphers, with Applications to AES. In SAC, volume 12804 of LNCS, pages 360–384. 2020. Springer. DOI: 10.1007/978-3-030-81652-0_14

Google Scholar ePrint

[DR02]

Joan Daemen and Vincent Rijmen. The Design of Rijndael: AES - The Advanced Encryption Standard. Information Security and Cryptography. Springer 2002.

Google Scholar ePrint

[FKL⁺00]

Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Michael Stay, David A. Wagner, and Doug Whiting. Improved Cryptanalysis of Rijndael. In FSE, volume 1978 of LNCS, pages 213–230. 2000. Springer. DOI: 10.1007/3-540-44706-7_15

Google Scholar ePrint

[Gid15]

Craig Gidney. Constructing Large Controlled Nots. https://algassert.com/circuits/2015/06/05/Constructing-Large-Controlled-Nots.html. 2015.

Google Scholar ePrint

[Gro96]

Lov K. Grover. A Fast Quantum Mechanical Algorithm for Database Search. In STOC, pages 212–219. 1996. ACM. DOI: 10.1145/237814.237866

Google Scholar ePrint

[HS20]

Akinori Hosoyamada and Yu Sasaki. Finding Hash Collisions with Quantum Computers by Using Differential Trails with Smaller Probability than Birthday Bound. In EUROCRYPT (2), volume 12106 of Lecture Notes in Computer Science, pages 249–279. 2020. Springer. DOI: 10.1007/978-3-030-45724-2_9

Google Scholar ePrint

[JNRV20]

Samuel Jaques, Michael Naehrig, Martin Roetteler, and Fernando Virdia. Implementing Grover Oracles for Quantum Key Search on AES and LowMC. In EUROCRYPT (2), volume 12106 of Lecture Notes in Computer Science, pages 280–310. 2020. Springer. DOI: 10.1007/978-3-030-45724-2_10

Google Scholar ePrint

[KLL15]

Shelby Kimmel, Cedric Yen-Yu Lin, and Han-Hsuan Lin. Oracles with Costs. In TQC, volume 44 of LIPIcs, pages 1–26. 2015. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPICS.TQC.2015.1

Google Scholar ePrint

[KLLN16a]

Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, and María Naya-Plasencia. Breaking Symmetric Cryptosystems Using Quantum Period Finding. In CRYPTO (2), volume 9815 of Lecture Notes in Computer Science, pages 207–237. 2016. Springer. DOI: 10.1007/978-3-662-53008-5_8

Google Scholar ePrint

[KLLN16b]

Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, and María Naya-Plasencia. Quantum Differential and Linear Cryptanalysis. IACR Trans. Symmetric Cryptol., 2016(1):71–94, 2016. DOI: 10.13154/TOSC.V2016.I1.71-94

Google Scholar ePrint

[KM10]

Hidenori Kuwakado and Masakatu Morii. Quantum distinguisher between the 3-round Feistel cipher and the random permutation. In ISIT, pages 2682–2685. 2010. IEEE. DOI: 10.1109/ISIT.2010.5513654

Google Scholar ePrint

[KMPM19]

Elena Kirshanova, Erik Mårtensson, Eamonn W. Postlethwaite, and Subhayan Roy Moulik. Quantum Algorithms for the Approximate k-List Problem and Their Application to Lattice Sieving. In ASIACRYPT, volume 11921 of LNCS, pages 521–551. 2019. Springer. DOI: 10.1007/978-3-030-34578-5_19

Google Scholar ePrint

[Knu98]

Lars Knudsen. DEAL - a 128-bit block cipher. Technical report number 151, Department of Informatics, University of Bergen. February 1998.

Google Scholar ePrint

[KT17]

Ghazal Kachigar and Jean-Pierre Tillich. Quantum Information Set Decoding Algorithms. In PQCrypto, volume 10346 of Lecture Notes in Computer Science, pages 69–89. 2017. Springer. DOI: 10.1007/978-3-319-59879-6_5

Google Scholar ePrint

[Kup13]

Greg Kuperberg. Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem. In TQC, volume 22 of LIPIcs, pages 20–34. 2013. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPICS.TQC.2013.20

Google Scholar ePrint

[Laa15]

Thijs Laarhoven. Search problems in cryptography. PhD thesis, PhD thesis, Eindhoven University of Technology, 2015.

Google Scholar ePrint

[LMvdP15]

Thijs Laarhoven, Michele Mosca, and Joop van de Pol. Finding shortest lattice vectors faster using quantum search. Des. Codes Cryptogr., 77(2-3):375–400, 2015. DOI: 10.1007/s10623-015-0067-5

Google Scholar ePrint

[MDRM10]

Hamid Mala, Mohammad Dakhilalian, Vincent Rijmen, and Mahmoud Modarres-Hashemi. Improved Impossible Differential Cryptanalysis of 7-Round AES-128. In INDOCRYPT, volume 6498 of Lecture Notes in Computer Science, pages 282–291. 2010. Springer. DOI: 10.1007/978-3-642-17401-8_20

Google Scholar ePrint

[Mon18]

Ashley Montanaro. Quantum-Walk Speedup of Backtracking Algorithms. Theory Comput., 14(1):1–24, 2018. DOI: 10.4086/TOC.2018.V014A015

Google Scholar ePrint

[NC16]

Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information (10th Anniversary edition). 2016.

Google Scholar ePrint

[Sho94]

Peter W. Shor. Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In FOCS, pages 124–134. 1994. IEEE Computer Society. DOI: 10.1109/SFCS.1994.365700

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/aee0fhbmo

History

Submitted: 2024-07-01
Accepted: 2024-09-02
Published: 2024-10-07

How to cite

André Schrottenloher and Marc Stevens, Quantum Procedures for Nested Search Problems. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/aee0fhbmo.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-3-9,
    author = "Schrottenloher, André and Stevens, Marc",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Quantum Procedures for Nested Search Problems",
    volume = "1",
    number = "3",
    date = "2024-10-07",
    year = "2024",
    issn = "3006-5496",
    doi = "10.62056/aee0fhbmo"
}

TY - JOUR
AU - Schrottenloher, André
AU - Stevens, Marc
PY  - 2024
TI  - Quantum Procedures for Nested Search Problems
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 3
DO  - 10.62056/aee0fhbmo
UR  - https://doi.org/10.62056/aee0fhbmo
AB  - <p>In this paper we study search problems that arise very often in cryptanalysis: nested search problems, where each search layer has known degrees of freedom and/or constraints. A generic quantum solution for such problems consists of nesting Grover's quantum search algorithm or amplitude amplification (QAA) by Brassard et al., obtaining up to a square-root speedup on classical algorithms. However, the analysis of nested Grover or QAA is complex and introduces technicalities that in previous works are handled in a case-by-case manner. Moreover, straightforward nesting of l layers multiplies the complexity by a constant factor (pi/2)^l.</p><p>In this paper, we aim to remedy both these issues and introduce a generic framework and tools to transform a classical nested search into a quantum procedure. It improves the state-of-the-art in three ways: 1) our framework results in quantum procedures that are significantly simpler to describe and analyze; 2) it reduces the overhead factor from (pi/2)^l to sqrt(l); 3) it is simpler to apply and optimize, without needing manual quantum analysis. We give generic complexity formulas and show that for concrete instances, numerical optimizations enable further improvements, reducing even more the gap to an exact quadratic speedup.</p><p>We demonstrate our framework by giving a tighter analysis of quantum attacks on reduced-round AES. </p>
ER  -

André Schrottenloher and Marc Stevens, Quantum Procedures for Nested Search Problems. IACR Communications in Cryptology, vol. 1, no. 3, Oct 07, 2024, doi: 10.62056/aee0fhbmo.