Consider the following exchange:

  • Alice has some plaintext $x$. She sends the encrypted version $\mathcal E(x)$ to Bob.
  • Bob returns $(\mathcal E(x), T)$, where $T$ is a turing machine encoding the function he wants to preform on the unencrypted data.
  • To decrypt this result, Alice first decrypts $\mathcal E(x)$ to get the original plaintext $x$, and then runs the turing machine $T$ with $x$ as the input. The decrypted result is the output of the turing machine.

By sending back $T$, Bob essentially offloads the work of actual computation on the ciphertext to the decryption function. However, from what I can tell, this is technically still a fully homomorphic encryption system, as it allows Bob to execute an arbitrary function on the plaintext, without ever knowing the plaintext himself (since the computation of the Turing machine is done by Alice).

Is this cryptosystem actually considered homomorphic encryption? Is there a subtlety in the constraints for a FHE system that excludes this? Or is it just rejected for being pedantic and useless?

  • 1
    $\begingroup$ What if Alice and Bob be want to send their data, fhe encrypted, to Charlie who returns $f(x,y)$? How can this system allow that while keeping the desired data confidential? $\endgroup$ Dec 29 '17 at 2:58

No, this is not considered homomorphic encryption. This is excluded by requiring that the ciphertext size and running time of the decryption operation be bounded by the security parameter, independent of the circuit size. Your pathological example is given as the first footnote in Craig Gentry's seminal paper on a realization of FHE.

  • $\begingroup$ @Challenge5 Nice try though :p $\endgroup$
    – LeoDucas
    Jan 16 '19 at 6:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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