labrador/core/
jl.rs

1use crate::ring;
2use crate::ring::rq_matrix::RqMatrix;
3use crate::ring::rq_vector::RqVector;
4use crate::ring::zq::Zq;
5
6// LaBRADOR: Compact Proofs for R1CS from Module-SIS | Page 5 | Proving smallness section
7const UPPER_BOUND_FACTOR: Zq = Zq::new(128);
8const LOWER_BOUND_FACTOR: Zq = Zq::new(30);
9
10pub struct Projection {
11    random_linear_map_vector: Vec<RqMatrix>,
12    security_level: usize,
13}
14
15impl Projection {
16    pub fn new(random_linear_map_vector: Vec<RqMatrix>, security_level: usize) -> Self {
17        Self {
18            random_linear_map_vector,
19            security_level,
20        }
21    }
22
23    fn compute_projection(&self, index: usize, witness: &RqVector) -> Vec<Zq> {
24        let mut projection = vec![Zq::ZERO; 2 * self.security_level];
25        let coefficients = witness.concatenate_coefficients();
26        for (i, pi_ij) in self.random_linear_map_vector[index]
27            .get_elements()
28            .iter()
29            .enumerate()
30        {
31            projection[i] = pi_ij
32                .concatenate_coefficients()
33                .iter()
34                .zip(coefficients.iter())
35                .map(|(m, s)| *m * *s)
36                .sum::<Zq>();
37        }
38        projection
39    }
40
41    pub fn compute_batch_projection(&self, witness_vector: &[RqVector]) -> Vec<Zq> {
42        let mut result = vec![Zq::ZERO; 2 * self.security_level];
43        for (index_i, witness) in witness_vector.iter().enumerate() {
44            ring::zq::add_assign_two_zq_vectors(
45                &mut result,
46                self.compute_projection(index_i, witness),
47            );
48        }
49        result
50    }
51
52    pub fn get_projection_matrices(&self) -> &[RqMatrix] {
53        &self.random_linear_map_vector
54    }
55
56    pub fn get_conjugated_projection_matrices(&self) -> Vec<RqMatrix> {
57        self.random_linear_map_vector
58            .iter()
59            .map(|pi_i| {
60                pi_i.get_elements()
61                    .iter()
62                    .map(|pi_ij| {
63                        pi_ij
64                            .get_elements()
65                            .iter()
66                            .map(|polynomial| polynomial.conjugate_automorphism())
67                            .collect()
68                    })
69                    .collect()
70            })
71            .collect()
72    }
73
74    #[allow(clippy::as_conversions)]
75    fn norm_squared(projection: &[Zq]) -> Zq {
76        projection
77            .iter()
78            .map(|coeff| {
79                coeff.centered_mod(Zq::new(Zq::Q as u32))
80                    * coeff.centered_mod(Zq::new(Zq::Q as u32))
81            })
82            .sum()
83    }
84
85    // Function to verify upper bound of projection
86    pub fn verify_projection_upper_bound(projection: &[Zq], beta_squared: Zq) -> bool {
87        Self::norm_squared(projection) < (UPPER_BOUND_FACTOR * beta_squared)
88    }
89
90    // Function to verify lower bound of projection
91    pub fn verify_projection_lower_bound(projection: &[Zq], beta_squared: Zq) -> bool {
92        Self::norm_squared(projection) > (LOWER_BOUND_FACTOR * beta_squared)
93    }
94}
95
96#[cfg(test)]
97mod tests {
98    use super::*;
99    use crate::relation::witness::Witness;
100    use crate::transcript::sponges::shake::ShakeSponge;
101    use crate::transcript::LabradorTranscript;
102    use rand::rng;
103
104    // Test that the probability of the inequality being true is close to 1/2
105    #[test]
106    #[cfg(not(feature = "skip-slow-tests"))]
107    fn test_projection_is_smaller_than_upper_bound() {
108        let (security_parameter, rank, multiplicity) = (128, 5, 1);
109        // 1000 was chosen to provide a reasonably large sample size
110
111        let trials: f64 = 1000.0;
112        let mut success_count: f64 = 0.0;
113        for _ in 0..1000 {
114            let mut transcript = LabradorTranscript::new(ShakeSponge::default());
115            // This gives randomness to the transcript, to generate random projection matrices.
116            transcript.set_u1(RqVector::random(&mut rng(), 1));
117            let projections =
118                transcript.generate_projections(security_parameter, rank, multiplicity);
119
120            let witness = RqVector::random(&mut rand::rng(), rank);
121            let result = projections.compute_projection(0, &witness);
122
123            let beta = witness.l2_norm_squared();
124            // Check if the norm of the projection is smaller than 128 * (squared norm of the projection of the random polynomial)
125            let test: bool = Projection::verify_projection_upper_bound(&result, beta);
126            if test {
127                success_count += 1.0;
128            }
129        }
130
131        let observed_probability = success_count / trials;
132
133        // We allow some tolerance because of the statistical nature of the results.
134        let tolerance = 0.05;
135        assert!(
136            (observed_probability - 0.5).abs() < tolerance,
137            "Observed probability {} is not close to 0.5",
138            observed_probability
139        );
140    }
141
142    // On average the projected norm squared is the same as 128 * vector norm squared
143    #[test]
144    #[cfg(not(feature = "skip-slow-tests"))]
145    fn test_projection_average_value() {
146        use crate::relation::witness::Witness;
147
148        let (security_parameter, rank, multiplicity) = (128, 3, 1);
149        let trials: u128 = 10000;
150
151        // let witness = RqVector::random_ternary(&mut rand::rng(), rank);
152        let witness = Witness::new(rank, multiplicity, Zq::new(6400)).s;
153        let witness_norm = (128 * witness[0].l2_norm_squared().to_u128()) as f64;
154
155        let mut norm_sum = 0u128;
156        // Run the test multiple times to simulate the probability
157        for _ in 0..trials {
158            let mut transcript = LabradorTranscript::new(ShakeSponge::default());
159            // This gives randomness to the transcript, to generate random projection matrices.
160            transcript.set_u1(RqVector::random(&mut rng(), 1));
161            let projections =
162                transcript.generate_projections(security_parameter, rank, multiplicity);
163            let result = projections.compute_projection(0, &witness[0]);
164            norm_sum += Projection::norm_squared(&result).to_u128();
165        }
166
167        // Calculate the observed probability
168        let average = norm_sum as f64 / trials as f64;
169        let ratio = if witness_norm <= average {
170            average / witness_norm
171        } else {
172            witness_norm / average
173        };
174
175        // we choose a small tolerance value for possible statistical error
176        let tolerance_percent: f64 = 1.01;
177        assert!(
178            ratio < tolerance_percent,
179            "Average norm value {} is not equal to {}.",
180            average,
181            witness_norm,
182        );
183    }
184
185    // Test lower bound verification
186    #[test]
187    fn test_lower_bound() {
188        let (security_parameter, rank, multiplicity) = (128, 5, 1);
189
190        let mut transcript = LabradorTranscript::new(ShakeSponge::default());
191        transcript.set_u1(RqVector::random(&mut rng(), 1));
192        let projections = transcript.generate_projections(security_parameter, rank, multiplicity);
193        let witness = Witness::new(rank, multiplicity, Zq::new(6400)).s;
194
195        let beta = witness[0].l2_norm_squared();
196        // Check if the norm of the projection is bigger than 30 * (squared norm of the projection of the random polynomial)
197        assert!(Projection::verify_projection_lower_bound(
198            &projections.compute_projection(0, &witness[0]),
199            beta
200        ));
201    }
202}
labrador/core/jl.rs

labrador/core/
jl.rs
