Secure (sub-exponential time) FHE

mikeazo

2/9/23, 1:42 PM

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?

0 + 0

homomorphic-encryption

deterministic-encryption

kelalaka

2/9/23, 2:19 PM

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..

Hhan

2/9/23, 4:14 PM

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.

Hhan

2/9/23, 4:18 PM

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 https://eprint.iacr.org/2017/903.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Secure (sub-exponential time) FHE

TH: ปลอดภัย (เวลาย่อยเอ็กซ์โพเนนเชียล) FHE

RO: Securizat (timp sub-exponenţial) FHE

RU: Безопасный (субэкспоненциальное время) FHE

VI: An toàn (thời gian theo cấp số nhân) FHE

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.