Paper 2017/887

Succinct Spooky Free Compilers Are Not Black Box Sound

Zvika Brakerski, Yael Tauman Kalai, and Renen Perlman

Abstract

It is tempting to think that if we encrypt a sequence of messages $\{x_i\}$ using a semantically secure encryption scheme, such that each $x_i$ is encrypted with its own independently generated public key $pk_i$, then even if the scheme is malleable (or homomorphic) then malleability is limited to acting on each $x_i$ independently. However, it is known that this is not the case, and in fact even non-local malleability might be possible. This phenomenon is known as spooky interactions. We formally define the notion of spooky free compilers that has been implicit in the delegation of computation literature. A spooky free compiler allows to encode a sequence of queries to a multi-prover interactive proof system (MIP) in a way that allows to apply the MIP prover algorithm on the encoded values on one hand, and prevents spooky interactions on the other. In our definition, the compiler is allowed to be tailored to a specific MIP. We show that (under a plausible complexity assumption) spooky free compilers that are sufficiently succinct to imply delegation schemes for NP with communication $n^{\alpha}$ (for any constant $\alpha<1$) cannot be proven secure via black-box reduction to a falsifiable assumption. On the other hand, we show that it is possible to construct non-succinct spooky free fully homomorphic encryption, the strongest conceivable flavor of spooky free compiler, in a straightforward way from any fully homomorphic encryption scheme. Our impossibility result relies on adapting the techniques of Gentry and Wichs (2011) which rule out succinct adaptively sound delegation protocols. We note that spooky free compilers are only known to imply non-adaptive delegation, so the aforementioned result cannot be applied directly. Interestingly, we are still unable to show that spooky free compilers imply adaptive delegation, nor can we apply our techniques directly to rule out arbitrary non-adaptive NP-delegation.