I would just like to ask what is the classification of both BFV and CKKS scheme are they Somewhat Homomorphic or Fully Homomorphic?

Brakerski/Fan-Vercauteren (BFV) [Brakerski12, FV12, BEHZ16, HPS18] https://eprint.iacr.org/2012/144.pdf

Cheon-Kim-Kim-Song (CKKS) [CKKS17] https://eprint.iacr.org/2016/421.pdf

  • $\begingroup$ Which scheme are those? Could you please provide links to the exact version you are asking about? $\endgroup$ Aug 19 '19 at 16:46

Both schemes are presented as Leveled Homomorphic Encryption schemes, which means that for each $L$, there is at least a set of parameters ($\lambda$, $q$, etc) that allows us to homomorphically evaluate circuits of multiplicative depth up to $L$ (and the reciprocal also holds, i.e. for each set of parameters, there is a limit $L$ on the multiplicative depth of the circuits that can be evaluated).

In those basic forms, they are not really fully homomorphic, because once you set the parameters, you can't evaluate any circuit.

However, there are bootstrapping methods for both schemes, and once you implement the bootstrapping to refresh the ciphertexts after each operation, they become fully homomorphic.

For the FV scheme, the bootstrapping is presented in the own paper, in section 5.

For the HEANN scheme (which you called CKKS in your question), the bootstrapping method only appeared in that subsequent paper and it was improved in this paper that was published this year in Eurocrypt.

  • $\begingroup$ Just to clarify is CKKS and HEANN scheme different from each other since in Microsoft SEAL they called it CKKS scheme? $\endgroup$
    – fallere456
    Aug 22 '19 at 10:42
  • 1
    $\begingroup$ Yes, they are the same. Microsoft has chosen to refer the scheme by the initial letters of the authors' names, while the authors themselves refer to the scheme as HEANN, as you can see in one of the papers I linked in the answer. $\endgroup$ Aug 28 '19 at 11:24

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.