lattice_commitments/
commitment.rs

1use std::collections::HashMap;
2use std::marker::PhantomData;
3
4use rand::Rng;
5use ring_math::Matrix2D;
6use ring_math::Polynomial;
7use ring_math::PolynomialRingElement;
8use ring_math::Vector;
9use scalarff::scalar_ring;
10use scalarff::BigUint;
11use scalarff::FieldElement;
12
13/// Instance of a vector commitment scheme. Contains functions
14/// for committing to a vector and verifying the commitment.
15#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
16#[derive(Clone, Debug)]
17pub struct Vcs<T: PolynomialRingElement> {
18    _phantom: PhantomData<T>,
19    pub k: usize,     // Width (over Rq) of the commitment matrices
20    pub n: usize,     // Height (over Rq) of the commitment matrix A_1
21    pub l: usize,     // Dimension (over Rq) of the message space
22    pub beta: usize,  // infinite norm bound for prover randomness vector
23    pub kappa: usize, // l1 norm bound for challenge vectors
24    pub theta: f64,   // standard deviation in discrete gaussian distribution
25    pub N: usize,     // degree of the ring modulus
26}
27
28fn f64_to_u64(v: f64) -> u64 {
29    let z = v.ceil() as u64;
30    z
31}
32
33scalar_ring!(BetaRing, 2, "beta_bound_ring");
34
35impl<T: PolynomialRingElement> Vcs<T> {
36    /// Construct a new vector commitment scheme instance.
37    pub fn new(polynomial_degree: usize) -> Self {
38        // requirements
39        // n < k
40        // k > n + l
41        let kappa: u32 = 36;
42        let beta: u32 = 1;
43        let k: u32 = 3;
44        let n: u32 = 1;
45        let l: u32 = 1;
46        if kappa > polynomial_degree as u32 {
47            panic!("kappa must be less than the polynomial degree otherwise challenge vector does not exist");
48        }
49        Vcs {
50            N: polynomial_degree,
51            _phantom: PhantomData,
52            k: usize::try_from(k).unwrap(),
53            n: usize::try_from(n).unwrap(),
54            l: usize::try_from(l).unwrap(),
55            beta: usize::try_from(beta).unwrap(),
56            kappa: usize::try_from(kappa).unwrap(),
57            // theta: 33792000,
58            theta: 11.0 * f64::from(kappa * beta) * f64::sqrt(f64::from(k) * 64.0),
59        }
60    }
61
62    /// Sample a challenge vector with a specified l_1 and l_infinite norm
63    ///
64    /// l_inf should be 1 and l1 should be kappa
65    pub fn sample_challenge_vector(&self) -> T {
66        // generate random values in range 0..N
67        // if duplicate value returned discard?
68        let mut existing: HashMap<usize, bool> = HashMap::new();
69        let mut rng = rand::thread_rng();
70        while existing.len() < self.kappa {
71            let degree = rng.gen_range(0..self.N);
72            if existing.contains_key(&degree) {
73                continue;
74            }
75            existing.insert(degree, true);
76        }
77        let mut poly = T::zero().polynomial().clone();
78        for (degree, _) in existing.iter() {
79            poly.term(&T::F::one(), *degree);
80        }
81        T::from(poly)
82    }
83
84    /// Generate a proof that the user knows the opening value of a commitment.
85    ///
86    /// Similar to proving knowledge of a hash pre-image.
87    #[cfg(feature = "zk")]
88    pub fn prove_opening(&self, alpha: Matrix2D<T>, r: Vector<T>) -> (Vector<T>, Vector<T>, T) {
89        // sample a y using a discrete gaussian distribution
90        let y = Vector::from_vec(
91            vec![T::zero(); self.k]
92                .iter()
93                .map(|_| {
94                    T::from(u64::from(discrete_gaussian::sample_vartime(
95                        self.theta,
96                        &mut rand::thread_rng(),
97                    )))
98                })
99                .collect::<Vec<_>>(),
100        );
101        let (alpha_1, _alpha_2) = self.decompose_alpha(alpha);
102        let t = alpha_1.clone() * y.clone();
103
104        // challenge vector sampled from verifier randomness
105        let d = self.sample_challenge_vector();
106
107        let z = y + r * d.clone();
108
109        (t, z, d)
110    }
111
112    /// Verify a proof that a user knows the opening value of a commitment.
113    #[cfg(feature = "zk")]
114    pub fn verify_opening_proof(
115        &self,
116        t: Vector<T>,
117        d: T,
118        z: Vector<T>,
119        cm: Vector<T>,
120        alpha: Matrix2D<T>,
121    ) -> bool {
122        // check that the l2_norm for each element in z is <= 2 * theta * sqrt(N)
123        // check that A_1 * z = t + d * c_1
124
125        for v in z.iter() {
126            if v.norm_l2() > BigUint::from(f64_to_u64(2.0 * self.theta * 8.0)) {
127                return false;
128            }
129        }
130        if d.norm_l1() != BigUint::from(u64::try_from(self.kappa).unwrap()) {
131            return false;
132        }
133        if d.norm_max() != T::one().to_biguint() {
134            return false;
135        }
136
137        let (alpha_1, _alpha_2) = self.decompose_alpha(alpha);
138        let (cm_1, _cm_2) = self.decompose_cm(cm);
139        let lhs = alpha_1 * z;
140        let rhs = t + cm_1 * d;
141
142        lhs == rhs
143    }
144
145    /// Commit to a value `x`
146    ///
147    /// Returns the public parameters alpha, the commitment vector, and the secret r
148    pub fn commit<R: rand::Rng>(
149        &self,
150        x: &Vector<T>,
151        rng: &mut R,
152    ) -> (Matrix2D<T>, Vector<T>, Vector<T>) {
153        assert_eq!(self.l, x.len(), "invalid message length");
154
155        // the short integer polynomial
156        let r = Vector::from_vec(
157            vec![T::zero(); self.k]
158                .iter()
159                .map(|_| Self::sample_beta(rng))
160                .collect::<Vec<_>>(),
161        );
162
163        #[cfg(debug_assertions)]
164        {
165            // check the l_inf norm of the r
166            for v in r.iter() {
167                assert!(v.norm_max() <= BetaRing::prime());
168            }
169        }
170
171        let (alpha_1, alpha_2) = self.public_params();
172        let alpha = alpha_1.compose_vertical(alpha_2.clone());
173
174        // matrix vector multiplication
175        let inter1 = alpha.clone() * r.clone();
176        let inter2 = Vector::from_vec([vec![T::zero(); self.n], x.to_vec()].concat());
177        let commitment = inter2.clone() + inter1.clone();
178
179        (alpha, commitment, r)
180    }
181
182    /// Open a previously created commitment
183    /// commitment: the commitment vector being verified
184    /// alpha_1: random public parameter selected during commitment
185    /// x: the message that was committed to
186    /// r: a polynomial with l2 norm less than 4*theta*sqrt(N)
187    ///
188    /// Solving for r without previous knowledge should involve solving
189    /// the modular SIS problem (hard).
190    pub fn open(
191        &self,
192        commitment: &Vector<T>,
193        alpha: &Matrix2D<T>,
194        x: &Vector<T>,
195        r: &Vector<T>,
196    ) -> bool {
197        for v in r.iter() {
198            if v.norm_l2() > BigUint::from(f64_to_u64(4.0 * self.theta * 8.0)) {
199                return false;
200            }
201        }
202        let padded_x = Vector::from_vec([vec![T::zero(); self.n], x.to_vec()].concat());
203        let c = alpha.clone() * r.clone() + padded_x.clone();
204        c == *commitment
205    }
206
207    /// Generate random public params for use in the scheme
208    pub fn public_params(&self) -> (Matrix2D<T>, Matrix2D<T>) {
209        let alpha_1_prime =
210            Matrix2D::sample_uniform(self.n, self.k - self.n, &mut rand::thread_rng());
211        let alpha_2_prime =
212            Matrix2D::sample_uniform(self.l, self.k - self.n - self.l, &mut rand::thread_rng());
213        let alpha_1 = Matrix2D::identity(self.n).compose_horizontal(alpha_1_prime);
214        let alpha_2 = Matrix2D::zero(self.l, self.n)
215            .compose_horizontal(Matrix2D::identity(self.l))
216            .compose_horizontal(alpha_2_prime);
217        (alpha_1, alpha_2)
218    }
219
220    /// Decompose an alpha matrix into A_1 and A_2
221    pub fn decompose_alpha(&self, alpha: Matrix2D<T>) -> (Matrix2D<T>, Matrix2D<T>) {
222        alpha.split_vertical(self.n, self.l)
223    }
224
225    /// Decompose a commitment to c_1 and c_2
226    pub fn decompose_cm(&self, cm: Vector<T>) -> (Vector<T>, Vector<T>) {
227        let v = cm.0.clone();
228        (Vector(v[..self.n].to_vec()), Vector(v[self.n..].to_vec()))
229    }
230
231    /// Sample an element in S_β
232    fn sample_beta<R: rand::Rng>(rng: &mut R) -> T {
233        // maybe put this sampling in the polynomial implementation?
234        T::from_polynomial(Polynomial {
235            coefficients: T::zero()
236                .coef()
237                .iter()
238                .map(|_| BetaRing::sample_uniform(rng).to_biguint())
239                .map(|v| T::F::from_biguint(&v))
240                .collect::<Vec<_>>(),
241        })
242    }
243
244    /// infinite norm bound for generating S_β elements
245    pub fn beta_bound() -> BigUint {
246        BetaRing::prime()
247    }
248}
lattice_commitments/commitment.rs

lattice_commitments/
commitment.rs
