Ron Rothblum: Spooky Encryption and its Application

Friday, May 13, 2016 - 10:30am to 12:00pm

Location:

Hewlett G882

Speaker:

Ron Rothblum

Seminar group:

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