This workshop, sponsored by AIM and the NSF, will be devoted to developing and analyzing quantum algorithms to attack public-key cryptosystems. It is known that systems based on factorization of integers and discrete logarithms will be broken by quantum computers in polynomial time. Other systems, typically based on coding theory, hash functions, isogenies, lattices, or multivariate systems of equations, are considered secure against quantum attacks, meaning that the security scales at least super-polynomially and ideally exponentially with the system parameters. However, the exact security is largely unknown and there is a lack of exchange between researchers in post-quantum cryptography and those in quantum algorithms.
The aim of this workshop is to establish a more intensive collaboration between mathematicians working on designing and analyzing public-key cryptosystems and computer scientists working on quantum algorithms. Bringing together this expertise is essential to ensure that current proposals in post-quantum cryptography, an area working on alternatives to cryptography based on factorization and discrete logarithms with the aim to find algorithms that withstand attacks by quantum computers, actually get analyzed with the full power of both fields.
The main topics for the workshop are
- Exact security of ECC and RSA under quantum attacks
- Quantum algorithms for generic post-quantum systems
- Quantum algorithms for post-quantum systems with extra structure
This event will be run as an AIM-style workshop. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and parallel working sessions.