The Price of Verifiability: Lower Bounds for Verifiable Random Functions

Nicholas Brandt; Dennis Hofheinz; Julia Kastner; Akin Ünal

Paper 2022/762

The Price of Verifiability: Lower Bounds for Verifiable Random Functions

Nicholas Brandt

, ETH Zurich

Dennis Hofheinz, ETH Zurich

Julia Kastner

, ETH Zurich

Akin Ünal, ETH Zurich

Abstract

Verifiable random functions (VRFs) are a useful extension of pseudorandom functions for which it is possible to generate a proof that a certain image is indeed the correct function value (relative to a public verification key). Due to their strong soundness requirements on such proofs, VRFs are notoriously hard to construct, and existing constructions suffer either from complex proofs (for function images), or rely on complex and non-standard assumptions. In this work, we attempt to explain this phenomenon. We show that for a large class of pairing-based VRFs, it is not possible to obtain short proofs and a reduction to a simple assumption simultaneously. Since the class of "consecutively verifiable" VRFs we consider contains in particular the VRF of Lysyanskaya and that of Dodis-Yampolskiy, our results explain the large proof size, resp. the complex assumption of these VRFs.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: VRFs Algebraic Group Model Generic Group Model Meta-Reduction Lower Bounds Impossibility Results
Contact author(s): nicholas brandt @ inf ethz ch
hofheinz @ inf ethz ch
julia kastner @ inf ethz ch
akin uenal @ inf ethz ch
History: 2022-06-16: approved; 2022-06-14: received; See all versions
Short URL: https://ia.cr/2022/762
License: CC BY

BibTeX

@misc{cryptoeprint:2022/762,
      author = {Nicholas Brandt and Dennis Hofheinz and Julia Kastner and Akin Ünal},
      title = {The Price of Verifiability: Lower Bounds for Verifiable Random Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2022/762},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/762}},
      url = {https://eprint.iacr.org/2022/762}
}