Hardware Gaussian random numbers for lattice-based cryptography

Question

I have been recently reading about lattice-based cryptography.

I read that a key aspect of such protocols rely on added Gaussian noise on lattices, and which therefore require highly efficient and constant-time Gaussian samplers, which appears to need non-trivial algorithms. For what I got this is still something that could be improved in lattice-based cryptography.

I know that there are hardware random number generators that naturally produce Gaussian distributions. For example, thermal electronic noise from active and passive components often shows Gaussian behaviour. Also some optical random number generators are known to produce unpredictable and normally distributed random numbers.

My question is: could Gaussian hardware random number generators play a role in adding the Gaussian noise required for the security of lattice-based cryptography?

Or is there something fundamental that I am missing about how these Gaussian sampler must be built? Perhaps related to the choice of the standard deviation? Or because some determinism is preferred?

Any help in understanding this would be helpful, and also any instruction to where to find a good, (simple :-D ) introduction to Gaussian sampling in lattice-based cryptography.

I am very new to the field, so forgive me if I said anything imprecise or incorrect

Kind Regards, Rafa

Answer 1

You are confusing discrete Gaussian sampling with Gaussian sampling. A discrete Gaussian of parameters $\mu, \sigma$ is a random variable supported on $\mathbb{Z}$ with pmf: $$\Pr[X = k]\propto \exp(-\pi \|x-\mu\|^2/\sigma^2)$$ A continuous Gaussian of parameters $\mu, \sigma$ is a random variable supported on $\mathbb{R}$ with pdf: $$\Pr[X = r] \propto\exp(-\pi \|x - \mu\|^2/\sigma^2)$$ One natural hope would be that discrete Gaussians are simply "Continuous Gaussians rounded to the nearest integer". This is not the case (one is left with two distributions which, while similar, are not identical. One particular difference is that I don't believe the sum of two rounded Gaussians is rounded Gaussian, but under suitable restrictions this holds for discrete Gaussians). That being said one can adapt certain proofs to use "rounded Gaussians", which this paper by Hulsing et al. does.

Note that the discrete Gaussian distribution is much harder to sample from than continuous Gaussians. While (under suitable restrictions) it still satisfies a "convolution theorem" that sums of discrete Gaussians are discrete Gaussians, one needs certain restrictions which don't exist in the continuous case. Another example of a difference is that no analogue of the Box-Muller Transform exists for discrete Gaussians, which is a fairly efficient way to generate continuous Gaussians from a uniformly random source.

Sometimes one can even use a random variable which seems less connected to Discrete Gaussians, namely Binomial random variables (which are quite efficient to sample from in constant time). See page 14 of the Kyber paper (a current NIST PQC round 2 KEM candidate) for some discussion of this. Dilithium (a NIST PQC round 2 signature candidate) uses uniform noise due to concerns with implementing discrete Gaussian sampling efficiently in constant time.

As for a good introduction to the literature, there has been some work before about hardware implementations (here, although I don't know enough about hardware to evaluate the work. Beyond this Micciancio has some links to recent work, although it is missing some papers from the last year (which are essentially updates to current NIST PQC candidate's samplers).

I generically like Michael Walter's exposition of existing methods (see for example section 6 in this paper or section 3 of this paper). If one starts there, and then additionally looks at recent work on NIST PQC round 2 candidates (in particular the lattice based signature schemes Falcon and qTESLA) that'd be a very good start.