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.
09:30-10:30 Stacey Jeffery – Quantum Search Beyond Grover
I will describe several techniques for designing quantum algorithms for search problems based on random walks. No prior quantum algorithms knowledge will be necessary.
10:30-11:00 Coffee Break
11:00-12:00 Yu-Ao Chen – 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.
The security of symmetric cryptography is completely based on cryptanalysis: we only gain confidence in the security of a symmetric primitive through extensive and continuous scrutiny. It is therefore not possible to determine whether a symmetric primitive might be secure or not in a post-quantum world without first understanding how a quantum adversary could attack it. In this talk I will provide an overview of the subject and present some recent results on symmetric quantum cryptanalysis: a new efficient quantum collision search algorithm (joint work with A. Chailloux and M. Naya-Plasencia), and new efficient quantum algorithms for solving the K-xor problem (joint work with L. Grassi and M. Naya-Plasencia) and a very recent improvement that provides optimal merging algorithms. We will discuss some implications of these results in quantum-safe symmetric cryptography.
14:45-15:45 Vlad Gheorghiu – Non-Asymptotic Quantum Resource Estimation
Software engineers know well that asymptotically optimal algorithms can be outperformed by alternatives in practice; the O(n log n) time algorithm for integer multiplication is not necessarily the best algorithm for multiplying 64-bit integers. With that in mind: Does a known quantum algorithm for cryptanalysis outperform its classical counterpart in practice? E.g. does Grover search outperform exhaustive search in a pre-image attack on SHA-256? And if so, how much of an advantage does it provide? A satisfactory answer will depend on future technological progress. Nevertheless, we can begin to estimate the cost of particular quantum circuits using current proposals for quantum architectures. In this talk we will discuss the resources required for quantum computation using the surface code.
15:45-16:15 Coffee Break
16:15-17:15 Greg Kuperberg – Quantum Hidden Shift Algorithms 2.0
The dihedral hidden subgroup problem is equivalent to the hidden shift problem for a cyclic group, while the hidden shift problem for an arbitrary abelian group is generally similar. In 2003, I found a subexponential time algorithm for this problem, more precisely stretched exponential time. Later there were two variations, one due to Regev and the other due to me. These algorithms became more interesting when Childs, Jao, and Soukharev showed that they yield a quantum algorithm to find isogenies between elliptic curves. I will discuss my lesser known second algorithm, which deserves more attention because it supersedes my original algorithm as well as Regev's algorithm. The newer algorithm has a better constant in the exponent, it is expensive only in classical space and not quantum space, and it is tunable in various ways. The algorithm also breaks out of the representation theory of finite groups and instead uses a novel quantum data structure that can be called a "phase vector".
Building S101 (opposite of Darmstadium where Eurocrypt will take place)
- 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.