Security Proofs in Number-theoretic Cryptography
Status
This project started in July 2008.
Researchers
Prof. Dr. Ueli Maurer, Cryptography & Information Security Group, ETH
Divesh Aggarwal, Cryptography & Information Security Group, ETH
Description
Public-key cryptographic techniques are used as the basis of essentially all cryptographic protocols, both in practical applications as well as in protocols studied in research, including identification protocols, bit commitment schemes, interactive proofs, payment systems, and secure multi-party computation.
The security of many public key cryptosystems is based on problems in computational number theory and algebra. The true computational complexity of these problems is not known. That is to say, they are believed to be intractable, although no proof of this is known. Some such public key cryptosystems based on problems in computational number theory have also been broken in the past. So, making progress towards proving security of these cryptosystems is of utmost importance. For this reason, various techniques of reducing computation problems that are widely believed to be hard to these problems have been studied in the literature.
Probably the two most fundamental problems in number-theoretic cryptography are to prove or disprove that breaking the RSA system is as hard as factoring integers and that breaking the Diffie-Hellman protocol is as hard as computing discrete logarithm. While the second problem has been solved to a large extent, the first problem is still wide open for general models of computation.
A promising solution is therefore to investigate reasonably restricted models of computation and to see if one can prove relevant lower bounds in them. The simplest case of such restricted model is the model that restricts the algorithms to the class of “generic algorithms” – that is algorithms which do not exploit the representation of the elements. As a part of the preliminary research in this project, we studied the RSA problem and its equivalence to factoring for generic ring algorithms.
The project aims at making progress towards proving the security of public key encryption schemes based on computational number theory and algebra. We will look at reasonable restricted models of computation and study the hardness of the problems underlying these encryption schemes in these models. As a future goal, we will try to provide new encryption schemes and prove their security in the restricted models of computation that have been studied in the literature.
Publications
Divesh Aggarwal and Ueli Maurer

Breaking RSA Generically is Equivalent to Factoring

Advances in Cryptology – EUROCRYPT 2009, Lecture Notes in Computer Science, Springer-Verlag, vol. 5479, pp. 36-53, Apr 2009