3
$\begingroup$

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

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

Edit: update the information

$\endgroup$
2
  • 1
    $\begingroup$ 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... $\endgroup$ Sep 10 '21 at 11:35
  • $\begingroup$ 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. $\endgroup$
    – Karim
    Sep 14 '21 at 12:56
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Karim
    Sep 15 '21 at 9:11
  • 1
    $\begingroup$ Yes, that’s the short version. $\endgroup$ Sep 15 '21 at 11:40
  • 1
    $\begingroup$ The LWE with binary secrets is also proven to be secure, 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... $\endgroup$ Sep 15 '21 at 11:45
  • 2
    $\begingroup$ @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. $\endgroup$ Sep 15 '21 at 12:13

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.