labrador/core/
jl.rs

1use crate::ring::rq_matrix::RqMatrix;
2use crate::ring::rq_vector::RqVector;
3use crate::ring::zq::Zq;
4use crate::ring::{self, Norms};
5
6// LaBRADOR: Compact Proofs for R1CS from Module-SIS | Page 5 | Proving smallness section
7const UPPER_BOUND_FACTOR: u128 = 128;
8const LOWER_BOUND_FACTOR: u128 = 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            .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.elements()
61                    .iter()
62                    .map(|pi_ij| {
63                        pi_ij
64                            .elements()
65                            .iter()
66                            .map(|polynomial| polynomial.conjugate_automorphism())
67                            .collect()
68                    })
69                    .collect()
70            })
71            .collect()
72    }
73
74    // Function to verify upper bound of projection
75    pub fn verify_projection_upper_bound(projection: &[Zq], beta_squared: u128) -> bool {
76        projection.l2_norm_squared() <= (UPPER_BOUND_FACTOR * beta_squared)
77    }
78
79    // Function to verify lower bound of projection
80    pub fn verify_projection_lower_bound(projection: &[Zq], beta_squared: u128) -> bool {
81        projection.l2_norm_squared() > (LOWER_BOUND_FACTOR * beta_squared)
82    }
83}
84
85#[cfg(test)]
86mod tests {
87    use super::*;
88    use crate::relation::witness::Witness;
89    use crate::ring::Norms;
90    use crate::transcript::sponges::shake::ShakeSponge;
91    use crate::transcript::LabradorTranscript;
92    use rand::rng;
93
94    // Test that the probability of the inequality being true is close to 1/2
95    #[test]
96    #[cfg(not(feature = "skip-slow-tests"))]
97    fn test_projection_is_smaller_than_upper_bound() {
98        let (security_parameter, rank, multiplicity) = (128, 5, 1);
99        // 1000 was chosen to provide a reasonably large sample size
100
101        let trials: f64 = 1000.0;
102        let mut success_count: f64 = 0.0;
103        for _ in 0..1000 {
104            let mut transcript = LabradorTranscript::new(ShakeSponge::default());
105            // This gives randomness to the transcript, to generate random projection matrices.
106            transcript.set_u1(RqVector::random(&mut rng(), 1));
107            let projections =
108                transcript.generate_projections(security_parameter, rank, multiplicity);
109
110            let witness_vector = Witness::new(rank, multiplicity, 6400 * 6400).s;
111            let result = projections.compute_projection(0, &witness_vector[0]);
112            let beta = witness_vector[0].l2_norm_squared();
113            // dbg!(&result);
114            dbg!(result.l2_norm_squared());
115            dbg!(UPPER_BOUND_FACTOR * beta);
116            // Check if the norm of the projection is smaller than 128 * (squared norm of the projection of the random polynomial)
117            let test: bool = Projection::verify_projection_upper_bound(&result, beta);
118            if test {
119                success_count += 1.0;
120            }
121        }
122
123        let observed_probability = success_count / trials;
124
125        // We allow some tolerance because of the statistical nature of the results.
126        let tolerance = 0.05;
127        assert!(
128            (observed_probability - 0.5).abs() < tolerance,
129            "Observed probability {} is not close to 0.5",
130            observed_probability
131        );
132    }
133
134    // On average the projected norm squared is the same as 128 * vector norm squared
135    #[test]
136    #[cfg(not(feature = "skip-slow-tests"))]
137    fn test_projection_average_value() {
138        use crate::{relation::witness::Witness, ring::Norms};
139
140        let (security_parameter, rank, multiplicity) = (128, 3, 1);
141        let trials: u128 = 10000;
142
143        // let witness = RqVector::random_ternary(&mut rand::rng(), rank);
144        let witness = Witness::new(rank, multiplicity, 6400).s;
145        let witness_norm = 128 * witness[0].l2_norm_squared();
146
147        let mut norm_sum = 0u128;
148        // Run the test multiple times to simulate the probability
149        for _ in 0..trials {
150            let mut transcript = LabradorTranscript::new(ShakeSponge::default());
151            // This gives randomness to the transcript, to generate random projection matrices.
152            transcript.set_u1(RqVector::random(&mut rng(), 1));
153            let projections =
154                transcript.generate_projections(security_parameter, rank, multiplicity);
155            let result = projections.compute_projection(0, &witness[0]);
156            norm_sum += result.l2_norm_squared();
157        }
158
159        // Calculate the observed probability
160        let average = norm_sum as f64 / trials as f64;
161        let ratio = if witness_norm as f64 <= average {
162            average / witness_norm as f64
163        } else {
164            witness_norm as f64 / average
165        };
166
167        // we choose a small tolerance value for possible statistical error
168        let tolerance_percent: f64 = 1.05;
169        assert!(
170            ratio < tolerance_percent,
171            "Average norm value {} is not equal to {}.",
172            average,
173            witness_norm,
174        );
175    }
176
177    // Test lower bound verification
178    #[test]
179    fn test_lower_bound() {
180        let (security_parameter, rank, multiplicity) = (128, 5, 1);
181
182        let mut transcript = LabradorTranscript::new(ShakeSponge::default());
183        transcript.set_u1(RqVector::random(&mut rng(), 1));
184        let projections = transcript.generate_projections(security_parameter, rank, multiplicity);
185        let witness = Witness::new(rank, multiplicity, 6400).s;
186
187        let beta = witness[0].l2_norm_squared();
188        // Check if the norm of the projection is bigger than 30 * (squared norm of the projection of the random polynomial)
189        assert!(Projection::verify_projection_lower_bound(
190            &projections.compute_projection(0, &witness[0]),
191            beta
192        ));
193    }
194}
labrador/core/jl.rs

labrador/core/
jl.rs
