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