Supervisor:
prof Dominique Unruh

Opponents:
dr Frêdêric Dupuis (Loria, France)
dr Marc Kaplan (VeriQloud)

Summary:
Have you heard of Quantum Computers? Scientists and engineers are working to build a computer based on laws of nature (or quantum mechanics). This new machine (a quantum computer) can solve some computationally hard tasks, for instance integer factorization, much faster than any classical computer (computers that we use nowadays). The integer factorization problem is the problem of writing an integer number as a product of smaller integers. For instance given 15, the algorithm has to find 3 × 5. When a number is large, the integer factorization needs a long time to be solved using a classical computer. In contrast, a quantum computer can solve the integer factorization much faster. It sounds cool and interesting that we would solve some problems faster. However, we use a cryptosystem based on integer factorization, named RSA, to encrypt data. No one can learn about our data unless they can solve the factoring problem. The RSA encryption scheme is widely used cryptosystem. For instance Estonian ID card uses RSA algorithm for digital signatures and other services. Since a quantum computer can solve the factoring problem, the RSA scheme is not secure in the presence of a large-scale quantum computer. Post-quantum cryptography is an emerging discipline that deals with this issue. The goal is to have an encryption scheme that is secure even for a quantum attacker. The first step is to find a mathematical problem that is hard to solve even for a quantum computer. Then, the second step is to design a cryptographic scheme based on a quantum-hard problem. And finally, we need to prove mathematically the security of our scheme. In this thesis, we focus on the third step. We verify the security of some cryptosystems against a quantum attacker. We prove the security of some cryptographic constructions against a quantum adversary.