Paper 2023/223

Classical and Quantum Security of Elliptic Curve VRF, via Relative Indifferentiability

Chris Peikert, University of Michigan–Ann Arbor, Algorand, Inc.
Jiayu Xu, Oregon State University
Abstract

Verifiable random functions (VRFs) are essentially pseudorandom functions for which selected outputs can be proved correct and unique, without compromising the security of other outputs. VRFs have numerous applications across cryptography, and in particular they have recently been used to implement committee selection in the Algorand protocol. Elliptic Curve VRF (ECVRF) is an elegant construction, originally due to Papadopoulos et al., that is now under consideration by the Internet Research Task Force. Prior work proved that ECVRF possesses the main desired security properties of a VRF, under suitable assumptions. However, several recent versions of ECVRF include changes that make some of these proofs inapplicable. Moreover, the prior analysis holds only for *classical* attackers, in the random-oracle model (ROM); it says nothing about whether any of the desired properties hold against *quantum* attacks, in the quantumly accessible ROM. We note that certain important properties of ECVRF, like uniqueness, do *not* rely on assumptions that are known to be broken by quantum computers, so it is plausible that these properties could hold even in the quantum setting. This work provides a multi-faceted security analysis of recent versions of ECVRF, in both the classical and quantum settings. First, we motivate and formally define new security properties for VRFs, like non-malleability and binding, and prove that recent versions of ECVRF satisfy them (under standard assumptions). Second, we identify a subtle obstruction in proving that recent versions of ECVRF have *uniqueness* via prior indifferentiability definitions and theorems, even in the classical setting. Third, we fill this gap by defining a stronger notion called *relative indifferentiability*, and extend prior work to show that a standard domain extender used in ECVRF satisfies this notion, in both the classical and quantum settings. This final contribution is of independent interest and we believe it should be applicable elsewhere.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. CT-RSA'23
Keywords
Verifiable random functionsECVRFpost-quantum securityQROMindifferentiabilityFiat-Shamirnon-malleability
Contact author(s)
cpeikert @ alum mit edu
xujiay @ oregonstate edu
History
2023-02-20: approved
2023-02-18: received
See all versions
Short URL
https://ia.cr/2023/223
License
Creative Commons Attribution-NonCommercial-ShareAlike
CC BY-NC-SA

BibTeX

@misc{cryptoeprint:2023/223,
      author = {Chris Peikert and Jiayu Xu},
      title = {Classical and Quantum Security of Elliptic Curve {VRF}, via Relative Indifferentiability},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/223},
      year = {2023},
      url = {https://eprint.iacr.org/2023/223}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.