How to solve the problem of FHE ciphertext expansion?

xiao

1/29/24, 2:32 AM

FHE typically has large ciphertext expansion factor, meaning that the ratio

$$\frac{|\mathsf{Enc}_{pk}(m)|}{|m|}$$

is typically quite large --- in standard schemes it is $\omega(1)$. Even getting $\Theta(1)$ seems to take some work, not to mention the end goal of expansion factor $1 + o(1)$.

To this end, I have seen some work on FHE-friendly block ciphers --- do these help reduce the ciphertext expansion factor of FHE?

Finally, I have seen some people suggest amortization as a way to reduce ciphertext expansion factor, namely encoding multiple "plaintexts" into a single ciphertext (say in BGV/BFV-type schemes). My issue is that this makes it harder to do operations on single-ciphertexts, namely the operations of

filtering, and
comparisons

Is there an FHE scheme of small ciphertext expansion factor supporting these operations? Moreover, is there a binary FHE scheme (along the lines of FHEW/TFHE/FINAL) with these kinds of properties?

103

0 + 4

block-cipher

homomorphic-encryption

data-privacy

Hilder Vitor Lima Pereira

1/29/24, 7:43 PM

This paper presents a "transciphering" (or hybrid homomorphic encryption) technique. It is meant to reduce (or remove) the communication overhead when the client upload data to the server that will run the homomorphic computation. So it is not reducing the ciphertext expansion of the FHE schemes, but just alleviating one of the problems that come from that expansion.

xiao

1/30/24, 2:32 AM

May I ask that this transcoding is only to cut and transmit the FHE ciphertext, and does not reduce the size of the FHE ciphertext?

Hilder Vitor Lima Pereira

1/30/24, 9:24 AM

This technique means that the client encrypt their data using some block cipher (which typically has very low ciphertext expansion), then upload "symmetric" ciphertexts (thus, very small overhead for the communication). But then the server has to transform these ciphertexts into FHE ciphertexts, which have the usual huge ciphertext expansion. Please, search for transciphering or hybrid homomorphic encryption on Google and you will understand that...

Mark

2/3/24, 4:04 AM

Worth mentioning that the transciphering is only "one way" typically. Meaning you can send AES (or whatever block cipher ctxts), expand them to FHE ctxts, but can't switch back to AES. So any intermediate computations you store are still "large", and any results you send back to the client are "large". There are compression techniques for FHE that reduce significant amounts of the overhead though, namely section 3 of [this paper](https://eprint.iacr.org/2019/720.pdf). The issue is that you can't homomorphically operate on the shrunken ctxts, and probably need to bootstrap to regain FHE ops.

Elon Musk

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

EN: How to solve the problem of FHE ciphertext expansion?

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.