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