gsw_rs/
bootstrap.rs

1//! Bootstrapping for GSW FHE.
2//!
3//! Bootstrapping refreshes a noisy ciphertext by homomorphically evaluating
4//! the decryption circuit. This requires an evaluation key containing
5//! encryptions of the secret key bits under the same secret key (circular security).
6
7use rand::Rng;
8
9use crate::gadget::{bit_decomp, flatten_matrix, powers_of_2};
10use crate::gsw::{encrypt, homomorphic_add, Ciphertext, GswPublicKey, GswSecretKey};
11use crate::modular::mod_q;
12use crate::params::Params;
13
14/// Evaluation key: encryption of each bit of the secret key.
15#[derive(Clone, Debug)]
16pub struct EvaluationKey {
17    pub encryptions: Vec<Ciphertext>,
18    #[allow(dead_code)]
19    params: Params,
20}
21
22/// Generate the evaluation key for bootstrapping.
23pub fn gen_evaluation_key<R: Rng>(
24    rng: &mut R,
25    sk: &GswSecretKey,
26    pk: &GswPublicKey,
27) -> EvaluationKey {
28    let params = sk.params();
29    let bits = bit_decomp(&sk.s, params);
30
31    let encryptions: Vec<Ciphertext> = bits
32        .iter()
33        .map(|&b| encrypt(rng, pk, b as u8))
34        .collect();
35
36    EvaluationKey {
37        encryptions,
38        params: params.clone(),
39    }
40}
41
42/// Homomorphic linear combination: compute Enc(sum of c_i * x_i) from Enc(x_i).
43fn homomorphic_linear_fixed(
44    params: &Params,
45    cts: &[Ciphertext],
46    coefficients: &[u64],
47) -> Ciphertext {
48    assert_eq!(cts.len(), coefficients.len());
49    let n = params.n_expanded;
50    let q = params.q;
51
52    let mut result = None;
53
54    for (ct, &coeff) in cts.iter().zip(coefficients.iter()) {
55        if coeff == 0 {
56            continue;
57        }
58
59        let mut scaled = vec![vec![0u64; n]; n];
60        for i in 0..n {
61            for j in 0..n {
62                scaled[i][j] = mod_q((ct[i][j] as i64) * (coeff as i64), q);
63            }
64        }
65        let scaled_flat = flatten_matrix(&scaled, params);
66
67        result = Some(match result {
68            None => scaled_flat,
69            Some(acc) => homomorphic_add(params, &acc, &scaled_flat),
70        });
71    }
72
73    result.unwrap_or_else(|| vec![vec![0u64; n]; n])
74}
75
76/// Compute the decryption linear part in the clear (for verification).
77/// Matches decrypt: C[l-1] · v
78pub fn decrypt_linear_part_clear(sk: &GswSecretKey, ct: &Ciphertext) -> u64 {
79    let params = sk.params();
80    let q = params.q;
81    let l = params.l;
82    let n_expanded = params.n_expanded;
83    let row_idx = l - 1;
84
85    let v = powers_of_2(&sk.s, params);
86    let mut dot: i64 = 0;
87    for j in 0..n_expanded {
88        dot += (ct[row_idx][j] as i64) * (v[j] as i64);
89    }
90    mod_q(dot, q)
91}
92
93/// Bootstrap a noisy ciphertext to reduce its noise.
94/// Homomorphically computes C[l-1] · v where v = PowersOf2(s).
95pub fn bootstrap(
96    params: &Params,
97    noisy_ct: &Ciphertext,
98    ek: &EvaluationKey,
99) -> Ciphertext {
100    let l = params.l;
101    let n_expanded = params.n_expanded;
102    let row_idx = l - 1;
103    let q = params.q;
104
105    let mut coefficients = vec![0u64; n_expanded];
106    let c_row = &noisy_ct[row_idx];
107
108    for i in 0..n_expanded {
109        let block = i / l;
110        let k = i % l;
111        let mut coef: i64 = 0;
112        for j_bit in 0..l {
113            let j = block * l + j_bit;
114            let term = mod_q(
115                (c_row[j] as i64) * ((1i64 << (k + j_bit)) as i64),
116                q,
117            ) as i64;
118            coef = mod_q(coef + term, q) as i64;
119        }
120        coefficients[i] = mod_q(coef, q) as u64;
121    }
122
123    homomorphic_linear_fixed(params, &ek.encryptions, &coefficients)
124}
gsw_rs/bootstrap.rs

gsw_rs/
bootstrap.rs
