**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.

**Category / Keywords: **public-key cryptography / public-key cryptography, verifiable random functions, tightness, provable securtiy

**Original Publication**** (with minor differences): **IACR-PKC-2021

**Date: **received 26 Feb 2021

**Contact author: **iacr-eprint at davidniehues net

**Available format(s): **PDF | BibTeX Citation

**Version: **20210302:145729 (All versions of this report)

**Short URL: **ia.cr/2021/217

[ Cryptology ePrint archive ]