Spooky Encryption and its Applications

Consider encrypting $n$ inputs under $n$ 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 \cite{DLNNR04} showed that a semantically secure scheme disallows \emph{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 \emph{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 \emph{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. \cite{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 immediately yields a function secret sharing (FSS) scheme for all functions.

We also define a notion of \emph{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 \emph{homomorphic} encryption schemes from SNARKs, and it remains an open problem whether it is possible to do so from falsifiable assumptions.