gsw_rs/
lwe.rs

1//! LWE (Learning With Errors) primitives.
2
3use rand::Rng;
4
5use crate::modular::mod_q;
6use crate::params::Params;
7
8/// Secret key: vector t in Z_q^n. Stored as (1, -t) for GSW compatibility.
9#[derive(Clone, Debug)]
10pub struct SecretKey {
11    /// Full secret vector s = (1, -t_1, ..., -t_n) in Z_q^{n+1}
12    pub s: Vec<u64>,
13    params: Params,
14}
15
16impl SecretKey {
17    pub fn params(&self) -> &Params {
18        &self.params
19    }
20}
21
22/// Public key: LWE matrix A where b = A*s + e (approximately).
23/// Stored as matrix of shape (m, n+1) with first column being b.
24#[derive(Clone, Debug)]
25pub struct PublicKey {
26    /// Matrix A where each row is (b_i, a_i1, ..., a_in)
27    pub a: Vec<Vec<u64>>,
28    params: Params,
29}
30
31impl PublicKey {
32    pub fn params(&self) -> &Params {
33        &self.params
34    }
35}
36
37/// Generate a random value in Z_q.
38fn rand_zq<R: Rng>(rng: &mut R, q: u64) -> u64 {
39    rng.gen_range(0..q)
40}
41
42/// Generate a small error in [-B, B] for LWE.
43fn sample_error<R: Rng>(rng: &mut R, bound: i64) -> i64 {
44    if bound <= 0 {
45        return 0;
46    }
47    rng.gen_range(-bound..=bound)
48}
49
50/// Generate secret key: random t in Z_q^n, return s = (1, -t).
51pub fn keygen<R: Rng>(rng: &mut R, params: &Params) -> (SecretKey, PublicKey) {
52    let n = params.n;
53    let m = params.m;
54    let q = params.q;
55    let bound = params.error_bound;
56
57    // Secret vector t in Z_q^n
58    let t: Vec<u64> = (0..n).map(|_| rand_zq(rng, q)).collect();
59
60    // s = (1, -t_1, ..., -t_n)
61    let mut s = vec![1u64];
62    for &ti in &t {
63        s.push(mod_q(-(ti as i64), q));
64    }
65
66    // Public key: A = [b | B] where b = B*t + e
67    let b_mat: Vec<Vec<u64>> = (0..m)
68        .map(|_| (0..n).map(|_| rand_zq(rng, q)).collect())
69        .collect();
70
71    let e: Vec<i64> = (0..m).map(|_| sample_error(rng, bound)).collect();
72
73    let mut b = vec![0u64; m];
74    for i in 0..m {
75        let mut dot: i64 = 0;
76        for j in 0..n {
77            dot += b_mat[i][j] as i64 * t[j] as i64;
78        }
79        b[i] = mod_q(dot + e[i], q);
80    }
81
82    let mut a = vec![vec![0u64; n + 1]; m];
83    for i in 0..m {
84        a[i][0] = b[i];
85        for j in 0..n {
86            a[i][j + 1] = b_mat[i][j];
87        }
88    }
89
90    (
91        SecretKey {
92            s: s.clone(),
93            params: params.clone(),
94        },
95        PublicKey {
96            a,
97            params: params.clone(),
98        },
99    )
100}
gsw_rs/lwe.rs

gsw_rs/
lwe.rs
