6.876J (MIT) and CS294175 (Berkeley)
Advanced Topics in Cryptography Spring 2020
Announcements
Course Information
INSTRUCTORS

Shafi Goldwasser
Yael Kalai
Vinod Vaikuntanathan

LOCATION 
Calvin Hall 116 (at Berkeley) and 9151 (at MIT)

TIME 
F 10am  12

FORMAT 
Each course participant will deliver one or more lectures on recent research results in cryptography, in consultation with the lecturers.

GRADING 
Each student gives one or more lectures or scribes one or more lectures.

Schedule (subject to change)
Abstracts:
Learning vs Verifying
This talk will address the following question: In what cases does learning a good hypothesis require more resources than verifying a hypothesis proposed by someone else?** If verification is significantly cheaper than learning, that could have important practical implications for delegation of machine learning tasks in commercial settings, and might also have consequences for verification of scientific publications, and for AI safety. Two results will be discussed: (1) There exists a learning problem where verification requires quadratically less random samples than are required for learning. (2) The broad class of Fouriersparse functions (which includes decision trees, for example) can be efficiently verified using random samples only, even though it is widely believed to be impossible to efficiently learn this class from random samples alone.
Jonathan is a PhD student at UC Berkeley. This is joint work with Shafi Goldwasser (UC Berkeley), Guy Rothblum (WIS), and Amir Yehudayoff (Technion).
Publicly Verifiable NonInteractive Delegation
We construct a delegation scheme for all polynomial time computations. Our scheme is
publicly verifiable and completely noninteractive in the common reference string (CRS) model.
Our scheme is based on an efficiently falsifiable decisional assumption on groups with bilinear maps. Prior to this work, publicly verifiable noninteractive delegation schemes were only
known under knowledge assumptions (or in the Random Oracle model) or under nonstandard
assumptions related to obfuscation or multilinear maps.
We obtain our result in two steps. First, we construct a scheme with a long CRS (polynomial
in the running time of the computation) by following the blueprint of Paneth and Rothblum
(TCC 2017). Then we bootstrap this scheme to obtain a short CRS. Our bootstrapping theorem
exploits the fact that our scheme can securely delegate certain nondeterministic computations.
Lisa is a PhD student at MIT. This is joint work with Yael Kalai (Microsoft Research and MIT) and Omer Paneth (TelAviv University).