search

estimate-all-the-lwe-ntru-schemes / estimate-all-the-lwe-ntru-schemes.github.io

Repository and website for the Estimate all the {LWE, NTRU} schemes! code and paper.
23 stars 7 forks source link

Why in Saber, the secret distribution is taken “normal”? #14

Open Suparna-Kundu opened 4 years ago

Suparna-Kundu commented 4 years ago

In the security code of scheme Saber, the secret distribution is taken “normal”. Here https://lwe-estimator.readthedocs.io/en/latest/_apidoc/estimator.html in estimator description, it is mentioned that normal form instances, i.e. the secret follow the noise distribution. But in Saber, the noise distribution and secret distribution are different. Can you please explain the reason to me?

fvirdia commented 4 years ago

Hi!

You are indeed right, and this is an error on our part. We did our best pulling parameters from each submission, but we must have got it wrong with Saber.

Given the constraints of the estimator (in particular: the error distribution is always assumed gaussian), I would consider setting sd (the error standard deviation) to be the standard deviation of the centered binomial distribution, and the secret distribution to be a uniform bounded distribution such as (-q/2p, q/2p).

This apparent swap between error and secret distribution should not be a problem, since every LWE sample (A, As+e) can be considered as an LWE sample (A^-1, A^-1 e + s) with distributions swapped.

Note: inverting assumes A to be square, but usually m=n and m=2n don't result in a big change in attack cost.

Another option could be simply setting sd to have the standard deviation of the uniform distribution in (-q/2p, q/2p), and patch the estimator to allow gaussian noise with a standard deviation different from that of the gaussian error distribution, which is currently not supported.