CAREER: Temporal Cryptography and Verifiable Lotteries

New York University, New York NY

Investigators

Abstract

Lotteries are used to distribute billions of dollars annually in cash prizes, as well as important resources including immigration visas, school placements and assignments of judges to appeal cases. One would like to have public confidence that these lotteries were conducted fairly, specifically that the results were random and without bias and that they were not predictable or secretly known prior to their official announcement. Today, nearly all lotteries either provide no technical assurance to the public whatsoever or rely on ancient means of physical randomness generation such as rolling dice or spinning wheels. This project will build a solid scientific foundation for cryptographically verifiable lotteries that can provide strong assurance, even to remote observers, that a lottery was fair. To do so, this project will develop new tools from the emerging field of temporal (time-based) cryptography, including verifiable delay functions and timed commitments. Temporal cryptography is a powerful building block for distributed randomness protocols and other applications, but key questions remain on how to parameterize and analyze such protocols. Second, the project will develop the theory of temporal cryptography and consider its relation to classic bounds and impossibility results on randomness generation, consensus and general multiparty computation protocols. Finally, this project will build a practical understanding of lottery requirements and user expectations through empirical study of lottery mechanisms and user studies to understand current expectations and reactions to cryptographic verifiability. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.