phantom-zone/src/rgsw/keygen.rs
src/rgsw/keygen.rsRaw
1use std::{
2 clone,
3 fmt::Debug,
4 iter,
5 marker::PhantomData,
6 ops::{Div, Neg, Sub},
7};
8
9use itertools::{izip, Itertools};
10use num_traits::{PrimInt, Signed, ToPrimitive, Zero};
11
12use crate::{
13 backend::{ArithmeticOps, GetModulus, Modulus, VectorOps},
14 decomposer::{self, Decomposer, RlweDecomposer},
15 ntt::{self, Ntt, NttInit},
16 random::{
17 DefaultSecureRng, NewWithSeed, RandomElementInModulus, RandomFill,
18 RandomFillGaussianInModulus, RandomFillUniformInModulus,
19 },
20 rgsw::decompose_r,
21 utils::{fill_random_ternary_secret_with_hamming_weight, TryConvertFrom1, WithLocal},
22 Matrix, MatrixEntity, MatrixMut, Row, RowEntity, RowMut, Secret, ShoupMatrixFMA,
23};
24
25pub(crate) fn generate_auto_map(ring_size: usize, k: isize) -> (Vec<usize>, Vec<bool>) {
26 assert!(k & 1 == 1, "Auto {k} must be odd");
27
28 let k = if k < 0 {
29 // k is -ve, return k%(2*N)
30 (2 * ring_size) - (k.abs() as usize % (2 * ring_size))
31 } else {
32 k as usize
33 };
34 let (auto_map_index, auto_sign_index): (Vec<usize>, Vec<bool>) = (0..ring_size)
35 .into_iter()
36 .map(|i| {
37 let mut to_index = (i * k) % (2 * ring_size);
38 let mut sign = true;
39
40 // wrap around. false implies negative
41 if to_index >= ring_size {
42 to_index = to_index - ring_size;
43 sign = false;
44 }
45
46 (to_index, sign)
47 })
48 .unzip();
49 (auto_map_index, auto_sign_index)
50}
51
52/// Encrypts message m as a RGSW ciphertext.
53///
54/// - m_eval: is `m` is evaluation domain
55/// - out_rgsw: RGSW(m) is stored as single matrix of dimension (d_rgsw * 3,
56/// ring_size). The matrix has the following structure [RLWE'_A(-sm) ||
57/// RLWE'_B(-sm) || RLWE'_B(m)]^T and RLWE'_A(m) is generated via seed (where
58/// p_rng is assumed to be seeded with seed)
59pub(crate) fn secret_key_encrypt_rgsw<
60 Mmut: MatrixMut + MatrixEntity,
61 S,
62 R: RandomFillGaussianInModulus<[Mmut::MatElement], ModOp::M>
63 + RandomFillUniformInModulus<[Mmut::MatElement], ModOp::M>,
64 PR: RandomFillUniformInModulus<[Mmut::MatElement], ModOp::M>,
65 ModOp: VectorOps<Element = Mmut::MatElement> + GetModulus<Element = Mmut::MatElement>,
66 NttOp: Ntt<Element = Mmut::MatElement>,
67>(
68 out_rgsw: &mut Mmut,
69 m: &[Mmut::MatElement],
70 gadget_a: &[Mmut::MatElement],
71 gadget_b: &[Mmut::MatElement],
72 s: &[S],
73 mod_op: &ModOp,
74 ntt_op: &NttOp,
75 p_rng: &mut PR,
76 rng: &mut R,
77) where
78 <Mmut as Matrix>::R: RowMut + RowEntity + TryConvertFrom1<[S], ModOp::M> + Debug,
79 Mmut::MatElement: Copy + Debug,
80{
81 let d_a = gadget_a.len();
82 let d_b = gadget_b.len();
83 let q = mod_op.modulus();
84 let ring_size = s.len();
85 assert!(out_rgsw.dimension() == (d_a * 2 + d_b, ring_size));
86 assert!(m.as_ref().len() == ring_size);
87
88 // RLWE(-sm), RLWE(m)
89 let (rlwe_dash_nsm, b_rlwe_dash_m) = out_rgsw.split_at_row_mut(d_a * 2);
90
91 let mut s_eval = Mmut::R::try_convert_from(s, &q);
92 ntt_op.forward(s_eval.as_mut());
93
94 let mut scratch_space = Mmut::R::zeros(ring_size);
95
96 // RLWE'(-sm)
97 let (a_rlwe_dash_nsm, b_rlwe_dash_nsm) = rlwe_dash_nsm.split_at_mut(d_a);
98 izip!(
99 a_rlwe_dash_nsm.iter_mut(),
100 b_rlwe_dash_nsm.iter_mut(),
101 gadget_a.iter()
102 )
103 .for_each(|(ai, bi, beta_i)| {
104 // Sample a_i
105 RandomFillUniformInModulus::random_fill(rng, &q, ai.as_mut());
106
107 // a_i * s
108 scratch_space.as_mut().copy_from_slice(ai.as_ref());
109 ntt_op.forward(scratch_space.as_mut());
110 mod_op.elwise_mul_mut(scratch_space.as_mut(), s_eval.as_ref());
111 ntt_op.backward(scratch_space.as_mut());
112
113 // b_i = e_i + a_i * s
114 RandomFillGaussianInModulus::random_fill(rng, &q, bi.as_mut());
115 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.as_ref());
116
117 // a_i + \beta_i * m
118 mod_op.elwise_scalar_mul(scratch_space.as_mut(), m.as_ref(), beta_i);
119 mod_op.elwise_add_mut(ai.as_mut(), scratch_space.as_ref());
120 });
121
122 // RLWE(m)
123 let mut a_rlwe_dash_m = {
124 // polynomials of part A of RLWE'(m) are sampled from seed
125 let mut a = Mmut::zeros(d_b, ring_size);
126 a.iter_rows_mut()
127 .for_each(|ai| RandomFillUniformInModulus::random_fill(p_rng, &q, ai.as_mut()));
128 a
129 };
130
131 izip!(
132 a_rlwe_dash_m.iter_rows_mut(),
133 b_rlwe_dash_m.iter_mut(),
134 gadget_b.iter()
135 )
136 .for_each(|(ai, bi, beta_i)| {
137 // ai * s
138 ntt_op.forward(ai.as_mut());
139 mod_op.elwise_mul_mut(ai.as_mut(), s_eval.as_ref());
140 ntt_op.backward(ai.as_mut());
141
142 // beta_i * m
143 mod_op.elwise_scalar_mul(scratch_space.as_mut(), m.as_ref(), beta_i);
144
145 // Sample e_i
146 RandomFillGaussianInModulus::random_fill(rng, &q, bi.as_mut());
147 // e_i + beta_i * m + ai*s
148 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.as_ref());
149 mod_op.elwise_add_mut(bi.as_mut(), ai.as_ref());
150 });
151}
152
153pub(crate) fn public_key_encrypt_rgsw<
154 Mmut: MatrixMut + MatrixEntity,
155 M: Matrix<MatElement = Mmut::MatElement>,
156 R: RandomFillGaussianInModulus<[Mmut::MatElement], ModOp::M>
157 + RandomFill<[u8]>
158 + RandomElementInModulus<usize, usize>,
159 ModOp: VectorOps<Element = Mmut::MatElement> + GetModulus<Element = Mmut::MatElement>,
160 NttOp: Ntt<Element = Mmut::MatElement>,
161>(
162 out_rgsw: &mut Mmut,
163 m: &[M::MatElement],
164 public_key: &M,
165 gadget_a: &[Mmut::MatElement],
166 gadget_b: &[Mmut::MatElement],
167 mod_op: &ModOp,
168 ntt_op: &NttOp,
169 rng: &mut R,
170) where
171 <Mmut as Matrix>::R: RowMut + RowEntity + TryConvertFrom1<[i32], ModOp::M>,
172 Mmut::MatElement: Copy,
173{
174 let ring_size = public_key.dimension().1;
175 let d_a = gadget_a.len();
176 let d_b = gadget_b.len();
177 assert!(public_key.dimension().0 == 2);
178 assert!(out_rgsw.dimension() == (d_a * 2 + d_b * 2, ring_size));
179
180 let mut pk_eval = Mmut::zeros(2, ring_size);
181 izip!(pk_eval.iter_rows_mut(), public_key.iter_rows()).for_each(|(to_i, from_i)| {
182 to_i.as_mut().copy_from_slice(from_i.as_ref());
183 ntt_op.forward(to_i.as_mut());
184 });
185 let p0 = pk_eval.get_row_slice(0);
186 let p1 = pk_eval.get_row_slice(1);
187
188 let q = mod_op.modulus();
189
190 // RGSW(m) = RLWE'(-sm), RLWE(m)
191 let (rlwe_dash_nsm, rlwe_dash_m) = out_rgsw.split_at_row_mut(d_a * 2);
192
193 // RLWE(-sm)
194 let (rlwe_dash_nsm_parta, rlwe_dash_nsm_partb) = rlwe_dash_nsm.split_at_mut(d_a);
195 izip!(
196 rlwe_dash_nsm_parta.iter_mut(),
197 rlwe_dash_nsm_partb.iter_mut(),
198 gadget_a.iter()
199 )
200 .for_each(|(ai, bi, beta_i)| {
201 // sample ephemeral secret u_i
202 let mut u = vec![0i32; ring_size];
203 fill_random_ternary_secret_with_hamming_weight(u.as_mut(), ring_size >> 1, rng);
204 let mut u_eval = Mmut::R::try_convert_from(u.as_ref(), &q);
205 ntt_op.forward(u_eval.as_mut());
206
207 let mut u_eval_copy = Mmut::R::zeros(ring_size);
208 u_eval_copy.as_mut().copy_from_slice(u_eval.as_ref());
209
210 // p0 * u
211 mod_op.elwise_mul_mut(u_eval.as_mut(), p0.as_ref());
212 // p1 * u
213 mod_op.elwise_mul_mut(u_eval_copy.as_mut(), p1.as_ref());
214 ntt_op.backward(u_eval.as_mut());
215 ntt_op.backward(u_eval_copy.as_mut());
216
217 // sample error
218 RandomFillGaussianInModulus::random_fill(rng, &q, ai.as_mut());
219 RandomFillGaussianInModulus::random_fill(rng, &q, bi.as_mut());
220
221 // a = p0*u+e0
222 mod_op.elwise_add_mut(ai.as_mut(), u_eval.as_ref());
223 // b = p1*u+e1
224 mod_op.elwise_add_mut(bi.as_mut(), u_eval_copy.as_ref());
225
226 // a = p0*u + e0 + \beta*m
227 // use u_eval as scratch
228 mod_op.elwise_scalar_mul(u_eval.as_mut(), m.as_ref(), beta_i);
229 mod_op.elwise_add_mut(ai.as_mut(), u_eval.as_ref());
230 });
231
232 // RLWE(m)
233 let (rlwe_dash_m_parta, rlwe_dash_m_partb) = rlwe_dash_m.split_at_mut(d_b);
234 izip!(
235 rlwe_dash_m_parta.iter_mut(),
236 rlwe_dash_m_partb.iter_mut(),
237 gadget_b.iter()
238 )
239 .for_each(|(ai, bi, beta_i)| {
240 // sample ephemeral secret u_i
241 let mut u = vec![0i32; ring_size];
242 fill_random_ternary_secret_with_hamming_weight(u.as_mut(), ring_size >> 1, rng);
243 let mut u_eval = Mmut::R::try_convert_from(u.as_ref(), &q);
244 ntt_op.forward(u_eval.as_mut());
245
246 let mut u_eval_copy = Mmut::R::zeros(ring_size);
247 u_eval_copy.as_mut().copy_from_slice(u_eval.as_ref());
248
249 // p0 * u
250 mod_op.elwise_mul_mut(u_eval.as_mut(), p0.as_ref());
251 // p1 * u
252 mod_op.elwise_mul_mut(u_eval_copy.as_mut(), p1.as_ref());
253 ntt_op.backward(u_eval.as_mut());
254 ntt_op.backward(u_eval_copy.as_mut());
255
256 // sample error
257 RandomFillGaussianInModulus::random_fill(rng, &q, ai.as_mut());
258 RandomFillGaussianInModulus::random_fill(rng, &q, bi.as_mut());
259
260 // a = p0*u+e0
261 mod_op.elwise_add_mut(ai.as_mut(), u_eval.as_ref());
262 // b = p1*u+e1
263 mod_op.elwise_add_mut(bi.as_mut(), u_eval_copy.as_ref());
264
265 // b = p1*u + e0 + \beta*m
266 // use u_eval as scratch
267 mod_op.elwise_scalar_mul(u_eval.as_mut(), m.as_ref(), beta_i);
268 mod_op.elwise_add_mut(bi.as_mut(), u_eval.as_ref());
269 });
270}
271
272/// Generates RLWE Key switching key to key switch ciphertext RLWE_{from_s}(m)
273/// to RLWE_{to_s}(m).
274///
275/// Key switching equals
276/// \sum decompose(c_1)_i * RLWE_{to_s}(\beta^i -from_s)
277/// Hence, key switchin key equals RLWE'(-from_s) = RLWE(-from_s), RLWE(beta^1
278/// -from_s), ..., RLWE(beta^{d-1} -from_s).
279///
280/// - ksk_out: Output Key switching key. Key switching key stores only part B
281/// polynomials of ksk RLWE ciphertexts (i.e. RLWE'_B(-from_s)) in coefficient
282/// domain
283/// - neg_from_s: Negative of secret polynomial to key switch from
284/// - to_s: secret polynomial to key switch to.
285pub(crate) fn rlwe_ksk_gen<
286 Mmut: MatrixMut + MatrixEntity,
287 ModOp: ArithmeticOps<Element = Mmut::MatElement>
288 + VectorOps<Element = Mmut::MatElement>
289 + GetModulus<Element = Mmut::MatElement>,
290 NttOp: Ntt<Element = Mmut::MatElement>,
291 R: RandomFillGaussianInModulus<[Mmut::MatElement], ModOp::M>,
292 PR: RandomFillUniformInModulus<[Mmut::MatElement], ModOp::M>,
293>(
294 ksk_out: &mut Mmut,
295 neg_from_s: Mmut::R,
296 mut to_s: Mmut::R,
297 gadget_vector: &[Mmut::MatElement],
298 mod_op: &ModOp,
299 ntt_op: &NttOp,
300 p_rng: &mut PR,
301 rng: &mut R,
302) where
303 <Mmut as Matrix>::R: RowMut,
304{
305 let ring_size = neg_from_s.as_ref().len();
306 let d = gadget_vector.len();
307 assert!(ksk_out.dimension() == (d, ring_size));
308
309 let q = mod_op.modulus();
310
311 ntt_op.forward(to_s.as_mut());
312
313 // RLWE'_{to_s}(-from_s)
314 let mut part_a = {
315 let mut a = Mmut::zeros(d, ring_size);
316 a.iter_rows_mut()
317 .for_each(|ai| RandomFillUniformInModulus::random_fill(p_rng, q, ai.as_mut()));
318 a
319 };
320 izip!(
321 part_a.iter_rows_mut(),
322 ksk_out.iter_rows_mut(),
323 gadget_vector.iter(),
324 )
325 .for_each(|(ai, bi, beta_i)| {
326 // si * ai
327 ntt_op.forward(ai.as_mut());
328 mod_op.elwise_mul_mut(ai.as_mut(), to_s.as_ref());
329 ntt_op.backward(ai.as_mut());
330
331 // ei + to_s*ai
332 RandomFillGaussianInModulus::random_fill(rng, &q, bi.as_mut());
333 mod_op.elwise_add_mut(bi.as_mut(), ai.as_ref());
334
335 // beta_i * -from_s
336 // use ai as scratch space
337 mod_op.elwise_scalar_mul(ai.as_mut(), neg_from_s.as_ref(), beta_i);
338
339 // bi = ei + to_s*ai + beta_i*-from_s
340 mod_op.elwise_add_mut(bi.as_mut(), ai.as_ref());
341 });
342}
343
344pub(crate) fn galois_key_gen<
345 Mmut: MatrixMut + MatrixEntity,
346 ModOp: ArithmeticOps<Element = Mmut::MatElement>
347 + VectorOps<Element = Mmut::MatElement>
348 + GetModulus<Element = Mmut::MatElement>,
349 NttOp: Ntt<Element = Mmut::MatElement>,
350 S,
351 R: RandomFillGaussianInModulus<[Mmut::MatElement], ModOp::M>,
352 PR: RandomFillUniformInModulus<[Mmut::MatElement], ModOp::M>,
353>(
354 ksk_out: &mut Mmut,
355 s: &[S],
356 auto_k: isize,
357 gadget_vector: &[Mmut::MatElement],
358 mod_op: &ModOp,
359 ntt_op: &NttOp,
360 p_rng: &mut PR,
361 rng: &mut R,
362) where
363 <Mmut as Matrix>::R: RowMut,
364 Mmut::R: TryConvertFrom1<[S], ModOp::M> + RowEntity,
365 Mmut::MatElement: Copy + Sub<Output = Mmut::MatElement>,
366{
367 let ring_size = s.len();
368 let (auto_map_index, auto_map_sign) = generate_auto_map(ring_size, auto_k);
369
370 let q = mod_op.modulus();
371
372 // s(X) -> -s(X^k)
373 let s = Mmut::R::try_convert_from(s, q);
374 let mut neg_s_auto = Mmut::R::zeros(s.as_ref().len());
375 izip!(s.as_ref(), auto_map_index.iter(), auto_map_sign.iter()).for_each(
376 |(el, to_index, sign)| {
377 // if sign is +ve (true), then negate because we need -s(X) (i.e. do the
378 // opposite than the usual case)
379 if *sign {
380 neg_s_auto.as_mut()[*to_index] = mod_op.neg(el);
381 } else {
382 neg_s_auto.as_mut()[*to_index] = *el;
383 }
384 },
385 );
386
387 // Ksk from -s(X^k) to s(X)
388 rlwe_ksk_gen(
389 ksk_out,
390 neg_s_auto,
391 s,
392 gadget_vector,
393 mod_op,
394 ntt_op,
395 p_rng,
396 rng,
397 );
398}
399
400/// Encrypt polynomial m(X) as RLWE ciphertext.
401///
402/// - rlwe_out: returned RLWE ciphertext RLWE(m) in coefficient domain. RLWE
403/// ciphertext is a matirx with first row consiting polynomial `a` and the
404/// second rows consting polynomial `b`
405pub(crate) fn secret_key_encrypt_rlwe<
406 Ro: Row + RowMut + RowEntity,
407 ModOp: VectorOps<Element = Ro::Element> + GetModulus<Element = Ro::Element>,
408 NttOp: Ntt<Element = Ro::Element>,
409 S,
410 R: RandomFillGaussianInModulus<[Ro::Element], ModOp::M>,
411 PR: RandomFillUniformInModulus<[Ro::Element], ModOp::M>,
412>(
413 m: &[Ro::Element],
414 b_rlwe_out: &mut Ro,
415 s: &[S],
416 mod_op: &ModOp,
417 ntt_op: &NttOp,
418 p_rng: &mut PR,
419 rng: &mut R,
420) where
421 Ro: TryConvertFrom1<[S], ModOp::M> + Debug,
422{
423 let ring_size = s.len();
424 assert!(m.as_ref().len() == ring_size);
425 assert!(b_rlwe_out.as_ref().len() == ring_size);
426
427 let q = mod_op.modulus();
428
429 // sample a
430 let mut a = {
431 let mut a = Ro::zeros(ring_size);
432 RandomFillUniformInModulus::random_fill(p_rng, q, a.as_mut());
433 a
434 };
435
436 // s * a
437 let mut sa = Ro::try_convert_from(s, q);
438 ntt_op.forward(sa.as_mut());
439 ntt_op.forward(a.as_mut());
440 mod_op.elwise_mul_mut(sa.as_mut(), a.as_ref());
441 ntt_op.backward(sa.as_mut());
442
443 // sample e
444 RandomFillGaussianInModulus::random_fill(rng, q, b_rlwe_out.as_mut());
445 mod_op.elwise_add_mut(b_rlwe_out.as_mut(), m.as_ref());
446 mod_op.elwise_add_mut(b_rlwe_out.as_mut(), sa.as_ref());
447}
448
449pub(crate) fn public_key_encrypt_rlwe<
450 M: Matrix,
451 Mmut: MatrixMut<MatElement = M::MatElement>,
452 ModOp: VectorOps<Element = M::MatElement> + GetModulus<Element = M::MatElement>,
453 NttOp: Ntt<Element = M::MatElement>,
454 S,
455 R: RandomFillGaussianInModulus<[M::MatElement], ModOp::M>
456 + RandomFillUniformInModulus<[M::MatElement], ModOp::M>
457 + RandomFill<[u8]>
458 + RandomElementInModulus<usize, usize>,
459>(
460 rlwe_out: &mut Mmut,
461 pk: &M,
462 m: &[M::MatElement],
463 mod_op: &ModOp,
464 ntt_op: &NttOp,
465 rng: &mut R,
466) where
467 <Mmut as Matrix>::R: RowMut + TryConvertFrom1<[S], ModOp::M> + RowEntity,
468 M::MatElement: Copy,
469 S: Zero + Signed + Copy,
470{
471 let ring_size = m.len();
472 assert!(rlwe_out.dimension() == (2, ring_size));
473
474 let q = mod_op.modulus();
475
476 let mut u = vec![S::zero(); ring_size];
477 fill_random_ternary_secret_with_hamming_weight(u.as_mut(), ring_size >> 1, rng);
478 let mut u = Mmut::R::try_convert_from(&u, q);
479 ntt_op.forward(u.as_mut());
480
481 let mut ua = Mmut::R::zeros(ring_size);
482 ua.as_mut().copy_from_slice(pk.get_row_slice(0));
483 let mut ub = Mmut::R::zeros(ring_size);
484 ub.as_mut().copy_from_slice(pk.get_row_slice(1));
485
486 // a*u
487 ntt_op.forward(ua.as_mut());
488 mod_op.elwise_mul_mut(ua.as_mut(), u.as_ref());
489 ntt_op.backward(ua.as_mut());
490
491 // b*u
492 ntt_op.forward(ub.as_mut());
493 mod_op.elwise_mul_mut(ub.as_mut(), u.as_ref());
494 ntt_op.backward(ub.as_mut());
495
496 // sample error
497 rlwe_out.iter_rows_mut().for_each(|ri| {
498 RandomFillGaussianInModulus::random_fill(rng, &q, ri.as_mut());
499 });
500
501 // a*u + e0
502 mod_op.elwise_add_mut(rlwe_out.get_row_mut(0), ua.as_ref());
503 // b*u + e1
504 mod_op.elwise_add_mut(rlwe_out.get_row_mut(1), ub.as_ref());
505
506 // b*u + e1 + m
507 mod_op.elwise_add_mut(rlwe_out.get_row_mut(1), m);
508}
509
510/// Generates RLWE public key
511pub(crate) fn gen_rlwe_public_key<
512 Ro: RowMut + RowEntity,
513 S,
514 ModOp: VectorOps<Element = Ro::Element> + GetModulus<Element = Ro::Element>,
515 NttOp: Ntt<Element = Ro::Element>,
516 PRng: RandomFillUniformInModulus<[Ro::Element], ModOp::M>,
517 Rng: RandomFillGaussianInModulus<[Ro::Element], ModOp::M>,
518>(
519 part_b_out: &mut Ro,
520 s: &[S],
521 ntt_op: &NttOp,
522 mod_op: &ModOp,
523 p_rng: &mut PRng,
524 rng: &mut Rng,
525) where
526 Ro: TryConvertFrom1<[S], ModOp::M>,
527{
528 let ring_size = s.len();
529 assert!(part_b_out.as_ref().len() == ring_size);
530
531 let q = mod_op.modulus();
532
533 // sample a
534 let mut a = {
535 let mut tmp = Ro::zeros(ring_size);
536 RandomFillUniformInModulus::random_fill(p_rng, &q, tmp.as_mut());
537 tmp
538 };
539 ntt_op.forward(a.as_mut());
540
541 // s*a
542 let mut sa = Ro::try_convert_from(s, &q);
543 ntt_op.forward(sa.as_mut());
544 mod_op.elwise_mul_mut(sa.as_mut(), a.as_ref());
545 ntt_op.backward(sa.as_mut());
546
547 // s*a + e
548 RandomFillGaussianInModulus::random_fill(rng, &q, part_b_out.as_mut());
549 mod_op.elwise_add_mut(part_b_out.as_mut(), sa.as_ref());
550}
551
552/// Decrypts degree 1 RLWE ciphertext RLWE(m) and returns m
553///
554/// - rlwe_ct: input degree 1 ciphertext RLWE(m).
555pub(crate) fn decrypt_rlwe<
556 R: RowMut,
557 M: Matrix<MatElement = R::Element>,
558 ModOp: VectorOps<Element = R::Element> + GetModulus<Element = R::Element>,
559 NttOp: Ntt<Element = R::Element>,
560 S,
561>(
562 rlwe_ct: &M,
563 s: &[S],
564 m_out: &mut R,
565 ntt_op: &NttOp,
566 mod_op: &ModOp,
567) where
568 R: TryConvertFrom1<[S], ModOp::M>,
569 R::Element: Copy,
570{
571 let ring_size = s.len();
572 assert!(rlwe_ct.dimension() == (2, ring_size));
573 assert!(m_out.as_ref().len() == ring_size);
574
575 // transform a to evluation form
576 m_out.as_mut().copy_from_slice(rlwe_ct.get_row_slice(0));
577 ntt_op.forward(m_out.as_mut());
578
579 // -s*a
580 let mut s = R::try_convert_from(&s, mod_op.modulus());
581 ntt_op.forward(s.as_mut());
582 mod_op.elwise_mul_mut(m_out.as_mut(), s.as_ref());
583 mod_op.elwise_neg_mut(m_out.as_mut());
584 ntt_op.backward(m_out.as_mut());
585
586 // m+e = b - s*a
587 mod_op.elwise_add_mut(m_out.as_mut(), rlwe_ct.get_row_slice(1));
588}
589
590// Measures noise in degree 1 RLWE ciphertext against encoded ideal message
591// encoded_m
592pub(crate) fn measure_noise<
593 Mmut: MatrixMut + Matrix,
594 ModOp: VectorOps<Element = Mmut::MatElement> + GetModulus<Element = Mmut::MatElement>,
595 NttOp: Ntt<Element = Mmut::MatElement>,
596 S,
597>(
598 rlwe_ct: &Mmut,
599 encoded_m_ideal: &Mmut::R,
600 ntt_op: &NttOp,
601 mod_op: &ModOp,
602 s: &[S],
603) -> f64
604where
605 <Mmut as Matrix>::R: RowMut,
606 Mmut::R: RowEntity + TryConvertFrom1<[S], ModOp::M>,
607 Mmut::MatElement: PrimInt + ToPrimitive + Debug,
608{
609 let ring_size = s.len();
610 assert!(rlwe_ct.dimension() == (2, ring_size));
611 assert!(encoded_m_ideal.as_ref().len() == ring_size);
612
613 // -(s * a)
614 let q = mod_op.modulus();
615 let mut s = Mmut::R::try_convert_from(s, &q);
616 ntt_op.forward(s.as_mut());
617 let mut a = Mmut::R::zeros(ring_size);
618 a.as_mut().copy_from_slice(rlwe_ct.get_row_slice(0));
619 ntt_op.forward(a.as_mut());
620 mod_op.elwise_mul_mut(s.as_mut(), a.as_ref());
621 mod_op.elwise_neg_mut(s.as_mut());
622 ntt_op.backward(s.as_mut());
623
624 // m+e = b - s*a
625 let mut m_plus_e = s;
626 mod_op.elwise_add_mut(m_plus_e.as_mut(), rlwe_ct.get_row_slice(1));
627
628 // difference
629 mod_op.elwise_sub_mut(m_plus_e.as_mut(), encoded_m_ideal.as_ref());
630
631 let mut max_diff_bits = f64::MIN;
632 m_plus_e.as_ref().iter().for_each(|v| {
633 let bits = (q.map_element_to_i64(v).to_f64().unwrap()).log2();
634
635 if max_diff_bits < bits {
636 max_diff_bits = bits;
637 }
638 });
639
640 return max_diff_bits;
641}