Ron Rothblum: Spooky Encryption and its Application

Speaker: Ron Rothblum

Date: Friday, May 13, 2016

Time: 10:30 AM to 12:00 PM

Public: Yes

Location: Gates Bldg, 882, Hewlett

Event Type:

Room Description:

Host: Vinod Vaikuntanathan

Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, cis-seminars@csail.mit.edu

Reminder Subject: TALK: Ron Rothblum: Spooky Encryption and its Application

Abstract: Consider a setting where inputs x_1,...,x_n are encrypted under
independent public keys. Given the ciphertexts c_i =
Enc(pk_i,x_i), Alice outputs ciphertexts c'_1,...,c'_n that
decrypt to y_1,...,y_n, respectively. What relationships between
the x_i's and y_i's can Alice induce?

If the scheme is homomorphic then "local" (component-wise)
relationships are achievable. On the other hand security of the
scheme disallows "signaling" relationships, meaning that y_i
cannot depend on x_j for j \neq i. However, there are also
relationships which are neither signaling nor local. Dwork et
al. [DLNNR01] asked if it is possible to have encryption schemes
that support such "spooky" relationships. Answering this question
is the focus of our work.

We show that under the Learning with Errors assumption, there
exists an encryption scheme supporting a large and natural class
of such spooky relationships. For this result, the public keys
all depend on common public randomness. Our second result shows
that, assuming sub-exponentially hard indistinguishability
obfuscation (iO) (and additional more standard assumptions), we
can remove the common randomness and choose the public keys
completely independently.

We discuss several implications of spooky encryption. Firstly, it
gives a strong counter-example to a method proposed by Aiello et
al. [ABOR00] for building arguments for NP from homomorphic
encryption. Secondly, it gives a simple 2-round multi-party
computation protocol where, at the end of the first round, the
parties can locally compute an additive secret sharing of the
output. Lastly, it yields a function secret sharing (FSS) scheme
for all functions.

Joint work with Yevgeniy Dodis, Shai Halevi and Daniel Wichs

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information Security (CIS) Seminar Series 2016.

Created by Deborah Goodwin Email at Monday, April 25, 2016 at 11:34 AM.