Paper 2019/1271

Round-optimal Verifiable Oblivious Pseudorandom Functions From Ideal Lattices

Martin R. Albrecht, Alex Davidson, Amit Deo, and Nigel P. Smart


Verifiable Oblivious Pseudorandom Functions (VOPRFs) are protocols that allow a client to learn verifiable pseudorandom function (PRF) evaluations on inputs of their choice. The PRF evaluations are computed by a server using their own secret key. The security of the protocol prevents both the server from learning anything about the client's input, and likewise the client from learning anything about the server's key. VOPRFs have many applications including password-based authentication, secret-sharing, anonymous authentication and efficient private set intersection. In this work, we construct the first round-optimal (online) VOPRF protocol that retains security from well-known subexponential lattice hardness assumptions. Our protocol requires constructions of non-interactive zero-knowledge arguments of knowledge (NIZKAoK). Using recent developments in the area of post-quantum zero-knowledge arguments of knowledge, we show that our VOPRF may be securely instantiated in the quantum random oracle model. We construct such arguments as extensions of prior work in the area of lattice-based zero-knowledge proof systems.

Note: Full version following PKC 2021 acceptance

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in PKC 2021
oblivious pseudorandom functionlatticespost-quantum
Contact author(s)
martin albrecht @ royalholloway ac uk
adavidson @ lip pt
amit deo @ ens-lyon fr
nigel smart @ kuleuven be
2021-03-01: last of 3 revisions
2019-11-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Martin R.  Albrecht and Alex Davidson and Amit Deo and Nigel P.  Smart},
      title = {Round-optimal Verifiable Oblivious Pseudorandom Functions From Ideal Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1271},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.