qfall_math/integer_mod_q/polynomial_ring_zq/sample/
uniform.rs

1// Copyright © 2023 Niklas Siemer
2//
3// This file is part of qFALL-math.
4//
5// qFALL-math is free software: you can redistribute it and/or modify it under
6// the terms of the Mozilla Public License Version 2.0 as published by the
7// Mozilla Foundation. See <https://mozilla.org/en-US/MPL/2.0/>.
8
9//! This module contains algorithms for sampling according to the uniform distribution.
10
11use crate::{
12    integer::PolyOverZ,
13    integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq},
14};
15
16impl PolynomialRingZq {
17    /// Generates a [`PolynomialRingZq`] instance with maximum degree `modulus.get_degree() - 1`
18    /// and coefficients chosen uniform at random in `[0, modulus.get_q())`.
19    ///
20    /// The internally used uniform at random chosen bytes are generated
21    /// by [`ThreadRng`](rand::rngs::ThreadRng), which uses ChaCha12 and
22    /// is considered cryptographically secure.
23    ///
24    /// Parameters:
25    /// - `modulus`: specifies the [`ModulusPolynomialRingZq`] over which the
26    ///   ring of polynomials modulo `modulus.get_q()` is defined
27    ///
28    /// Returns a fresh [`PolynomialRingZq`] instance of length `modulus.get_degree() - 1`
29    /// with coefficients chosen uniform at random in `[0, modulus.get_q())`.
30    ///
31    /// # Examples
32    /// ```
33    /// use qfall_math::integer_mod_q::{PolynomialRingZq, ModulusPolynomialRingZq};
34    /// use std::str::FromStr;
35    /// let modulus = ModulusPolynomialRingZq::from_str("3  1 2 3 mod 17").unwrap();
36    ///
37    /// let sample = PolynomialRingZq::sample_uniform(&modulus);
38    /// ```
39    ///
40    /// # Panics ...
41    /// - if the provided [`ModulusPolynomialRingZq`] has degree `0` or smaller.
42    pub fn sample_uniform(modulus: impl Into<ModulusPolynomialRingZq>) -> Self {
43        let modulus = modulus.into();
44        assert!(
45            modulus.get_degree() > 0,
46            "ModulusPolynomial of degree 0 is insufficient to sample over."
47        );
48
49        let poly_z =
50            PolyOverZ::sample_uniform(modulus.get_degree() - 1, 0, modulus.get_q()).unwrap();
51
52        // we do not have to reduce here, as all entries are already in the correct range
53        // hence directly setting is more efficient
54        PolynomialRingZq {
55            poly: poly_z,
56            modulus,
57        }
58    }
59}
60
61#[cfg(test)]
62mod test_sample_uniform {
63    use crate::{
64        integer::Z,
65        integer_mod_q::{ModulusPolynomialRingZq, PolyOverZq, PolynomialRingZq},
66        traits::{GetCoefficient, SetCoefficient},
67    };
68    use std::str::FromStr;
69
70    /// Checks whether the boundaries of the interval are kept for small moduli.
71    #[test]
72    fn boundaries_kept_small() {
73        let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
74
75        for _ in 0..32 {
76            let poly = PolynomialRingZq::sample_uniform(&modulus);
77
78            for i in 0..3 {
79                let sample: Z = poly.get_coeff(i).unwrap();
80                assert!(Z::ZERO <= sample);
81                assert!(sample < modulus.get_q());
82            }
83        }
84    }
85
86    /// Checks whether the boundaries of the interval are kept for large moduli.
87    #[test]
88    fn boundaries_kept_large() {
89        let modulus =
90            ModulusPolynomialRingZq::from_str(&format!("4  1 0 0 1 mod {}", u64::MAX)).unwrap();
91
92        for _ in 0..256 {
93            let poly = PolynomialRingZq::sample_uniform(&modulus);
94
95            for i in 0..3 {
96                let sample: Z = poly.get_coeff(i).unwrap();
97                assert!(Z::ZERO <= sample);
98                assert!(sample < modulus.get_q());
99            }
100        }
101    }
102
103    /// Checks whether the number of coefficients is correct.
104    #[test]
105    fn nr_coeffs() {
106        let degrees = [1, 3, 7, 15, 32, 120];
107        for degree in degrees {
108            let mut modulus = PolyOverZq::from((1, u64::MAX));
109            modulus.set_coeff(degree, 1).unwrap();
110            let modulus = ModulusPolynomialRingZq::from(&modulus);
111
112            let res = PolynomialRingZq::sample_uniform(&modulus);
113
114            assert_eq!(
115                res.get_degree() + 1,
116                modulus.get_degree(),
117                "Could fail with probability 1/{}.",
118                u64::MAX
119            );
120        }
121    }
122
123    /// Checks whether 0 modulus polynomial is insufficient.
124    #[test]
125    #[should_panic]
126    fn invalid_modulus() {
127        let modulus = ModulusPolynomialRingZq::from_str("1  1 mod 17").unwrap();
128
129        let _ = PolynomialRingZq::sample_uniform(&modulus);
130    }
131}
qfall_math/integer_mod_q/polynomial_ring_zq/sample/uniform.rs

qfall_math/integer_mod_q/polynomial_ring_zq/sample/
uniform.rs
