Traceable Verifiable Random Functions

Dan Boneh, Aditi Partap, Lior Rotem

TL;DR

This paper introduces "traceable threshold verifiable random functions" (traceable threshold VRFs), a new cryptographic primitive that allows for accountability in threshold VRF systems. They achieve this by designing a construction that can identify a coalition of parties who leak their secret key shares to create a "black box" for evaluating the VRF. This work is crucial for enhancing the security and trustworthiness of applications relying on threshold VRFs, such as randomness beacons and deterministic wallets.

What Problem Does This Paper Address?

Verifiable Random Functions (VRFs) are powerful tools for generating verifiable random outputs. Threshold VRFs extend this by distributing the secret key among multiple parties, requiring a quorum to perform evaluations. These are increasingly used in critical applications like blockchains for generating randomness. However, a significant security vulnerability in existing threshold VRFs is the lack of accountability. If a coalition of parties colludes and leaks their key shares to create an evaluation "box" that can be used to compute VRF outputs, there's currently no mechanism to identify these colluding parties. This lack of accountability creates a risk-free incentive for malicious behavior. This paper addresses this gap by introducing the concept of traceable threshold VRFs, aiming to deter such leaks by making it possible to identify the responsible parties.

Methods

The authors propose a novel construction for traceable threshold VRFs based on Paillier encryption. Their approach builds upon existing work on traitor tracing for secret sharing and threshold decryption. Key technical innovations include:

  • Formalizing Traceability: They define "traceable threshold VRFs" and introduce a tracing algorithm that, given a tracing key and black-box access to a "good" evaluation box, can identify the subset of corrupted parties.
  • Paillier Encryption Foundation: The core of their construction leverages the homomorphic properties of Paillier encryption to build a threshold VRF.
  • Overcoming Technical Challenges: They address two main challenges:
  • Non-Integral Domain: Standard list-decoding algorithms for Reed-Solomon codes, crucial for tracing, don't directly apply to the ring $\mathbb{Z}_{N^2}$ used in Paillier encryption. They adapt these techniques to work within this structure.
  • Validating Incorrect Shares: Their tracing algorithm requires feeding the evaluation box with potentially incorrect partial evaluations. They overcome this by encoding information in the tracing key that allows the tracer to forge valid proofs for these incorrect shares, making the tracing process undetectable to the box.
  • Bootstrapping for Many-Time Traceability: The initial construction is "one-time traceable" (requiring the adversary not to observe honest parties' partial evaluations before constructing the box). They then present two methods to bootstrap this into a "many-time traceable" scheme, which is more practical and doesn't have this restriction. These methods involve either using synchronized epochs or an "exponential decay" approach.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Accountability is Crucial: The paper highlights that accountability is a missing but essential security property for threshold VRFs, especially in applications where trust is paramount.
  • Leveraging Existing Tracing Techniques: The authors successfully adapt ideas from traitor tracing in secret sharing to the VRF setting, demonstrating the power of cross-pollinating cryptographic techniques.
  • The Power of "Trapdoors": The tracing key acts as a "trapdoor" that allows the tracer to forge proofs, which is essential for the tracing mechanism to work even when the evaluation box is imperfect.
  • Bridging Theory and Practice: The paper moves from theoretical definitions to concrete constructions, addressing practical challenges like the non-integral domain of $\mathbb{Z}_{N^2}$ and the need for many-time traceability.

Key Results

  • They present the first construction of a traceable threshold VRF with provable accountability guarantees.
  • Their construction is based on the Paillier encryption scheme and operates in the random oracle model.
  • They achieve both one-time and many-time traceability, with the latter being more practical for real-world applications.
  • The scheme satisfies standard VRF properties like correctness, uniqueness, and pseudorandomness, in addition to the new traceability notions.

Limitations and Future Work

  • One-Time Traceability (Base Scheme): The initial construction is one-time traceable, meaning it's not secure if corrupted parties observe honest parties' partial evaluations before creating the "box." The paper addresses this with bootstrapping methods.
  • Tracing Key Secrecy: For their constructions, the tracing key must remain secret, as its knowledge could allow an adversary to evade tracing. The authors suggest building traceable threshold VRFs that support public-key tracing as a future direction.
  • f ≥ t Case: The current work focuses on the case where the number of corruptions $f$ is less than the threshold $t$. The case where $f \ge t$ is left as future work.
  • Alternative Constructions: The authors suggest exploring constructions based on post-quantum secure assumptions.
  • VRFs as Signatures: They propose viewing VRFs as a type of signature and exploring traceable threshold signatures that might not require uniqueness.

Summary updated

BibTeX
@article{boneh2025traceable,
  author = {Dan Boneh and Aditi Partap and Lior Rotem},
  title = {{Traceable Verifiable Random Functions}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2025},
}

Loading related content...

Figure