Paper 2021/217

Verifiable Random Functions with Optimal Tightness

David Niehues

Abstract

Verifiable random functions (VRFs), introduced by Micali, Rabin and Vadhan (FOCS’99), are the public-key equivalent of pseudorandom functions. A public verification key and proofs accompanying the output enable all parties to verify the correctness of the output. However, all known standard model VRFs have a reduction loss that is much worse than what one would expect from known optimal constructions of closely related primitives like unique signatures. We show that: 1. Every security proof for a VRF that relies on a non-interactive assumption has to lose a factor of Q, where Q is the number of adversarial queries. To that end, we extend the meta-reduction technique of Bader et al. (EUROCRYPT’16) to also cover VRFs. 2. This raises the question: Is this bound optimal? We answer this question in the affirmative by presenting the first VRF with a reduction from the non-interactive qDBDHI assumption to the security of VRF that achieves this optimal loss. We thus paint a complete picture of the achievability of tight verifiable random functions: We show that a security loss of Q is unavoidable and present the first construction that achieves this bound.

Note: fix typo and update reference to "Algebraic pseudorandom functions with improved efficiency from the augmented cascade" to point to the updated eprint-version instead of a university website.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in Pkc 2021
Keywords
public-key cryptographyverifiable random functionstightnessprovable securtiy
Contact author(s)
iacr-eprint @ davidniehues net
History
2022-04-21: revised
2021-03-02: received
See all versions
Short URL
https://ia.cr/2021/217
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/217,
      author = {David Niehues},
      title = {Verifiable Random Functions with Optimal Tightness},
      howpublished = {Cryptology ePrint Archive, Paper 2021/217},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/217}},
      url = {https://eprint.iacr.org/2021/217}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.