@inbook{22059,
  abstract     = {{Verifiable random functions (VRFs), introduced by Micali,
Rabin and Vadhan (FOCS’99), are the public-key equivalent of pseudo-
random functions. A public verification key and proofs accompanying the
output enable all parties to verify the correctness of the output. How-
ever, 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 adver-
sarial 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 ques-
tion 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.}},
  author       = {{Niehues, David}},
  booktitle    = {{Public-Key Cryptography – PKC 2021}},
  isbn         = {{9783030752477}},
  issn         = {{0302-9743}},
  title        = {{{Verifiable Random Functions with Optimal Tightness}}},
  doi          = {{10.1007/978-3-030-75248-4_3}},
  year         = {{2021}},
}