labrador/core/
jl.rs

1use crate::ring::poly::PolyVector;
2use crate::ring::poly::ZqVector;
3use crate::ring::rq::Rq;
4use crate::ring::rq_vector::RqVector;
5use crate::ring::zq::Zq;
6use rand::prelude::*;
7use rand::rng;
8
9/// The security level \lambda is 128
10pub const SECURITY_LEVEL: usize = 128;
11/// The size of the projection matrix is 2\lambda
12pub const PROJECTION_MATRIX_SIZE: usize = 2 * SECURITY_LEVEL;
13/// Projection matrix with values in {1,0,-1} mod q
14pub struct ProjectionMatrix<const D: usize> {
15    matrix: Vec<ZqVector>,
16}
17
18impl<const D: usize> ProjectionMatrix<D> {
19    /// Defines a matrix of size 256xnxD
20    /// n is the size of the vector of polynomials
21    pub fn new(n: usize) -> Self {
22        let mut matrix = vec![ZqVector::new(vec![Zq::ZERO; n * D]); PROJECTION_MATRIX_SIZE];
23        let mut rng = rng();
24        for row in matrix.iter_mut() {
25            for elem in row.iter_mut() {
26                let rand_val: f64 = rng.random();
27                *elem = if rand_val < 0.25 {
28                    Zq::MAX // -1 in Zq
29                } else if rand_val < 0.75 {
30                    Zq::ZERO
31                } else {
32                    Zq::ONE
33                };
34            }
35        }
36
37        ProjectionMatrix { matrix }
38    }
39
40    /// Returns the matrix
41    pub fn get_matrix(&self) -> &Vec<ZqVector> {
42        &self.matrix
43    }
44}
45
46/// Calculate projection vector
47#[derive(Debug, Clone)]
48pub struct ProjectionVector<const N: usize, const D: usize> {
49    projection: Rq<PROJECTION_MATRIX_SIZE>,
50}
51
52impl<const N: usize, const D: usize> ProjectionVector<N, D> {
53    /// Calculates Projection
54    pub fn new(matrix: &ProjectionMatrix<D>, s_i: &RqVector<N, D>) -> Self {
55        let mut projection = Rq::new([Zq::ZERO; PROJECTION_MATRIX_SIZE]);
56        let coefficients = s_i.concatenate_coefficients();
57        for (i, item) in projection.iter_mut().enumerate() {
58            *item = matrix.get_matrix()[i]
59                .iter()
60                .zip(coefficients.iter())
61                .map(|(m, s)| *m * *s)
62                .sum::<Zq>();
63        }
64        ProjectionVector { projection }
65    }
66
67    /// Obtain projection
68    pub fn get_projection(&self) -> &Rq<PROJECTION_MATRIX_SIZE> {
69        &self.projection
70    }
71
72    /// Euclidean norm
73    pub fn norm_squared(&self) -> Zq {
74        self.projection.iter().map(|coeff| *coeff * *coeff).sum()
75    }
76}
77
78#[derive(Debug, Clone)]
79pub struct Projections {
80    pub projection: ZqVector,
81}
82
83impl Projections {
84    /// Calculates Projection
85    pub fn new(matrices: &[Vec<ZqVector>], witness: &[PolyVector]) -> Self {
86        let mut temp = Vec::with_capacity(PROJECTION_MATRIX_SIZE);
87        let coefficients: Vec<ZqVector> = witness
88            .iter()
89            .map(|s_i| s_i.concatenate_coefficients(PROJECTION_MATRIX_SIZE))
90            .collect();
91
92        for j in 0..PROJECTION_MATRIX_SIZE {
93            let mut sum = Zq::ZERO;
94            for i in 0..matrices.len() {
95                let pi = &matrices[i][j];
96                let s_i = &coefficients[i];
97                let inner = pi.inner_product(s_i);
98                sum += inner;
99            }
100            temp.push(sum);
101        }
102        let projection = ZqVector::new(temp);
103
104        Projections { projection }
105    }
106
107    /// Obtain projection
108    pub fn get_projection(&self) -> &ZqVector {
109        &self.projection
110    }
111
112    /// Euclidean norm
113    pub fn norm_squared(&self) -> Zq {
114        self.projection.iter().map(|coeff| *coeff * *coeff).sum()
115    }
116}
117
118// Bound verification
119
120// LaBRADOR: Compact Proofs for R1CS from Module-SIS | Page 5 | Proving smallness section
121const UPPER_BOUND_FACTOR: Zq = Zq::new(128);
122const LOWER_BOUND_FACTOR: Zq = Zq::new(30);
123
124// Function to verify upper bound of projection
125pub fn verify_upper_bound<const N: usize, const D: usize>(
126    projection: ProjectionVector<N, D>,
127    beta_squared: Zq,
128) -> bool {
129    projection.norm_squared() < (UPPER_BOUND_FACTOR * beta_squared)
130}
131// Function to verify lower bound of projection
132pub fn verify_lower_bound<const N: usize, const D: usize>(
133    projection: ProjectionVector<N, D>,
134    beta_squared: Zq,
135) -> bool {
136    projection.norm_squared() > (LOWER_BOUND_FACTOR * beta_squared)
137}
138
139#[cfg(test)]
140mod tests {
141    use super::*;
142
143    // Test Size correctness of projection matrix
144    #[test]
145    fn test_size_projection_matrix() {
146        let n = 10;
147        let matrix = ProjectionMatrix::<4>::new(n);
148
149        assert_eq!(
150            matrix.matrix.len(),
151            PROJECTION_MATRIX_SIZE,
152            "Matrix should have {} rows",
153            PROJECTION_MATRIX_SIZE
154        );
155        assert_eq!(
156            matrix.matrix[0].len(),
157            n * 4,
158            "Matrix should have {} columns",
159            n * 4
160        );
161
162        let n2 = 1;
163        let matrix = ProjectionMatrix::<4>::new(n2);
164
165        assert_eq!(
166            matrix.matrix.len(),
167            PROJECTION_MATRIX_SIZE,
168            "Matrix should have {} rows",
169            PROJECTION_MATRIX_SIZE
170        );
171        assert_eq!(
172            matrix.matrix[0].len(),
173            n2 * 4,
174            "Matrix should have {} columns",
175            n2 * 4
176        );
177    }
178
179    // Test the distribution of values in the random matrix
180    #[test]
181    fn test_random_distribution_matrix() {
182        // 1000 was chosen to provide a reasonably large sample size
183        let n = 1000;
184        let matrix = ProjectionMatrix::<4>::new(n);
185        let mut counts = [0.0, 0.0, 0.0]; // -1, 0, 1
186        for row in matrix.matrix.iter() {
187            for &elem in row.iter() {
188                if elem == Zq::MAX {
189                    counts[0] += 1.0;
190                } else if elem == Zq::ZERO {
191                    counts[1] += 1.0;
192                } else if elem == Zq::ONE {
193                    counts[2] += 1.0;
194                }
195            }
196        }
197        // Number of elements in the matrix as f64 (256x4x1000)
198        let total: f64 = 1024000.0;
199        println!("this is the total amount of elements{}", total);
200        let expected = [0.25, 0.5, 0.25];
201        for i in 0..3 {
202            let actual = counts[i] / total;
203            println!("This is the actual value {}", actual);
204            assert!(
205                //Since its a statistical test some small error tolerance is allowed
206                (actual - expected[i]).abs() < 0.005,
207                "Values are not within expected proportions"
208            );
209        }
210    }
211
212    // Test that the probability of the inequality being true is close to 1/2
213    #[test]
214    #[cfg(not(feature = "skip-slow-tests"))]
215    fn test_probability_is_close_to_half() {
216        // 10.000 was chosen to provide a reasonably large sample size
217        let trials: f64 = 10000.0;
218        let mut success_count: f64 = 0.0;
219        let n = 5;
220        for _ in 0..10000 {
221            let mut rng = rng();
222            // Generate the random polynomials
223            let polynomials = RqVector::<5, 5>::random_ternary(&mut rng);
224            // Generate projection matrix
225            let matrix = ProjectionMatrix::new(n);
226            // Generate Projection
227            let projection = ProjectionVector::new(&matrix, &polynomials);
228            let beta = polynomials.compute_norm_squared();
229            // Check if the norm of the projection is smaller than 128 * (squared norm of the projection of the random polynomial)
230            let test: bool = verify_upper_bound(projection, beta);
231            if test {
232                success_count += 1.0;
233            }
234        }
235
236        let observed_probability = success_count / trials;
237
238        // We allow some tolerance because of the statistical nature of the results.
239        let tolerance = 0.05;
240        assert!(
241            (observed_probability - 0.5).abs() < tolerance,
242            "Observed probability {} is not close to 0.5",
243            observed_probability
244        );
245    }
246
247    // On average the projected norm squared is the same as 128 * vector norm squared
248    #[test]
249    #[cfg(not(feature = "skip-slow-tests"))]
250    fn average_value() {
251        // 100.000 was chosen to provide a reasonably large sample size
252        let trials: u128 = 100000;
253        let n = 3;
254        let mut rng = rng();
255        let polynomials = RqVector::<3, 3>::random_ternary(&mut rng);
256        let mut matrix = ProjectionMatrix::new(n);
257        let mut projection = ProjectionVector::new(&matrix, &polynomials);
258        let mut norm_sum = projection.norm_squared();
259        let norm_value = (Zq::new(SECURITY_LEVEL.try_into().unwrap())
260            * RqVector::compute_norm_squared(&polynomials))
261        .to_u128();
262        // Run the test multiple times to simulate the probability
263        for _ in 0..trials {
264            matrix = ProjectionMatrix::new(n);
265            projection = ProjectionVector::new(&matrix, &polynomials);
266            norm_sum += projection.norm_squared();
267        }
268
269        // Calculate the observed probability
270        let average = norm_sum.to_u128() / trials;
271        let difference = if norm_value <= average {
272            average - norm_value
273        } else {
274            norm_value - average
275        };
276
277        // we choose a small tolerance value for possible statistical error
278        let tolerance: u128 = 2;
279        assert!(
280            difference < tolerance,
281            "Average norm value {} is not equal to {}.",
282            average,
283            Zq::new(SECURITY_LEVEL.try_into().unwrap()) * polynomials.compute_norm_squared(),
284        );
285    }
286
287    // Test lower bound verification
288    #[test]
289    fn test_lower_bound() {
290        let n = 5;
291        let mut rng = rng();
292        // Generate random vector of polynomials of small norm
293        let polynomials = RqVector::<5, 64>::random_ternary(&mut rng);
294        // Generate projection matrix
295        let matrix = ProjectionMatrix::new(n);
296        // Generate Projection
297        let projection = ProjectionVector::new(&matrix, &polynomials);
298        let beta = polynomials.compute_norm_squared();
299        // Check if the norm of the projection is bigger than 30 * (squared norm of the projection of the random polynomial)
300        assert!(verify_lower_bound(projection, beta));
301    }
302
303    // Test vector concatenation
304    #[test]
305    fn test_vector_concatenation() {
306        let polynomials: RqVector<2, 4> = RqVector::from(vec![
307            vec![Zq::ONE, Zq::ZERO, Zq::ZERO, Zq::MAX].into(),
308            vec![Zq::new(6), Zq::ZERO, Zq::new(5), Zq::new(3)].into(),
309        ]);
310        let vector = vec![
311            Zq::ONE,
312            Zq::ZERO,
313            Zq::ZERO,
314            Zq::MAX,
315            Zq::new(6),
316            Zq::ZERO,
317            Zq::new(5),
318            Zq::new(3),
319        ];
320        assert!(polynomials.concatenate_coefficients() == vector);
321    }
322}
labrador/core/jl.rs

labrador/core/
jl.rs
