qFALL-math beyond types

This chapter includes the presentation of some helpful additional features, which we believe will be helpful for a more complex use of qFALL-math.

Random Sampling

... according to the uniform distribution

Drawing uniform random samples is an inevitable part of modern and post-quantum cryptography. Thus, we provide this feature with cryptographically secure randomness.

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

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, uniform_sample_z is uniformly random sampled over the interval \( [-5, 4] \). The function returns an error if the specified interval does not include at least two integer values.

The sampling for Zq is a little easier to instantiate as sample_uniform samples uniformly over the interval \( [0, \text{modulus}-1] \) for the given modulus parameter.

Furthermore, it is possible to instantiate matrices uniformly at random. In these cases, the first two parameters specify the dimensions of the newly created matrix. All subsequent parameters determine - as is the case for the integer data types - the size of the interval over which sampling takes place.

let uniform_matz = MatZ::sample_uniform(2, 2, -5, 5)?;
let uniform_matzq = MatZq::sample_uniform(2, 2, 7);

All sampling is also available for all our polynomial (matrix) data types except PolyOverQ. Their instantiation looks similar to the ones presented above. Please, refer to the documentation to find specifics.

The random number generator used for instantiation of uniformly random bits is ThreadRng from Rust's rand-crate and considered to be cryptographically secure.

... according to the discrete Gaussian distribution

Discrete Gaussians are often required to instantiate lattice-based problems like Learning with Errors. Hence, we also support the instantiation of integer data types sampled according to the discrete Gaussian distribution.

let n = 1024;
let center = 0;
let s = 1;

let discrete_gauss_sample_z = Z::sample_discrete_gauss(&n, &center, &s)?;

let modulus = 7;
let discrete_gauss_sample_zq = Zq::sample_discrete_gauss(&modulus, &n, &center, &s)?;

The discrete Gaussian distribution is implemented via a rejection sampling algorithm called SampleZ from GPV08. This algorithm takes the security parameter n, a center, and the Gaussian parameter s to sample a value \( x \) according to the discrete Gaussian distribution over the interval \( [c - s \log n, c + s \log n] \cap \mathbb{Z} \). center defines the value with peak probability.

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 a center vector, which is \( 0 \) in our example. This center does not have to be a lattice point. The lattice to sample from must be specified via a basis.

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

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

... according to the binomial distribution

As discrete Gaussian sampling is expensive and usually not done in constant time, several schemes replace it by a similar binomial distribution. Thus, we offer binomial sampling for all of our data types as well.

let binomial_sample_z = Z::sample_binomial(5, 0.5)?;
let binomial_sample_zq = Zq::sample_binomial(3, 5, 0.5)?;

The last first two parameters denote the number of experiments n and probability p with which these experiments succeed. Any parameters preceding these, are specific to their type. For sampling with the center around a specific value like 0, qFALL offers sample_binomial_with_offset.