labrador/core/
challenge_set.rs

1use crate::ring::poly::PolyRing;
2use crate::ring::zq::Zq;
3use rand::prelude::*;
4use rand::seq::SliceRandom;
5
6pub struct ChallengeSet {
7    challenges: PolyRing,
8    norm: f64,
9}
10
11/// Challenge Space over R = Z_q\[X\] / (X^d + 1), paper page 6:
12impl ChallengeSet {
13    pub fn new(deg_bound_d: usize) -> Self {
14        // threshold \in R, threshold is "T" in the paper(Challenge Space, page 6) which is at most 15.
15        let op_norm = 15.0;
16        // Sample challenges with a given norm.
17        let challenges: PolyRing = sample_challenge_with_norm(deg_bound_d, op_norm);
18        let norm = PolyRing::operator_norm(&challenges);
19        ChallengeSet { challenges, norm }
20    }
21
22    /// Returns a reference to the challenge polynomial.
23    pub fn get_challenges(&self) -> &PolyRing {
24        &self.challenges
25    }
26
27    /// Returns the norm of the challenges.
28    pub fn get_norm(&self) -> f64 {
29        self.norm
30    }
31}
32
33/// Generates a candidate challenge polynomial with 64 coefficients:
34/// - 23 coefficients are 0
35/// - 31 coefficients are chosen uniformly from {+1, -1}
36/// - 10 coefficients are chosen uniformly from {+2, -2}
37///
38/// The coefficients are then shuffled randomly.
39fn sample_challenge(deg_bound_d: usize) -> PolyRing {
40    let mut rng = rand::rng();
41    let mut challenge: Vec<Zq> = Vec::with_capacity(deg_bound_d);
42
43    // Add 23 zeros.
44    for _ in 0..23 {
45        challenge.push(Zq::ZERO);
46    }
47    // Add 31 coefficients, each either +1 or -1.
48    for _ in 0..31 {
49        let value = if rng.random_bool(0.5) {
50            Zq::ONE
51        } else {
52            -Zq::ONE
53        };
54        challenge.push(value);
55    }
56    // Add 10 coefficients, each either +2 or -2.
57    for _ in 0..10 {
58        let value = if rng.random_bool(0.5) {
59            Zq::new(2)
60        } else {
61            -Zq::new(2)
62        };
63        challenge.push(value);
64    }
65
66    // Shuffle the vector to randomize the positions.
67    challenge.shuffle(&mut rng);
68    PolyRing::new(challenge)
69}
70
71/// Rejection sampling: repeatedly sample candidate challenges until one has an operator norm
72/// less than the specified threshold. Returns the accepted challenge and the number of samples tried.
73fn sample_challenge_with_norm(deg_bound_d: usize, threshold: f64) -> PolyRing {
74    loop {
75        let candidate = sample_challenge(deg_bound_d);
76        let norm = PolyRing::operator_norm(&candidate);
77        if norm < threshold {
78            return candidate;
79        }
80    }
81}
82
83#[cfg(test)]
84mod tests {
85    use super::*;
86
87    /// Test Challenge Set:
88    /// const 71 and const 15 are from Challenge Space, paper page 6.
89    /// l2 norm <= 71
90    /// operator norm <= 15
91    #[test]
92    fn test_challenge_set() {
93        let op_norm = 15.0;
94        let deg_bound_d: usize = 8;
95        let cs_1: ChallengeSet = ChallengeSet::new(deg_bound_d);
96        let norm = cs_1.get_norm();
97        let challenges_1 = cs_1.get_challenges();
98
99        let cs_2: ChallengeSet = ChallengeSet::new(deg_bound_d);
100        let challenges_2 = cs_2.get_challenges();
101
102        // l2 norm 71 is from paper page 6, Challenge Space.
103        assert_eq!(challenges_1.inner_product(challenges_1), Zq::new(71));
104        assert!(norm <= op_norm);
105
106        assert_ne!(challenges_1, challenges_2);
107    }
108}
labrador/core/challenge_set.rs

labrador/core/
challenge_set.rs
