# [Busec] Reminder: The Second Charles River Crypto day: This Friday, Nov 30 at BU's Hariri inst.

Ran Canetti canetti at bu.edu
Wed Nov 28 07:04:09 EST 2012


Dear All:

This is a reminder that you are cordially invited to the second Charles
River Crypto Day,
to be held at  the Hariri Institute in Boston University on Friday,
November 30, 2011.
The program appears below (this time with all the abstracts). The event
is open to the public.

Shafi, Yael, Ran

Venue and parking: The location is the same as last year. The address is
111 Cummington mall, Room 180. The closest entrance is at the corner of
Cummington Mall and Hinsdale st. If you need parking permit at the
adjacent parking structure (entrance from Hinsdale st), please send an
email to Ellen Grady (grady at bu.edu) by end of today.

==========================================================================

Program:
========

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

11:30 - 12:30
Delegation for Bounded Space
Ran Raz, Weizmann Institute and IAS

Lunch (provided)

1:30  - 2:30
Reduction-Resilient Cryptography:  Security Goals that Resist
Reductions from All Standard Assumptions
Daniel Wichs, IBM Research

2:45  - 3:45
The Computational Complexity of Differential Privacy
Salil Vadhan, Harvard University

============================================================================

Abstracts:

============================================================================

Functional Encryption, Reusable Garbled Circuits and more

Vinod Vaikuntanathan, University of Toronto

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.

============================================================================

Delegation for Bounded Space

Ran Raz, Weizmann Institute and IAS

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

=========================================================================

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

Daniel Wichs, IBM Research

Abstract: 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.

=============================================================================

The Computational Complexity of Differential Privacy

Harvard University

Abstract:
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.