Paper 2016/272

Spooky Encryption and its Applications

Yevgeniy Dodis, Shai Halevi, Ron D. Rothblum, and Daniel Wichs

Abstract

Consider a setting where inputs $x_1,\dots ,x_n$ are encrypted under independent public keys. Given the ciphertexts $\{c_i=Enc(p{k}_i,x_i){\}}_i$, Alice outputs ciphertexts $c_1^{\prime },\dots ,c_n^{\prime }$ that decrypt to $y_1,\dots ,y_n$ respectively. What relationships between the $x_i$'s and $y_i$'s can Alice induce? Motivated by applications to delegating computations, Dwork, Langberg, Naor, Nissim and Reingold (unpublished manuscript, 2004) showed that a semantically secure scheme disallows signaling in this setting, meaning that $$ cannot depend on $$ for $$ . On the other hand if the scheme is homomorphic then any local (component-wise) relationship is achievable, meaning that each $$ can be an arbitrary function of $$. However, there are also relationships which are neither signaling nor local. Dwork et al. asked if it is possible to have encryption schemes that support such ``spooky'' relationships. Answering this question is the focus of our work. Our first result shows that, under the LWE assumption, there exist encryption schemes supporting a large class of ``spooky'' relationships, which we call additive function sharing (AFS) spooky. In particular, for any polynomial-time function $$, Alice can ensure that $$ are random subject to $$. 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. Furthermore, in the case of $$ inputs, we get a scheme that supports an even larger class of spooky relationships. We discuss several implications of AFS-spooky encryption. Firstly, it gives a strong counter-example to a method proposed by Aiello et al. (ICALP, 2000) 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 immediately yields a function secret sharing (FSS) scheme for all functions. We also define a notion of spooky-free encryption, which ensures that no spooky relationship is achievable. We show that any non-malleable encryption scheme is spooky-free. Furthermore, we can construct spooky-free homomorphic encryption schemes from SNARKs, and it remains an open problem whether it is possible to do so from falsifiable assumptions.