2nd Charles River Crypto Day

The 2nd Annual Charles River Crypto Day will be held on Friday, November 30th, 2011, from 9:30 a.m. to 4 p.m at Boston University’s Rafik B. Hariri Institute for Computing and Computational Sciences Engineering, at 111 Cummington Mall, Boston, MA 02215. The event is free and open to the public.

Sponsored and hosted by the Hariri Institute and the BU Center for Reliable Information Systems and Cyber Security (RISCS),  the Charles River Crypto Day brings together academics and research scientists from local universities and research labs to discuss recent advances in cryptography. The Charles River Crypto Day series, which is open to the public, is a recurring networking opportunity for faculty, postdocs, graduate students, and research scientists pursuing basic cryptography research in the Greater Boston Area.

Program

9:30-10:00 Gathering and breakfast

10:00-11:00 Vinod Vaikuntanathan, University of Toronto
Functional Encryption, Reusable Garbled Circuits and more

We construct a functional encryption scheme for all circuits, where the size of the ciphertext grows with the depth of the circuit. Previously, the only known constructions of functional encryption were either for specific inner product predicates, or for a weak form of functional encryption where the ciphertext size grows with the *size* of the circuit for f. Our constructions are secure under the learning with errors assumption.

We demonstrate the power of this result, by using it to construct a reusable circuit garbling scheme with input and circuit privacy: an open problem that was studied extensively by the cryptographic community during the past 30 years since Yao’s introduction of a one-time circuit garbling method in the mid 80’s. Our scheme also leads to a new paradigm for general function obfuscation which we call token-based obfuscation.

11:30 – 12:30  Ran Raz, Weizmann Institute and IAS

Delegation for Bounded Space

The problem of delegating computation considers a setting where one party, the delegator (or verifier), wishes to delegate a computation to another party, the worker (or prover).  The challenge is that the delegator may not trust the worker, and thus it is desirable to have the worker “prove” that the computation was done correctly.

Computation delegation became a central problem in cryptography, especially with the increasing popularity of cloud computing, where weak devices use cloud platforms to run their computations.

We give a 1-round delegation scheme for every language computable in time $t=t(n)$ and space $s=s(n)$, where the running time of the prover is $\poly(t)$ and the running time of the verifier is $\tilde{O}(n + \poly(s))$.

The proof exploits a curious connection between the problem of {\em computation delegation} and the model of {\em multi-prover interactive proofs that are sound against no-signaling (cheating) strategies}, a model that was studied in the context of quantum computation, and is motivated by the physical principle that information cannot travel faster than light.

We give a new construction of multi-prover interactive proofs (MIP) that are sound against no-signaling (cheating) strategies. We then show how to use the method suggested by Aiello et al. to convert our MIP into a 1-round delegation scheme, by using a computational private information retrieval (PIR) scheme.

Joint work with Yael Tauman Kalai and Ron Rothblum

Lunch (provided)

1:30  – 2:30  Assumptions Daniel Wichs, IBM Research

Reduction-Resilient Cryptography:  Security Goals that Resist Reductions from All Standard

This talk will explore several recent black-box separation results with a common theme: some desirable security notions have a “non-standard” structure that resists black-box reductions from all “standard” assumptions. We formalize the notion of  “standard” assumptions and security notions as ones that have the format of a (possibly interactive) game between a challenger and an attacker, where the challenger interacts with the attacker as a black box. This captures essentially all of our favorite cryptographic assumptions including: FACTORING, CDH, DDH, RSA. LWE, etc. The “non-standard” security notions we explore appear diverse,  but have a common thread of reasoning about adversarial distributions and leakage. In particular, we give separation results for: leakage-resilience with a unique secret, deterministic encryption on correlated messages, tools for generating and condensing pseudo-entropy, and instantiating the Fiat-Shamir heuristic for all proof-systems.

This talk is partially based on joint work with Nir Bitansky and Sanjam Garg.

2:45 -3:45  Salil Vadhan, Harvard University

The Computational Complexity of Differential Privacy

A major challenge in data privacy research is to enable the wide analysis of datasets with potentially sensitive information about individuals, while ensuring that the privacy of those individuals is protected.  Over the past decade, differential privacy has emerged as strong privacy protection model that supports a very rich variety of useful analyses.  However, computational complexity has turned out to be an obstacle for achieving one of the most exciting possibilities of differential privacy — noninteractively publishing a private “summary” of a dataset that enables answering up to exponentially many statistical queries about the dataset (such as all multivariate marginal statistics).

Whether these complexity barriers can be broken remains an intriguing open problem, but we will describe both negative and positive results that shed light on what can be achieved.  On the negative side, we prove that if we require the summary to be a “synthetic dataset,” then generating the summary is as hard as forging digital signatures, even if we want to preserve very simple statistics (2-way marginals, i.e. correlations between pairs of attributes).  On the positive side, we provide an algorithm for generating less structured summaries (based on polynomial approximations) in subexponential time, even for an exponential-sized family of statistics (all multivariate marginals).

Based on joint works with Justin Thaler and Jon Ullman.

We wish to thank BU’s Rafik B. Hariri Institute for Computing and Computational Science & Engineering and the Center for Reliable Information Systems and Cyber Security (RISCS) for making this event possible via generous support.