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,\ldots,x_n$ are encrypted under independent public keys. Given the ciphertexts $\{c_i = Enc(pk_i,x_i)\}_i$, Alice outputs ciphertexts $c'_1,\ldots,c'_n$ that decrypt to $y_1,\ldots,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 $y_i$ cannot depend on $x_j$ for $j \neq i$ . On the other hand if the scheme is homomorphic then any local (componentwise) relationship is achievable, meaning that each $y_i$ can be an arbitrary function of $x_i$. 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 polynomialtime function $f$, Alice can ensure that $y_1,\ldots,y_n$ are random subject to $\sum_{i=1}^n y_i = f(x_1,\ldots,x_n)$. For this result, the public keys all depend on common public randomness. Our second result shows that, assuming subexponentially 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 $n=2$ inputs, we get a scheme that supports an even larger class of spooky relationships. We discuss several implications of AFSspooky encryption. Firstly, it gives a strong counterexample to a method proposed by Aiello et al. (ICALP, 2000) for building arguments for NP from homomorphic encryption. Secondly, it gives a simple 2round multiparty 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 spookyfree encryption, which ensures that no spooky relationship is achievable. We show that any nonmalleable encryption scheme is spookyfree. Furthermore, we can construct spookyfree homomorphic encryption schemes from SNARKs, and it remains an open problem whether it is possible to do so from falsifiable assumptions.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 Spooky EncryptionDelegationHomomorphic EncryptionFunction Secret Sharing
 Contact author(s)
 ronr @ csail mit edu
 History
 20160310: received
 Short URL
 https://ia.cr/2016/272
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/272, author = {Yevgeniy Dodis and Shai Halevi and Ron D. Rothblum and Daniel Wichs}, title = {Spooky Encryption and its Applications}, howpublished = {Cryptology ePrint Archive, Paper 2016/272}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/272}}, url = {https://eprint.iacr.org/2016/272} }