Paper 2020/294

Public-Key Generation with Verifiable Randomness

Olivier Blazy, Patrick Towa, and Damien Vergnaud


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.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2020
Public-Key CryptographyRandomnessVerifiabilityZero-Knowledge
Contact author(s)
olivier blazy @ unilim fr
patrick towa @ gmail com
damien vergnaud @ lip6 fr
2020-09-29: last of 4 revisions
2020-03-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Olivier Blazy and Patrick Towa and Damien Vergnaud},
      title = {Public-Key Generation with Verifiable Randomness},
      howpublished = {Cryptology ePrint Archive, Paper 2020/294},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.