The computational model of a quantum computer is fundamentally different from the classical model of computation. Quantum computers can solve certain problems efficiently, which, to the best of our knowledge, are infeasible on a classical computer. E.g., Shor’s celebrated period-finding algorithm, can be used to factorise huge numbers and compute huge discrete logarithms, thus breaking almost all currently used asymmetric cryptosystems. Such exploits assume ECLSQ (Error-Correcting Large-Scale Quantum) computers, which will not be available for many years (if ever). Nevertheless, with the current advent of the first NISQ (“Noisy Intermediate-Scale Quantum”) computers, it becomes increasingly important for computer scientists – and especially for cryptographers – to understand how quantum computers work, what quantum computers can do, and what they
can’t do.
Topics:
- classical bits and qubits
- classical and quantum states
- quantum gates and quantum circuits
- Deutsch’s problem and Simon’s problem
- Grover’s amplitude amplification: how to find a needle in a haystack
- the application of Grover's algorithm to symmetric cryptanalysis
- quantum Fourier analysis and Shor’s algorithm for period finding
- lower bounds: what quantum computers can't efficiently compute
The students will conceive knowledge about the state of research in quantum algorithms, with a focus on the application to attack cryptosystems. Given some guidance, they will be able to tackle current research problems in quantum cryptanalysis. |
