qfall_math/integer_mod_q/polynomial_ring_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 integer::PolyOverZ,
13 integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq},
14 macros::seeded::seedable_function,
15};
16
17impl PolynomialRingZq {
18 seedable_function!(
19 /// Generates a [`PolynomialRingZq`] instance with maximum degree `modulus.get_degree() - 1`
20 /// and coefficients chosen uniform at random in `[0, modulus.get_q())`.
21 ///
22 /// The internally used uniform at random chosen bytes are generated
23 #[unseeded]
24 /// by [`ThreadRng`](rand::rngs::ThreadRng), which uses ChaCha12 and is
25 #[seeded]
26 /// by a [`StdRng`](rand::rngs::StdRng) seeded with `seed`, which uses ChaCha12 and is
27 #[optionally_seeded]
28 /// by a [`StdRng`](rand::rngs::StdRng) seeded with `seed` or by [`ThreadRng`](rand::rngs::ThreadRng)
29 #[optionally_seeded]
30 /// if `seed` is `None`. Both use ChaCha12 and are
31 /// considered cryptographically secure.
32 ///
33 /// Parameters:
34 /// - `modulus`: specifies the [`ModulusPolynomialRingZq`] over which the
35 /// ring of polynomials modulo `modulus.get_q()` is defined
36 #[seeded]
37 /// - `seed`: specifies the 256-bit seed of the PRNG used for sampling
38 #[optionally_seeded]
39 /// - `seed`: specifies an optional 256-bit seed of the PRNG used for sampling.
40 #[optionally_seeded]
41 /// If `None` is provided, a fresh [`ThreadRng`](rand::rngs::ThreadRng) is used instead.
42 ///
43 /// Returns a fresh [`PolynomialRingZq`] instance of length `modulus.get_degree() - 1`
44 /// with coefficients chosen uniform at random in `[0, modulus.get_q())`.
45 ///
46 /// # Examples
47 /// ```
48 /// use qfall_math::integer_mod_q::{PolynomialRingZq, ModulusPolynomialRingZq};
49 /// use std::str::FromStr;
50 /// let modulus = ModulusPolynomialRingZq::from_str("3 1 2 1 mod 17").unwrap();
51 ///
52 #[unseeded]
53 /// let sample = PolynomialRingZq::sample_uniform(&modulus);
54 #[seeded]
55 /// let sample = PolynomialRingZq::sample_uniform_seeded(&modulus, [42; 32]);
56 /// ```
57 ///
58 /// # Panics ...
59 /// - if the provided [`ModulusPolynomialRingZq`] has degree `0` or smaller.
60 pub(crate) fn sample_uniform(
61 modulus: impl Into<ModulusPolynomialRingZq>,
62 seed: Option<[u8; 32]>,
63 ) -> Self {
64 let modulus = modulus.into();
65 assert!(
66 modulus.get_degree() > 0,
67 "ModulusPolynomial of degree 0 is insufficient to sample over."
68 );
69
70 let poly_z = PolyOverZ::sample_uniform_optionally_seeded(
71 modulus.get_degree() - 1,
72 0,
73 modulus.get_q(),
74 seed,
75 )
76 .unwrap();
77
78 // we do not have to reduce here, as all entries are already in the correct range
79 // hence directly setting is more efficient
80 PolynomialRingZq {
81 poly: poly_z,
82 modulus,
83 }
84 }
85 );
86}
87
88#[cfg(test)]
89mod test_sample_uniform {
90 use crate::utils::sample::test_seed;
91 use crate::{
92 integer::Z,
93 integer_mod_q::{ModulusPolynomialRingZq, PolyOverZq, PolynomialRingZq},
94 traits::{GetCoefficient, SetCoefficient},
95 };
96 use std::str::FromStr;
97
98 /// Checks whether the boundaries of the interval are kept for small moduli.
99 #[test]
100 fn boundaries_kept_small() {
101 for seeded in [false, true] {
102 let modulus = ModulusPolynomialRingZq::from_str("4 1 0 0 1 mod 17").unwrap();
103
104 for _ in 0..32 {
105 let poly = PolynomialRingZq::sample_uniform_optionally_seeded(
106 &modulus,
107 seeded.then(test_seed),
108 );
109
110 for i in 0..3 {
111 let sample: Z = poly.get_coeff(i).unwrap();
112 assert!(Z::ZERO <= sample);
113 assert!(sample < modulus.get_q());
114 }
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 =
124 ModulusPolynomialRingZq::from_str(&format!("4 1 0 0 1 mod {}", u64::MAX)).unwrap();
125
126 for _ in 0..256 {
127 let poly = PolynomialRingZq::sample_uniform_optionally_seeded(
128 &modulus,
129 seeded.then(test_seed),
130 );
131
132 for i in 0..3 {
133 let sample: Z = poly.get_coeff(i).unwrap();
134 assert!(Z::ZERO <= sample);
135 assert!(sample < modulus.get_q());
136 }
137 }
138 }
139 }
140
141 /// Checks whether the number of coefficients is correct.
142 #[test]
143 fn nr_coeffs() {
144 for seeded in [false, true] {
145 let degrees = [1, 3, 7, 15, 32, 120];
146 for degree in degrees {
147 let mut modulus = PolyOverZq::from((1, u64::MAX));
148 modulus.set_coeff(degree, 1).unwrap();
149 let modulus = ModulusPolynomialRingZq::from(&modulus);
150
151 let res = PolynomialRingZq::sample_uniform_optionally_seeded(
152 &modulus,
153 seeded.then(test_seed),
154 );
155
156 assert_eq!(
157 res.get_degree() + 1,
158 modulus.get_degree(),
159 "Could fail with probability 1/{}.",
160 u64::MAX
161 );
162 }
163 }
164 }
165
166 /// Checks whether 0 modulus polynomial is insufficient.
167 #[test]
168 fn invalid_modulus() {
169 for seeded in [false, true] {
170 let result = std::panic::catch_unwind(|| {
171 let modulus = ModulusPolynomialRingZq::from_str("1 1 mod 17").unwrap();
172
173 let _ = PolynomialRingZq::sample_uniform_optionally_seeded(
174 &modulus,
175 seeded.then(test_seed),
176 );
177 });
178 assert!(result.is_err());
179 }
180 }
181
182 /// Checks whether the same seed results in the same sample.
183 #[test]
184 fn same_seed_same_sample() {
185 use crate::integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq};
186 use std::str::FromStr;
187 let modulus = ModulusPolynomialRingZq::from_str("3 1 2 1 mod 17").unwrap();
188 let sample_0 = PolynomialRingZq::sample_uniform_seeded(&modulus, [42; 32]);
189 let sample_1 = PolynomialRingZq::sample_uniform_seeded(&modulus, [42; 32]);
190
191 assert_eq!(sample_0, sample_1);
192 }
193
194 /// Checks whether the seeded variant outputs the known sample for a fixed seed.
195 #[test]
196 fn known_answer() {
197 use crate::integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq};
198 use std::str::FromStr;
199 let modulus = ModulusPolynomialRingZq::from_str("3 1 2 1 mod 17").unwrap();
200 let sample = PolynomialRingZq::sample_uniform_seeded(&modulus, [42; 32]);
201
202 assert_eq!("2 2 16 / 3 1 2 1 mod 17", sample.to_string());
203 }
204
205 /// Checks whether the unseeded and the seeded function are available.
206 #[test]
207 fn availability() {
208 use crate::integer_mod_q::{ModulusPolynomialRingZq, PolynomialRingZq};
209 use std::str::FromStr;
210 let modulus = ModulusPolynomialRingZq::from_str("3 1 2 1 mod 17").unwrap();
211
212 // explicitly checks the existence of the unseeded and the seeded function
213 let _ = PolynomialRingZq::sample_uniform(&modulus);
214 let _ = PolynomialRingZq::sample_uniform_seeded(&modulus, test_seed());
215 }
216}