Ph.D. Dissertation Proposal
Verifiable Randomness and its Applications
Christopher Vatcher
10:30am Thursday, 24 September 2015, ITE 325b
We propose to create a public verifiable randomness beacon, to integrate with the Random-Sample Voting system, constructed to be secure against adversaries who have even almost complete control over the system’s source of public randomness including the entropy source.
By verifiable randomness, we do not mean we can prove a sequence of bits to be random. Instead, verifiability means it is possible to prove: (a) a consumer used uniform bits originating from a specific entropy source and therefore cannot lie about the bits used; and (b) the bits used were unpredictable prior to their generation and, with overwhelming probability, were free of adversarial influence. This is in contrast to ordinary public randomness where parties must agree to trust some randomness provider, who becomes a target of corruption. Verifiable randomness is an enhancement of public randomness used to perform random selection in voting, conduct random audits, preserve privacy, generate random challenges for secure multi-party computation, and public lottery draws. Random-Sample Voting specifically requires verifiable randomness for random voter selection and random audits.
Our work extends the work of Eastlake and Clark and Hengartner by considering (a) adversaries who have fine control over the entropy source and (b) physical entropy sources, which we can make verifiable.
Our specific aims include (a) creating adversary models for three entropy source abstractions based on trusted providers, sensor networks, and distributed proof-of-work systems; (b) create a verifiable random beacon that integrates each model; (c) integrate our work with the Random-Sample Voting system; and (d) integrate with NIST’s beacon and propose a verifiable randomness standard based on our work.
Our method is to weaken the trust assumption on the entropy source by introducing verifiable entropy sources, which have mechanisms for limiting adversarial influence and accumulating evidence that their outputs obey a known distribution. Combined with an appropriate randomness extractor, we can generate verifiable random bits. Using sources like weather, we will construct a verifiable randomness beacon: a public randomness provider unencumbered by generous and often unfounded trust assumptions. Such a beacon can serve as a singular gateway for accessing and aggregating multiple entropy sources without compromising the randomness provided to consumers.
Committee: Drs. Alan T. Sherman (Chair), Konstantinos Kalpakis, Weining Kang (Math/Stat), David Chaum (Random-Sample Voting), Aggelos Kiayias (University of Athens)