2
$\begingroup$

Is it theoretically possible to use homomorphic encryption to run an encrypted algorithm over encrypted data? If this is not possible, is it at least possible to run an encrypted algorithm over plain data (beyond a plain algorithm over encrypted data)? Ideally, can you cite papers where I can read about it?

$\endgroup$

2 Answers 2

1
$\begingroup$

Yes it is possible. An interpreter is an algorithm that takes a program $M$ and a datum $x$ as input and outputs the result of running program $M$ on input $x$. For any Turing-complete programming language, one might construct such an interpreter. See this Wikipedia entry for more details.

Say we have a universal interpreter $U$ that expects an input of the form $\langle M,x\rangle$ such that $U(\langle M,x\rangle)=M(x)$. Then you can produce the ciphertext $c=\mathrm{Enc}(\langle M,x\rangle)$ and evaluate $U$ homomorphically on this ciphertext $c'=\mathrm{Eval}(U,c)$. The correctness of the FHE scheme implies that $\mathrm{Dec}(c')=U(\langle M,x\rangle)=M(x)$. So the recipient learns $M$ applied to $x$ and the evaluator learns neither $M$ nor $x$.

I omit many details in this answer such as the fact that FHE schemes evaluate circuits of addition and multiplication over finite fields. If you restrict to boolean circuits, this paper and this one show how you can build a universal circuit for a fixed size. I am unaware if the same has been done with respect to arithmetic circuits over fields.

$\endgroup$
1
  • 1
    $\begingroup$ there appear to be some works that show up when searching for arithmetic universal circuits, for example this. $\endgroup$
    – Mark Schultz-Wu
    May 1, 2023 at 20:58
0
$\begingroup$

This can (sort of) be done. There are a few things to mention

  1. One can take as input encrypted data, an encrypted function, and produce an encrypted output. The keywords to search on for this are "function-private fully-homomorphic encryption"

  2. If one wants to take plaintext data, an encrypted function, and produce an encrypted output, this should also be able to be done with the same techniques.

  3. If one wants to take plaintext data, an encrypted function, and produce plaintext output, the problem is significantly harder. I believe terms to search on are "indistinguishability obfuscation", and perhaps "white-box cryptography" (though the two topics are distinct).

$\endgroup$
1
  • 1
    $\begingroup$ I wouldn't call function-hiding FHE "evaluating encrypted data over an encrypted function", since the evaluator knows the function (but does not reveal it beyond the output). There is an ambiguity in the question as to who is actually allowed to know the function, but it sounds like the answer to one interpretation would be to use multi-key FHE: Alice produces an encrypted input, Bob produces an encryption of his secret function, and Charlie homomorphically evaluates the universal circuit, which takes Bob's input and evaluates it on Alice's input. $\endgroup$
    – integrator
    May 1, 2023 at 11:30

Your Answer

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

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