qfall_math/integer_mod_q/polynomial_ring_zq/sample/
discrete_gauss.rs

1// Copyright 2023 Jan 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    macros::seeded::seedable_function,
17    rational::Q,
18};
19
20impl PolynomialRingZq {
21    seedable_function!(
22        /// Initializes a new [`PolynomialRingZq`] with maximum degree `modulus.get_degree() - 1`
23        /// and with each entry sampled independently according to the
24        /// discrete Gaussian distribution.
25        ///
26        /// Parameters:
27        /// - `modulus`: specifies the [`ModulusPolynomialRingZq`] over which the
28        ///   ring of polynomials modulo `modulus.get_q()` is defined
29        /// - `center`: specifies the positions of the center with peak probability
30        /// - `s`: specifies the Gaussian parameter, which is proportional
31        ///   to the standard deviation `sigma * sqrt(2 * pi) = s`
32        #[seeded]
33        /// - `seed`: specifies the 256-bit seed of the PRNG used for sampling
34        #[optionally_seeded]
35        /// - `seed`: specifies an optional 256-bit seed of the PRNG used for sampling.
36        #[optionally_seeded]
37        ///   If `None` is provided, a fresh [`ThreadRng`](rand::rngs::ThreadRng) is used instead.
38        ///
39        /// Returns a fresh [`PolynomialRingZq`] instance of length `modulus.get_degree() - 1`
40        /// with coefficients chosen independently according the discrete Gaussian distribution or
41        /// a [`MathError`] if `s < 0`.
42        ///
43        /// # Examples
44        /// ```
45        /// use qfall_math::integer_mod_q::{PolynomialRingZq, ModulusPolynomialRingZq};
46        /// use std::str::FromStr;
47        /// let modulus = ModulusPolynomialRingZq::from_str("3  1 2 1 mod 17").unwrap();
48        ///
49        #[unseeded]
50        /// let sample = PolynomialRingZq::sample_discrete_gauss(&modulus, 0, 1).unwrap();
51        #[seeded]
52        /// let sample = PolynomialRingZq::sample_discrete_gauss_seeded(&modulus, 0, 1, [42; 32]).unwrap();
53        /// ```
54        ///
55        /// # Errors and Failures
56        /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
57        ///   if `s < 0`.
58        ///
59        /// # Panics ...
60        /// - if the provided [`ModulusPolynomialRingZq`] has degree `0` or smaller.
61        pub(crate) fn sample_discrete_gauss(
62            modulus: impl Into<ModulusPolynomialRingZq>,
63            center: impl Into<Q>,
64            s: impl Into<Q>,
65            seed: Option<[u8; 32]>,
66        ) -> Result<Self, MathError> {
67            let modulus = modulus.into();
68            assert!(
69                modulus.get_degree() > 0,
70                "ModulusPolynomial of degree 0 is insufficient to sample over."
71            );
72
73            let poly_z = PolyOverZ::sample_discrete_gauss_optionally_seeded(
74                modulus.get_degree() - 1,
75                center,
76                s,
77                seed,
78            )?;
79            let mut poly_ringzq = PolynomialRingZq {
80                poly: poly_z,
81                modulus,
82            };
83            poly_ringzq.reduce();
84
85            Ok(poly_ringzq)
86        }
87    );
88}
89
90#[cfg(test)]
91mod test_sample_discrete_gauss {
92    use crate::utils::sample::test_seed;
93    use crate::{
94        integer::Z,
95        integer_mod_q::{ModulusPolynomialRingZq, PolyOverZq, PolynomialRingZq},
96        rational::Q,
97        traits::{GetCoefficient, SetCoefficient},
98    };
99    use std::str::FromStr;
100
101    /// Checks whether `sample_discrete_gauss` is available for all types
102    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
103    /// or [`Into<Q>`], i.e. u8, i16, f32, Z, Q, ...
104    #[test]
105    fn availability() {
106        for seeded in [false, true] {
107            let center = Q::ZERO;
108            let s = Q::ONE;
109            let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
110
111            let _ = PolynomialRingZq::sample_discrete_gauss_optionally_seeded(
112                &modulus,
113                0f32,
114                1u8,
115                seeded.then(test_seed),
116            );
117            let _ = PolynomialRingZq::sample_discrete_gauss_optionally_seeded(
118                &modulus,
119                0f64,
120                1u16,
121                seeded.then(test_seed),
122            );
123            let _ = PolynomialRingZq::sample_discrete_gauss_optionally_seeded(
124                &modulus,
125                0f32,
126                1u32,
127                seeded.then(test_seed),
128            );
129            let _ = PolynomialRingZq::sample_discrete_gauss_optionally_seeded(
130                &modulus,
131                0f64,
132                1u64,
133                seeded.then(test_seed),
134            );
135            let _ = PolynomialRingZq::sample_discrete_gauss_optionally_seeded(
136                &modulus,
137                0f32,
138                1i8,
139                seeded.then(test_seed),
140            );
141            let _ = PolynomialRingZq::sample_discrete_gauss_optionally_seeded(
142                &modulus,
143                0f32,
144                1i16,
145                seeded.then(test_seed),
146            );
147            let _ = PolynomialRingZq::sample_discrete_gauss_optionally_seeded(
148                &modulus,
149                0f32,
150                1i32,
151                seeded.then(test_seed),
152            );
153            let _ = PolynomialRingZq::sample_discrete_gauss_optionally_seeded(
154                &modulus,
155                0f64,
156                1i64,
157                seeded.then(test_seed),
158            );
159            let _ = PolynomialRingZq::sample_discrete_gauss_optionally_seeded(
160                &modulus,
161                center,
162                s,
163                seeded.then(test_seed),
164            );
165            let _ = PolynomialRingZq::sample_discrete_gauss_optionally_seeded(
166                &modulus,
167                0f32,
168                1f64,
169                seeded.then(test_seed),
170            );
171
172            // explicitly checks the existence of the unseeded and the seeded function
173            if seeded {
174                let _ = PolynomialRingZq::sample_discrete_gauss_seeded(
175                    &modulus,
176                    0f32,
177                    1u8,
178                    test_seed(),
179                );
180            } else {
181                let _ = PolynomialRingZq::sample_discrete_gauss(&modulus, 0f32, 1u8);
182            }
183        }
184    }
185
186    /// Checks whether the boundaries of the interval are kept for small moduli.
187    #[test]
188    fn boundaries_kept_small() {
189        for seeded in [false, true] {
190            let modulus = ModulusPolynomialRingZq::from_str("4  1 0 0 1 mod 17").unwrap();
191
192            for _ in 0..32 {
193                let poly = PolynomialRingZq::sample_discrete_gauss_optionally_seeded(
194                    &modulus,
195                    15,
196                    1,
197                    seeded.then(test_seed),
198                )
199                .unwrap();
200
201                for i in 0..3 {
202                    let sample: Z = poly.get_coeff(i).unwrap();
203                    assert!(Z::ZERO <= sample);
204                    assert!(sample < modulus.get_q());
205                }
206            }
207        }
208    }
209
210    /// Checks whether the boundaries of the interval are kept for large moduli.
211    #[test]
212    fn boundaries_kept_large() {
213        for seeded in [false, true] {
214            let modulus =
215                ModulusPolynomialRingZq::from_str(&format!("4  1 0 0 1 mod {}", u64::MAX)).unwrap();
216
217            for _ in 0..256 {
218                let poly = PolynomialRingZq::sample_discrete_gauss_optionally_seeded(
219                    &modulus,
220                    1,
221                    1,
222                    seeded.then(test_seed),
223                )
224                .unwrap();
225
226                for i in 0..3 {
227                    let sample: Z = poly.get_coeff(i).unwrap();
228                    assert!(Z::ZERO <= sample);
229                    assert!(sample < modulus.get_q());
230                }
231            }
232        }
233    }
234
235    /// Checks whether the number of coefficients is correct.
236    #[test]
237    fn nr_coeffs() {
238        for seeded in [false, true] {
239            let degrees = [1, 3, 7, 15, 32, 120];
240            for degree in degrees {
241                let mut modulus = PolyOverZq::from((1, u64::MAX));
242                modulus.set_coeff(degree, 1).unwrap();
243                let modulus = ModulusPolynomialRingZq::from(&modulus);
244
245                let res = PolynomialRingZq::sample_discrete_gauss_optionally_seeded(
246                    &modulus,
247                    i64::MAX,
248                    1,
249                    seeded.then(test_seed),
250                )
251                .unwrap();
252
253                assert_eq!(
254                    res.get_degree() + 1,
255                    modulus.get_degree(),
256                    "Could fail with negligible probability."
257                );
258            }
259        }
260    }
261
262    /// Checks whether 0 degree modulus polynomial is insufficient.
263    #[test]
264    fn invalid_modulus() {
265        for seeded in [false, true] {
266            let result = std::panic::catch_unwind(|| {
267                let modulus = ModulusPolynomialRingZq::from_str("1  1 mod 17").unwrap();
268
269                let _ = PolynomialRingZq::sample_discrete_gauss_optionally_seeded(
270                    &modulus,
271                    0,
272                    1,
273                    seeded.then(test_seed),
274                )
275                .unwrap();
276            });
277            assert!(result.is_err());
278        }
279    }
280
281    /// Checks whether the same seed results in the same sample.
282    #[test]
283    fn same_seed_same_sample() {
284        use crate::integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq};
285        use std::str::FromStr;
286        let modulus = ModulusPolynomialRingZq::from_str("3  1 2 1 mod 17").unwrap();
287        let sample_0 =
288            PolynomialRingZq::sample_discrete_gauss_seeded(&modulus, 0, 1, [42; 32]).unwrap();
289        let sample_1 =
290            PolynomialRingZq::sample_discrete_gauss_seeded(&modulus, 0, 1, [42; 32]).unwrap();
291
292        assert_eq!(sample_0, sample_1);
293    }
294
295    /// Checks whether the seeded variant outputs the known sample for a fixed seed.
296    #[test]
297    fn known_answer() {
298        use crate::integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq};
299        use std::str::FromStr;
300        let modulus = ModulusPolynomialRingZq::from_str("3  1 2 1 mod 17").unwrap();
301        let sample =
302            PolynomialRingZq::sample_discrete_gauss_seeded(&modulus, 0, 1, [42; 32]).unwrap();
303
304        assert_eq!("1  1 / 3  1 2 1 mod 17", sample.to_string());
305    }
306}
qfall_math/integer_mod_q/polynomial_ring_zq/sample/discrete_gauss.rs

qfall_math/integer_mod_q/polynomial_ring_zq/sample/
discrete_gauss.rs
