Paper 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.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- RSATrapdoor PermutationsNIZK
- Contact author(s)
- reyzin @ bu edu
- History
- 2019-10-03: last of 3 revisions
- 2018-01-16: received
- See all versions
- Short URL
- https://ia.cr/2018/057
- License
-
CC BY