By program integrity, I mean the (encrypted) result I receive is indeed the expected result and not, say, an intermediate result or a result affected by an adversary. Can homomorphic encryption defend against active attacks?

By program obfuscation, I mean the adversary not being able to infer what operations are performed (data access patterns aside).


If the homomorphic evaluation procedure is deterministic, as is usually the case, the program integrity requirement is trivially fulfilled: given a function $f$, the input ciphertext $C$ and the output ciphertext $C'$, anyone can publicly evaluate $f$ on $C$ (homomorphically) and check that the result is indeed $C'$. However, this conflicts with a standard other requirement, where one wants the output $C'$ to be distributed as an encryption with uniformly random coins.

When the output ciphertext is randomized, to ensure program integrity, the usual strategy is to use a zero-knowledge proof system. Namely, given a function $f$, the input ciphertext $C$ and the output ciphertext $C'$, the homomorphic evaluator will prove in zero-knowledge that $C'$ was obtained as the result of homomorphically evaluating $f$ on $C$ (and randomizing the output). Many solutions exist to implement this, depending on the other constraints (e.g. if we want this verification to be less expensive than performing the entire homomorphic evaluation, on can use succinct zero-knowledge proofs).

Regarding your 'program obfuscation' requirement, this sounds like what is usually called circuit privacy (i.e., when evaluating $f$ on $C$ homomorphically and getting an output $C'$, seeing $(C,C')$ should leak nothing about $f$). Any 'partially homomorphic' encryption scheme we know of (Paillier, ElGamal, Goldwasser-Micali, and the like) is re-randomizable (given a ciphertext $C$, anyone can publicly construct a ciphertext $C'$ encrypting the same value with uniformly distributed random coins), hence can be trivially made circuit-private. For fully homomorphic encryption, it's a bit more complex, but there are also well-established techniques, such as using noise flooding, or some more advanced strategies such as this one.

  • $\begingroup$ For a PHE scheme that supports a known operation, what does it mean the scheme is circuit-private? Doesn't circuit privacy refer to the operation? $\endgroup$ – sava Jul 27 '18 at 23:46

Both of these properties cannot be met at the same time, because it doesn't make sense. How could you verify somethign you don't know?

However, for each property, there are stratégies that helps you. You could use your favorite way to cehck integrity on the evaluation function of the FHE itself, hence ensuring the computation performed was the expected one.

The second property is usually called circuit privacy, and as specified by Geoffroy in his answer, there have been different techniques to reach it. (Note that it is possible even in the case where the user is malicious) Also note that the data access pattern is not revealed if the user sends all the data at once, and the server performs all computation locally before sending back the result.


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.