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

qfall_math/integer_mod_q/poly_over_zq/sample/
discrete_gauss.rs
