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 PR: RandomUniformDist<[Mmut::MatElement], Parameters = Mmut::MatElement>,
388>(
389 ksk_out: &mut Mmut,
390 neg_from_s: Mmut::R,
391 mut to_s: Mmut::R,
392 gadget_vector: &[Mmut::MatElement],
393 mod_op: &ModOp,
394 ntt_op: &NttOp,
395 p_rng: &mut PR,
396 rng: &mut R,
397) where
398 <Mmut as Matrix>::R: RowMut,
399{
400 let ring_size = neg_from_s.as_ref().len();
401 let d = gadget_vector.len();
402 assert!(ksk_out.dimension() == (d, ring_size));
403
404 let q = ArithmeticOps::modulus(mod_op);
405
406 ntt_op.forward(to_s.as_mut());
407
408 // RLWE'_{to_s}(-from_s)
409 let mut part_a = {
410 let mut a = Mmut::zeros(d, ring_size);
411 a.iter_rows_mut()
412 .for_each(|ai| RandomUniformDist::random_fill(p_rng, &q, ai.as_mut()));
413 a
414 };
415 izip!(
416 part_a.iter_rows_mut(),
417 ksk_out.iter_rows_mut(),
418 gadget_vector.iter(),
419 )
420 .for_each(|(ai, bi, beta_i)| {
421 // si * ai
422 ntt_op.forward(ai.as_mut());
423 mod_op.elwise_mul_mut(ai.as_mut(), to_s.as_ref());
424 ntt_op.backward(ai.as_mut());
425
426 // ei + to_s*ai
427 RandomGaussianDist::random_fill(rng, &q, bi.as_mut());
428 mod_op.elwise_add_mut(bi.as_mut(), ai.as_ref());
429
430 // beta_i * -from_s
431 // use ai as scratch space
432 mod_op.elwise_scalar_mul(ai.as_mut(), neg_from_s.as_ref(), beta_i);
433
434 // bi = ei + to_s*ai + beta_i*-from_s
435 mod_op.elwise_add_mut(bi.as_mut(), ai.as_ref());
436 });
437}
438
439pub(crate) fn galois_key_gen<
440 Mmut: MatrixMut + MatrixEntity,
441 ModOp: ArithmeticOps<Element = Mmut::MatElement> + VectorOps<Element = Mmut::MatElement>,
442 NttOp: Ntt<Element = Mmut::MatElement>,
443 S,
444 R: RandomGaussianDist<[Mmut::MatElement], Parameters = Mmut::MatElement>,
445 PR: RandomUniformDist<[Mmut::MatElement], Parameters = Mmut::MatElement>,
446>(
447 ksk_out: &mut Mmut,
448 s: &[S],
449 auto_k: isize,
450 gadget_vector: &[Mmut::MatElement],
451 mod_op: &ModOp,
452 ntt_op: &NttOp,
453 p_rng: &mut PR,
454 rng: &mut R,
455) where
456 <Mmut as Matrix>::R: RowMut,
457 Mmut::R: TryConvertFrom<[S], Parameters = Mmut::MatElement> + RowEntity,
458 Mmut::MatElement: Copy + Sub<Output = Mmut::MatElement>,
459{
460 let ring_size = s.len();
461 let (auto_map_index, auto_map_sign) = generate_auto_map(ring_size, auto_k);
462
463 let q = ArithmeticOps::modulus(mod_op);
464
465 // s(X) -> -s(X^k)
466 let s = Mmut::R::try_convert_from(s, &q);
467 let mut neg_s_auto = Mmut::R::zeros(s.as_ref().len());
468 izip!(s.as_ref(), auto_map_index.iter(), auto_map_sign.iter()).for_each(
469 |(el, to_index, sign)| {
470 // if sign is +ve (true), then negate because we need -s(X) (i.e. do the
471 // opposite than the usual case)
472 if *sign {
473 neg_s_auto.as_mut()[*to_index] = q - *el;
474 } else {
475 neg_s_auto.as_mut()[*to_index] = *el;
476 }
477 },
478 );
479
480 // Ksk from -s(X^k) to s(X)
481 rlwe_ksk_gen(
482 ksk_out,
483 neg_s_auto,
484 s,
485 gadget_vector,
486 mod_op,
487 ntt_op,
488 p_rng,
489 rng,
490 );
491}
492
493pub(crate) fn routine<M: Matrix + ?Sized, ModOp: VectorOps<Element = M::MatElement>>(
494 write_to_row: &mut [M::MatElement],
495 matrix_a: &[M::R],
496 matrix_b: &[M::R],
497 mod_op: &ModOp,
498) {
499 izip!(matrix_a.iter(), matrix_b.iter()).for_each(|(a, b)| {
500 mod_op.elwise_fma_mut(write_to_row, a.as_ref(), b.as_ref());
501 });
502}
503
504/// Decomposes ring polynomial r(X) into d polynomials using decomposer into
505/// output matrix decomp_r
506///
507/// Note that decomposition of r(X) requires decomposition of each of
508/// coefficients.
509///
510/// - decomp_r: must have dimensions d x ring_size. i^th decomposed polynomial
511/// will be stored at i^th row.
512pub(crate) fn decompose_r<M: Matrix + MatrixMut, D: Decomposer<Element = M::MatElement>>(
513 r: &[M::MatElement],
514 decomp_r: &mut [M::R],
515 decomposer: &D,
516) where
517 <M as Matrix>::R: RowMut,
518 M::MatElement: Copy,
519{
520 let ring_size = r.len();
521 let d = decomposer.d();
522
523 for ri in 0..ring_size {
524 let el_decomposed = decomposer.decompose(&r[ri]);
525 for j in 0..d {
526 decomp_r[j].as_mut()[ri] = el_decomposed[j];
527 }
528 }
529}
530
531/// Sends RLWE_{s}(X) -> RLWE_{s}(X^k) where k is some galois element
532pub(crate) fn galois_auto<
533 MT: Matrix + IsTrivial + MatrixMut,
534 Mmut: MatrixMut<MatElement = MT::MatElement>,
535 ModOp: ArithmeticOps<Element = MT::MatElement> + VectorOps<Element = MT::MatElement>,
536 NttOp: Ntt<Element = MT::MatElement>,
537 D: Decomposer<Element = MT::MatElement>,
538>(
539 rlwe_in: &mut MT,
540 ksk: &Mmut,
541 scratch_matrix_dplus2_ring: &mut Mmut,
542 auto_map_index: &[usize],
543 auto_map_sign: &[bool],
544 mod_op: &ModOp,
545 ntt_op: &NttOp,
546 decomposer: &D,
547) where
548 <Mmut as Matrix>::R: RowMut,
549 <MT as Matrix>::R: RowMut,
550 MT::MatElement: Copy + Zero,
551{
552 let d = decomposer.d();
553
554 let (scratch_matrix_d_ring, tmp_rlwe_out) = scratch_matrix_dplus2_ring.split_at_row_mut(d);
555
556 // send b(X) -> b(X^k)
557 izip!(
558 rlwe_in.get_row(1),
559 auto_map_index.iter(),
560 auto_map_sign.iter()
561 )
562 .for_each(|(el_in, to_index, sign)| {
563 if !*sign {
564 tmp_rlwe_out[1].as_mut()[*to_index] = mod_op.neg(el_in);
565 } else {
566 tmp_rlwe_out[1].as_mut()[*to_index] = *el_in;
567 // scratch_matrix_dplus2_ring.set(d + 1, *to_index, *el_in);
568 }
569 });
570
571 if !rlwe_in.is_trivial() {
572 // send a(X) -> a(X^k) and decompose a(X^k)
573 izip!(
574 rlwe_in.get_row(0),
575 auto_map_index.iter(),
576 auto_map_sign.iter()
577 )
578 .for_each(|(el_in, to_index, sign)| {
579 let el_out = if !*sign { mod_op.neg(el_in) } else { *el_in };
580
581 let el_out_decomposed = decomposer.decompose(&el_out);
582 for j in 0..d {
583 scratch_matrix_d_ring[j].as_mut()[*to_index] = el_out_decomposed[j];
584 }
585 });
586
587 // transform decomposed a(X^k) to evaluation domain
588 scratch_matrix_d_ring.iter_mut().for_each(|r| {
589 ntt_op.forward(r.as_mut());
590 });
591
592 // RLWE(m^k) = a', b'; RLWE(m) = a, b
593 // key switch: (a * RLWE'(s(X^k)))
594 let (ksk_a, ksk_b) = ksk.split_at_row(d);
595 tmp_rlwe_out[0].as_mut().fill(Mmut::MatElement::zero());
596 // a' = decomp<a> * RLWE'_A(s(X^k))
597 routine::<Mmut, ModOp>(
598 tmp_rlwe_out[0].as_mut(),
599 scratch_matrix_d_ring,
600 ksk_a,
601 mod_op,
602 );
603 // send b(X^k) to evaluation domain
604 ntt_op.forward(tmp_rlwe_out[1].as_mut());
605 // b' = b(X^k)
606 // b' += decomp<a(X^k)> * RLWE'_B(s(X^k))
607 routine::<Mmut, ModOp>(
608 tmp_rlwe_out[1].as_mut(),
609 scratch_matrix_d_ring,
610 ksk_b,
611 mod_op,
612 );
613
614 // transform RLWE(m^k) to coefficient domain
615 tmp_rlwe_out
616 .iter_mut()
617 .for_each(|r| ntt_op.backward(r.as_mut()));
618
619 rlwe_in
620 .get_row_mut(0)
621 .copy_from_slice(tmp_rlwe_out[0].as_ref());
622 }
623
624 rlwe_in
625 .get_row_mut(1)
626 .copy_from_slice(tmp_rlwe_out[1].as_ref());
627}
628
629/// Returns RLWE(m0m1) = RLWE(m0) x RGSW(m1). Mutates rlwe_in inplace to equal
630/// RLWE(m0m1)
631///
632/// - rlwe_in: is RLWE(m0) with polynomials in coefficient domain
633/// - rgsw_in: is RGSW(m1) with polynomials in evaluation domain
634/// - scratch_matrix_d_ring: is a matrix of dimension (d_rgsw, ring_size) used
635/// as scratch space to store decomposed Ring elements temporarily
636pub(crate) fn rlwe_by_rgsw<
637 Mmut: MatrixMut,
638 MT: Matrix<MatElement = Mmut::MatElement> + MatrixMut<MatElement = Mmut::MatElement> + IsTrivial,
639 D: Decomposer<Element = Mmut::MatElement>,
640 ModOp: VectorOps<Element = Mmut::MatElement>,
641 NttOp: Ntt<Element = Mmut::MatElement>,
642>(
643 rlwe_in: &mut MT,
644 rgsw_in: &Mmut,
645 scratch_matrix_dplus2_ring: &mut Mmut,
646 decomposer: &D,
647 ntt_op: &NttOp,
648 mod_op: &ModOp,
649) where
650 Mmut::MatElement: Copy + Zero,
651 <Mmut as Matrix>::R: RowMut,
652 <MT as Matrix>::R: RowMut,
653{
654 let d_rgsw = decomposer.d();
655 assert!(scratch_matrix_dplus2_ring.dimension() == (d_rgsw + 2, rlwe_in.dimension().1));
656 assert!(rgsw_in.dimension() == (d_rgsw * 4, rlwe_in.dimension().1));
657
658 // decomposed RLWE x RGSW
659 let (rlwe_dash_nsm, rlwe_dash_m) = rgsw_in.split_at_row(d_rgsw * 2);
660 let (scratch_matrix_d_ring, scratch_rlwe_out) =
661 scratch_matrix_dplus2_ring.split_at_row_mut(d_rgsw);
662 scratch_rlwe_out[0].as_mut().fill(Mmut::MatElement::zero());
663 scratch_rlwe_out[1].as_mut().fill(Mmut::MatElement::zero());
664 // RLWE_in = a_in, b_in; RLWE_out = a_out, b_out
665 if !rlwe_in.is_trivial() {
666 // a_in = 0 when RLWE_in is trivial RLWE ciphertext
667 // decomp<a_in>
668 decompose_r::<Mmut, D>(rlwe_in.get_row_slice(0), scratch_matrix_d_ring, decomposer);
669 scratch_matrix_d_ring
670 .iter_mut()
671 .for_each(|r| ntt_op.forward(r.as_mut()));
672 // a_out += decomp<a_in> \cdot RLWE_A'(-sm)
673 routine::<Mmut, ModOp>(
674 scratch_rlwe_out[0].as_mut(),
675 scratch_matrix_d_ring.as_ref(),
676 &rlwe_dash_nsm[..d_rgsw],
677 mod_op,
678 );
679 // b_out += decomp<a_in> \cdot RLWE_B'(-sm)
680 routine::<Mmut, ModOp>(
681 scratch_rlwe_out[1].as_mut(),
682 scratch_matrix_d_ring.as_ref(),
683 &rlwe_dash_nsm[d_rgsw..],
684 mod_op,
685 );
686 }
687 // decomp<b_in>
688 decompose_r::<Mmut, D>(rlwe_in.get_row_slice(1), scratch_matrix_d_ring, decomposer);
689 scratch_matrix_d_ring
690 .iter_mut()
691 .for_each(|r| ntt_op.forward(r.as_mut()));
692 // a_out += decomp<b_in> \cdot RLWE_A'(m)
693 routine::<Mmut, ModOp>(
694 scratch_rlwe_out[0].as_mut(),
695 scratch_matrix_d_ring.as_ref(),
696 &rlwe_dash_m[..d_rgsw],
697 mod_op,
698 );
699 // b_out += decomp<b_in> \cdot RLWE_B'(m)
700 routine::<Mmut, ModOp>(
701 scratch_rlwe_out[1].as_mut(),
702 scratch_matrix_d_ring.as_ref(),
703 &rlwe_dash_m[d_rgsw..],
704 mod_op,
705 );
706
707 // transform rlwe_out to coefficient domain
708 scratch_rlwe_out
709 .iter_mut()
710 .for_each(|r| ntt_op.backward(r.as_mut()));
711
712 rlwe_in
713 .get_row_mut(0)
714 .copy_from_slice(scratch_rlwe_out[0].as_mut());
715 rlwe_in
716 .get_row_mut(1)
717 .copy_from_slice(scratch_rlwe_out[1].as_mut());
718 rlwe_in.set_not_trivial();
719}
720
721/// Encrypts message m as a RGSW ciphertext.
722///
723/// - m_eval: is `m` is evaluation domain
724/// - out_rgsw: RGSW(m) is stored as single matrix of dimension (d_rgsw * 3,
725/// ring_size). The matrix has the following structure [RLWE'_A(-sm) ||
726/// RLWE'_B(-sm) || RLWE'_B(m)]^T and RLWE'_A(m) is generated via seed
727pub(crate) fn secret_key_encrypt_rgsw<
728 Mmut: MatrixMut + MatrixEntity,
729 S,
730 R: RandomGaussianDist<[Mmut::MatElement], Parameters = Mmut::MatElement>
731 + RandomUniformDist<[Mmut::MatElement], Parameters = Mmut::MatElement>,
732 PR: RandomUniformDist<[Mmut::MatElement], Parameters = Mmut::MatElement>,
733 ModOp: VectorOps<Element = Mmut::MatElement>,
734 NttOp: Ntt<Element = Mmut::MatElement>,
735>(
736 out_rgsw: &mut Mmut,
737 m: &Mmut::R,
738 gadget_vector: &[Mmut::MatElement],
739 s: &[S],
740 mod_op: &ModOp,
741 ntt_op: &NttOp,
742 p_rng: &mut PR,
743 rng: &mut R,
744) where
745 <Mmut as Matrix>::R: RowMut + RowEntity + TryConvertFrom<[S], Parameters = Mmut::MatElement>,
746 Mmut::MatElement: Copy,
747{
748 let d = gadget_vector.len();
749 let q = mod_op.modulus();
750 let ring_size = s.len();
751 assert!(out_rgsw.dimension() == (d * 3, ring_size));
752 assert!(m.as_ref().len() == ring_size);
753
754 // RLWE(-sm), RLWE(m)
755 let (rlwe_dash_nsm, b_rlwe_dash_m) = out_rgsw.split_at_row_mut(d * 2);
756
757 let mut s_eval = Mmut::R::try_convert_from(s, &q);
758 ntt_op.forward(s_eval.as_mut());
759
760 let mut scratch_space = Mmut::R::zeros(ring_size);
761
762 // RLWE'(-sm)
763 let (a_rlwe_dash_nsm, b_rlwe_dash_nsm) = rlwe_dash_nsm.split_at_mut(d);
764 izip!(
765 a_rlwe_dash_nsm.iter_mut(),
766 b_rlwe_dash_nsm.iter_mut(),
767 gadget_vector.iter()
768 )
769 .for_each(|(ai, bi, beta_i)| {
770 // Sample a_i
771 RandomUniformDist::random_fill(rng, &q, ai.as_mut());
772
773 // a_i * s
774 scratch_space.as_mut().copy_from_slice(ai.as_ref());
775 ntt_op.forward(scratch_space.as_mut());
776 mod_op.elwise_mul_mut(scratch_space.as_mut(), s_eval.as_ref());
777 ntt_op.backward(scratch_space.as_mut());
778
779 // b_i = e_i + a_i * s
780 RandomGaussianDist::random_fill(rng, &q, bi.as_mut());
781 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.as_ref());
782
783 // a_i + \beta_i * m
784 mod_op.elwise_scalar_mul(scratch_space.as_mut(), m.as_ref(), beta_i);
785 mod_op.elwise_add_mut(ai.as_mut(), scratch_space.as_ref());
786 });
787
788 // RLWE(m)
789 let mut a_rlwe_dash_m = {
790 // polynomials of part A of RLWE'(m) are sampled from seed
791 let mut a = Mmut::zeros(d, ring_size);
792 a.iter_rows_mut()
793 .for_each(|ai| RandomUniformDist::random_fill(p_rng, &q, ai.as_mut()));
794 a
795 };
796
797 izip!(
798 a_rlwe_dash_m.iter_rows_mut(),
799 b_rlwe_dash_m.iter_mut(),
800 gadget_vector.iter()
801 )
802 .for_each(|(ai, bi, beta_i)| {
803 // ai * s
804 ntt_op.forward(ai.as_mut());
805 mod_op.elwise_mul_mut(ai.as_mut(), s_eval.as_ref());
806 ntt_op.backward(ai.as_mut());
807
808 // beta_i * m
809 mod_op.elwise_scalar_mul(scratch_space.as_mut(), m.as_ref(), beta_i);
810
811 // Sample e_i
812 RandomGaussianDist::random_fill(rng, &q, bi.as_mut());
813 // e_i + beta_i * m + ai*s
814 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.as_ref());
815 mod_op.elwise_add_mut(bi.as_mut(), ai.as_ref());
816 });
817}
818
819/// Encrypt polynomial m(X) as RLWE ciphertext.
820///
821/// - rlwe_out: returned RLWE ciphertext RLWE(m) in coefficient domain. RLWE
822/// ciphertext is a matirx with first row consiting polynomial `a` and the
823/// second rows consting polynomial `b`
824pub(crate) fn secret_key_encrypt_rlwe<
825 Ro: Row + RowMut + RowEntity,
826 ModOp: VectorOps<Element = Ro::Element>,
827 NttOp: Ntt<Element = Ro::Element>,
828 S,
829 R: RandomGaussianDist<[Ro::Element], Parameters = Ro::Element>,
830 PR: RandomUniformDist<[Ro::Element], Parameters = Ro::Element>,
831>(
832 m: &Ro,
833 b_rlwe_out: &mut Ro,
834 s: &[S],
835 mod_op: &ModOp,
836 ntt_op: &NttOp,
837 p_rng: &mut PR,
838 rng: &mut R,
839) where
840 Ro: TryConvertFrom<[S], Parameters = Ro::Element> + Debug,
841{
842 let ring_size = s.len();
843 assert!(m.as_ref().len() == ring_size);
844 assert!(b_rlwe_out.as_ref().len() == ring_size);
845
846 let q = mod_op.modulus();
847
848 // sample a
849 let mut a = {
850 let mut a = Ro::zeros(ring_size);
851 RandomUniformDist::random_fill(p_rng, &q, a.as_mut());
852 a
853 };
854
855 // s * a
856 let mut sa = Ro::try_convert_from(s, &q);
857 ntt_op.forward(sa.as_mut());
858 ntt_op.forward(a.as_mut());
859 mod_op.elwise_mul_mut(sa.as_mut(), a.as_ref());
860 ntt_op.backward(sa.as_mut());
861
862 // sample e
863 RandomGaussianDist::random_fill(rng, &q, b_rlwe_out.as_mut());
864 mod_op.elwise_add_mut(b_rlwe_out.as_mut(), m.as_ref());
865 mod_op.elwise_add_mut(b_rlwe_out.as_mut(), sa.as_ref());
866}
867
868/// Decrypts degree 1 RLWE ciphertext RLWE(m) and returns m
869///
870/// - rlwe_ct: input degree 1 ciphertext RLWE(m).
871pub(crate) fn decrypt_rlwe<
872 R: RowMut,
873 M: Matrix<MatElement = R::Element>,
874 ModOp: VectorOps<Element = R::Element>,
875 NttOp: Ntt<Element = R::Element>,
876 S,
877>(
878 rlwe_ct: &M,
879 s: &[S],
880 m_out: &mut R,
881 ntt_op: &NttOp,
882 mod_op: &ModOp,
883) where
884 R: TryConvertFrom<[S], Parameters = R::Element>,
885 R::Element: Copy,
886{
887 let ring_size = s.len();
888 assert!(rlwe_ct.dimension() == (2, ring_size));
889 assert!(m_out.as_ref().len() == ring_size);
890
891 // transform a to evluation form
892 m_out.as_mut().copy_from_slice(rlwe_ct.get_row_slice(0));
893 ntt_op.forward(m_out.as_mut());
894
895 // -s*a
896 let mut s = R::try_convert_from(&s, &mod_op.modulus());
897 ntt_op.forward(s.as_mut());
898 mod_op.elwise_mul_mut(m_out.as_mut(), s.as_ref());
899 mod_op.elwise_neg_mut(m_out.as_mut());
900 ntt_op.backward(m_out.as_mut());
901
902 // m+e = b - s*a
903 mod_op.elwise_add_mut(m_out.as_mut(), rlwe_ct.get_row_slice(1));
904}
905
906// Measures noise in degree 1 RLWE ciphertext against encoded ideal message
907// encoded_m
908pub(crate) fn measure_noise<
909 Mmut: MatrixMut + Matrix,
910 ModOp: VectorOps<Element = Mmut::MatElement>,
911 NttOp: Ntt<Element = Mmut::MatElement>,
912 S,
913>(
914 rlwe_ct: &Mmut,
915 encoded_m_ideal: &Mmut::R,
916 ntt_op: &NttOp,
917 mod_op: &ModOp,
918 s: &[S],
919) -> f64
920where
921 <Mmut as Matrix>::R: RowMut,
922 Mmut::R: RowEntity + TryConvertFrom<[S], Parameters = Mmut::MatElement>,
923 Mmut::MatElement: PrimInt + ToPrimitive + Debug,
924{
925 let ring_size = s.len();
926 assert!(rlwe_ct.dimension() == (2, ring_size));
927 assert!(encoded_m_ideal.as_ref().len() == ring_size);
928
929 // -(s * a)
930 let q = VectorOps::modulus(mod_op);
931 let mut s = Mmut::R::try_convert_from(s, &q);
932 ntt_op.forward(s.as_mut());
933 let mut a = Mmut::R::zeros(ring_size);
934 a.as_mut().copy_from_slice(rlwe_ct.get_row_slice(0));
935 ntt_op.forward(a.as_mut());
936 mod_op.elwise_mul_mut(s.as_mut(), a.as_ref());
937 mod_op.elwise_neg_mut(s.as_mut());
938 ntt_op.backward(s.as_mut());
939
940 // m+e = b - s*a
941 let mut m_plus_e = s;
942 mod_op.elwise_add_mut(m_plus_e.as_mut(), rlwe_ct.get_row_slice(1));
943
944 // difference
945 mod_op.elwise_sub_mut(m_plus_e.as_mut(), encoded_m_ideal.as_ref());
946
947 let mut max_diff_bits = f64::MIN;
948 m_plus_e.as_ref().iter().for_each(|v| {
949 let mut v = *v;
950
951 if v >= (q >> 1) {
952 // v is -ve
953 v = q - v;
954 }
955
956 let bits = (v.to_f64().unwrap()).log2();
957
958 if max_diff_bits < bits {
959 max_diff_bits = bits;
960 }
961 });
962
963 return max_diff_bits;
964}
965
966#[cfg(test)]
967mod tests {
968 use std::vec;
969
970 use itertools::{izip, Itertools};
971 use rand::{thread_rng, Rng};
972
973 use crate::{
974 backend::{ModInit, ModularOpsU64},
975 decomposer::{gadget_vector, DefaultDecomposer},
976 ntt::{self, Ntt, NttBackendU64, NttInit},
977 random::{DefaultSecureRng, NewWithSeed, RandomUniformDist},
978 rgsw::{
979 measure_noise, AutoKeyEvaluationDomain, RgswCiphertextEvaluationDomain, RlweCiphertext,
980 SeededAutoKey, SeededRgswCiphertext, SeededRlweCiphertext,
981 },
982 utils::{generate_prime, negacyclic_mul},
983 Matrix, Secret,
984 };
985
986 use super::{
987 decrypt_rlwe, galois_auto, galois_key_gen, generate_auto_map, rlwe_by_rgsw,
988 secret_key_encrypt_rgsw, secret_key_encrypt_rlwe, RlweSecret,
989 };
990
991 #[test]
992 fn rlwe_encrypt_decryption() {
993 let logq = 50;
994 let logp = 2;
995 let ring_size = 1 << 4;
996 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
997 let p = 1u64 << logp;
998
999 let mut rng = DefaultSecureRng::new();
1000
1001 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
1002
1003 // sample m0
1004 let mut m0 = vec![0u64; ring_size as usize];
1005 RandomUniformDist::<[u64]>::random_fill(&mut rng, &(1u64 << logp), m0.as_mut_slice());
1006
1007 let ntt_op = NttBackendU64::new(q, ring_size as usize);
1008 let mod_op = ModularOpsU64::new(q);
1009
1010 // encrypt m0
1011 let mut rlwe_seed = [0u8; 32];
1012 rng.fill_bytes(&mut rlwe_seed);
1013 let mut seeded_rlwe_in_ct =
1014 SeededRlweCiphertext::<_, [u8; 32]>::empty(ring_size as usize, rlwe_seed, q);
1015 let mut p_rng = DefaultSecureRng::new_with_seed(rlwe_seed);
1016 let encoded_m = m0
1017 .iter()
1018 .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
1019 .collect_vec();
1020 secret_key_encrypt_rlwe(
1021 &encoded_m,
1022 &mut seeded_rlwe_in_ct.data,
1023 s.values(),
1024 &mod_op,
1025 &ntt_op,
1026 &mut p_rng,
1027 &mut rng,
1028 );
1029 let rlwe_in_ct =
1030 RlweCiphertext::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_rlwe_in_ct);
1031
1032 let mut encoded_m_back = vec![0u64; ring_size as usize];
1033 decrypt_rlwe(
1034 &rlwe_in_ct,
1035 s.values(),
1036 &mut encoded_m_back,
1037 &ntt_op,
1038 &mod_op,
1039 );
1040 let m_back = encoded_m_back
1041 .iter()
1042 .map(|v| (((*v as f64 * p as f64) / q as f64).round() as u64) % p)
1043 .collect_vec();
1044 assert_eq!(m0, m_back);
1045 }
1046
1047 #[test]
1048 fn rlwe_by_rgsw_works() {
1049 let logq = 24;
1050 let logp = 2;
1051 let ring_size = 1 << 4;
1052 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
1053 let p = 1u64 << logp;
1054 let d_rgsw = 2;
1055 let logb = 12;
1056
1057 let mut rng = DefaultSecureRng::new_seeded([0u8; 32]);
1058
1059 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
1060
1061 let mut m0 = vec![0u64; ring_size as usize];
1062 RandomUniformDist::<[u64]>::random_fill(&mut rng, &(1u64 << logp), m0.as_mut_slice());
1063 let mut m1 = vec![0u64; ring_size as usize];
1064 m1[thread_rng().gen_range(0..ring_size) as usize] = 1;
1065
1066 let ntt_op = NttBackendU64::new(q, ring_size as usize);
1067 let mod_op = ModularOpsU64::new(q);
1068
1069 // Encrypt m1 as RGSW(m1)
1070 let mut rgsw_seed = [0u8; 32];
1071 rng.fill_bytes(&mut rgsw_seed);
1072 let mut seeded_rgsw_ct = SeededRgswCiphertext::<Vec<Vec<u64>>, [u8; 32]>::empty(
1073 ring_size as usize,
1074 d_rgsw,
1075 rgsw_seed,
1076 q,
1077 );
1078 let mut p_rng = DefaultSecureRng::new_seeded(rgsw_seed);
1079 let gadget_vector = gadget_vector(logq, logb, d_rgsw);
1080 secret_key_encrypt_rgsw(
1081 &mut seeded_rgsw_ct.data,
1082 &m1,
1083 &gadget_vector,
1084 s.values(),
1085 &mod_op,
1086 &ntt_op,
1087 &mut p_rng,
1088 &mut rng,
1089 );
1090 let rgsw_ct = RgswCiphertextEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(
1091 &seeded_rgsw_ct,
1092 );
1093
1094 // Encrypt m0 as RLWE(m0)
1095 let mut rlwe_seed = [0u8; 32];
1096 rng.fill_bytes(&mut rlwe_seed);
1097 let mut seeded_rlwe_in_ct =
1098 SeededRlweCiphertext::<_, [u8; 32]>::empty(ring_size as usize, rlwe_seed, q);
1099 let mut p_rng = DefaultSecureRng::new_seeded(rlwe_seed);
1100 let encoded_m = m0
1101 .iter()
1102 .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
1103 .collect_vec();
1104 secret_key_encrypt_rlwe(
1105 &encoded_m,
1106 &mut seeded_rlwe_in_ct.data,
1107 s.values(),
1108 &mod_op,
1109 &ntt_op,
1110 &mut p_rng,
1111 &mut rng,
1112 );
1113 let mut rlwe_in_ct =
1114 RlweCiphertext::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_rlwe_in_ct);
1115
1116 // RLWE(m0m1) = RLWE(m0) x RGSW(m1)
1117 let mut scratch_space = vec![vec![0u64; ring_size as usize]; d_rgsw + 2];
1118 let decomposer = DefaultDecomposer::new(q, logb, d_rgsw);
1119 rlwe_by_rgsw(
1120 &mut rlwe_in_ct,
1121 &rgsw_ct.data,
1122 &mut scratch_space,
1123 &decomposer,
1124 &ntt_op,
1125 &mod_op,
1126 );
1127
1128 // Decrypt RLWE(m0m1)
1129 let mut encoded_m0m1_back = vec![0u64; ring_size as usize];
1130 decrypt_rlwe(
1131 &rlwe_in_ct,
1132 s.values(),
1133 &mut encoded_m0m1_back,
1134 &ntt_op,
1135 &mod_op,
1136 );
1137 let m0m1_back = encoded_m0m1_back
1138 .iter()
1139 .map(|v| (((*v as f64 * p as f64) / (q as f64)).round() as u64) % p)
1140 .collect_vec();
1141
1142 let mul_mod = |v0: &u64, v1: &u64| (v0 * v1) % p;
1143 let m0m1 = negacyclic_mul(&m0, &m1, mul_mod, p);
1144 assert!(
1145 m0m1 == m0m1_back,
1146 "Expected {:?} \n Got {:?}",
1147 m0m1,
1148 m0m1_back
1149 );
1150 }
1151
1152 #[test]
1153 fn galois_auto_works() {
1154 let logq = 50;
1155 let ring_size = 1 << 4;
1156 let q = generate_prime(logq, 2 * ring_size, 1u64 << logq).unwrap();
1157 let logp = 3;
1158 let p = 1u64 << logp;
1159 let d_rgsw = 10;
1160 let logb = 5;
1161
1162 let mut rng = DefaultSecureRng::new();
1163 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
1164
1165 let mut m = vec![0u64; ring_size as usize];
1166 RandomUniformDist::random_fill(&mut rng, &p, m.as_mut_slice());
1167 let encoded_m = m
1168 .iter()
1169 .map(|v| (((*v as f64 * q as f64) / (p as f64)).round() as u64))
1170 .collect_vec();
1171
1172 let ntt_op = NttBackendU64::new(q, ring_size as usize);
1173 let mod_op = ModularOpsU64::new(q);
1174
1175 // RLWE_{s}(m)
1176 let mut seed_rlwe = [0u8; 32];
1177 rng.fill_bytes(&mut seed_rlwe);
1178 let mut seeded_rlwe_m = SeededRlweCiphertext::empty(ring_size as usize, seed_rlwe, q);
1179 let mut p_rng = DefaultSecureRng::new_seeded(seed_rlwe);
1180 secret_key_encrypt_rlwe(
1181 &encoded_m,
1182 &mut seeded_rlwe_m.data,
1183 s.values(),
1184 &mod_op,
1185 &ntt_op,
1186 &mut p_rng,
1187 &mut rng,
1188 );
1189 let mut rlwe_m = RlweCiphertext::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_rlwe_m);
1190
1191 let auto_k = -5;
1192
1193 // Generate galois key to key switch from s^k to s
1194 let mut seed_auto = [0u8; 32];
1195 rng.fill_bytes(&mut seed_auto);
1196 let mut seeded_auto_key = SeededAutoKey::empty(ring_size as usize, d_rgsw, seed_auto, q);
1197 let mut p_rng = DefaultSecureRng::new_seeded(seed_auto);
1198 let gadget_vector = gadget_vector(logq, logb, d_rgsw);
1199 galois_key_gen(
1200 &mut seeded_auto_key.data,
1201 s.values(),
1202 auto_k,
1203 &gadget_vector,
1204 &mod_op,
1205 &ntt_op,
1206 &mut p_rng,
1207 &mut rng,
1208 );
1209 let auto_key =
1210 AutoKeyEvaluationDomain::<Vec<Vec<u64>>, DefaultSecureRng, NttBackendU64>::from(
1211 &seeded_auto_key,
1212 );
1213
1214 // Send RLWE_{s}(m) -> RLWE_{s}(m^k)
1215 let mut scratch_space = vec![vec![0u64; ring_size as usize]; d_rgsw + 2];
1216 let (auto_map_index, auto_map_sign) = generate_auto_map(ring_size as usize, auto_k);
1217 let decomposer = DefaultDecomposer::new(q, logb, d_rgsw);
1218 galois_auto(
1219 &mut rlwe_m,
1220 &auto_key.data,
1221 &mut scratch_space,
1222 &auto_map_index,
1223 &auto_map_sign,
1224 &mod_op,
1225 &ntt_op,
1226 &decomposer,
1227 );
1228
1229 let rlwe_m_k = rlwe_m;
1230
1231 // Decrypt RLWE_{s}(m^k) and check
1232 let mut encoded_m_k_back = vec![0u64; ring_size as usize];
1233 decrypt_rlwe(
1234 &rlwe_m_k,
1235 s.values(),
1236 &mut encoded_m_k_back,
1237 &ntt_op,
1238 &mod_op,
1239 );
1240 let m_k_back = encoded_m_k_back
1241 .iter()
1242 .map(|v| (((*v as f64 * p as f64) / q as f64).round() as u64) % p)
1243 .collect_vec();
1244
1245 let mut m_k = vec![0u64; ring_size as usize];
1246 // Send \delta m -> \delta m^k
1247 izip!(m.iter(), auto_map_index.iter(), auto_map_sign.iter()).for_each(
1248 |(v, to_index, sign)| {
1249 if !*sign {
1250 m_k[*to_index] = (p - *v) % p;
1251 } else {
1252 m_k[*to_index] = *v;
1253 }
1254 },
1255 );
1256
1257 {
1258 let encoded_m_k = m_k
1259 .iter()
1260 .map(|v| ((*v as f64 * q as f64) / p as f64).round() as u64)
1261 .collect_vec();
1262
1263 let noise = measure_noise(&rlwe_m_k, &encoded_m_k, &ntt_op, &mod_op, s.values());
1264 println!("Ksk noise: {noise}");
1265 }
1266
1267 // FIXME(Jay): Galios autormophism will incur high error unless we fix in
1268 // accurate decomoposition of Decomposer when q is prime
1269 assert_eq!(m_k_back, m_k);
1270 // dbg!(m_k_back, m_k, q);
1271 }
1272}