Post-Quantum Cryptography and Quantum Algorithms

Last week, the Lorentz Center hosted a workshop on Post-Quantum Cryptography and Quantum Algorithms, which attracted both cryptographers and quantum algorithms people. The aim of this workshop was to "look into alternative cryptosystems which also withstand attacks using quantum computers" and to encourage cryptographers and quantum algorithms to work together on the two overlapping fields.

When cryptographers consider 'attacks using quantum computers', they mostly think of Shor's algorithm, which allows us to efficiently factor large numbers and solve the discrete logarithm problem on a quantum computer. Thus, Shor's algorithm gives us an exponential speedup over the best known classical algorithms. Cryptosystems that rely on the hardness of such problems, such as RSA and Elliptic Curve Cryptography, will be much less secure (read: broken) once we have a quantum computer. Because these systems are used widely in practice, we would like to find some alternatives that, as far as we know, are still secure against attacks using a quantum computer.

The alternatives discussed at the workshop were based on problems from the fields of lattices, error-correcting codes and multivariate quadratic equations. For each of these fields there was an introductory tutorial and one or two invited talks. Additionally, there were two tutorials and one invited talk on quantum algorithms. The tutorials on quantum algorithms were very interesting, because quantum algorithms are often no more than black boxes to cryptographers and these talks explained some of the 'magic' behind them.

The first quantum algorithms tutorial was given by Stephen Jordan. He gave a high-level overview about the kind of quantum algorithms that provide super-polynomial speed-ups, such as Shor's algorithm. These algorithms solve some variant of the Hidden Subgroup Problem, for various groups. He also described several groups for which we do not yet know how to solve the HSP. For example, if we could solve the HSP over the symmetric group, we would be able to solve the Graph Isomorphism problem using a quantum computer. Finally, he mentioned that we might be able to solve certain lattice problems if we were able to construct certain quantum states corresponding to a Gaussian or similar distribution over lattices. Constructing these states efficiently is an open problem.

The other tutorial on quantum algorithm was given by Frederic Magniez. It focused on applications of Grover's algorithm, which allows us to perform a search of an unsorted database in the square root of the size of the database. When used to find collisions in specific functions, this can sometimes even be improved to a cube root. Thus, this kind of quantum algorithm gives polynomial speedups. For symmetric cryptography, the existence of Grover's algorithm usually means that we need to double the length of the key if we want a comparable security level against a quantum computer. However, it is not always trivial to apply Grover's algorithm to other search problems. This lead to some interesting open problems, i.e., whether Grover could be used to speed up other classical algorithms in cryptanalysis.

Besides these talks, there was some room in the program for people to contribute their own talks. The remainder of the time was spent discussing open problems and drinking coffee. The group was split into three groups, one for lattices, one for error-correcting codes and one for multivariate quadratic equations. Each group had a few people from the area of quantum algorithms as well. For those interested, there is a wiki page with slides of the main talks, a list of open problems and a summary of the topics that were discussed by the three groups.