Post-Quantum Cryptography and Quantum Algorithms

The aim of this workshop is 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.

We would like to bring researchers from two different fields together: on one side cryptographers whose focus lies on cryptosystems running an 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.

So far only small quantum computers have been built. Realizing a large quantum computer which can pose a threat to the popular RSA cryptosystem and elliptic-curve-based cryptosystems is an enormous challenge. Currently it is unclear when physicists will succeed in building such machines. On the other hand many institutes and organizations are massively supporting research in quantum physics; very prominent amongst them the National Institute of Standards and Technology (NIST).

A movement has started in cryptography based on the idea that not everyone will have access to quantum computers when they are built. Everyday cryptography still will be carried out on conventional computing devices and the field of {\em post-quantum cryptography} aims at finding and analyzing cryptosystems so that they are ready to be used once quantum computers become a reality.

There are several candidates which are promising successors of elliptic-curve cryptography (ECC) and RSA. Most prominent amongst them are code-based cryptography, lattice-based cryptography, multivariate-equations cryptography, and hash-based cryptography.

Unlike RSA and ECC these cryptosystems have not shown any vulnerabilities to attacks with quantum computers and the best attacks on conventional computers and on quantum computers all take exponential time. However, in comparison to RSA and elliptic curves all those candidates suffer from drawbacks, for example code-based cryptography imposes bigger key sizes.  Research in post-quantum cryptography tries to evaluate problems and prepare for a future without RSA and elliptic-curve Diffie-Hellman.

A community of post-quantum-cryptography researchers has started to form -- initiated by a “PQCrypto” meeting in 2006 in Leuven.  Since then two more “PQCrypto” conferences have been held, namely in Cincinnati (2008) and Darmstadt (2010). The most recent conference took place in December 2011 in Taipei, and a fifth workshop is planned to take place in Limoges in the summer of 2013.  One goal of this workshop is to support forming this community by bringing together researchers in the area of post-quantum cryptography to discuss strategies and directions in cryptography.

At the same time researchers in quantum computing develop algorithms that would run on a quantum computer. Attacks on RSA and elliptic-curve cryptography were found in this community and some researchers have started to look into attacking post-quantum systems. But most uses of the label ``post-quantum'' have not yet been put to a serious test; more attention from the experts is required.

We think that it is important to bring both communities together, so researchers can learn about problems and challenges in quantum computing and post-quantum cryptography and the algorithms currently under consideration in post-quantum cryptography get the cryptanalytic scrutiny under quantum attacks that is necessary to build confidence. So the second goal of the proposed workshop is to make researchers in post-quantum cryptography and in quantum algorithms talk to each other and understand (and ideally solve) each other's problems.  We have reserved ample space in the schedule for joint research.  In order to give the discussions some structure we will collect open problems before and during the workshop. We will ask the invited speakers to contribute unsolved questions from their particular research area. We will contact the participants beforehand to encourage them to bring open problems. Based on this and on input from the discussions after the tutorials a list of topics to tackle during the rest of the week will be developed on Monday. The list might be updated later during the week.  In order to ensure that people from different areas talk to each other we will provide a couple of questions with the aim to stimulate the exchange between different research areas.  Examples are

* Can the results on quantum-attack immunity of lattices be extended to the lattices appearing in fully-homomorphic cryptography or how can these be attacked?

* What is the exact complexity of quantum attacks against the PQC system?

* Can we transport ideas of average-worst case reductions from lattice-based cryptography to code-based cryptography?

* How to secure post-quantum systems against side-channel attacks?