[Busec] BUsec this week: Raluca Popa (Mon 10AM) & Kobbi Nissim (Wed 3PM)

Sharon Goldberg goldbe at cs.bu.edu
Sun Dec 2 10:52:57 EST 2012

Hi All,

We have two exciting talks this week.

In seminar on Monday at 10AM, Raluca Popa from MIT will tell us about
her new result on functional encryption.  Then, on Wednesday at 3PM,
Kobbi Nissim from BGU will be speaking about his new work on
differential privacy in the CS colloquium.

In seminar the following Monday 10AM, Chris Fletcher from MIT will
tell us about implementations with fully homomorphic encryption.

Abstracts below.

See you then!

BUsec Calendar:  http://www.bu.edu/cs/busec/
BUsec Mailing list:  http://cs-mailman.bu.edu/mailman/listinfo/busec
How to get to BU from MIT:  Try the CT2 bus or MIT's "Boston Daytime
Shuttle" http://web.mit.edu/facilities/transportation/shuttles/daytime_boston.html


Title: Succinct functional encryption and applications: reusable
garbled circuits and beyond
Speaker: Raluca Popa, MIT.
Monday, December 3, 10AM in MCS137

Functional encryption is a powerful primitive: given an encryption
 Enc(x) of a value x and a secret key sk_f corresponding to a circuit f,
 it enables efficient computation of f(x) without revealing any
 additional information about x. Constructing functional encryption
 schemes with succinct ciphertexts that guarantee security for even a
 single secret key (for a general function f) is an important open
 problem with far reaching applications, which this paper addresses.

Our main result is a functional encryption scheme for any general
 function f of depth d, with succinct ciphertexts whose size grows with
 the depth d rather than the size of the circuit for f. We prove the
 security of our construction based on the intractability of the learning
 with error (LWE) problem.  More generally, we show how to construct a
 functional encryption scheme from any public-index predicate encryption
 scheme and fully homomorphic encryption scheme.

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.

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.
 Furthermore, we show applications of our scheme to homomorphic
 encryption for Turing machines that runs in input-specific time rather
 than worst case time, and to publicly verifiable and secret delegation.

 Joint work with
 Shafi Goldwasser, Yael Kalai, Vinod Vaikuntanathan, and Nickolai Zeldovich


Characterizing the Sample Complexity of Private Learners
Speaker: Kobbi Nissim, Ben Gurion University
Wednesday December 5 at 3PM in MCS148

The notion of private learning [Kasiviswanathan, Lee, N, Raskhodnikova, and
 Smith '08] is a combination of PAC (probably approximately correct) learning
 [Valiant 84] and differential privacy [Dwork, McSherry, N, and Smith '06].
 Kasiviswanathan el al. presented a generic construction of private learner
 for finite concept classes, where the sample complexity depends
 logarithmically in the size of the concept class. For concept classes of
 small VC dimension, this sample complexity is significantly larger than what
 is sufficient for non-private learning.

In this talk I will motivate differential privacy and private learning, and
 will present some of the known bounds on the sample complexity of private
 learners. In particular, a recent characterization of the sample complexity
 as a combinatorial measure of the learned concept class.

Joint work with Amos Beimel and Uri Stemmer.

Techniques for performing secure computation on encrypted data
Speaker: Chris Fletcher, MIT
Monday Dec 10, 10AM in MCS137

Privacy of data is a huge problem in cloud computing, and more
generally in outsourcing computation.  From financial information to
medical records, sensitive data is stored and computed upon in the
cloud.  Computation requires the data to be exposed to the cloud
servers, which may be attacked by malicious applications, hypervisors,
operating systems or insiders.

In the ideal scenario, no one other than the user sees the private
data in decrypted form, as is achieved through the use of fully
homomorphic encryption (FHE) techniques.  The first part of the talk
will focus on (a) techniques to run general purpose programs under FHE
and (b) how some programs are naturally better suited for FHE than
others.  I will talk about the how ambiguity in program control flow
and data structures leads to large overheads for certain programs, in
addition to the crypto overheads already imposed by FHE (which impose
about a billion times slowdown).

Motivated by large FHE overheads, the second part of the talk
describes how to approximate FHE with a tamper-resistant processor
called Ascend.  Ascend performs program obfuscation in hardware: given
an untrusted program and private user data running within the Ascend
chip, the chip's external input/output and power pins give off a
signal that is independent of the private user data.  I will discuss
how strict periodic accesses to an Oblivious RAM obfuscate
input/output behavior and how strict periodic accesses to on-chip
circuits (e.g., on-chip caches) coupled with DPA-resistant techniques
obfuscate Ascend's power signature.  Surprisingly, Ascend incurs only
a ~5X performance overhead running SPEC benchmarks.  The trusted
computing base is only the Ascend chip: no software (the user
application, server operating system, etc) or anything outside the
Ascend processor (external RAM or communication channels) is trusted.

This is joint work with Marten van Dijk, Srini Devadas, Ling Ren and
Xiangyao Yu.

More information about the Busec mailing list