Addressing Side-Channel Vulnerabilities in the Discrete Ziggurat Sampler

Post-quantum cryptography with lattices typically requires
high precision sampling of vectors with discrete Gaussian distributions. Lattice signatures require large values of the standard deviation parameter, which poses difficult problems in finding a suitable trade-off between throughput performance and memory resources on constrained devices. In this paper, we propose modifications to the Ziggurat method, known to be advantageous with respect to these issues, but problematic due to its inherent rejection-based timing profile. We improve upon information leakage through timing channels significantly and require: only 64-bit unsigned integers, no floating-point arithmetic, no division and no external libraries. Also proposed is a constant-time Gaussian function, possessing all aforementioned advantageous properties. The measures taken to
secure the sampler completely close side-channel vulnerabilities through direct timing of operations and these have no negative implications on its applicability to lattice-based signatures. We demonstrate the improved method with a 128-bit reference implementation, showing that we retain
the sampler's efficiency and decrease memory consumption by a factor of 100. We show that this amounts to memory savings by a factor of almost 5,000, in comparison to an optimised, state-of-the-art implementation of another popular sampling method, based on cumulative distribution tables.