labrador/commitments/
ajtai_commitment.rs

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

labrador/commitments/
ajtai_commitment.rs
