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

labrador/commitments/
ajtai_commitment.rs
