poulpy/rlwe/src/gadget_product.rs
rlwe/src/gadget_product.rsRaw
1use crate::{ciphertext::Ciphertext, elem::ElemCommon, parameters::Parameters};
2use base2k::{
3 Module, VecZnx, VecZnxBig, VecZnxBigOps, VecZnxDft, VecZnxDftOps, VmpPMat, VmpPMatOps,
4};
5use std::cmp::min;
6
7pub fn gadget_product_core_tmp_bytes(
8 module: &Module,
9 log_base2k: usize,
10 res_log_q: usize,
11 in_log_q: usize,
12 gct_rows: usize,
13 gct_log_q: usize,
14) -> usize {
15 let gct_cols: usize = (gct_log_q + log_base2k - 1) / log_base2k;
16 let in_cols: usize = (in_log_q + log_base2k - 1) / log_base2k;
17 let out_cols: usize = (res_log_q + log_base2k - 1) / log_base2k;
18 module.vmp_apply_dft_to_dft_tmp_bytes(out_cols, in_cols, gct_rows, gct_cols)
19}
20
21impl Parameters {
22 pub fn gadget_product_tmp_bytes(
23 &self,
24 res_log_q: usize,
25 in_log_q: usize,
26 gct_rows: usize,
27 gct_log_q: usize,
28 ) -> usize {
29 gadget_product_core_tmp_bytes(
30 self.module(),
31 self.log_base2k(),
32 res_log_q,
33 in_log_q,
34 gct_rows,
35 gct_log_q,
36 )
37 }
38}
39
40pub fn gadget_product_core(
41 module: &Module,
42 res_dft_0: &mut VecZnxDft,
43 res_dft_1: &mut VecZnxDft,
44 a: &VecZnx,
45 b: &Ciphertext<VmpPMat>,
46 b_cols: usize,
47 tmp_bytes: &mut [u8],
48) {
49 assert!(b_cols <= b.cols());
50 module.vec_znx_dft(res_dft_1, a);
51 module.vmp_apply_dft_to_dft(res_dft_0, res_dft_1, b.at(0), tmp_bytes);
52 module.vmp_apply_dft_to_dft_inplace(res_dft_1, b.at(1), tmp_bytes);
53}
54
55pub fn gadget_product_big_tmp_bytes(
56 module: &Module,
57 c_cols: usize,
58 a_cols: usize,
59 b_rows: usize,
60 b_cols: usize,
61) -> usize {
62 return module.vmp_apply_dft_to_dft_tmp_bytes(c_cols, a_cols, b_rows, b_cols)
63 + 2 * module.bytes_of_vec_znx_dft(min(c_cols, a_cols));
64}
65
66/// Evaluates the gadget product: c.at(i) = IDFT(<DFT(a.at(i)), b.at(i)>)
67///
68/// # Arguments
69///
70/// * `module`: backend support for operations mod (X^N + 1).
71/// * `c`: a [Ciphertext<VecZnxBig>] with cols_c cols.
72/// * `a`: a [Ciphertext<VecZnx>] with cols_a cols.
73/// * `b`: a [Ciphertext<VmpPMat>] with at least min(cols_c, cols_a) rows.
74pub fn gadget_product_big(
75 module: &Module,
76 c: &mut Ciphertext<VecZnxBig>,
77 a: &Ciphertext<VecZnx>,
78 b: &Ciphertext<VmpPMat>,
79 tmp_bytes: &mut [u8],
80) {
81 let cols: usize = min(c.cols(), a.cols());
82
83 let (tmp_bytes_b1_dft, tmp_bytes) = tmp_bytes.split_at_mut(module.bytes_of_vec_znx_dft(cols));
84 let (tmp_bytes_res_dft, tmp_bytes) = tmp_bytes.split_at_mut(module.bytes_of_vec_znx_dft(cols));
85
86 let mut a1_dft: VecZnxDft = module.new_vec_znx_dft_from_bytes_borrow(cols, tmp_bytes_b1_dft);
87 let mut res_dft: VecZnxDft = module.new_vec_znx_dft_from_bytes_borrow(cols, tmp_bytes_res_dft);
88
89 // a1_dft = DFT(a[1])
90 module.vec_znx_dft(&mut a1_dft, a.at(1));
91
92 // c[i] = IDFT(DFT(a[1]) * b[i])
93 (0..2).for_each(|i| {
94 module.vmp_apply_dft_to_dft(&mut res_dft, &a1_dft, b.at(i), tmp_bytes);
95 module.vec_znx_idft_tmp_a(c.at_mut(i), &mut res_dft);
96 })
97}
98
99/// Evaluates the gadget product: c.at(i) = NORMALIZE(IDFT(<DFT(a.at(i)), b.at(i)>)
100///
101/// # Arguments
102///
103/// * `module`: backend support for operations mod (X^N + 1).
104/// * `c`: a [Ciphertext<VecZnx>] with cols_c cols.
105/// * `a`: a [Ciphertext<VecZnx>] with cols_a cols.
106/// * `b`: a [Ciphertext<VmpPMat>] with at least min(cols_c, cols_a) rows.
107pub fn gadget_product(
108 module: &Module,
109 c: &mut Ciphertext<VecZnx>,
110 a: &Ciphertext<VecZnx>,
111 b: &Ciphertext<VmpPMat>,
112 tmp_bytes: &mut [u8],
113) {
114 let cols: usize = min(c.cols(), a.cols());
115
116 let (tmp_bytes_b1_dft, tmp_bytes) = tmp_bytes.split_at_mut(module.bytes_of_vec_znx_dft(cols));
117 let (tmp_bytes_res_dft, tmp_bytes) = tmp_bytes.split_at_mut(module.bytes_of_vec_znx_dft(cols));
118
119 let mut a1_dft: VecZnxDft = module.new_vec_znx_dft_from_bytes_borrow(cols, tmp_bytes_b1_dft);
120 let mut res_dft: VecZnxDft = module.new_vec_znx_dft_from_bytes_borrow(cols, tmp_bytes_res_dft);
121 let mut res_big: VecZnxBig = res_dft.as_vec_znx_big();
122
123 // a1_dft = DFT(a[1])
124 module.vec_znx_dft(&mut a1_dft, a.at(1));
125
126 // c[i] = IDFT(DFT(a[1]) * b[i])
127 (0..2).for_each(|i| {
128 module.vmp_apply_dft_to_dft(&mut res_dft, &a1_dft, b.at(i), tmp_bytes);
129 module.vec_znx_idft_tmp_a(&mut res_big, &mut res_dft);
130 module.vec_znx_big_normalize(c.log_base2k(), c.at_mut(i), &mut res_big, tmp_bytes);
131 })
132}
133
134#[cfg(test)]
135mod test {
136 use crate::{
137 ciphertext::{Ciphertext, new_gadget_ciphertext},
138 decryptor::decrypt_rlwe,
139 elem::{Elem, ElemCommon, ElemVecZnx},
140 encryptor::encrypt_grlwe_sk,
141 gadget_product::gadget_product_core,
142 keys::SecretKey,
143 parameters::{Parameters, ParametersLiteral},
144 plaintext::Plaintext,
145 };
146 use base2k::{
147 BACKEND, Infos, Sampling, SvpPPolOps, VecZnx, VecZnxBig, VecZnxBigOps, VecZnxDft,
148 VecZnxDftOps, VecZnxOps, VmpPMat, alloc_aligned_u8,
149 };
150 use sampling::source::{Source, new_seed};
151
152 #[test]
153 fn test_gadget_product_core() {
154 let log_base2k: usize = 10;
155 let q_cols: usize = 7;
156 let p_cols: usize = 1;
157
158 // Basic parameters with enough limbs to test edge cases
159 let params_lit: ParametersLiteral = ParametersLiteral {
160 backend: BACKEND::FFT64,
161 log_n: 12,
162 log_q: q_cols * log_base2k,
163 log_p: p_cols * log_base2k,
164 log_base2k: log_base2k,
165 log_scale: 20,
166 xe: 3.2,
167 xs: 1 << 11,
168 };
169
170 let params: Parameters = Parameters::new(¶ms_lit);
171
172 // scratch space
173 let mut tmp_bytes: Vec<u8> = alloc_aligned_u8(
174 params.decrypt_rlwe_tmp_byte(params.log_qp())
175 | params.gadget_product_tmp_bytes(
176 params.log_qp(),
177 params.log_qp(),
178 params.cols_qp(),
179 params.log_qp(),
180 )
181 | params.encrypt_grlwe_sk_tmp_bytes(params.cols_qp(), params.log_qp()),
182 );
183
184 // Samplers for public and private randomness
185 let mut source_xe: Source = Source::new(new_seed());
186 let mut source_xa: Source = Source::new(new_seed());
187 let mut source_xs: Source = Source::new(new_seed());
188
189 // Two secret keys
190 let mut sk0: SecretKey = SecretKey::new(params.module());
191 sk0.fill_ternary_hw(params.xs(), &mut source_xs);
192 let mut sk0_svp_ppol: base2k::SvpPPol = params.module().new_svp_ppol();
193 params.module().svp_prepare(&mut sk0_svp_ppol, &sk0.0);
194
195 let mut sk1: SecretKey = SecretKey::new(params.module());
196 sk1.fill_ternary_hw(params.xs(), &mut source_xs);
197 let mut sk1_svp_ppol: base2k::SvpPPol = params.module().new_svp_ppol();
198 params.module().svp_prepare(&mut sk1_svp_ppol, &sk1.0);
199
200 // The gadget ciphertext
201 let mut gadget_ct: Ciphertext<VmpPMat> = new_gadget_ciphertext(
202 params.module(),
203 log_base2k,
204 params.cols_qp(),
205 params.log_qp(),
206 );
207
208 // gct = [-b*sk1 + g(sk0) + e, b]
209 encrypt_grlwe_sk(
210 params.module(),
211 &mut gadget_ct,
212 &sk0.0,
213 &sk1_svp_ppol,
214 &mut source_xa,
215 &mut source_xe,
216 params.xe(),
217 &mut tmp_bytes,
218 );
219
220 // Intermediate buffers
221 let mut res_dft_0: VecZnxDft = params.module().new_vec_znx_dft(gadget_ct.cols());
222 let mut res_dft_1: VecZnxDft = params.module().new_vec_znx_dft(gadget_ct.cols());
223 let mut res_big_0: VecZnxBig = res_dft_0.as_vec_znx_big();
224 let mut res_big_1: VecZnxBig = res_dft_1.as_vec_znx_big();
225
226 // Input polynopmial, uniformly distributed
227 let mut a: VecZnx = params.module().new_vec_znx(params.cols_q());
228 params
229 .module()
230 .fill_uniform(log_base2k, &mut a, params.cols_q(), &mut source_xa);
231
232 // res = g^-1(a) * gct
233 let mut elem_res: Elem<VecZnx> =
234 Elem::<VecZnx>::new(params.module(), log_base2k, params.log_qp(), 2);
235
236 // Ideal output = a * s
237 let mut a_dft: VecZnxDft = params.module().new_vec_znx_dft(a.cols());
238 let mut a_big: VecZnxBig = a_dft.as_vec_znx_big();
239 let mut a_times_s: VecZnx = params.module().new_vec_znx(a.cols());
240
241 // a * sk0
242 params.module().svp_apply_dft(&mut a_dft, &sk0_svp_ppol, &a);
243 params.module().vec_znx_idft_tmp_a(&mut a_big, &mut a_dft);
244 params.module().vec_znx_big_normalize(
245 params.log_base2k(),
246 &mut a_times_s,
247 &a_big,
248 &mut tmp_bytes,
249 );
250
251 // Plaintext for decrypted output of gadget product
252 let mut pt: Plaintext =
253 Plaintext::new(params.module(), params.log_base2k(), params.log_qp());
254
255 // Iterates over all possible cols values for input/output polynomials and gadget ciphertext.
256
257 (1..a.cols() + 1).for_each(|a_cols| {
258 (1..gadget_ct.cols() + 1).for_each(|b_cols| {
259 pt.elem_mut().zero();
260 elem_res.zero();
261
262 //let b_cols: usize = min(a_cols+1, gadget_ct.cols());
263
264 println!("a_cols: {} b_cols: {}", a_cols, b_cols);
265
266 // res_dft_0 = DFT(gct_[0] * ct[1] = a * (-bs' + s + e) = -cs' + as + e')
267 // res_dft_1 = DFT(gct_[1] * ct[1] = a * b = c)
268 gadget_product_core(
269 params.module(),
270 &mut res_dft_0,
271 &mut res_dft_1,
272 &a,
273 &gadget_ct,
274 b_cols,
275 &mut tmp_bytes,
276 );
277
278 // res_big_0 = IDFT(res_dft_0)
279 params
280 .module()
281 .vec_znx_idft_tmp_a(&mut res_big_0, &mut res_dft_0);
282 // res_big_1 = IDFT(res_dft_1);
283 params
284 .module()
285 .vec_znx_idft_tmp_a(&mut res_big_1, &mut res_dft_1);
286
287 // res_big_0 = normalize(res_big_0)
288 params.module().vec_znx_big_normalize(
289 log_base2k,
290 elem_res.at_mut(0),
291 &res_big_0,
292 &mut tmp_bytes,
293 );
294
295 // res_big_1 = normalize(res_big_1)
296 params.module().vec_znx_big_normalize(
297 log_base2k,
298 elem_res.at_mut(1),
299 &res_big_1,
300 &mut tmp_bytes,
301 );
302
303 // <(-c*sk1 + a*sk0 + e, a), (1, sk1)> = a*sk0 + e
304 decrypt_rlwe(
305 params.module(),
306 pt.elem_mut(),
307 &elem_res,
308 &sk1_svp_ppol,
309 &mut tmp_bytes,
310 );
311
312 // a * sk0 + e - a*sk0 = e
313 params
314 .module()
315 .vec_znx_sub_inplace(pt.at_mut(0), &mut a_times_s);
316 pt.at_mut(0).normalize(log_base2k, &mut tmp_bytes);
317
318 //pt.at(0).print(pt.elem().cols(), 16);
319
320 let noise_have: f64 = pt.at(0).std(log_base2k).log2();
321
322 let var_a_err: f64;
323
324 if a_cols < a.cols() {
325 var_a_err = 1f64 / 12f64;
326 } else {
327 var_a_err = 0f64;
328 }
329
330 let a_logq: usize = a_cols * log_base2k;
331 let b_logq: usize = b_cols * log_base2k;
332 let var_msg: f64 = params.xs() as f64;
333
334 let noise_pred: f64 =
335 params.noise_grlwe_product(var_msg, var_a_err, a_logq, b_logq);
336
337 assert!(noise_have <= noise_pred + 1.0);
338
339 println!("noise_pred: {}", noise_have);
340 println!("noise_have: {}", noise_pred);
341 });
342 });
343 }
344}
345
346impl Parameters {
347 pub fn noise_grlwe_product(
348 &self,
349 var_msg: f64,
350 var_a_err: f64,
351 a_logq: usize,
352 b_logq: usize,
353 ) -> f64 {
354 let n: f64 = self.n() as f64;
355 let var_xs: f64 = self.xs() as f64;
356
357 let var_gct_err_lhs: f64;
358 let var_gct_err_rhs: f64;
359 if b_logq < self.log_qp() {
360 let var_round: f64 = 1f64 / 12f64;
361 var_gct_err_lhs = var_round;
362 var_gct_err_rhs = var_round;
363 } else {
364 var_gct_err_lhs = self.xe() * self.xe();
365 var_gct_err_rhs = 0f64;
366 }
367
368 noise_grlwe_product(
369 n,
370 self.log_base2k(),
371 var_xs,
372 var_msg,
373 var_a_err,
374 var_gct_err_lhs,
375 var_gct_err_rhs,
376 a_logq,
377 b_logq,
378 )
379 }
380}
381
382pub fn noise_grlwe_product(
383 n: f64,
384 log_base2k: usize,
385 var_xs: f64,
386 var_msg: f64,
387 var_a_err: f64,
388 var_gct_err_lhs: f64,
389 var_gct_err_rhs: f64,
390 a_logq: usize,
391 b_logq: usize,
392) -> f64 {
393 let a_logq: usize = min(a_logq, b_logq);
394 let a_cols: usize = (a_logq + log_base2k - 1) / log_base2k;
395
396 let b_scale = 2.0f64.powi(b_logq as i32);
397 let a_scale: f64 = 2.0f64.powi((b_logq - a_logq) as i32);
398
399 let base: f64 = (1 << (log_base2k)) as f64;
400 let var_base: f64 = base * base / 12f64;
401
402 // lhs = a_cols * n * (var_base * var_gct_err_lhs + var_e_a * var_msg * p^2)
403 // rhs = a_cols * n * var_base * var_gct_err_rhs * var_xs
404 let mut noise: f64 =
405 (a_cols as f64) * n * var_base * (var_gct_err_lhs + var_xs * var_gct_err_rhs);
406 noise += var_msg * var_a_err * a_scale * a_scale;
407 noise = noise.sqrt();
408 noise /= b_scale;
409 noise.log2().min(-1.0) // max noise is [-2^{-1}, 2^{-1}]
410}