Please, I would like to find some hints or solution to my following problem, I would appreciate your assistance to walk with me throughout the solution

Given fully homomorphic encryption (FHE) scheme(gen, enc, dec, eval), design a secure computation protocol so that two players, Alice and Bob, can jointly and securely evaluate a function $g : \{0, 1\}^ k \times \{0, 1\}^k \rightarrow \{0, 1\}^k$ Here, both Alice and Bob provide inputs but only Bob learns the output


If you can live with security against passive adversaries here is how you could do that: Denote the inputs of Alice and Bob $x$ and $y$ respectively. Bob generates public- and private-key for the FHE scheme. He sends the public key to Alice a long with an encryption of his input. Alice encrypts her own input and computes an encryption of $g(x,y)$ using the homomorphic properties of the FHE scheme (i.e., using the eval algorithm). Alice then sends this encryption to Bob, who decrypts and now has the intended output.

Note that if you assume active adversaries this breaks down because you have no guarantee that Alice will compute the agreed upon function.


You would need to make sure that the ciphertext Alice sends to Bob does not reveal more information about Alices input than $g(x,y)$. As Ricky points out in the comment this may require some additional properties of the FHE scheme. One way to ensure this (as Ricky points out) is to require the FHE scheme to be circuit private. This means that an encryption of $g(x,y)$ obtained using the eval algorithm is indistinguishable from a fresh encryption of $g(x,y)$, i.e., an encryption obtained by directly encrypting the result $g(x,y)$.

  • $\begingroup$ More generally, $\;\;$ "generates public- and private-key for" $\: \mapsto \:$ "generates a secret key and evaluation key for" $\;\;$ and $\;\;$ "the public key" $\: \mapsto \:$ "the evaluation key" $\;$ .$\;\;\;\;\;\;$ Even for passive adversaries, the FHE scheme would have to have circuit-privacy. $\;\;\;\;\;\;\;\;\;\;\;\;$ $\endgroup$ – user991 Nov 16 '14 at 21:59
  • $\begingroup$ I am not fully aware of the FHE terminology, but as far as I recall "circuit privacy" is the property that a ciphertext derived from the eval function is indistinguishable from a "fresh" encryption. I.e., that an evaluated ciphertext does not reveal the evaluated circuit. I do not think this property is required here, since $g$ is not part of a private input. It is simply an agreed upon public function. $\endgroup$ – Guut Boy Nov 16 '14 at 22:35
  • $\begingroup$ Also, while it may be the case that there are separate keys for encryption and evaluation for some FHE schemes, both keys are public thus constituting a collective public key. Note Alice would need both in this example. $\endgroup$ – Guut Boy Nov 16 '14 at 22:42
  • $\begingroup$ Oh yes, I missed that you were going about it in an unusual way. $\:$ Your suggestion does require that the FHE scheme be public-key, and would need what might be called input-privacy, rather than circuit-privacy. $\endgroup$ – user991 Nov 16 '14 at 23:23
  • $\begingroup$ I am a little puzzled why you would think this is unusual. As far as I know FHE schemes are in general public-key encryption schemes. At least I have never heard of other types of FHE. Do you have a reference for a non-public-key FHE scheme? I would be interested in knowing more about that. $\endgroup$ – Guut Boy Nov 17 '14 at 9:14

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.