qfall_math/integer_mod_q/polynomial_ring_zq/sample/
discrete_gauss.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
10//! according to the discrete Gaussian distribution.
11
12use crate::{
13    error::MathError,
14    integer::PolyOverZ,
15    integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq},
16    rational::Q,
17};
18
19impl PolynomialRingZq {
20    /// Initializes a new [`PolynomialRingZq`] with maximum degree `modulus.get_degree() - 1`
21    /// and with each entry sampled independently according to the
22    /// discrete Gaussian distribution.
23    ///
24    /// Parameters:
25    /// - `modulus`: specifies the [`ModulusPolynomialRingZq`] over which the
26    ///   ring of polynomials modulo `modulus.get_q()` is defined
27    /// - `center`: specifies the positions of the center with peak probability
28    /// - `s`: specifies the Gaussian parameter, which is proportional
29    ///   to the standard deviation `sigma * sqrt(2 * pi) = s`
30    ///
31    /// Returns a fresh [`PolynomialRingZq`] instance of length `modulus.get_degree() - 1`
32    /// with coefficients chosen independently according the discrete Gaussian distribution or
33    /// a [`MathError`] if `s < 0`.
34    ///
35    /// # Examples
36    /// ```
37    /// use qfall_math::integer_mod_q::{PolynomialRingZq, ModulusPolynomialRingZq};
38    /// use std::str::FromStr;
39    /// let modulus = ModulusPolynomialRingZq::from_str("3  1 2 3 mod 17").unwrap();
40    ///
41    /// let sample = PolynomialRingZq::sample_discrete_gauss(&modulus, 0, 1).unwrap();
42    /// ```
43    ///
44    /// # Errors and Failures
45    /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
46    ///   if `s < 0`.
47    ///
48    /// # Panics ...
49    /// - if the provided [`ModulusPolynomialRingZq`] has degree `0` or smaller.
50    pub fn sample_discrete_gauss(
51        modulus: impl Into<ModulusPolynomialRingZq>,
52        center: impl Into<Q>,
53        s: impl Into<Q>,
54    ) -> Result<Self, MathError> {
55        let modulus = modulus.into();
56        assert!(
57            modulus.get_degree() > 0,
58            "ModulusPolynomial of degree 0 is insufficient to sample over."
59        );
60
61        let poly_z = PolyOverZ::sample_discrete_gauss(modulus.get_degree() - 1, center, s)?;
62        let mut poly_ringzq = PolynomialRingZq {
63            poly: poly_z,
64            modulus,
65        };
66        poly_ringzq.reduce();
67
68        Ok(poly_ringzq)
69    }
70}
71
72#[cfg(test)]
73mod test_sample_discrete_gauss {
74    use crate::{
75        integer::Z,
76        integer_mod_q::{ModulusPolynomialRingZq, PolyOverZq, PolynomialRingZq},
77        rational::Q,
78        traits::{GetCoefficient, SetCoefficient},
79    };
80    use std::str::FromStr;
81
82    /// Checks whether `sample_discrete_gauss` is available for all types
83    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
84    /// or [`Into<Q>`], i.e. u8, i16, f32, Z, Q, ...
85    #[test]
86    fn availability() {
87        let center = Q::ZERO;
88        let s = Q::ONE;
89        let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
90
91        let _ = PolynomialRingZq::sample_discrete_gauss(&modulus, 0f32, 1u8);
92        let _ = PolynomialRingZq::sample_discrete_gauss(&modulus, 0f64, 1u16);
93        let _ = PolynomialRingZq::sample_discrete_gauss(&modulus, 0f32, 1u32);
94        let _ = PolynomialRingZq::sample_discrete_gauss(&modulus, 0f64, 1u64);
95        let _ = PolynomialRingZq::sample_discrete_gauss(&modulus, 0f32, 1i8);
96        let _ = PolynomialRingZq::sample_discrete_gauss(&modulus, 0f32, 1i16);
97        let _ = PolynomialRingZq::sample_discrete_gauss(&modulus, 0f32, 1i32);
98        let _ = PolynomialRingZq::sample_discrete_gauss(&modulus, 0f64, 1i64);
99        let _ = PolynomialRingZq::sample_discrete_gauss(&modulus, center, s);
100        let _ = PolynomialRingZq::sample_discrete_gauss(&modulus, 0f32, 1f64);
101    }
102
103    /// Checks whether the boundaries of the interval are kept for small moduli.
104    #[test]
105    fn boundaries_kept_small() {
106        let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
107
108        for _ in 0..32 {
109            let poly = PolynomialRingZq::sample_discrete_gauss(&modulus, 15, 1).unwrap();
110
111            for i in 0..3 {
112                let sample: Z = poly.get_coeff(i).unwrap();
113                assert!(Z::ZERO <= sample);
114                assert!(sample < modulus.get_q());
115            }
116        }
117    }
118
119    /// Checks whether the boundaries of the interval are kept for large moduli.
120    #[test]
121    fn boundaries_kept_large() {
122        let modulus =
123            ModulusPolynomialRingZq::from_str(&format!("4  1 0 0 1 mod {}", u64::MAX)).unwrap();
124
125        for _ in 0..256 {
126            let poly = PolynomialRingZq::sample_discrete_gauss(&modulus, 1, 1).unwrap();
127
128            for i in 0..3 {
129                let sample: Z = poly.get_coeff(i).unwrap();
130                assert!(Z::ZERO <= sample);
131                assert!(sample < modulus.get_q());
132            }
133        }
134    }
135
136    /// Checks whether the number of coefficients is correct.
137    #[test]
138    fn nr_coeffs() {
139        let degrees = [1, 3, 7, 15, 32, 120];
140        for degree in degrees {
141            let mut modulus = PolyOverZq::from((1, u64::MAX));
142            modulus.set_coeff(degree, 1).unwrap();
143            let modulus = ModulusPolynomialRingZq::from(&modulus);
144
145            let res = PolynomialRingZq::sample_discrete_gauss(&modulus, i64::MAX, 1).unwrap();
146
147            assert_eq!(
148                res.get_degree() + 1,
149                modulus.get_degree(),
150                "Could fail with negligible probability."
151            );
152        }
153    }
154
155    /// Checks whether 0 degree modulus polynomial is insufficient.
156    #[test]
157    #[should_panic]
158    fn invalid_modulus() {
159        let modulus = ModulusPolynomialRingZq::from_str("1  1 mod 17").unwrap();
160
161        let _ = PolynomialRingZq::sample_discrete_gauss(&modulus, 0, 1).unwrap();
162    }
163}
qfall_math/integer_mod_q/polynomial_ring_zq/sample/discrete_gauss.rs

qfall_math/integer_mod_q/polynomial_ring_zq/sample/
discrete_gauss.rs
