Ron Rothblum: Spooky Encryption and its Application

Friday, May 13, 2016 - 10:30am to 12:00pm
Location: 
Hewlett G882
Speaker: 
Ron Rothblum
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