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    witness_bound: Zq,
43    random_matrix: RqMatrix,
44}
45
46impl AjtaiScheme {
47    pub fn new(
48        beta: Zq,
49        witness_bound: Zq,
50        random_matrix: RqMatrix,
51    ) -> Result<Self, ParameterError> {
52        if witness_bound.is_zero() {
53            return Err(ParameterError::InvalidWitnessBounds(witness_bound));
54        }
55        Self::validate_parameters(
56            beta,
57            random_matrix.get_row_len(),
58            random_matrix.get_col_len(),
59        )?;
60
61        Ok(Self {
62            witness_bound,
63            random_matrix,
64        })
65    }
66
67    /// Generates commitment and opening information with bounds checking
68    pub fn commit(&self, witness: &RqVector) -> Result<RqVector, CommitError> {
69        if !self.check_bounds(witness) {
70            return Err(CommitError::InvalidWitnessBounds(self.witness_bound));
71        }
72        if witness.get_length() != self.random_matrix.get_col_len() {
73            return Err(CommitError::InvalidWitnessSize);
74        }
75        let commitment = &self.random_matrix * witness;
76        Ok(commitment)
77    }
78
79    /// Verifies commitment against opening information
80    pub fn verify(
81        &self,
82        commitment: &RqVector,
83        opening: &RqVector,
84    ) -> Result<(), VerificationError> {
85        if !self.check_bounds(opening) {
86            return Err(VerificationError::InvalidWitnessBounds(self.witness_bound));
87        }
88        if opening.get_length() != self.random_matrix.get_col_len() {
89            return Err(VerificationError::InvalidOpeningSize);
90        }
91        if commitment.get_length() != self.random_matrix.get_row_len() {
92            return Err(VerificationError::InvalidCommitmentSize);
93        }
94
95        let recomputed = &self.random_matrix * opening;
96        if commitment != &recomputed {
97            return Err(VerificationError::CommitmentMismatch);
98        }
99
100        Ok(())
101    }
102
103    /// Validates scheme parameters against cryptographic security requirements
104    fn validate_parameters(beta: Zq, row_len: usize, col_len: usize) -> Result<(), ParameterError> {
105        if [row_len, col_len].contains(&0) {
106            return Err(ParameterError::ZeroParameter);
107        }
108        Self::verify_security_relation(beta, 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(beta: Zq, m: usize) -> Result<(), ParameterError> {
124        // Calculate q from Zq properties
125        let q_val = Zq::MAX;
126        let q: u128 = q_val.to_u128() + 1;
127
128        // Calculate beta²
129        let beta_squared = beta
130            .to_u128()
131            .checked_pow(2)
132            .ok_or(ParameterError::SecurityBoundViolation)?;
133
134        // Calculate m³
135        let m_cubed: u128 = m
136            .checked_pow(3)
137            .ok_or(ParameterError::SecurityBoundViolation)?
138            .try_into()
139            .map_err(|_| ParameterError::TooLargeCommitmentLength(m))?;
140
141        // Calculate q²
142        let q_squared = q
143            .checked_pow(2)
144            .ok_or(ParameterError::SecurityBoundViolation)?;
145
146        // Check if beta² * m³ < q²
147        // Use division instead of multiplication to avoid potential overflow
148        if beta_squared >= q_squared.checked_div(m_cubed).unwrap_or(0) {
149            return Err(ParameterError::SecurityBoundViolation);
150        }
151
152        Ok(())
153    }
154
155    /// Checks polynomial coefficients against specified bound
156    fn check_bounds(&self, _polynomials: &RqVector) -> bool {
157        // As now there are no concrete parameters, we return true.
158        true
159        // polynomials
160        //     .iter()
161        //     .all(|p| p.check_bounds(self.witness_bound))
162    }
163
164    /// Returns a reference to the internal matrix
165    pub fn matrix(&self) -> &RqMatrix {
166        &self.random_matrix
167    }
168
169    /// Returns the witness bound
170    pub fn witness_bound(&self) -> Zq {
171        self.witness_bound
172    }
173
174    pub fn get_row_size(&self) -> usize {
175        self.random_matrix.get_elements().len()
176    }
177
178    pub fn get_col_size(&self) -> usize {
179        self.random_matrix.get_elements()[0].get_elements().len()
180    }
181}
182
183#[cfg(test)]
184mod tests {
185    use super::*;
186    use crate::ring::rq::Rq;
187
188    const TEST_M: usize = 8;
189    const TEST_N: usize = 8;
190
191    // Test helpers
192    mod test_utils {
193        use super::*;
194
195        pub fn valid_witness(scheme: &AjtaiScheme) -> RqVector {
196            vec![Rq::new([scheme.witness_bound(); Rq::DEGREE]); TEST_N].into()
197        }
198
199        pub fn random_valid_witness() -> RqVector {
200            let mut rng = rand::rng();
201            RqVector::random_ternary(&mut rng, TEST_N)
202        }
203
204        pub fn setup_scheme() -> AjtaiScheme {
205            let mut rng = rand::rng();
206            let random_matrix = RqMatrix::random(&mut rng, TEST_M, TEST_N);
207            AjtaiScheme::new(Zq::ONE, Zq::ONE, random_matrix).unwrap()
208        }
209    }
210
211    #[test]
212    fn rejects_invalid_parameters() {
213        assert!(AjtaiScheme::new(
214            Zq::ONE,
215            Zq::ZERO,
216            RqMatrix::new(vec![RqVector::new(vec![Rq::zero()])])
217        )
218        .is_err());
219        let _ = test_utils::setup_scheme(); // Will panic if setup fails
220    }
221
222    #[test]
223    fn initializes_with_correct_bounds() {
224        let scheme = test_utils::setup_scheme();
225        assert_eq!(scheme.witness_bound(), Zq::ONE);
226    }
227
228    #[test]
229    fn completes_commitment_cycle() {
230        let scheme = test_utils::setup_scheme();
231        let witness = test_utils::valid_witness(&scheme);
232
233        let commitment = scheme.commit(&witness).unwrap();
234        assert!(scheme.verify(&commitment, &witness).is_ok());
235
236        let mut bad_opening = witness.clone();
237        let mut rng = rand::rng();
238        bad_opening[0] = Rq::random(&mut rng);
239        assert!(scheme.verify(&commitment, &bad_opening).is_err());
240    }
241
242    #[test]
243    fn maintains_security_properties() {
244        let scheme = test_utils::setup_scheme();
245
246        // Use random witnesses to ensure they're different
247        let witness1 = test_utils::random_valid_witness();
248        let witness2 = test_utils::random_valid_witness();
249
250        // Ensure the witnesses are actually different
251        assert_ne!(witness1, witness2, "Test requires different witnesses");
252
253        let c1 = scheme.commit(&witness1).unwrap();
254        let c2 = scheme.commit(&witness2).unwrap();
255        assert_ne!(
256            c1, c2,
257            "Different witnesses should produce different commitments"
258        );
259    }
260
261    #[test]
262    fn handles_edge_cases() {
263        let scheme = test_utils::setup_scheme();
264        let zero_witness = RqVector::zero(TEST_N);
265
266        assert!(scheme.commit(&zero_witness).is_ok());
267        assert!(scheme.commit(&test_utils::valid_witness(&scheme)).is_ok());
268    }
269
270    #[test]
271    fn stress_test() {
272        let scheme = test_utils::setup_scheme();
273
274        (0..100).for_each(|_| {
275            let witness = test_utils::valid_witness(&scheme);
276            let commitment = scheme.commit(&witness).unwrap();
277            assert!(scheme.verify(&commitment, &witness).is_ok());
278        });
279    }
280}
labrador/commitments/ajtai_commitment.rs

labrador/commitments/
ajtai_commitment.rs
