0
$\begingroup$

My understanding is that the sampling precision in Gaussian Noise sampler is related to security. But not sure about why is that? I read that when the samples are floating-point numbers and precision after the decimal point is equivalent to 72 bits that can be correlated to 128-bit security.

However, certain schemes use 32 bits precision, so how does that impact the security? And what is a good number to select for the precision value? Also, if the samples are integer values then how to deal with precision and security?

$\endgroup$
0
$\begingroup$

The discrete Gaussian distruibution have the most entropy at the same standard deviation compared to other discrete probability distributions. It's important in some LWE/SIS digital signature algorithms because it helps reduces the signature size (most notably in BLISS and FALCON), but otherwise not so essential in key exchange or encryption (and has been replaced with binomial distribution in NewHope).

The reason using Gaussian distribution reduces the signature size, is because it allows certain entries in the signature to be represented with shorter codewords using e.g. Huffman coding. But doing it right can be difficult, as slightest observable difference from true discrete Gaussian distribution can lead to leak of private key information.

Take a Fiat-Shamir signature scheme as an example, the signature $z$ is calculated as:

$z = Ay+sc$

Where $A$ is a component of the public key, $s$ is a private key component, and $c$ is the output of hash function and $y$ is randomly generated according to discreate Gaussian distribution.

We want $z$ also be in discrete Gaussian distribution, becuase

  1. since we've added $sc$ to bind the private key to the signature, and

  2. $c$ is a public component,

we have to hide the private component with $Ay$. And here, in order to achieve the expected distribution, rejection sampling is used.

See also: How would low-precision Gaussian sampling impact the security of BLISS?

$\endgroup$

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.