6.876J (MIT) and CS294-175 (Berkeley)
Advanced Topics in Cryptography Spring 2020


Course Information

INSTRUCTORS Shafi Goldwasser
Yael Kalai
Vinod Vaikuntanathan
LOCATION Calvin Hall 116 (at Berkeley) and 9-151 (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)

Lecture Topic References
Lecture 1 (Jan 31) Learning vs. Verifying (Jonathan Shafer)
Lecture 2 (Feb 6) Non-interactive Publicly Verifiable Delegation (Lisa Yang) Kalai-Paneth-Yang Paper
Lecture 3 (Feb 14) Key Value Commitments (Srini Raghuraman)
Lecture 4 (Feb 21) No Class Today due to the Simons Workshop.
Lecture 5 (Feb 28) Federated Learning (Saleet Klein) Federated Learning Survey
Lecture 6 (Mar 6) Fiat-Shamir (Alex Lombardi)
Lecture 7 (Mar 13) SNARKs (Succinct Non-Interactive Arguments of Knowledge) (Nicholas Ward) Nick's slides
Lecture 8 (Mar 20) Pseudorandom Functions from Lattices (Lun Wang) Lun's slides
No Lecture (Mar 27)
Lecture 9 (Apr 3) Fine-Grained Cryptography (Nagaganesh Jaladanki) Ganesh's slides
Lecture 10 (Apr 10) CONGEST Lower Bounds via Communication Complexity (Seri Khoury) Seri's slides
Lecture 11 (Apr 17) Two-Round Multi-Party Computation without Lattices (James Bartusek)
Lecture 12 (Apr 24) SafetyPin: Encrypted Backups with Human-Memorable Secrets (Emma Dauterman)
Lecture 13 (May 1)
Lecture 14 (May 8)


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 Fourier-sparse 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 Non-Interactive Delegation

We construct a delegation scheme for all polynomial time computations. Our scheme is publicly verifiable and completely non-interactive 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 non-interactive delegation schemes were only known under knowledge assumptions (or in the Random Oracle model) or under non-standard 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 non-deterministic computations.

Lisa is a PhD student at MIT. This is joint work with Yael Kalai (Microsoft Research and MIT) and Omer Paneth (Tel-Aviv University).

CONGEST Lower Bounds via Communication Complexity

One of the well-studied models of distributed graph algorithms is the CONGEST model. In this model, there is a network of n nodes that can communicate with each other via synchronous communication rounds. In each round, each node can send a logn-bit message to each of its neighbors. The goal of the nodes is to compute some function of the network (e.g., the value of the maximum independent set) while minimizing the number of communication rounds.

In the first part of this talk, I will discuss a very fruitful technique for proving lower bounds for the CONGEST model. I will present recent progress in hardness of approximation of maximum independent set in the this model.

In the second part of this talk, I will discuss the classical lower bound for 2-party set-disjointness (fooling sets method).

Two-Round Multi-Party Computation without Lattices

Recent developments in the field of secure multi-party computation have resulted in protocols that allow parties to jointly compute arbitrary functionalities over their private inputs, with minimal interaction and based on 20th century tools and assumptions. In this talk, we will see the obfuscation-based “round-compressing compiler” of [GGHR14] and how it was later instantiated using garbled circuits and oblivious transfer [GS18, BL18] to yield a two-round multi-party computation protocol from minimal assumptions. Depending on time, we’ll also see how to use the DDH assumption to reduce interaction even further by making the first round messages reusable across an arbitrary number of second round executions, each of which may compute a different function over the parties’ inputs [BGMM20].

SafetyPin: Encrypted Backups with Human-Memorable Secrets

We present the design and implementation of SafetyPin, a system for encrypted mobile-phone backups. Like existing mobile-backup systems, including those of Apple and Google, SafetyPin requires users to remember only a short PIN and prevents brute-force PIN-guessing attacks using hardware security protections. Unlike today’s systems, SafetyPin provides strong protection against hardware compromise: the system protects the confidentiality of backed-up user data even against an attacker that can adaptively compromise many of the system’s constituent hardware security modules. To achieve these security properties while respecting the resource limits of today’s hardware security models, we develop a collection of new cryptographic tools.