lettuce 0.1.3

Healthy lattice consructions in pure Rust.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203

mod nizk;
pub use nizk::*;

use std::sync::Arc;

use rand::SeedableRng;

use crate::*;

const SIGMA: f64 = 27000f64;

/// An implementation of [Baum et. al. commitments](https://eprint.iacr.org/2016/997.pdf). See
/// also:
/// [spec](https://github.com/chancehudson/lattices/blob/main/lettuce/src/commitments/bdlop/spec.pdf)
///
/// <div class="warning">The current implementation is not sound!</div>
///
/// The current implementation does not argue invertibility of
/// challenge elements. The sigma and dimension parameters
/// have also not be analyzed for security.
#[derive(Clone, Debug)]
pub struct BDLOP<const N: usize, E: FieldScalar> {
    pub a_1: Arc<Matrix<Polynomial<N, E>>>,
    pub a_2: Arc<Matrix<Polynomial<N, E>>>,
    pub c_1: Vector<Polynomial<N, E>>,
    pub c_2: Vector<Polynomial<N, E>>,
}

impl<const N: usize, E: FieldScalar> BDLOP<N, E> {
    /// Return a byte representation of the commitments.
    pub fn as_le_bytes(&self) -> impl Iterator<Item = u8> {
        self.c_1
            .iter()
            .flat_map(|v| v.as_le_bytes())
            .chain(self.c_2.iter().flat_map(|v| v.as_le_bytes()))
    }

    /// Given a message length determine the dimension of a commitment matrix.
    ///
    /// BDLOP commitments vertically compose an SIS commitment to 0 with an SIS commitment
    /// to a message vector. We need two lattice bases, A_1 and A_2.
    ///
    /// Pages 11 and 10 of https://eprint.iacr.org/2016/997.pdf
    fn dimension(msg_len: usize) -> (usize, usize) {
        // approx n*log(q) for the message length only
        // we want our message to be mixed with at least this many vectors of random elements
        //
        // we subtract msg_len because the A_2 matrix will provide an additional msg_len
        // vectors of mixing
        let a_1_height = msg_len;
        // the A_2 matrix always has height equal to the message length
        let width = a_1_height + msg_len;
        (a_1_height, width)
    }

    pub fn lattice_for<R: Rng>(
        msg_len: usize,
        rng: &mut R,
    ) -> (Arc<Matrix<Polynomial<N, E>>>, Arc<Matrix<Polynomial<N, E>>>) {
        let (a_1_height, width) = Self::dimension(msg_len);
        // the A_1 lattice base
        let a_1 = Matrix::identity(a_1_height).compose_horizontal(Matrix::random(
            a_1_height,
            width - a_1_height,
            rng,
        ));

        // the A_2 lattice base
        let a_2 = Matrix::zero(msg_len, a_1_height)
            .compose_horizontal(Matrix::identity(msg_len))
            .compose_horizontal(Matrix::random(msg_len, width - a_1_height - msg_len, rng));
        (Arc::new(a_1), Arc::new(a_2))
    }

    /// Generate a BDLOP commitment to a vector of scalar elements.
    ///
    /// Elements will be encoded into polynomials.
    pub fn commit<R: Rng>(
        val: Vector<Polynomial<N, E>>,
        lattice: &(Arc<Matrix<Polynomial<N, E>>>, Arc<Matrix<Polynomial<N, E>>>),
        rng: &mut R,
    ) -> (Self, Vector<Polynomial<N, E>>) {
        let (a_1, a_2) = lattice.clone();

        // the secret committing to the zero component
        let r = (0..a_1.width())
            .map(|_| {
                let mut p = Polynomial::default();
                for coef in p.coefs_mut() {
                    *coef = ternary_sample(rng);
                }
                p
            })
            .collect::<Vector<_>>();

        let c_1 = a_1.as_ref() * &r;
        let c_2 = (a_2.as_ref() * &r) + &val;

        (Self { a_1, a_2, c_1, c_2 }, r)
    }

    /// Attempt to open a commitment directly using the stored `r` value.
    /// First attempts to open c_1 to the zero vector. If this succeeds c_2 is opened to whatever
    /// value is committed.
    pub fn try_open(&self, r: &Vector<Polynomial<N, E>>) -> Result<Vector<Polynomial<N, E>>> {
        if self.a_1.as_ref() * r != self.c_1 {
            anyhow::bail!("Failed to open commitment, secret is incorrect");
        }
        Ok(&self.c_2 - self.a_2.as_ref() * &r)
    }

    /// Attempt to generate a non-interactive ZK argument of opening.
    ///
    /// Described on page 15 of <https://eprint.iacr.org/2016/997.pdf>
    pub fn try_open_zk<R: Rng>(
        &self,
        r: &Vector<Polynomial<N, E>>,
        rng: &mut R,
    ) -> Result<(
        Polynomial<N, E>,
        Vector<Polynomial<N, E>>,
        Vector<Polynomial<N, E>>,
    )> {
        if self.a_1.as_ref() * r != self.c_1 {
            anyhow::bail!("Failed to open commitment, secret is incorrect");
        }
        loop {
            let y = (0..self.a_1.width())
                .map(|_| Polynomial::sample_gaussian(SIGMA, rng))
                .collect::<Vector<_>>();
            let t = self.a_1.as_ref() * &y;
            let hash = blake3::hash(&t.iter().flat_map(|v| v.as_le_bytes()).collect::<Vec<u8>>());
            let mut csprng = rand_chacha::ChaCha20Rng::from_seed(hash.into());

            let d: Polynomial<N, E> = std::array::from_fn(|_| ternary_sample(&mut csprng)).into();
            let z = y.clone() + &(d.batch_mul(r.clone()));
            // TODO: rejection sampling
            // if p.norm_l2() >= 2.0 * sigma * (self.a_1.width() as f64).sqrt() {
            //     // reject and try again
            //     continue;
            // }
            return Ok((d, t, z));
        }
    }
}

impl<const N: usize, E: FieldScalar> Add<&Self> for BDLOP<N, E> {
    type Output = Self;
    fn add(mut self, rhs: &Self) -> Self::Output {
        self += rhs;
        self
    }
}

impl<const N: usize, E: FieldScalar> AddAssign<&Self> for BDLOP<N, E> {
    fn add_assign(&mut self, rhs: &Self) {
        assert!(
            self.a_1 == rhs.a_1 && self.a_2 == rhs.a_2,
            "BDLOP: refusing to add commitments on different lattices"
        );
        self.c_1 += &rhs.c_1;
        self.c_2 += &rhs.c_2;
    }
}

#[test]
fn bdlop_commit_var_dimension() -> Result<()> {
    type Field = MilliScalarMont;
    const RING_DEGREE: usize = 64;
    let rng = &mut rand::rng();
    // just make sure our dimensions match in matrix/vector ops
    for i in 1..10 {
        let lattice = BDLOP::<RING_DEGREE, Field>::lattice_for(i, rng);
        let (commitment, r) = BDLOP::commit(Vector::sample_uniform(i, rng), &lattice, rng);
        commitment
            .try_open(&r)
            .expect("failed to open BDLOP commitment");
        commitment
            .try_open(&(r.clone() + &r))
            .expect_err("should fail to open BDLOP commitment to bad r value");
    }
    Ok(())
}

#[test]
fn bdlop_open_zk() -> Result<()> {
    type Field = MilliScalarMont;
    const RING_DEGREE: usize = 128;
    let rng = &mut rand::rng();
    let msg_len = 1;
    let lattice = BDLOP::<RING_DEGREE, Field>::lattice_for(msg_len, rng);
    let msg = Vector::sample_uniform(msg_len, rng);

    let (c, r) = BDLOP::commit(msg, &lattice, rng);
    let (d, t, z) = c.try_open_zk(&r, rng)?;

    for p in &z {
        let max_l2 = 4.0 * SIGMA * (RING_DEGREE as f64).sqrt();
        assert!(p.norm_l2() < max_l2);
    }
    assert_eq!(c.a_1.as_ref() * &z, t + &(c.c_1 * d));
    Ok(())
}