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