Paper 2022/1045

On UC-Secure Range Extension and Batch Verification for ECVRF

Christian Badertscher, Input Output (Switzerland)
Peter Gaži, Input Output (Slovakia)
Iñigo Querejeta-Azurmendi, Input Output (UK)
Alexander Russell, University of Connecticut, Input Output (US)

Verifiable random functions (Micali et al., FOCS'99) allow a key-pair holder to verifiably evaluate a pseudorandom function under that particular key pair. These primitives enable fair and verifiable pseudorandom lotteries, essential in proof-of-stake blockchains such as Algorand and Cardano, and are being used to secure billions of dollars of capital. As a result, there is an ongoing IRTF effort to standardize VRFs, with a proposed ECVRF based on elliptic-curve cryptography appearing as the most promising candidate. In this work, towards understanding the general security of VRFs and in particular the ECVRF construction, we provide an ideal functionality in the Universal Composability (UC) framework (Canetti, FOCS'01) that captures VRF security, and show that ECVRF UC-realizes this functionality. We further show how the range of a VRF can generically be extended in a modular fashion based on the above functionality. This observation is particularly useful for protocols such as Ouroboros since it allows to reduce the number of VRF evaluations (per slot) and VRF verifications (per block) from two to one at the price of additional (but much faster) hash-function evaluations. Finally, we study batch verification in the context of VRFs. We provide a UC-functionality capturing a VRF with batch-verification capability, and propose modifications to ECVRF that allow for this feature. We again prove that our proposal UC-realizes the desired functionality. We provide a performance analysis showing that verification can yield a factor-two speedup for batches with 1024 proofs, at the cost of increasing the proof size from 80 to 128 bytes.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. ESORICS 2022
ECVRF Batch Verifications Proof-of-Stake Provable Security Universal Composition
Contact author(s)
christian badertscher @ iohk io
peter gazi @ iohk io
querejeta azurmendi @ iohk io
alexander russell @ iohk io
2022-09-22: revised
2022-08-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Christian Badertscher and Peter Gaži and Iñigo Querejeta-Azurmendi and Alexander Russell},
      title = {On UC-Secure Range Extension and Batch Verification for ECVRF},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1045},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.