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