labrador/relation/
witness.rs

1use rand::rng;
2
3use crate::ring::{rq::Rq, rq_vector::RqVector, Norms};
4
5pub struct Witness {
6    pub s: Vec<RqVector>,
7}
8
9impl Witness {
10    pub fn new(rank: usize, multiplicity: usize, bound_sq: u128) -> Self {
11        #[allow(clippy::as_conversions)]
12        let std = ((bound_sq as f64) / ((rank * multiplicity * Rq::DEGREE) as f64)).sqrt();
13        #[allow(clippy::as_conversions)]
14        let std = std as u32;
15        loop {
16            let s: Vec<RqVector> = (0..multiplicity)
17                .map(|_| RqVector::random_with_bound(&mut rng(), rank, std))
18                .collect();
19            if Self::validate_l2_norm(&s, bound_sq) {
20                return Self { s };
21            }
22        }
23    }
24
25    fn validate_l2_norm(candidate: &[RqVector], bound_sq: u128) -> bool {
26        for witness in candidate {
27            if witness.l2_norm_squared() > bound_sq {
28                return false;
29            }
30        }
31        true
32    }
33}
34
35#[cfg(test)]
36mod tests {
37
38    use crate::ring::{rq::Rq, rq_vector::RqVector, zq::Zq, Norms};
39
40    use super::Witness;
41
42    #[test]
43    fn test_witness_vector_norm() {
44        let bound_sq = 320000;
45        let witness_vector = Witness::new(40, 100, bound_sq);
46        assert_eq!(witness_vector.s.len(), 100);
47        assert_eq!(witness_vector.s[0].len(), 40);
48        for witness in witness_vector.s.iter() {
49            let l2_norm = witness.l2_norm_squared();
50            assert!(l2_norm < bound_sq * bound_sq)
51        }
52    }
53
54    #[test]
55    fn test_witness_with_larger_bound() {
56        let poly1 = Rq::new([Zq::new(10000); Rq::DEGREE]);
57        let poly2 = Rq::new([Zq::new(142310); Rq::DEGREE]);
58        let poly3 = Rq::new([Zq::new(9310); Rq::DEGREE]);
59        let poly_vector = vec![poly1, poly2, poly3];
60        assert!(!Witness::validate_l2_norm(
61            &[RqVector::new(poly_vector)],
62            1000
63        ));
64    }
65}
labrador/relation/witness.rs

labrador/relation/
witness.rs
