On UC-Secure Range Extension and Batch Verification for ECVRF

This technical report contains three important results. First, it describes a simple construction in the random-oracle model (ROM) that generically extends the range of a verifiable random function (VRF) specified as a UC functionality. We prove our construction UC secure and show that it can be used in Ouroboros to reduce the number of VRF evaluations (per slot) and VRF verifications (per block) from two to one at the price of additional hash-function evaluations.

As a second result, we show that the Elliptic Curve VRF (ECVRF) construction, whose standardization by the IETF is progressing, achieves the strong notion of UC security in the ROM.

Finally, we show how ECVRF can be tweaked and equipped with a batch-verification capability for increased efficiency. We formalize the security goal of batch verification in UC and formally prove the security of this construction in the ROM.