Project "Public Key Cryptography and Quantum Computing" (QPKC)

What we want

In this project, we want to study the impact of quantum computing on public key cryptography. In particular, we are going to analyse the security of current cryptosystems, their mathematical primitives, and padding schemes once quantum computers become available. We plan to quantify the relation between the cryptosystem's security parameters and the size (i.e., number of qubits) of quantum computers. We expect that the security parameters must be chosen significantly larger (e.g., more than 10,000 bits for RSA keys). Therefore, we want to determine when it is advantageous to use alternative arithmetic techniques like Schönhage-Strassen multiplication and provide efficient implementations of several cryptosystems.

We are also going to study new public key cryptosystem that presume quantum computers like the system proposed by Okamoto et al.

Rationale

The problems to factor integers and compute discrete logarithms are intractable with classical computers. The public key cryptosystems in widespread use nowadays are based on their hardness. In the last decade, however, several quantum algorithms were developed that solve these problems in quantum polynomial time. There are no quantum computers available, though, on which these algorithms could be implemented for input as large as, say, an RSA modulus.

A lot of research is going into the development of quantum computers. It may take some time, but larger and larger quantum computers will be built. We therefore have to establish how to choose security parameters depending on the size of available quantum computers. This involves counting the number of qubits and quantum gates on an ideal quantum computer as well as the additional cost incurred by error correction protecting against quantum noise.

For some cryptosystems - like the lattice based NTRU - it is not known how they are affected by quantum computers. In cooperation with our project "Lattices in Cryptology", we are studying such cryptosystems regarding their security against quantum attacks.

There are algorithms for integer multiplication that are asymptotically much more efficient than the "naive" approach. For example, the Schönhage-Strassen multiplication requires O(n log(n) loglog(n)) steps compared to O(n2). But in practice, the fast multiplication algorithms perform better than naive multiplication only if they operate on very large integers.
With the advent of quantum computers, it will most likely be necessary to choose the security parameters of established public key cryptosystems much larger than estimated by the Lenstra-Verheul heuristic [LV01], possibly making it worthwhile to implement the cryptosystems using fast multiplication.

Of course, quantum computers not only make existing cryptosystems attackable, but they also allow for new public key systems that are not feasible with classical computers. For example, the Okamoto-Tanaka-Uchiyama [OTU00] system presumes an efficient algorithm for computing discrete logarithms. We are going to consider the size of security parameters and the efficiency of such systems, since there are no such results known.

[LV01]
A. Lenstra, E. Verheul: Selecting Cryptographic Key Sizes.
Journal of Cryptology 14(4):255-293, 2001.
[OTU00]
T. Okamoto, K. Tanaka, S. Uchiyama: Quantum Public-Key Cryptosystems.
Proc. of CRYPTO 2000, pp.147-165, LNCS 1880, Springer-Verlag, 2000.

Who we are

The following persons are working on the QPKC-project

If you want to contact us, send mail to qpkc-project@cdc.informatik.tu-darmstadt.de
Note 1: This is not an open mailing list.
Note 2: No commercial email to this address, please.

Publications

Workshop

In 2006 we organized the workshop CLC2006 devoted to code and lattice based cryptography and it's analysis.

Internal Links

counter

Printerenglisch deutsche Flagge   Impressum