I was reading the NewHope paper, and I see that they are using Binomial distribution and not a discrete Gaussian distribution as was used by BCNS. I also remember hearing somewhere that lattice key exchange does not require a very high precision sampling, whereas signature schemes need high precision sampling. Why is this distinction? How does the sampling algorithm used affect the security in these schemes?


1 Answer 1


The way and the purpose in which gaussians are used in key exchange and digital signatures is completely different.

In public key encryption (and key exchange), we need computational-indistinguishablilty of (A,As+e) when A is a random matrix (over some ring) and (s,e) are vectors over that same ring with small coefficients. To get the tightest security reduction based on worst-case hard problems, s and e should be gaussian, and this is why it is sometimes (falsely) believed that s and e should be gaussians for security. In reality, they don't need to be -- the distinguishability problem seems to be just as hard in practice when s and e are "simpler-to-sample" distributions such as uniform or binomial.

In digital signatures (using the Fiat-Shamir transform), the signature is computed as z=Sc+y, where S is a secret matrix of small coefficients, c is a challenge vector (with very small coefficients) and y is some vector that is chosen during signing. For security, one needs that z has small coefficients and is independent of the secret key S. For z to have small coefficients, y needs to have small coefficients. In order for z to be independent of S, we need to use rejection sampling so that the distribution of y "masks" the shift by Sc. If we don't use high-enough precision here, then we may not get the distribution of z that is statistically independent of S, which will be disastrous for security.

In some recent papers, it was shown that the way to get the shortest possible z requires taking y to be a discrete gaussian, and so you need to be able to sample discrete gaussians with a high precision. It should be mentioned that you can also create digital signatures by simply using the uniform distribution, but thy will be slightly longer.

For hash-and-sign signatures, it's again the same high-level idea as for Fiat-Shamir ones. You want to make sure that the signature is independent of the secret key. The most efficient way we know how to create such signatures is to have them come from the discrete gaussian distribution.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.