qfall_math/integer_mod_q/z_q/sample/uniform.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 sampling algorithms for uniform random sampling.
10
11use crate::{
12 integer::Z, integer_mod_q::Zq, macros::seeded::seedable_function,
13 utils::sample::uniform::UniformIntegerSampler,
14};
15
16impl Zq {
17 seedable_function!(
18 /// Chooses a [`Zq`] instance uniformly at random in `[0, modulus)`.
19 ///
20 /// The internally used uniform at random chosen bytes are generated
21 #[unseeded]
22 /// by [`ThreadRng`](rand::rngs::ThreadRng), which uses ChaCha12 and is
23 #[seeded]
24 /// by a [`StdRng`](rand::rngs::StdRng) seeded with `seed`, which uses ChaCha12 and is
25 #[optionally_seeded]
26 /// by a [`StdRng`](rand::rngs::StdRng) seeded with `seed` or by [`ThreadRng`](rand::rngs::ThreadRng)
27 #[optionally_seeded]
28 /// if `seed` is `None`. Both use ChaCha12 and are
29 /// considered cryptographically secure.
30 ///
31 /// Parameters:
32 /// - `modulus`: specifies the [`Modulus`](crate::integer_mod_q::Modulus)
33 /// of the new [`Zq`] instance and thus the size of the interval over which is sampled
34 #[seeded]
35 /// - `seed`: specifies the 256-bit seed of the PRNG used for sampling
36 #[optionally_seeded]
37 /// - `seed`: specifies an optional 256-bit seed of the PRNG used for sampling.
38 #[optionally_seeded]
39 /// If `None` is provided, a fresh [`ThreadRng`](rand::rngs::ThreadRng) is used instead.
40 ///
41 /// Returns a new [`Zq`] instance with a value chosen
42 /// uniformly at random in `[0, modulus)`.
43 ///
44 /// # Examples
45 /// ```
46 /// use qfall_math::integer_mod_q::Zq;
47 ///
48 #[unseeded]
49 /// let sample = Zq::sample_uniform(17);
50 #[seeded]
51 /// let sample = Zq::sample_uniform_seeded(17, [42; 32]);
52 /// ```
53 ///
54 /// # Panics
55 /// - if the given modulus is smaller than or equal to `1`.
56 pub(crate) fn sample_uniform(modulus: impl Into<Z>, seed: Option<[u8; 32]>) -> Self {
57 let modulus: Z = modulus.into();
58 let mut uis = UniformIntegerSampler::init(&modulus, seed).unwrap();
59
60 let random = uis.sample();
61 Zq::from((random, modulus))
62 }
63 );
64}
65
66#[cfg(test)]
67mod test_sample_uniform {
68 use crate::utils::sample::test_seed;
69 use crate::{
70 integer::Z,
71 integer_mod_q::{Modulus, Zq},
72 };
73
74 /// Checks whether the boundaries of the interval are kept for small moduli.
75 /// These should be protected by the sampling algorithm and [`Zq`]s instantiation.
76 #[test]
77 fn boundaries_kept_small() {
78 for seeded in [false, true] {
79 let modulus = Z::from(17);
80 for _ in 0..32 {
81 let sample = Zq::sample_uniform_optionally_seeded(&modulus, seeded.then(test_seed));
82 assert!(Z::ZERO <= sample.value);
83 assert!(sample.value < modulus);
84 }
85 }
86 }
87
88 /// Checks whether the boundaries of the interval are kept for large moduli.
89 /// These should be protected by the sampling algorithm and [`Zq`]s instantiation.
90 #[test]
91 fn boundaries_kept_large() {
92 for seeded in [false, true] {
93 let modulus = Z::from(u64::MAX);
94 for _ in 0..256 {
95 let sample = Zq::sample_uniform_optionally_seeded(&modulus, seeded.then(test_seed));
96 assert!(Z::ZERO <= sample.value);
97 assert!(sample.value < modulus);
98 }
99 }
100 }
101
102 /// Checks whether providing an invalid interval results in an error.
103 #[test]
104 fn invalid_interval() {
105 for seeded in [false, true] {
106 let result = std::panic::catch_unwind(|| {
107 let modulus = Z::ZERO;
108
109 let _ = Zq::sample_uniform_optionally_seeded(&modulus, seeded.then(test_seed));
110 });
111 assert!(result.is_err());
112 }
113 }
114
115 /// Checks whether `sample_uniform` is available for all types
116 /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
117 #[test]
118 fn availability() {
119 for seeded in [false, true] {
120 let modulus = Modulus::from(7);
121 let z = Z::from(7);
122
123 let _ = Zq::sample_uniform_optionally_seeded(7u8, seeded.then(test_seed));
124 let _ = Zq::sample_uniform_optionally_seeded(7u16, seeded.then(test_seed));
125 let _ = Zq::sample_uniform_optionally_seeded(7u32, seeded.then(test_seed));
126 let _ = Zq::sample_uniform_optionally_seeded(7u64, seeded.then(test_seed));
127 let _ = Zq::sample_uniform_optionally_seeded(7i8, seeded.then(test_seed));
128 let _ = Zq::sample_uniform_optionally_seeded(7i16, seeded.then(test_seed));
129 let _ = Zq::sample_uniform_optionally_seeded(7i32, seeded.then(test_seed));
130 let _ = Zq::sample_uniform_optionally_seeded(7i64, seeded.then(test_seed));
131 let _ = Zq::sample_uniform_optionally_seeded(&modulus, seeded.then(test_seed));
132 let _ = Zq::sample_uniform_optionally_seeded(&z, seeded.then(test_seed));
133
134 // explicitly checks the existence of the unseeded and the seeded function
135 if seeded {
136 let _ = Zq::sample_uniform_seeded(7u8, test_seed());
137 } else {
138 let _ = Zq::sample_uniform(7u8);
139 }
140 }
141 }
142
143 /// Roughly checks the uniformity of the distribution.
144 /// This test could possibly fail for a truly uniform distribution
145 /// with probability smaller than 1/1000.
146 #[test]
147 fn uniformity() {
148 for seeded in [false, true] {
149 let modulus = Z::from(5);
150 let mut counts = [0; 5];
151 // count sampled instances
152 for _ in 0..1000 {
153 let sample_z =
154 Zq::sample_uniform_optionally_seeded(&modulus, seeded.then(test_seed));
155 let sample_int = i64::try_from(&sample_z.value).unwrap() as usize;
156 counts[sample_int] += 1;
157 }
158
159 // Check that every sampled integer was sampled roughly the same time
160 // this could possibly fail for true uniform randomness with probability
161 for count in counts {
162 assert!(count > 150, "This test can fail with probability close to 0.
163 It fails if the sampled occurrences do not look like a typical uniform random distribution.
164 If this happens, rerun the tests several times and check whether this issue comes up again.");
165 }
166 }
167 }
168
169 /// Checks whether the same seed results in the same sample.
170 #[test]
171 fn same_seed_same_sample() {
172 use crate::integer_mod_q::Zq;
173 let sample_0 = Zq::sample_uniform_seeded(17, [42; 32]);
174 let sample_1 = Zq::sample_uniform_seeded(17, [42; 32]);
175
176 assert_eq!(sample_0, sample_1);
177 }
178
179 /// Checks whether the seeded variant outputs the known sample for a fixed seed.
180 #[test]
181 fn known_answer() {
182 use crate::integer_mod_q::Zq;
183 let sample = Zq::sample_uniform_seeded(17, [42; 32]);
184
185 assert_eq!("2 mod 17", sample.to_string());
186 }
187}