Efficient Noninteractive Certification of RSA Moduli and Beyond

Abstract

In many applications, it is important to verify that an RSA public key (N; e) speci es a
\npermutation over the entire space ZN, in order to prevent attacks due to adversarially-generated
\npublic keys. We design and implement a simple and e cient noninteractive zero-knowledge
\nprotocol (in the random oracle model) for this task. Applications concerned about adversarial
\nkey generation can just append our proof to the RSA public key without any other modi cations
\nto existing code or cryptographic libraries. Users need only perform a one-time veri cation of
\nthe proof to ensure that raising to the power e is a permutation of the integers modulo N. For
\ntypical parameter settings, the proof consists of nine integers modulo N; generating the proof
\nand verifying it both require about nine modular exponentiations.
\nWe extend our results beyond RSA keys and also provide e cient noninteractive zero-
\nknowledge proofs for other properties of N, which can be used to certify that N is suitable
\nfor the Paillier cryptosystem, is a product of two primes, or is a Blum integer. As compared to
\nthe recent work of Auerbach and Poettering (PKC 2018), who provide two-message protocols for
\nsimilar languages, our protocols are more e cient and do not require interaction, which enables
\na broader class of applications.