Dagstuhl-Seminar 15371
Quantum Cryptanalysis
( 06. Sep – 11. Sep, 2015 )
(zum Vergrößern in der Bildmitte klicken)
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/15371
Organisatoren
- Michele Mosca (University of Waterloo, CA)
- Martin Roetteler (Microsoft Corporation - Redmond, US)
- Nicolas Sendrier (INRIA - Le Chesnay, FR)
- Rainer Steinwandt (Florida Atlantic University - Boca Raton, US)
Kontakt
- Andreas Dolzmann (für wissenschaftliche Fragen)
- Susanne Bach-Bernhard (für administrative Fragen)
Presse/News
Impacts
- Applying Grover’s Algorithm to AES : Quantum Resource Estimates : article in LNCS 9606 : pp. 29-43 - Grassl, Markus; Langenberg, Brandon; Rötteler, Martin; Steinwandt, Rainer - Berlin : Springer, 2016 - (Lecture notes in computer science ; 9606 : article).
- Circuit-extension handshakes for Tor achieving forward secrecy in a quantum world : article in Proceedings on Privacy Enhancing Technologies 2016 : pp. 219–236 - Schanck, John M.; Whyte, William; Zhang, Zhenfei - Berlin : de Gruyter, 2016 - (Proceedings on Privacy Enhancing Technologies 2016 ; article).
- Computational Security of Quantum Encryption - Alagic, Gorjan; Broadbent, Anne; Fefferman, Bill; Gagliardoni, Tommaso; Schaffner, Christian; St. Jules, Michael - Cryptology ePrint Archive, 2016. - 30 pp..
- Encryption faces quantum foe : Researchers urge readiness against attacks from future-generation computers : Online security braces for quantum revolution : article pp. 167-168 - Cesare, Chris - Indianapolis : Macmillan Publ., 2015. - (Nature ; Vol. 525).
- Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3 - Amy, Matthew; Matteo, Olivia Di; Gheorghiu, Vlad; Mosca, Michele; Parent, Alex; Schanck, John M. - Cornell University : arXiv.org, 2016. - 21 pp..
- Jetzt wappnen für den Quantenangriff : Artikel : 4 S. - Cesare, Chris - Spektrum der Wissenschaft Verlagsgesellschaft, 2015 - (Spektrum der Wissenschaft ; 2015).
- Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups - Rötteler, Martin - Cornell University : arXiv.org, 2016. - 18 pp..
- Report on Post-Quantum Cryptography - Chen, Lily; Liu, Yi-Kai; Moody, Dustin; Perlner, Ray; Smith-Tone, Daniel; Peralta, Rene; Jordan, Stephen - NIST National Institute of Standards and Technology, 2016 - (NISTIR ; 8105).
- Semantic Security and Indistinguishability in the Quantum World - Gagliardoni, Tommaso; Hülsing, Andreas; Schaffner, Christian - Cryptology ePrint Archive, 2016. - 37 pp..
Programm
While it has been known for some time that quantum computers could in principle undermine the security of many schemes—including RSA and elliptic curve based digital signatures—significantly less is known on actual estimates about the required resources that would be needed to carry out such quantum attacks. This leaves the providers and consumers of cryptographic methods in a fundamental dilemma, namely to estimate the impact of future quantum computers on the landscape of currently deployed cryptography and on the landscape of potential quantum-safe alternatives.
- Is it reasonable to assume that quantum computers pose a threat for currently deployed cryptography? What are concrete implications for the security level of currently deployed cryptographic schemes? In particular, does the threat of a quantum computer at the horizon require the change of key sizes now or in the near future?
- What is the time horizon until when a physical quantum computer capable of say breaking a discrete logarithm problem on a 163-bit binary elliptic curve will be available?
- To what extent are the proposed post-quantum cryptosystems truly resistant to quantum attacks? And what are appropriate key sizes and security parameters?
Questions like these are pertinent to this third installation of a quantum cryptanalysis seminar at Schloss Dagstuhl. We seek to leverage the full potential of quantum attacks on today’s cryptographic schemes and at the same time to identify plausible quantum computational assumptions for their replacements. We are particularly interested in
- Algorithmic Innovation: computational assumptions, recent trends and innovations in cryptography and quantum algorithms, new ideas to attack classical cryptography.
- Resource Estimation: quantify the quantum hardware resources required to carry out attacks against classical schemes. We intend to hold a “hardware day” devoted to circuit-level discussions and quantum hardware/implementation survey talks.
- The seminar aims to be interdisciplinary with participation of colleagues from classical cryptography and quantum computing. The general organization will follow its predecessors in that we plan to have ample time for discussions and personal interactions.
Press Reviews
- Online security braces for quantum revolution
Article published in "nature" on September 8, 2015 (in English) - Jetzt wappnen für den Quantenangriff
Translation of nature's article published in "Spektrum" on September 23, 2015 (in German)
It is known that quantum algorithms exist that jeopardize the security of most of our widely-deployed cryptosystems, including RSA and Elliptic Curve Cryptography. It is also known that advances in quantum hardware implementations are making it increasingly likely that large-scale quantum computers will be built in the near future that can implement these algorithms and devastate most of the world's cryptographic infrastructure. What is not known is an estimate of the resources that will be required to carry out these attacks -- or even whether other quantum attacks exist that have not yet been accounted for in our security estimates. In this seminar, we examined both computational resource estimates for meaningful quantum cryptanalytic attacks against classical (i.e.: conventional) cryptography, as well as the security of proposed quantum-safe cryptosystems against emerging quantum cryptanalytic attacks.
This seminar had a number of research highlights spanning the areas of implementations of quantum hardware and software, quantum algorithms, and post-quantum cryptography.
Implementations of quantum information processing were outlined to help contextualize the current state of quantum computation. Recent advances in the synthesis of efficient quantum circuits were presented, as well as an update on implementations - particularly in the domain of superconducting integrated circuits. Seminar participants were warned that traditional approaches to the modeling of quantum processors may be reaching an end, while the LIQUi|> software architecture for control of quantum hardware and simulation of quantum algorithms was unveiled. Challenges involving practical costs for error correction in systems with specific types of quantum memory (particularly quantum bucket brigade RAM architectures) were articulated.
In the domain of algorithmic advances, seminar participants demonstrated quantum improvements on the gapped group testing problem, as well as improvements on lattice sieving using nearest neighbour search algorithms. A discussion of how quantum computers can sometimes provide quadratic speedup for the differential cryptanalysis of symmetric-key cryptosystems was also presented. A quantum version of the unique-SVP algorithm was discussed, but it was found to have slightly worse performance than its' classical counterpart. For the purposes of improving our understanding quantum algorithms before large-scale quantum computers become available, a technique involving trapdoor simulation of quantum algorithms was proposed.
Seminar participants also gave a number of recent results in the domain of quantum-safe cryptography. These included a provably-secure form of Authenticated Key Exchange based on the Ring-Learning with Errors problem, a proposal for a quantum-safe method to prevent key leakage during key agreement failure stemming from invalid public keys, and updates on hash-based digital signatures. The EU PQCRYPTO project also presented some preliminary recommendations for post-quantum cryptography.
In the domain of code-based cryptography, it was demonstrated that assuming hardness of Niederreiter problem, CFS signatures are strongly existentially unforgeable in the random oracle model. A number of results related to lattice reduction were also presented, including an improvement on the BKZ lattice reduction algorithm, some lattice enumeration work involving factoring integers by CVP algorithms for the prime number lattice, and a reduction of gapped uSVP to the Hidden Subgroup Problem in dihedral groups. A LIQUi|> implementation of a quantum algorithm to extract hidden shift was also presented, as well as demonstration of instances of HSPs over dihedral group which can be efficiently solved on a quantum computer. Seminar participants also proposed alternative ways of thinking about the dihedral coset problem, including some hardness reductions. A very new result on finding a generator of a principal ideal was also debuted at this seminar and provoked lively and ongoing discussion among participants.
Other talks were presented on diverse and compelling topics including quantum-mechanical means for program obfuscation, and a means for quantum indistinguishability of some types of ciphertext messages. A presentation was also made about how standardization bodies and industry deal with information security and risk, and many discussions - both formal and informal - among participants began to deal with the applied challenges of developing and deploying quantum-safe information security standards and tools.
Overall, the success of this seminar can be observed not only through the quantity of new results, but also in their diversity and interdisciplinarity. While there exist venues for cryptography and cryptanalysis, for quantum algorithms, and for implementations of quantum information processing, it remains critical that these communities continue to come together to ensure rigorous and broad cryptanalysis of proposed quantum-safe cryptographic algorithms, and to share a well-defined mutual understanding of the quantum-computational resource requirements - and their present availability - for attacking both public and symmetric key cryptography. The security of the world's information depends on it.
The organizers (Michele Mosca, Martin Roetteler, Nicolas Sendrier, and Rainer Steinwandt) are grateful to the participants of this seminar and the team of Schloss Dagstuhl for an inspiring and productive third edition of this seminar series.
Creative Commons BY 3.0 Unported license
Michele Mosca, Martin Roetteler, Nicolas Sendrier, and Rainer Steinwandt
- Gorjan Alagic (University of Copenhagen, DK) [dblp]
- Aleksandrs Belovs (University of Latvia, LV) [dblp]
- Daniel J. Bernstein (University of Illinois - Chicago, US) [dblp]
- Jean-François Biasse (University of South Florida - Tampa, US) [dblp]
- Alexei Bocharov (Microsoft Corporation - Redmond, US) [dblp]
- Harry Buhrman (CWI - Amsterdam, NL) [dblp]
- André Chailloux (INRIA Rocquencourt, FR) [dblp]
- Jintai Ding (University of Cincinnati, US) [dblp]
- Hang Dinh (Indiana University South Bend, US) [dblp]
- Jürgen Eschner (Universität des Saarlandes, DE)
- Jennifer Katherine Fernick (University of Waterloo, CA)
- Tommaso Gagliardoni (TU Darmstadt, DE) [dblp]
- Markus Grassl (Universität Erlangen-Nürnberg, DE) [dblp]
- Sean Hallgren (Pennsylvania State University - University Park, US) [dblp]
- Peter Hoyer (University of Calgary, CA) [dblp]
- Andreas Hülsing (TU Eindhoven, NL) [dblp]
- Stacey Jeffery (CalTech - Pasadena, US) [dblp]
- Stavros Kousidis (BSI - Bonn, DE) [dblp]
- Thijs Laarhoven (TU Eindhoven, NL) [dblp]
- Bradley Lackey (University of Maryland - College Park, US) [dblp]
- Tanja Lange (TU Eindhoven, NL) [dblp]
- Anthony Leverrier (INRIA Rocquencourt, FR) [dblp]
- Yi-Kai Liu (NIST - Gaithersburg, US) [dblp]
- Alexander May (Ruhr-Universität Bochum, DE) [dblp]
- Kirill Morozov (Kyushu University - Fukuoka, JP) [dblp]
- Michele Mosca (University of Waterloo, CA) [dblp]
- Michael Naehrig (Microsoft Research - Redmond, US) [dblp]
- Maris Ozols (University of Cambridge, GB) [dblp]
- Ray Perlner (NIST - Gaithersburg, US) [dblp]
- Martin Roetteler (Microsoft Corporation - Redmond, US) [dblp]
- Christian Schaffner (University of Amsterdam, NL) [dblp]
- John M. Schanck (University of Waterloo, CA) [dblp]
- Claus Peter Schnorr (Goethe-Universität Frankfurt am Main, DE) [dblp]
- Nicolas Sendrier (INRIA - Le Chesnay, FR) [dblp]
- Dan J. Shepherd (CESG - Cheltenham, GB) [dblp]
- Daniel C. Smith-Tone (University of Louisville, US) [dblp]
- Fang Song (University of Waterloo, CA) [dblp]
- Rainer Steinwandt (Florida Atlantic University - Boca Raton, US) [dblp]
- Krysta Svore (Microsoft Corporation - Redmond, US) [dblp]
- Tsuyoshi Takagi (Kyushu University - Fukuoka, JP) [dblp]
- Enrico Thomae (operational services GmbH - Zwickau, DE) [dblp]
- Jean-Pierre Tillich (INRIA - Le Chesnay, FR) [dblp]
- Joop van de Pol (University of Bristol, GB) [dblp]
- Frank K. Wilhelm (Universität des Saarlandes, DE) [dblp]
- Bo-Yin Yang (Academica Sinica - Taipei, TW) [dblp]
Verwandte Seminare
- Dagstuhl-Seminar 11381: Quantum Cryptanalysis (2011-09-18 - 2011-09-23) (Details)
- Dagstuhl-Seminar 13371: Quantum Cryptanalysis (2013-09-08 - 2013-09-13) (Details)
- Dagstuhl-Seminar 17401: Quantum Cryptanalysis (2017-10-01 - 2017-10-06) (Details)
- Dagstuhl-Seminar 19421: Quantum Cryptanalysis (2019-10-13 - 2019-10-18) (Details)
- Dagstuhl-Seminar 21421: Quantum Cryptanalysis (2021-10-17 - 2021-10-22) (Details)
- Dagstuhl-Seminar 23421: Quantum Cryptanalysis (2023-10-15 - 2023-10-20) (Details)
- Dagstuhl-Seminar 25431: Quantum Cryptanalysis (2025-10-19 - 2025-10-24) (Details)
Klassifikation
- data structures / algorithms / complexity
- security / cryptology
Schlagworte
- Quantum computing
- post-quantum cryptography
- computational algebra
- quantum circuit complexity
- quantum hardware and resource estimation
