Cryptology ePrint Archive: Report 2018/057

Certifying RSA Public Keys with an Efficient NIZK

Sharon Goldberg and Leonid Reyzin and Omar Sagga and Foteini Baldimtsi

Abstract: In many applications, it is important to verify that an RSA public key (N,e) specifies a permutation, in order to prevent attacks due to adversarially-generated public keys. We design and implement a simple and efficient noninteractive zero-knowledge protocol (in the random oracle model) for this task. The key feature of our protocol is compatibility with existing RSA implementations and standards. The protocol works for any choice of e. Applications concerned about adversarial key generation can just append our proof to the RSA public key without any other modifications to existing code or cryptographic libraries. Users need only perform a one-time verification of the proof to ensure that raising to the power e is a permutation of the integers modulo N. For typical parameter settings, the proof consists of nine integers modulo N; generating the proof and verifying it both require about nine modular exponentiations.

Category / Keywords: public-key cryptography / RSA, Trapdoor Permutations, NIZK

Date: received 12 Jan 2018, last revised 25 Mar 2018

Contact author: reyzin at bu edu

Available format(s): PDF | BibTeX Citation

Version: 20180325:214404 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]