Efficient noninteractive certification of RSA moduli and beyond
Files
First author draft
Date
DOI
Authors
Goldberg, Sharon
Reyzin, Leonid
Sagga, Omar
Baldimtsi, Foteini
Version
OA Version
First author draft
Citation
Sharon Goldberg, Leonid Reyzin, Omar Sagga, Foteini Baldtimsi. "Efficient noninteractive certification of RSA moduli and beyond." IACR ePrint (Cryptology) Report, Volume 2018, Issue 057.
Abstract
In many applications, it is important to verify that an RSA public key (N; e) speci es a
permutation over the entire space ZN, in order to prevent attacks due to adversarially-generated
public keys. We design and implement a simple and e cient 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 modi cations
to existing code or cryptographic libraries. Users need only perform a one-time veri cation 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 e cient 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 e cient and do not require interaction, which enables
a broader class of applications.