qfall_math/integer_mod_q/poly_over_zq/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 algorithms for sampling according to the uniform distribution.
10
11use crate::{
12    error::MathError,
13    integer::Z,
14    integer_mod_q::{Modulus, PolyOverZq},
15    macros::seeded::seedable_function,
16    traits::SetCoefficient,
17    utils::{index::evaluate_index, sample::uniform::UniformIntegerSampler},
18};
19use std::fmt::Display;
20
21impl PolyOverZq {
22    seedable_function!(
23        /// Generates a [`PolyOverZq`] instance with maximum degree `max_degree`
24        /// and coefficients chosen uniform at random in `[0, modulus)`.
25        ///
26        /// The internally used uniform at random chosen bytes are generated
27        #[unseeded]
28        /// by [`ThreadRng`](rand::rngs::ThreadRng), which uses ChaCha12 and is
29        #[seeded]
30        /// by a [`StdRng`](rand::rngs::StdRng) seeded with `seed`, which uses ChaCha12 and is
31        #[optionally_seeded]
32        /// by a [`StdRng`](rand::rngs::StdRng) seeded with `seed` or by [`ThreadRng`](rand::rngs::ThreadRng)
33        #[optionally_seeded]
34        /// if `seed` is `None`. Both use ChaCha12 and are
35        /// considered cryptographically secure.
36        ///
37        /// Parameters:
38        /// - `max_degree`: specifies the length of the polynomial,
39        ///   i.e. the number of coefficients
40        /// - `modulus`: specifies the modulus of the coefficients and thus,
41        ///   the interval size over which is sampled
42        #[seeded]
43        /// - `seed`: specifies the 256-bit seed of the PRNG used for sampling
44        #[optionally_seeded]
45        /// - `seed`: specifies an optional 256-bit seed of the PRNG used for sampling.
46        #[optionally_seeded]
47        ///   If `None` is provided, a fresh [`ThreadRng`](rand::rngs::ThreadRng) is used instead.
48        ///
49        /// Returns a fresh [`PolyOverZq`] instance of length `max_degree` with coefficients
50        /// chosen uniform at random in `[0, modulus)` or a [`MathError`]
51        /// if the `max_degree` was smaller than `0` or the provided `modulus` was chosen too small.
52        ///
53        /// # Examples
54        /// ```
55        /// use qfall_math::integer_mod_q::PolyOverZq;
56        ///
57        #[unseeded]
58        /// let sample = PolyOverZq::sample_uniform(3, 17).unwrap();
59        #[seeded]
60        /// let sample = PolyOverZq::sample_uniform_seeded(3, 17, [42; 32]).unwrap();
61        /// ```
62        ///
63        /// # Errors and Failures
64        /// - Returns a [`MathError`] of type [`InvalidInterval`](MathError::InvalidInterval)
65        ///   if the given `modulus` isn't larger than `1`, i.e. the interval size is at most `1`.
66        /// - Returns a [`MathError`] of type [`OutOfBounds`](MathError::OutOfBounds) if
67        ///   the `max_degree` is negative or it does not fit into an [`i64`].
68        ///
69        /// # Panics ...
70        /// - if `modulus` is smaller than `2`.
71        pub(crate) fn sample_uniform(
72            max_degree: impl TryInto<i64> + Display + Copy,
73            modulus: impl Into<Z>,
74            seed: Option<[u8; 32]>,
75        ) -> Result<Self, MathError> {
76            let max_degree = evaluate_index(max_degree)?;
77            let interval_size = modulus.into();
78            let modulus = Modulus::from(&interval_size);
79            let mut poly_zq = PolyOverZq::from(&modulus);
80
81            let mut uis = UniformIntegerSampler::init(&interval_size, seed)?;
82
83            for index in 0..=max_degree {
84                let sample = uis.sample();
85                unsafe { poly_zq.set_coeff_unchecked(index, sample) };
86            }
87            Ok(poly_zq)
88        }
89    );
90}
91
92#[cfg(test)]
93mod test_sample_uniform {
94    use crate::utils::sample::test_seed;
95    use crate::{
96        integer::Z,
97        integer_mod_q::{Modulus, PolyOverZq},
98        traits::GetCoefficient,
99    };
100
101    /// Checks whether the boundaries of the interval are kept for small moduli.
102    #[test]
103    fn boundaries_kept_small() {
104        for seeded in [false, true] {
105            let modulus = Z::from(17);
106
107            let poly_zq =
108                PolyOverZq::sample_uniform_optionally_seeded(32, &modulus, seeded.then(test_seed))
109                    .unwrap();
110
111            for i in 0..32 {
112                let sample: Z = poly_zq.get_coeff(i).unwrap();
113                assert!(Z::ZERO <= sample);
114                assert!(sample < modulus);
115            }
116        }
117    }
118
119    /// Checks whether the boundaries of the interval are kept for large moduli.
120    #[test]
121    fn boundaries_kept_large() {
122        for seeded in [false, true] {
123            let modulus = Z::from(i64::MAX);
124
125            let poly_zq =
126                PolyOverZq::sample_uniform_optionally_seeded(256, &modulus, seeded.then(test_seed))
127                    .unwrap();
128
129            for i in 0..256 {
130                let sample: Z = poly_zq.get_coeff(i).unwrap();
131                assert!(Z::ZERO <= sample);
132                assert!(sample < modulus);
133            }
134        }
135    }
136
137    /// Checks whether the number of coefficients is correct.
138    #[test]
139    fn nr_coeffs() {
140        for seeded in [false, true] {
141            let degrees = [1, 3, 7, 15, 32, 120];
142            for degree in degrees {
143                let res = PolyOverZq::sample_uniform_optionally_seeded(
144                    degree,
145                    u64::MAX,
146                    seeded.then(test_seed),
147                )
148                .unwrap();
149
150                assert_eq!(
151                    degree,
152                    res.get_degree(),
153                    "Could fail with probability 1/{}.",
154                    u64::MAX
155                );
156            }
157        }
158    }
159
160    /// Checks whether providing an invalid interval/ modulus results in an error.
161    #[test]
162    fn invalid_modulus_negative() {
163        for seeded in [false, true] {
164            let result = std::panic::catch_unwind(|| {
165                let _ = PolyOverZq::sample_uniform_optionally_seeded(
166                    1,
167                    i64::MIN,
168                    seeded.then(test_seed),
169                );
170            });
171            assert!(result.is_err());
172        }
173    }
174
175    /// Checks whether providing an invalid interval/ modulus results in an error.
176    #[test]
177    fn invalid_modulus_one() {
178        for seeded in [false, true] {
179            let result = std::panic::catch_unwind(|| {
180                let _ = PolyOverZq::sample_uniform_optionally_seeded(1, 1, seeded.then(test_seed));
181            });
182            assert!(result.is_err());
183        }
184    }
185
186    /// Checks whether providing a length smaller than `1` results in an error.
187    #[test]
188    fn invalid_max_degree() {
189        for seeded in [false, true] {
190            let modulus = Z::from(15);
191
192            let res_0 =
193                PolyOverZq::sample_uniform_optionally_seeded(-1, &modulus, seeded.then(test_seed));
194            let res_1 = PolyOverZq::sample_uniform_optionally_seeded(
195                i64::MIN,
196                &modulus,
197                seeded.then(test_seed),
198            );
199
200            assert!(res_0.is_err());
201            assert!(res_1.is_err());
202        }
203    }
204
205    /// Checks whether `sample_uniform` is available for all types
206    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
207    #[test]
208    fn availability() {
209        for seeded in [false, true] {
210            let modulus = Modulus::from(10);
211            let z = Z::from(10);
212
213            let _ =
214                PolyOverZq::sample_uniform_optionally_seeded(1u64, 10u16, seeded.then(test_seed))
215                    .unwrap();
216            let _ =
217                PolyOverZq::sample_uniform_optionally_seeded(1i64, 10u32, seeded.then(test_seed))
218                    .unwrap();
219            let _ =
220                PolyOverZq::sample_uniform_optionally_seeded(1u8, 10u64, seeded.then(test_seed))
221                    .unwrap();
222            let _ =
223                PolyOverZq::sample_uniform_optionally_seeded(1u16, 10i8, seeded.then(test_seed))
224                    .unwrap();
225            let _ =
226                PolyOverZq::sample_uniform_optionally_seeded(1u32, 10i16, seeded.then(test_seed))
227                    .unwrap();
228            let _ =
229                PolyOverZq::sample_uniform_optionally_seeded(1i32, 10i32, seeded.then(test_seed))
230                    .unwrap();
231            let _ =
232                PolyOverZq::sample_uniform_optionally_seeded(1i16, 10i64, seeded.then(test_seed))
233                    .unwrap();
234            let _ = PolyOverZq::sample_uniform_optionally_seeded(1i8, &z, seeded.then(test_seed))
235                .unwrap();
236            let _ =
237                PolyOverZq::sample_uniform_optionally_seeded(1, z, seeded.then(test_seed)).unwrap();
238            let _ =
239                PolyOverZq::sample_uniform_optionally_seeded(1, &modulus, seeded.then(test_seed))
240                    .unwrap();
241            let _ =
242                PolyOverZq::sample_uniform_optionally_seeded(1, modulus, seeded.then(test_seed))
243                    .unwrap();
244
245            // explicitly checks the existence of the unseeded and the seeded function
246            if seeded {
247                let _ = PolyOverZq::sample_uniform_seeded(1u64, 10u16, test_seed());
248            } else {
249                let _ = PolyOverZq::sample_uniform(1u64, 10u16);
250            }
251        }
252    }
253
254    /// Checks whether the same seed results in the same sample.
255    #[test]
256    fn same_seed_same_sample() {
257        use crate::integer_mod_q::PolyOverZq;
258        let sample_0 = PolyOverZq::sample_uniform_seeded(3, 17, [42; 32]).unwrap();
259        let sample_1 = PolyOverZq::sample_uniform_seeded(3, 17, [42; 32]).unwrap();
260
261        assert_eq!(sample_0, sample_1);
262    }
263
264    /// Checks whether the seeded variant outputs the known sample for a fixed seed.
265    #[test]
266    fn known_answer() {
267        use crate::integer_mod_q::PolyOverZq;
268        let sample = PolyOverZq::sample_uniform_seeded(3, 17, [42; 32]).unwrap();
269
270        assert_eq!("4  2 16 3 7 mod 17", sample.to_string());
271    }
272}
qfall_math/integer_mod_q/poly_over_zq/sample/uniform.rs

qfall_math/integer_mod_q/poly_over_zq/sample/
uniform.rs
