Paper 2018/057

Efficient Noninteractive Certification of RSA Moduli and Beyond

Sharon Goldberg, Leonid Reyzin, Omar Sagga, and Foteini Baldimtsi


In many applications, it is important to verify that an RSA public key $(N,e)$ specifies a permutation over the entire space $Z_N$, 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. 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. We extend our results beyond RSA keys and also provide efficient noninteractive zero-knowledge proofs for other properties of $N$, which can be used to certify that $N$ is suitable for the Paillier cryptosystem, is a product of two primes, or is a Blum integer. As compared to the recent work of Auerbach and Poettering (PKC 2018), who provide two-message protocols for similar languages, our protocols are more efficient and do not require interaction, which enables a broader class of applications.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in ASIACRYPT 2019
RSAPaillierTrapdoor PermutationsNIZK
Contact author(s)
reyzin @ bu edu
2019-10-03: last of 3 revisions
2018-01-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sharon Goldberg and Leonid Reyzin and Omar Sagga and Foteini Baldimtsi},
      title = {Efficient Noninteractive Certification of RSA Moduli and Beyond},
      howpublished = {Cryptology ePrint Archive, Paper 2018/057},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.