September 6 – 11 , 2015, Dagstuhl Seminar 15371
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)
1 / 3 >
For support, please contact
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 and Martin Roetteler and Nicolas Sendrier and Rainer Steinwandt
Dagstuhl Seminar Series
- 17401: "Quantum Cryptanalysis" (2017)
- 13371: "Quantum Cryptanalysis" (2013)
- 11381: "Quantum Cryptanalysis" (2011)
- Data Structures / Algorithms / Complexity
- Security / Cryptology
- Quantum computing
- Post-quantum cryptography
- Computational algebra
- Quantum circuit complexity
- Quantum hardware and resource estimation