labrador/commitments/
ajtai_commitment.rs

1use crate::ring::rq_matrix::RqMatrix;
2use crate::ring::rq_vector::RqVector;
3use crate::ring::zq::Zq;
4use crate::ring::Norms;
5use thiserror::Error;
6
7// Error types with documentation
8#[derive(Debug, Error)]
9pub enum ParameterError {
10    #[error("parameters must be positive")]
11    ZeroParameter,
12    #[error("security bound β·m^(3/2) must be less than q")]
13    SecurityBoundViolation,
14    #[error("invalid witness bounds specified")]
15    InvalidWitnessBounds(u128),
16    #[error("commitment output length {0} is too large")]
17    TooLargeCommitmentLength(usize),
18}
19
20#[derive(Debug, Error)]
21pub enum CommitError {
22    #[error("witness coefficients exceed bound {0}")]
23    InvalidWitnessBounds(u128),
24    #[error("invalid witness vector size")]
25    InvalidWitnessSize,
26}
27
28#[derive(Debug, Error)]
29pub enum VerificationError {
30    #[error("witness coefficients exceed bound {0}")]
31    InvalidWitnessBounds(u128),
32    #[error("commitment does not match opening")]
33    CommitmentMismatch,
34    #[error("invalid opening vector size")]
35    InvalidOpeningSize,
36    #[error("invalid commitment vector size")]
37    InvalidCommitmentSize,
38}
39
40/// Ajtai commitment scheme implementation with matrix-based operations
41#[derive(Debug)]
42pub struct AjtaiScheme {
43    // Square of norm_bound.
44    norm_bound_sq: u128,
45    random_matrix: RqMatrix,
46}
47
48impl AjtaiScheme {
49    pub fn new(norm_bound_sq: u128, random_matrix: RqMatrix) -> Result<Self, ParameterError> {
50        if norm_bound_sq == 0 {
51            return Err(ParameterError::InvalidWitnessBounds(norm_bound_sq));
52        }
53        Self::validate_parameters(
54            norm_bound_sq,
55            random_matrix.row_len(),
56            random_matrix.col_len(),
57        )?;
58
59        Ok(Self {
60            norm_bound_sq,
61            random_matrix,
62        })
63    }
64
65    /// Generates commitment and opening information with bounds checking
66    pub fn commit(&self, witness: &RqVector) -> Result<RqVector, CommitError> {
67        if !self.check_bounds(witness) {
68            return Err(CommitError::InvalidWitnessBounds(self.norm_bound_sq));
69        }
70        if witness.len() != self.random_matrix.col_len() {
71            return Err(CommitError::InvalidWitnessSize);
72        }
73        let commitment = &self.random_matrix * witness;
74        Ok(commitment)
75    }
76
77    /// Verifies commitment against opening information
78    pub fn verify(
79        &self,
80        commitment: &RqVector,
81        opening: &RqVector,
82    ) -> Result<(), VerificationError> {
83        if !self.check_bounds(opening) {
84            return Err(VerificationError::InvalidWitnessBounds(self.norm_bound_sq));
85        }
86        if opening.len() != self.random_matrix.col_len() {
87            return Err(VerificationError::InvalidOpeningSize);
88        }
89        if commitment.len() != self.random_matrix.row_len() {
90            return Err(VerificationError::InvalidCommitmentSize);
91        }
92
93        let recomputed = &self.random_matrix * opening;
94        if commitment != &recomputed {
95            return Err(VerificationError::CommitmentMismatch);
96        }
97
98        Ok(())
99    }
100
101    /// Verifies the security relation β²m³ < q² required for Ajtai's commitment scheme.
102    ///
103    /// This bound ensures the scheme's security by:
104    /// 1. Making the underlying lattice problem hard (SIS assumption)
105    /// 2. Preventing statistical attacks on the commitment
106    /// 3. Ensuring the commitment is binding under standard lattice assumptions
107    ///
108    /// The relation β²m³ < q² is a necessary condition derived from the security
109    /// proof of Ajtai's commitment scheme, where:
110    /// - β bounds the size of witness coefficients
111    /// - m is the commitment output length
112    /// - q is the modulus of the underlying ring
113    fn validate_parameters(
114        norm_bound_sq: u128,
115        row_len: usize,
116        col_len: usize,
117    ) -> Result<(), ParameterError> {
118        if [row_len, col_len].contains(&0) {
119            return Err(ParameterError::ZeroParameter);
120        }
121        // Calculate q from Zq properties
122        let q: u128 = Zq::NEG_ONE.to_u128() + 1;
123
124        // Calculate m³
125        let m_cubed: u128 = row_len
126            .checked_pow(3)
127            .ok_or(ParameterError::SecurityBoundViolation)?
128            .try_into()
129            .map_err(|_| ParameterError::TooLargeCommitmentLength(row_len))?;
130
131        // Calculate q²
132        let q_squared = q
133            .checked_pow(2)
134            .ok_or(ParameterError::SecurityBoundViolation)?;
135
136        // Check if norm_bound² * m³ < q²
137        // Use division instead of multiplication to avoid potential overflow
138        if norm_bound_sq >= q_squared.checked_div(m_cubed).unwrap_or(0) {
139            return Err(ParameterError::SecurityBoundViolation);
140        }
141        Ok(())
142    }
143
144    /// Checks that l2 norm of the value committing to is less than the norm bound
145    fn check_bounds(&self, _polynomials: &RqVector) -> bool {
146        _polynomials.l2_norm_squared() <= self.norm_bound_sq()
147    }
148
149    /// Returns a reference to the internal matrix
150    pub fn matrix(&self) -> &RqMatrix {
151        &self.random_matrix
152    }
153
154    /// Returns the norm bound
155    pub fn norm_bound_sq(&self) -> u128 {
156        self.norm_bound_sq
157    }
158
159    pub fn get_row_size(&self) -> usize {
160        self.random_matrix.elements().len()
161    }
162}
163
164#[cfg(test)]
165mod tests {
166    use super::*;
167    use crate::ring::rq::Rq;
168
169    const TEST_M: usize = 8;
170    const TEST_N: usize = 8;
171
172    // Test helpers
173    mod test_utils {
174        use crate::relation::witness::Witness;
175
176        use super::*;
177
178        pub fn valid_witness(coeff: Zq) -> RqVector {
179            vec![Rq::new([coeff; Rq::DEGREE]); TEST_N].into()
180        }
181
182        pub fn random_valid_witness() -> Vec<RqVector> {
183            Witness::new(TEST_N, 1, 10000).s
184        }
185
186        pub fn setup_scheme() -> AjtaiScheme {
187            let mut rng = rand::rng();
188            let random_matrix = RqMatrix::random(&mut rng, TEST_M, TEST_N);
189            AjtaiScheme::new(10000 * 10000, random_matrix).unwrap()
190        }
191    }
192
193    #[test]
194    fn rejects_invalid_parameters() {
195        assert!(AjtaiScheme::new(
196            0,
197            RqMatrix::new(vec![RqVector::new(vec![Rq::zero()])], false)
198        )
199        .is_err());
200        let _ = test_utils::setup_scheme(); // Will panic if setup fails
201    }
202
203    #[test]
204    fn initializes_with_correct_bounds() {
205        let scheme = test_utils::setup_scheme();
206        assert_eq!(scheme.norm_bound_sq(), 10000 * 10000);
207    }
208
209    #[test]
210    fn completes_commitment_cycle() {
211        let scheme = test_utils::setup_scheme();
212        let witness = test_utils::valid_witness(Zq::new(1));
213
214        let commitment = scheme.commit(&witness).unwrap();
215        assert!(scheme.verify(&commitment, &witness).is_ok());
216
217        let mut bad_opening = witness.clone();
218        let mut rng = rand::rng();
219        bad_opening.set(0, Rq::random(&mut rng));
220        assert!(scheme.verify(&commitment, &bad_opening).is_err());
221    }
222
223    #[test]
224    fn maintains_security_properties() {
225        let scheme = test_utils::setup_scheme();
226
227        // Use random witnesses to ensure they're different
228        let witness1 = test_utils::random_valid_witness();
229        let witness2 = test_utils::random_valid_witness();
230
231        // Ensure the witnesses are actually different
232        assert_ne!(witness1, witness2, "Test requires different witnesses");
233
234        let c1 = scheme.commit(&witness1[0]).unwrap();
235        let c2 = scheme.commit(&witness2[0]).unwrap();
236        assert_ne!(
237            c1, c2,
238            "Different witnesses should produce different commitments"
239        );
240    }
241
242    #[test]
243    fn handles_edge_cases() {
244        let scheme = test_utils::setup_scheme();
245        let zero_witness = RqVector::zero(TEST_N);
246
247        assert!(scheme.commit(&zero_witness).is_ok());
248        assert!(scheme
249            .commit(&test_utils::valid_witness(Zq::new(1)))
250            .is_ok());
251    }
252
253    #[test]
254    fn stress_test() {
255        let scheme = test_utils::setup_scheme();
256
257        (0..100).for_each(|_| {
258            let witness = test_utils::valid_witness(Zq::new(1));
259            let commitment = scheme.commit(&witness).unwrap();
260            assert!(scheme.verify(&commitment, &witness).is_ok());
261        });
262    }
263}
labrador/commitments/ajtai_commitment.rs

labrador/commitments/
ajtai_commitment.rs
