In Gentry's easy FHE intro, it is stated that

Researchers [1, 8] showed that if $\epsilon$ is a deterministic fully homomorphic encryption scheme (or, more broadly, one for which it is easy to tell whether two ciphertexts encrypt the same thing), then $\epsilon$ can be broken in sub-exponential time.

Side question: This answer mentions that any probabilistic PHE scheme can be made deterministic. This holds also for FHE schemes right? Any implementations out there make this easy to do?

Main question: Are there any FHE schemes that meet the "more broadly..." part of the quote? Specifically, are there any FHE schemes out there that allow for easy determination of whether two ciphertexts encrypt the same thing?

  • 1
    $\begingroup$ I have seen a paper years ago talking about a deterministic FHE scheme, but I've lost the paper. I'll look at it again. An attack will be interesting.. $\endgroup$
    – kelalaka
    Oct 9 '21 at 14:19
  • $\begingroup$ For the side question: To turn a probabilistic PHE into a deterministic one by fixing random coin, you should carefully choose the way to fix a random coin; e.g. it must satisfies Enc(1)+Enc(1)=Enc(2). This observation makes the function to determine errors itself homomorphic. For FHE, I am not sure such coin choice is easy. $\endgroup$
    – Hhan
    Oct 9 '21 at 16:14
  • $\begingroup$ For the main question: I don't think such a mechanism is considered in the major FHE schemes. The equality test leaks some information of messages. Instead, a weak-zero-test is considered in eprint.iacr.org/2017/903. $\endgroup$
    – Hhan
    Oct 9 '21 at 16:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.