qfall_math/integer_mod_q/mat_zq/sample/
discrete_gauss.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 algorithms for sampling according to the discrete Gaussian distribution.
10
11use crate::{
12    error::MathError,
13    integer_mod_q::{MatZq, Modulus},
14    rational::{MatQ, Q},
15    traits::{MatrixDimensions, MatrixSetEntry},
16    utils::sample::discrete_gauss::{
17        DiscreteGaussianIntegerSampler, LookupTableSetting, TAILCUT, sample_d,
18        sample_d_precomputed_gso,
19    },
20};
21use std::fmt::Display;
22
23impl MatZq {
24    /// Initializes a new matrix with dimensions `num_rows` x `num_columns` and with each entry
25    /// sampled independently according to the discrete Gaussian distribution,
26    /// using [`Z::sample_discrete_gauss`](crate::integer::Z::sample_discrete_gauss).
27    ///
28    /// Parameters:
29    /// - `num_rows`: specifies the number of rows the new matrix should have
30    /// - `num_cols`: specifies the number of columns the new matrix should have
31    /// - `center`: specifies the positions of the center with peak probability
32    /// - `s`: specifies the Gaussian parameter, which is proportional
33    ///   to the standard deviation `sigma * sqrt(2 * pi) = s`
34    ///
35    /// Returns a matrix with each entry sampled independently from the
36    /// specified discrete Gaussian distribution or an error if `s < 0`.
37    ///
38    /// # Examples
39    /// ```
40    /// use qfall_math::integer_mod_q::MatZq;
41    ///
42    /// let sample = MatZq::sample_discrete_gauss(3, 1, 83, 0, 1.25f32).unwrap();
43    /// ```
44    ///
45    /// # Errors and Failures
46    /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
47    ///   if `s < 0`.
48    ///
49    /// # Panics ...
50    /// - if the provided number of rows and columns or the modulus are not suited to create a matrix.
51    ///   For further information see [`MatZq::new`].
52    /// - if the provided `modulus < 2`.
53    pub fn sample_discrete_gauss(
54        num_rows: impl TryInto<i64> + Display,
55        num_cols: impl TryInto<i64> + Display,
56        modulus: impl Into<Modulus>,
57        center: impl Into<Q>,
58        s: impl Into<Q>,
59    ) -> Result<MatZq, MathError> {
60        let center: Q = center.into();
61        let s: Q = s.into();
62        let mut out = Self::new(num_rows, num_cols, modulus);
63
64        let mut dgis = DiscreteGaussianIntegerSampler::init(
65            &center,
66            &s,
67            unsafe { TAILCUT },
68            LookupTableSetting::FillOnTheFly,
69        )?;
70
71        for row in 0..out.get_num_rows() {
72            for col in 0..out.get_num_columns() {
73                let sample = dgis.sample_z();
74                unsafe { out.set_entry_unchecked(row, col, sample) };
75            }
76        }
77
78        Ok(out)
79    }
80
81    /// SampleD samples a discrete Gaussian from the lattice with a provided `basis`.
82    ///
83    /// We do not check whether `basis` is actually a basis. Hence, the callee is
84    /// responsible for making sure that `basis` provides a suitable basis.
85    ///
86    /// Parameters:
87    /// - `basis`: specifies a basis for the lattice from which is sampled
88    /// - `center`: specifies the positions of the center with peak probability
89    /// - `s`: specifies the Gaussian parameter, which is proportional
90    ///   to the standard deviation `sigma * sqrt(2 * pi) = s`
91    ///
92    /// Returns a lattice vector sampled according to the discrete Gaussian distribution
93    /// or an error if `s < 0`, the number of rows of the `basis` and `center` differ,
94    /// or if `center` is not a column vector.
95    ///
96    /// # Examples
97    /// ```
98    /// use qfall_math::{integer_mod_q::MatZq, rational::MatQ};
99    /// let basis = MatZq::identity(5, 5, 17);
100    /// let center = MatQ::new(5, 1);
101    ///
102    /// let sample = MatZq::sample_d(&basis, &center, 1.25f32).unwrap();
103    /// ```
104    ///
105    /// # Errors and Failures
106    /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
107    ///   if `s < 0`.
108    /// - Returns a [`MathError`] of type [`MismatchingMatrixDimension`](MathError::MismatchingMatrixDimension)
109    ///   if the number of rows of the `basis` and `center` differ.
110    /// - Returns a [`MathError`] of type [`StringConversionError`](MathError::StringConversionError)
111    ///   if `center` is not a column vector.
112    ///
113    /// This function implements SampleD according to:
114    /// - \[1\] Gentry, Craig and Peikert, Chris and Vaikuntanathan, Vinod (2008).
115    ///   Trapdoors for hard lattices and new cryptographic constructions.
116    ///   In: Proceedings of the fortieth annual ACM symposium on Theory of computing.
117    ///   <https://dl.acm.org/doi/pdf/10.1145/1374376.1374407>
118    pub fn sample_d(basis: &MatZq, center: &MatQ, s: impl Into<Q>) -> Result<Self, MathError> {
119        let s: Q = s.into();
120
121        let sample = sample_d(
122            &basis.get_representative_least_nonnegative_residue(),
123            center,
124            &s,
125        )?;
126
127        Ok(MatZq::from((&sample, basis.get_mod())))
128    }
129
130    /// SampleD samples a discrete Gaussian from the lattice with a provided `basis`.
131    ///
132    /// We do not check whether `basis` is actually a basis or whether `basis_gso` is
133    /// actually the gso of `basis`. Hence, the callee is responsible for making sure
134    /// that `basis` provides a suitable basis and `basis_gso` is a corresponding GSO.
135    ///
136    /// Parameters:
137    /// - `basis`: specifies a basis for the lattice from which is sampled
138    /// - `basis_gso`: specifies the precomputed gso for `basis`
139    /// - `center`: specifies the positions of the center with peak probability
140    /// - `s`: specifies the Gaussian parameter, which is proportional
141    ///   to the standard deviation `sigma * sqrt(2 * pi) = s`
142    ///
143    /// Returns a lattice vector sampled according to the discrete Gaussian distribution
144    /// or an error if `s < 0`, the number of rows of the `basis` and `center` differ,
145    /// or if `center` is not a column vector.
146    ///
147    /// # Examples
148    /// ```
149    /// use qfall_math::{integer::MatZ, integer_mod_q::MatZq, rational::MatQ};
150    /// let basis = MatZq::identity(5, 5, 17);
151    /// let center = MatQ::new(5, 1);
152    /// let basis_gso = MatQ::from(&basis.get_representative_least_nonnegative_residue()).gso();
153    ///
154    /// let sample = MatZq::sample_d_precomputed_gso(&basis, &basis_gso, &center, 1.25f32).unwrap();
155    /// ```
156    ///
157    /// # Errors and Failures
158    /// - Returns a [`MathError`] of type [`InvalidIntegerInput`](MathError::InvalidIntegerInput)
159    ///   if `s < 0`.
160    /// - Returns a [`MathError`] of type [`MismatchingMatrixDimension`](MathError::MismatchingMatrixDimension)
161    ///   if the number of rows of the `basis` and `center` differ.
162    /// - Returns a [`MathError`] of type [`StringConversionError`](MathError::StringConversionError)
163    ///   if `center` is not a column vector.
164    ///
165    /// # Panics ...
166    /// - if the number of rows/columns of `basis_gso` and `basis` mismatch.
167    ///
168    /// This function implements SampleD according to:
169    /// - \[1\] Gentry, Craig and Peikert, Chris and Vaikuntanathan, Vinod (2008).
170    ///   Trapdoors for hard lattices and new cryptographic constructions.
171    ///   In: Proceedings of the fortieth annual ACM symposium on Theory of computing.
172    ///   <https://dl.acm.org/doi/pdf/10.1145/1374376.1374407>
173    pub fn sample_d_precomputed_gso(
174        basis: &MatZq,
175        basis_gso: &MatQ,
176        center: &MatQ,
177        s: impl Into<Q>,
178    ) -> Result<Self, MathError> {
179        let s: Q = s.into();
180
181        let sample = sample_d_precomputed_gso(
182            &basis.get_representative_least_nonnegative_residue(),
183            basis_gso,
184            center,
185            &s,
186        )?;
187
188        Ok(MatZq::from((&sample, basis.get_mod())))
189    }
190}
191
192#[cfg(test)]
193mod test_sample_discrete_gauss {
194    use crate::{
195        integer::Z,
196        integer_mod_q::{MatZq, Modulus},
197        rational::Q,
198    };
199
200    // This function only allows for a broader availability, which is tested here.
201
202    /// Checks whether `sample_discrete_gauss` is available for all types
203    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
204    /// or [`Into<Q>`], i.e. u8, i16, f32, Z, Q, ...
205    #[test]
206    fn availability() {
207        let n = Z::from(1024);
208        let center = Q::ZERO;
209        let s = Q::ONE;
210        let modulus = Modulus::from(83);
211
212        let _ = MatZq::sample_discrete_gauss(2u64, 3i8, &modulus, 0f32, 1u16);
213        let _ = MatZq::sample_discrete_gauss(3u8, 2i16, 83u8, &center, 1u8);
214        let _ = MatZq::sample_discrete_gauss(1, 1, &n, &center, 1u32);
215        let _ = MatZq::sample_discrete_gauss(1, 1, 83i8, &center, 1u64);
216        let _ = MatZq::sample_discrete_gauss(1, 1, 83, &center, 1i64);
217        let _ = MatZq::sample_discrete_gauss(1, 1, 83, &center, 1i32);
218        let _ = MatZq::sample_discrete_gauss(1, 1, 83, &center, 1i16);
219        let _ = MatZq::sample_discrete_gauss(1, 1, 83, &center, 1i8);
220        let _ = MatZq::sample_discrete_gauss(1, 1, 83, &center, 1i64);
221        let _ = MatZq::sample_discrete_gauss(1, 1, 83, &center, &n);
222        let _ = MatZq::sample_discrete_gauss(1, 1, 83, &center, &s);
223        let _ = MatZq::sample_discrete_gauss(1, 1, 83, &center, 1.25f64);
224        let _ = MatZq::sample_discrete_gauss(1, 1, 83, 0, 1.25f64);
225        let _ = MatZq::sample_discrete_gauss(1, 1, 83, center, 15.75f32);
226    }
227}
228
229#[cfg(test)]
230mod test_sample_d {
231    use crate::{
232        integer::Z,
233        integer_mod_q::MatZq,
234        rational::{MatQ, Q},
235    };
236
237    // Appropriate inputs were tested in utils and thus omitted here.
238    // This function only allows for a broader availability, which is tested here.
239
240    /// Checks whether `sample_d` is available for all types
241    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
242    /// or [`Into<Q>`], i.e. u8, i16, f32, Z, Q, ...
243    #[test]
244    fn availability() {
245        let basis = MatZq::identity(5, 5, 17);
246        let n = Z::from(1024);
247        let center = MatQ::new(5, 1);
248        let s = Q::ONE;
249
250        let _ = MatZq::sample_d(&basis, &center, 1u16);
251        let _ = MatZq::sample_d(&basis, &center, 1u8);
252        let _ = MatZq::sample_d(&basis, &center, 1u32);
253        let _ = MatZq::sample_d(&basis, &center, 1u64);
254        let _ = MatZq::sample_d(&basis, &center, 1i64);
255        let _ = MatZq::sample_d(&basis, &center, 1i32);
256        let _ = MatZq::sample_d(&basis, &center, 1i16);
257        let _ = MatZq::sample_d(&basis, &center, 1i8);
258        let _ = MatZq::sample_d(&basis, &center, 1i64);
259        let _ = MatZq::sample_d(&basis, &center, &n);
260        let _ = MatZq::sample_d(&basis, &center, &s);
261        let _ = MatZq::sample_d(&basis, &center, 1.25f64);
262        let _ = MatZq::sample_d(&basis, &center, 15.75f32);
263    }
264
265    /// Checks whether `sample_d_precomputed_gso` is available for all types
266    /// implementing [`Into<Z>`], i.e. u8, u16, u32, u64, i8, ...
267    /// or [`Into<Q>`], i.e. u8, i16, f32, Z, Q, ...
268    #[test]
269    fn availability_prec_gso() {
270        let basis = MatZq::identity(5, 5, 17);
271        let n = Z::from(1024);
272        let center = MatQ::new(5, 1);
273        let s = Q::ONE;
274        let basis_gso = MatQ::from(&basis.get_representative_least_nonnegative_residue());
275
276        let _ = MatZq::sample_d_precomputed_gso(&basis, &basis_gso, &center, 1u16);
277        let _ = MatZq::sample_d_precomputed_gso(&basis, &basis_gso, &center, 1u8);
278        let _ = MatZq::sample_d_precomputed_gso(&basis, &basis_gso, &center, 1u32);
279        let _ = MatZq::sample_d_precomputed_gso(&basis, &basis_gso, &center, 1u64);
280        let _ = MatZq::sample_d_precomputed_gso(&basis, &basis_gso, &center, 1i64);
281        let _ = MatZq::sample_d_precomputed_gso(&basis, &basis_gso, &center, 1i32);
282        let _ = MatZq::sample_d_precomputed_gso(&basis, &basis_gso, &center, 1i16);
283        let _ = MatZq::sample_d_precomputed_gso(&basis, &basis_gso, &center, 1i8);
284        let _ = MatZq::sample_d_precomputed_gso(&basis, &basis_gso, &center, 1i64);
285        let _ = MatZq::sample_d_precomputed_gso(&basis, &basis_gso, &center, &n);
286        let _ = MatZq::sample_d_precomputed_gso(&basis, &basis_gso, &center, &s);
287        let _ = MatZq::sample_d_precomputed_gso(&basis, &basis_gso, &center, 1.25f64);
288        let _ = MatZq::sample_d_precomputed_gso(&basis, &basis_gso, &center, 15.75f32);
289    }
290}
qfall_math/integer_mod_q/mat_zq/sample/discrete_gauss.rs

qfall_math/integer_mod_q/mat_zq/sample/
discrete_gauss.rs
