Paper 2024/643

Key-Homomorphic and Aggregate Verifiable Random Functions

Giulio Malavolta, Bocconi University, Max Planck Institute for Security and Privacy

A verifiable random function (VRF) allows one to compute a random-looking image, while at the same time providing a unique proof that the function was evaluated correctly. VRFs are a cornerstone of modern cryptography and, among other applications, are at the heart of recently proposed proof-of-stake consensus protocols. In this work we initiate the formal study of aggregate VRFs, i.e., VRFs that allow for the aggregation of proofs/images into a small di- gest, whose size is independent of the number of input proofs/images, yet it still enables sound verification. We formalize this notion along with its security properties and we propose two constructions: The first scheme is conceptually simple, concretely efficient, and uses (asymmetric) bilinear groups of prime order. Pseudorandomness holds in the random oracle model and aggregate pseudorandomness is proven in the algebraic group model. The second scheme is in the standard model and it is proven secure against the learning with errors (LWE) problem. As a cryptographic building block of independent interest, we introduce the notion of key homomorphic VRFs, where the verification keys and the proofs are endowed with a group structure. We conclude by discussing several applications of key-homomorphic and aggregate VRFs, such as distributed VRFs and aggregate proof-of-stake protocols.

Available format(s)
Public-key cryptography
Publication info
Contact author(s)
giulio malavolta @ hotmail it
2024-04-29: approved
2024-04-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Giulio Malavolta},
      title = {Key-Homomorphic and Aggregate Verifiable Random Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2024/643},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.