QuAC: Quantum Algorithms for Cryptanalysis

Workshop co-located with Eurocrypt 2019 on Sunday May 19, 2019 in Darmstadt, Germany


That quantum computers are bad news for RSA and discrete logarithms gave rise to post-quantum cryptography, which is now under consideration for standardisation by NIST, ETSI, ISO and the IETF. A natural question, then, is how quantum computers fare against these post-quantum schemes. Here, so far, the main application is Grover’s algorithm for various exhaustive search steps within classical cryptanalytic algorithms.

This workshop will give an overview of the use of quantum algorithms in cryptanalysis beyond Grover to encourage the broader exploration of quantum algorithms for cryptanalysis. The program is comprised of invited talks from expert speakers who have worked in the development of quantum algorithms and their application in cryptanalysis. The goal is a summer-school-like format and we strongly encourage audience participation.

Speakers / Preliminary Schedule

08:30-09:30 Registration

09:30-10:30 Stacey Jeffery – Quantum Search Beyond Grover

10:30-11:00 Coffee Break

11:00-12:00 Xiao-shan Gao – Quantum Algorithms for Optimization over Finite Fields and Applications in Cryptanalysis

In this talk, we present quantum algorithms for two fundamental computation problems: solving polynomial systems and optimization over finite fields. The quantum algorithms can solve these problems with any given success probability and have complexities polynomial in the size of the input and the condition number of certain polynomial system related to the problem. So, we achieved exponential speedup for these problems when their condition numbers are small. We apply the quantum algorithm to the cryptanalysis of the stream cipher Trivum, the block cipher AES, the hash function SHA-3/Keccak, the multivariate public key cryptosystems, the lattice based cipher NTRU, and show that they are secure under quantum algebraic attack only if the condition numbers of the corresponding equation systems are large.

12:30-13:45 Lunch

13:45-14:45 María Naya-Plasencia – New Algorithms for Quantum Symmetric Cryptanalysis

14:45-15:45 Vlad Gheorghiu and John Schanck – Non-Asymptotic Quantum Resource Estimation

15:45-16:15 Coffee Break

16:15-17:15 Greg Kuperberg – Quantum Hidden Shift Algorithms 2.0






Martin R. Albrecht
Information Security Group, Royal Holloway, University of London, UK
Rachel Player
Sorbonne Université, CNRS, INRIA, Laboratoire d'Informatique de Paris 6, LIP6, Équipe PolSys, France
Information Security Group, Royal Holloway, University of London, UK


This event is supported by the PROMETHEUS H2020 Project.