Ehsan Ebrahimi is a doctoral student at the Chair of Security and Theoretical Computer Science. He defended his doctoral thesis thesis “Post-Quantum Security in the Present of Superposition Queries” on January 21, supervised by Professor Dominique Unruh. Here is an overview of his work.
Quantum Computing. 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 much faster than any classical computer (computers that we use nowadays). An example of such problems is integer factorization.
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 algorithm that can be run in classical computers.
In contrast, there is a quantum algorithm that can solve the integer factorization really fast. (A large-scale quantum computer can run this algorithm and solve the problem).
Negative Impact on Cryptography. It sounds cool and interesting that a quantum computer would solve some problems faster than any classical computers. 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. We need to substitute the broken cryptographic constructions like RSA, with schemes that are secure even for an attacker that has a quantum computer. To do that, the first step is to study a mathematical problem that is hard to solve even for a quantum computer. (instead of factoring problem that is easy to solve for a quantum computer.)
The next step is to design a cryptographic scheme based on those quantum-hard problems (instead of RSA algorithm). And finally, we need to prove mathematically the security of
our scheme. Toward to standardize post-quantum security, National Institute of Standard and Technology (an agency of the United States Department of Commerce) initiated a competition in 2017.
Our Contribution. In this thesis, we focus on the security proofs against an attacker that has a quantum computer. We overcome some security challenges that may arise when we consider a quantum attacker in our security analysis for some cryptographic construction. Our result and ideas have been used in multiple submissions to the National Institute of Standard and Technology’s competition to propose a post-quantum secure public-key encryption scheme.
