Abstract
Lattice-based cryptography is arguably the most popular paradigm for cryptographic primitives designed to maintain data security in the age of quantum computers. One prevalent component of these primitives is the Gaussian sampler - a random number generator producing Gaussian-distributed values. The work in this thesis aims to explore candidate algorithms for the secure sampling of Gaussian distributions with high standard deviation.The sampling methods chosen for this research are all well-suited to producing wide distributions, in that their complexities do not grow with the standard deviation. Three new sampling algorithms are proposed, securing such methods by drawing on both novel solutions and common cryptographic techniques. All constructions in this thesis are designed to enable arbitrary precision, in blocks of 64 bits.
This thesis aims to develop algorithms for Gaussian sampling which are robust against side-channel analysis. Side-channel vulnerabilities consist of physical properties of the device on which the algorithms are being executed. These can include power and voltage measurements, or just the timing of the algorithms. When these measurements can be made during an algorithm’s execution, any variation in these which are dependent on secret data can leak information. Thus, this thesis aims to construct algorithms which run in constant time or minimise these variations.
The first method discussed is the Ziggurat, a fast and lightweight rejection sampler which uses rectangular boxes to minimise calls to the Gaussian function. This method samples from the discrete Gaussian distribution and is the only discrete sampler able to reach high standard deviation with no additional performance or memory costs. To address the information leakage through side channels in this sampler, a constant-time, fixed-point algorithm to evaluate the Gaussian function was constructed. Then, further work was conducted to adjust the Ziggurat algorithm to eliminate immediate value leakage from timing. Two timing paths remain, which is the best a rejection sampler can be expected to have, but they now each have a probability distribution over the entire range of output values. The resulting Ziggurat design is better-suited for use with side-channel countermeasures and retains its competitive performance and memory profile.
The second and third contributions involve secure sampling algorithms for rounded, continuous Gaussian distributions, shown to be provably secure for use in lattice-based signatures. Both of these make use of the Box-Muller sampling algorithm, which utilises an inverse Gaussian transformation from uniform random values to standard normal random values. Wider distributions can be achieved by multiplying each sample by the standard deviation. Numerous methods exist for evaluating the transcendental functions required by the Box-Muller sampler. This thesis proposes two algorithms for these evaluations and makes novel adjustments to ensure the security of their implementation.
The first Box-Muller algorithm is computed using the CORDIC family of algorithms, which use coordinate rotations to calculate the transcendental functions. These are lightweight algorithms and are well-studied, outside of lattice-based cryptography. There is, hence, a plethora of literature offering ways of reducing run-time and parallelising the algorithm. The CORDIC family also ports to hardware efficiently, in that the use of a multiplication operation is not required and circuit space is saved. The second significant contribution of this thesis is the closing of side-channel vulnerabilities in the CORDIC algorithm for Box-Muller sampling. Side-channel countermeasures are not required for this sampler, as it is designed to be secure against conventional side-channel attacks on its own.
The second Box-Muller algorithm evaluates the constituent functions by polynomial approximation. For this, a separate algorithm to find the best polynomial approximations, known as the Remez algorithm, was constructed. Remez polynomials are of the interpolating kind and can be found for the entire domain of the function, or for several splines over the domain, whereby the degree of polynomial required can be reduced. Polynomials can be evaluated in constant-time with fixed-point precision trivially and over splines. Resulting from this work is a side-channel-secure method of sampling, with a time-memory trade-off which is capable of outperforming the current state-of-the-art secure samplers.
| Date of Award | Dec 2021 |
|---|---|
| Original language | English |
| Awarding Institution |
|
| Supervisor | Ayesha Khalid (Supervisor) & Maire O'Neill (Supervisor) |