phantom-zone/src/rgsw.rs
src/rgsw.rsRaw
1use std::{
2 clone,
3 fmt::Debug,
4 marker::PhantomData,
5 ops::{Div, Neg, Sub},
6};
7
8use itertools::{izip, Itertools};
9use num_traits::{PrimInt, ToPrimitive, Zero};
10
11use crate::{
12 backend::{ArithmeticOps, VectorOps},
13 decomposer::{self, Decomposer},
14 ntt::{self, Ntt, NttInit},
15 random::{DefaultSecureRng, NewWithSeed, RandomGaussianDist, RandomUniformDist},
16 utils::{fill_random_ternary_secret_with_hamming_weight, TryConvertFrom, WithLocal},
17 Matrix, MatrixEntity, MatrixMut, Row, RowEntity, RowMut, Secret,
18};
19
20pub struct SeededAutoKey<M, S>
21where
22 M: Matrix,
23{
24 data: M,
25 seed: S,
26 modulus: M::MatElement,
27}
28
29impl<M: Matrix + MatrixEntity, S> SeededAutoKey<M, S> {
30 fn from_raw(data: M, seed: S, modulus: M::MatElement) -> Self {
31 assert!(data.dimension().0 % 3 == 0);
32
33 SeededAutoKey {
34 data,
35 seed,
36 modulus,
37 }
38 }
39
40 fn empty(ring_size: usize, d_rgsw: usize, seed: S, modulus: M::MatElement) -> Self {
41 SeededAutoKey {
42 data: M::zeros(d_rgsw, ring_size),
43 seed,
44 modulus: modulus,
45 }
46 }
47}
48
49pub struct AutoKeyEvaluationDomain<M, R, N> {
50 data: M,
51 _phantom: PhantomData<(R, N)>,
52}
53
54impl<
55 M: MatrixMut + MatrixEntity,
56 R: RandomUniformDist<[M::MatElement], Parameters = M::MatElement> + NewWithSeed,
57 N: NttInit<Element = M::MatElement> + Ntt<Element = M::MatElement>,
58 > From<&SeededAutoKey<M, R::Seed>> for AutoKeyEvaluationDomain<M, R, N>
59where
60 <M as Matrix>::R: RowMut,
61 M::MatElement: Copy,
62 R::Seed: Clone,
63{
64 fn from(value: &SeededAutoKey<M, R::Seed>) -> Self {
65 let (d, ring_size) = value.data.dimension();
66 let mut data = M::zeros(2 * d, ring_size);
67
68 // sample RLWE'_A(-s(X^k))
69 let mut p_rng = R::new_with_seed(value.seed.clone());
70 data.iter_rows_mut().take(d).for_each(|r| {
71 RandomUniformDist::random_fill(&mut p_rng, &value.modulus, r.as_mut());
72 });
73
74 // copy over RLWE'_B(-s(X^k))
75 izip!(data.iter_rows_mut().skip(d), value.data.iter_rows()).for_each(|(to_r, from_r)| {
76 to_r.as_mut().copy_from_slice(from_r.as_ref());
77 });
78
79 // send RLWE'(-s(X^k)) polynomials to evaluation domain
80 let ntt_op = N::new(value.modulus, ring_size);
81 data.iter_rows_mut()
82 .for_each(|r| ntt_op.forward(r.as_mut()));
83
84 AutoKeyEvaluationDomain {
85 data,
86 _phantom: PhantomData,
87 }
88 }
89}
90
91pub struct SeededRgswCiphertext<M, S>
92where
93 M: Matrix,
94{
95 data: M,
96 seed: S,
97 modulus: M::MatElement,
98}
99
100impl<M: Matrix + MatrixEntity, S> SeededRgswCiphertext<M, S> {
101 fn from_raw(data: M, seed: S, modulus: M::MatElement) -> SeededRgswCiphertext<M, S> {
102 assert!(data.dimension().0 % 3 == 0);
103
104 SeededRgswCiphertext {
105 data,
106 seed,
107 modulus,
108 }
109 }
110
111 fn empty(
112 ring_size: usize,
113 d_rgsw: usize,
114 seed: S,
115 modulus: M::MatElement,
116 ) -> SeededRgswCiphertext<M, S> {
117 SeededRgswCiphertext {
118 data: M::zeros(d_rgsw * 3, ring_size),
119 seed,
120 modulus: modulus,
121 }
122 }
123}
124
125impl<M: Debug + Matrix, S: Debug> Debug for SeededRgswCiphertext<M, S>
126where
127 M::MatElement: Debug,
128{
129 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
130 f.debug_struct("SeededRgswCiphertext")
131 .field("data", &self.data)
132 .field("seed", &self.seed)
133 .field("modulus", &self.modulus)
134 .finish()
135 }
136}
137
138pub struct RgswCiphertextEvaluationDomain<M, R, N> {
139 data: M,
140 _phantom: PhantomData<(R, N)>,
141}
142
143impl<
144 M: MatrixMut + MatrixEntity,
145 R: NewWithSeed + RandomUniformDist<[M::MatElement], Parameters = M::MatElement>,
146 N: NttInit<Element = M::MatElement> + Ntt<Element = M::MatElement> + Debug,
147 > From<&SeededRgswCiphertext<M, R::Seed>> for RgswCiphertextEvaluationDomain<M, R, N>
148where
149 <M as Matrix>::R: RowMut,
150 M::MatElement: Copy,
151 R::Seed: Clone,
152 M: Debug,
153{
154 fn from(value: &SeededRgswCiphertext<M, R::Seed>) -> Self {
155 let d = value.data.dimension().0.div(3);
156
157 let mut data = M::zeros(4 * d, value.data.dimension().1);
158
159 // copy RLWE'(-sm)
160 izip!(data.iter_rows_mut().take(2 * d), value.data.iter_rows()).for_each(
161 |(to_ri, from_ri)| {
162 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
163 },
164 );
165
166 // sample A polynomials of RLWE'(m) - RLWE'A(m)
167 // TODO(Jay): Do we want to be generic over RandomGenerator used here? I think
168 // not.
169 let mut p_rng = R::new_with_seed(value.seed.clone());
170 izip!(data.iter_rows_mut().skip(2 * d).take(d))
171 .for_each(|ri| p_rng.random_fill(&value.modulus, ri.as_mut()));
172
173 // RLWE'_B(m)
174 izip!(
175 data.iter_rows_mut().skip(3 * d),
176 value.data.iter_rows().skip(2 * d)
177 )
178 .for_each(|(to_ri, from_ri)| {
179 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
180 });
181
182 // Send polynomials to evaluation domain
183 let ring_size = data.dimension().1;
184 let nttop = N::new(value.modulus, ring_size);
185 data.iter_rows_mut()
186 .for_each(|ri| nttop.forward(ri.as_mut()));
187
188 Self {
189 data: data,
190 _phantom: PhantomData,
191 }
192 }
193}
194
195impl<M: Debug, R, N> Debug for RgswCiphertextEvaluationDomain<M, R, N> {
196 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
197 f.debug_struct("RgswCiphertextEvaluationDomain")
198 .field("data", &self.data)
199 .field("_phantom", &self._phantom)
200 .finish()
201 }
202}
203
204impl<M: Matrix, R, N> Matrix for RgswCiphertextEvaluationDomain<M, R, N> {
205 type MatElement = M::MatElement;
206 type R = M::R;
207
208 fn dimension(&self) -> (usize, usize) {
209 self.data.dimension()
210 }
211}
212
213impl<M: Matrix, R, N> AsRef<[M::R]> for RgswCiphertextEvaluationDomain<M, R, N> {
214 fn as_ref(&self) -> &[M::R] {
215 self.data.as_ref()
216 }
217}
218
219pub struct SeededRlweCiphertext<R, S>
220where
221 R: Row,
222{
223 data: R,
224 seed: S,
225 modulus: R::Element,
226}
227
228impl<R: RowEntity, S> SeededRlweCiphertext<R, S> {
229 fn empty(ring_size: usize, seed: S, modulus: R::Element) -> Self {
230 SeededRlweCiphertext {
231 data: R::zeros(ring_size),
232 seed,
233 modulus,
234 }
235 }
236}
237
238pub struct RlweCiphertext<M, Rng> {
239 data: M,
240 is_trivial: bool,
241 _phatom: PhantomData<Rng>,
242}
243
244impl<M, Rng> RlweCiphertext<M, Rng> {
245 pub(crate) fn from_raw(data: M, is_trivial: bool) -> Self {
246 RlweCiphertext {
247 data,
248 is_trivial,
249 _phatom: PhantomData,
250 }
251 }
252}
253
254impl<M: Matrix, Rng> Matrix for RlweCiphertext<M, Rng> {
255 type MatElement = M::MatElement;
256 type R = M::R;
257
258 fn dimension(&self) -> (usize, usize) {
259 self.data.dimension()
260 }
261}
262
263impl<M: MatrixMut, Rng> MatrixMut for RlweCiphertext<M, Rng> where <M as Matrix>::R: RowMut {}
264
265impl<M: Matrix, Rng> AsRef<[<M as Matrix>::R]> for RlweCiphertext<M, Rng> {
266 fn as_ref(&self) -> &[<M as Matrix>::R] {
267 self.data.as_ref()
268 }
269}
270
271impl<M: MatrixMut, Rng> AsMut<[<M as Matrix>::R]> for RlweCiphertext<M, Rng>
272where
273 <M as Matrix>::R: RowMut,
274{
275 fn as_mut(&mut self) -> &mut [<M as Matrix>::R] {
276 self.data.as_mut()
277 }
278}
279
280impl<M, Rng> IsTrivial for RlweCiphertext<M, Rng> {
281 fn is_trivial(&self) -> bool {
282 self.is_trivial
283 }
284 fn set_not_trivial(&mut self) {
285 self.is_trivial = false;
286 }
287}
288
289impl<R: Row, M: MatrixEntity<R = R, MatElement = R::Element> + MatrixMut, Rng: NewWithSeed>
290 From<&SeededRlweCiphertext<R, Rng::Seed>> for RlweCiphertext<M, Rng>
291where
292 Rng::Seed: Clone,
293 Rng: RandomUniformDist<[M::MatElement], Parameters = M::MatElement>,
294 <M as Matrix>::R: RowMut,
295 R::Element: Copy,
296{
297 fn from(value: &SeededRlweCiphertext<R, Rng::Seed>) -> Self {
298 let mut data = M::zeros(2, value.data.as_ref().len());
299
300 // sample a
301 let mut p_rng = Rng::new_with_seed(value.seed.clone());
302 RandomUniformDist::random_fill(&mut p_rng, &value.modulus, data.get_row_mut(0));
303
304 data.get_row_mut(1).copy_from_slice(value.data.as_ref());
305
306 RlweCiphertext {
307 data,
308 is_trivial: false,
309 _phatom: PhantomData,
310 }
311 }
312}
313
314pub trait IsTrivial {
315 fn is_trivial(&self) -> bool;
316 fn set_not_trivial(&mut self);
317}
318
319#[derive(Clone)]
320pub struct RlweSecret {
321 values: Vec<i32>,
322}
323
324impl Secret for RlweSecret {
325 type Element = i32;
326 fn values(&self) -> &[Self::Element] {
327 &self.values
328 }
329}
330
331impl RlweSecret {
332 pub fn random(hw: usize, n: usize) -> RlweSecret {
333 DefaultSecureRng::with_local_mut(|rng| {
334 let mut out = vec![0i32; n];
335 fill_random_ternary_secret_with_hamming_weight(&mut out, hw, rng);
336
337 RlweSecret { values: out }
338 })
339 }
340}
341
342pub(crate) fn generate_auto_map(ring_size: usize, k: isize) -> (Vec<usize>, Vec<bool>) {
343 assert!(k & 1 == 1, "Auto {k} must be odd");
344
345 let k = if k < 0 {
346 // k is -ve, return k%(2*N)
347 (2 * ring_size) - (k.abs() as usize % (2 * ring_size))
348 } else {
349 k as usize
350 };
351 let (auto_map_index, auto_sign_index): (Vec<usize>, Vec<bool>) = (0..ring_size)
352 .into_iter()
353 .map(|i| {
354 let mut to_index = (i * k) % (2 * ring_size);
355 let mut sign = true;
356
357 // wrap around. false implies negative
358 if to_index >= ring_size {
359 to_index = to_index - ring_size;
360 sign = false;
361 }
362
363 (to_index, sign)
364 })
365 .unzip();
366 (auto_map_index, auto_sign_index)
367}
368
369/// Generates RLWE Key switching key to key switch ciphertext RLWE_{from_s}(m)
370/// to RLWE_{to_s}(m).
371///
372/// Key switching equals
373/// \sum decompose(c_1)_i * RLWE_{to_s}(\beta^i -from_s)
374/// Hence, key switchin key equals RLWE'(-from_s) = RLWE(-from_s), RLWE(beta^1
375/// -from_s), ..., RLWE(beta^{d-1} -from_s).
376///
377/// - ksk_out: Output Key switching key. Key switching key stores only part B
378/// polynomials of ksk RLWE ciphertexts (i.e. RLWE'_B(-from_s)) in coefficient
379/// domain
380/// - neg_from_s: Negative of secret polynomial to key switch from
381/// - to_s: secret polynomial to key switch to.
382pub(crate) fn rlwe_ksk_gen<
383 Mmut: MatrixMut + MatrixEntity,
384 ModOp: ArithmeticOps<Element = Mmut::MatElement> + VectorOps<Element = Mmut::MatElement>,
385 NttOp: Ntt<Element = Mmut::MatElement>,
386 R: RandomGaussianDist<[Mmut::MatElement], Parameters = Mmut::MatElement>
387 + RandomUniformDist<[Mmut::MatElement], Parameters = Mmut::MatElement>
388 + NewWithSeed,
389>(
390 ksk_out: &mut Mmut,
391 neg_from_s: Mmut::R,
392 mut to_s: Mmut::R,
393 gadget_vector: &[Mmut::MatElement],
394 mod_op: &ModOp,
395 ntt_op: &NttOp,
396 seed: R::Seed,
397 rng: &mut R,
398) where
399 <Mmut as Matrix>::R: RowMut,
400{
401 let ring_size = neg_from_s.as_ref().len();
402 let d = gadget_vector.len();
403 assert!(ksk_out.dimension() == (d, ring_size));
404
405 let q = ArithmeticOps::modulus(mod_op);
406
407 ntt_op.forward(to_s.as_mut());
408
409 // RLWE'_{to_s}(-from_s)
410 let mut part_a = {
411 let mut a = Mmut::zeros(d, ring_size);
412 let mut p_rng = R::new_with_seed(seed);
413 a.iter_rows_mut()
414 .for_each(|ai| RandomUniformDist::random_fill(&mut p_rng, &q, ai.as_mut()));
415 a
416 };
417 izip!(
418 part_a.iter_rows_mut(),
419 ksk_out.iter_rows_mut(),
420 gadget_vector.iter(),
421 )
422 .for_each(|(ai, bi, beta_i)| {
423 // si * ai
424 ntt_op.forward(ai.as_mut());
425 mod_op.elwise_mul_mut(ai.as_mut(), to_s.as_ref());
426 ntt_op.backward(ai.as_mut());
427
428 // ei + to_s*ai
429 RandomGaussianDist::random_fill(rng, &q, bi.as_mut());
430 mod_op.elwise_add_mut(bi.as_mut(), ai.as_ref());
431
432 // beta_i * -from_s
433 // use ai as scratch space
434 mod_op.elwise_scalar_mul(ai.as_mut(), neg_from_s.as_ref(), beta_i);
435
436 // bi = ei + to_s*ai + beta_i*-from_s
437 mod_op.elwise_add_mut(bi.as_mut(), ai.as_ref());
438 });
439}
440
441pub(crate) fn galois_key_gen<
442 Mmut: MatrixMut + MatrixEntity,
443 ModOp: ArithmeticOps<Element = Mmut::MatElement> + VectorOps<Element = Mmut::MatElement>,
444 NttOp: Ntt<Element = Mmut::MatElement>,
445 S,
446 R: RandomGaussianDist<[Mmut::MatElement], Parameters = Mmut::MatElement>
447 + RandomUniformDist<[Mmut::MatElement], Parameters = Mmut::MatElement>
448 + NewWithSeed,
449>(
450 ksk_out: &mut Mmut,
451 s: &[S],
452 auto_k: isize,
453 gadget_vector: &[Mmut::MatElement],
454 mod_op: &ModOp,
455 ntt_op: &NttOp,
456 seed: R::Seed,
457 rng: &mut R,
458) where
459 <Mmut as Matrix>::R: RowMut,
460 Mmut::R: TryConvertFrom<[S], Parameters = Mmut::MatElement> + RowEntity,
461 Mmut::MatElement: Copy + Sub<Output = Mmut::MatElement>,
462{
463 let ring_size = s.len();
464 let (auto_map_index, auto_map_sign) = generate_auto_map(ring_size, auto_k);
465
466 let q = ArithmeticOps::modulus(mod_op);
467
468 // s(X) -> -s(X^k)
469 let s = Mmut::R::try_convert_from(s, &q);
470 let mut neg_s_auto = Mmut::R::zeros(s.as_ref().len());
471 izip!(s.as_ref(), auto_map_index.iter(), auto_map_sign.iter()).for_each(
472 |(el, to_index, sign)| {
473 // if sign is +ve (true), then negate because we need -s(X) (i.e. do the
474 // opposite than the usual case)
475 if *sign {
476 neg_s_auto.as_mut()[*to_index] = q - *el;
477 } else {
478 neg_s_auto.as_mut()[*to_index] = *el;
479 }
480 },
481 );
482
483 // Ksk from -s(X^k) to s(X)
484 rlwe_ksk_gen(
485 ksk_out,
486 neg_s_auto,
487 s,
488 gadget_vector,
489 mod_op,
490 ntt_op,
491 seed,
492 rng,
493 );
494}
495
496pub(crate) fn routine<M: Matrix + ?Sized, ModOp: VectorOps<Element = M::MatElement>>(
497 write_to_row: &mut [M::MatElement],
498 matrix_a: &[M::R],
499 matrix_b: &[M::R],
500 mod_op: &ModOp,
501) {
502 izip!(matrix_a.iter(), matrix_b.iter()).for_each(|(a, b)| {
503 mod_op.elwise_fma_mut(write_to_row, a.as_ref(), b.as_ref());
504 });
505}
506
507/// Decomposes ring polynomial r(X) into d polynomials using decomposer into
508/// output matrix decomp_r
509///
510/// Note that decomposition of r(X) requires decomposition of each of
511/// coefficients.
512///
513/// - decomp_r: must have dimensions d x ring_size. i^th decomposed polynomial
514/// will be stored at i^th row.
515pub(crate) fn decompose_r<M: Matrix + MatrixMut, D: Decomposer<Element = M::MatElement>>(
516 r: &[M::MatElement],
517 decomp_r: &mut [M::R],
518 decomposer: &D,
519) where
520 <M as Matrix>::R: RowMut,
521 M::MatElement: Copy,
522{
523 let ring_size = r.len();
524 let d = decomposer.d();
525
526 for ri in 0..ring_size {
527 let el_decomposed = decomposer.decompose(&r[ri]);
528 for j in 0..d {
529 decomp_r[j].as_mut()[ri] = el_decomposed[j];
530 }
531 }
532}
533
534/// Sends RLWE_{s}(X) -> RLWE_{s}(X^k) where k is some galois element
535pub(crate) fn galois_auto<
536 MT: Matrix + IsTrivial + MatrixMut,
537 Mmut: MatrixMut<MatElement = MT::MatElement>,
538 ModOp: ArithmeticOps<Element = MT::MatElement> + VectorOps<Element = MT::MatElement>,
539 NttOp: Ntt<Element = MT::MatElement>,
540 D: Decomposer<Element = MT::MatElement>,
541>(
542 rlwe_in: &mut MT,
543 ksk: &Mmut,
544 scratch_matrix_dplus2_ring: &mut Mmut,
545 auto_map_index: &[usize],
546 auto_map_sign: &[bool],
547 mod_op: &ModOp,
548 ntt_op: &NttOp,
549 decomposer: &D,
550) where
551 <Mmut as Matrix>::R: RowMut,
552 <MT as Matrix>::R: RowMut,
553 MT::MatElement: Copy + Zero,
554{
555 let d = decomposer.d();
556
557 let (scratch_matrix_d_ring, tmp_rlwe_out) = scratch_matrix_dplus2_ring.split_at_row_mut(d);
558
559 // send b(X) -> b(X^k)
560 izip!(
561 rlwe_in.get_row(1),
562 auto_map_index.iter(),
563 auto_map_sign.iter()
564 )
565 .for_each(|(el_in, to_index, sign)| {
566 if !*sign {
567 tmp_rlwe_out[1].as_mut()[*to_index] = mod_op.neg(el_in);
568 } else {
569 tmp_rlwe_out[1].as_mut()[*to_index] = *el_in;
570 // scratch_matrix_dplus2_ring.set(d + 1, *to_index, *el_in);
571 }
572 });
573
574 if !rlwe_in.is_trivial() {
575 // send a(X) -> a(X^k) and decompose a(X^k)
576 izip!(
577 rlwe_in.get_row(0),
578 auto_map_index.iter(),
579 auto_map_sign.iter()
580 )
581 .for_each(|(el_in, to_index, sign)| {
582 let el_out = if !*sign { mod_op.neg(el_in) } else { *el_in };
583
584 let el_out_decomposed = decomposer.decompose(&el_out);
585 for j in 0..d {
586 scratch_matrix_d_ring[j].as_mut()[*to_index] = el_out_decomposed[j];
587 }
588 });
589
590 // transform decomposed a(X^k) to evaluation domain
591 scratch_matrix_d_ring.iter_mut().for_each(|r| {
592 ntt_op.forward(r.as_mut());
593 });
594
595 // RLWE(m^k) = a', b'; RLWE(m) = a, b
596 // key switch: (a * RLWE'(s(X^k)))
597 let (ksk_a, ksk_b) = ksk.split_at_row(d);
598 tmp_rlwe_out[0].as_mut().fill(Mmut::MatElement::zero());
599 // a' = decomp<a> * RLWE'_A(s(X^k))
600 routine::<Mmut, ModOp>(
601 tmp_rlwe_out[0].as_mut(),
602 scratch_matrix_d_ring,
603 ksk_a,
604 mod_op,
605 );
606 // send b(X^k) to evaluation domain
607 ntt_op.forward(tmp_rlwe_out[1].as_mut());
608 // b' = b(X^k)
609 // b' += decomp<a(X^k)> * RLWE'_B(s(X^k))
610 routine::<Mmut, ModOp>(
611 tmp_rlwe_out[1].as_mut(),
612 scratch_matrix_d_ring,
613 ksk_b,
614 mod_op,
615 );
616
617 // transform RLWE(m^k) to coefficient domain
618 tmp_rlwe_out
619 .iter_mut()
620 .for_each(|r| ntt_op.backward(r.as_mut()));
621
622 rlwe_in
623 .get_row_mut(0)
624 .copy_from_slice(tmp_rlwe_out[0].as_ref());
625 }
626
627 rlwe_in
628 .get_row_mut(1)
629 .copy_from_slice(tmp_rlwe_out[1].as_ref());
630}
631
632/// Returns RLWE(m0m1) = RLWE(m0) x RGSW(m1). Mutates rlwe_in inplace to equal
633/// RLWE(m0m1)
634///
635/// - rlwe_in: is RLWE(m0) with polynomials in coefficient domain
636/// - rgsw_in: is RGSW(m1) with polynomials in evaluation domain
637/// - scratch_matrix_d_ring: is a matrix of dimension (d_rgsw, ring_size) used
638/// as scratch space to store decomposed Ring elements temporarily
639pub(crate) fn rlwe_by_rgsw<
640 Mmut: MatrixMut,
641 MT: Matrix<MatElement = Mmut::MatElement> + MatrixMut<MatElement = Mmut::MatElement> + IsTrivial,
642 D: Decomposer<Element = Mmut::MatElement>,
643 ModOp: VectorOps<Element = Mmut::MatElement>,
644 NttOp: Ntt<Element = Mmut::MatElement>,
645>(
646 rlwe_in: &mut MT,
647 rgsw_in: &Mmut,
648 scratch_matrix_dplus2_ring: &mut Mmut,
649 decomposer: &D,
650 ntt_op: &NttOp,
651 mod_op: &ModOp,
652) where
653 Mmut::MatElement: Copy + Zero,
654 <Mmut as Matrix>::R: RowMut,
655 <MT as Matrix>::R: RowMut,
656{
657 let d_rgsw = decomposer.d();
658 assert!(scratch_matrix_dplus2_ring.dimension() == (d_rgsw + 2, rlwe_in.dimension().1));
659 assert!(rgsw_in.dimension() == (d_rgsw * 4, rlwe_in.dimension().1));
660
661 // decomposed RLWE x RGSW
662 let (rlwe_dash_nsm, rlwe_dash_m) = rgsw_in.split_at_row(d_rgsw * 2);
663 let (scratch_matrix_d_ring, scratch_rlwe_out) =
664 scratch_matrix_dplus2_ring.split_at_row_mut(d_rgsw);
665 scratch_rlwe_out[0].as_mut().fill(Mmut::MatElement::zero());
666 scratch_rlwe_out[1].as_mut().fill(Mmut::MatElement::zero());
667 // RLWE_in = a_in, b_in; RLWE_out = a_out, b_out
668 if !rlwe_in.is_trivial() {
669 // a_in = 0 when RLWE_in is trivial RLWE ciphertext
670 // decomp<a_in>
671 decompose_r::<Mmut, D>(rlwe_in.get_row_slice(0), scratch_matrix_d_ring, decomposer);
672 scratch_matrix_d_ring
673 .iter_mut()
674 .for_each(|r| ntt_op.forward(r.as_mut()));
675 // a_out += decomp<a_in> \cdot RLWE_A'(-sm)
676 routine::<Mmut, ModOp>(
677 scratch_rlwe_out[0].as_mut(),
678 scratch_matrix_d_ring.as_ref(),
679 &rlwe_dash_nsm[..d_rgsw],
680 mod_op,
681 );
682 // b_out += decomp<a_in> \cdot RLWE_B'(-sm)
683 routine::<Mmut, ModOp>(
684 scratch_rlwe_out[1].as_mut(),
685 scratch_matrix_d_ring.as_ref(),
686 &rlwe_dash_nsm[d_rgsw..],
687 mod_op,
688 );
689 }
690 // decomp<b_in>
691 decompose_r::<Mmut, D>(rlwe_in.get_row_slice(1), scratch_matrix_d_ring, decomposer);
692 scratch_matrix_d_ring
693 .iter_mut()
694 .for_each(|r| ntt_op.forward(r.as_mut()));
695 // a_out += decomp<b_in> \cdot RLWE_A'(m)
696 routine::<Mmut, ModOp>(
697 scratch_rlwe_out[0].as_mut(),
698 scratch_matrix_d_ring.as_ref(),
699 &rlwe_dash_m[..d_rgsw],
700 mod_op,
701 );
702 // b_out += decomp<b_in> \cdot RLWE_B'(m)
703 routine::<Mmut, ModOp>(
704 scratch_rlwe_out[1].as_mut(),
705 scratch_matrix_d_ring.as_ref(),
706 &rlwe_dash_m[d_rgsw..],
707 mod_op,
708 );
709
710 // transform rlwe_out to coefficient domain
711 scratch_rlwe_out
712 .iter_mut()
713 .for_each(|r| ntt_op.backward(r.as_mut()));
714
715 rlwe_in
716 .get_row_mut(0)
717 .copy_from_slice(scratch_rlwe_out[0].as_mut());
718 rlwe_in
719 .get_row_mut(1)
720 .copy_from_slice(scratch_rlwe_out[1].as_mut());
721 rlwe_in.set_not_trivial();
722}
723
724/// Encrypts message m as a RGSW ciphertext.
725///
726/// - m_eval: is `m` is evaluation domain
727/// - out_rgsw: RGSW(m) is stored as single matrix of dimension (d_rgsw * 3,
728/// ring_size). The matrix has the following structure [RLWE'_A(-sm) ||
729/// RLWE'_B(-sm) || RLWE'_B(m)]^T and RLWE'_A(m) is generated via seed
730pub(crate) fn secret_key_encrypt_rgsw<
731 Mmut: MatrixMut + MatrixEntity,
732 S,
733 R: RandomGaussianDist<[Mmut::MatElement], Parameters = Mmut::MatElement>
734 + RandomUniformDist<[Mmut::MatElement], Parameters = Mmut::MatElement>
735 + NewWithSeed,
736 ModOp: VectorOps<Element = Mmut::MatElement>,
737 NttOp: Ntt<Element = Mmut::MatElement>,
738>(
739 out_rgsw: &mut Mmut,
740 m: &Mmut::R,
741 gadget_vector: &[Mmut::MatElement],
742 s: &[S],
743 mod_op: &ModOp,
744 ntt_op: &NttOp,
745 seed: R::Seed,
746 rng: &mut R,
747) where
748 <Mmut as Matrix>::R:
749 RowMut + RowEntity + TryConvertFrom<[S], Parameters = Mmut::MatElement> + Debug,
750 Mmut::MatElement: Copy + Debug,
751 Mmut: Debug,
752{
753 let d = gadget_vector.len();
754 let q = mod_op.modulus();
755 let ring_size = s.len();
756 assert!(out_rgsw.dimension() == (d * 3, ring_size));
757 assert!(m.as_ref().len() == ring_size);
758
759 // RLWE(-sm), RLWE(m)
760 let (rlwe_dash_nsm, b_rlwe_dash_m) = out_rgsw.split_at_row_mut(d * 2);
761
762 let mut s_eval = Mmut::R::try_convert_from(s, &q);
763 ntt_op.forward(s_eval.as_mut());
764
765 let mut scratch_space = Mmut::R::zeros(ring_size);
766
767 // RLWE'(-sm)
768 let (a_rlwe_dash_nsm, b_rlwe_dash_nsm) = rlwe_dash_nsm.split_at_mut(d);
769 izip!(
770 a_rlwe_dash_nsm.iter_mut(),
771 b_rlwe_dash_nsm.iter_mut(),
772 gadget_vector.iter()
773 )
774 .for_each(|(ai, bi, beta_i)| {
775 // Sample a_i
776 RandomUniformDist::random_fill(rng, &q, ai.as_mut());
777
778 // a_i * s
779 scratch_space.as_mut().copy_from_slice(ai.as_ref());
780 ntt_op.forward(scratch_space.as_mut());
781 mod_op.elwise_mul_mut(scratch_space.as_mut(), s_eval.as_ref());
782 ntt_op.backward(scratch_space.as_mut());
783
784 // b_i = e_i + a_i * s
785 RandomGaussianDist::random_fill(rng, &q, bi.as_mut());
786 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.as_ref());
787
788 // a_i + \beta_i * m
789 mod_op.elwise_scalar_mul(scratch_space.as_mut(), m.as_ref(), beta_i);
790 mod_op.elwise_add_mut(ai.as_mut(), scratch_space.as_ref());
791 });
792
793 // RLWE(m)
794 let mut a_rlwe_dash_m = {
795 // polynomials of part A of RLWE'(m) are sampled from seed
796 let mut p_rng = R::new_with_seed(seed);
797 let mut a = Mmut::zeros(d, ring_size);
798 a.iter_rows_mut()
799 .for_each(|ai| RandomUniformDist::random_fill(&mut p_rng, &q, ai.as_mut()));
800 a
801 };
802
803 izip!(
804 a_rlwe_dash_m.iter_rows_mut(),
805 b_rlwe_dash_m.iter_mut(),
806 gadget_vector.iter()
807 )
808 .for_each(|(ai, bi, beta_i)| {
809 // ai * s
810 ntt_op.forward(ai.as_mut());
811 mod_op.elwise_mul_mut(ai.as_mut(), s_eval.as_ref());
812 ntt_op.backward(ai.as_mut());
813
814 // beta_i * m
815 mod_op.elwise_scalar_mul(scratch_space.as_mut(), m.as_ref(), beta_i);
816
817 // Sample e_i
818 RandomGaussianDist::random_fill(rng, &q, bi.as_mut());
819 // e_i + beta_i * m + ai*s
820 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.as_ref());
821 mod_op.elwise_add_mut(bi.as_mut(), ai.as_ref());
822 });
823}
824
825/// Encrypt polynomial m(X) as RLWE ciphertext.
826///
827/// - rlwe_out: returned RLWE ciphertext RLWE(m) in coefficient domain. RLWE
828/// ciphertext is a matirx with first row consiting polynomial `a` and the
829/// second rows consting polynomial `b`
830pub(crate) fn secret_key_encrypt_rlwe<
831 Ro: Row + RowMut + RowEntity,
832 ModOp: VectorOps<Element = Ro::Element>,
833 NttOp: Ntt<Element = Ro::Element>,
834 S,
835 R: RandomUniformDist<[Ro::Element], Parameters = Ro::Element>
836 + RandomGaussianDist<[Ro::Element], Parameters = Ro::Element>
837 + NewWithSeed,
838>(
839 m: &Ro,
840 b_rlwe_out: &mut Ro,
841 s: &[S],
842 mod_op: &ModOp,
843 ntt_op: &NttOp,
844 seed: R::Seed,
845 rng: &mut R,
846) where
847 Ro: TryConvertFrom<[S], Parameters = Ro::Element> + Debug,
848{
849 let ring_size = s.len();
850 assert!(m.as_ref().len() == ring_size);
851 assert!(b_rlwe_out.as_ref().len() == ring_size);
852
853 let q = mod_op.modulus();
854
855 // sample a
856 let mut a = {
857 let mut a = Ro::zeros(ring_size);
858 let mut p_rng = R::new_with_seed(seed);
859 RandomUniformDist::random_fill(&mut p_rng, &q, a.as_mut());
860 a
861 };
862
863 // s * a
864 let mut sa = Ro::try_convert_from(s, &q);
865 ntt_op.forward(sa.as_mut());
866 ntt_op.forward(a.as_mut());
867 mod_op.elwise_mul_mut(sa.as_mut(), a.as_ref());
868 ntt_op.backward(sa.as_mut());
869
870 // sample e
871 RandomGaussianDist::random_fill(rng, &q, b_rlwe_out.as_mut());
872 mod_op.elwise_add_mut(b_rlwe_out.as_mut(), m.as_ref());
873 mod_op.elwise_add_mut(b_rlwe_out.as_mut(), sa.as_ref());
874}
875
876/// Decrypts degree 1 RLWE ciphertext RLWE(m) and returns m
877///
878/// - rlwe_ct: input degree 1 ciphertext RLWE(m).
879pub(crate) fn decrypt_rlwe<
880 R: RowMut,
881 M: Matrix<MatElement = R::Element>,
882 ModOp: VectorOps<Element = R::Element>,
883 NttOp: Ntt<Element = R::Element>,
884 S,
885>(
886 rlwe_ct: &M,
887 s: &[S],
888 m_out: &mut R,
889 ntt_op: &NttOp,
890 mod_op: &ModOp,
891) where
892 R: TryConvertFrom<[S], Parameters = R::Element>,
893 R::Element: Copy,
894{
895 let ring_size = s.len();
896 assert!(rlwe_ct.dimension() == (2, ring_size));
897 assert!(m_out.as_ref().len() == ring_size);
898
899 // transform a to evluation form
900 m_out.as_mut().copy_from_slice(rlwe_ct.get_row_slice(0));
901 ntt_op.forward(m_out.as_mut());
902
903 // -s*a
904 let mut s = R::try_convert_from(&s, &mod_op.modulus());
905 ntt_op.forward(s.as_mut());
906 mod_op.elwise_mul_mut(m_out.as_mut(), s.as_ref());
907 mod_op.elwise_neg_mut(m_out.as_mut());
908 ntt_op.backward(m_out.as_mut());
909
910 // m+e = b - s*a
911 mod_op.elwise_add_mut(m_out.as_mut(), rlwe_ct.get_row_slice(1));
912}
913
914// Measures noise in degree 1 RLWE ciphertext against encoded ideal message
915// encoded_m
916pub(crate) fn measure_noise<
917 Mmut: MatrixMut + Matrix,
918 ModOp: VectorOps<Element = Mmut::MatElement>,
919 NttOp: Ntt<Element = Mmut::MatElement>,
920 S,
921>(
922 rlwe_ct: &Mmut,
923 encoded_m_ideal: &Mmut::R,
924 ntt_op: &NttOp,
925 mod_op: &ModOp,
926 s: &[S],
927) -> f64
928where
929 <Mmut as Matrix>::R: RowMut,
930 Mmut::R: RowEntity + TryConvertFrom<[S], Parameters = Mmut::MatElement>,
931 Mmut::MatElement: PrimInt + ToPrimitive + Debug,
932{
933 let ring_size = s.len();
934 assert!(rlwe_ct.dimension() == (2, ring_size));
935 assert!(encoded_m_ideal.as_ref().len() == ring_size);
936
937 // -(s * a)
938 let q = VectorOps::modulus(mod_op);
939 let mut s = Mmut::R::try_convert_from(s, &q);
940 ntt_op.forward(s.as_mut());
941 let mut a = Mmut::R::zeros(ring_size);
942 a.as_mut().copy_from_slice(rlwe_ct.get_row_slice(0));
943 ntt_op.forward(a.as_mut());
944 mod_op.elwise_mul_mut(s.as_mut(), a.as_ref());
945 mod_op.elwise_neg_mut(s.as_mut());
946 ntt_op.backward(s.as_mut());
947
948 // m+e = b - s*a
949 let mut m_plus_e = s;
950 mod_op.elwise_add_mut(m_plus_e.as_mut(), rlwe_ct.get_row_slice(1));
951
952 // difference
953 mod_op.elwise_sub_mut(m_plus_e.as_mut(), encoded_m_ideal.as_ref());
954
955 let mut max_diff_bits = f64::MIN;
956 m_plus_e.as_ref().iter().for_each(|v| {
957 let mut v = *v;
958
959 if v >= (q >> 1) {
960 // v is -ve
961 v = q - v;
962 }
963
964 let bits = (v.to_f64().unwrap()).log2();
965
966 if max_diff_bits < bits {
967 max_diff_bits = bits;
968 }
969 });
970
971 return max_diff_bits;
972}
973
974#[cfg(test)]
975mod tests {
976 use std::vec;
977
978 use itertools::{izip, Itertools};
979 use rand::{thread_rng, Rng};
980
981 use crate::{
982 backend::{ModInit, ModularOpsU64},
983 decomposer::{gadget_vector, DefaultDecomposer},
984 ntt::{self, Ntt, NttBackendU64, NttInit},
985 random::{DefaultSecureRng, RandomUniformDist},
986 rgsw::{
987 measure_noise, AutoKeyEvaluationDomain, RgswCiphertextEvaluationDomain, RlweCiphertext,
988 SeededAutoKey, SeededRgswCiphertext, SeededRlweCiphertext,
989 },
990 utils::{generate_prime, negacyclic_mul},
991 Matrix, Secret,
992 };
993
994 use super::{
995 decrypt_rlwe, galois_auto, galois_key_gen, generate_auto_map, rlwe_by_rgsw,
996 secret_key_encrypt_rgsw, secret_key_encrypt_rlwe, RlweSecret,
997 };
998
999 #[test]
1000 fn rlwe_encrypt_decryption() {
1001 let logq = 50;
1002 let logp = 2;
1003 let ring_size = 1 << 4;
1004 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
1005 let p = 1u64 << logp;
1006
1007 let mut rng = DefaultSecureRng::new();
1008
1009 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
1010
1011 // sample m0
1012 let mut m0 = vec![0u64; ring_size as usize];
1013 RandomUniformDist::<[u64]>::random_fill(&mut rng, &(1u64 << logp), m0.as_mut_slice());
1014
1015 let ntt_op = NttBackendU64::new(q, ring_size as usize);
1016 let mod_op = ModularOpsU64::new(q);
1017
1018 // encrypt m0
1019 let mut rlwe_seed = [0u8; 32];
1020 rng.fill_bytes(&mut rlwe_seed);
1021 let mut seeded_rlwe_in_ct =
1022 SeededRlweCiphertext::<_, [u8; 32]>::empty(ring_size as usize, rlwe_seed, q);
1023 let encoded_m = m0
1024 .iter()
1025 .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
1026 .collect_vec();
1027 secret_key_encrypt_rlwe(
1028 &encoded_m,
1029 &mut seeded_rlwe_in_ct.data,
1030 s.values(),
1031 &mod_op,
1032 &ntt_op,
1033 seeded_rlwe_in_ct.seed,
1034 &mut rng,
1035 );
1036 let rlwe_in_ct =
1037 RlweCiphertext::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_rlwe_in_ct);
1038
1039 let mut encoded_m_back = vec![0u64; ring_size as usize];
1040 decrypt_rlwe(
1041 &rlwe_in_ct,
1042 s.values(),
1043 &mut encoded_m_back,
1044 &ntt_op,
1045 &mod_op,
1046 );
1047 let m_back = encoded_m_back
1048 .iter()
1049 .map(|v| ((*v as f64 * p as f64) / q as f64).round() as u64)
1050 .collect_vec();
1051 assert_eq!(m0, m_back);
1052 }
1053
1054 #[test]
1055 fn rlwe_by_rgsw_works() {
1056 let logq = 24;
1057 let logp = 2;
1058 let ring_size = 1 << 4;
1059 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
1060 let p = 1u64 << logp;
1061 let d_rgsw = 2;
1062 let logb = 12;
1063
1064 let mut rng = DefaultSecureRng::new_seeded([0u8; 32]);
1065
1066 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
1067
1068 let mut m0 = vec![0u64; ring_size as usize];
1069 RandomUniformDist::<[u64]>::random_fill(&mut rng, &(1u64 << logp), m0.as_mut_slice());
1070 let mut m1 = vec![0u64; ring_size as usize];
1071 m1[thread_rng().gen_range(0..ring_size) as usize] = 1;
1072
1073 let ntt_op = NttBackendU64::new(q, ring_size as usize);
1074 let mod_op = ModularOpsU64::new(q);
1075
1076 // Encrypt m1 as RGSW(m1)
1077 let mut rgsw_seed = [0u8; 32];
1078 rng.fill_bytes(&mut rgsw_seed);
1079 let mut seeded_rgsw_ct = SeededRgswCiphertext::<Vec<Vec<u64>>, [u8; 32]>::empty(
1080 ring_size as usize,
1081 d_rgsw,
1082 rgsw_seed,
1083 q,
1084 );
1085 let gadget_vector = gadget_vector(logq, logb, d_rgsw);
1086 secret_key_encrypt_rgsw(
1087 &mut seeded_rgsw_ct.data,
1088 &m1,
1089 &gadget_vector,
1090 s.values(),
1091 &mod_op,
1092 &ntt_op,
1093 seeded_rgsw_ct.seed,
1094 &mut rng,
1095 );
1096 let rgsw_ct = RgswCiphertextEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(
1097 &seeded_rgsw_ct,
1098 );
1099
1100 // Encrypt m0 as RLWE(m0)
1101 let mut rlwe_seed = [0u8; 32];
1102 rng.fill_bytes(&mut rlwe_seed);
1103 let mut seeded_rlwe_in_ct =
1104 SeededRlweCiphertext::<_, [u8; 32]>::empty(ring_size as usize, rlwe_seed, q);
1105 let encoded_m = m0
1106 .iter()
1107 .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
1108 .collect_vec();
1109 secret_key_encrypt_rlwe(
1110 &encoded_m,
1111 &mut seeded_rlwe_in_ct.data,
1112 s.values(),
1113 &mod_op,
1114 &ntt_op,
1115 seeded_rlwe_in_ct.seed,
1116 &mut rng,
1117 );
1118 let mut rlwe_in_ct =
1119 RlweCiphertext::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_rlwe_in_ct);
1120
1121 // RLWE(m0m1) = RLWE(m0) x RGSW(m1)
1122 let mut scratch_space = vec![vec![0u64; ring_size as usize]; d_rgsw + 2];
1123 let decomposer = DefaultDecomposer::new(q, logb, d_rgsw);
1124 rlwe_by_rgsw(
1125 &mut rlwe_in_ct,
1126 &rgsw_ct.data,
1127 &mut scratch_space,
1128 &decomposer,
1129 &ntt_op,
1130 &mod_op,
1131 );
1132
1133 // Decrypt RLWE(m0m1)
1134 let mut encoded_m0m1_back = vec![0u64; ring_size as usize];
1135 decrypt_rlwe(
1136 &rlwe_in_ct,
1137 s.values(),
1138 &mut encoded_m0m1_back,
1139 &ntt_op,
1140 &mod_op,
1141 );
1142 let m0m1_back = encoded_m0m1_back
1143 .iter()
1144 .map(|v| (((*v as f64 * p as f64) / (q as f64)).round() as u64) % p)
1145 .collect_vec();
1146
1147 let mul_mod = |v0: &u64, v1: &u64| (v0 * v1) % p;
1148 let m0m1 = negacyclic_mul(&m0, &m1, mul_mod, p);
1149 assert!(
1150 m0m1 == m0m1_back,
1151 "Expected {:?} \n Got {:?}",
1152 m0m1,
1153 m0m1_back
1154 );
1155 }
1156
1157 #[test]
1158 fn galois_auto_works() {
1159 let logq = 50;
1160 let ring_size = 1 << 4;
1161 let q = generate_prime(logq, 2 * ring_size, 1u64 << logq).unwrap();
1162 let logp = 3;
1163 let p = 1u64 << logp;
1164 let d_rgsw = 10;
1165 let logb = 5;
1166
1167 let mut rng = DefaultSecureRng::new();
1168 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
1169
1170 let mut m = vec![0u64; ring_size as usize];
1171 RandomUniformDist::random_fill(&mut rng, &p, m.as_mut_slice());
1172 let encoded_m = m
1173 .iter()
1174 .map(|v| (((*v as f64 * q as f64) / (p as f64)).round() as u64))
1175 .collect_vec();
1176
1177 let ntt_op = NttBackendU64::new(q, ring_size as usize);
1178 let mod_op = ModularOpsU64::new(q);
1179
1180 // RLWE_{s}(m)
1181 let mut seed_rlwe = [0u8; 32];
1182 rng.fill_bytes(&mut seed_rlwe);
1183 let mut seeded_rlwe_m = SeededRlweCiphertext::empty(ring_size as usize, seed_rlwe, q);
1184 secret_key_encrypt_rlwe(
1185 &encoded_m,
1186 &mut seeded_rlwe_m.data,
1187 s.values(),
1188 &mod_op,
1189 &ntt_op,
1190 seeded_rlwe_m.seed,
1191 &mut rng,
1192 );
1193 let mut rlwe_m = RlweCiphertext::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_rlwe_m);
1194
1195 let auto_k = -5;
1196
1197 // Generate galois key to key switch from s^k to s
1198 let mut seed_auto = [0u8; 32];
1199 rng.fill_bytes(&mut seed_auto);
1200 let mut seeded_auto_key = SeededAutoKey::empty(ring_size as usize, d_rgsw, seed_auto, q);
1201 let gadget_vector = gadget_vector(logq, logb, d_rgsw);
1202 galois_key_gen(
1203 &mut seeded_auto_key.data,
1204 s.values(),
1205 auto_k,
1206 &gadget_vector,
1207 &mod_op,
1208 &ntt_op,
1209 seeded_auto_key.seed,
1210 &mut rng,
1211 );
1212 let auto_key =
1213 AutoKeyEvaluationDomain::<Vec<Vec<u64>>, DefaultSecureRng, NttBackendU64>::from(
1214 &seeded_auto_key,
1215 );
1216
1217 // Send RLWE_{s}(m) -> RLWE_{s}(m^k)
1218 let mut scratch_space = vec![vec![0u64; ring_size as usize]; d_rgsw + 2];
1219 let (auto_map_index, auto_map_sign) = generate_auto_map(ring_size as usize, auto_k);
1220 let decomposer = DefaultDecomposer::new(q, logb, d_rgsw);
1221 galois_auto(
1222 &mut rlwe_m,
1223 &auto_key.data,
1224 &mut scratch_space,
1225 &auto_map_index,
1226 &auto_map_sign,
1227 &mod_op,
1228 &ntt_op,
1229 &decomposer,
1230 );
1231
1232 let rlwe_m_k = rlwe_m;
1233
1234 // Decrypt RLWE_{s}(m^k) and check
1235 let mut encoded_m_k_back = vec![0u64; ring_size as usize];
1236 decrypt_rlwe(
1237 &rlwe_m_k,
1238 s.values(),
1239 &mut encoded_m_k_back,
1240 &ntt_op,
1241 &mod_op,
1242 );
1243 let m_k_back = encoded_m_k_back
1244 .iter()
1245 .map(|v| (((*v as f64 * p as f64) / q as f64).round() as u64) % p)
1246 .collect_vec();
1247
1248 let mut m_k = vec![0u64; ring_size as usize];
1249 // Send \delta m -> \delta m^k
1250 izip!(m.iter(), auto_map_index.iter(), auto_map_sign.iter()).for_each(
1251 |(v, to_index, sign)| {
1252 if !*sign {
1253 m_k[*to_index] = (p - *v) % p;
1254 } else {
1255 m_k[*to_index] = *v;
1256 }
1257 },
1258 );
1259
1260 {
1261 let encoded_m_k = m_k
1262 .iter()
1263 .map(|v| ((*v as f64 * q as f64) / p as f64).round() as u64)
1264 .collect_vec();
1265
1266 let noise = measure_noise(&rlwe_m_k, &encoded_m_k, &ntt_op, &mod_op, s.values());
1267 println!("Ksk noise: {noise}");
1268 }
1269
1270 // FIXME(Jay): Galios autormophism will incur high error unless we fix in
1271 // accurate decomoposition of Decomposer when q is prime
1272 assert_eq!(m_k_back, m_k);
1273 // dbg!(m_k_back, m_k, q);
1274 }
1275}