---
_id: '22059'
abstract:
- lang: eng
  text: "Verifiable random functions (VRFs), introduced by Micali,\r\nRabin and Vadhan
    (FOCS’99), are the public-key equivalent of pseudo-\r\nrandom functions. A public
    verification key and proofs accompanying the\r\noutput enable all parties to verify
    the correctness of the output. How-\r\never, all known standard model VRFs have
    a reduction loss that is much\r\nworse than what one would expect from known optimal
    constructions of\r\nclosely related primitives like unique signatures. We show
    that:\r\n1. Every security proof for a VRF that relies on a non-interactive\r\nassumption
    has to lose a factor of Q, where Q is the number of adver-\r\nsarial queries.
    To that end, we extend the meta-reduction technique\r\nof Bader et al. (EUROCRYPT’16)
    to also cover VRFs.\r\n2. This raises the question: Is this bound optimal? We
    answer this ques-\r\ntion in the affirmative by presenting the first VRF with
    a reduction\r\nfrom the non-interactive qDBDHI assumption to the security of VRF\r\nthat
    achieves this optimal loss.\r\nWe thus paint a complete picture of the achievability
    of tight verifiable\r\nrandom functions: We show that a security loss of Q is
    unavoidable and\r\npresent the first construction that achieves this bound."
author:
- first_name: David
  full_name: Niehues, David
  id: '36113'
  last_name: Niehues
citation:
  ama: 'Niehues D. Verifiable Random Functions with Optimal Tightness. In: <i>Public-Key
    Cryptography – PKC 2021</i>. Cham; 2021. doi:<a href="https://doi.org/10.1007/978-3-030-75248-4_3">10.1007/978-3-030-75248-4_3</a>'
  apa: Niehues, D. (2021). Verifiable Random Functions with Optimal Tightness. In
    <i>Public-Key Cryptography – PKC 2021</i>. Cham. <a href="https://doi.org/10.1007/978-3-030-75248-4_3">https://doi.org/10.1007/978-3-030-75248-4_3</a>
  bibtex: '@inbook{Niehues_2021, place={Cham}, title={Verifiable Random Functions
    with Optimal Tightness}, DOI={<a href="https://doi.org/10.1007/978-3-030-75248-4_3">10.1007/978-3-030-75248-4_3</a>},
    booktitle={Public-Key Cryptography – PKC 2021}, author={Niehues, David}, year={2021}
    }'
  chicago: Niehues, David. “Verifiable Random Functions with Optimal Tightness.” In
    <i>Public-Key Cryptography – PKC 2021</i>. Cham, 2021. <a href="https://doi.org/10.1007/978-3-030-75248-4_3">https://doi.org/10.1007/978-3-030-75248-4_3</a>.
  ieee: D. Niehues, “Verifiable Random Functions with Optimal Tightness,” in <i>Public-Key
    Cryptography – PKC 2021</i>, Cham, 2021.
  mla: Niehues, David. “Verifiable Random Functions with Optimal Tightness.” <i>Public-Key
    Cryptography – PKC 2021</i>, 2021, doi:<a href="https://doi.org/10.1007/978-3-030-75248-4_3">10.1007/978-3-030-75248-4_3</a>.
  short: 'D. Niehues, in: Public-Key Cryptography – PKC 2021, Cham, 2021.'
date_created: 2021-05-10T16:07:50Z
date_updated: 2022-01-06T06:55:24Z
ddc:
- '000'
department:
- _id: '558'
doi: 10.1007/978-3-030-75248-4_3
file:
- access_level: closed
  content_type: application/pdf
  creator: davnie
  date_created: 2021-05-10T16:09:17Z
  date_updated: 2021-05-10T16:09:17Z
  file_id: '22060'
  file_name: Niehues - 2021 - Verifiable Random Functions with Optimal Tightness.pdf
  file_size: 697361
  relation: main_file
file_date_updated: 2021-05-10T16:09:17Z
has_accepted_license: '1'
language:
- iso: eng
place: Cham
project:
- _id: '1'
  name: SFB 901
- _id: '4'
  name: SFB 901 - Project Area C
- _id: '13'
  name: SFB 901 - Subproject C1
publication: Public-Key Cryptography – PKC 2021
publication_identifier:
  isbn:
  - '9783030752477'
  - '9783030752484'
  issn:
  - 0302-9743
  - 1611-3349
publication_status: published
status: public
title: Verifiable Random Functions with Optimal Tightness
type: book_chapter
user_id: '36113'
year: '2021'
...