Paper 2025/312

Traceable Verifiable Random Functions

Dan Boneh, Stanford University
Aditi Partap, Stanford University
Lior Rotem, Stanford University
Abstract

A threshold verifiable random function (threshold VRF) is a VRF where the evaluation key is secret shared among n parties, and a quorum of t parties is needed to evaluate the VRF. Threshold VRFs are used widely in practice in applications such as randomness beacons and deterministic wallets. Despite their long history, the question of accountability for leaking key shares in a threshold VRF has not been studied. Specifically, consider a set of f parties who use their key shares to create an evaluation box that lets anyone evaluate the VRF at any point in the domain of the VRF. When is less than the threshold , this box must also take as input additional evaluation shares. Our goal is to design a threshold VRF where there is a tracing algorithm that can trace any such box to the coalition of parties that created it, using only blackbox access to . The risk of tracing should deter the coalition from selling such a box. Questions in this vein were previously explored in the context of threshold decryption and secret sharing. Here we define and study traceability for a threshold VRF. Our traceable threshold VRF is built from a VRF based on Paillier encryption. The starting point for our tracing algorithm is the tracing technique of Boneh-Partap-Rotem (Crypto 2024) designed for tracing leaks in the context of secret sharing. However, there are multiple technical challenges in making this approach work, and we develop the necessary tools to overcome all these challenges. The end result is a threshold VRF with a provably secure tracing algorithm.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
TraceabilityVerifiable Random Functionsthreshold VRFs
Contact author(s)
dabo @ cs stanford edu
aditi712 @ cs stanford edu
lrotem @ cs stanford edu
History
2025-02-21: approved
2025-02-21: received
See all versions
Short URL
https://ia.cr/2025/312
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/312,
      author = {Dan Boneh and Aditi Partap and Lior Rotem},
      title = {Traceable Verifiable Random Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/312},
      year = {2025},
      url = {https://eprint.iacr.org/2025/312}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.