International Association for Cryptologic Research

International Association
for Cryptologic Research


Public-Key Generation with Verifiable Randomness

Olivier Blazy
Patrick Towa
Damien Vergnaud
DOI: 10.1007/978-3-030-64837-4_4
Search ePrint
Search Google
Presentation: Slides
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. 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. 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.
Video from ASIACRYPT 2020
  title={Public-Key Generation with Verifiable Randomness},
  booktitle={Advances in Cryptology - ASIACRYPT 2020},
  author={Olivier Blazy and Patrick Towa and Damien Vergnaud},