Computer Science Thesis Oral
— 5:00pm
Location:
In Person
-
Traffic21 Classroom, Gates Hillman 6501
Speaker:
ABHIRAM KOTHAPALLI
,
Ph.D. Candidate, Computer Science Department, Carnegie Mellon University
https://abhiramkothapalli.github.io/
A Theory of Composition for Proofs of Knowledge
In 1985, Goldwasser, Micali, and Rackoff introduced a compelling new notion of a proof, known as a proof of knowledge, in which a verifier interactively checks that a prover knows a satisfying witness for a claimed statement. Paradoxically, such interactions can be significantly shorter than the underlying witness, and reveal no information about it. For the past three decades, we have made significant progress in theoretical computer science by studying the time complexity, space complexity, and communication complexity of these interactions. Remarkably we are also seeing proofs of knowledge being used in practice today to secure billions of dollars worth of assets. Today, however, in search of practical efficiency, a growing body of work challenges the traditional paradigm by describing interactions in which the verifier does not fully resolve the prover’s statement to true or false but rather reduces it to a simpler statement to be checked. Such interactive reductions, although central to modern proofs of knowledge, lack a unifying theoretical foundation. Towards a common language, we introduce reductions of knowledge, which reduce the task of checking knowledge of a witness in one relation to the task of checking knowledge of a witness in another (simpler) relation. We show that reductions of knowledge can be composed naturally, and thus serve as both a unifying abstraction and a theory of composition. We demonstrate that large swathes of the extant literature can be expressed crisply in this framework, as well as develop new techniques that cannot be expressed in preexisting models. Putting everything together, we demonstrate that reductions of knowledge formalize a simple, but subtly powerful new perspective that proofs of knowledge are maps between propositions of knowledge. Thesis Committee: Bryan Parno (Chair) Aayush Jain Elaine Shi Srinath Setty (Microsoft Research)