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(&r[ri]);
522 for j in 0..d {
523 decomp_r[j].as_mut()[ri] = el_decomposed[j];
524 }
525 }
526}
527
528/// Sends RLWE_{s}(X) -> RLWE_{s}(X^k) where k is some galois element
529///
530/// - scratch_matrix: must have dimension at-least d+2 x ring_size. d rows to
531/// store decomposed polynomials and 2 for rlwe
532pub(crate) fn galois_auto<
533 MT: Matrix + IsTrivial + MatrixMut,
534 Mmut: MatrixMut<MatElement = MT::MatElement>,
535 ModOp: ArithmeticOps<Element = MT::MatElement> + VectorOps<Element = MT::MatElement>,
536 NttOp: Ntt<Element = MT::MatElement>,
537 D: Decomposer<Element = MT::MatElement>,
538>(
539 rlwe_in: &mut MT,
540 ksk: &Mmut,
541 scratch_matrix: &mut Mmut,
542 auto_map_index: &[usize],
543 auto_map_sign: &[bool],
544 mod_op: &ModOp,
545 ntt_op: &NttOp,
546 decomposer: &D,
547) where
548 <Mmut as Matrix>::R: RowMut,
549 <MT as Matrix>::R: RowMut,
550 MT::MatElement: Copy + Zero,
551{
552 let d = decomposer.decomposition_count();
553 let ring_size = rlwe_in.dimension().1;
554 assert!(rlwe_in.dimension().0 == 2);
555 assert!(scratch_matrix.fits(d + 2, ring_size));
556
557 let (scratch_matrix_d_ring, tmp_rlwe_out) = scratch_matrix.split_at_row_mut(d);
558
559 // send b(X) -> b(X^k)
560 izip!(
561 rlwe_in.get_row(1),
562 auto_map_index.iter(),
563 auto_map_sign.iter()
564 )
565 .for_each(|(el_in, to_index, sign)| {
566 if !*sign {
567 tmp_rlwe_out[1].as_mut()[*to_index] = mod_op.neg(el_in);
568 } else {
569 tmp_rlwe_out[1].as_mut()[*to_index] = *el_in;
570 // scratch_matrix_dplus2_ring.set(d + 1, *to_index, *el_in);
571 }
572 });
573
574 if !rlwe_in.is_trivial() {
575 // send a(X) -> a(X^k) and decompose a(X^k)
576 izip!(
577 rlwe_in.get_row(0),
578 auto_map_index.iter(),
579 auto_map_sign.iter()
580 )
581 .for_each(|(el_in, to_index, sign)| {
582 let el_out = if !*sign { mod_op.neg(el_in) } else { *el_in };
583
584 let el_out_decomposed = decomposer.decompose(&el_out);
585 for j in 0..d {
586 scratch_matrix_d_ring[j].as_mut()[*to_index] = el_out_decomposed[j];
587 }
588 });
589
590 // transform decomposed a(X^k) to evaluation domain
591 scratch_matrix_d_ring.iter_mut().for_each(|r| {
592 ntt_op.forward(r.as_mut());
593 });
594
595 // RLWE(m^k) = a', b'; RLWE(m) = a, b
596 // key switch: (a * RLWE'(s(X^k)))
597 let (ksk_a, ksk_b) = ksk.split_at_row(d);
598 tmp_rlwe_out[0].as_mut().fill(Mmut::MatElement::zero());
599 // a' = decomp<a> * RLWE'_A(s(X^k))
600 routine(
601 tmp_rlwe_out[0].as_mut(),
602 scratch_matrix_d_ring,
603 ksk_a,
604 mod_op,
605 );
606 // send b(X^k) to evaluation domain
607 ntt_op.forward(tmp_rlwe_out[1].as_mut());
608 // b' = b(X^k)
609 // b' += decomp<a(X^k)> * RLWE'_B(s(X^k))
610 routine(
611 tmp_rlwe_out[1].as_mut(),
612 scratch_matrix_d_ring,
613 ksk_b,
614 mod_op,
615 );
616
617 // transform RLWE(m^k) to coefficient domain
618 tmp_rlwe_out
619 .iter_mut()
620 .for_each(|r| ntt_op.backward(r.as_mut()));
621
622 rlwe_in
623 .get_row_mut(0)
624 .copy_from_slice(tmp_rlwe_out[0].as_ref());
625 }
626
627 rlwe_in
628 .get_row_mut(1)
629 .copy_from_slice(tmp_rlwe_out[1].as_ref());
630}
631
632/// Returns RLWE(m0m1) = RLWE(m0) x RGSW(m1). Mutates rlwe_in inplace to equal
633/// RLWE(m0m1)
634///
635/// - rlwe_in: is RLWE(m0) with polynomials in coefficient domain
636/// - rgsw_in: is RGSW(m1) with polynomials in evaluation domain
637/// - scratch_matrix_d_ring: is a matrix of dimension (d_rgsw, ring_size) used
638/// as scratch space to store decomposed Ring elements temporarily
639pub(crate) fn less1_rlwe_by_rgsw<
640 Mmut: MatrixMut,
641 MT: Matrix<MatElement = Mmut::MatElement> + MatrixMut<MatElement = Mmut::MatElement> + IsTrivial,
642 D: Decomposer<Element = Mmut::MatElement>,
643 ModOp: VectorOps<Element = Mmut::MatElement>,
644 NttOp: Ntt<Element = Mmut::MatElement>,
645>(
646 rlwe_in: &mut MT,
647 rgsw_in: &Mmut,
648 scratch_matrix_dplus2_ring: &mut Mmut,
649 decomposer: &D,
650 ntt_op: &NttOp,
651 mod_op: &ModOp,
652 skip0: usize,
653 skip1: usize,
654) where
655 Mmut::MatElement: Copy + Zero,
656 <Mmut as Matrix>::R: RowMut,
657 <MT as Matrix>::R: RowMut,
658{
659 let d_rgsw = decomposer.decomposition_count();
660 assert!(scratch_matrix_dplus2_ring.dimension() == (d_rgsw + 2, rlwe_in.dimension().1));
661 assert!(rgsw_in.dimension() == (d_rgsw * 4, rlwe_in.dimension().1));
662
663 // decomposed RLWE x RGSW
664 let (rlwe_dash_nsm, rlwe_dash_m) = rgsw_in.split_at_row(d_rgsw * 2);
665 let (scratch_matrix_d_ring, scratch_rlwe_out) =
666 scratch_matrix_dplus2_ring.split_at_row_mut(d_rgsw);
667 scratch_rlwe_out[0].as_mut().fill(Mmut::MatElement::zero());
668 scratch_rlwe_out[1].as_mut().fill(Mmut::MatElement::zero());
669 // RLWE_in = a_in, b_in; RLWE_out = a_out, b_out
670 if !rlwe_in.is_trivial() {
671 // a_in = 0 when RLWE_in is trivial RLWE ciphertext
672 // decomp<a_in>
673 decompose_r(rlwe_in.get_row_slice(0), scratch_matrix_d_ring, decomposer);
674 scratch_matrix_d_ring
675 .iter_mut()
676 .for_each(|r| ntt_op.forward(r.as_mut()));
677 // a_out += decomp<a_in> \cdot RLWE_A'(-sm)
678 routine(
679 scratch_rlwe_out[0].as_mut(),
680 scratch_matrix_d_ring[skip0..].as_ref(),
681 &rlwe_dash_nsm[skip0..d_rgsw],
682 mod_op,
683 );
684 // b_out += decomp<a_in> \cdot RLWE_B'(-sm)
685 routine(
686 scratch_rlwe_out[1].as_mut(),
687 scratch_matrix_d_ring[skip0..].as_ref(),
688 &rlwe_dash_nsm[d_rgsw + skip0..],
689 mod_op,
690 );
691 }
692 // decomp<b_in>
693 decompose_r(rlwe_in.get_row_slice(1), scratch_matrix_d_ring, decomposer);
694 scratch_matrix_d_ring
695 .iter_mut()
696 .for_each(|r| ntt_op.forward(r.as_mut()));
697 // a_out += decomp<b_in> \cdot RLWE_A'(m)
698 routine(
699 scratch_rlwe_out[0].as_mut(),
700 scratch_matrix_d_ring[skip1..].as_ref(),
701 &rlwe_dash_m[skip1..d_rgsw],
702 mod_op,
703 );
704 // b_out += decomp<b_in> \cdot RLWE_B'(m)
705 routine(
706 scratch_rlwe_out[1].as_mut(),
707 scratch_matrix_d_ring[skip1..].as_ref(),
708 &rlwe_dash_m[d_rgsw + skip1..],
709 mod_op,
710 );
711
712 // transform rlwe_out to coefficient domain
713 scratch_rlwe_out
714 .iter_mut()
715 .for_each(|r| ntt_op.backward(r.as_mut()));
716
717 rlwe_in
718 .get_row_mut(0)
719 .copy_from_slice(scratch_rlwe_out[0].as_mut());
720 rlwe_in
721 .get_row_mut(1)
722 .copy_from_slice(scratch_rlwe_out[1].as_mut());
723 rlwe_in.set_not_trivial();
724}
725
726/// Returns RLWE(m0m1) = RLWE(m0) x RGSW(m1). Mutates rlwe_in inplace to equal
727/// RLWE(m0m1)
728///
729/// - rlwe_in: is RLWE(m0) with polynomials in coefficient domain
730/// - rgsw_in: is RGSW(m1) with polynomials in evaluation domain
731/// - scratch_matrix_d_ring: is a matrix with atleast max(d_a, d_b) rows and
732/// ring_size columns. It's used to store decomposed polynomials and out RLWE
733/// temoporarily
734pub(crate) fn rlwe_by_rgsw<
735 Mmut: MatrixMut,
736 MT: Matrix<MatElement = Mmut::MatElement> + MatrixMut<MatElement = Mmut::MatElement> + IsTrivial,
737 D: RlweDecomposer<Element = Mmut::MatElement>,
738 ModOp: VectorOps<Element = Mmut::MatElement>,
739 NttOp: Ntt<Element = Mmut::MatElement>,
740>(
741 rlwe_in: &mut MT,
742 rgsw_in: &Mmut,
743 scratch_matrix: &mut Mmut,
744 decomposer: &D,
745 ntt_op: &NttOp,
746 mod_op: &ModOp,
747) where
748 Mmut::MatElement: Copy + Zero,
749 <Mmut as Matrix>::R: RowMut,
750 <MT as Matrix>::R: RowMut,
751{
752 let decomposer_a = decomposer.a();
753 let decomposer_b = decomposer.b();
754 let d_a = decomposer_a.decomposition_count();
755 let d_b = decomposer_b.decomposition_count();
756 let max_d = std::cmp::max(d_a, d_b);
757 assert!(scratch_matrix.fits(max_d + 2, rlwe_in.dimension().1));
758 assert!(rgsw_in.dimension() == (d_a * 2 + d_b * 2, rlwe_in.dimension().1));
759
760 // decomposed RLWE x RGSW
761 let (rlwe_dash_nsm, rlwe_dash_m) = rgsw_in.split_at_row(d_a * 2);
762 let (scratch_matrix_d_ring, scratch_rlwe_out) = scratch_matrix.split_at_row_mut(max_d);
763 scratch_rlwe_out[0].as_mut().fill(Mmut::MatElement::zero());
764 scratch_rlwe_out[1].as_mut().fill(Mmut::MatElement::zero());
765 // RLWE_in = a_in, b_in; RLWE_out = a_out, b_out
766 if !rlwe_in.is_trivial() {
767 // a_in = 0 when RLWE_in is trivial RLWE ciphertext
768 // decomp<a_in>
769 decompose_r(
770 rlwe_in.get_row_slice(0),
771 scratch_matrix_d_ring,
772 decomposer_a,
773 );
774 scratch_matrix_d_ring
775 .iter_mut()
776 .for_each(|r| ntt_op.forward(r.as_mut()));
777 // a_out += decomp<a_in> \cdot RLWE_A'(-sm)
778 routine(
779 scratch_rlwe_out[0].as_mut(),
780 scratch_matrix_d_ring.as_ref(),
781 &rlwe_dash_nsm[..d_a],
782 mod_op,
783 );
784 // b_out += decomp<a_in> \cdot RLWE_B'(-sm)
785 routine(
786 scratch_rlwe_out[1].as_mut(),
787 scratch_matrix_d_ring.as_ref(),
788 &rlwe_dash_nsm[d_a..],
789 mod_op,
790 );
791 }
792 // decomp<b_in>
793 decompose_r(
794 rlwe_in.get_row_slice(1),
795 scratch_matrix_d_ring,
796 decomposer_b,
797 );
798 scratch_matrix_d_ring
799 .iter_mut()
800 .for_each(|r| ntt_op.forward(r.as_mut()));
801 // a_out += decomp<b_in> \cdot RLWE_A'(m)
802 routine(
803 scratch_rlwe_out[0].as_mut(),
804 scratch_matrix_d_ring.as_ref(),
805 &rlwe_dash_m[..d_b],
806 mod_op,
807 );
808 // b_out += decomp<b_in> \cdot RLWE_B'(m)
809 routine(
810 scratch_rlwe_out[1].as_mut(),
811 scratch_matrix_d_ring.as_ref(),
812 &rlwe_dash_m[d_b..],
813 mod_op,
814 );
815
816 // transform rlwe_out to coefficient domain
817 scratch_rlwe_out
818 .iter_mut()
819 .for_each(|r| ntt_op.backward(r.as_mut()));
820
821 rlwe_in
822 .get_row_mut(0)
823 .copy_from_slice(scratch_rlwe_out[0].as_mut());
824 rlwe_in
825 .get_row_mut(1)
826 .copy_from_slice(scratch_rlwe_out[1].as_mut());
827 rlwe_in.set_not_trivial();
828}
829
830/// Inplace mutates rlwe_0 to equal RGSW(m0m1) = RGSW(m0)xRGSW(m1)
831/// in evaluation domain
832///
833/// Warning -
834/// Pass a fresh RGSW ciphertext as the second operand, i.e. as `rgsw_1`.
835/// This is to assure minimal error growth in the resulting RGSW ciphertext.
836/// RGSWxRGSW boils down to d_rgsw*2 RLWExRGSW multiplications. Hence, the noise
837/// growth in resulting ciphertext depends on the norm of second RGSW
838/// ciphertext, not the first. This is useful in cases where one is accumulating
839/// multiple RGSW ciphertexts into 1. In which case, pass the accumulating RGSW
840/// ciphertext as rlwe_0 (the one with higher noise) and subsequent RGSW
841/// ciphertexts, with lower noise, to be accumulated as second
842/// operand.
843///
844/// - rgsw_0: RGSW(m0)
845/// - rgsw_1_eval: RGSW(m1) in Evaluation domain
846/// - scratch_matrix_d_plus_rgsw_by_ring: scratch space matrix with rows
847/// (max(d_a, d_b) + d_a*2+d_b*2) and columns ring_size
848pub(crate) fn rgsw_by_rgsw_inplace<
849 Mmut: MatrixMut,
850 D: RlweDecomposer<Element = Mmut::MatElement>,
851 ModOp: VectorOps<Element = Mmut::MatElement>,
852 NttOp: Ntt<Element = Mmut::MatElement>,
853>(
854 rgsw_0: &mut Mmut,
855 rgsw_1_eval: &Mmut,
856 decomposer: &D,
857 scratch_matrix: &mut Mmut,
858 ntt_op: &NttOp,
859 mod_op: &ModOp,
860) where
861 <Mmut as Matrix>::R: RowMut,
862 Mmut::MatElement: Copy + Zero,
863{
864 let decomposer_a = decomposer.a();
865 let decomposer_b = decomposer.b();
866 let d_a = decomposer_a.decomposition_count();
867 let d_b = decomposer_b.decomposition_count();
868 let max_d = std::cmp::max(d_a, d_b);
869 let rgsw_rows = d_a * 2 + d_b * 2;
870 assert!(rgsw_0.dimension().0 == rgsw_rows);
871 let ring_size = rgsw_0.dimension().1;
872 assert!(rgsw_1_eval.dimension() == (rgsw_rows, ring_size));
873 assert!(scratch_matrix.fits(max_d + rgsw_rows, ring_size));
874
875 let (decomp_r_space, rgsw_space) = scratch_matrix.split_at_row_mut(max_d);
876
877 // zero rgsw_space
878 rgsw_space
879 .iter_mut()
880 .for_each(|ri| ri.as_mut().fill(Mmut::MatElement::zero()));
881 let (rlwe_dash_space_nsm, rlwe_dash_space_m) = rgsw_space.split_at_mut(d_a * 2);
882 let (rlwe_dash_space_nsm_parta, rlwe_dash_space_nsm_partb) =
883 rlwe_dash_space_nsm.split_at_mut(d_a);
884 let (rlwe_dash_space_m_parta, rlwe_dash_space_m_partb) = rlwe_dash_space_m.split_at_mut(d_b);
885
886 let (rgsw0_nsm, rgsw0_m) = rgsw_0.split_at_row(d_a * 2);
887 let (rgsw1_nsm, rgsw1_m) = rgsw_1_eval.split_at_row(d_a * 2);
888
889 // RGSW x RGSW
890 izip!(
891 rgsw0_nsm.iter().take(d_a).chain(rgsw0_m.iter().take(d_b)),
892 rgsw0_nsm.iter().skip(d_a).chain(rgsw0_m.iter().skip(d_b)),
893 rlwe_dash_space_nsm_parta
894 .iter_mut()
895 .chain(rlwe_dash_space_m_parta.iter_mut()),
896 rlwe_dash_space_nsm_partb
897 .iter_mut()
898 .chain(rlwe_dash_space_m_partb.iter_mut()),
899 )
900 .for_each(|(rlwe_a, rlwe_b, rlwe_out_a, rlwe_out_b)| {
901 // Part A
902 decompose_r(rlwe_a.as_ref(), decomp_r_space.as_mut(), decomposer_a);
903 decomp_r_space
904 .iter_mut()
905 .take(d_a)
906 .for_each(|ri| ntt_op.forward(ri.as_mut()));
907 routine(
908 rlwe_out_a.as_mut(),
909 &decomp_r_space[..d_a],
910 &rgsw1_nsm[..d_a],
911 mod_op,
912 );
913 routine(
914 rlwe_out_b.as_mut(),
915 &decomp_r_space[..d_a],
916 &rgsw1_nsm[d_a..],
917 mod_op,
918 );
919
920 // Part B
921 decompose_r(rlwe_b.as_ref(), decomp_r_space.as_mut(), decomposer_b);
922 decomp_r_space
923 .iter_mut()
924 .take(d_b)
925 .for_each(|ri| ntt_op.forward(ri.as_mut()));
926 routine(
927 rlwe_out_a.as_mut(),
928 &decomp_r_space[..d_b],
929 &rgsw1_m[..d_b],
930 mod_op,
931 );
932 routine(
933 rlwe_out_b.as_mut(),
934 &decomp_r_space[..d_b],
935 &rgsw1_m[d_b..],
936 mod_op,
937 );
938 });
939
940 // copy over RGSW(m0m1) into RGSW(m0)
941 izip!(rgsw_0.iter_rows_mut(), rgsw_space.iter())
942 .for_each(|(to_ri, from_ri)| to_ri.as_mut().copy_from_slice(from_ri.as_ref()));
943
944 // send back to coefficient domain
945 rgsw_0
946 .iter_rows_mut()
947 .for_each(|ri| ntt_op.backward(ri.as_mut()));
948}
949
950/// Encrypts message m as a RGSW ciphertext.
951///
952/// - m_eval: is `m` is evaluation domain
953/// - out_rgsw: RGSW(m) is stored as single matrix of dimension (d_rgsw * 3,
954/// ring_size). The matrix has the following structure [RLWE'_A(-sm) ||
955/// RLWE'_B(-sm) || RLWE'_B(m)]^T and RLWE'_A(m) is generated via seed (where
956/// p_rng is assumed to be seeded with seed)
957pub(crate) fn secret_key_encrypt_rgsw<
958 Mmut: MatrixMut + MatrixEntity,
959 S,
960 R: RandomFillGaussianInModulus<[Mmut::MatElement], ModOp::M>
961 + RandomFillUniformInModulus<[Mmut::MatElement], ModOp::M>,
962 PR: RandomFillUniformInModulus<[Mmut::MatElement], ModOp::M>,
963 ModOp: VectorOps<Element = Mmut::MatElement> + GetModulus<Element = Mmut::MatElement>,
964 NttOp: Ntt<Element = Mmut::MatElement>,
965>(
966 out_rgsw: &mut Mmut,
967 m: &[Mmut::MatElement],
968 gadget_a: &[Mmut::MatElement],
969 gadget_b: &[Mmut::MatElement],
970 s: &[S],
971 mod_op: &ModOp,
972 ntt_op: &NttOp,
973 p_rng: &mut PR,
974 rng: &mut R,
975) where
976 <Mmut as Matrix>::R: RowMut + RowEntity + TryConvertFrom1<[S], ModOp::M> + Debug,
977 Mmut::MatElement: Copy + Debug,
978{
979 let d_a = gadget_a.len();
980 let d_b = gadget_b.len();
981 let q = mod_op.modulus();
982 let ring_size = s.len();
983 assert!(out_rgsw.dimension() == (d_a * 2 + d_b, ring_size));
984 assert!(m.as_ref().len() == ring_size);
985
986 // RLWE(-sm), RLWE(m)
987 let (rlwe_dash_nsm, b_rlwe_dash_m) = out_rgsw.split_at_row_mut(d_a * 2);
988
989 let mut s_eval = Mmut::R::try_convert_from(s, &q);
990 ntt_op.forward(s_eval.as_mut());
991
992 let mut scratch_space = Mmut::R::zeros(ring_size);
993
994 // RLWE'(-sm)
995 let (a_rlwe_dash_nsm, b_rlwe_dash_nsm) = rlwe_dash_nsm.split_at_mut(d_a);
996 izip!(
997 a_rlwe_dash_nsm.iter_mut(),
998 b_rlwe_dash_nsm.iter_mut(),
999 gadget_a.iter()
1000 )
1001 .for_each(|(ai, bi, beta_i)| {
1002 // Sample a_i
1003 RandomFillUniformInModulus::random_fill(rng, &q, ai.as_mut());
1004
1005 // a_i * s
1006 scratch_space.as_mut().copy_from_slice(ai.as_ref());
1007 ntt_op.forward(scratch_space.as_mut());
1008 mod_op.elwise_mul_mut(scratch_space.as_mut(), s_eval.as_ref());
1009 ntt_op.backward(scratch_space.as_mut());
1010
1011 // b_i = e_i + a_i * s
1012 RandomFillGaussianInModulus::random_fill(rng, &q, bi.as_mut());
1013 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.as_ref());
1014
1015 // a_i + \beta_i * m
1016 mod_op.elwise_scalar_mul(scratch_space.as_mut(), m.as_ref(), beta_i);
1017 mod_op.elwise_add_mut(ai.as_mut(), scratch_space.as_ref());
1018 });
1019
1020 // RLWE(m)
1021 let mut a_rlwe_dash_m = {
1022 // polynomials of part A of RLWE'(m) are sampled from seed
1023 let mut a = Mmut::zeros(d_b, ring_size);
1024 a.iter_rows_mut()
1025 .for_each(|ai| RandomFillUniformInModulus::random_fill(p_rng, &q, ai.as_mut()));
1026 a
1027 };
1028
1029 izip!(
1030 a_rlwe_dash_m.iter_rows_mut(),
1031 b_rlwe_dash_m.iter_mut(),
1032 gadget_b.iter()
1033 )
1034 .for_each(|(ai, bi, beta_i)| {
1035 // ai * s
1036 ntt_op.forward(ai.as_mut());
1037 mod_op.elwise_mul_mut(ai.as_mut(), s_eval.as_ref());
1038 ntt_op.backward(ai.as_mut());
1039
1040 // beta_i * m
1041 mod_op.elwise_scalar_mul(scratch_space.as_mut(), m.as_ref(), beta_i);
1042
1043 // Sample e_i
1044 RandomFillGaussianInModulus::random_fill(rng, &q, bi.as_mut());
1045 // e_i + beta_i * m + ai*s
1046 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.as_ref());
1047 mod_op.elwise_add_mut(bi.as_mut(), ai.as_ref());
1048 });
1049}
1050
1051pub(crate) fn public_key_encrypt_rgsw<
1052 Mmut: MatrixMut + MatrixEntity,
1053 M: Matrix<MatElement = Mmut::MatElement>,
1054 R: RandomFillGaussianInModulus<[Mmut::MatElement], ModOp::M>
1055 + RandomFill<[u8]>
1056 + RandomElementInModulus<usize, usize>,
1057 ModOp: VectorOps<Element = Mmut::MatElement> + GetModulus<Element = Mmut::MatElement>,
1058 NttOp: Ntt<Element = Mmut::MatElement>,
1059>(
1060 out_rgsw: &mut Mmut,
1061 m: &[M::MatElement],
1062 public_key: &M,
1063 gadget_a: &[Mmut::MatElement],
1064 gadget_b: &[Mmut::MatElement],
1065 mod_op: &ModOp,
1066 ntt_op: &NttOp,
1067 rng: &mut R,
1068) where
1069 <Mmut as Matrix>::R: RowMut + RowEntity + TryConvertFrom1<[i32], ModOp::M>,
1070 Mmut::MatElement: Copy,
1071{
1072 let ring_size = public_key.dimension().1;
1073 let d_a = gadget_a.len();
1074 let d_b = gadget_b.len();
1075 assert!(public_key.dimension().0 == 2);
1076 assert!(out_rgsw.dimension() == (d_a * 2 + d_b * 2, ring_size));
1077
1078 let mut pk_eval = Mmut::zeros(2, ring_size);
1079 izip!(pk_eval.iter_rows_mut(), public_key.iter_rows()).for_each(|(to_i, from_i)| {
1080 to_i.as_mut().copy_from_slice(from_i.as_ref());
1081 ntt_op.forward(to_i.as_mut());
1082 });
1083 let p0 = pk_eval.get_row_slice(0);
1084 let p1 = pk_eval.get_row_slice(1);
1085
1086 let q = mod_op.modulus();
1087
1088 // RGSW(m) = RLWE'(-sm), RLWE(m)
1089 let (rlwe_dash_nsm, rlwe_dash_m) = out_rgsw.split_at_row_mut(d_a * 2);
1090
1091 // RLWE(-sm)
1092 let (rlwe_dash_nsm_parta, rlwe_dash_nsm_partb) = rlwe_dash_nsm.split_at_mut(d_a);
1093 izip!(
1094 rlwe_dash_nsm_parta.iter_mut(),
1095 rlwe_dash_nsm_partb.iter_mut(),
1096 gadget_a.iter()
1097 )
1098 .for_each(|(ai, bi, beta_i)| {
1099 // sample ephemeral secret u_i
1100 let mut u = vec![0i32; ring_size];
1101 fill_random_ternary_secret_with_hamming_weight(u.as_mut(), ring_size >> 1, rng);
1102 let mut u_eval = Mmut::R::try_convert_from(u.as_ref(), &q);
1103 ntt_op.forward(u_eval.as_mut());
1104
1105 let mut u_eval_copy = Mmut::R::zeros(ring_size);
1106 u_eval_copy.as_mut().copy_from_slice(u_eval.as_ref());
1107
1108 // p0 * u
1109 mod_op.elwise_mul_mut(u_eval.as_mut(), p0.as_ref());
1110 // p1 * u
1111 mod_op.elwise_mul_mut(u_eval_copy.as_mut(), p1.as_ref());
1112 ntt_op.backward(u_eval.as_mut());
1113 ntt_op.backward(u_eval_copy.as_mut());
1114
1115 // sample error
1116 RandomFillGaussianInModulus::random_fill(rng, &q, ai.as_mut());
1117 RandomFillGaussianInModulus::random_fill(rng, &q, bi.as_mut());
1118
1119 // a = p0*u+e0
1120 mod_op.elwise_add_mut(ai.as_mut(), u_eval.as_ref());
1121 // b = p1*u+e1
1122 mod_op.elwise_add_mut(bi.as_mut(), u_eval_copy.as_ref());
1123
1124 // a = p0*u + e0 + \beta*m
1125 // use u_eval as scratch
1126 mod_op.elwise_scalar_mul(u_eval.as_mut(), m.as_ref(), beta_i);
1127 mod_op.elwise_add_mut(ai.as_mut(), u_eval.as_ref());
1128 });
1129
1130 // RLWE(m)
1131 let (rlwe_dash_m_parta, rlwe_dash_m_partb) = rlwe_dash_m.split_at_mut(d_b);
1132 izip!(
1133 rlwe_dash_m_parta.iter_mut(),
1134 rlwe_dash_m_partb.iter_mut(),
1135 gadget_b.iter()
1136 )
1137 .for_each(|(ai, bi, beta_i)| {
1138 // sample ephemeral secret u_i
1139 let mut u = vec![0i32; ring_size];
1140 fill_random_ternary_secret_with_hamming_weight(u.as_mut(), ring_size >> 1, rng);
1141 let mut u_eval = Mmut::R::try_convert_from(u.as_ref(), &q);
1142 ntt_op.forward(u_eval.as_mut());
1143
1144 let mut u_eval_copy = Mmut::R::zeros(ring_size);
1145 u_eval_copy.as_mut().copy_from_slice(u_eval.as_ref());
1146
1147 // p0 * u
1148 mod_op.elwise_mul_mut(u_eval.as_mut(), p0.as_ref());
1149 // p1 * u
1150 mod_op.elwise_mul_mut(u_eval_copy.as_mut(), p1.as_ref());
1151 ntt_op.backward(u_eval.as_mut());
1152 ntt_op.backward(u_eval_copy.as_mut());
1153
1154 // sample error
1155 RandomFillGaussianInModulus::random_fill(rng, &q, ai.as_mut());
1156 RandomFillGaussianInModulus::random_fill(rng, &q, bi.as_mut());
1157
1158 // a = p0*u+e0
1159 mod_op.elwise_add_mut(ai.as_mut(), u_eval.as_ref());
1160 // b = p1*u+e1
1161 mod_op.elwise_add_mut(bi.as_mut(), u_eval_copy.as_ref());
1162
1163 // b = p1*u + e0 + \beta*m
1164 // use u_eval as scratch
1165 mod_op.elwise_scalar_mul(u_eval.as_mut(), m.as_ref(), beta_i);
1166 mod_op.elwise_add_mut(bi.as_mut(), u_eval.as_ref());
1167 });
1168}
1169
1170/// Generates RLWE Key switching key to key switch ciphertext RLWE_{from_s}(m)
1171/// to RLWE_{to_s}(m).
1172///
1173/// Key switching equals
1174/// \sum decompose(c_1)_i * RLWE_{to_s}(\beta^i -from_s)
1175/// Hence, key switchin key equals RLWE'(-from_s) = RLWE(-from_s), RLWE(beta^1
1176/// -from_s), ..., RLWE(beta^{d-1} -from_s).
1177///
1178/// - ksk_out: Output Key switching key. Key switching key stores only part B
1179/// polynomials of ksk RLWE ciphertexts (i.e. RLWE'_B(-from_s)) in coefficient
1180/// domain
1181/// - neg_from_s: Negative of secret polynomial to key switch from
1182/// - to_s: secret polynomial to key switch to.
1183pub(crate) fn rlwe_ksk_gen<
1184 Mmut: MatrixMut + MatrixEntity,
1185 ModOp: ArithmeticOps<Element = Mmut::MatElement>
1186 + VectorOps<Element = Mmut::MatElement>
1187 + GetModulus<Element = Mmut::MatElement>,
1188 NttOp: Ntt<Element = Mmut::MatElement>,
1189 R: RandomFillGaussianInModulus<[Mmut::MatElement], ModOp::M>,
1190 PR: RandomFillUniformInModulus<[Mmut::MatElement], ModOp::M>,
1191>(
1192 ksk_out: &mut Mmut,
1193 neg_from_s: Mmut::R,
1194 mut to_s: Mmut::R,
1195 gadget_vector: &[Mmut::MatElement],
1196 mod_op: &ModOp,
1197 ntt_op: &NttOp,
1198 p_rng: &mut PR,
1199 rng: &mut R,
1200) where
1201 <Mmut as Matrix>::R: RowMut,
1202{
1203 let ring_size = neg_from_s.as_ref().len();
1204 let d = gadget_vector.len();
1205 assert!(ksk_out.dimension() == (d, ring_size));
1206
1207 let q = mod_op.modulus();
1208
1209 ntt_op.forward(to_s.as_mut());
1210
1211 // RLWE'_{to_s}(-from_s)
1212 let mut part_a = {
1213 let mut a = Mmut::zeros(d, ring_size);
1214 a.iter_rows_mut()
1215 .for_each(|ai| RandomFillUniformInModulus::random_fill(p_rng, q, ai.as_mut()));
1216 a
1217 };
1218 izip!(
1219 part_a.iter_rows_mut(),
1220 ksk_out.iter_rows_mut(),
1221 gadget_vector.iter(),
1222 )
1223 .for_each(|(ai, bi, beta_i)| {
1224 // si * ai
1225 ntt_op.forward(ai.as_mut());
1226 mod_op.elwise_mul_mut(ai.as_mut(), to_s.as_ref());
1227 ntt_op.backward(ai.as_mut());
1228
1229 // ei + to_s*ai
1230 RandomFillGaussianInModulus::random_fill(rng, &q, bi.as_mut());
1231 mod_op.elwise_add_mut(bi.as_mut(), ai.as_ref());
1232
1233 // beta_i * -from_s
1234 // use ai as scratch space
1235 mod_op.elwise_scalar_mul(ai.as_mut(), neg_from_s.as_ref(), beta_i);
1236
1237 // bi = ei + to_s*ai + beta_i*-from_s
1238 mod_op.elwise_add_mut(bi.as_mut(), ai.as_ref());
1239 });
1240}
1241
1242pub(crate) fn galois_key_gen<
1243 Mmut: MatrixMut + MatrixEntity,
1244 ModOp: ArithmeticOps<Element = Mmut::MatElement>
1245 + VectorOps<Element = Mmut::MatElement>
1246 + GetModulus<Element = Mmut::MatElement>,
1247 NttOp: Ntt<Element = Mmut::MatElement>,
1248 S,
1249 R: RandomFillGaussianInModulus<[Mmut::MatElement], ModOp::M>,
1250 PR: RandomFillUniformInModulus<[Mmut::MatElement], ModOp::M>,
1251>(
1252 ksk_out: &mut Mmut,
1253 s: &[S],
1254 auto_k: isize,
1255 gadget_vector: &[Mmut::MatElement],
1256 mod_op: &ModOp,
1257 ntt_op: &NttOp,
1258 p_rng: &mut PR,
1259 rng: &mut R,
1260) where
1261 <Mmut as Matrix>::R: RowMut,
1262 Mmut::R: TryConvertFrom1<[S], ModOp::M> + RowEntity,
1263 Mmut::MatElement: Copy + Sub<Output = Mmut::MatElement>,
1264{
1265 let ring_size = s.len();
1266 let (auto_map_index, auto_map_sign) = generate_auto_map(ring_size, auto_k);
1267
1268 let q = mod_op.modulus();
1269
1270 // s(X) -> -s(X^k)
1271 let s = Mmut::R::try_convert_from(s, q);
1272 let mut neg_s_auto = Mmut::R::zeros(s.as_ref().len());
1273 izip!(s.as_ref(), auto_map_index.iter(), auto_map_sign.iter()).for_each(
1274 |(el, to_index, sign)| {
1275 // if sign is +ve (true), then negate because we need -s(X) (i.e. do the
1276 // opposite than the usual case)
1277 if *sign {
1278 neg_s_auto.as_mut()[*to_index] = mod_op.neg(el);
1279 } else {
1280 neg_s_auto.as_mut()[*to_index] = *el;
1281 }
1282 },
1283 );
1284
1285 // Ksk from -s(X^k) to s(X)
1286 rlwe_ksk_gen(
1287 ksk_out,
1288 neg_s_auto,
1289 s,
1290 gadget_vector,
1291 mod_op,
1292 ntt_op,
1293 p_rng,
1294 rng,
1295 );
1296}
1297
1298/// Encrypt polynomial m(X) as RLWE ciphertext.
1299///
1300/// - rlwe_out: returned RLWE ciphertext RLWE(m) in coefficient domain. RLWE
1301/// ciphertext is a matirx with first row consiting polynomial `a` and the
1302/// second rows consting polynomial `b`
1303pub(crate) fn secret_key_encrypt_rlwe<
1304 Ro: Row + RowMut + RowEntity,
1305 ModOp: VectorOps<Element = Ro::Element> + GetModulus<Element = Ro::Element>,
1306 NttOp: Ntt<Element = Ro::Element>,
1307 S,
1308 R: RandomFillGaussianInModulus<[Ro::Element], ModOp::M>,
1309 PR: RandomFillUniformInModulus<[Ro::Element], ModOp::M>,
1310>(
1311 m: &[Ro::Element],
1312 b_rlwe_out: &mut Ro,
1313 s: &[S],
1314 mod_op: &ModOp,
1315 ntt_op: &NttOp,
1316 p_rng: &mut PR,
1317 rng: &mut R,
1318) where
1319 Ro: TryConvertFrom1<[S], ModOp::M> + Debug,
1320{
1321 let ring_size = s.len();
1322 assert!(m.as_ref().len() == ring_size);
1323 assert!(b_rlwe_out.as_ref().len() == ring_size);
1324
1325 let q = mod_op.modulus();
1326
1327 // sample a
1328 let mut a = {
1329 let mut a = Ro::zeros(ring_size);
1330 RandomFillUniformInModulus::random_fill(p_rng, q, a.as_mut());
1331 a
1332 };
1333
1334 // s * a
1335 let mut sa = Ro::try_convert_from(s, q);
1336 ntt_op.forward(sa.as_mut());
1337 ntt_op.forward(a.as_mut());
1338 mod_op.elwise_mul_mut(sa.as_mut(), a.as_ref());
1339 ntt_op.backward(sa.as_mut());
1340
1341 // sample e
1342 RandomFillGaussianInModulus::random_fill(rng, q, b_rlwe_out.as_mut());
1343 mod_op.elwise_add_mut(b_rlwe_out.as_mut(), m.as_ref());
1344 mod_op.elwise_add_mut(b_rlwe_out.as_mut(), sa.as_ref());
1345}
1346
1347pub(crate) fn public_key_encrypt_rlwe<
1348 M: Matrix,
1349 Mmut: MatrixMut<MatElement = M::MatElement>,
1350 ModOp: VectorOps<Element = M::MatElement> + GetModulus<Element = M::MatElement>,
1351 NttOp: Ntt<Element = M::MatElement>,
1352 S,
1353 R: RandomFillGaussianInModulus<[M::MatElement], ModOp::M>
1354 + RandomFillUniformInModulus<[M::MatElement], ModOp::M>
1355 + RandomFill<[u8]>
1356 + RandomElementInModulus<usize, usize>,
1357>(
1358 rlwe_out: &mut Mmut,
1359 pk: &M,
1360 m: &[M::MatElement],
1361 mod_op: &ModOp,
1362 ntt_op: &NttOp,
1363 rng: &mut R,
1364) where
1365 <Mmut as Matrix>::R: RowMut + TryConvertFrom1<[S], ModOp::M> + RowEntity,
1366 M::MatElement: Copy,
1367 S: Zero + Signed + Copy,
1368{
1369 let ring_size = m.len();
1370 assert!(rlwe_out.dimension() == (2, ring_size));
1371
1372 let q = mod_op.modulus();
1373
1374 let mut u = vec![S::zero(); ring_size];
1375 fill_random_ternary_secret_with_hamming_weight(u.as_mut(), ring_size >> 1, rng);
1376 let mut u = Mmut::R::try_convert_from(&u, q);
1377 ntt_op.forward(u.as_mut());
1378
1379 let mut ua = Mmut::R::zeros(ring_size);
1380 ua.as_mut().copy_from_slice(pk.get_row_slice(0));
1381 let mut ub = Mmut::R::zeros(ring_size);
1382 ub.as_mut().copy_from_slice(pk.get_row_slice(1));
1383
1384 // a*u
1385 ntt_op.forward(ua.as_mut());
1386 mod_op.elwise_mul_mut(ua.as_mut(), u.as_ref());
1387 ntt_op.backward(ua.as_mut());
1388
1389 // b*u
1390 ntt_op.forward(ub.as_mut());
1391 mod_op.elwise_mul_mut(ub.as_mut(), u.as_ref());
1392 ntt_op.backward(ub.as_mut());
1393
1394 // sample error
1395 rlwe_out.iter_rows_mut().for_each(|ri| {
1396 RandomFillGaussianInModulus::random_fill(rng, &q, ri.as_mut());
1397 });
1398
1399 // a*u + e0
1400 mod_op.elwise_add_mut(rlwe_out.get_row_mut(0), ua.as_ref());
1401 // b*u + e1
1402 mod_op.elwise_add_mut(rlwe_out.get_row_mut(1), ub.as_ref());
1403
1404 // b*u + e1 + m
1405 mod_op.elwise_add_mut(rlwe_out.get_row_mut(1), m);
1406}
1407
1408/// Generates RLWE public key
1409pub(crate) fn gen_rlwe_public_key<
1410 Ro: RowMut + RowEntity,
1411 S,
1412 ModOp: VectorOps<Element = Ro::Element> + GetModulus<Element = Ro::Element>,
1413 NttOp: Ntt<Element = Ro::Element>,
1414 PRng: RandomFillUniformInModulus<[Ro::Element], ModOp::M>,
1415 Rng: RandomFillGaussianInModulus<[Ro::Element], ModOp::M>,
1416>(
1417 part_b_out: &mut Ro,
1418 s: &[S],
1419 ntt_op: &NttOp,
1420 mod_op: &ModOp,
1421 p_rng: &mut PRng,
1422 rng: &mut Rng,
1423) where
1424 Ro: TryConvertFrom1<[S], ModOp::M>,
1425{
1426 let ring_size = s.len();
1427 assert!(part_b_out.as_ref().len() == ring_size);
1428
1429 let q = mod_op.modulus();
1430
1431 // sample a
1432 let mut a = {
1433 let mut tmp = Ro::zeros(ring_size);
1434 RandomFillUniformInModulus::random_fill(p_rng, &q, tmp.as_mut());
1435 tmp
1436 };
1437 ntt_op.forward(a.as_mut());
1438
1439 // s*a
1440 let mut sa = Ro::try_convert_from(s, &q);
1441 ntt_op.forward(sa.as_mut());
1442 mod_op.elwise_mul_mut(sa.as_mut(), a.as_ref());
1443 ntt_op.backward(sa.as_mut());
1444
1445 // s*a + e
1446 RandomFillGaussianInModulus::random_fill(rng, &q, part_b_out.as_mut());
1447 mod_op.elwise_add_mut(part_b_out.as_mut(), sa.as_ref());
1448}
1449
1450/// Decrypts degree 1 RLWE ciphertext RLWE(m) and returns m
1451///
1452/// - rlwe_ct: input degree 1 ciphertext RLWE(m).
1453pub(crate) fn decrypt_rlwe<
1454 R: RowMut,
1455 M: Matrix<MatElement = R::Element>,
1456 ModOp: VectorOps<Element = R::Element> + GetModulus<Element = R::Element>,
1457 NttOp: Ntt<Element = R::Element>,
1458 S,
1459>(
1460 rlwe_ct: &M,
1461 s: &[S],
1462 m_out: &mut R,
1463 ntt_op: &NttOp,
1464 mod_op: &ModOp,
1465) where
1466 R: TryConvertFrom1<[S], ModOp::M>,
1467 R::Element: Copy,
1468{
1469 let ring_size = s.len();
1470 assert!(rlwe_ct.dimension() == (2, ring_size));
1471 assert!(m_out.as_ref().len() == ring_size);
1472
1473 // transform a to evluation form
1474 m_out.as_mut().copy_from_slice(rlwe_ct.get_row_slice(0));
1475 ntt_op.forward(m_out.as_mut());
1476
1477 // -s*a
1478 let mut s = R::try_convert_from(&s, mod_op.modulus());
1479 ntt_op.forward(s.as_mut());
1480 mod_op.elwise_mul_mut(m_out.as_mut(), s.as_ref());
1481 mod_op.elwise_neg_mut(m_out.as_mut());
1482 ntt_op.backward(m_out.as_mut());
1483
1484 // m+e = b - s*a
1485 mod_op.elwise_add_mut(m_out.as_mut(), rlwe_ct.get_row_slice(1));
1486}
1487
1488// Measures noise in degree 1 RLWE ciphertext against encoded ideal message
1489// encoded_m
1490pub(crate) fn measure_noise<
1491 Mmut: MatrixMut + Matrix,
1492 ModOp: VectorOps<Element = Mmut::MatElement> + GetModulus<Element = Mmut::MatElement>,
1493 NttOp: Ntt<Element = Mmut::MatElement>,
1494 S,
1495>(
1496 rlwe_ct: &Mmut,
1497 encoded_m_ideal: &Mmut::R,
1498 ntt_op: &NttOp,
1499 mod_op: &ModOp,
1500 s: &[S],
1501) -> f64
1502where
1503 <Mmut as Matrix>::R: RowMut,
1504 Mmut::R: RowEntity + TryConvertFrom1<[S], ModOp::M>,
1505 Mmut::MatElement: PrimInt + ToPrimitive + Debug,
1506{
1507 let ring_size = s.len();
1508 assert!(rlwe_ct.dimension() == (2, ring_size));
1509 assert!(encoded_m_ideal.as_ref().len() == ring_size);
1510
1511 // -(s * a)
1512 let q = mod_op.modulus();
1513 let mut s = Mmut::R::try_convert_from(s, &q);
1514 ntt_op.forward(s.as_mut());
1515 let mut a = Mmut::R::zeros(ring_size);
1516 a.as_mut().copy_from_slice(rlwe_ct.get_row_slice(0));
1517 ntt_op.forward(a.as_mut());
1518 mod_op.elwise_mul_mut(s.as_mut(), a.as_ref());
1519 mod_op.elwise_neg_mut(s.as_mut());
1520 ntt_op.backward(s.as_mut());
1521
1522 // m+e = b - s*a
1523 let mut m_plus_e = s;
1524 mod_op.elwise_add_mut(m_plus_e.as_mut(), rlwe_ct.get_row_slice(1));
1525
1526 // difference
1527 mod_op.elwise_sub_mut(m_plus_e.as_mut(), encoded_m_ideal.as_ref());
1528
1529 let mut max_diff_bits = f64::MIN;
1530 m_plus_e.as_ref().iter().for_each(|v| {
1531 let bits = (q.map_element_to_i64(v).to_f64().unwrap()).log2();
1532
1533 if max_diff_bits < bits {
1534 max_diff_bits = bits;
1535 }
1536 });
1537
1538 return max_diff_bits;
1539}
1540
1541#[cfg(test)]
1542pub(crate) mod tests {
1543 use std::{marker::PhantomData, ops::Mul, vec};
1544
1545 use itertools::{izip, Itertools};
1546 use rand::{thread_rng, Rng};
1547
1548 use crate::{
1549 backend::{GetModulus, ModInit, ModularOpsU64, Modulus, VectorOps},
1550 decomposer::{Decomposer, DefaultDecomposer, RlweDecomposer},
1551 ntt::{self, Ntt, NttBackendU64, NttInit},
1552 random::{DefaultSecureRng, NewWithSeed, RandomFillUniformInModulus},
1553 rgsw::{
1554 gen_rlwe_public_key, measure_noise, public_key_encrypt_rgsw, AutoKeyEvaluationDomain,
1555 RgswCiphertext, RgswCiphertextEvaluationDomain, RlweCiphertext, RlwePublicKey,
1556 SeededAutoKey, SeededRgswCiphertext, SeededRlweCiphertext, SeededRlwePublicKey,
1557 },
1558 utils::{generate_prime, negacyclic_mul, Stats, TryConvertFrom1},
1559 Matrix, Secret,
1560 };
1561
1562 use super::{
1563 decrypt_rlwe, galois_auto, galois_key_gen, generate_auto_map, public_key_encrypt_rlwe,
1564 rgsw_by_rgsw_inplace, rlwe_by_rgsw, secret_key_encrypt_rgsw, secret_key_encrypt_rlwe,
1565 RlweSecret,
1566 };
1567
1568 pub(crate) fn _sk_encrypt_rlwe<T: Modulus<Element = u64> + Clone>(
1569 m: &[u64],
1570 s: &[i32],
1571 ntt_op: &NttBackendU64,
1572 mod_op: &ModularOpsU64<T>,
1573 ) -> RlweCiphertext<Vec<Vec<u64>>, DefaultSecureRng> {
1574 let ring_size = m.len();
1575 let q = mod_op.modulus();
1576 assert!(s.len() == ring_size);
1577
1578 let mut rng = DefaultSecureRng::new();
1579 let mut rlwe_seed = [0u8; 32];
1580 rng.fill_bytes(&mut rlwe_seed);
1581 let mut seeded_rlwe_ct =
1582 SeededRlweCiphertext::<_, [u8; 32], _>::empty(ring_size as usize, rlwe_seed, q.clone());
1583 let mut p_rng = DefaultSecureRng::new_seeded(rlwe_seed);
1584 secret_key_encrypt_rlwe(
1585 &m,
1586 &mut seeded_rlwe_ct.data,
1587 s,
1588 mod_op,
1589 ntt_op,
1590 &mut p_rng,
1591 &mut rng,
1592 );
1593
1594 RlweCiphertext::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_rlwe_ct)
1595 }
1596
1597 // Encrypt m as RGSW ciphertext RGSW(m) using supplied public key
1598 pub(crate) fn _pk_encrypt_rgsw<T: Modulus<Element = u64> + Clone>(
1599 m: &[u64],
1600 public_key: &RlwePublicKey<Vec<Vec<u64>>, DefaultSecureRng>,
1601 decomposer: &(DefaultDecomposer<u64>, DefaultDecomposer<u64>),
1602 mod_op: &ModularOpsU64<T>,
1603 ntt_op: &NttBackendU64,
1604 ) -> RgswCiphertext<Vec<Vec<u64>>, T> {
1605 let (_, ring_size) = Matrix::dimension(&public_key.data);
1606 let gadget_vector_a = decomposer.a().gadget_vector();
1607 let gadget_vector_b = decomposer.b().gadget_vector();
1608
1609 let mut rng = DefaultSecureRng::new();
1610
1611 assert!(m.len() == ring_size);
1612
1613 // public key encrypt RGSW(m1)
1614 let mut rgsw_ct = RgswCiphertext::empty(ring_size, decomposer, mod_op.modulus().clone());
1615 public_key_encrypt_rgsw(
1616 &mut rgsw_ct.data,
1617 m,
1618 &public_key.data,
1619 &gadget_vector_a,
1620 &gadget_vector_b,
1621 mod_op,
1622 ntt_op,
1623 &mut rng,
1624 );
1625
1626 rgsw_ct
1627 }
1628
1629 /// Encrypts m as RGSW ciphertext RGSW(m) using supplied secret key. Returns
1630 /// unseeded RGSW ciphertext in coefficient domain
1631 pub(crate) fn _sk_encrypt_rgsw<T: Modulus<Element = u64> + Clone>(
1632 m: &[u64],
1633 s: &[i32],
1634 decomposer: &(DefaultDecomposer<u64>, DefaultDecomposer<u64>),
1635 mod_op: &ModularOpsU64<T>,
1636 ntt_op: &NttBackendU64,
1637 ) -> SeededRgswCiphertext<Vec<Vec<u64>>, [u8; 32], T> {
1638 let ring_size = s.len();
1639 assert!(m.len() == s.len());
1640
1641 let q = mod_op.modulus();
1642
1643 let gadget_vector_a = decomposer.a().gadget_vector();
1644 let gadget_vector_b = decomposer.b().gadget_vector();
1645
1646 let mut rng = DefaultSecureRng::new();
1647 let mut rgsw_seed = [0u8; 32];
1648 rng.fill_bytes(&mut rgsw_seed);
1649 let mut seeded_rgsw_ct = SeededRgswCiphertext::<Vec<Vec<u64>>, [u8; 32], T>::empty(
1650 ring_size as usize,
1651 decomposer,
1652 rgsw_seed,
1653 q.clone(),
1654 );
1655 let mut p_rng = DefaultSecureRng::new_seeded(rgsw_seed);
1656 secret_key_encrypt_rgsw(
1657 &mut seeded_rgsw_ct.data,
1658 m,
1659 &gadget_vector_a,
1660 &gadget_vector_b,
1661 s,
1662 mod_op,
1663 ntt_op,
1664 &mut p_rng,
1665 &mut rng,
1666 );
1667 seeded_rgsw_ct
1668 }
1669
1670 /// Prints noise in RGSW ciphertext RGSW(m).
1671 ///
1672 /// - rgsw_ct: RGSW ciphertext in coefficient domain
1673 pub(crate) fn _measure_noise_rgsw<T: Modulus<Element = u64> + Clone>(
1674 rgsw_ct: &[Vec<u64>],
1675 m: &[u64],
1676 s: &[i32],
1677 decomposer: &(DefaultDecomposer<u64>, DefaultDecomposer<u64>),
1678 q: &T,
1679 ) {
1680 let gadget_vector_a = decomposer.a().gadget_vector();
1681 let gadget_vector_b = decomposer.b().gadget_vector();
1682 let d_a = gadget_vector_a.len();
1683 let d_b = gadget_vector_b.len();
1684 let ring_size = s.len();
1685 assert!(Matrix::dimension(&rgsw_ct) == (d_a * 2 + d_b * 2, ring_size));
1686 assert!(m.len() == ring_size);
1687
1688 let mod_op = ModularOpsU64::new(q.clone());
1689 let ntt_op = NttBackendU64::new(q, ring_size);
1690
1691 let mul_mod =
1692 |a: &u64, b: &u64| ((*a as u128 * *b as u128) % q.q().unwrap() as u128) as u64;
1693 let s_poly = Vec::<u64>::try_convert_from(s, q);
1694 let mut neg_s = s_poly.clone();
1695 mod_op.elwise_neg_mut(neg_s.as_mut());
1696 let neg_sm0m1 = negacyclic_mul(&neg_s, &m, mul_mod, q.q().unwrap());
1697
1698 // RLWE(\beta^j -s * m)
1699 for j in 0..d_a {
1700 let ideal_m = {
1701 // RLWE(\beta^j -s * m)
1702 let mut beta_neg_sm0m1 = vec![0u64; ring_size as usize];
1703 mod_op.elwise_scalar_mul(beta_neg_sm0m1.as_mut(), &neg_sm0m1, &gadget_vector_a[j]);
1704 beta_neg_sm0m1
1705 };
1706
1707 let mut rlwe = vec![vec![0u64; ring_size as usize]; 2];
1708 rlwe[0].copy_from_slice(rgsw_ct.get_row_slice(j));
1709 rlwe[1].copy_from_slice(rgsw_ct.get_row_slice(d_a + j));
1710 let noise = measure_noise(&rlwe, &ideal_m, &ntt_op, &mod_op, s);
1711
1712 println!(r"Noise RLWE(\beta^{j} -sm0m1): {noise}");
1713 }
1714
1715 // RLWE(\beta^j m)
1716 for j in 0..d_b {
1717 let ideal_m = {
1718 // RLWE(\beta^j m)
1719 let mut beta_m0m1 = vec![0u64; ring_size as usize];
1720 mod_op.elwise_scalar_mul(beta_m0m1.as_mut(), &m, &gadget_vector_b[j]);
1721 beta_m0m1
1722 };
1723
1724 let mut rlwe = vec![vec![0u64; ring_size as usize]; 2];
1725 rlwe[0].copy_from_slice(rgsw_ct.get_row_slice(d_a * 2 + j));
1726 rlwe[1].copy_from_slice(rgsw_ct.get_row_slice(d_a * 2 + d_b + j));
1727 let noise = measure_noise(&rlwe, &ideal_m, &ntt_op, &mod_op, s);
1728
1729 println!(r"Noise RLWE(\beta^{j} m0m1): {noise}");
1730 }
1731 }
1732
1733 #[test]
1734 fn rlwe_encrypt_decryption() {
1735 let logq = 50;
1736 let logp = 2;
1737 let ring_size = 1 << 4;
1738 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
1739 let p = 1u64 << logp;
1740
1741 let mut rng = DefaultSecureRng::new();
1742
1743 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
1744
1745 // sample m0
1746 let mut m0 = vec![0u64; ring_size as usize];
1747 RandomFillUniformInModulus::<[u64], u64>::random_fill(
1748 &mut rng,
1749 &(1u64 << logp),
1750 m0.as_mut_slice(),
1751 );
1752
1753 let ntt_op = NttBackendU64::new(&q, ring_size as usize);
1754 let mod_op = ModularOpsU64::new(q);
1755
1756 // encrypt m0
1757 let encoded_m = m0
1758 .iter()
1759 .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
1760 .collect_vec();
1761 let rlwe_in_ct = _sk_encrypt_rlwe(&encoded_m, s.values(), &ntt_op, &mod_op);
1762
1763 let mut encoded_m_back = vec![0u64; ring_size as usize];
1764 decrypt_rlwe(
1765 &rlwe_in_ct,
1766 s.values(),
1767 &mut encoded_m_back,
1768 &ntt_op,
1769 &mod_op,
1770 );
1771 let m_back = encoded_m_back
1772 .iter()
1773 .map(|v| (((*v as f64 * p as f64) / q as f64).round() as u64) % p)
1774 .collect_vec();
1775 assert_eq!(m0, m_back);
1776
1777 // let noise = measure_noise(&rlwe_in_ct, &encoded_m, &ntt_op, &mod_op,
1778 // s.values()); println!("Noise: {noise}");
1779 }
1780
1781 #[test]
1782 fn rlwe_by_rgsw_works() {
1783 let logq = 50;
1784 let logp = 2;
1785 let ring_size = 1 << 9;
1786 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
1787 let p: u64 = 1u64 << logp;
1788
1789 let mut rng = DefaultSecureRng::new_seeded([0u8; 32]);
1790
1791 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
1792
1793 let mut m0 = vec![0u64; ring_size as usize];
1794 RandomFillUniformInModulus::<[u64], _>::random_fill(
1795 &mut rng,
1796 &(1u64 << logp),
1797 m0.as_mut_slice(),
1798 );
1799 let mut m1 = vec![0u64; ring_size as usize];
1800 m1[thread_rng().gen_range(0..ring_size) as usize] = 1;
1801
1802 let ntt_op = NttBackendU64::new(&q, ring_size as usize);
1803 let mod_op = ModularOpsU64::new(q);
1804 let d_rgsw = 10;
1805 let logb = 5;
1806 let decomposer = (
1807 DefaultDecomposer::new(q, logb, d_rgsw),
1808 DefaultDecomposer::new(q, logb, d_rgsw),
1809 );
1810
1811 // create public key
1812 let mut pk_seed = [0u8; 32];
1813 rng.fill_bytes(&mut pk_seed);
1814 let mut pk_prng = DefaultSecureRng::new_seeded(pk_seed);
1815 let mut seeded_pk =
1816 SeededRlwePublicKey::<Vec<u64>, _>::empty(ring_size as usize, pk_seed, q);
1817 gen_rlwe_public_key(
1818 &mut seeded_pk.data,
1819 s.values(),
1820 &ntt_op,
1821 &mod_op,
1822 &mut pk_prng,
1823 &mut rng,
1824 );
1825 let pk = RlwePublicKey::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_pk);
1826
1827 // Encrypt m1 as RGSW(m1)
1828 let rgsw_ct = {
1829 //TODO(Jay): Figure out better way to test secret key and public key variant of
1830 // RGSW ciphertext encryption within the same test
1831
1832 if true {
1833 // Encryption m1 as RGSW(m1) using secret key
1834 let seeded_rgsw_ct =
1835 _sk_encrypt_rgsw(&m1, s.values(), &decomposer, &mod_op, &ntt_op);
1836 RgswCiphertextEvaluationDomain::<Vec<Vec<u64>>, DefaultSecureRng, NttBackendU64>::from(&seeded_rgsw_ct)
1837 } else {
1838 // Encrypt m1 as RGSW(m1) using public key
1839 let rgsw_ct = _pk_encrypt_rgsw(&m1, &pk, &decomposer, &mod_op, &ntt_op);
1840 RgswCiphertextEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(&rgsw_ct)
1841 }
1842 };
1843
1844 // Encrypt m0 as RLWE(m0)
1845 let mut rlwe_in_ct = {
1846 let encoded_m = m0
1847 .iter()
1848 .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
1849 .collect_vec();
1850
1851 _sk_encrypt_rlwe(&encoded_m, s.values(), &ntt_op, &mod_op)
1852 };
1853
1854 // RLWE(m0m1) = RLWE(m0) x RGSW(m1)
1855 let mut scratch_space = vec![
1856 vec![0u64; ring_size as usize];
1857 std::cmp::max(
1858 decomposer.a().decomposition_count(),
1859 decomposer.b().decomposition_count()
1860 ) + 2
1861 ];
1862 rlwe_by_rgsw(
1863 &mut rlwe_in_ct,
1864 &rgsw_ct.data,
1865 &mut scratch_space,
1866 &decomposer,
1867 &ntt_op,
1868 &mod_op,
1869 );
1870
1871 // Decrypt RLWE(m0m1)
1872 let mut encoded_m0m1_back = vec![0u64; ring_size as usize];
1873 decrypt_rlwe(
1874 &rlwe_in_ct,
1875 s.values(),
1876 &mut encoded_m0m1_back,
1877 &ntt_op,
1878 &mod_op,
1879 );
1880 let m0m1_back = encoded_m0m1_back
1881 .iter()
1882 .map(|v| (((*v as f64 * p as f64) / (q as f64)).round() as u64) % p)
1883 .collect_vec();
1884
1885 let mul_mod = |v0: &u64, v1: &u64| (v0 * v1) % p;
1886 let m0m1 = negacyclic_mul(&m0, &m1, mul_mod, p);
1887
1888 // {
1889 // // measure noise
1890 // let encoded_m_ideal = m0m1
1891 // .iter()
1892 // .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
1893 // .collect_vec();
1894
1895 // let noise = measure_noise(&rlwe_in_ct, &encoded_m_ideal, &ntt_op,
1896 // &mod_op, s.values()); println!("Noise RLWE(m0m1)(=
1897 // RLWE(m0)xRGSW(m1)) : {noise}"); }
1898
1899 assert!(
1900 m0m1 == m0m1_back,
1901 "Expected {:?} \n Got {:?}",
1902 m0m1,
1903 m0m1_back
1904 );
1905 }
1906
1907 #[test]
1908 fn galois_auto_works() {
1909 let logq = 55;
1910 let ring_size = 1 << 11;
1911 let q = generate_prime(logq, 2 * ring_size, 1u64 << logq).unwrap();
1912 let logp = 3;
1913 let p = 1u64 << logp;
1914 let d_rgsw = 5;
1915 let logb = 11;
1916
1917 let mut rng = DefaultSecureRng::new();
1918 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
1919
1920 let mut m = vec![0u64; ring_size as usize];
1921 RandomFillUniformInModulus::random_fill(&mut rng, &p, m.as_mut_slice());
1922 let encoded_m = m
1923 .iter()
1924 .map(|v| (((*v as f64 * q as f64) / (p as f64)).round() as u64))
1925 .collect_vec();
1926
1927 let ntt_op = NttBackendU64::new(&q, ring_size as usize);
1928 let mod_op = ModularOpsU64::new(q);
1929
1930 // RLWE_{s}(m)
1931 let mut seed_rlwe = [0u8; 32];
1932 rng.fill_bytes(&mut seed_rlwe);
1933 let mut seeded_rlwe_m = SeededRlweCiphertext::empty(ring_size as usize, seed_rlwe, q);
1934 let mut p_rng = DefaultSecureRng::new_seeded(seed_rlwe);
1935 secret_key_encrypt_rlwe(
1936 &encoded_m,
1937 &mut seeded_rlwe_m.data,
1938 s.values(),
1939 &mod_op,
1940 &ntt_op,
1941 &mut p_rng,
1942 &mut rng,
1943 );
1944 let mut rlwe_m = RlweCiphertext::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_rlwe_m);
1945
1946 let auto_k = -125;
1947
1948 // Generate galois key to key switch from s^k to s
1949 let decomposer = DefaultDecomposer::new(q, logb, d_rgsw);
1950 let mut seed_auto = [0u8; 32];
1951 rng.fill_bytes(&mut seed_auto);
1952 let mut seeded_auto_key =
1953 SeededAutoKey::empty(ring_size as usize, &decomposer, seed_auto, q);
1954 let mut p_rng = DefaultSecureRng::new_seeded(seed_auto);
1955 let gadget_vector = decomposer.gadget_vector();
1956 galois_key_gen(
1957 &mut seeded_auto_key.data,
1958 s.values(),
1959 auto_k,
1960 &gadget_vector,
1961 &mod_op,
1962 &ntt_op,
1963 &mut p_rng,
1964 &mut rng,
1965 );
1966 let auto_key =
1967 AutoKeyEvaluationDomain::<Vec<Vec<u64>>, DefaultSecureRng, NttBackendU64>::from(
1968 &seeded_auto_key,
1969 );
1970
1971 // Send RLWE_{s}(m) -> RLWE_{s}(m^k)
1972 let mut scratch_space = vec![vec![0u64; ring_size as usize]; d_rgsw + 2];
1973 let (auto_map_index, auto_map_sign) = generate_auto_map(ring_size as usize, auto_k);
1974 galois_auto(
1975 &mut rlwe_m,
1976 &auto_key.data,
1977 &mut scratch_space,
1978 &auto_map_index,
1979 &auto_map_sign,
1980 &mod_op,
1981 &ntt_op,
1982 &decomposer,
1983 );
1984
1985 let rlwe_m_k = rlwe_m;
1986
1987 // Decrypt RLWE_{s}(m^k) and check
1988 let mut encoded_m_k_back = vec![0u64; ring_size as usize];
1989 decrypt_rlwe(
1990 &rlwe_m_k,
1991 s.values(),
1992 &mut encoded_m_k_back,
1993 &ntt_op,
1994 &mod_op,
1995 );
1996 let m_k_back = encoded_m_k_back
1997 .iter()
1998 .map(|v| (((*v as f64 * p as f64) / q as f64).round() as u64) % p)
1999 .collect_vec();
2000
2001 let mut m_k = vec![0u64; ring_size as usize];
2002 // Send \delta m -> \delta m^k
2003 izip!(m.iter(), auto_map_index.iter(), auto_map_sign.iter()).for_each(
2004 |(v, to_index, sign)| {
2005 if !*sign {
2006 m_k[*to_index] = (p - *v) % p;
2007 } else {
2008 m_k[*to_index] = *v;
2009 }
2010 },
2011 );
2012
2013 {
2014 let encoded_m_k = m_k
2015 .iter()
2016 .map(|v| ((*v as f64 * q as f64) / p as f64).round() as u64)
2017 .collect_vec();
2018
2019 let noise = measure_noise(&rlwe_m_k, &encoded_m_k, &ntt_op, &mod_op, s.values());
2020 println!("Ksk noise: {noise}");
2021 }
2022
2023 assert_eq!(m_k_back, m_k);
2024 }
2025
2026 #[test]
2027 fn sk_rgsw_by_rgsw() {
2028 let logq = 60;
2029 let logp = 2;
2030 let ring_size = 1 << 11;
2031 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
2032 let p = 1u64 << logp;
2033 let d_rgsw = 5;
2034 let logb = 12;
2035
2036 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
2037
2038 let mut rng = DefaultSecureRng::new();
2039 let ntt_op = NttBackendU64::new(&q, ring_size as usize);
2040 let mod_op = ModularOpsU64::new(q);
2041 let decomposer = (
2042 DefaultDecomposer::new(q, logb, d_rgsw),
2043 DefaultDecomposer::new(q, logb, d_rgsw),
2044 );
2045
2046 let mul_mod = |a: &u64, b: &u64| ((*a as u128 * *b as u128) % q as u128) as u64;
2047
2048 let mut carry_m = vec![0u64; ring_size as usize];
2049 carry_m[thread_rng().gen_range(0..ring_size) as usize] = 1;
2050
2051 // RGSW(carry_m)
2052 let mut rgsw_carrym = {
2053 let seeded_rgsw = _sk_encrypt_rgsw(&carry_m, s.values(), &decomposer, &mod_op, &ntt_op);
2054 let mut rgsw_eval =
2055 RgswCiphertextEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(
2056 &seeded_rgsw,
2057 );
2058 rgsw_eval
2059 .data
2060 .iter_mut()
2061 .for_each(|ri| ntt_op.backward(ri.as_mut()));
2062 rgsw_eval.data
2063 };
2064
2065 let mut scratch_matrix = vec![
2066 vec![0u64; ring_size as usize];
2067 decomposer.a().decomposition_count() * 2
2068 + decomposer.b().decomposition_count() * 2
2069 + std::cmp::max(
2070 decomposer.a().decomposition_count(),
2071 decomposer.b().decomposition_count()
2072 )
2073 ];
2074
2075 _measure_noise_rgsw(&rgsw_carrym, &carry_m, s.values(), &decomposer, &q);
2076
2077 for i in 0..2 {
2078 let mut m = vec![0u64; ring_size as usize];
2079 m[thread_rng().gen_range(0..ring_size) as usize] = if (i & 1) == 1 { q - 1 } else { 1 };
2080 let rgsw_m = RgswCiphertextEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(
2081 &_sk_encrypt_rgsw(&m, s.values(), &decomposer, &mod_op, &ntt_op),
2082 );
2083 rgsw_by_rgsw_inplace(
2084 &mut rgsw_carrym,
2085 &rgsw_m.data,
2086 &decomposer,
2087 &mut scratch_matrix,
2088 &ntt_op,
2089 &mod_op,
2090 );
2091
2092 // measure noise
2093 carry_m = negacyclic_mul(&carry_m, &m, mul_mod, q);
2094 println!("########### Noise RGSW(carrym) in {i}^th loop ###########");
2095 _measure_noise_rgsw(&rgsw_carrym, &carry_m, s.values(), &decomposer, &q);
2096 }
2097 {
2098 // RLWE(m) x RGSW(carry_m)
2099 let mut m = vec![0u64; ring_size as usize];
2100 RandomFillUniformInModulus::random_fill(&mut rng, &q, m.as_mut_slice());
2101 let mut rlwe_ct = _sk_encrypt_rlwe(&m, s.values(), &ntt_op, &mod_op);
2102
2103 // send rgsw to evaluation domain
2104 rgsw_carrym
2105 .iter_mut()
2106 .for_each(|ri| ntt_op.forward(ri.as_mut_slice()));
2107
2108 rlwe_by_rgsw(
2109 &mut rlwe_ct,
2110 &rgsw_carrym,
2111 &mut scratch_matrix,
2112 &decomposer,
2113 &ntt_op,
2114 &mod_op,
2115 );
2116 let m_expected = negacyclic_mul(&carry_m, &m, mul_mod, q);
2117 let noise = measure_noise(&rlwe_ct, &m_expected, &ntt_op, &mod_op, s.values());
2118 println!("RLWE(m) x RGSW(carry_m): {noise}");
2119 }
2120 }
2121
2122 #[test]
2123 fn some_work() {
2124 let logq = 50;
2125 let ring_size = 1 << 11;
2126 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
2127 let d_rgsw = 10;
2128 let logb = 5;
2129 let decomposer = (
2130 DefaultDecomposer::new(q, logb, d_rgsw),
2131 DefaultDecomposer::new(q, logb, d_rgsw),
2132 );
2133
2134 let ntt_op = NttBackendU64::new(&q, ring_size as usize);
2135 let mod_op = ModularOpsU64::new(q);
2136 let mut rng = DefaultSecureRng::new_seeded([0u8; 32]);
2137
2138 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
2139
2140 let mut check = Stats { samples: vec![] };
2141
2142 for _ in 0..100 {
2143 let mut m0 = vec![0u64; ring_size as usize];
2144 m0[thread_rng().gen_range(0..ring_size) as usize] = 1;
2145 let mut m1 = vec![0u64; ring_size as usize];
2146 m1[thread_rng().gen_range(0..ring_size) as usize] = 1;
2147
2148 let mut rgsw_ct0 = {
2149 let seeded_rgsw_ct =
2150 _sk_encrypt_rgsw(&m0, s.values(), &decomposer, &mod_op, &ntt_op);
2151 RgswCiphertextEvaluationDomain::<Vec<Vec<u64>>, DefaultSecureRng, NttBackendU64>::from(&seeded_rgsw_ct)
2152 };
2153 let rgsw_ct1 = {
2154 let seeded_rgsw_ct =
2155 _sk_encrypt_rgsw(&m1, s.values(), &decomposer, &mod_op, &ntt_op);
2156 RgswCiphertextEvaluationDomain::<Vec<Vec<u64>>, DefaultSecureRng, NttBackendU64>::from(&seeded_rgsw_ct)
2157 };
2158
2159 // RGSW x RGSW
2160 // send RGSW(m0) to coefficient domain
2161 rgsw_ct0
2162 .data
2163 .iter_mut()
2164 .for_each(|r| ntt_op.backward(r.as_mut_slice()));
2165 let mut scratch_matrix = vec![
2166 vec![0u64; ring_size as usize];
2167 std::cmp::max(
2168 decomposer.a().decomposition_count(),
2169 decomposer.b().decomposition_count()
2170 ) + decomposer.a().decomposition_count() * 2
2171 + decomposer.b().decomposition_count() * 2
2172 ];
2173 rgsw_by_rgsw_inplace(
2174 &mut rgsw_ct0.data,
2175 &rgsw_ct1.data,
2176 &decomposer,
2177 &mut scratch_matrix,
2178 &ntt_op,
2179 &mod_op,
2180 );
2181 let mut rgsw_m0m1 = rgsw_ct0;
2182 // Back to Evaluation for RLWExRGSW
2183 rgsw_m0m1
2184 .data
2185 .iter_mut()
2186 .for_each(|r| ntt_op.forward(r.as_mut_slice()));
2187
2188 // Sample m2, encrypt it as RLWE(m2) and multiply RLWE(m2)xRGSW(m0m1)
2189 let mut m2 = vec![0u64; ring_size as usize];
2190 RandomFillUniformInModulus::random_fill(&mut rng, &q, m2.as_mut_slice());
2191 let mut rlwe_in_ct = { _sk_encrypt_rlwe(&m2, s.values(), &ntt_op, &mod_op) };
2192 let mut scratch_space = vec![
2193 vec![0u64; ring_size as usize];
2194 std::cmp::max(
2195 decomposer.a().decomposition_count(),
2196 decomposer.b().decomposition_count()
2197 ) + 2
2198 ];
2199 rlwe_by_rgsw(
2200 &mut rlwe_in_ct,
2201 &rgsw_m0m1.data,
2202 &mut scratch_space,
2203 &decomposer,
2204 &ntt_op,
2205 &mod_op,
2206 );
2207
2208 // Decrypt RLWE(m0m1m2)
2209 let mut m0m1m2_back = vec![0u64; ring_size as usize];
2210 decrypt_rlwe(&rlwe_in_ct, s.values(), &mut m0m1m2_back, &ntt_op, &mod_op);
2211
2212 // Calculate m0m1m2
2213 let mul_mod = |v0: &u64, v1: &u64| ((*v0 as u128 * *v1 as u128) % q as u128) as u64;
2214 let m0m1 = negacyclic_mul(&m0, &m1, mul_mod, q);
2215 let m0m1m2 = negacyclic_mul(&m2, &m0m1, mul_mod, q);
2216
2217 // diff
2218 mod_op.elwise_sub_mut(m0m1m2_back.as_mut_slice(), m0m1m2.as_ref());
2219
2220 check.add_more(&Vec::<i64>::try_convert_from(&m0m1m2_back, &q));
2221 }
2222
2223 println!("Std: {}", check.std_dev().abs().log2());
2224 }
2225}