Welcome to the resource topic for 2016/272
Title:
Spooky Encryption and its Applications
Authors: Yevgeniy Dodis, Shai Halevi, Ron D. Rothblum, 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 (component-wise) 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 polynomial-time 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 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 n=2 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.
ePrint: https://eprint.iacr.org/2016/272
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .