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