qfall_math/integer_mod_q/z_q/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 to the discrete Gaussian distribution.
10
11use crate::{
12    error::MathError,
13    integer_mod_q::{Modulus, Zq},
14    rational::Q,
15    utils::sample::discrete_gauss::{DiscreteGaussianIntegerSampler, LookupTableSetting, TAILCUT},
16};
17
18impl Zq {
19    /// Chooses a [`Zq`] instance chosen according to the discrete Gaussian distribution
20    /// in `[center - ⌈6 * s⌉ , center + ⌊ 6 * s⌋ ]`.
21    ///
22    /// This function samples discrete Gaussians according to the definition of
23    /// SampleZ in [GPV08](https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=d9f54077d568784c786f7b1d030b00493eb3ae35).
24    ///
25    /// Parameters:
26    /// - `modulus`: specifies the modulus of the new [`Zq`] element
27    /// - `center`: specifies the position 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 new [`Zq`] sample chosen according to the specified discrete Gaussian
32    /// distribution or a [`MathError`] if the specified parameters were not chosen
33    /// appropriately, i.e. `s < 0`.
34    ///
35    /// # Examples
36    /// ```
37    /// use qfall_math::integer_mod_q::Zq;
38    ///
39    /// let sample = Zq::sample_discrete_gauss(17, 0, 1).unwrap();
40    /// ```
41    ///
42    /// # Errors and Failures
43    /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
44    ///   if `s < 0`.
45    ///
46    /// # Panics ...
47    /// - if `modulus` is smaller than `2`.
48    ///
49    /// This function implements SampleZ according to:
50    /// - \[1\] Gentry, Craig and Peikert, Chris and Vaikuntanathan, Vinod (2008).
51    ///   Trapdoors for hard lattices and new cryptographic constructions.
52    ///   In: Proceedings of the fortieth annual ACM symposium on Theory of computing.
53    ///   <https://dl.acm.org/doi/pdf/10.1145/1374376.1374407>
54    pub fn sample_discrete_gauss(
55        modulus: impl Into<Modulus>,
56        center: impl Into<Q>,
57        s: impl Into<Q>,
58    ) -> Result<Self, MathError> {
59        let modulus: Modulus = modulus.into();
60        let center: Q = center.into();
61        let s: Q = s.into();
62
63        let mut dgis = DiscreteGaussianIntegerSampler::init(
64            &center,
65            &s,
66            unsafe { TAILCUT },
67            LookupTableSetting::NoLookup,
68        )?;
69
70        let sample = dgis.sample_z();
71        Ok(Zq::from((&sample, &modulus)))
72    }
73}
74
75#[cfg(test)]
76mod test_sample_discrete_gauss {
77    use crate::{integer::Z, integer_mod_q::Zq, rational::Q};
78
79    // Appropriate interval and invalid inputs were tested in
80    // utils::sample::discrete_gauss::test_sample_z and are thus omitted here.
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 z = Z::from(2);
88        let q = Q::from(2);
89
90        let _ = Zq::sample_discrete_gauss(17u64, 7u8, 1u16);
91        let _ = Zq::sample_discrete_gauss(17u16, 7u16, 1u8);
92        let _ = Zq::sample_discrete_gauss(17u8, 7u32, 1u32);
93        let _ = Zq::sample_discrete_gauss(17u32, 7u64, 1u64);
94        let _ = Zq::sample_discrete_gauss(17i16, 7i8, 1i64);
95        let _ = Zq::sample_discrete_gauss(17i8, 7i16, 1i32);
96        let _ = Zq::sample_discrete_gauss(17i64, 7i32, 1i16);
97        let _ = Zq::sample_discrete_gauss(17i32, 7i64, 1i8);
98        let _ = Zq::sample_discrete_gauss(17, q.clone(), 1i64);
99        let _ = Zq::sample_discrete_gauss(z.clone(), 0i8, z.clone());
100        let _ = Zq::sample_discrete_gauss(17, z.clone(), q.clone());
101        let _ = Zq::sample_discrete_gauss(17, 1f32, 1f64);
102        let _ = Zq::sample_discrete_gauss(17, 1f64, 1f32);
103
104        // With references
105        let _ = Zq::sample_discrete_gauss(17i64, 7i32, 1i16);
106        let _ = Zq::sample_discrete_gauss(17i32, 7i64, 1i8);
107        let _ = Zq::sample_discrete_gauss(17, &q, 1i64);
108        let _ = Zq::sample_discrete_gauss(&z, 0i8, &z);
109        let _ = Zq::sample_discrete_gauss(17, &z, &q);
110    }
111
112    /// Roughly checks the collected samples are distributed
113    /// according to the discrete Gaussian distribution.
114    ///
115    /// This test could possibly fail for a truly uniform distribution
116    /// with probability smaller than 1/1000.
117    #[test]
118    fn distribution() {
119        let mut counts = [0; 20];
120        // count sampled instances
121        for _ in 0..200 {
122            let sample = Zq::sample_discrete_gauss(20, 0, 2).unwrap();
123            let sample_int = i64::try_from(&sample.get_representative_least_nonnegative_residue())
124                .unwrap() as usize;
125            counts[sample_int] += 1;
126        }
127
128        let expl_text = String::from("This test can fail with probability close to 0. 
129        It fails if the sampled occurrences do not look like a typical discrete Gaussian random distribution. 
130        If this happens, rerun the tests several times and check whether this issue comes up again.");
131
132        // Check that the sampled occurrences roughly look
133        // like a discrete Gaussian distribution
134        assert!(counts[0] > 70, "{expl_text}");
135        assert!(counts[0] < 130, "{expl_text}");
136        assert!(counts[19] > 20, "{expl_text}");
137        assert!(counts[19] < 70, "{expl_text}");
138        assert!(counts[1] > 20, "{expl_text}");
139        assert!(counts[1] < 70, "{expl_text}");
140        assert!(counts[18] < 20, "{expl_text}");
141        assert!(counts[2] < 20, "{expl_text}");
142        for count in counts.iter().take(18).skip(3) {
143            assert!(count < &10, "{expl_text}");
144        }
145    }
146}
qfall_math/integer_mod_q/z_q/sample/discrete_gauss.rs

qfall_math/integer_mod_q/z_q/sample/
discrete_gauss.rs
