poulpy/poulpy-core/src/glwe_packing.rs
poulpy-core/src/glwe_packing.rsRaw
1use std::collections::HashMap;
2
3use poulpy_hal::{
4 api::{
5 DFT, IDFTConsume, ScratchAvailable, TakeVecZnx, TakeVecZnxDft, VecZnxAddInplace, VecZnxAutomorphismInplace,
6 VecZnxBigAddSmallInplace, VecZnxBigAutomorphismInplace, VecZnxBigNormalize, VecZnxBigNormalizeTmpBytes,
7 VecZnxBigSubSmallBInplace, VecZnxCopy, VecZnxDftAllocBytes, VecZnxNegateInplace, VecZnxNormalizeInplace, VecZnxRotate,
8 VecZnxRotateInplace, VecZnxRshInplace, VecZnxSub, VecZnxSubABInplace, VmpApplyDftToDft, VmpApplyDftToDftAdd,
9 VmpApplyDftToDftTmpBytes,
10 },
11 layouts::{Backend, DataMut, DataRef, Module, Scratch},
12};
13
14use crate::{
15 GLWEOperations, TakeGLWECt,
16 layouts::{GLWECiphertext, Infos, prepared::GGLWEAutomorphismKeyPrepared},
17};
18
19/// [GLWEPacker] enables only the fly GLWE packing
20/// with constant memory of Log(N) ciphertexts.
21/// Main difference with usual GLWE packing is that
22/// the output is bit-reversed.
23pub struct GLWEPacker {
24 accumulators: Vec<Accumulator>,
25 log_batch: usize,
26 counter: usize,
27}
28
29/// [Accumulator] stores intermediate packing result.
30/// There are Log(N) such accumulators in a [GLWEPacker].
31struct Accumulator {
32 data: GLWECiphertext<Vec<u8>>,
33 value: bool, // Implicit flag for zero ciphertext
34 control: bool, // Can be combined with incoming value
35}
36
37impl Accumulator {
38 /// Allocates a new [Accumulator].
39 ///
40 /// #Arguments
41 ///
42 /// * `module`: static backend FFT tables.
43 /// * `basek`: base 2 logarithm of the GLWE ciphertext in memory digit representation.
44 /// * `k`: base 2 precision of the GLWE ciphertext precision over the Torus.
45 /// * `rank`: rank of the GLWE ciphertext.
46 pub fn alloc(n: usize, basek: usize, k: usize, rank: usize) -> Self {
47 Self {
48 data: GLWECiphertext::alloc(n, basek, k, rank),
49 value: false,
50 control: false,
51 }
52 }
53}
54
55impl GLWEPacker {
56 /// Instantiates a new [GLWEPacker].
57 ///
58 /// # Arguments
59 ///
60 /// * `module`: static backend FFT tables.
61 /// * `log_batch`: packs coefficients which are multiples of X^{N/2^log_batch}.
62 /// i.e. with `log_batch=0` only the constant coefficient is packed
63 /// and N GLWE ciphertext can be packed. With `log_batch=2` all coefficients
64 /// which are multiples of X^{N/4} are packed. Meaning that N/4 ciphertexts
65 /// can be packed.
66 /// * `basek`: base 2 logarithm of the GLWE ciphertext in memory digit representation.
67 /// * `k`: base 2 precision of the GLWE ciphertext precision over the Torus.
68 /// * `rank`: rank of the GLWE ciphertext.
69 pub fn new(n: usize, log_batch: usize, basek: usize, k: usize, rank: usize) -> Self {
70 let mut accumulators: Vec<Accumulator> = Vec::<Accumulator>::new();
71 let log_n: usize = (usize::BITS - (n - 1).leading_zeros()) as _;
72 (0..log_n - log_batch).for_each(|_| accumulators.push(Accumulator::alloc(n, basek, k, rank)));
73 Self {
74 accumulators,
75 log_batch,
76 counter: 0,
77 }
78 }
79
80 /// Implicit reset of the internal state (to be called before a new packing procedure).
81 fn reset(&mut self) {
82 for i in 0..self.accumulators.len() {
83 self.accumulators[i].value = false;
84 self.accumulators[i].control = false;
85 }
86 self.counter = 0;
87 }
88
89 /// Number of scratch space bytes required to call [Self::add].
90 pub fn scratch_space<B: Backend>(
91 module: &Module<B>,
92 basek: usize,
93 ct_k: usize,
94 k_ksk: usize,
95 digits: usize,
96 rank: usize,
97 ) -> usize
98 where
99 Module<B>: VecZnxDftAllocBytes + VmpApplyDftToDftTmpBytes + VecZnxBigNormalizeTmpBytes,
100 {
101 pack_core_scratch_space(module, basek, ct_k, k_ksk, digits, rank)
102 }
103
104 pub fn galois_elements<B: Backend>(module: &Module<B>) -> Vec<i64> {
105 GLWECiphertext::trace_galois_elements(module)
106 }
107
108 /// Adds a GLWE ciphertext to the [GLWEPacker].
109 /// #Arguments
110 ///
111 /// * `module`: static backend FFT tables.
112 /// * `res`: space to append fully packed ciphertext. Only when the number
113 /// of packed ciphertexts reaches N/2^log_batch is a result written.
114 /// * `a`: ciphertext to pack. Can optionally give None to pack a 0 ciphertext.
115 /// * `auto_keys`: a [HashMap] containing the [AutomorphismKeyExec]s.
116 /// * `scratch`: scratch space of size at least [Self::scratch_space].
117 pub fn add<DataA: DataRef, DataAK: DataRef, B: Backend>(
118 &mut self,
119 module: &Module<B>,
120 a: Option<&GLWECiphertext<DataA>>,
121 auto_keys: &HashMap<i64, GGLWEAutomorphismKeyPrepared<DataAK, B>>,
122 scratch: &mut Scratch<B>,
123 ) where
124 Module<B>: VecZnxDftAllocBytes
125 + VmpApplyDftToDftTmpBytes
126 + VecZnxBigNormalizeTmpBytes
127 + VmpApplyDftToDft<B>
128 + VmpApplyDftToDftAdd<B>
129 + DFT<B>
130 + IDFTConsume<B>
131 + VecZnxBigAddSmallInplace<B>
132 + VecZnxBigNormalize<B>
133 + VecZnxCopy
134 + VecZnxRotateInplace
135 + VecZnxSub
136 + VecZnxNegateInplace
137 + VecZnxRshInplace
138 + VecZnxAddInplace
139 + VecZnxNormalizeInplace<B>
140 + VecZnxSubABInplace
141 + VecZnxRotate
142 + VecZnxAutomorphismInplace
143 + VecZnxBigSubSmallBInplace<B>
144 + VecZnxBigAutomorphismInplace<B>,
145 Scratch<B>: TakeVecZnxDft<B> + ScratchAvailable + TakeVecZnx,
146 {
147 assert!(
148 self.counter < self.accumulators[0].data.n(),
149 "Packing limit of {} reached",
150 self.accumulators[0].data.n() >> self.log_batch
151 );
152
153 pack_core(
154 module,
155 a,
156 &mut self.accumulators,
157 self.log_batch,
158 auto_keys,
159 scratch,
160 );
161 self.counter += 1 << self.log_batch;
162 }
163
164 /// Flush result to`res`.
165 pub fn flush<Data: DataMut, B: Backend>(&mut self, module: &Module<B>, res: &mut GLWECiphertext<Data>)
166 where
167 Module<B>: VecZnxCopy,
168 {
169 assert!(self.counter == self.accumulators[0].data.n());
170 // Copy result GLWE into res GLWE
171 res.copy(
172 module,
173 &self.accumulators[module.log_n() - self.log_batch - 1].data,
174 );
175
176 self.reset();
177 }
178}
179
180fn pack_core_scratch_space<B: Backend>(
181 module: &Module<B>,
182 basek: usize,
183 ct_k: usize,
184 k_ksk: usize,
185 digits: usize,
186 rank: usize,
187) -> usize
188where
189 Module<B>: VecZnxDftAllocBytes + VmpApplyDftToDftTmpBytes + VecZnxBigNormalizeTmpBytes,
190{
191 combine_scratch_space(module, basek, ct_k, k_ksk, digits, rank)
192}
193
194fn pack_core<D: DataRef, DataAK: DataRef, B: Backend>(
195 module: &Module<B>,
196 a: Option<&GLWECiphertext<D>>,
197 accumulators: &mut [Accumulator],
198 i: usize,
199 auto_keys: &HashMap<i64, GGLWEAutomorphismKeyPrepared<DataAK, B>>,
200 scratch: &mut Scratch<B>,
201) where
202 Module<B>: VecZnxDftAllocBytes
203 + VmpApplyDftToDftTmpBytes
204 + VecZnxBigNormalizeTmpBytes
205 + VmpApplyDftToDft<B>
206 + VmpApplyDftToDftAdd<B>
207 + DFT<B>
208 + IDFTConsume<B>
209 + VecZnxBigAddSmallInplace<B>
210 + VecZnxBigNormalize<B>
211 + VecZnxCopy
212 + VecZnxRotateInplace
213 + VecZnxSub
214 + VecZnxNegateInplace
215 + VecZnxRshInplace
216 + VecZnxAddInplace
217 + VecZnxNormalizeInplace<B>
218 + VecZnxSubABInplace
219 + VecZnxRotate
220 + VecZnxAutomorphismInplace
221 + VecZnxBigSubSmallBInplace<B>
222 + VecZnxBigAutomorphismInplace<B>,
223 Scratch<B>: TakeVecZnxDft<B> + ScratchAvailable + TakeVecZnx,
224{
225 let log_n: usize = module.log_n();
226
227 if i == log_n {
228 return;
229 }
230
231 // Isolate the first accumulator
232 let (acc_prev, acc_next) = accumulators.split_at_mut(1);
233
234 // Control = true accumlator is free to overide
235 if !acc_prev[0].control {
236 let acc_mut_ref: &mut Accumulator = &mut acc_prev[0]; // from split_at_mut
237
238 // No previous value -> copies and sets flags accordingly
239 if let Some(a_ref) = a {
240 acc_mut_ref.data.copy(module, a_ref);
241 acc_mut_ref.value = true
242 } else {
243 acc_mut_ref.value = false
244 }
245 acc_mut_ref.control = true; // Able to be combined on next call
246 } else {
247 // Compresses acc_prev <- combine(acc_prev, a).
248 combine(module, &mut acc_prev[0], a, i, auto_keys, scratch);
249 acc_prev[0].control = false;
250
251 // Propagates to next accumulator
252 if acc_prev[0].value {
253 pack_core(
254 module,
255 Some(&acc_prev[0].data),
256 acc_next,
257 i + 1,
258 auto_keys,
259 scratch,
260 );
261 } else {
262 pack_core(
263 module,
264 None::<&GLWECiphertext<Vec<u8>>>,
265 acc_next,
266 i + 1,
267 auto_keys,
268 scratch,
269 );
270 }
271 }
272}
273
274fn combine_scratch_space<B: Backend>(
275 module: &Module<B>,
276 basek: usize,
277 ct_k: usize,
278 k_ksk: usize,
279 digits: usize,
280 rank: usize,
281) -> usize
282where
283 Module<B>: VecZnxDftAllocBytes + VmpApplyDftToDftTmpBytes + VecZnxBigNormalizeTmpBytes,
284{
285 GLWECiphertext::bytes_of(module.n(), basek, ct_k, rank)
286 + (GLWECiphertext::rsh_scratch_space(module.n())
287 | GLWECiphertext::automorphism_scratch_space(module, basek, ct_k, ct_k, k_ksk, digits, rank))
288}
289
290/// [combine] merges two ciphertexts together.
291fn combine<D: DataRef, DataAK: DataRef, B: Backend>(
292 module: &Module<B>,
293 acc: &mut Accumulator,
294 b: Option<&GLWECiphertext<D>>,
295 i: usize,
296 auto_keys: &HashMap<i64, GGLWEAutomorphismKeyPrepared<DataAK, B>>,
297 scratch: &mut Scratch<B>,
298) where
299 Module<B>: VecZnxDftAllocBytes
300 + VmpApplyDftToDftTmpBytes
301 + VecZnxBigNormalizeTmpBytes
302 + VmpApplyDftToDft<B>
303 + VmpApplyDftToDftAdd<B>
304 + DFT<B>
305 + IDFTConsume<B>
306 + VecZnxBigAddSmallInplace<B>
307 + VecZnxBigNormalize<B>
308 + VecZnxCopy
309 + VecZnxRotateInplace
310 + VecZnxSub
311 + VecZnxNegateInplace
312 + VecZnxRshInplace
313 + VecZnxAddInplace
314 + VecZnxNormalizeInplace<B>
315 + VecZnxSubABInplace
316 + VecZnxRotate
317 + VecZnxAutomorphismInplace
318 + VecZnxBigSubSmallBInplace<B>
319 + VecZnxBigAutomorphismInplace<B>,
320 Scratch<B>: TakeVecZnxDft<B> + ScratchAvailable + TakeVecZnx,
321{
322 let n: usize = acc.data.n();
323 let log_n: usize = (u64::BITS - (n - 1).leading_zeros()) as _;
324 let a: &mut GLWECiphertext<Vec<u8>> = &mut acc.data;
325 let basek: usize = a.basek();
326 let k: usize = a.k();
327 let rank: usize = a.rank();
328
329 let gal_el: i64 = if i == 0 {
330 -1
331 } else {
332 module.galois_element(1 << (i - 1))
333 };
334
335 let t: i64 = 1 << (log_n - i - 1);
336
337 // Goal is to evaluate: a = a + b*X^t + phi(a - b*X^t))
338 // We also use the identity: AUTO(a * X^t, g) = -X^t * AUTO(a, g)
339 // where t = 2^(log_n - i - 1) and g = 5^{2^(i - 1)}
340 // Different cases for wether a and/or b are zero.
341 //
342 // Implicite RSH without modulus switch, introduces extra I(X) * Q/2 on decryption.
343 // Necessary so that the scaling of the plaintext remains constant.
344 // It however is ok to do so here because coefficients are eventually
345 // either mapped to garbage or twice their value which vanishes I(X)
346 // since 2*(I(X) * Q/2) = I(X) * Q = 0 mod Q.
347 if acc.value {
348 if let Some(b) = b {
349 let (mut tmp_b, scratch_1) = scratch.take_glwe_ct(n, basek, k, rank);
350
351 // a = a * X^-t
352 a.rotate_inplace(module, -t);
353
354 // tmp_b = a * X^-t - b
355 tmp_b.sub(module, a, b);
356 tmp_b.rsh(module, 1);
357
358 // a = a * X^-t + b
359 a.add_inplace(module, b);
360 a.rsh(module, 1);
361
362 tmp_b.normalize_inplace(module, scratch_1);
363
364 // tmp_b = phi(a * X^-t - b)
365 if let Some(key) = auto_keys.get(&gal_el) {
366 tmp_b.automorphism_inplace(module, key, scratch_1);
367 } else {
368 panic!("auto_key[{}] not found", gal_el);
369 }
370
371 // a = a * X^-t + b - phi(a * X^-t - b)
372 a.sub_inplace_ab(module, &tmp_b);
373 a.normalize_inplace(module, scratch_1);
374
375 // a = a + b * X^t - phi(a * X^-t - b) * X^t
376 // = a + b * X^t - phi(a * X^-t - b) * - phi(X^t)
377 // = a + b * X^t + phi(a - b * X^t)
378 a.rotate_inplace(module, t);
379 } else {
380 a.rsh(module, 1);
381 // a = a + phi(a)
382 if let Some(key) = auto_keys.get(&gal_el) {
383 a.automorphism_add_inplace(module, key, scratch);
384 } else {
385 panic!("auto_key[{}] not found", gal_el);
386 }
387 }
388 } else if let Some(b) = b {
389 let (mut tmp_b, scratch_1) = scratch.take_glwe_ct(n, basek, k, rank);
390 tmp_b.rotate(module, 1 << (log_n - i - 1), b);
391 tmp_b.rsh(module, 1);
392
393 // a = (b* X^t - phi(b* X^t))
394 if let Some(key) = auto_keys.get(&gal_el) {
395 a.automorphism_sub_ba(module, &tmp_b, key, scratch_1);
396 } else {
397 panic!("auto_key[{}] not found", gal_el);
398 }
399
400 acc.value = true;
401 }
402}