1
$\begingroup$

Suppose we have A and B, e.g. a user a server, where A encrypts data to be processed by B homomorphically.

It seems that we could construct a pseudo-fully homomorphic encryption system---prior to Gentry's FHE scheme---where:

  1. B processes encrypted data using additive (or multiplicative) PHE, then sends the encrypted result to A.
  2. A decrypts the result, encrypts it again using a multiplicative (or additive) PHE scheme, e.g. ElGamal or RSA, and sends it to B.
  3. B processes the data using multiplicative PHE, then sends the encrypted result to A.
  4. Repeat these steps for a desired multiplication or addition operation.

Why wasn't such an "interactive" version of FHE used prior to canonical FHE? Am I missing something in my understanding?

Improve this question
$\endgroup$
1
  • $\begingroup$ As a quick comment: if A has to send data back-and-forth to B every time B switches from addition to multiplication, then this will almost always be vastly slower than A just doing the computations themselves. So you'd only want to do this if there was some other reason for A not to do it all themselves, such as B having some secret data as well. But then you're just doing MPC, as Mark describes. $\endgroup$
    – Sam Jaques
    Commented Jun 16, 2022 at 9:15

1 Answer 1

Reset to default
0
$\begingroup$

What you describe is very similar to multi-party computation, which is a form of secure computation that requires interactions to compute multiplications (for technical reasons additions can be done "for free"). This wasn't done in precisely the way you describe (there are more complex constructions that work better), but it had been known since the late 80's.

One can view FHE as a "non-interactive" form of MPC, so you viewing them as similar is natural. But FHE is sufficiently different than MPC that people view it worthwhile to separate the concepts, and mandate that the computations done in FHE can be one with solely

  1. some (public) key materical,
  2. the ciphertexts, and
  3. a description of the computation to be done,

i.e. no interaction is required from someone who has access to the secret key.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The question is strange. B processes encrypted data using additive (or multiplicative) PHE, then sends the encrypted result to A. So, A can use their private key to decrypt... The question is lacks the knowledge about who is the owner of the data, who computes and who wants the result... $\endgroup$
    – kelalaka
    Commented Jun 16, 2022 at 18:48
  • $\begingroup$ @kelalaka Apologies for the ambiguity. A owns the data and uses B as its data processor (i.e. as in many outsourced secure computation scenarios.) $\endgroup$
    – Shep
    Commented Jun 16, 2022 at 23:20
  • $\begingroup$ @Mark Thanks for the reply. Considering the 'interaction' part as MPC makes much more sense. $\endgroup$
    – Shep
    Commented Jun 16, 2022 at 23:26

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.