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