he_ring/bfv/
bootstrap.rs

1
2use feanor_math::algorithms::int_factor::is_prime_power;
3use feanor_math::homomorphism::*;
4use feanor_math::integer::{int_cast, IntegerRingStore};
5use feanor_math::ring::*;
6use feanor_math::rings::zn::ZnRingStore;
7
8use crate::cyclotomic::CyclotomicRingStore;
9use crate::lintransform::matmul::MatmulTransform;
10use crate::digitextract::*;
11use crate::lintransform::pow2;
12use crate::lintransform::composite;
13
14use super::*;
15
16#[derive(Clone, Debug)]
17pub struct ThinBootstrapParams<Params: BFVCiphertextParams> {
18    pub scheme_params: Params,
19    pub v: usize,
20    pub t: i64
21}
22
23///
24/// Precomputed data required to perform BFV bootstrapping.
25/// 
26/// The standard way to create this data is to use [`ThinBootstrapParams::build_pow2()`]
27/// or [`ThinBootstrapParams::build_odd()`], but note that this computation is very expensive.
28/// 
29pub struct ThinBootstrapData<Params: BFVCiphertextParams> {
30    digit_extract: DigitExtract,
31    slots_to_coeffs_thin: PlaintextCircuit<<PlaintextRing<Params> as RingStore>::Type>,
32    coeffs_to_slots_thin: PlaintextCircuit<<PlaintextRing<Params> as RingStore>::Type>,
33    plaintext_ring_hierarchy: Vec<PlaintextRing<Params>>
34}
35
36impl<Params: BFVCiphertextParams> ThinBootstrapParams<Params>
37    where NumberRing<Params>: Clone
38{
39    pub fn build_pow2<const LOG: bool>(&self) -> ThinBootstrapData<Params> {
40        let log2_n = ZZ.abs_log2_ceil(&(self.scheme_params.number_ring().n() as i64)).unwrap();
41        assert_eq!(self.scheme_params.number_ring().n(), 1 << log2_n);
42
43        let (p, r) = is_prime_power(&ZZ, &self.t).unwrap();
44        let v = self.v;
45        let e = r + v;
46        if LOG {
47            println!("Setting up bootstrapping for plaintext modulus p^r = {}^{} = {} within the cyclotomic ring Q[X]/(Phi_{})", p, r, self.t, <_ as HECyclotomicNumberRing>::n(&self.scheme_params.number_ring()));
48            println!("Choosing e = r + v = {} + {}", r, v);
49        }
50
51        let plaintext_ring = self.scheme_params.create_plaintext_ring(ZZ.pow(p, e));
52        let original_plaintext_ring = self.scheme_params.create_plaintext_ring(ZZ.pow(p, r));
53
54        let digit_extract = DigitExtract::new_default(p, e, r);
55
56        let hypercube = HypercubeStructure::halevi_shoup_hypercube(CyclotomicGaloisGroup::new(plaintext_ring.n() as u64), p);
57        let H = HypercubeIsomorphism::new::<LOG>(&plaintext_ring, hypercube);
58        let original_H = H.change_modulus(&original_plaintext_ring);
59        let slots_to_coeffs = log_time::<_, _, LOG, _>("Creating Slots-to-Coeffs transform", |[]| MatmulTransform::to_circuit_many(pow2::slots_to_coeffs_thin(&original_H), &original_H));
60        let coeffs_to_slots = log_time::<_, _, LOG, _>("Creating Coeffs-to-Slots transform", |[]| pow2::coeffs_to_slots_thin(&H));
61        let plaintext_ring_hierarchy = ((r + 1)..=e).map(|k| self.scheme_params.create_plaintext_ring(ZZ.pow(p, k))).collect();
62
63        return ThinBootstrapData {
64            digit_extract,
65            slots_to_coeffs_thin: slots_to_coeffs,
66            coeffs_to_slots_thin: coeffs_to_slots,
67            plaintext_ring_hierarchy: plaintext_ring_hierarchy
68        };
69    }
70
71    pub fn build_odd<const LOG: bool>(&self) -> ThinBootstrapData<Params> {
72        assert!(self.scheme_params.number_ring().n() % 2 != 0);
73
74        let (p, r) = is_prime_power(&ZZ, &self.t).unwrap();
75        let v = self.v;
76        let e = r + v;
77        if LOG {
78            println!("Setting up bootstrapping for plaintext modulus p^r = {}^{} = {} within the cyclotomic ring Q[X]/(Phi_{})", p, r, self.t, self.scheme_params.number_ring().n());
79            println!("Choosing e = r + v = {} + {}", r, v);
80        }
81
82        let plaintext_ring = self.scheme_params.create_plaintext_ring(ZZ.pow(p, e));
83        let original_plaintext_ring = self.scheme_params.create_plaintext_ring(ZZ.pow(p, r));
84
85        let digit_extract = if p == 2 && e <= 23 {
86            DigitExtract::new_precomputed_p_is_2(p, e, r)
87        } else {
88            DigitExtract::new_default(p, e, r)
89        };
90
91        let hypercube = HypercubeStructure::halevi_shoup_hypercube(CyclotomicGaloisGroup::new(plaintext_ring.n() as u64), p);
92        let H = HypercubeIsomorphism::new::<LOG>(&plaintext_ring, hypercube);
93        let original_H = H.change_modulus(&original_plaintext_ring);
94        let slots_to_coeffs = log_time::<_, _, LOG, _>("Creating Slots-to-Coeffs transform", |[]| MatmulTransform::to_circuit_many(composite::slots_to_powcoeffs_thin(&original_H), &original_H));
95        let coeffs_to_slots = log_time::<_, _, LOG, _>("Creating Coeffs-to-Slots transform", |[]| MatmulTransform::to_circuit_many(composite::powcoeffs_to_slots_thin(&H), &H));
96        let plaintext_ring_hierarchy = ((r + 1)..=e).map(|k| self.scheme_params.create_plaintext_ring(ZZ.pow(p, k))).collect();
97
98        return ThinBootstrapData {
99            digit_extract,
100            slots_to_coeffs_thin: slots_to_coeffs,
101            coeffs_to_slots_thin: coeffs_to_slots,
102            plaintext_ring_hierarchy: plaintext_ring_hierarchy
103        };
104    }
105}
106
107impl<Params: BFVCiphertextParams> ThinBootstrapData<Params> {
108
109    fn r(&self) -> usize {
110        self.digit_extract.e() - self.digit_extract.v()
111    }
112
113    fn e(&self) -> usize {
114        self.digit_extract.e()
115    }
116
117    fn v(&self) -> usize {
118        self.digit_extract.v()
119    }
120
121    fn p(&self) -> i64 {
122        self.digit_extract.p()
123    }
124
125    pub fn required_galois_keys(&self, P: &PlaintextRing<Params>) -> Vec<CyclotomicGaloisGroupEl> {
126        let mut result = Vec::new();
127        result.extend(self.slots_to_coeffs_thin.required_galois_keys(&P.galois_group()).into_iter());
128        result.extend(self.coeffs_to_slots_thin.required_galois_keys(&P.galois_group()).into_iter());
129        result.sort_by_key(|g| P.galois_group().representative(*g));
130        result.dedup_by(|g, s| P.galois_group().eq_el(*g, *s));
131        return result;
132    }
133
134    #[instrument(skip_all)]
135    pub fn bootstrap_thin<'a, const LOG: bool>(
136        &self,
137        C: &CiphertextRing<Params>, 
138        Cmul: &CiphertextRing<Params>, 
139        P_base: &PlaintextRing<Params>,
140        ct: Ciphertext<Params>,
141        rk: &RelinKey<'a, Params>,
142        gk: &[(CyclotomicGaloisGroupEl, KeySwitchKey<'a, Params>)],
143        debug_sk: Option<&SecretKey<Params>>
144    ) -> Ciphertext<Params>
145        where Params: 'a
146    {
147        assert!(LOG || debug_sk.is_none());
148        assert_eq!(ZZ.pow(self.p(), self.r()), *P_base.base_ring().modulus());
149        if LOG {
150            println!("Starting Bootstrapping")
151        }
152        if let Some(sk) = debug_sk {
153            Params::dec_println_slots(P_base, C, &ct, sk);
154        }
155
156        let P_main = self.plaintext_ring_hierarchy.last().unwrap();
157        debug_assert_eq!(ZZ.pow(self.p(), self.e()), *P_main.base_ring().modulus());
158
159        let values_in_coefficients = log_time::<_, _, LOG, _>("1. Computing Slots-to-Coeffs transform", |[key_switches]| {
160            let result = self.slots_to_coeffs_thin.evaluate_bfv::<Params>(P_base, C, None, std::slice::from_ref(&ct), None, gk, key_switches);
161            assert_eq!(1, result.len());
162            return result.into_iter().next().unwrap();
163        });
164        if let Some(sk) = debug_sk {
165            Params::dec_println(P_base, C, &values_in_coefficients, sk);
166        }
167
168        let noisy_decryption = log_time::<_, _, LOG, _>("2. Computing noisy decryption c0 + c1 * s", |[]| {
169            let (c0, c1) = Params::mod_switch_to_plaintext(P_main, C, values_in_coefficients);
170            let enc_sk = Params::enc_sk(P_main, C);
171            return Params::hom_add_plain(P_main, C, &c0, Params::hom_mul_plain(P_main, C, &c1, enc_sk));
172        });
173        if let Some(sk) = debug_sk {
174            Params::dec_println(P_main, C, &noisy_decryption, sk);
175        }
176
177        let noisy_decryption_in_slots = log_time::<_, _, LOG, _>("3. Computing Coeffs-to-Slots transform", |[key_switches]| {
178            let result = self.coeffs_to_slots_thin.evaluate_bfv::<Params>(P_main, C, None, std::slice::from_ref(&noisy_decryption), None, gk, key_switches);
179            assert_eq!(1, result.len());
180            return result.into_iter().next().unwrap();
181        });
182        if let Some(sk) = debug_sk {
183            Params::dec_println_slots(P_main, C, &noisy_decryption_in_slots, sk);
184        }
185
186        if LOG {
187            println!("4. Performing digit extraction");
188        }
189        let rounding_divisor_half = P_main.base_ring().coerce(&ZZbig, ZZbig.rounded_div(ZZbig.pow(int_cast(self.p(), ZZbig, ZZ), self.v()), &ZZbig.int_hom().map(2)));
190        let digit_extraction_input = Params::hom_add_plain(P_main, C, &P_main.inclusion().map(rounding_divisor_half), noisy_decryption_in_slots);
191        let result = self.digit_extract.evaluate_bfv::<Params>(P_base, &self.plaintext_ring_hierarchy, C, Cmul, digit_extraction_input, rk).0;
192
193        return result;
194    }
195}
196
197impl DigitExtract {
198    
199    ///
200    /// Evaluates the digit extraction function on a BFV-encrypted input.
201    /// 
202    /// For details on how the digit extraction function looks like, see
203    /// [`DigitExtract`] and [`DigitExtract::evaluate_generic()`].
204    /// 
205    pub fn evaluate_bfv<'a, Params: BFVCiphertextParams>(&self, 
206        P_base: &PlaintextRing<Params>, 
207        P: &[PlaintextRing<Params>], 
208        C: &CiphertextRing<Params>, 
209        Cmul: &CiphertextRing<Params>, 
210        input: Ciphertext<Params>, 
211        rk: &RelinKey<'a, Params>
212    ) -> (Ciphertext<Params>, Ciphertext<Params>) {
213        let (p, actual_r) = is_prime_power(StaticRing::<i64>::RING, P_base.base_ring().modulus()).unwrap();
214        assert_eq!(self.p(), p);
215        assert!(actual_r >= self.r());
216        for i in 0..(self.e() - self.r()) {
217            assert_eq!(ZZ.pow(self.p(), actual_r + i + 1), *P[i].base_ring().modulus());
218        }
219        let get_P = |exp: usize| if exp == self.r() {
220            P_base
221        } else {
222            &P[exp - self.r() - 1]
223        };
224        let result = self.evaluate_generic(
225            input,
226            |exp, params, circuit| circuit.evaluate_bfv::<Params>(
227                get_P(exp),
228                C,
229                Some(Cmul),
230                params,
231                Some(rk),
232                &[],
233                &mut 0
234            ),
235            |_, _, x| x
236        );
237        return result;
238    }
239}
240
241#[test]
242fn test_pow2_bfv_thin_bootstrapping_17() {
243    let mut rng = thread_rng();
244    
245    // 8 slots of rank 16
246    let params = Pow2BFV {
247        log2_q_min: 790,
248        log2_q_max: 800,
249        log2_N: 7,
250        ciphertext_allocator: DefaultCiphertextAllocator::default(),
251        negacyclic_ntt: PhantomData::<DefaultNegacyclicNTT>
252    };
253    let t = 17;
254    let digits = 3;
255    let bootstrap_params = ThinBootstrapParams {
256        scheme_params: params.clone(),
257        v: 2,
258        t: t
259    };
260    let bootstrapper = bootstrap_params.build_pow2::<true>();
261    
262    let P = params.create_plaintext_ring(t);
263    let (C, Cmul) = params.create_ciphertext_rings();
264    
265    let sk = Pow2BFV::gen_sk(&C, &mut rng, None);
266    let gk = bootstrapper.required_galois_keys(&P).into_iter().map(|g| (g, Pow2BFV::gen_gk(&C, &mut rng, &sk, g, digits))).collect::<Vec<_>>();
267    let rk = Pow2BFV::gen_rk(&C, &mut rng, &sk, digits);
268    
269    let m = P.int_hom().map(2);
270    let ct = Pow2BFV::enc_sym(&P, &C, &mut rng, &m, &sk);
271    let res_ct = bootstrapper.bootstrap_thin::<true>(
272        &C, 
273        &Cmul, 
274        &P, 
275        ct, 
276        &rk, 
277        &gk,
278        None
279    );
280
281    assert_el_eq!(P, P.int_hom().map(2), Pow2BFV::dec(&P, &C, res_ct, &sk));
282}
283
284#[test]
285fn test_pow2_bfv_thin_bootstrapping_23() {
286    let mut rng = thread_rng();
287    
288    // 4 slots of rank 32
289    let params = Pow2BFV {
290        log2_q_min: 790,
291        log2_q_max: 800,
292        log2_N: 7,
293        ciphertext_allocator: DefaultCiphertextAllocator::default(),
294        negacyclic_ntt: PhantomData::<DefaultNegacyclicNTT>
295    };
296    let t = 23;
297    let digits = 3;
298    let bootstrap_params = ThinBootstrapParams {
299        scheme_params: params.clone(),
300        v: 2,
301        t: t
302    };
303    let bootstrapper = bootstrap_params.build_pow2::<true>();
304    
305    let P = params.create_plaintext_ring(t);
306    let (C, Cmul) = params.create_ciphertext_rings();
307    
308    let sk = Pow2BFV::gen_sk(&C, &mut rng, None);
309    let gk = bootstrapper.required_galois_keys(&P).into_iter().map(|g| (g, Pow2BFV::gen_gk(&C, &mut rng, &sk, g, digits))).collect::<Vec<_>>();
310    let rk = Pow2BFV::gen_rk(&C, &mut rng, &sk, digits);
311    
312    let m = P.int_hom().map(2);
313    let ct = Pow2BFV::enc_sym(&P, &C, &mut rng, &m, &sk);
314    let res_ct = bootstrapper.bootstrap_thin::<true>(
315        &C, 
316        &Cmul, 
317        &P, 
318        ct, 
319        &rk, 
320        &gk,
321        None
322    );
323
324    assert_el_eq!(P, P.int_hom().map(2), Pow2BFV::dec(&P, &C, res_ct, &sk));
325}
326
327#[test]
328fn test_composite_bfv_thin_bootstrapping_2() {
329    // let (chrome_layer, _guard) = tracing_chrome::ChromeLayerBuilder::new().build();
330    // let filtered_chrome_layer = chrome_layer.with_filter(tracing_subscriber::filter::filter_fn(|metadata| !["small_basis_to_mult_basis", "mult_basis_to_small_basis", "small_basis_to_coeff_basis", "coeff_basis_to_small_basis"].contains(&metadata.name())));
331    // tracing_subscriber::registry().with(filtered_chrome_layer).init();
332    
333    let mut rng = thread_rng();
334    
335    let params = CompositeBFV {
336        log2_q_min: 660,
337        log2_q_max: 700,
338        n1: 31,
339        n2: 11,
340        ciphertext_allocator: DefaultCiphertextAllocator::default()
341    };
342    let t = 8;
343    let digits = 3;
344    let bootstrap_params = ThinBootstrapParams {
345        scheme_params: params.clone(),
346        v: 9,
347        t: t
348    };
349    let bootstrapper = bootstrap_params.build_odd::<true>();
350    
351    let P = params.create_plaintext_ring(t);
352    let (C, Cmul) = params.create_ciphertext_rings();
353    
354    let sk = CompositeBFV::gen_sk(&C, &mut rng, None);
355    let gk = bootstrapper.required_galois_keys(&P).into_iter().map(|g| (g, CompositeBFV::gen_gk(&C, &mut rng, &sk, g, digits))).collect::<Vec<_>>();
356    let rk = CompositeBFV::gen_rk(&C, &mut rng, &sk, digits);
357    
358    let m = P.int_hom().map(2);
359    let ct = CompositeBFV::enc_sym(&P, &C, &mut rng, &m, &sk);
360    let res_ct = bootstrapper.bootstrap_thin::<true>(
361        &C, 
362        &Cmul, 
363        &P, 
364        ct, 
365        &rk, 
366        &gk,
367        None
368    );
369
370    assert_el_eq!(P, P.int_hom().map(2), CompositeBFV::dec(&P, &C, res_ct, &sk));
371}
he_ring/bfv/bootstrap.rs

he_ring/bfv/
bootstrap.rs
