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