# Connections between Instance Hiding and Fully Homomorphic Encryption

Another approach taken by researchers for carrying out computations over encrypted data is Instance Hiding.

In brief, If a user wants to outsource the computation of a function for a particular input x (instance). She transforms the input x to an encrypted input y (thus hides it) in such a way that the server cannot infer x from y and sends to the server. The server computes the function on y and returns the result. (References below).

This is also called Encrypting Problem Instances. The functions that allow such transformations are called encryptable functions. These techniques argue that encryptabality is property of a function and not all functions can be encryptable.

If this is the case, it may contradict some results of Fully Homomorphic Encryption. FHE tries to evaluate functions on encrypted inputs much generically.

Edit : in FHE, We transform the inputs (encrypt) them to cipher text which is then fed to say a function "add" carried out by server. Here add is generic function, does this mean add is encryptable function ?

I guess the catch is making assumptions on transformations

What is the catch here ? anybody ?

Refer :Abadi, Martin, Joan Feigenbaum, and Joe Kilian. "On hiding information from an oracle." Proceedings of the nineteenth annual ACM symposium on Theory of computing. ACM, 1987.

Here's what's common in both scenarios: Alice holds $x$ and wants to compute $f(x)$. A server Bob will help with the computation. Alice doesn't want Bob to learn $x$, so she sends some encoding of $x$ that hides $x$. Bob does some work and sends back a result from which Alice can infer $f(x)$.
The two settings differ on: (1) how Bob is allowed to help Alice with the computation, (2) what kind of guarantee Alice has about the privacy of her data $x$.
In the setting of the Abadi-Feigenbaum-Kilian paper, Bob must evaluate $f$ itself on the stuff that Alice sends to him. He is not allowed to compute some other thing related to $f$. This is quite a severe restriction! Also, this setting demands unconditional privacy against Bob.
In the setting of FHE, Bob doesn't literally perform the computation $f$ on what Alice sends him; rather, he performs the homomorphic evaluation of $f$ on a ciphertext.'' Also, Alice gets a privacy guarantee that is only computational.
• Your comment and your edits don't seem relevant to anything in my answer, which I still believe is the correct answer to your question. Is there something specific about my answer that didn't make sense? $f(y)$ and $\text{Eval}(y,f)$ -- where Eval is the homomorphic evaluation procedure from an FHE -- are different operations. The AFK setting does not permit Bob to do the latter in order to help Alice learn $f(x)$, so none of the AFK impossibility results are relevant to outsourced computation using FHE (among other reasons). Apr 22 '13 at 5:42