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