qfall_math/integer_mod_q/z_q/sample/

discrete_gauss.rs

// Copyright 2023 Jan Niklas Siemer
//
// This file is part of qFALL-math.
//
// qFALL-math is free software: you can redistribute it and/or modify it under
// the terms of the Mozilla Public License Version 2.0 as published by the
// Mozilla Foundation. See <https://mozilla.org/en-US/MPL/2.0/>.

//! This module contains algorithms for sampling according to the discrete Gaussian distribution.

use crate::{
    error::MathError,
    integer_mod_q::{Modulus, Zq},
    macros::seeded::seedable_function,
    rational::Q,
    utils::sample::discrete_gauss::{DiscreteGaussianIntegerSampler, LookupTableSetting, TAILCUT},
};

impl Zq {
    seedable_function!(
        /// Chooses a [`Zq`] instance chosen according to the discrete Gaussian distribution
        /// in `[center - ⌈6 * s⌉ , center + ⌊ 6 * s⌋ ]`.
        ///
        /// This function samples discrete Gaussians according to the definition of
        /// SampleZ in [GPV08](https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=d9f54077d568784c786f7b1d030b00493eb3ae35).
        ///
        /// Parameters:
        /// - `modulus`: specifies the modulus of the new [`Zq`] element
        /// - `center`: specifies the position of the center with peak probability
        /// - `s`: specifies the Gaussian parameter, which is proportional
        ///   to the standard deviation `sigma * sqrt(2 * pi) = s`
        #[seeded]
        /// - `seed`: specifies the 256-bit seed of the PRNG used for sampling
        #[optionally_seeded]
        /// - `seed`: specifies an optional 256-bit seed of the PRNG used for sampling.
        #[optionally_seeded]
        ///   If `None` is provided, a fresh [`ThreadRng`](rand::rngs::ThreadRng) is used instead.
        ///
        /// Returns new [`Zq`] sample chosen according to the specified discrete Gaussian
        /// distribution or a [`MathError`] if the specified parameters were not chosen
        /// appropriately, i.e. `s < 0`.
        ///
        /// # Examples
        /// ```
        /// use qfall_math::integer_mod_q::Zq;
        ///
        #[unseeded]
        /// let sample = Zq::sample_discrete_gauss(17, 0, 1).unwrap();
        #[seeded]
        /// let sample = Zq::sample_discrete_gauss_seeded(17, 0, 1, [42; 32]).unwrap();
        /// ```
        ///
        /// # Errors and Failures
        /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
        ///   if `s < 0`.
        ///
        /// # Panics ...
        /// - if `modulus` is smaller than `2`.
        ///
        /// This function implements SampleZ according to:
        /// - \[1\] Gentry, Craig and Peikert, Chris and Vaikuntanathan, Vinod (2008).
        ///   Trapdoors for hard lattices and new cryptographic constructions.
        ///   In: Proceedings of the fortieth annual ACM symposium on Theory of computing.
        ///   <https://dl.acm.org/doi/pdf/10.1145/1374376.1374407>
        pub(crate) fn sample_discrete_gauss(
            modulus: impl Into<Modulus>,
            center: impl Into<Q>,
            s: impl Into<Q>,
            seed: Option<[u8; 32]>,
        ) -> Result<Self, MathError> {
            let modulus: Modulus = modulus.into();
            let center: Q = center.into();
            let s: Q = s.into();

            let mut dgis = DiscreteGaussianIntegerSampler::init(
                &center,
                &s,
                unsafe { TAILCUT },
                LookupTableSetting::NoLookup,
                seed,
            )?;

            let sample = dgis.sample_z();
            Ok(Zq::from((&sample, &modulus)))
        }
    );
}

#[cfg(test)]
mod test_sample_discrete_gauss {
    use crate::utils::sample::test_seed;
    use crate::{integer::Z, integer_mod_q::Zq, rational::Q};

    // Appropriate interval and invalid inputs were tested in
    // utils::sample::discrete_gauss::test_sample_z and are thus omitted here.

    /// Checks whether `sample_discrete_gauss` is available for all types
    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
    /// or [`Into<Q>`], i.e. u8, i16, f32, Z, Q, ...
    #[test]
    fn availability() {
        for seeded in [false, true] {
            let z = Z::from(2);
            let q = Q::from(2);

            let _ = Zq::sample_discrete_gauss_optionally_seeded(
                17u64,
                7u8,
                1u16,
                seeded.then(test_seed),
            );
            let _ = Zq::sample_discrete_gauss_optionally_seeded(
                17u16,
                7u16,
                1u8,
                seeded.then(test_seed),
            );
            let _ = Zq::sample_discrete_gauss_optionally_seeded(
                17u8,
                7u32,
                1u32,
                seeded.then(test_seed),
            );
            let _ = Zq::sample_discrete_gauss_optionally_seeded(
                17u32,
                7u64,
                1u64,
                seeded.then(test_seed),
            );
            let _ = Zq::sample_discrete_gauss_optionally_seeded(
                17i16,
                7i8,
                1i64,
                seeded.then(test_seed),
            );
            let _ = Zq::sample_discrete_gauss_optionally_seeded(
                17i8,
                7i16,
                1i32,
                seeded.then(test_seed),
            );
            let _ = Zq::sample_discrete_gauss_optionally_seeded(
                17i64,
                7i32,
                1i16,
                seeded.then(test_seed),
            );
            let _ = Zq::sample_discrete_gauss_optionally_seeded(
                17i32,
                7i64,
                1i8,
                seeded.then(test_seed),
            );
            let _ = Zq::sample_discrete_gauss_optionally_seeded(
                17,
                q.clone(),
                1i64,
                seeded.then(test_seed),
            );
            let _ = Zq::sample_discrete_gauss_optionally_seeded(
                z.clone(),
                0i8,
                z.clone(),
                seeded.then(test_seed),
            );
            let _ = Zq::sample_discrete_gauss_optionally_seeded(
                17,
                z.clone(),
                q.clone(),
                seeded.then(test_seed),
            );
            let _ =
                Zq::sample_discrete_gauss_optionally_seeded(17, 1f32, 1f64, seeded.then(test_seed));
            let _ =
                Zq::sample_discrete_gauss_optionally_seeded(17, 1f64, 1f32, seeded.then(test_seed));

            // With references
            let _ = Zq::sample_discrete_gauss_optionally_seeded(
                17i64,
                7i32,
                1i16,
                seeded.then(test_seed),
            );
            let _ = Zq::sample_discrete_gauss_optionally_seeded(
                17i32,
                7i64,
                1i8,
                seeded.then(test_seed),
            );
            let _ =
                Zq::sample_discrete_gauss_optionally_seeded(17, &q, 1i64, seeded.then(test_seed));
            let _ =
                Zq::sample_discrete_gauss_optionally_seeded(&z, 0i8, &z, seeded.then(test_seed));
            let _ = Zq::sample_discrete_gauss_optionally_seeded(17, &z, &q, seeded.then(test_seed));

            // explicitly checks the existence of the unseeded and the seeded function
            if seeded {
                let _ = Zq::sample_discrete_gauss_seeded(17u64, 7u8, 1u16, test_seed());
            } else {
                let _ = Zq::sample_discrete_gauss(17u64, 7u8, 1u16);
            }
        }
    }

    /// Roughly checks the collected samples are distributed
    /// according to the discrete Gaussian distribution.
    ///
    /// This test could possibly fail for a truly uniform distribution
    /// with probability smaller than 1/1000.
    #[test]
    fn distribution() {
        for seeded in [false, true] {
            let mut counts = [0; 20];
            // count sampled instances
            for _ in 0..200 {
                let sample =
                    Zq::sample_discrete_gauss_optionally_seeded(20, 0, 2, seeded.then(test_seed))
                        .unwrap();
                let sample_int =
                    i64::try_from(&sample.get_representative_least_nonnegative_residue()).unwrap()
                        as usize;
                counts[sample_int] += 1;
            }

            let expl_text = String::from("This test can fail with probability close to 0. 
        It fails if the sampled occurrences do not look like a typical discrete Gaussian random distribution. 
        If this happens, rerun the tests several times and check whether this issue comes up again.");

            // Check that the sampled occurrences roughly look
            // like a discrete Gaussian distribution
            assert!(counts[0] > 70, "{expl_text}");
            assert!(counts[0] < 130, "{expl_text}");
            assert!(counts[19] > 20, "{expl_text}");
            assert!(counts[19] < 70, "{expl_text}");
            assert!(counts[1] > 20, "{expl_text}");
            assert!(counts[1] < 70, "{expl_text}");
            assert!(counts[18] < 20, "{expl_text}");
            assert!(counts[2] < 20, "{expl_text}");
            for count in counts.iter().take(18).skip(3) {
                assert!(count < &10, "{expl_text}");
            }
        }
    }

    /// Checks whether the same seed results in the same sample.
    #[test]
    fn same_seed_same_sample() {
        use crate::integer_mod_q::Zq;
        let sample_0 = Zq::sample_discrete_gauss_seeded(17, 0, 1, [42; 32]).unwrap();
        let sample_1 = Zq::sample_discrete_gauss_seeded(17, 0, 1, [42; 32]).unwrap();

        assert_eq!(sample_0, sample_1);
    }

    /// Checks whether the seeded variant outputs the known sample for a fixed seed.
    #[test]
    fn known_answer() {
        use crate::integer_mod_q::Zq;
        let sample = Zq::sample_discrete_gauss_seeded(17, 0, 1, [42; 32]).unwrap();

        assert_eq!("1 mod 17", sample.to_string());
    }
}