2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ To answer this please check the question, i have edited it for more clarity. In FHE, too we ultimately build any function from basic functions like add and multi, $\endgroup$
    – sashank
    Apr 22, 2013 at 4:41
  • 1
    $\begingroup$ 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). $\endgroup$
    – Mikero
    Apr 22, 2013 at 5:42
  • $\begingroup$ Eval(y,f) in reality means to f(y) , Eval method is purely coined for definitional purposes, in reality, Bob computes f(y), in both AFK and FHE. To be more clear check the hcrypt project, notice that there is no Eval method the add and multi method only exists hcrypt.com/scarab-library, Eval is purely for definitional issues $\endgroup$
    – sashank
    Apr 22, 2013 at 6:11
  • $\begingroup$ You are claiming that fhe_add and fhe_mul actually do nothing more than interpret ciphertexts as numbers, and just add and multiply those numbers? I encourage you to actually look at the source code of these functions to see how much stuff actually has to happen in order to multiply ciphertexts. In some schemes, yes, homomorphic addition is really an addition operation over ciphertexts, but it's a different operation than addition of plaintexts. For one, the plaintexts are integers mod 2, and ciphertexts are vectors over a larger modulus. Again, different operations! $\endgroup$
    – Mikero
    Apr 22, 2013 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.