labrador/core/
jl.rs

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

labrador/core/
jl.rs
