Lorentz Center - Post-Quantum Cryptography and Quantum Algorithms from 5 Nov 2012 through 9 Nov 2012
  Current Workshop  |   Overview   Back  |   Home   |   Search   |     

    Post-Quantum Cryptography and Quantum Algorithms
    from 5 Nov 2012 through 9 Nov 2012


Post-Quantum Cryptography and Quantum Algorithms

November 5 - November 9, 2012

Description and aims of the workshop

The aim of the workshop was to look into alternative cryptosystems which also withstand attacks using quantum computers - computers which exploit quantum parallelism to solve some problems much more efficiently than is known to be possible on conventional computers, and thus shake up the landscape for computationally secure cryptography.

The workshop brought researchers from two different fields together: on one side cryptographers whose focus lies on cryptosystems running on conventional computers which are not broken by quantum algorithms and on the other side researchers in quantum computing who are investigating how to design cryptanalytic algorithms which can be run on quantum computers.

Format of the workshop

During the first three days there were five tutorial talks -- two on quantum computing and three on post-quantum systems (one each for those based on codes, lattices, and multivariate equations).  These ensured a solid basis for discussions across the boundaries of the two groups.  Spread over the whole week there were seven invited talks on latest results in the different areas. These talks were scheduled after the tutorials which served as introductions to their fields. Moreover, eight participants contributed short talks during the afternoon sessions.  The focus of the workshop lay on the working groups. Three groups worked on how to use quantum algorithms for cryptanalysis of cryptosystems based on codes, lattices, and multivariate-quadratic equations. The working groups exceeded our expectations with discussions lasting till after building closure and more demand for working group sessions than for presentation sessions. Many more discussions took place during coffee breaks, lunches, and the social event.  There is a wiki page which documents the whole week. Participants could edit it themselves and propose talks and document the discussions in the working groups.

Results of the workshop

It was very fruitful to bring both communities together, so researchers could learn about problems and challenges in quantum computing and post-quantum cryptography. During the breakout groups the algorithms currently under consideration in post-quantum cryptography were scrutinized under possible quantum cryptanalysis. For each of the three main lines of post-quantum cryptography research (code-based crypto, lattice-based crypto, multivariate-systems-based crypto) at least one working group was formed. The cross-pollination between the two communities worked out very well in that experts on the cryptosystems explained the currently best attack methods on conventional computers, the experts on quantum computing gave details on how the algorithms could be modified to run on a quantum computer, and then all members of the working group worked together to analyze and optimize the algorithms in the new setting. Grover's algorithm makes searching faster and this meant that some classical algorithms that gained their speed in load-balancing several smaller lists didn't gain as much as algorithms operating with one big list. As a result, the ranking within the different classical algorithms got changed in their quantum variants. Taking this a step further, some groups worked out new quantum algorithms beating the adaptations of classical algorithms. These results should not be seen as defeating post-quantum cryptography, rather on the contrary: The improvements to the attacks are of type that can be dealt with by slightly increasing the parameters in the cryptosystems and the new analysis supports the claims of cryptographers working on codes, lattices, and multivariates that there are alternative systems for the era with quantum computers.


The organizers would like to thank the Lorentz Center for the opportunity to host the workshop in Leiden. In particular, many thanks for the financial support and the personal guidance before and during the workshop by Ikram Cakir, Henriette Jensenius, and Mieke Schutte. We would also like to express our appreciation to our other generous sponsors, the European Network of Excellence in Cryptology ECRYPT-II (ICT-2007-216676) and the Institute for Quantum Computing at the University of Waterloo.


Scientific Organizers:

Tanja Lange (Technische Universiteit Eindhoven, Netherlands)

Michele Mosca (University of Waterloo and Perimeter Institute, Canada)

Christiane Peters (Technical University of Denmark, Denmark)