Abstract: That a quantum computer can be used to break some cryptographic schemes via Shor’s algorithm is a well-known fact. But which cryptographic schemes are that? Where are they used? How does a quantum computer actually solve a computational task like integer factorization so much faster than a regular computer? In this lecture, I will try to answer these questions. I will then go on to to discuss a number of approaches for constructing post-quantum cryptography. Finally, I will show how quantum computing theory is necessary not only for cryptanalysis, but also for security proofs of modern cryptographic schemes.
Biography: Christian Majenz obtained his master's degree in physics from the University of Freiburg, supervised by David Gross. He obtained his PhD from the University of Copenhagen under the supervision of Matthias Christandl, spending time at Caltech along the way. After a postdoc at the QuSoft Center and CWI in Amsterdam he moved back to Copenhagen where he is currently an Assistant Professor at the Technical University of Denmark. His main research interests are provable security for post-quantum cryptography, other quantum aspects of cryptography and representation-theoretic techniques in quantum theory.