Lattice-based cryptography: secret from Gaussian distribution chi

Karim

1/10/23, 11:01 AM

In a lecture, by Chris Peikert (link 40:20), he showed more efficient cryptosystems that have the secret be drawn from the Gaussian error distribution $\chi$. In the lecture he said "some applications which really really need secrets to come from the error distribution and they don't really work so well if they come from uniform distribution" and he adds "for some strange reason this is the form is what gets you further in terms of building applications like Full Homomorphic Encryption (FHE)".

Do we know today why this is the case?
What efficiency does error distribution bring over a uniform one?

Edit: update the information

0 + 0

lattice-crypto

Hilder Vitor Lima Pereira

1/10/23, 11:35 AM

Are you sure he said the application only worked with Gaussian secret or the requirement is that the secret has small norm? Maybe you should check this, because some FHE schemes work well when the secret is short, but "short" can be Gaussian, binary, ternary...

Karim

1/14/23, 12:56 PM

Sorry for the late reply I was trying to find where I heard that. So it wasn't from Vadim Lyubashevsky but Chris Peikert during a Winter School. I will update by question with link to the lecture.

Score:2

Crypto

Chris Peikert

1/14/23, 1:10 PM

Some FHE operations, like “modulus switching/reduction,” need a “small” LWE secret to work. Similarly, some cryptosystems like Lyubashevsky-Peikert-Regev’10 and Lindner-Peikert’11 have smaller keys and/or ciphertexts (and correspondingly faster operations) thanks to the use of a “small” secret.

Smaller secrets yield better efficiency in these systems, but for security there is a limit to how small we can take them to be. It was proved in Applebaum-Cash-Peikert-Sahai’09 that drawing the LWE secret from the error distribution (which yields a relatively small secret) is essentially no less secure than using a uniformly random secret.

0 + 0

Karim

1/15/23, 9:11 AM

So if I understand correctly, drawing the secret from the error distribution kills 2 birds with one stone. It gives small secrets without sacrificing security by making the secret too small. Is that correct?

Chris Peikert

1/15/23, 11:40 AM

Yes, that’s the short version.

Hilder Vitor Lima Pereira

1/15/23, 11:45 AM

The [LWE with binary secrets is also proven to be secure](https://theoryofcomputing.org/articles/v014a013/v014a013.pdf), you just have to increase the dimension $n$. However, I think that there is no worst-case to average-case reduction for the RLWE with binary or ternary secrets, but people use it anyway, like in HElib or TFHE, since it is still possible to estimate concrete security for such secrets and they are even shorter than when the distribution is Gaussian...

Chris Peikert

1/15/23, 12:13 PM

@HilderVitorLimaPereira All that is true. However, using a binary/ternary secret stands on less firm ground (security-wise) than using the error distribution, since it is based only on known cryptanalysis, whereas using the error distribution has a tight hardness proof based on the original LWE problem. So we have a typical tradeoff between what seems to be secure versus what we can prove.

Elon Musk

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

EN: Lattice-based cryptography: secret from Gaussian distribution chi

TH: การเข้ารหัสแบบ Lattice: ความลับจาก Gaussian distribution chi

RO: Criptografia bazată pe zăbrele: secret din distribuția gaussiană chi

RU: Криптография на основе решеток: секрет гауссовского распределения чи

VI: Mật mã dựa trên lưới: bí mật từ chi phân phối Gaussian

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.