qfall_math/integer_mod_q/z_q/sample/
uniform.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 sampling algorithms for uniform random sampling.
10
11use crate::{integer::Z, integer_mod_q::Zq, utils::sample::uniform::UniformIntegerSampler};
12
13impl Zq {
14    /// Chooses a [`Zq`] instance uniformly at random in `[0, modulus)`.
15    ///
16    /// The internally used uniform at random chosen bytes are generated
17    /// by [`ThreadRng`](rand::rngs::ThreadRng), which uses ChaCha12 and
18    /// is considered cryptographically secure.
19    ///
20    /// Parameters:
21    /// - `modulus`: specifies the [`Modulus`](crate::integer_mod_q::Modulus)
22    ///   of the new [`Zq`] instance and thus the size of the interval over which is sampled
23    ///
24    /// Returns a new [`Zq`] instance with a value chosen
25    /// uniformly at random in `[0, modulus)`.
26    ///
27    /// # Examples
28    /// ```
29    /// use qfall_math::integer_mod_q::Zq;
30    ///
31    /// let sample = Zq::sample_uniform(17);
32    /// ```
33    ///
34    /// # Panics
35    /// - if the given modulus is smaller than or equal to `1`.
36    pub fn sample_uniform(modulus: impl Into<Z>) -> Self {
37        let modulus: Z = modulus.into();
38        let mut uis = UniformIntegerSampler::init(&modulus).unwrap();
39
40        let random = uis.sample();
41        Zq::from((random, modulus))
42    }
43}
44
45#[cfg(test)]
46mod test_sample_uniform {
47    use crate::{
48        integer::Z,
49        integer_mod_q::{Modulus, Zq},
50    };
51
52    /// Checks whether the boundaries of the interval are kept for small moduli.
53    /// These should be protected by the sampling algorithm and [`Zq`]s instantiation.
54    #[test]
55    fn boundaries_kept_small() {
56        let modulus = Z::from(17);
57        for _ in 0..32 {
58            let sample = Zq::sample_uniform(&modulus);
59            assert!(Z::ZERO <= sample.value);
60            assert!(sample.value < modulus);
61        }
62    }
63
64    /// Checks whether the boundaries of the interval are kept for large moduli.
65    /// These should be protected by the sampling algorithm and [`Zq`]s instantiation.
66    #[test]
67    fn boundaries_kept_large() {
68        let modulus = Z::from(u64::MAX);
69        for _ in 0..256 {
70            let sample = Zq::sample_uniform(&modulus);
71            assert!(Z::ZERO <= sample.value);
72            assert!(sample.value < modulus);
73        }
74    }
75
76    /// Checks whether providing an invalid interval results in an error.
77    #[test]
78    #[should_panic]
79    fn invalid_interval() {
80        let modulus = Z::ZERO;
81
82        let _ = Zq::sample_uniform(&modulus);
83    }
84
85    /// Checks whether `sample_uniform` is available for all types
86    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
87    #[test]
88    fn availability() {
89        let modulus = Modulus::from(7);
90        let z = Z::from(7);
91
92        let _ = Zq::sample_uniform(7u8);
93        let _ = Zq::sample_uniform(7u16);
94        let _ = Zq::sample_uniform(7u32);
95        let _ = Zq::sample_uniform(7u64);
96        let _ = Zq::sample_uniform(7i8);
97        let _ = Zq::sample_uniform(7i16);
98        let _ = Zq::sample_uniform(7i32);
99        let _ = Zq::sample_uniform(7i64);
100        let _ = Zq::sample_uniform(&modulus);
101        let _ = Zq::sample_uniform(&z);
102    }
103
104    /// Roughly checks the uniformity of the distribution.
105    /// This test could possibly fail for a truly uniform distribution
106    /// with probability smaller than 1/1000.
107    #[test]
108    fn uniformity() {
109        let modulus = Z::from(5);
110        let mut counts = [0; 5];
111        // count sampled instances
112        for _ in 0..1000 {
113            let sample_z = Zq::sample_uniform(&modulus);
114            let sample_int = i64::try_from(&sample_z.value).unwrap() as usize;
115            counts[sample_int] += 1;
116        }
117
118        // Check that every sampled integer was sampled roughly the same time
119        // this could possibly fail for true uniform randomness with probability
120        for count in counts {
121            assert!(count > 150, "This test can fail with probability close to 0. 
122            It fails if the sampled occurrences do not look like a typical uniform random distribution. 
123            If this happens, rerun the tests several times and check whether this issue comes up again.");
124        }
125    }
126}
qfall_math/integer_mod_q/z_q/sample/uniform.rs

qfall_math/integer_mod_q/z_q/sample/
uniform.rs
