Building systems using malicious components: how I learned to stop worrying and trust SNARK proofs

Eran Tromer
Tel Aviv University and Columbia University

"Computers are unreliable and vulnerable to attacks. Therefore, we shouldn't believe what they say, unless they prove its correctness." Imagine how much more robust our systems and networks would be, if they could be built on this tenet! But how can we succinctly prove that some complex computation was not corrupted, and actually produced the correct output? Can this be done efficiently? And how would such proofs be used and propagated in a larger system?

In recent years, there has been dramatic progress in the theory and implementation of cryptographic proof systems with the requisite properties: zero-knowledge Noninteractive ARguments of Knowledge (zkSNARK) and its extension to Proof-Carrying Data.

We will survey this progress, and discuss several applications:

• Ensuring the integrity of any logic circuit, or any C programs
• Zerocash: Preserving users' privacy in Bitcoin-like cryptocurrencies
• ProtoProof: Verifying the authenticity of edited photographs

Includes joint work with Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Daniel Genkin, Matthew Green, Ian Miers, Assa Naveh, Gilad Roth and Madars Virza.

Slides:

Download the slides for this presentation in PDF format. Slides are frequently not available until after the presentation.

Videos:

• Join the live presentation. Wednesday 4:30-5:45 (Pacific).  Requires Microsoft Windows Media player.
• View the Stanford Consolodated Archive Lectures
• View video by lecture sequence in HTML5. Available after 8PM Pacific on the day of the lecture.
• View Video on YouTube. The YouTube video is uploaded the day following the presentation. You may need to disable your pop-up blocker for this link to work. Or use the direct link which is available here only after the presentation has been published to YouTube.

About the speaker:

Eran Tromer is a faculty member at Tel Aviv University's School of Computer Science, where he heads the Lab for Experimental Information Security and is codirector of the Check Point Institute for Information Security. Currently he is a visiting scientist at Columbia University. He received his Ph.D. at the Weizmann Institute of Science, and previously pursued his research at MIT and at Microsoft Research. His research area is cryptography and information security, focusing on risks posed by physical attacks and untrusted platforms, and on mitigating these risks using robust protocols and rigorous proofs. His work has guided government standards and industry practice, and has improved the security of systems used by millions of people.

Contact information:

Eran Tromer University of Tel Aviv and Columbia University