CS Theory Seminar

Abstract: The advent of big data and associated privacy concerns have made it
important to process sensitive information in a provably secure manner.
This brings new challenges: how do we ensure correctness of computation?
How can we guarantee privacy?

Cryptographic proof systems, where a prover aims to convince a verifier
that a given statement is true, lie at the heart of many of these
questions. An important goal in this context is to ensure short proofs
with minimal overhead for the prover and verifier. Another key goal is
to achieve strong forms of privacy such as zero-knowledge, in order to
prove the validity of statements without revealing secrets associated
with them.

In this talk, I will describe recent progress at the frontier of
answering these questions, with protocols consisting of just one message
from each participant, and with provable security from well-studied
assumptions.

I will also describe how soundness of these systems relates to
no-signaling strategies from quantum physics, and how privacy can be
achieved by relying on a new cryptographic learning technique, that
pitches the simulator of the security proof against the discriminator.

Based on multiple joint works with Saikrishna Badrinarayanan, Abhishek
Jain, Yael Kalai, Ron Rothblum, Amit Sahai and Daniel Wichs.