Homomorphic encryption is often touted for its ability to 1) Compute on encrypte

Question

Homomorphic encryption is often touted for its ability to

1) Compute on encrypted data with public functions
2) Compute an encrypted function on public (or private) data

I feel I have a good grasp of #1 as most of the papers I've come across on homomorphic encryption (both partially and fully) seem to deal with this type of problem, but #2 I haven't been able to wrap my head around.

So, to whittle this down to the simplest case, given a fully homomorphic encryption scheme, let the public input be a,b,c,d (each is a single bit for simplicity). How would I construct a function to compute (a?b)?(c?

Explanation / Answer

Theoretically, with fully-homomorphic encryption (like with Gentry's scheme), you could make a circuit (with memory) which computes over encrypted data and outputs encrypted results. The circuit could be a general-purpose CPU, and the encrypted data the code which is to be executed .

Since this method requires doing some pretty heavy stuff for every gate in the circuit (including every gate which is used for RAM in our custom CPU) and for every clock cycle as well, the cost would be tremendous (polynomial, yes, but with a hell of an exponent).

Now this would work over encrypted data, and produce encrypted results. If you want an encrypted function which runs over public input data and produces a public output, then the party who holds the decrypting key must be involved at some point. Without such a party, I don't think it is known whether it is doable.

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.