Verifiable Random Functions with Optimal Tightness

D. Niehues, in: Public-Key Cryptography – PKC 2021, Cham, 2021.

Download
Restricted Niehues - 2021 - Verifiable Random Functions with Optimal Tightness.pdf 697.36 KB
Book Chapter | Published | English
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.
Publishing Year
Book Title
Public-Key Cryptography – PKC 2021
LibreCat-ID

Cite this

Niehues D. Verifiable Random Functions with Optimal Tightness. In: Public-Key Cryptography – PKC 2021. Cham; 2021. doi:10.1007/978-3-030-75248-4_3
Niehues, D. (2021). Verifiable Random Functions with Optimal Tightness. In Public-Key Cryptography – PKC 2021. Cham. https://doi.org/10.1007/978-3-030-75248-4_3
@inbook{Niehues_2021, place={Cham}, title={Verifiable Random Functions with Optimal Tightness}, DOI={10.1007/978-3-030-75248-4_3}, booktitle={Public-Key Cryptography – PKC 2021}, author={Niehues, David}, year={2021} }
Niehues, David. “Verifiable Random Functions with Optimal Tightness.” In Public-Key Cryptography – PKC 2021. Cham, 2021. https://doi.org/10.1007/978-3-030-75248-4_3.
D. Niehues, “Verifiable Random Functions with Optimal Tightness,” in Public-Key Cryptography – PKC 2021, Cham, 2021.
Niehues, David. “Verifiable Random Functions with Optimal Tightness.” Public-Key Cryptography – PKC 2021, 2021, doi:10.1007/978-3-030-75248-4_3.
Main File(s)
File Name
Niehues - 2021 - Verifiable Random Functions with Optimal Tightness.pdf 697.36 KB
Access Level
Restricted Closed Access
Last Uploaded
2021-05-10T16:09:17Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar
ISBN Search