Random Sampling

An essential part of lattice-based cryptography are random values sampled according to specific distributions. qfall-math provides functions to sample from the following distributions efficiently and conveniently. The samplers themselves are implemented in utils::sample.

Uniform Distribution

Drawing uniform random samples is an inevitable part of modern and post-quantum cryptography. Thus, qFALL provides uniform samplers for all reasonable data types.

let uniform_sample_z = Z::sample_uniform(-5, 5)?;
let uniform_sample_zq = Zq::sample_uniform(257);

For Z, the first parameter specifies the inclusive lower bound of the interval, from which is sampled. The second parameter specifies the exclusive upper bound. Hence, the first line samples a random integer from the interval \( [-5, 4] \). The function returns an error if the specified interval is invalid. For Zq, the function samples uniformly from \( [0, \text{modulus}-1] \).

A similar API instantiates polynomials and matrices with each entry sampled from any implemented distribution. In these cases, the first parameters specify the dimensions of the new matrix or the maximum degree of the freshly instantiated polynomial. All subsequent parameters are specific to the distribution to sample from.

let uniform_matz = MatZ::sample_uniform(2, 2, -5, 5)?;
let uniform_polyoverz = PolyOverZ::sample_uniform(256, -5, 5)?;
let uniform_matzq = MatZq::sample_uniform(2, 2, 257);
let uniform_matpolynomialringzq = MatPolynomialRingZq::sample_uniform(2, 2, &modulus);

Discrete Gaussian Distribution

Discrete Gaussians are often required to instantiate lattice-based problems like Learning with Errors. Thus, we support the instantiation of integer and residue class data type sampled according to the discrete Gaussian distribution.

let discrete_gauss_z = Z::sample_discrete_gauss(center, s)?;
let discrete_gauss_zq = Zq::sample_discrete_gauss(modulus, center, s)?;

The discrete Gaussian distribution is implemented via rejection sampling from GPV08. This algorithm takes a center and the Gaussian parameter s to sample a value \( x \) according to the discrete Gaussian distribution over the interval \( [c - 6 * s, c + 6 * s] \cap \mathbb{Z} \). center defines the value(s) with peak probability. The tailcut is chosen as 6 per convention and can be changed here: qfall_math::utils::sample::discrete_gauss::TAILCUT.

Furthermore, qfall-math supports sampling discrete Gaussian over arbitrary lattices by implementing SampleD from GPV08. It outputs a discrete Gaussian distributed point of the lattice centered around center, which is the \( 0 \)-vector in our example. The lattice is specified by a basis and the specified center does not have to be a lattice point.

let basis = MatZ::from_str("[[7,3],[7,0]]")?;
let center = MatQ::new(2, 1);
let s = 8.0;

let discrete_gauss_over_lattice = MatZ::sample_d(&basis, &center, s)?;

Binomial Distribution

As discrete Gaussian sampling is computationally expensive and hard to implement in constant time, several schemes replace it by sampling from a similar binomial distribution.

let binomial_z = Z::sample_binomial(5, 0.5)?;
let binomial_zq = Zq::sample_binomial(3, 5, 0.5)?;

The last two parameters denote the number of experiments n and probability p with which each Bernulli-experiment succeeds. Any parameters preceding these, are specific to their type, i.e. the modulus in case of Zq. To sample centered binomial distributions, qfall-math offers the function sample_binomial_with_offset for each type.

Further Information

The presented samplers are available for all types of integers and residue classes including polynomials and matrices over these types. For rationals, there are fewer and other samplers available. Please, refer to the documentation to find specifics.

All presented samplers use random bits generated by ThreadRng from the rand-crate. This sampler is considered to be cryptographically secure by building on ChaCha with 12 rounds.