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