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, Signed, ToPrimitive, Zero};
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, TryConvertFrom1, WithLocal},
20 Matrix, MatrixEntity, MatrixMut, Row, RowEntity, RowMut, Secret,
21};
22
23pub struct SeededAutoKey<M, S, Mod>
24where
25 M: Matrix,
26{
27 data: M,
28 seed: S,
29 modulus: Mod,
30}
31
32impl<M: Matrix + MatrixEntity, S, Mod: Modulus<Element = M::MatElement>> SeededAutoKey<M, S, Mod> {
33 fn empty<D: Decomposer>(ring_size: usize, auto_decomposer: &D, seed: S, modulus: Mod) -> Self {
34 SeededAutoKey {
35 data: M::zeros(auto_decomposer.decomposition_count(), ring_size),
36 seed,
37 modulus,
38 }
39 }
40}
41
42pub struct AutoKeyEvaluationDomain<M, R, N> {
43 data: M,
44 _phantom: PhantomData<(R, N)>,
45}
46
47impl<
48 M: MatrixMut + MatrixEntity,
49 Mod: Modulus<Element = M::MatElement> + Clone,
50 R: RandomFillUniformInModulus<[M::MatElement], Mod> + NewWithSeed,
51 N: NttInit<Mod> + Ntt<Element = M::MatElement>,
52 > From<&SeededAutoKey<M, R::Seed, Mod>> for AutoKeyEvaluationDomain<M, R, N>
53where
54 <M as Matrix>::R: RowMut,
55 M::MatElement: Copy,
56 R::Seed: Clone,
57{
58 fn from(value: &SeededAutoKey<M, R::Seed, Mod>) -> Self {
59 let (d, ring_size) = value.data.dimension();
60 let mut data = M::zeros(2 * d, ring_size);
61
62 // sample RLWE'_A(-s(X^k))
63 let mut p_rng = R::new_with_seed(value.seed.clone());
64 data.iter_rows_mut().take(d).for_each(|r| {
65 RandomFillUniformInModulus::random_fill(&mut p_rng, &value.modulus, r.as_mut());
66 });
67
68 // copy over RLWE'_B(-s(X^k))
69 izip!(data.iter_rows_mut().skip(d), value.data.iter_rows()).for_each(|(to_r, from_r)| {
70 to_r.as_mut().copy_from_slice(from_r.as_ref());
71 });
72
73 // send RLWE'(-s(X^k)) polynomials to evaluation domain
74 let ntt_op = N::new(&value.modulus, ring_size);
75 data.iter_rows_mut()
76 .for_each(|r| ntt_op.forward(r.as_mut()));
77
78 AutoKeyEvaluationDomain {
79 data,
80 _phantom: PhantomData,
81 }
82 }
83}
84
85pub struct RgswCiphertext<M: Matrix, Mod> {
86 /// Rgsw ciphertext polynomials
87 pub(crate) data: M,
88 modulus: Mod,
89 /// Decomposition for RLWE part A
90 d_a: usize,
91 /// Decomposition for RLWE part B
92 d_b: usize,
93}
94
95impl<M: MatrixEntity, Mod: Modulus<Element = M::MatElement>> RgswCiphertext<M, Mod> {
96 pub(crate) fn empty<D: RlweDecomposer>(
97 ring_size: usize,
98 decomposer: &D,
99 modulus: Mod,
100 ) -> RgswCiphertext<M, Mod> {
101 RgswCiphertext {
102 data: M::zeros(
103 decomposer.a().decomposition_count() * 2 + decomposer.b().decomposition_count() * 2,
104 ring_size,
105 ),
106 d_a: decomposer.a().decomposition_count(),
107 d_b: decomposer.b().decomposition_count(),
108 modulus,
109 }
110 }
111}
112
113pub struct SeededRgswCiphertext<M, S, Mod>
114where
115 M: Matrix,
116{
117 pub(crate) data: M,
118 seed: S,
119 modulus: Mod,
120 /// Decomposition for RLWE part A
121 d_a: usize,
122 /// Decomposition for RLWE part B
123 d_b: usize,
124}
125
126impl<M: Matrix + MatrixEntity, S, Mod> SeededRgswCiphertext<M, S, Mod> {
127 pub(crate) fn empty<D: RlweDecomposer>(
128 ring_size: usize,
129 decomposer: &D,
130 seed: S,
131 modulus: Mod,
132 ) -> SeededRgswCiphertext<M, S, Mod> {
133 SeededRgswCiphertext {
134 data: M::zeros(
135 decomposer.a().decomposition_count() * 2 + decomposer.b().decomposition_count(),
136 ring_size,
137 ),
138 seed,
139 modulus,
140 d_a: decomposer.a().decomposition_count(),
141 d_b: decomposer.b().decomposition_count(),
142 }
143 }
144}
145
146impl<M: Debug + Matrix, S: Debug, Mod: Debug> Debug for SeededRgswCiphertext<M, S, Mod>
147where
148 M::MatElement: Debug,
149{
150 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
151 f.debug_struct("SeededRgswCiphertext")
152 .field("data", &self.data)
153 .field("seed", &self.seed)
154 .field("modulus", &self.modulus)
155 .finish()
156 }
157}
158
159pub struct RgswCiphertextEvaluationDomain<M, R, N> {
160 pub(crate) data: M,
161 _phantom: PhantomData<(R, N)>,
162}
163
164impl<
165 M: MatrixMut + MatrixEntity,
166 Mod: Modulus<Element = M::MatElement>,
167 R: NewWithSeed + RandomFillUniformInModulus<[M::MatElement], Mod>,
168 N: NttInit<Mod> + Ntt<Element = M::MatElement> + Debug,
169 > From<&SeededRgswCiphertext<M, R::Seed, Mod>> for RgswCiphertextEvaluationDomain<M, R, N>
170where
171 <M as Matrix>::R: RowMut,
172 M::MatElement: Copy,
173 R::Seed: Clone,
174 M: Debug,
175{
176 fn from(value: &SeededRgswCiphertext<M, R::Seed, Mod>) -> Self {
177 let mut data = M::zeros(value.d_a * 2 + value.d_b * 2, value.data.dimension().1);
178
179 // copy RLWE'(-sm)
180 izip!(
181 data.iter_rows_mut().take(value.d_a * 2),
182 value.data.iter_rows().take(value.d_a * 2)
183 )
184 .for_each(|(to_ri, from_ri)| {
185 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
186 });
187
188 // sample A polynomials of RLWE'(m) - RLWE'A(m)
189 // TODO(Jay): Do we want to be generic over RandomGenerator used here? I think
190 // not.
191 let mut p_rng = R::new_with_seed(value.seed.clone());
192 izip!(data.iter_rows_mut().skip(value.d_a * 2).take(value.d_b * 1))
193 .for_each(|ri| p_rng.random_fill(&value.modulus, ri.as_mut()));
194
195 // RLWE'_B(m)
196 izip!(
197 data.iter_rows_mut().skip(value.d_a * 2 + value.d_b),
198 value.data.iter_rows().skip(value.d_a * 2)
199 )
200 .for_each(|(to_ri, from_ri)| {
201 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
202 });
203
204 // Send polynomials to evaluation domain
205 let ring_size = data.dimension().1;
206 let nttop = N::new(&value.modulus, ring_size);
207 data.iter_rows_mut()
208 .for_each(|ri| nttop.forward(ri.as_mut()));
209
210 Self {
211 data: data,
212 _phantom: PhantomData,
213 }
214 }
215}
216
217impl<
218 M: MatrixMut + MatrixEntity,
219 Mod: Modulus<Element = M::MatElement>,
220 R,
221 N: NttInit<Mod> + Ntt<Element = M::MatElement>,
222 > From<&RgswCiphertext<M, Mod>> for RgswCiphertextEvaluationDomain<M, R, N>
223where
224 <M as Matrix>::R: RowMut,
225 M::MatElement: Copy,
226 M: Debug,
227{
228 fn from(value: &RgswCiphertext<M, Mod>) -> Self {
229 let mut data = M::zeros(value.d_a * 2 + value.d_b * 2, value.data.dimension().1);
230
231 // copy RLWE'(-sm)
232 izip!(
233 data.iter_rows_mut().take(value.d_a * 2),
234 value.data.iter_rows().take(value.d_a * 2)
235 )
236 .for_each(|(to_ri, from_ri)| {
237 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
238 });
239
240 // copy RLWE'(m)
241 izip!(
242 data.iter_rows_mut().skip(value.d_a * 2),
243 value.data.iter_rows().skip(value.d_a * 2)
244 )
245 .for_each(|(to_ri, from_ri)| {
246 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
247 });
248
249 // Send polynomials to evaluation domain
250 let ring_size = data.dimension().1;
251 let nttop = N::new(&value.modulus, ring_size);
252 data.iter_rows_mut()
253 .for_each(|ri| nttop.forward(ri.as_mut()));
254
255 Self {
256 data: data,
257 _phantom: PhantomData,
258 }
259 }
260}
261
262impl<M: Debug, R, N> Debug for RgswCiphertextEvaluationDomain<M, R, N> {
263 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
264 f.debug_struct("RgswCiphertextEvaluationDomain")
265 .field("data", &self.data)
266 .field("_phantom", &self._phantom)
267 .finish()
268 }
269}
270
271impl<M: Matrix, R, N> Matrix for RgswCiphertextEvaluationDomain<M, R, N> {
272 type MatElement = M::MatElement;
273 type R = M::R;
274
275 fn dimension(&self) -> (usize, usize) {
276 self.data.dimension()
277 }
278
279 fn fits(&self, row: usize, col: usize) -> bool {
280 self.data.fits(row, col)
281 }
282}
283
284impl<M: Matrix, R, N> AsRef<[M::R]> for RgswCiphertextEvaluationDomain<M, R, N> {
285 fn as_ref(&self) -> &[M::R] {
286 self.data.as_ref()
287 }
288}
289
290pub struct SeededRlweCiphertext<R, S, Mod> {
291 pub(crate) data: R,
292 pub(crate) seed: S,
293 pub(crate) modulus: Mod,
294}
295
296impl<R: RowEntity, S, Mod> SeededRlweCiphertext<R, S, Mod> {
297 pub(crate) fn empty(ring_size: usize, seed: S, modulus: Mod) -> Self {
298 SeededRlweCiphertext {
299 data: R::zeros(ring_size),
300 seed,
301 modulus,
302 }
303 }
304}
305
306pub struct RlweCiphertext<M, Rng> {
307 pub(crate) data: M,
308 pub(crate) is_trivial: bool,
309 pub(crate) _phatom: PhantomData<Rng>,
310}
311
312impl<M, Rng> RlweCiphertext<M, Rng> {
313 pub(crate) fn new_trivial(data: M) -> Self {
314 RlweCiphertext {
315 data,
316 is_trivial: true,
317 _phatom: PhantomData,
318 }
319 }
320}
321
322impl<M: Matrix, Rng> Matrix for RlweCiphertext<M, Rng> {
323 type MatElement = M::MatElement;
324 type R = M::R;
325
326 fn dimension(&self) -> (usize, usize) {
327 self.data.dimension()
328 }
329
330 fn fits(&self, row: usize, col: usize) -> bool {
331 self.data.fits(row, col)
332 }
333}
334
335impl<M: MatrixMut, Rng> MatrixMut for RlweCiphertext<M, Rng> where <M as Matrix>::R: RowMut {}
336
337impl<M: Matrix, Rng> AsRef<[<M as Matrix>::R]> for RlweCiphertext<M, Rng> {
338 fn as_ref(&self) -> &[<M as Matrix>::R] {
339 self.data.as_ref()
340 }
341}
342
343impl<M: MatrixMut, Rng> AsMut<[<M as Matrix>::R]> for RlweCiphertext<M, Rng>
344where
345 <M as Matrix>::R: RowMut,
346{
347 fn as_mut(&mut self) -> &mut [<M as Matrix>::R] {
348 self.data.as_mut()
349 }
350}
351
352impl<M, Rng> IsTrivial for RlweCiphertext<M, Rng> {
353 fn is_trivial(&self) -> bool {
354 self.is_trivial
355 }
356 fn set_not_trivial(&mut self) {
357 self.is_trivial = false;
358 }
359}
360
361impl<
362 R: Row,
363 M: MatrixEntity<R = R, MatElement = R::Element> + MatrixMut,
364 Rng: NewWithSeed + RandomFillUniformInModulus<[M::MatElement], Mod>,
365 Mod: Modulus<Element = R::Element>,
366 > From<&SeededRlweCiphertext<R, Rng::Seed, Mod>> for RlweCiphertext<M, Rng>
367where
368 Rng::Seed: Clone,
369 <M as Matrix>::R: RowMut,
370 R::Element: Copy,
371{
372 fn from(value: &SeededRlweCiphertext<R, Rng::Seed, Mod>) -> Self {
373 let mut data = M::zeros(2, value.data.as_ref().len());
374
375 // sample a
376 let mut p_rng = Rng::new_with_seed(value.seed.clone());
377 RandomFillUniformInModulus::random_fill(&mut p_rng, &value.modulus, data.get_row_mut(0));
378
379 data.get_row_mut(1).copy_from_slice(value.data.as_ref());
380
381 RlweCiphertext {
382 data,
383 is_trivial: false,
384 _phatom: PhantomData,
385 }
386 }
387}
388
389pub trait IsTrivial {
390 fn is_trivial(&self) -> bool;
391 fn set_not_trivial(&mut self);
392}
393
394pub struct SeededRlwePublicKey<Ro: Row, S> {
395 data: Ro,
396 seed: S,
397 modulus: Ro::Element,
398}
399
400impl<Ro: RowEntity, S> SeededRlwePublicKey<Ro, S> {
401 pub(crate) fn empty(ring_size: usize, seed: S, modulus: Ro::Element) -> Self {
402 Self {
403 data: Ro::zeros(ring_size),
404 seed,
405 modulus,
406 }
407 }
408}
409
410pub struct RlwePublicKey<M, R> {
411 data: M,
412 _phantom: PhantomData<R>,
413}
414
415impl<
416 M: MatrixMut + MatrixEntity,
417 Rng: NewWithSeed + RandomFillUniformInModulus<[M::MatElement], M::MatElement>,
418 > From<&SeededRlwePublicKey<M::R, Rng::Seed>> for RlwePublicKey<M, Rng>
419where
420 <M as Matrix>::R: RowMut,
421 M::MatElement: Copy,
422 Rng::Seed: Copy,
423{
424 fn from(value: &SeededRlwePublicKey<M::R, Rng::Seed>) -> Self {
425 let mut data = M::zeros(2, value.data.as_ref().len());
426
427 // sample a
428 let mut p_rng = Rng::new_with_seed(value.seed);
429 RandomFillUniformInModulus::random_fill(&mut p_rng, &value.modulus, data.get_row_mut(0));
430
431 // copy over b
432 data.get_row_mut(1).copy_from_slice(value.data.as_ref());
433
434 Self {
435 data,
436 _phantom: PhantomData,
437 }
438 }
439}
440
441#[derive(Clone)]
442pub struct RlweSecret {
443 pub(crate) values: Vec<i32>,
444}
445
446impl Secret for RlweSecret {
447 type Element = i32;
448 fn values(&self) -> &[Self::Element] {
449 &self.values
450 }
451}
452
453impl RlweSecret {
454 pub fn random(hw: usize, n: usize) -> RlweSecret {
455 DefaultSecureRng::with_local_mut(|rng| {
456 let mut out = vec![0i32; n];
457 fill_random_ternary_secret_with_hamming_weight(&mut out, hw, rng);
458
459 RlweSecret { values: out }
460 })
461 }
462}
463
464pub(crate) fn generate_auto_map(ring_size: usize, k: isize) -> (Vec<usize>, Vec<bool>) {
465 assert!(k & 1 == 1, "Auto {k} must be odd");
466
467 let k = if k < 0 {
468 // k is -ve, return k%(2*N)
469 (2 * ring_size) - (k.abs() as usize % (2 * ring_size))
470 } else {
471 k as usize
472 };
473 let (auto_map_index, auto_sign_index): (Vec<usize>, Vec<bool>) = (0..ring_size)
474 .into_iter()
475 .map(|i| {
476 let mut to_index = (i * k) % (2 * ring_size);
477 let mut sign = true;
478
479 // wrap around. false implies negative
480 if to_index >= ring_size {
481 to_index = to_index - ring_size;
482 sign = false;
483 }
484
485 (to_index, sign)
486 })
487 .unzip();
488 (auto_map_index, auto_sign_index)
489}
490
491pub(crate) fn routine<R: RowMut, ModOp: VectorOps<Element = R::Element>>(
492 write_to_row: &mut [R::Element],
493 matrix_a: &[R],
494 matrix_b: &[R],
495 mod_op: &ModOp,
496) {
497 izip!(matrix_a.iter(), matrix_b.iter()).for_each(|(a, b)| {
498 mod_op.elwise_fma_mut(write_to_row, a.as_ref(), b.as_ref());
499 });
500}
501
502/// Decomposes ring polynomial r(X) into d polynomials using decomposer into
503/// output matrix decomp_r
504///
505/// Note that decomposition of r(X) requires decomposition of each of
506/// coefficients.
507///
508/// - decomp_r: must have dimensions d x ring_size. i^th decomposed polynomial
509/// will be stored at i^th row.
510pub(crate) fn decompose_r<R: RowMut, D: Decomposer<Element = R::Element>>(
511 r: &[R::Element],
512 decomp_r: &mut [R],
513 decomposer: &D,
514) where
515 R::Element: Copy,
516{
517 let ring_size = r.len();
518 let d = decomposer.decomposition_count();
519
520 for ri in 0..ring_size {
521 // let el_decomposed = decomposer.decompose_to_vec(&r[ri]);
522
523 decomposer
524 .decompose_iter(&r[ri])
525 .enumerate()
526 .for_each(|(index, el)| {
527 decomp_r[index].as_mut()[ri] = el;
528 });
529
530 // for j in 0..d {
531 // decomp_r[j].as_mut()[ri] = el_decomposed[j];
532 // }
533 }
534}
535
536/// Sends RLWE_{s}(X) -> RLWE_{s}(X^k) where k is some galois element
537///
538/// - scratch_matrix: must have dimension at-least d+2 x ring_size. d rows to
539/// store decomposed polynomials and 2 for rlwe
540pub(crate) fn galois_auto<
541 MT: Matrix + IsTrivial + MatrixMut,
542 Mmut: MatrixMut<MatElement = MT::MatElement>,
543 ModOp: ArithmeticOps<Element = MT::MatElement> + VectorOps<Element = MT::MatElement>,
544 NttOp: Ntt<Element = MT::MatElement>,
545 D: Decomposer<Element = MT::MatElement>,
546>(
547 rlwe_in: &mut MT,
548 ksk: &Mmut,
549 scratch_matrix: &mut Mmut,
550 auto_map_index: &[usize],
551 auto_map_sign: &[bool],
552 mod_op: &ModOp,
553 ntt_op: &NttOp,
554 decomposer: &D,
555) where
556 <Mmut as Matrix>::R: RowMut,
557 <MT as Matrix>::R: RowMut,
558 MT::MatElement: Copy + Zero,
559{
560 let d = decomposer.decomposition_count();
561 let ring_size = rlwe_in.dimension().1;
562 assert!(rlwe_in.dimension().0 == 2);
563 assert!(scratch_matrix.fits(d + 2, ring_size));
564
565 let (scratch_matrix_d_ring, tmp_rlwe_out) = scratch_matrix.split_at_row_mut(d);
566
567 if !rlwe_in.is_trivial() {
568 tmp_rlwe_out.iter_mut().for_each(|r| {
569 r.as_mut().fill(Mmut::MatElement::zero());
570 });
571
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_to_vec(&el_out);
582
583 decomposer
584 .decompose_iter(&el_out)
585 .enumerate()
586 .for_each(|(index, el)| {
587 scratch_matrix_d_ring[index].as_mut()[*to_index] = el;
588 });
589
590 // for j in 0..d {
591 // scratch_matrix_d_ring[j].as_mut()[*to_index] =
592 // el_out_decomposed[j]; }
593 });
594
595 // transform decomposed a(X^k) to evaluation domain
596 scratch_matrix_d_ring.iter_mut().for_each(|r| {
597 ntt_op.forward(r.as_mut());
598 });
599
600 // RLWE(m^k) = a', b'; RLWE(m) = a, b
601 // key switch: (a * RLWE'(s(X^k)))
602 let (ksk_a, ksk_b) = ksk.split_at_row(d);
603 // a' = decomp<a> * RLWE'_A(s(X^k))
604 routine(
605 tmp_rlwe_out[0].as_mut(),
606 scratch_matrix_d_ring,
607 ksk_a,
608 mod_op,
609 );
610
611 // b' += decomp<a(X^k)> * RLWE'_B(s(X^k))
612 routine(
613 tmp_rlwe_out[1].as_mut(),
614 scratch_matrix_d_ring,
615 ksk_b,
616 mod_op,
617 );
618
619 // transform RLWE(m^k) to coefficient domain
620 tmp_rlwe_out
621 .iter_mut()
622 .for_each(|r| ntt_op.backward(r.as_mut()));
623
624 // send b(X) -> b(X^k) and then b'(X) += b(X^k)
625 izip!(
626 rlwe_in.get_row(1),
627 auto_map_index.iter(),
628 auto_map_sign.iter()
629 )
630 .for_each(|(el_in, to_index, sign)| {
631 let row = tmp_rlwe_out[1].as_mut();
632 if !*sign {
633 row[*to_index] = mod_op.sub(&row[*to_index], el_in);
634 } else {
635 row[*to_index] = mod_op.add(&row[*to_index], el_in);
636 }
637 });
638
639 // copy over A; Leave B for later
640 rlwe_in
641 .get_row_mut(0)
642 .copy_from_slice(tmp_rlwe_out[0].as_ref());
643 } else {
644 // RLWE is trivial, a(X) is 0.
645 // send b(X) -> b(X^k)
646 izip!(
647 rlwe_in.get_row(1),
648 auto_map_index.iter(),
649 auto_map_sign.iter()
650 )
651 .for_each(|(el_in, to_index, sign)| {
652 if !*sign {
653 tmp_rlwe_out[1].as_mut()[*to_index] = mod_op.neg(el_in);
654 } else {
655 tmp_rlwe_out[1].as_mut()[*to_index] = *el_in;
656 }
657 });
658 }
659
660 // Copy over B
661 rlwe_in
662 .get_row_mut(1)
663 .copy_from_slice(tmp_rlwe_out[1].as_ref());
664}
665
666/// Returns RLWE(m0m1) = RLWE(m0) x RGSW(m1). Mutates rlwe_in inplace to equal
667/// RLWE(m0m1)
668///
669/// - rlwe_in: is RLWE(m0) with polynomials in coefficient domain
670/// - rgsw_in: is RGSW(m1) with polynomials in evaluation domain
671/// - scratch_matrix_d_ring: is a matrix of dimension (d_rgsw, ring_size) used
672/// as scratch space to store decomposed Ring elements temporarily
673pub(crate) fn less1_rlwe_by_rgsw<
674 Mmut: MatrixMut,
675 MT: Matrix<MatElement = Mmut::MatElement> + MatrixMut<MatElement = Mmut::MatElement> + IsTrivial,
676 D: Decomposer<Element = Mmut::MatElement>,
677 ModOp: VectorOps<Element = Mmut::MatElement>,
678 NttOp: Ntt<Element = Mmut::MatElement>,
679>(
680 rlwe_in: &mut MT,
681 rgsw_in: &Mmut,
682 scratch_matrix_dplus2_ring: &mut Mmut,
683 decomposer: &D,
684 ntt_op: &NttOp,
685 mod_op: &ModOp,
686 skip0: usize,
687 skip1: usize,
688) where
689 Mmut::MatElement: Copy + Zero,
690 <Mmut as Matrix>::R: RowMut,
691 <MT as Matrix>::R: RowMut,
692{
693 let d_rgsw = decomposer.decomposition_count();
694 assert!(scratch_matrix_dplus2_ring.dimension() == (d_rgsw + 2, rlwe_in.dimension().1));
695 assert!(rgsw_in.dimension() == (d_rgsw * 4, rlwe_in.dimension().1));
696
697 // decomposed RLWE x RGSW
698 let (rlwe_dash_nsm, rlwe_dash_m) = rgsw_in.split_at_row(d_rgsw * 2);
699 let (scratch_matrix_d_ring, scratch_rlwe_out) =
700 scratch_matrix_dplus2_ring.split_at_row_mut(d_rgsw);
701 scratch_rlwe_out[0].as_mut().fill(Mmut::MatElement::zero());
702 scratch_rlwe_out[1].as_mut().fill(Mmut::MatElement::zero());
703 // RLWE_in = a_in, b_in; RLWE_out = a_out, b_out
704 if !rlwe_in.is_trivial() {
705 // a_in = 0 when RLWE_in is trivial RLWE ciphertext
706 // decomp<a_in>
707 decompose_r(rlwe_in.get_row_slice(0), scratch_matrix_d_ring, decomposer);
708 scratch_matrix_d_ring
709 .iter_mut()
710 .for_each(|r| ntt_op.forward(r.as_mut()));
711 // a_out += decomp<a_in> \cdot RLWE_A'(-sm)
712 routine(
713 scratch_rlwe_out[0].as_mut(),
714 scratch_matrix_d_ring[skip0..].as_ref(),
715 &rlwe_dash_nsm[skip0..d_rgsw],
716 mod_op,
717 );
718 // b_out += decomp<a_in> \cdot RLWE_B'(-sm)
719 routine(
720 scratch_rlwe_out[1].as_mut(),
721 scratch_matrix_d_ring[skip0..].as_ref(),
722 &rlwe_dash_nsm[d_rgsw + skip0..],
723 mod_op,
724 );
725 }
726 // decomp<b_in>
727 decompose_r(rlwe_in.get_row_slice(1), scratch_matrix_d_ring, decomposer);
728 scratch_matrix_d_ring
729 .iter_mut()
730 .for_each(|r| ntt_op.forward(r.as_mut()));
731 // a_out += decomp<b_in> \cdot RLWE_A'(m)
732 routine(
733 scratch_rlwe_out[0].as_mut(),
734 scratch_matrix_d_ring[skip1..].as_ref(),
735 &rlwe_dash_m[skip1..d_rgsw],
736 mod_op,
737 );
738 // b_out += decomp<b_in> \cdot RLWE_B'(m)
739 routine(
740 scratch_rlwe_out[1].as_mut(),
741 scratch_matrix_d_ring[skip1..].as_ref(),
742 &rlwe_dash_m[d_rgsw + skip1..],
743 mod_op,
744 );
745
746 // transform rlwe_out to coefficient domain
747 scratch_rlwe_out
748 .iter_mut()
749 .for_each(|r| ntt_op.backward(r.as_mut()));
750
751 rlwe_in
752 .get_row_mut(0)
753 .copy_from_slice(scratch_rlwe_out[0].as_mut());
754 rlwe_in
755 .get_row_mut(1)
756 .copy_from_slice(scratch_rlwe_out[1].as_mut());
757 rlwe_in.set_not_trivial();
758}
759
760/// Returns RLWE(m0m1) = RLWE(m0) x RGSW(m1). Mutates rlwe_in inplace to equal
761/// RLWE(m0m1)
762///
763/// - rlwe_in: is RLWE(m0) with polynomials in coefficient domain
764/// - rgsw_in: is RGSW(m1) with polynomials in evaluation domain
765/// - scratch_matrix_d_ring: is a matrix with atleast max(d_a, d_b) rows and
766/// ring_size columns. It's used to store decomposed polynomials and out RLWE
767/// temoporarily
768pub(crate) fn rlwe_by_rgsw<
769 Mmut: MatrixMut,
770 MT: Matrix<MatElement = Mmut::MatElement> + MatrixMut<MatElement = Mmut::MatElement> + IsTrivial,
771 D: RlweDecomposer<Element = Mmut::MatElement>,
772 ModOp: VectorOps<Element = Mmut::MatElement>,
773 NttOp: Ntt<Element = Mmut::MatElement>,
774>(
775 rlwe_in: &mut MT,
776 rgsw_in: &Mmut,
777 scratch_matrix: &mut Mmut,
778 decomposer: &D,
779 ntt_op: &NttOp,
780 mod_op: &ModOp,
781) where
782 Mmut::MatElement: Copy + Zero,
783 <Mmut as Matrix>::R: RowMut,
784 <MT as Matrix>::R: RowMut,
785{
786 let decomposer_a = decomposer.a();
787 let decomposer_b = decomposer.b();
788 let d_a = decomposer_a.decomposition_count();
789 let d_b = decomposer_b.decomposition_count();
790 let max_d = std::cmp::max(d_a, d_b);
791 assert!(scratch_matrix.fits(max_d + 2, rlwe_in.dimension().1));
792 assert!(rgsw_in.dimension() == (d_a * 2 + d_b * 2, rlwe_in.dimension().1));
793
794 // decomposed RLWE x RGSW
795 let (rlwe_dash_nsm, rlwe_dash_m) = rgsw_in.split_at_row(d_a * 2);
796 let (scratch_matrix_d_ring, scratch_rlwe_out) = scratch_matrix.split_at_row_mut(max_d);
797 scratch_rlwe_out[0].as_mut().fill(Mmut::MatElement::zero());
798 scratch_rlwe_out[1].as_mut().fill(Mmut::MatElement::zero());
799 // RLWE_in = a_in, b_in; RLWE_out = a_out, b_out
800 if !rlwe_in.is_trivial() {
801 // a_in = 0 when RLWE_in is trivial RLWE ciphertext
802 // decomp<a_in>
803 decompose_r(
804 rlwe_in.get_row_slice(0),
805 scratch_matrix_d_ring,
806 decomposer_a,
807 );
808 scratch_matrix_d_ring
809 .iter_mut()
810 .take(d_a)
811 .for_each(|r| ntt_op.forward(r.as_mut()));
812 // a_out += decomp<a_in> \cdot RLWE_A'(-sm)
813 routine(
814 scratch_rlwe_out[0].as_mut(),
815 scratch_matrix_d_ring.as_ref(),
816 &rlwe_dash_nsm[..d_a],
817 mod_op,
818 );
819 // b_out += decomp<a_in> \cdot RLWE_B'(-sm)
820 routine(
821 scratch_rlwe_out[1].as_mut(),
822 scratch_matrix_d_ring.as_ref(),
823 &rlwe_dash_nsm[d_a..],
824 mod_op,
825 );
826 }
827 // decomp<b_in>
828 decompose_r(
829 rlwe_in.get_row_slice(1),
830 scratch_matrix_d_ring,
831 decomposer_b,
832 );
833 scratch_matrix_d_ring
834 .iter_mut()
835 .take(d_b)
836 .for_each(|r| ntt_op.forward(r.as_mut()));
837 // a_out += decomp<b_in> \cdot RLWE_A'(m)
838 routine(
839 scratch_rlwe_out[0].as_mut(),
840 scratch_matrix_d_ring.as_ref(),
841 &rlwe_dash_m[..d_b],
842 mod_op,
843 );
844 // b_out += decomp<b_in> \cdot RLWE_B'(m)
845 routine(
846 scratch_rlwe_out[1].as_mut(),
847 scratch_matrix_d_ring.as_ref(),
848 &rlwe_dash_m[d_b..],
849 mod_op,
850 );
851
852 // transform rlwe_out to coefficient domain
853 scratch_rlwe_out
854 .iter_mut()
855 .for_each(|r| ntt_op.backward(r.as_mut()));
856
857 rlwe_in
858 .get_row_mut(0)
859 .copy_from_slice(scratch_rlwe_out[0].as_mut());
860 rlwe_in
861 .get_row_mut(1)
862 .copy_from_slice(scratch_rlwe_out[1].as_mut());
863 rlwe_in.set_not_trivial();
864}
865
866/// Inplace mutates rlwe_0 to equal RGSW(m0m1) = RGSW(m0)xRGSW(m1)
867/// in evaluation domain
868///
869/// Warning -
870/// Pass a fresh RGSW ciphertext as the second operand, i.e. as `rgsw_1`.
871/// This is to assure minimal error growth in the resulting RGSW ciphertext.
872/// RGSWxRGSW boils down to d_rgsw*2 RLWExRGSW multiplications. Hence, the noise
873/// growth in resulting ciphertext depends on the norm of second RGSW
874/// ciphertext, not the first. This is useful in cases where one is accumulating
875/// multiple RGSW ciphertexts into 1. In which case, pass the accumulating RGSW
876/// ciphertext as rlwe_0 (the one with higher noise) and subsequent RGSW
877/// ciphertexts, with lower noise, to be accumulated as second
878/// operand.
879///
880/// - rgsw_0: RGSW(m0)
881/// - rgsw_1_eval: RGSW(m1) in Evaluation domain
882/// - scratch_matrix_d_plus_rgsw_by_ring: scratch space matrix with rows
883/// (max(d_a, d_b) + d_a*2+d_b*2) and columns ring_size
884pub(crate) fn rgsw_by_rgsw_inplace<
885 Mmut: MatrixMut,
886 D: RlweDecomposer<Element = Mmut::MatElement>,
887 ModOp: VectorOps<Element = Mmut::MatElement>,
888 NttOp: Ntt<Element = Mmut::MatElement>,
889>(
890 rgsw_0: &mut Mmut,
891 rgsw_1_eval: &Mmut,
892 decomposer: &D,
893 scratch_matrix: &mut Mmut,
894 ntt_op: &NttOp,
895 mod_op: &ModOp,
896) where
897 <Mmut as Matrix>::R: RowMut,
898 Mmut::MatElement: Copy + Zero,
899{
900 let decomposer_a = decomposer.a();
901 let decomposer_b = decomposer.b();
902 let d_a = decomposer_a.decomposition_count();
903 let d_b = decomposer_b.decomposition_count();
904 let max_d = std::cmp::max(d_a, d_b);
905 let rgsw_rows = d_a * 2 + d_b * 2;
906 assert!(rgsw_0.dimension().0 == rgsw_rows);
907 let ring_size = rgsw_0.dimension().1;
908 assert!(rgsw_1_eval.dimension() == (rgsw_rows, ring_size));
909 assert!(scratch_matrix.fits(max_d + rgsw_rows, ring_size));
910
911 let (decomp_r_space, rgsw_space) = scratch_matrix.split_at_row_mut(max_d);
912
913 // zero rgsw_space
914 rgsw_space
915 .iter_mut()
916 .for_each(|ri| ri.as_mut().fill(Mmut::MatElement::zero()));
917 let (rlwe_dash_space_nsm, rlwe_dash_space_m) = rgsw_space.split_at_mut(d_a * 2);
918 let (rlwe_dash_space_nsm_parta, rlwe_dash_space_nsm_partb) =
919 rlwe_dash_space_nsm.split_at_mut(d_a);
920 let (rlwe_dash_space_m_parta, rlwe_dash_space_m_partb) = rlwe_dash_space_m.split_at_mut(d_b);
921
922 let (rgsw0_nsm, rgsw0_m) = rgsw_0.split_at_row(d_a * 2);
923 let (rgsw1_nsm, rgsw1_m) = rgsw_1_eval.split_at_row(d_a * 2);
924
925 // RGSW x RGSW
926 izip!(
927 rgsw0_nsm.iter().take(d_a).chain(rgsw0_m.iter().take(d_b)),
928 rgsw0_nsm.iter().skip(d_a).chain(rgsw0_m.iter().skip(d_b)),
929 rlwe_dash_space_nsm_parta
930 .iter_mut()
931 .chain(rlwe_dash_space_m_parta.iter_mut()),
932 rlwe_dash_space_nsm_partb
933 .iter_mut()
934 .chain(rlwe_dash_space_m_partb.iter_mut()),
935 )
936 .for_each(|(rlwe_a, rlwe_b, rlwe_out_a, rlwe_out_b)| {
937 // Part A
938 decompose_r(rlwe_a.as_ref(), decomp_r_space.as_mut(), decomposer_a);
939 decomp_r_space
940 .iter_mut()
941 .take(d_a)
942 .for_each(|ri| ntt_op.forward(ri.as_mut()));
943 routine(
944 rlwe_out_a.as_mut(),
945 &decomp_r_space[..d_a],
946 &rgsw1_nsm[..d_a],
947 mod_op,
948 );
949 routine(
950 rlwe_out_b.as_mut(),
951 &decomp_r_space[..d_a],
952 &rgsw1_nsm[d_a..],
953 mod_op,
954 );
955
956 // Part B
957 decompose_r(rlwe_b.as_ref(), decomp_r_space.as_mut(), decomposer_b);
958 decomp_r_space
959 .iter_mut()
960 .take(d_b)
961 .for_each(|ri| ntt_op.forward(ri.as_mut()));
962 routine(
963 rlwe_out_a.as_mut(),
964 &decomp_r_space[..d_b],
965 &rgsw1_m[..d_b],
966 mod_op,
967 );
968 routine(
969 rlwe_out_b.as_mut(),
970 &decomp_r_space[..d_b],
971 &rgsw1_m[d_b..],
972 mod_op,
973 );
974 });
975
976 // copy over RGSW(m0m1) into RGSW(m0)
977 izip!(rgsw_0.iter_rows_mut(), rgsw_space.iter())
978 .for_each(|(to_ri, from_ri)| to_ri.as_mut().copy_from_slice(from_ri.as_ref()));
979
980 // send back to coefficient domain
981 rgsw_0
982 .iter_rows_mut()
983 .for_each(|ri| ntt_op.backward(ri.as_mut()));
984}
985
986/// Encrypts message m as a RGSW ciphertext.
987///
988/// - m_eval: is `m` is evaluation domain
989/// - out_rgsw: RGSW(m) is stored as single matrix of dimension (d_rgsw * 3,
990/// ring_size). The matrix has the following structure [RLWE'_A(-sm) ||
991/// RLWE'_B(-sm) || RLWE'_B(m)]^T and RLWE'_A(m) is generated via seed (where
992/// p_rng is assumed to be seeded with seed)
993pub(crate) fn secret_key_encrypt_rgsw<
994 Mmut: MatrixMut + MatrixEntity,
995 S,
996 R: RandomFillGaussianInModulus<[Mmut::MatElement], ModOp::M>
997 + RandomFillUniformInModulus<[Mmut::MatElement], ModOp::M>,
998 PR: RandomFillUniformInModulus<[Mmut::MatElement], ModOp::M>,
999 ModOp: VectorOps<Element = Mmut::MatElement> + GetModulus<Element = Mmut::MatElement>,
1000 NttOp: Ntt<Element = Mmut::MatElement>,
1001>(
1002 out_rgsw: &mut Mmut,
1003 m: &[Mmut::MatElement],
1004 gadget_a: &[Mmut::MatElement],
1005 gadget_b: &[Mmut::MatElement],
1006 s: &[S],
1007 mod_op: &ModOp,
1008 ntt_op: &NttOp,
1009 p_rng: &mut PR,
1010 rng: &mut R,
1011) where
1012 <Mmut as Matrix>::R: RowMut + RowEntity + TryConvertFrom1<[S], ModOp::M> + Debug,
1013 Mmut::MatElement: Copy + Debug,
1014{
1015 let d_a = gadget_a.len();
1016 let d_b = gadget_b.len();
1017 let q = mod_op.modulus();
1018 let ring_size = s.len();
1019 assert!(out_rgsw.dimension() == (d_a * 2 + d_b, ring_size));
1020 assert!(m.as_ref().len() == ring_size);
1021
1022 // RLWE(-sm), RLWE(m)
1023 let (rlwe_dash_nsm, b_rlwe_dash_m) = out_rgsw.split_at_row_mut(d_a * 2);
1024
1025 let mut s_eval = Mmut::R::try_convert_from(s, &q);
1026 ntt_op.forward(s_eval.as_mut());
1027
1028 let mut scratch_space = Mmut::R::zeros(ring_size);
1029
1030 // RLWE'(-sm)
1031 let (a_rlwe_dash_nsm, b_rlwe_dash_nsm) = rlwe_dash_nsm.split_at_mut(d_a);
1032 izip!(
1033 a_rlwe_dash_nsm.iter_mut(),
1034 b_rlwe_dash_nsm.iter_mut(),
1035 gadget_a.iter()
1036 )
1037 .for_each(|(ai, bi, beta_i)| {
1038 // Sample a_i
1039 RandomFillUniformInModulus::random_fill(rng, &q, ai.as_mut());
1040
1041 // a_i * s
1042 scratch_space.as_mut().copy_from_slice(ai.as_ref());
1043 ntt_op.forward(scratch_space.as_mut());
1044 mod_op.elwise_mul_mut(scratch_space.as_mut(), s_eval.as_ref());
1045 ntt_op.backward(scratch_space.as_mut());
1046
1047 // b_i = e_i + a_i * s
1048 RandomFillGaussianInModulus::random_fill(rng, &q, bi.as_mut());
1049 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.as_ref());
1050
1051 // a_i + \beta_i * m
1052 mod_op.elwise_scalar_mul(scratch_space.as_mut(), m.as_ref(), beta_i);
1053 mod_op.elwise_add_mut(ai.as_mut(), scratch_space.as_ref());
1054 });
1055
1056 // RLWE(m)
1057 let mut a_rlwe_dash_m = {
1058 // polynomials of part A of RLWE'(m) are sampled from seed
1059 let mut a = Mmut::zeros(d_b, ring_size);
1060 a.iter_rows_mut()
1061 .for_each(|ai| RandomFillUniformInModulus::random_fill(p_rng, &q, ai.as_mut()));
1062 a
1063 };
1064
1065 izip!(
1066 a_rlwe_dash_m.iter_rows_mut(),
1067 b_rlwe_dash_m.iter_mut(),
1068 gadget_b.iter()
1069 )
1070 .for_each(|(ai, bi, beta_i)| {
1071 // ai * s
1072 ntt_op.forward(ai.as_mut());
1073 mod_op.elwise_mul_mut(ai.as_mut(), s_eval.as_ref());
1074 ntt_op.backward(ai.as_mut());
1075
1076 // beta_i * m
1077 mod_op.elwise_scalar_mul(scratch_space.as_mut(), m.as_ref(), beta_i);
1078
1079 // Sample e_i
1080 RandomFillGaussianInModulus::random_fill(rng, &q, bi.as_mut());
1081 // e_i + beta_i * m + ai*s
1082 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.as_ref());
1083 mod_op.elwise_add_mut(bi.as_mut(), ai.as_ref());
1084 });
1085}
1086
1087pub(crate) fn public_key_encrypt_rgsw<
1088 Mmut: MatrixMut + MatrixEntity,
1089 M: Matrix<MatElement = Mmut::MatElement>,
1090 R: RandomFillGaussianInModulus<[Mmut::MatElement], ModOp::M>
1091 + RandomFill<[u8]>
1092 + RandomElementInModulus<usize, usize>,
1093 ModOp: VectorOps<Element = Mmut::MatElement> + GetModulus<Element = Mmut::MatElement>,
1094 NttOp: Ntt<Element = Mmut::MatElement>,
1095>(
1096 out_rgsw: &mut Mmut,
1097 m: &[M::MatElement],
1098 public_key: &M,
1099 gadget_a: &[Mmut::MatElement],
1100 gadget_b: &[Mmut::MatElement],
1101 mod_op: &ModOp,
1102 ntt_op: &NttOp,
1103 rng: &mut R,
1104) where
1105 <Mmut as Matrix>::R: RowMut + RowEntity + TryConvertFrom1<[i32], ModOp::M>,
1106 Mmut::MatElement: Copy,
1107{
1108 let ring_size = public_key.dimension().1;
1109 let d_a = gadget_a.len();
1110 let d_b = gadget_b.len();
1111 assert!(public_key.dimension().0 == 2);
1112 assert!(out_rgsw.dimension() == (d_a * 2 + d_b * 2, ring_size));
1113
1114 let mut pk_eval = Mmut::zeros(2, ring_size);
1115 izip!(pk_eval.iter_rows_mut(), public_key.iter_rows()).for_each(|(to_i, from_i)| {
1116 to_i.as_mut().copy_from_slice(from_i.as_ref());
1117 ntt_op.forward(to_i.as_mut());
1118 });
1119 let p0 = pk_eval.get_row_slice(0);
1120 let p1 = pk_eval.get_row_slice(1);
1121
1122 let q = mod_op.modulus();
1123
1124 // RGSW(m) = RLWE'(-sm), RLWE(m)
1125 let (rlwe_dash_nsm, rlwe_dash_m) = out_rgsw.split_at_row_mut(d_a * 2);
1126
1127 // RLWE(-sm)
1128 let (rlwe_dash_nsm_parta, rlwe_dash_nsm_partb) = rlwe_dash_nsm.split_at_mut(d_a);
1129 izip!(
1130 rlwe_dash_nsm_parta.iter_mut(),
1131 rlwe_dash_nsm_partb.iter_mut(),
1132 gadget_a.iter()
1133 )
1134 .for_each(|(ai, bi, beta_i)| {
1135 // sample ephemeral secret u_i
1136 let mut u = vec![0i32; ring_size];
1137 fill_random_ternary_secret_with_hamming_weight(u.as_mut(), ring_size >> 1, rng);
1138 let mut u_eval = Mmut::R::try_convert_from(u.as_ref(), &q);
1139 ntt_op.forward(u_eval.as_mut());
1140
1141 let mut u_eval_copy = Mmut::R::zeros(ring_size);
1142 u_eval_copy.as_mut().copy_from_slice(u_eval.as_ref());
1143
1144 // p0 * u
1145 mod_op.elwise_mul_mut(u_eval.as_mut(), p0.as_ref());
1146 // p1 * u
1147 mod_op.elwise_mul_mut(u_eval_copy.as_mut(), p1.as_ref());
1148 ntt_op.backward(u_eval.as_mut());
1149 ntt_op.backward(u_eval_copy.as_mut());
1150
1151 // sample error
1152 RandomFillGaussianInModulus::random_fill(rng, &q, ai.as_mut());
1153 RandomFillGaussianInModulus::random_fill(rng, &q, bi.as_mut());
1154
1155 // a = p0*u+e0
1156 mod_op.elwise_add_mut(ai.as_mut(), u_eval.as_ref());
1157 // b = p1*u+e1
1158 mod_op.elwise_add_mut(bi.as_mut(), u_eval_copy.as_ref());
1159
1160 // a = p0*u + e0 + \beta*m
1161 // use u_eval as scratch
1162 mod_op.elwise_scalar_mul(u_eval.as_mut(), m.as_ref(), beta_i);
1163 mod_op.elwise_add_mut(ai.as_mut(), u_eval.as_ref());
1164 });
1165
1166 // RLWE(m)
1167 let (rlwe_dash_m_parta, rlwe_dash_m_partb) = rlwe_dash_m.split_at_mut(d_b);
1168 izip!(
1169 rlwe_dash_m_parta.iter_mut(),
1170 rlwe_dash_m_partb.iter_mut(),
1171 gadget_b.iter()
1172 )
1173 .for_each(|(ai, bi, beta_i)| {
1174 // sample ephemeral secret u_i
1175 let mut u = vec![0i32; ring_size];
1176 fill_random_ternary_secret_with_hamming_weight(u.as_mut(), ring_size >> 1, rng);
1177 let mut u_eval = Mmut::R::try_convert_from(u.as_ref(), &q);
1178 ntt_op.forward(u_eval.as_mut());
1179
1180 let mut u_eval_copy = Mmut::R::zeros(ring_size);
1181 u_eval_copy.as_mut().copy_from_slice(u_eval.as_ref());
1182
1183 // p0 * u
1184 mod_op.elwise_mul_mut(u_eval.as_mut(), p0.as_ref());
1185 // p1 * u
1186 mod_op.elwise_mul_mut(u_eval_copy.as_mut(), p1.as_ref());
1187 ntt_op.backward(u_eval.as_mut());
1188 ntt_op.backward(u_eval_copy.as_mut());
1189
1190 // sample error
1191 RandomFillGaussianInModulus::random_fill(rng, &q, ai.as_mut());
1192 RandomFillGaussianInModulus::random_fill(rng, &q, bi.as_mut());
1193
1194 // a = p0*u+e0
1195 mod_op.elwise_add_mut(ai.as_mut(), u_eval.as_ref());
1196 // b = p1*u+e1
1197 mod_op.elwise_add_mut(bi.as_mut(), u_eval_copy.as_ref());
1198
1199 // b = p1*u + e0 + \beta*m
1200 // use u_eval as scratch
1201 mod_op.elwise_scalar_mul(u_eval.as_mut(), m.as_ref(), beta_i);
1202 mod_op.elwise_add_mut(bi.as_mut(), u_eval.as_ref());
1203 });
1204}
1205
1206/// Generates RLWE Key switching key to key switch ciphertext RLWE_{from_s}(m)
1207/// to RLWE_{to_s}(m).
1208///
1209/// Key switching equals
1210/// \sum decompose(c_1)_i * RLWE_{to_s}(\beta^i -from_s)
1211/// Hence, key switchin key equals RLWE'(-from_s) = RLWE(-from_s), RLWE(beta^1
1212/// -from_s), ..., RLWE(beta^{d-1} -from_s).
1213///
1214/// - ksk_out: Output Key switching key. Key switching key stores only part B
1215/// polynomials of ksk RLWE ciphertexts (i.e. RLWE'_B(-from_s)) in coefficient
1216/// domain
1217/// - neg_from_s: Negative of secret polynomial to key switch from
1218/// - to_s: secret polynomial to key switch to.
1219pub(crate) fn rlwe_ksk_gen<
1220 Mmut: MatrixMut + MatrixEntity,
1221 ModOp: ArithmeticOps<Element = Mmut::MatElement>
1222 + VectorOps<Element = Mmut::MatElement>
1223 + GetModulus<Element = Mmut::MatElement>,
1224 NttOp: Ntt<Element = Mmut::MatElement>,
1225 R: RandomFillGaussianInModulus<[Mmut::MatElement], ModOp::M>,
1226 PR: RandomFillUniformInModulus<[Mmut::MatElement], ModOp::M>,
1227>(
1228 ksk_out: &mut Mmut,
1229 neg_from_s: Mmut::R,
1230 mut to_s: Mmut::R,
1231 gadget_vector: &[Mmut::MatElement],
1232 mod_op: &ModOp,
1233 ntt_op: &NttOp,
1234 p_rng: &mut PR,
1235 rng: &mut R,
1236) where
1237 <Mmut as Matrix>::R: RowMut,
1238{
1239 let ring_size = neg_from_s.as_ref().len();
1240 let d = gadget_vector.len();
1241 assert!(ksk_out.dimension() == (d, ring_size));
1242
1243 let q = mod_op.modulus();
1244
1245 ntt_op.forward(to_s.as_mut());
1246
1247 // RLWE'_{to_s}(-from_s)
1248 let mut part_a = {
1249 let mut a = Mmut::zeros(d, ring_size);
1250 a.iter_rows_mut()
1251 .for_each(|ai| RandomFillUniformInModulus::random_fill(p_rng, q, ai.as_mut()));
1252 a
1253 };
1254 izip!(
1255 part_a.iter_rows_mut(),
1256 ksk_out.iter_rows_mut(),
1257 gadget_vector.iter(),
1258 )
1259 .for_each(|(ai, bi, beta_i)| {
1260 // si * ai
1261 ntt_op.forward(ai.as_mut());
1262 mod_op.elwise_mul_mut(ai.as_mut(), to_s.as_ref());
1263 ntt_op.backward(ai.as_mut());
1264
1265 // ei + to_s*ai
1266 RandomFillGaussianInModulus::random_fill(rng, &q, bi.as_mut());
1267 mod_op.elwise_add_mut(bi.as_mut(), ai.as_ref());
1268
1269 // beta_i * -from_s
1270 // use ai as scratch space
1271 mod_op.elwise_scalar_mul(ai.as_mut(), neg_from_s.as_ref(), beta_i);
1272
1273 // bi = ei + to_s*ai + beta_i*-from_s
1274 mod_op.elwise_add_mut(bi.as_mut(), ai.as_ref());
1275 });
1276}
1277
1278pub(crate) fn galois_key_gen<
1279 Mmut: MatrixMut + MatrixEntity,
1280 ModOp: ArithmeticOps<Element = Mmut::MatElement>
1281 + VectorOps<Element = Mmut::MatElement>
1282 + GetModulus<Element = Mmut::MatElement>,
1283 NttOp: Ntt<Element = Mmut::MatElement>,
1284 S,
1285 R: RandomFillGaussianInModulus<[Mmut::MatElement], ModOp::M>,
1286 PR: RandomFillUniformInModulus<[Mmut::MatElement], ModOp::M>,
1287>(
1288 ksk_out: &mut Mmut,
1289 s: &[S],
1290 auto_k: isize,
1291 gadget_vector: &[Mmut::MatElement],
1292 mod_op: &ModOp,
1293 ntt_op: &NttOp,
1294 p_rng: &mut PR,
1295 rng: &mut R,
1296) where
1297 <Mmut as Matrix>::R: RowMut,
1298 Mmut::R: TryConvertFrom1<[S], ModOp::M> + RowEntity,
1299 Mmut::MatElement: Copy + Sub<Output = Mmut::MatElement>,
1300{
1301 let ring_size = s.len();
1302 let (auto_map_index, auto_map_sign) = generate_auto_map(ring_size, auto_k);
1303
1304 let q = mod_op.modulus();
1305
1306 // s(X) -> -s(X^k)
1307 let s = Mmut::R::try_convert_from(s, q);
1308 let mut neg_s_auto = Mmut::R::zeros(s.as_ref().len());
1309 izip!(s.as_ref(), auto_map_index.iter(), auto_map_sign.iter()).for_each(
1310 |(el, to_index, sign)| {
1311 // if sign is +ve (true), then negate because we need -s(X) (i.e. do the
1312 // opposite than the usual case)
1313 if *sign {
1314 neg_s_auto.as_mut()[*to_index] = mod_op.neg(el);
1315 } else {
1316 neg_s_auto.as_mut()[*to_index] = *el;
1317 }
1318 },
1319 );
1320
1321 // Ksk from -s(X^k) to s(X)
1322 rlwe_ksk_gen(
1323 ksk_out,
1324 neg_s_auto,
1325 s,
1326 gadget_vector,
1327 mod_op,
1328 ntt_op,
1329 p_rng,
1330 rng,
1331 );
1332}
1333
1334/// Encrypt polynomial m(X) as RLWE ciphertext.
1335///
1336/// - rlwe_out: returned RLWE ciphertext RLWE(m) in coefficient domain. RLWE
1337/// ciphertext is a matirx with first row consiting polynomial `a` and the
1338/// second rows consting polynomial `b`
1339pub(crate) fn secret_key_encrypt_rlwe<
1340 Ro: Row + RowMut + RowEntity,
1341 ModOp: VectorOps<Element = Ro::Element> + GetModulus<Element = Ro::Element>,
1342 NttOp: Ntt<Element = Ro::Element>,
1343 S,
1344 R: RandomFillGaussianInModulus<[Ro::Element], ModOp::M>,
1345 PR: RandomFillUniformInModulus<[Ro::Element], ModOp::M>,
1346>(
1347 m: &[Ro::Element],
1348 b_rlwe_out: &mut Ro,
1349 s: &[S],
1350 mod_op: &ModOp,
1351 ntt_op: &NttOp,
1352 p_rng: &mut PR,
1353 rng: &mut R,
1354) where
1355 Ro: TryConvertFrom1<[S], ModOp::M> + Debug,
1356{
1357 let ring_size = s.len();
1358 assert!(m.as_ref().len() == ring_size);
1359 assert!(b_rlwe_out.as_ref().len() == ring_size);
1360
1361 let q = mod_op.modulus();
1362
1363 // sample a
1364 let mut a = {
1365 let mut a = Ro::zeros(ring_size);
1366 RandomFillUniformInModulus::random_fill(p_rng, q, a.as_mut());
1367 a
1368 };
1369
1370 // s * a
1371 let mut sa = Ro::try_convert_from(s, q);
1372 ntt_op.forward(sa.as_mut());
1373 ntt_op.forward(a.as_mut());
1374 mod_op.elwise_mul_mut(sa.as_mut(), a.as_ref());
1375 ntt_op.backward(sa.as_mut());
1376
1377 // sample e
1378 RandomFillGaussianInModulus::random_fill(rng, q, b_rlwe_out.as_mut());
1379 mod_op.elwise_add_mut(b_rlwe_out.as_mut(), m.as_ref());
1380 mod_op.elwise_add_mut(b_rlwe_out.as_mut(), sa.as_ref());
1381}
1382
1383pub(crate) fn public_key_encrypt_rlwe<
1384 M: Matrix,
1385 Mmut: MatrixMut<MatElement = M::MatElement>,
1386 ModOp: VectorOps<Element = M::MatElement> + GetModulus<Element = M::MatElement>,
1387 NttOp: Ntt<Element = M::MatElement>,
1388 S,
1389 R: RandomFillGaussianInModulus<[M::MatElement], ModOp::M>
1390 + RandomFillUniformInModulus<[M::MatElement], ModOp::M>
1391 + RandomFill<[u8]>
1392 + RandomElementInModulus<usize, usize>,
1393>(
1394 rlwe_out: &mut Mmut,
1395 pk: &M,
1396 m: &[M::MatElement],
1397 mod_op: &ModOp,
1398 ntt_op: &NttOp,
1399 rng: &mut R,
1400) where
1401 <Mmut as Matrix>::R: RowMut + TryConvertFrom1<[S], ModOp::M> + RowEntity,
1402 M::MatElement: Copy,
1403 S: Zero + Signed + Copy,
1404{
1405 let ring_size = m.len();
1406 assert!(rlwe_out.dimension() == (2, ring_size));
1407
1408 let q = mod_op.modulus();
1409
1410 let mut u = vec![S::zero(); ring_size];
1411 fill_random_ternary_secret_with_hamming_weight(u.as_mut(), ring_size >> 1, rng);
1412 let mut u = Mmut::R::try_convert_from(&u, q);
1413 ntt_op.forward(u.as_mut());
1414
1415 let mut ua = Mmut::R::zeros(ring_size);
1416 ua.as_mut().copy_from_slice(pk.get_row_slice(0));
1417 let mut ub = Mmut::R::zeros(ring_size);
1418 ub.as_mut().copy_from_slice(pk.get_row_slice(1));
1419
1420 // a*u
1421 ntt_op.forward(ua.as_mut());
1422 mod_op.elwise_mul_mut(ua.as_mut(), u.as_ref());
1423 ntt_op.backward(ua.as_mut());
1424
1425 // b*u
1426 ntt_op.forward(ub.as_mut());
1427 mod_op.elwise_mul_mut(ub.as_mut(), u.as_ref());
1428 ntt_op.backward(ub.as_mut());
1429
1430 // sample error
1431 rlwe_out.iter_rows_mut().for_each(|ri| {
1432 RandomFillGaussianInModulus::random_fill(rng, &q, ri.as_mut());
1433 });
1434
1435 // a*u + e0
1436 mod_op.elwise_add_mut(rlwe_out.get_row_mut(0), ua.as_ref());
1437 // b*u + e1
1438 mod_op.elwise_add_mut(rlwe_out.get_row_mut(1), ub.as_ref());
1439
1440 // b*u + e1 + m
1441 mod_op.elwise_add_mut(rlwe_out.get_row_mut(1), m);
1442}
1443
1444/// Generates RLWE public key
1445pub(crate) fn gen_rlwe_public_key<
1446 Ro: RowMut + RowEntity,
1447 S,
1448 ModOp: VectorOps<Element = Ro::Element> + GetModulus<Element = Ro::Element>,
1449 NttOp: Ntt<Element = Ro::Element>,
1450 PRng: RandomFillUniformInModulus<[Ro::Element], ModOp::M>,
1451 Rng: RandomFillGaussianInModulus<[Ro::Element], ModOp::M>,
1452>(
1453 part_b_out: &mut Ro,
1454 s: &[S],
1455 ntt_op: &NttOp,
1456 mod_op: &ModOp,
1457 p_rng: &mut PRng,
1458 rng: &mut Rng,
1459) where
1460 Ro: TryConvertFrom1<[S], ModOp::M>,
1461{
1462 let ring_size = s.len();
1463 assert!(part_b_out.as_ref().len() == ring_size);
1464
1465 let q = mod_op.modulus();
1466
1467 // sample a
1468 let mut a = {
1469 let mut tmp = Ro::zeros(ring_size);
1470 RandomFillUniformInModulus::random_fill(p_rng, &q, tmp.as_mut());
1471 tmp
1472 };
1473 ntt_op.forward(a.as_mut());
1474
1475 // s*a
1476 let mut sa = Ro::try_convert_from(s, &q);
1477 ntt_op.forward(sa.as_mut());
1478 mod_op.elwise_mul_mut(sa.as_mut(), a.as_ref());
1479 ntt_op.backward(sa.as_mut());
1480
1481 // s*a + e
1482 RandomFillGaussianInModulus::random_fill(rng, &q, part_b_out.as_mut());
1483 mod_op.elwise_add_mut(part_b_out.as_mut(), sa.as_ref());
1484}
1485
1486/// Decrypts degree 1 RLWE ciphertext RLWE(m) and returns m
1487///
1488/// - rlwe_ct: input degree 1 ciphertext RLWE(m).
1489pub(crate) fn decrypt_rlwe<
1490 R: RowMut,
1491 M: Matrix<MatElement = R::Element>,
1492 ModOp: VectorOps<Element = R::Element> + GetModulus<Element = R::Element>,
1493 NttOp: Ntt<Element = R::Element>,
1494 S,
1495>(
1496 rlwe_ct: &M,
1497 s: &[S],
1498 m_out: &mut R,
1499 ntt_op: &NttOp,
1500 mod_op: &ModOp,
1501) where
1502 R: TryConvertFrom1<[S], ModOp::M>,
1503 R::Element: Copy,
1504{
1505 let ring_size = s.len();
1506 assert!(rlwe_ct.dimension() == (2, ring_size));
1507 assert!(m_out.as_ref().len() == ring_size);
1508
1509 // transform a to evluation form
1510 m_out.as_mut().copy_from_slice(rlwe_ct.get_row_slice(0));
1511 ntt_op.forward(m_out.as_mut());
1512
1513 // -s*a
1514 let mut s = R::try_convert_from(&s, mod_op.modulus());
1515 ntt_op.forward(s.as_mut());
1516 mod_op.elwise_mul_mut(m_out.as_mut(), s.as_ref());
1517 mod_op.elwise_neg_mut(m_out.as_mut());
1518 ntt_op.backward(m_out.as_mut());
1519
1520 // m+e = b - s*a
1521 mod_op.elwise_add_mut(m_out.as_mut(), rlwe_ct.get_row_slice(1));
1522}
1523
1524// Measures noise in degree 1 RLWE ciphertext against encoded ideal message
1525// encoded_m
1526pub(crate) fn measure_noise<
1527 Mmut: MatrixMut + Matrix,
1528 ModOp: VectorOps<Element = Mmut::MatElement> + GetModulus<Element = Mmut::MatElement>,
1529 NttOp: Ntt<Element = Mmut::MatElement>,
1530 S,
1531>(
1532 rlwe_ct: &Mmut,
1533 encoded_m_ideal: &Mmut::R,
1534 ntt_op: &NttOp,
1535 mod_op: &ModOp,
1536 s: &[S],
1537) -> f64
1538where
1539 <Mmut as Matrix>::R: RowMut,
1540 Mmut::R: RowEntity + TryConvertFrom1<[S], ModOp::M>,
1541 Mmut::MatElement: PrimInt + ToPrimitive + Debug,
1542{
1543 let ring_size = s.len();
1544 assert!(rlwe_ct.dimension() == (2, ring_size));
1545 assert!(encoded_m_ideal.as_ref().len() == ring_size);
1546
1547 // -(s * a)
1548 let q = mod_op.modulus();
1549 let mut s = Mmut::R::try_convert_from(s, &q);
1550 ntt_op.forward(s.as_mut());
1551 let mut a = Mmut::R::zeros(ring_size);
1552 a.as_mut().copy_from_slice(rlwe_ct.get_row_slice(0));
1553 ntt_op.forward(a.as_mut());
1554 mod_op.elwise_mul_mut(s.as_mut(), a.as_ref());
1555 mod_op.elwise_neg_mut(s.as_mut());
1556 ntt_op.backward(s.as_mut());
1557
1558 // m+e = b - s*a
1559 let mut m_plus_e = s;
1560 mod_op.elwise_add_mut(m_plus_e.as_mut(), rlwe_ct.get_row_slice(1));
1561
1562 // difference
1563 mod_op.elwise_sub_mut(m_plus_e.as_mut(), encoded_m_ideal.as_ref());
1564
1565 let mut max_diff_bits = f64::MIN;
1566 m_plus_e.as_ref().iter().for_each(|v| {
1567 let bits = (q.map_element_to_i64(v).to_f64().unwrap()).log2();
1568
1569 if max_diff_bits < bits {
1570 max_diff_bits = bits;
1571 }
1572 });
1573
1574 return max_diff_bits;
1575}
1576
1577#[cfg(test)]
1578pub(crate) mod tests {
1579 use std::{marker::PhantomData, ops::Mul, vec};
1580
1581 use itertools::{izip, Itertools};
1582 use rand::{thread_rng, Rng};
1583
1584 use crate::{
1585 backend::{GetModulus, ModInit, ModularOpsU64, Modulus, VectorOps},
1586 decomposer::{Decomposer, DefaultDecomposer, RlweDecomposer},
1587 ntt::{self, Ntt, NttBackendU64, NttInit},
1588 random::{DefaultSecureRng, NewWithSeed, RandomFillUniformInModulus},
1589 rgsw::{
1590 gen_rlwe_public_key, measure_noise, public_key_encrypt_rgsw, AutoKeyEvaluationDomain,
1591 RgswCiphertext, RgswCiphertextEvaluationDomain, RlweCiphertext, RlwePublicKey,
1592 SeededAutoKey, SeededRgswCiphertext, SeededRlweCiphertext, SeededRlwePublicKey,
1593 },
1594 utils::{generate_prime, negacyclic_mul, Stats, TryConvertFrom1},
1595 Matrix, Secret,
1596 };
1597
1598 use super::{
1599 decrypt_rlwe, galois_auto, galois_key_gen, generate_auto_map, public_key_encrypt_rlwe,
1600 rgsw_by_rgsw_inplace, rlwe_by_rgsw, secret_key_encrypt_rgsw, secret_key_encrypt_rlwe,
1601 RlweSecret,
1602 };
1603
1604 pub(crate) fn _sk_encrypt_rlwe<T: Modulus<Element = u64> + Clone>(
1605 m: &[u64],
1606 s: &[i32],
1607 ntt_op: &NttBackendU64,
1608 mod_op: &ModularOpsU64<T>,
1609 ) -> RlweCiphertext<Vec<Vec<u64>>, DefaultSecureRng> {
1610 let ring_size = m.len();
1611 let q = mod_op.modulus();
1612 assert!(s.len() == ring_size);
1613
1614 let mut rng = DefaultSecureRng::new();
1615 let mut rlwe_seed = [0u8; 32];
1616 rng.fill_bytes(&mut rlwe_seed);
1617 let mut seeded_rlwe_ct =
1618 SeededRlweCiphertext::<_, [u8; 32], _>::empty(ring_size as usize, rlwe_seed, q.clone());
1619 let mut p_rng = DefaultSecureRng::new_seeded(rlwe_seed);
1620 secret_key_encrypt_rlwe(
1621 &m,
1622 &mut seeded_rlwe_ct.data,
1623 s,
1624 mod_op,
1625 ntt_op,
1626 &mut p_rng,
1627 &mut rng,
1628 );
1629
1630 RlweCiphertext::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_rlwe_ct)
1631 }
1632
1633 // Encrypt m as RGSW ciphertext RGSW(m) using supplied public key
1634 pub(crate) fn _pk_encrypt_rgsw<T: Modulus<Element = u64> + Clone>(
1635 m: &[u64],
1636 public_key: &RlwePublicKey<Vec<Vec<u64>>, DefaultSecureRng>,
1637 decomposer: &(DefaultDecomposer<u64>, DefaultDecomposer<u64>),
1638 mod_op: &ModularOpsU64<T>,
1639 ntt_op: &NttBackendU64,
1640 ) -> RgswCiphertext<Vec<Vec<u64>>, T> {
1641 let (_, ring_size) = Matrix::dimension(&public_key.data);
1642 let gadget_vector_a = decomposer.a().gadget_vector();
1643 let gadget_vector_b = decomposer.b().gadget_vector();
1644
1645 let mut rng = DefaultSecureRng::new();
1646
1647 assert!(m.len() == ring_size);
1648
1649 // public key encrypt RGSW(m1)
1650 let mut rgsw_ct = RgswCiphertext::empty(ring_size, decomposer, mod_op.modulus().clone());
1651 public_key_encrypt_rgsw(
1652 &mut rgsw_ct.data,
1653 m,
1654 &public_key.data,
1655 &gadget_vector_a,
1656 &gadget_vector_b,
1657 mod_op,
1658 ntt_op,
1659 &mut rng,
1660 );
1661
1662 rgsw_ct
1663 }
1664
1665 /// Encrypts m as RGSW ciphertext RGSW(m) using supplied secret key. Returns
1666 /// unseeded RGSW ciphertext in coefficient domain
1667 pub(crate) fn _sk_encrypt_rgsw<T: Modulus<Element = u64> + Clone>(
1668 m: &[u64],
1669 s: &[i32],
1670 decomposer: &(DefaultDecomposer<u64>, DefaultDecomposer<u64>),
1671 mod_op: &ModularOpsU64<T>,
1672 ntt_op: &NttBackendU64,
1673 ) -> SeededRgswCiphertext<Vec<Vec<u64>>, [u8; 32], T> {
1674 let ring_size = s.len();
1675 assert!(m.len() == s.len());
1676
1677 let q = mod_op.modulus();
1678
1679 let gadget_vector_a = decomposer.a().gadget_vector();
1680 let gadget_vector_b = decomposer.b().gadget_vector();
1681
1682 let mut rng = DefaultSecureRng::new();
1683 let mut rgsw_seed = [0u8; 32];
1684 rng.fill_bytes(&mut rgsw_seed);
1685 let mut seeded_rgsw_ct = SeededRgswCiphertext::<Vec<Vec<u64>>, [u8; 32], T>::empty(
1686 ring_size as usize,
1687 decomposer,
1688 rgsw_seed,
1689 q.clone(),
1690 );
1691 let mut p_rng = DefaultSecureRng::new_seeded(rgsw_seed);
1692 secret_key_encrypt_rgsw(
1693 &mut seeded_rgsw_ct.data,
1694 m,
1695 &gadget_vector_a,
1696 &gadget_vector_b,
1697 s,
1698 mod_op,
1699 ntt_op,
1700 &mut p_rng,
1701 &mut rng,
1702 );
1703 seeded_rgsw_ct
1704 }
1705
1706 /// Prints noise in RGSW ciphertext RGSW(m).
1707 ///
1708 /// - rgsw_ct: RGSW ciphertext in coefficient domain
1709 pub(crate) fn _measure_noise_rgsw<T: Modulus<Element = u64> + Clone>(
1710 rgsw_ct: &[Vec<u64>],
1711 m: &[u64],
1712 s: &[i32],
1713 decomposer: &(DefaultDecomposer<u64>, DefaultDecomposer<u64>),
1714 q: &T,
1715 ) {
1716 let gadget_vector_a = decomposer.a().gadget_vector();
1717 let gadget_vector_b = decomposer.b().gadget_vector();
1718 let d_a = gadget_vector_a.len();
1719 let d_b = gadget_vector_b.len();
1720 let ring_size = s.len();
1721 assert!(Matrix::dimension(&rgsw_ct) == (d_a * 2 + d_b * 2, ring_size));
1722 assert!(m.len() == ring_size);
1723
1724 let mod_op = ModularOpsU64::new(q.clone());
1725 let ntt_op = NttBackendU64::new(q, ring_size);
1726
1727 let mul_mod =
1728 |a: &u64, b: &u64| ((*a as u128 * *b as u128) % q.q().unwrap() as u128) as u64;
1729 let s_poly = Vec::<u64>::try_convert_from(s, q);
1730 let mut neg_s = s_poly.clone();
1731 mod_op.elwise_neg_mut(neg_s.as_mut());
1732 let neg_sm0m1 = negacyclic_mul(&neg_s, &m, mul_mod, q.q().unwrap());
1733
1734 // RLWE(\beta^j -s * m)
1735 for j in 0..d_a {
1736 let ideal_m = {
1737 // RLWE(\beta^j -s * m)
1738 let mut beta_neg_sm0m1 = vec![0u64; ring_size as usize];
1739 mod_op.elwise_scalar_mul(beta_neg_sm0m1.as_mut(), &neg_sm0m1, &gadget_vector_a[j]);
1740 beta_neg_sm0m1
1741 };
1742
1743 let mut rlwe = vec![vec![0u64; ring_size as usize]; 2];
1744 rlwe[0].copy_from_slice(rgsw_ct.get_row_slice(j));
1745 rlwe[1].copy_from_slice(rgsw_ct.get_row_slice(d_a + j));
1746 let noise = measure_noise(&rlwe, &ideal_m, &ntt_op, &mod_op, s);
1747
1748 println!(r"Noise RLWE(\beta^{j} -sm0m1): {noise}");
1749 }
1750
1751 // RLWE(\beta^j m)
1752 for j in 0..d_b {
1753 let ideal_m = {
1754 // RLWE(\beta^j m)
1755 let mut beta_m0m1 = vec![0u64; ring_size as usize];
1756 mod_op.elwise_scalar_mul(beta_m0m1.as_mut(), &m, &gadget_vector_b[j]);
1757 beta_m0m1
1758 };
1759
1760 let mut rlwe = vec![vec![0u64; ring_size as usize]; 2];
1761 rlwe[0].copy_from_slice(rgsw_ct.get_row_slice(d_a * 2 + j));
1762 rlwe[1].copy_from_slice(rgsw_ct.get_row_slice(d_a * 2 + d_b + j));
1763 let noise = measure_noise(&rlwe, &ideal_m, &ntt_op, &mod_op, s);
1764
1765 println!(r"Noise RLWE(\beta^{j} m0m1): {noise}");
1766 }
1767 }
1768
1769 #[test]
1770 fn rlwe_encrypt_decryption() {
1771 let logq = 50;
1772 let logp = 2;
1773 let ring_size = 1 << 4;
1774 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
1775 let p = 1u64 << logp;
1776
1777 let mut rng = DefaultSecureRng::new();
1778
1779 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
1780
1781 // sample m0
1782 let mut m0 = vec![0u64; ring_size as usize];
1783 RandomFillUniformInModulus::<[u64], u64>::random_fill(
1784 &mut rng,
1785 &(1u64 << logp),
1786 m0.as_mut_slice(),
1787 );
1788
1789 let ntt_op = NttBackendU64::new(&q, ring_size as usize);
1790 let mod_op = ModularOpsU64::new(q);
1791
1792 // encrypt m0
1793 let encoded_m = m0
1794 .iter()
1795 .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
1796 .collect_vec();
1797 let rlwe_in_ct = _sk_encrypt_rlwe(&encoded_m, s.values(), &ntt_op, &mod_op);
1798
1799 let mut encoded_m_back = vec![0u64; ring_size as usize];
1800 decrypt_rlwe(
1801 &rlwe_in_ct,
1802 s.values(),
1803 &mut encoded_m_back,
1804 &ntt_op,
1805 &mod_op,
1806 );
1807 let m_back = encoded_m_back
1808 .iter()
1809 .map(|v| (((*v as f64 * p as f64) / q as f64).round() as u64) % p)
1810 .collect_vec();
1811 assert_eq!(m0, m_back);
1812
1813 // let noise = measure_noise(&rlwe_in_ct, &encoded_m, &ntt_op, &mod_op,
1814 // s.values()); println!("Noise: {noise}");
1815 }
1816
1817 #[test]
1818 fn rlwe_by_rgsw_works() {
1819 let logq = 50;
1820 let logp = 2;
1821 let ring_size = 1 << 9;
1822 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
1823 let p: u64 = 1u64 << logp;
1824
1825 let mut rng = DefaultSecureRng::new_seeded([0u8; 32]);
1826
1827 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
1828
1829 let mut m0 = vec![0u64; ring_size as usize];
1830 RandomFillUniformInModulus::<[u64], _>::random_fill(
1831 &mut rng,
1832 &(1u64 << logp),
1833 m0.as_mut_slice(),
1834 );
1835 let mut m1 = vec![0u64; ring_size as usize];
1836 m1[thread_rng().gen_range(0..ring_size) as usize] = 1;
1837
1838 let ntt_op = NttBackendU64::new(&q, ring_size as usize);
1839 let mod_op = ModularOpsU64::new(q);
1840 let d_rgsw = 10;
1841 let logb = 5;
1842 let decomposer = (
1843 DefaultDecomposer::new(q, logb, d_rgsw),
1844 DefaultDecomposer::new(q, logb, d_rgsw),
1845 );
1846
1847 // create public key
1848 let mut pk_seed = [0u8; 32];
1849 rng.fill_bytes(&mut pk_seed);
1850 let mut pk_prng = DefaultSecureRng::new_seeded(pk_seed);
1851 let mut seeded_pk =
1852 SeededRlwePublicKey::<Vec<u64>, _>::empty(ring_size as usize, pk_seed, q);
1853 gen_rlwe_public_key(
1854 &mut seeded_pk.data,
1855 s.values(),
1856 &ntt_op,
1857 &mod_op,
1858 &mut pk_prng,
1859 &mut rng,
1860 );
1861 let pk = RlwePublicKey::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_pk);
1862
1863 // Encrypt m1 as RGSW(m1)
1864 let rgsw_ct = {
1865 //TODO(Jay): Figure out better way to test secret key and public key variant of
1866 // RGSW ciphertext encryption within the same test
1867
1868 if true {
1869 // Encryption m1 as RGSW(m1) using secret key
1870 let seeded_rgsw_ct =
1871 _sk_encrypt_rgsw(&m1, s.values(), &decomposer, &mod_op, &ntt_op);
1872 RgswCiphertextEvaluationDomain::<Vec<Vec<u64>>, DefaultSecureRng, NttBackendU64>::from(&seeded_rgsw_ct)
1873 } else {
1874 // Encrypt m1 as RGSW(m1) using public key
1875 let rgsw_ct = _pk_encrypt_rgsw(&m1, &pk, &decomposer, &mod_op, &ntt_op);
1876 RgswCiphertextEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(&rgsw_ct)
1877 }
1878 };
1879
1880 // Encrypt m0 as RLWE(m0)
1881 let mut rlwe_in_ct = {
1882 let encoded_m = m0
1883 .iter()
1884 .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
1885 .collect_vec();
1886
1887 _sk_encrypt_rlwe(&encoded_m, s.values(), &ntt_op, &mod_op)
1888 };
1889
1890 // RLWE(m0m1) = RLWE(m0) x RGSW(m1)
1891 let mut scratch_space = vec![
1892 vec![0u64; ring_size as usize];
1893 std::cmp::max(
1894 decomposer.a().decomposition_count(),
1895 decomposer.b().decomposition_count()
1896 ) + 2
1897 ];
1898 rlwe_by_rgsw(
1899 &mut rlwe_in_ct,
1900 &rgsw_ct.data,
1901 &mut scratch_space,
1902 &decomposer,
1903 &ntt_op,
1904 &mod_op,
1905 );
1906
1907 // Decrypt RLWE(m0m1)
1908 let mut encoded_m0m1_back = vec![0u64; ring_size as usize];
1909 decrypt_rlwe(
1910 &rlwe_in_ct,
1911 s.values(),
1912 &mut encoded_m0m1_back,
1913 &ntt_op,
1914 &mod_op,
1915 );
1916 let m0m1_back = encoded_m0m1_back
1917 .iter()
1918 .map(|v| (((*v as f64 * p as f64) / (q as f64)).round() as u64) % p)
1919 .collect_vec();
1920
1921 let mul_mod = |v0: &u64, v1: &u64| (v0 * v1) % p;
1922 let m0m1 = negacyclic_mul(&m0, &m1, mul_mod, p);
1923
1924 // {
1925 // // measure noise
1926 // let encoded_m_ideal = m0m1
1927 // .iter()
1928 // .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
1929 // .collect_vec();
1930
1931 // let noise = measure_noise(&rlwe_in_ct, &encoded_m_ideal, &ntt_op,
1932 // &mod_op, s.values()); println!("Noise RLWE(m0m1)(=
1933 // RLWE(m0)xRGSW(m1)) : {noise}"); }
1934
1935 assert!(
1936 m0m1 == m0m1_back,
1937 "Expected {:?} \n Got {:?}",
1938 m0m1,
1939 m0m1_back
1940 );
1941 }
1942
1943 #[test]
1944 fn galois_auto_works() {
1945 let logq = 55;
1946 let ring_size = 1 << 11;
1947 let q = generate_prime(logq, 2 * ring_size, 1u64 << logq).unwrap();
1948 let logp = 3;
1949 let p = 1u64 << logp;
1950 let d_rgsw = 5;
1951 let logb = 11;
1952
1953 let mut rng = DefaultSecureRng::new();
1954 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
1955
1956 let mut m = vec![0u64; ring_size as usize];
1957 RandomFillUniformInModulus::random_fill(&mut rng, &p, m.as_mut_slice());
1958 let encoded_m = m
1959 .iter()
1960 .map(|v| (((*v as f64 * q as f64) / (p as f64)).round() as u64))
1961 .collect_vec();
1962
1963 let ntt_op = NttBackendU64::new(&q, ring_size as usize);
1964 let mod_op = ModularOpsU64::new(q);
1965
1966 // RLWE_{s}(m)
1967 let mut seed_rlwe = [0u8; 32];
1968 rng.fill_bytes(&mut seed_rlwe);
1969 let mut seeded_rlwe_m = SeededRlweCiphertext::empty(ring_size as usize, seed_rlwe, q);
1970 let mut p_rng = DefaultSecureRng::new_seeded(seed_rlwe);
1971 secret_key_encrypt_rlwe(
1972 &encoded_m,
1973 &mut seeded_rlwe_m.data,
1974 s.values(),
1975 &mod_op,
1976 &ntt_op,
1977 &mut p_rng,
1978 &mut rng,
1979 );
1980 let mut rlwe_m = RlweCiphertext::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_rlwe_m);
1981
1982 let auto_k = -125;
1983
1984 // Generate galois key to key switch from s^k to s
1985 let decomposer = DefaultDecomposer::new(q, logb, d_rgsw);
1986 let mut seed_auto = [0u8; 32];
1987 rng.fill_bytes(&mut seed_auto);
1988 let mut seeded_auto_key =
1989 SeededAutoKey::empty(ring_size as usize, &decomposer, seed_auto, q);
1990 let mut p_rng = DefaultSecureRng::new_seeded(seed_auto);
1991 let gadget_vector = decomposer.gadget_vector();
1992 galois_key_gen(
1993 &mut seeded_auto_key.data,
1994 s.values(),
1995 auto_k,
1996 &gadget_vector,
1997 &mod_op,
1998 &ntt_op,
1999 &mut p_rng,
2000 &mut rng,
2001 );
2002 let auto_key =
2003 AutoKeyEvaluationDomain::<Vec<Vec<u64>>, DefaultSecureRng, NttBackendU64>::from(
2004 &seeded_auto_key,
2005 );
2006
2007 // Send RLWE_{s}(m) -> RLWE_{s}(m^k)
2008 let mut scratch_space = vec![vec![0u64; ring_size as usize]; d_rgsw + 2];
2009 let (auto_map_index, auto_map_sign) = generate_auto_map(ring_size as usize, auto_k);
2010 galois_auto(
2011 &mut rlwe_m,
2012 &auto_key.data,
2013 &mut scratch_space,
2014 &auto_map_index,
2015 &auto_map_sign,
2016 &mod_op,
2017 &ntt_op,
2018 &decomposer,
2019 );
2020
2021 let rlwe_m_k = rlwe_m;
2022
2023 // Decrypt RLWE_{s}(m^k) and check
2024 let mut encoded_m_k_back = vec![0u64; ring_size as usize];
2025 decrypt_rlwe(
2026 &rlwe_m_k,
2027 s.values(),
2028 &mut encoded_m_k_back,
2029 &ntt_op,
2030 &mod_op,
2031 );
2032 let m_k_back = encoded_m_k_back
2033 .iter()
2034 .map(|v| (((*v as f64 * p as f64) / q as f64).round() as u64) % p)
2035 .collect_vec();
2036
2037 let mut m_k = vec![0u64; ring_size as usize];
2038 // Send \delta m -> \delta m^k
2039 izip!(m.iter(), auto_map_index.iter(), auto_map_sign.iter()).for_each(
2040 |(v, to_index, sign)| {
2041 if !*sign {
2042 m_k[*to_index] = (p - *v) % p;
2043 } else {
2044 m_k[*to_index] = *v;
2045 }
2046 },
2047 );
2048
2049 {
2050 let encoded_m_k = m_k
2051 .iter()
2052 .map(|v| ((*v as f64 * q as f64) / p as f64).round() as u64)
2053 .collect_vec();
2054
2055 let noise = measure_noise(&rlwe_m_k, &encoded_m_k, &ntt_op, &mod_op, s.values());
2056 println!("Ksk noise: {noise}");
2057 }
2058
2059 assert_eq!(m_k_back, m_k);
2060 }
2061
2062 #[test]
2063 fn sk_rgsw_by_rgsw() {
2064 let logq = 60;
2065 let logp = 2;
2066 let ring_size = 1 << 11;
2067 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
2068 let p = 1u64 << logp;
2069 let d_rgsw = 5;
2070 let logb = 12;
2071
2072 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
2073
2074 let mut rng = DefaultSecureRng::new();
2075 let ntt_op = NttBackendU64::new(&q, ring_size as usize);
2076 let mod_op = ModularOpsU64::new(q);
2077 let decomposer = (
2078 DefaultDecomposer::new(q, logb, d_rgsw),
2079 DefaultDecomposer::new(q, logb, d_rgsw),
2080 );
2081
2082 let mul_mod = |a: &u64, b: &u64| ((*a as u128 * *b as u128) % q as u128) as u64;
2083
2084 let mut carry_m = vec![0u64; ring_size as usize];
2085 carry_m[thread_rng().gen_range(0..ring_size) as usize] = 1;
2086
2087 // RGSW(carry_m)
2088 let mut rgsw_carrym = {
2089 let seeded_rgsw = _sk_encrypt_rgsw(&carry_m, s.values(), &decomposer, &mod_op, &ntt_op);
2090 let mut rgsw_eval =
2091 RgswCiphertextEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(
2092 &seeded_rgsw,
2093 );
2094 rgsw_eval
2095 .data
2096 .iter_mut()
2097 .for_each(|ri| ntt_op.backward(ri.as_mut()));
2098 rgsw_eval.data
2099 };
2100
2101 let mut scratch_matrix = vec![
2102 vec![0u64; ring_size as usize];
2103 decomposer.a().decomposition_count() * 2
2104 + decomposer.b().decomposition_count() * 2
2105 + std::cmp::max(
2106 decomposer.a().decomposition_count(),
2107 decomposer.b().decomposition_count()
2108 )
2109 ];
2110
2111 _measure_noise_rgsw(&rgsw_carrym, &carry_m, s.values(), &decomposer, &q);
2112
2113 for i in 0..2 {
2114 let mut m = vec![0u64; ring_size as usize];
2115 m[thread_rng().gen_range(0..ring_size) as usize] = if (i & 1) == 1 { q - 1 } else { 1 };
2116 let rgsw_m = RgswCiphertextEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(
2117 &_sk_encrypt_rgsw(&m, s.values(), &decomposer, &mod_op, &ntt_op),
2118 );
2119 rgsw_by_rgsw_inplace(
2120 &mut rgsw_carrym,
2121 &rgsw_m.data,
2122 &decomposer,
2123 &mut scratch_matrix,
2124 &ntt_op,
2125 &mod_op,
2126 );
2127
2128 // measure noise
2129 carry_m = negacyclic_mul(&carry_m, &m, mul_mod, q);
2130 println!("########### Noise RGSW(carrym) in {i}^th loop ###########");
2131 _measure_noise_rgsw(&rgsw_carrym, &carry_m, s.values(), &decomposer, &q);
2132 }
2133 {
2134 // RLWE(m) x RGSW(carry_m)
2135 let mut m = vec![0u64; ring_size as usize];
2136 RandomFillUniformInModulus::random_fill(&mut rng, &q, m.as_mut_slice());
2137 let mut rlwe_ct = _sk_encrypt_rlwe(&m, s.values(), &ntt_op, &mod_op);
2138
2139 // send rgsw to evaluation domain
2140 rgsw_carrym
2141 .iter_mut()
2142 .for_each(|ri| ntt_op.forward(ri.as_mut_slice()));
2143
2144 rlwe_by_rgsw(
2145 &mut rlwe_ct,
2146 &rgsw_carrym,
2147 &mut scratch_matrix,
2148 &decomposer,
2149 &ntt_op,
2150 &mod_op,
2151 );
2152 let m_expected = negacyclic_mul(&carry_m, &m, mul_mod, q);
2153 let noise = measure_noise(&rlwe_ct, &m_expected, &ntt_op, &mod_op, s.values());
2154 println!("RLWE(m) x RGSW(carry_m): {noise}");
2155 }
2156 }
2157
2158 #[test]
2159 fn some_work() {
2160 let logq = 50;
2161 let ring_size = 1 << 11;
2162 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
2163 let d_rgsw = 10;
2164 let logb = 5;
2165 let decomposer = (
2166 DefaultDecomposer::new(q, logb, d_rgsw),
2167 DefaultDecomposer::new(q, logb, d_rgsw),
2168 );
2169
2170 let ntt_op = NttBackendU64::new(&q, ring_size as usize);
2171 let mod_op = ModularOpsU64::new(q);
2172 let mut rng = DefaultSecureRng::new_seeded([0u8; 32]);
2173
2174 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
2175
2176 let mut check = Stats { samples: vec![] };
2177
2178 for _ in 0..100 {
2179 let mut m0 = vec![0u64; ring_size as usize];
2180 m0[thread_rng().gen_range(0..ring_size) as usize] = 1;
2181 let mut m1 = vec![0u64; ring_size as usize];
2182 m1[thread_rng().gen_range(0..ring_size) as usize] = 1;
2183
2184 let mut rgsw_ct0 = {
2185 let seeded_rgsw_ct =
2186 _sk_encrypt_rgsw(&m0, s.values(), &decomposer, &mod_op, &ntt_op);
2187 RgswCiphertextEvaluationDomain::<Vec<Vec<u64>>, DefaultSecureRng, NttBackendU64>::from(&seeded_rgsw_ct)
2188 };
2189 let rgsw_ct1 = {
2190 let seeded_rgsw_ct =
2191 _sk_encrypt_rgsw(&m1, s.values(), &decomposer, &mod_op, &ntt_op);
2192 RgswCiphertextEvaluationDomain::<Vec<Vec<u64>>, DefaultSecureRng, NttBackendU64>::from(&seeded_rgsw_ct)
2193 };
2194
2195 // RGSW x RGSW
2196 // send RGSW(m0) to coefficient domain
2197 rgsw_ct0
2198 .data
2199 .iter_mut()
2200 .for_each(|r| ntt_op.backward(r.as_mut_slice()));
2201 let mut scratch_matrix = vec![
2202 vec![0u64; ring_size as usize];
2203 std::cmp::max(
2204 decomposer.a().decomposition_count(),
2205 decomposer.b().decomposition_count()
2206 ) + decomposer.a().decomposition_count() * 2
2207 + decomposer.b().decomposition_count() * 2
2208 ];
2209 rgsw_by_rgsw_inplace(
2210 &mut rgsw_ct0.data,
2211 &rgsw_ct1.data,
2212 &decomposer,
2213 &mut scratch_matrix,
2214 &ntt_op,
2215 &mod_op,
2216 );
2217 let mut rgsw_m0m1 = rgsw_ct0;
2218 // Back to Evaluation for RLWExRGSW
2219 rgsw_m0m1
2220 .data
2221 .iter_mut()
2222 .for_each(|r| ntt_op.forward(r.as_mut_slice()));
2223
2224 // Sample m2, encrypt it as RLWE(m2) and multiply RLWE(m2)xRGSW(m0m1)
2225 let mut m2 = vec![0u64; ring_size as usize];
2226 RandomFillUniformInModulus::random_fill(&mut rng, &q, m2.as_mut_slice());
2227 let mut rlwe_in_ct = { _sk_encrypt_rlwe(&m2, s.values(), &ntt_op, &mod_op) };
2228 let mut scratch_space = vec![
2229 vec![0u64; ring_size as usize];
2230 std::cmp::max(
2231 decomposer.a().decomposition_count(),
2232 decomposer.b().decomposition_count()
2233 ) + 2
2234 ];
2235 rlwe_by_rgsw(
2236 &mut rlwe_in_ct,
2237 &rgsw_m0m1.data,
2238 &mut scratch_space,
2239 &decomposer,
2240 &ntt_op,
2241 &mod_op,
2242 );
2243
2244 // Decrypt RLWE(m0m1m2)
2245 let mut m0m1m2_back = vec![0u64; ring_size as usize];
2246 decrypt_rlwe(&rlwe_in_ct, s.values(), &mut m0m1m2_back, &ntt_op, &mod_op);
2247
2248 // Calculate m0m1m2
2249 let mul_mod = |v0: &u64, v1: &u64| ((*v0 as u128 * *v1 as u128) % q as u128) as u64;
2250 let m0m1 = negacyclic_mul(&m0, &m1, mul_mod, q);
2251 let m0m1m2 = negacyclic_mul(&m2, &m0m1, mul_mod, q);
2252
2253 // diff
2254 mod_op.elwise_sub_mut(m0m1m2_back.as_mut_slice(), m0m1m2.as_ref());
2255
2256 check.add_more(&Vec::<i64>::try_convert_from(&m0m1m2_back, &q));
2257 }
2258
2259 println!("Std: {}", check.std_dev().abs().log2());
2260 }
2261}