Moses Liskov and Robert D. Silverman
The underlying cryptographic security of a number of public key cryptographic protocols rests upon the difficulty of factoring large composite integers. The RSA system is one such example. Given current state of the art factoring algorithms, an integer which is the product of a limited number of primes is most difficult to factor when the primes are nearly equal. A zero knowledge proof that a number such as an RSA or similar key is the product of nearly equal primes would be extremely useful because it would enable the constructor of the key to prove to an outsider, such as a certifying authority, that the key is cryptographically secure. This would guard against later repudiation of the key by the user.
We give an interactive protocol for proving that a number such as an RSA key, which is the product of two primes, is the product of nearly equal primes. The soundness of the protocol is based on the assumption that discrete logs are difficult. We prove that the protocol statistically leaks no information beyond some point. We furthermore analyze the efficiency of the protocol. The protocol is easily extended to proving that a discrete log private key is securely constructed.
PostScript File (178K)
Zipped PostScript File (70K)
Adobe Acrobat (.pdf) File (208K)
Short certificate of secure RSA modulus
Wenbo Mao
PostScript File (263K)
Zipped PostScript File (103K)
Adobe Acrobat (.pdf) File (302K)
This site was last modified on June 22, 2000.
IEEE Home Page
IEEE Standards
P1363 Home Page