Paul Valiant Wins The Test Of Time Award At The Theory Of Cryptography Conference
- Posted by Jesse Polhemus
- on Oct. 1, 2019
Click the links that follow for more news about Paul Valiant and other recent accomplishments by our faculty.
The Theory of Cryptography Conference (TCC) is an International Association for Cryptologic Research (IACR) conference that focuses on paradigms, approaches, and techniques used to conceptualize, define, and provide solutions to natural cryptographic problems and computer security concerns. With a single author paper from 2008 ("Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency"), Professor Paul Valiant of Brown CS has just won the conference's fifth Test of Time Award, which recognizes outstanding papers that have made a significant contribution to the theory of cryptography, preferably with influence also in other areas of cryptography, computer science theory, and beyond. He joins a distinguished list of previous winners that includes Dan Boneh, Cynthia Dwork, and Silvio Micali.
Paul's paper asks the question: can long computations be easily adapted to produce a certificate of their correctness? While each individual step of a trillion-step computation can be easily certified, no one would read through a trillion certificates. In response, in an analogy to cryptographic "hash functions" that transform any long file into a 256-bit digest, Paul shows how to compress long proofs into short yet robust certificates. The key insight, Paul says, is that while regular proofs lose their security when compressed, this is not true for a variant called "proofs of knowledge". Paul's ideas have found crucial use in recent cryptocurrency developments, under the name "zk-SNARKs", where a "SNARK", named in honor of a mythical beast in a Lewis Carroll poem, stands for "Succinct Non-interactive ARgument of Knowledge". The Test of Time Award, to be presented in December in Nuremberg, Germany, cites Paul's paper "for demonstrating the power of recursive composition of proofs of knowledge and enabling the development of efficiently verifiable proofs of correctness for complex computations".
You can find a full version of Paul's paper here.
For more information, click the link that follows to contact Brown CS Communication Outreach Specialist Jesse C. Polhemus.
