How would one construct a security model to play against the adversary, and define the security of the overall scheme? This is in reference to the scheme introduced in "Fully Homomorphic Encryption Over Ideal Lattices".


1 Answer 1


Usually, the FHE schemes are proved to be CPA secure, therefore, the game is similar to the IND-CPA game, with the caveat that the attacker also hold a evaluation key (generally necessary to perform the homomorphic operations). Note that the evaluation key is public anyway, therefore it could just be considered as a part of the public key so that the game would be the same (this is done, for example, in the proof of security of BGV).

If there is some type of circular assumption (which is normally the case), then, you suppose that the evaluation key depends on the private key. However, this does not change the game.

Thus, the game would be more or less like this:

  1. Parameters are set, keys are generated and the adversary receives the public and the evaluation keys.
  2. The adversary can encrypt messages and compute over the ciphertexts freely.
  3. The adversary sends two messages $m_0$ and $m_1$ to the challenger and receive a ciphertext $c_b$ corresponding to $m_b$ (for a random $b$).
  4. The adversary can again encrypt and perform other computations.
  5. The adversary outputs a bit $b'$.

Side note:

As noted by @Maeher in the comments, we have to be careful when talking about CCA security and homomorphic encryption. It is already known that homomorphic encryption schemes cannot be CCA2 secure, thus, in your model, the best you could do to prove CCA security would be to use a game for IND-CCA1 security, as it is done, for instance, on this article (although they are dealing with Somewhat Homomorphic Encryption instead of FHE).

  • $\begingroup$ "If the scheme were to be proved CCA secure, you would just use the CCA game instead." It's not clear what you mean here. The homomorphism should preclude any FHE scheme from being CCA (or at least CCA2) secure. $\endgroup$
    – Maeher
    Feb 21, 2019 at 8:00
  • $\begingroup$ It is possible at least to construct Somewhat Homomorphic Encryption schemes that are IND-CCA1 secure. I am not aware of any Fully Homomorphic Encryption Scheme that is IND-CCA1, but I do not know of any result that shows that FHE cannot be IND-CCA1. If you know more about it, please, post some link here. I would really be glad. Ah, and yes, of course, CCA2 is not achievable. $\endgroup$ Feb 21, 2019 at 8:21
  • $\begingroup$ Honestly I was just thinking about CCA2 and only realized you might be referring to CCA1 while writing my comment. I'm not aware of any reason why an FHE scheme should not be CCA1 secure. But maybe you could clarify that last sentence a bit to avoid confusion. $\endgroup$
    – Maeher
    Feb 21, 2019 at 8:40
  • $\begingroup$ Yes, you are right. Since the whole answer was informal, I ended up writing this last sentence without paying attention to that. I am going to edit it. Thank you. $\endgroup$ Feb 21, 2019 at 8:55

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.