qfall_tools/primitive/
psf.rs

1// Copyright © 2023 Marcel Luca Schmidt, Marvin Beckmann
2//
3// This file is part of qFALL-tools.
4//
5// qFALL-tools 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//! Contains implementations of Preimage Samplable Functions, short [`PSF`].
10//!
11//! The main references are listed in the following
12//! and will be further referenced in submodules by these numbers:
13//! - \[1\] Micciancio, D., Peikert, C. (2012).
14//!   Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller.
15//!   In: Pointcheval, D., Johansson, T. (eds) Advances in Cryptology – EUROCRYPT 2012.
16//!   EUROCRYPT 2012. Lecture Notes in Computer Science, vol 7237.
17//!   Springer, Berlin, Heidelberg. <https://doi.org/10.1007/978-3-642-29011-4_41>
18//! - \[2\] Gür, K.D., Polyakov, Y., Rohloff, K., Ryan, G.W. and Savas, E., 2018,
19//!   January. Implementation and evaluation of improved Gaussian sampling for lattice
20//!   trapdoors. In Proceedings of the 6th Workshop on Encrypted Computing & Applied
21//!   Homomorphic Cryptography (pp. 61-71). <https://dl.acm.org/doi/pdf/10.1145/3267973.3267975>
22//! - \[3\] Peikert, Chris.
23//!   An efficient and parallel Gaussian sampler for lattices.
24//!   In: Annual Cryptology Conference - CRYPTO 2010.
25//!   Springer, Berlin, Heidelberg. <https://doi.org/10.1007/978-3-642-14623-7_5>
26
27mod gpv;
28mod gpv_ring;
29mod mp_perturbation;
30
31pub use gpv::PSFGPV;
32pub use gpv_ring::PSFGPVRing;
33pub use mp_perturbation::PSFPerturbation;
34
35/// This trait should be implemented by all constructions that are
36/// actual implementations of a preimage sampleable function.
37/// A formal definition for these PSFs can be found in
38/// [\[1\]](<index.html#:~:text=[1]>)
39pub trait PSF {
40    type A;
41    type Trapdoor;
42    type Domain;
43    type Range;
44
45    /// Samples a parity-check matrix and a trapdoor for that matrix.
46    ///
47    /// Returns the parity-check matrix and the trapdoor.
48    fn trap_gen(&self) -> (Self::A, Self::Trapdoor);
49
50    /// Samples an element in the domain according to a specified distribution.
51    ///
52    /// Returns the sampled element.
53    fn samp_d(&self) -> Self::Domain;
54
55    /// Samples an element `e` in the domain according to a specified distribution
56    /// conditioned on `f_a(a, e) = u`.
57    ///
58    /// Parameters:
59    /// - `a`: The parity-check matrix
60    /// - `r`: The G-Trapdoor for `a`
61    /// - `u`: The syndrome from the range
62    ///
63    /// Returns a sample `e` from the domain on the conditioned discrete
64    /// Gaussian distribution `f_a(a,e) = u`.
65    fn samp_p(&self, a: &Self::A, r: &Self::Trapdoor, u: &Self::Range) -> Self::Domain;
66
67    /// Implements the efficiently computable function `f_a`,
68    /// which is uniquely classified by `a`.
69    ///
70    /// Parameters:
71    /// - `a`: The parity-check matrix of dimensions `n x m`
72    /// - `sigma`: A column vector of length `m`
73    ///
74    /// Returns the result of `f_a`.
75    fn f_a(&self, a: &Self::A, sigma: &Self::Domain) -> Self::Range;
76
77    /// Checks whether an element is in the correct domain (and not just the correct type).
78    ///
79    /// Returns the result of the check as a boolean.
80    fn check_domain(&self, sigma: &Self::Domain) -> bool;
81}
qfall_tools/primitive/psf.rs

qfall_tools/primitive/
psf.rs
