Paper 2020/294
Public-Key Generation with Verifiable Randomness
Olivier Blazy and Patrick Towa and Damien Vergnaud
Abstract
We revisit the problem of proving that a user algorithm selected and correctly used a truly random seed in the generation of her cryptographic key. A first approach was proposed in 2002 by Juels and Guajardo for the validation of RSA secret keys. We present a new security model and general tools to efficiently prove that a private key was generated at random according to a prescribed process, without revealing any further information about the private key. In addition to formalizing randomness verifiability in key generation, which turns out to be highly non-trivial, we give a generic protocol for all key-generation algorithms based on probabilistic circuits and prove its security. We also propose a new protocol for factoring-based cryptography that we prove secure in the aforementioned model, as well as a practical instantiation. This latter relies on a new efficient zero-knowledge argument for the double discrete logarithm problem that achieves an exponential improvement in communication complexity compared to the state of the art, and is of independent interest.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Public-Key CryptographyRandomnessVerifiabilityZero-Knowledge
- Contact author(s)
- olivier blazy @ unilim fr,tow @ zurich ibm com,patrick towa @ gmail com,damien vergnaud @ lip6 fr
- History
- 2020-09-29: last of 4 revisions
- 2020-03-09: received
- See all versions
- Short URL
- https://ia.cr/2020/294
- License
-
CC BY