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