Abstract
For nearly 40 years, a fundamental result in cryptography known as Cleve’s Bound established that it is impossible to flip a fair coin among a group of participants if a majority are dishonest. This paper demonstrates that "delay functions"—computations that require a fixed amount of sequential time regardless of parallel processing power—are the essential mechanism for overcoming this limitation. The authors establish a formal equivalence: a fair coin-flipping protocol can be constructed if and only if delay functions exist.
Introduction: The Problem of Public Randomness
In distributed systems, generating "public randomness" for tasks like lotteries or leader elections is a high-stakes challenge. If a malicious actor can predict or influence the outcome, they can compromise the integrity of the entire system. In 1986, Richard Cleve proved an "impossibility result": in any protocol where participants attempt to agree on a random bit, a dishonest majority can always bias the outcome.
However, modern protocols like "Unicorn" appeared to bypass this limit by utilizing Delay Functions. These functions are designed to be easy to compute but require a minimum "wall-clock" time because they are inherently sequential. This research investigates whether delay functions are strictly necessary to beat Cleve’s bound and determines the minimum strength required for such functions to be effective.
Formalizing Sequentiality
To rigorously prove the necessity of delay functions, the researchers first had to define them formally. The core of their approach involves a sequentiality game that measures an adversary's ability to predict the output of a function faster than the intended evaluation time.
In this game, an adversary $\mathcal{A}_0$ first outputs some state $\alpha$. A random input $x$ is then sampled. A second adversary $\mathcal{A}_1$ attempts to compute the output $\tilde{y}$ using the input $x$ and the state $\alpha$. The function is considered sequential if no efficient adversary can successfully output $\tilde{y} = y$ (where $y$ is the true evaluation) significantly faster than the standard evaluation process.
Methodology and Proofs
The paper employs rigorous mathematical reductions to establish a two-pronged proof of equivalence:
- Necessity (The "Only If" part): The authors revisit Cleve’s original proof, which identifies specific strategies a cheater can use to bias a coin flip. They demonstrate that if a protocol successfully resists these strategies, it is because the cheater is unable to compute certain "default values" in time. These default values effectively constitute a weak delay function.
- Sufficiency (The "If" part): They show how to take a "weak" delay function—one that a cheater might still predict with some probability—and "boost" it into a strong, verifiable one.
- Hardness Amplification: To boost the delay function, they use a technique similar to parallel repetition. To ensure the result is verifiable without excessive overhead, they introduce a method where the output includes the "wire assignments" (internal states) of the circuit. This allows any party to verify the result in constant parallel time by checking the correctness of each gate.
Key Insights
- The "Default Value" Insight: The strategies Cleve used to prove impossibility serve as the blueprints for building a delay function. If a protocol is secure, the "default value" (the output an honest party would produce if others quit) must be computationally hard to find quickly.
- Time as a Unique Resource: Unlike memory or total computation, time is "publicly verifiable." Participants experience it at the same rate, and an adversary cannot "gain" time by simply adding more hardware mid-protocol.
- Weak to Strong: The authors prove that even a "weak" delay function—one that is only slightly hard to predict—is sufficient to build a fully secure Distributed Randomness Beacon (DRB).
Results and Future Work
The paper successfully proves that the existence of a coin-flipping protocol circumscribing Cleve’s bound is equivalent to the existence of a weak delay function. They provide a concrete construction for an $n$-party DRB secure against $n-1$ corrupt parties in a synchronous network.
Future work remains in addressing the Synchrony Assumption. Currently, the proof relies on messages arriving within a fixed time window. In asynchronous environments like the open internet, an adversary could delay messages to buy extra time for computation. Additionally, exploring constructions that do not rely on the Random Oracle Model or perfect clock synchronization remains an open challenge for the field.
Summary updated