[Busec] BUsec this week: Raluca Popa (Mon 10AM) & Kobbi Nissim (Wed 3PM)
goldbe at cs.bu.edu
Sun Dec 2 10:52:57 EST 2012
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.
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
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
More information about the Busec