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, 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 SeededRgswCiphertext<M, S>
21where
22 M: Matrix,
23{
24 data: M,
25 seed: S,
26 modulus: M::MatElement,
27}
28
29impl<M: Matrix + MatrixEntity, S> SeededRgswCiphertext<M, S> {
30 fn from_raw(data: M, seed: S, modulus: M::MatElement) -> SeededRgswCiphertext<M, S> {
31 assert!(data.dimension().0 % 3 == 0);
32
33 SeededRgswCiphertext {
34 data,
35 seed,
36 modulus,
37 }
38 }
39
40 fn empty(
41 ring_size: usize,
42 d_rgsw: usize,
43 seed: S,
44 modulus: M::MatElement,
45 ) -> SeededRgswCiphertext<M, S> {
46 SeededRgswCiphertext {
47 data: M::zeros(d_rgsw * 3, ring_size),
48 seed,
49 modulus: modulus,
50 }
51 }
52}
53
54impl<M: Debug + Matrix, S: Debug> Debug for SeededRgswCiphertext<M, S>
55where
56 M::MatElement: Debug,
57{
58 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
59 f.debug_struct("SeededRgswCiphertext")
60 .field("data", &self.data)
61 .field("seed", &self.seed)
62 .field("modulus", &self.modulus)
63 .finish()
64 }
65}
66
67pub struct RgswCiphertextEvaluationDomain<M, R, N> {
68 data: M,
69 _phantom: PhantomData<(R, N)>,
70}
71
72impl<
73 M: MatrixMut + MatrixEntity,
74 R: NewWithSeed + RandomUniformDist<[M::MatElement], Parameters = M::MatElement>,
75 N: NttInit<Element = M::MatElement> + Ntt<Element = M::MatElement> + Debug,
76 > From<&SeededRgswCiphertext<M, R::Seed>> for RgswCiphertextEvaluationDomain<M, R, N>
77where
78 <M as Matrix>::R: RowMut,
79 M::MatElement: Copy,
80 R::Seed: Clone,
81 M: Debug,
82{
83 fn from(value: &SeededRgswCiphertext<M, R::Seed>) -> Self {
84 let d = value.data.dimension().0.div(3);
85
86 let mut data = M::zeros(4 * d, value.data.dimension().1);
87
88 // copy RLWE'(-sm)
89 izip!(data.iter_rows_mut().take(2 * d), value.data.iter_rows()).for_each(
90 |(to_ri, from_ri)| {
91 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
92 },
93 );
94
95 // sample A polynomials of RLWE'(m) - RLWE'A(m)
96 // TODO(Jay): Do we want to be generic over RandomGenerator used here? I think
97 // not.
98 let mut p_rng = R::new_with_seed(value.seed.clone());
99 izip!(data.iter_rows_mut().skip(2 * d).take(d))
100 .for_each(|ri| p_rng.random_fill(&value.modulus, ri.as_mut()));
101
102 // RLWE'_B(m)
103 izip!(
104 data.iter_rows_mut().skip(3 * d),
105 value.data.iter_rows().skip(2 * d)
106 )
107 .for_each(|(to_ri, from_ri)| {
108 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
109 });
110
111 // Send polynomials to evaluation domain
112 let ring_size = data.dimension().1;
113 let nttop = N::new(value.modulus, ring_size);
114 data.iter_rows_mut()
115 .for_each(|ri| nttop.forward(ri.as_mut()));
116
117 Self {
118 data: data,
119 _phantom: PhantomData,
120 }
121 }
122}
123
124impl<M: Debug, R, N> Debug for RgswCiphertextEvaluationDomain<M, R, N> {
125 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
126 f.debug_struct("RgswCiphertextEvaluationDomain")
127 .field("data", &self.data)
128 .field("_phantom", &self._phantom)
129 .finish()
130 }
131}
132
133impl<M: Matrix, R, N> Matrix for RgswCiphertextEvaluationDomain<M, R, N> {
134 type MatElement = M::MatElement;
135 type R = M::R;
136
137 fn dimension(&self) -> (usize, usize) {
138 self.data.dimension()
139 }
140}
141
142impl<M: Matrix, R, N> AsRef<[M::R]> for RgswCiphertextEvaluationDomain<M, R, N> {
143 fn as_ref(&self) -> &[M::R] {
144 self.data.as_ref()
145 }
146}
147
148pub struct SeededRlweCiphertext<R, S>
149where
150 R: Row,
151{
152 data: R,
153 seed: S,
154 modulus: R::Element,
155}
156
157impl<R: RowEntity, S> SeededRlweCiphertext<R, S> {
158 fn empty(ring_size: usize, seed: S, modulus: R::Element) -> Self {
159 SeededRlweCiphertext {
160 data: R::zeros(ring_size),
161 seed,
162 modulus,
163 }
164 }
165}
166
167pub struct RlweCiphertext<M, Rng> {
168 data: M,
169 is_trivial: bool,
170 _phatom: PhantomData<Rng>,
171}
172
173impl<M, Rng> RlweCiphertext<M, Rng> {
174 pub(crate) fn from_raw(data: M, is_trivial: bool) -> Self {
175 RlweCiphertext {
176 data,
177 is_trivial,
178 _phatom: PhantomData,
179 }
180 }
181}
182
183impl<M: Matrix, Rng> Matrix for RlweCiphertext<M, Rng> {
184 type MatElement = M::MatElement;
185 type R = M::R;
186
187 fn dimension(&self) -> (usize, usize) {
188 self.data.dimension()
189 }
190}
191
192impl<M: MatrixMut, Rng> MatrixMut for RlweCiphertext<M, Rng> where <M as Matrix>::R: RowMut {}
193
194impl<M: Matrix, Rng> AsRef<[<M as Matrix>::R]> for RlweCiphertext<M, Rng> {
195 fn as_ref(&self) -> &[<M as Matrix>::R] {
196 self.data.as_ref()
197 }
198}
199
200impl<M: MatrixMut, Rng> AsMut<[<M as Matrix>::R]> for RlweCiphertext<M, Rng>
201where
202 <M as Matrix>::R: RowMut,
203{
204 fn as_mut(&mut self) -> &mut [<M as Matrix>::R] {
205 self.data.as_mut()
206 }
207}
208
209impl<M, Rng> IsTrivial for RlweCiphertext<M, Rng> {
210 fn is_trivial(&self) -> bool {
211 self.is_trivial
212 }
213 fn set_not_trivial(&mut self) {
214 self.is_trivial = false;
215 }
216}
217
218impl<R: Row, M: MatrixEntity<R = R, MatElement = R::Element> + MatrixMut, Rng: NewWithSeed>
219 From<&SeededRlweCiphertext<R, Rng::Seed>> for RlweCiphertext<M, Rng>
220where
221 Rng::Seed: Clone,
222 Rng: RandomUniformDist<[M::MatElement], Parameters = M::MatElement>,
223 <M as Matrix>::R: RowMut,
224 R::Element: Copy,
225{
226 fn from(value: &SeededRlweCiphertext<R, Rng::Seed>) -> Self {
227 let mut data = M::zeros(2, value.data.as_ref().len());
228
229 // sample a
230 let mut p_rng = Rng::new_with_seed(value.seed.clone());
231 RandomUniformDist::random_fill(&mut p_rng, &value.modulus, data.get_row_mut(0));
232
233 data.get_row_mut(1).copy_from_slice(value.data.as_ref());
234
235 RlweCiphertext {
236 data,
237 is_trivial: false,
238 _phatom: PhantomData,
239 }
240 }
241}
242
243pub trait IsTrivial {
244 fn is_trivial(&self) -> bool;
245 fn set_not_trivial(&mut self);
246}
247
248#[derive(Clone)]
249pub struct RlweSecret {
250 values: Vec<i32>,
251}
252
253impl Secret for RlweSecret {
254 type Element = i32;
255 fn values(&self) -> &[Self::Element] {
256 &self.values
257 }
258}
259
260impl RlweSecret {
261 pub fn random(hw: usize, n: usize) -> RlweSecret {
262 DefaultSecureRng::with_local_mut(|rng| {
263 let mut out = vec![0i32; n];
264 fill_random_ternary_secret_with_hamming_weight(&mut out, hw, rng);
265
266 RlweSecret { values: out }
267 })
268 }
269}
270
271pub(crate) fn generate_auto_map(ring_size: usize, k: isize) -> (Vec<usize>, Vec<bool>) {
272 assert!(k & 1 == 1, "Auto {k} must be odd");
273
274 let k = if k < 0 {
275 // k is -ve, return k%(2*N)
276 (2 * ring_size) - (k.abs() as usize % (2 * ring_size))
277 } else {
278 k as usize
279 };
280 let (auto_map_index, auto_sign_index): (Vec<usize>, Vec<bool>) = (0..ring_size)
281 .into_iter()
282 .map(|i| {
283 let mut to_index = (i * k) % (2 * ring_size);
284 let mut sign = true;
285
286 // wrap around. false implies negative
287 if to_index >= ring_size {
288 to_index = to_index - ring_size;
289 sign = false;
290 }
291
292 (to_index, sign)
293 })
294 .unzip();
295 (auto_map_index, auto_sign_index)
296}
297
298/// Generates RLWE Key switching key to key switch ciphertext RLWE_{from_s}(m)
299/// to RLWE_{to_s}(m).
300///
301/// Key switching equals
302/// \sum decompose(c_1)_i * RLWE_{to_s}(\beta^i -from_s)
303/// Hence, key switchin key equals RLWE'(-from_s) = RLWE(-from_s), RLWE(beta^1
304/// -from_s), ..., RLWE(beta^{d-1} -from_s).
305///
306/// - ksk_out: Output Key switching key. Key switching key stores only part B
307/// polynomials of ksk RLWE ciphertexts (i.e. RLWE'_B(-from_s)) in coefficient
308/// domain
309/// - neg_from_s: Negative of secret polynomial to key switch from
310/// - to_s: secret polynomial to key switch to.
311pub(crate) fn rlwe_ksk_gen<
312 Mmut: MatrixMut + MatrixEntity,
313 ModOp: ArithmeticOps<Element = Mmut::MatElement> + VectorOps<Element = Mmut::MatElement>,
314 NttOp: Ntt<Element = Mmut::MatElement>,
315 R: RandomGaussianDist<[Mmut::MatElement], Parameters = Mmut::MatElement>
316 + RandomUniformDist<[Mmut::MatElement], Parameters = Mmut::MatElement>
317 + NewWithSeed,
318>(
319 ksk_out: &mut Mmut,
320 mut neg_from_s: Mmut::R,
321 mut to_s: Mmut::R,
322 gadget_vector: &[Mmut::MatElement],
323 mod_op: &ModOp,
324 ntt_op: &NttOp,
325 seed: R::Seed,
326 rng: &mut R,
327) where
328 <Mmut as Matrix>::R: RowMut,
329{
330 let ring_size = neg_from_s.as_ref().len();
331 let d = gadget_vector.len();
332 assert!(ksk_out.dimension() == (d, ring_size));
333
334 let q = ArithmeticOps::modulus(mod_op);
335
336 ntt_op.forward(to_s.as_mut());
337
338 // RLWE'_{to_s}(-from_s)
339 let mut part_a = {
340 let mut a = Mmut::zeros(d, ring_size);
341 let mut p_rng = R::new_with_seed(seed);
342 a.iter_rows_mut()
343 .for_each(|ai| RandomUniformDist::random_fill(&mut p_rng, &q, ai.as_mut()));
344 a
345 };
346 izip!(
347 part_a.iter_rows_mut(),
348 ksk_out.iter_rows_mut(),
349 gadget_vector.iter(),
350 )
351 .for_each(|(ai, bi, beta_i)| {
352 // si * ai
353 ntt_op.forward(ai.as_mut());
354 mod_op.elwise_mul_mut(ai.as_mut(), to_s.as_ref());
355 ntt_op.backward(ai.as_mut());
356
357 // ei + to_s*ai
358 RandomGaussianDist::random_fill(rng, &q, bi.as_mut());
359 mod_op.elwise_add_mut(bi.as_mut(), ai.as_ref());
360
361 // beta_i * -from_s
362 // use ai as scratch space
363 mod_op.elwise_scalar_mul(ai.as_mut(), neg_from_s.as_ref(), beta_i);
364
365 // bi = ei + to_s*ai + beta_i*-from_s
366 mod_op.elwise_add_mut(bi.as_mut(), ai.as_ref());
367 });
368}
369
370pub(crate) fn galois_key_gen<
371 Mmut: MatrixMut + MatrixEntity,
372 ModOp: ArithmeticOps<Element = Mmut::MatElement> + VectorOps<Element = Mmut::MatElement>,
373 NttOp: Ntt<Element = Mmut::MatElement>,
374 S,
375 R: RandomGaussianDist<[Mmut::MatElement], Parameters = Mmut::MatElement>
376 + RandomUniformDist<[Mmut::MatElement], Parameters = Mmut::MatElement>
377 + NewWithSeed,
378>(
379 ksk_out: &mut Mmut,
380 s: &[S],
381 auto_k: isize,
382 gadget_vector: &[Mmut::MatElement],
383 mod_op: &ModOp,
384 ntt_op: &NttOp,
385 seed: R::Seed,
386 rng: &mut R,
387) where
388 <Mmut as Matrix>::R: RowMut,
389 Mmut::R: TryConvertFrom<[S], Parameters = Mmut::MatElement> + RowEntity,
390 Mmut::MatElement: Copy + Sub<Output = Mmut::MatElement>,
391{
392 let ring_size = s.len();
393 let (auto_map_index, auto_map_sign) = generate_auto_map(ring_size, auto_k);
394
395 let q = ArithmeticOps::modulus(mod_op);
396
397 // s(X) -> -s(X^k)
398 let s = Mmut::R::try_convert_from(s, &q);
399 let mut neg_s_auto = Mmut::R::zeros(s.as_ref().len());
400 izip!(s.as_ref(), auto_map_index.iter(), auto_map_sign.iter()).for_each(
401 |(el, to_index, sign)| {
402 // if sign is +ve (true), then negate because we need -s(X) (i.e. do the
403 // opposite than the usual case)
404 if *sign {
405 neg_s_auto.as_mut()[*to_index] = q - *el;
406 } else {
407 neg_s_auto.as_mut()[*to_index] = *el;
408 }
409 },
410 );
411
412 // Ksk from -s(X^k) to s(X)
413 rlwe_ksk_gen(
414 ksk_out,
415 neg_s_auto,
416 s,
417 gadget_vector,
418 mod_op,
419 ntt_op,
420 seed,
421 rng,
422 );
423}
424
425pub(crate) fn routine<M: Matrix + ?Sized, ModOp: VectorOps<Element = M::MatElement>>(
426 write_to_row: &mut [M::MatElement],
427 matrix_a: &[M::R],
428 matrix_b: &[M::R],
429 mod_op: &ModOp,
430) {
431 izip!(matrix_a.iter(), matrix_b.iter()).for_each(|(a, b)| {
432 mod_op.elwise_fma_mut(write_to_row, a.as_ref(), b.as_ref());
433 });
434}
435
436/// Decomposes ring polynomial r(X) into d polynomials using decomposer into
437/// output matrix decomp_r
438///
439/// Note that decomposition of r(X) requires decomposition of each of
440/// coefficients.
441///
442/// - decomp_r: must have dimensions d x ring_size. i^th decomposed polynomial
443/// will be stored at i^th row.
444pub(crate) fn decompose_r<M: Matrix + MatrixMut, D: Decomposer<Element = M::MatElement>>(
445 r: &[M::MatElement],
446 decomp_r: &mut [M::R],
447 decomposer: &D,
448) where
449 <M as Matrix>::R: RowMut,
450 M::MatElement: Copy,
451{
452 let ring_size = r.len();
453 let d = decomposer.d();
454
455 for ri in 0..ring_size {
456 let el_decomposed = decomposer.decompose(&r[ri]);
457 for j in 0..d {
458 decomp_r[j].as_mut()[ri] = el_decomposed[j];
459 }
460 }
461}
462
463/// Sends RLWE_{s}(X) -> RLWE_{s}(X^k) where k is some galois element
464pub(crate) fn galois_auto<
465 MT: Matrix + IsTrivial + MatrixMut,
466 Mmut: MatrixMut<MatElement = MT::MatElement>,
467 ModOp: ArithmeticOps<Element = MT::MatElement> + VectorOps<Element = MT::MatElement>,
468 NttOp: Ntt<Element = MT::MatElement>,
469 D: Decomposer<Element = MT::MatElement>,
470>(
471 rlwe_in: &mut MT,
472 ksk: &Mmut,
473 scratch_matrix_dplus2_ring: &mut Mmut,
474 auto_map_index: &[usize],
475 auto_map_sign: &[bool],
476 mod_op: &ModOp,
477 ntt_op: &NttOp,
478 decomposer: &D,
479) where
480 <Mmut as Matrix>::R: RowMut,
481 <MT as Matrix>::R: RowMut,
482 MT::MatElement: Copy + Zero,
483{
484 let d = decomposer.d();
485
486 let (scratch_matrix_d_ring, tmp_rlwe_out) = scratch_matrix_dplus2_ring.split_at_row_mut(d);
487
488 // send b(X) -> b(X^k)
489 izip!(
490 rlwe_in.get_row(1),
491 auto_map_index.iter(),
492 auto_map_sign.iter()
493 )
494 .for_each(|(el_in, to_index, sign)| {
495 if !*sign {
496 tmp_rlwe_out[1].as_mut()[*to_index] = mod_op.neg(el_in);
497 } else {
498 tmp_rlwe_out[1].as_mut()[*to_index] = *el_in;
499 // scratch_matrix_dplus2_ring.set(d + 1, *to_index, *el_in);
500 }
501 });
502
503 if !rlwe_in.is_trivial() {
504 // send a(X) -> a(X^k) and decompose a(X^k)
505 izip!(
506 rlwe_in.get_row(0),
507 auto_map_index.iter(),
508 auto_map_sign.iter()
509 )
510 .for_each(|(el_in, to_index, sign)| {
511 let el_out = if !*sign { mod_op.neg(el_in) } else { *el_in };
512
513 let el_out_decomposed = decomposer.decompose(&el_out);
514 for j in 0..d {
515 scratch_matrix_d_ring[j].as_mut()[*to_index] = el_out_decomposed[j];
516 }
517 });
518
519 // transform decomposed a(X^k) to evaluation domain
520 scratch_matrix_d_ring.iter_mut().for_each(|r| {
521 ntt_op.forward(r.as_mut());
522 });
523
524 // RLWE(m^k) = a', b'; RLWE(m) = a, b
525 // key switch: (a * RLWE'(s(X^k)))
526 let (ksk_a, ksk_b) = ksk.split_at_row(d);
527 tmp_rlwe_out[0].as_mut().fill(Mmut::MatElement::zero());
528 // a' = decomp<a> * RLWE'_A(s(X^k))
529 routine::<Mmut, ModOp>(
530 tmp_rlwe_out[0].as_mut(),
531 scratch_matrix_d_ring,
532 ksk_a,
533 mod_op,
534 );
535 // send b(X^k) to evaluation domain
536 ntt_op.forward(tmp_rlwe_out[1].as_mut());
537 // b' = b(X^k)
538 // b' += decomp<a(X^k)> * RLWE'_B(s(X^k))
539 routine::<Mmut, ModOp>(
540 tmp_rlwe_out[1].as_mut(),
541 scratch_matrix_d_ring,
542 ksk_b,
543 mod_op,
544 );
545
546 // transform RLWE(m^k) to coefficient domain
547 tmp_rlwe_out
548 .iter_mut()
549 .for_each(|r| ntt_op.backward(r.as_mut()));
550
551 rlwe_in
552 .get_row_mut(0)
553 .copy_from_slice(tmp_rlwe_out[0].as_ref());
554 }
555
556 rlwe_in
557 .get_row_mut(1)
558 .copy_from_slice(tmp_rlwe_out[1].as_ref());
559}
560
561/// Returns RLWE(m0m1) = RLWE(m0) x RGSW(m1). Mutates rlwe_in inplace to equal
562/// RLWE(m0m1)
563///
564/// - rlwe_in: is RLWE(m0) with polynomials in coefficient domain
565/// - rgsw_in: is RGSW(m1) with polynomials in evaluation domain
566/// - scratch_matrix_d_ring: is a matrix of dimension (d_rgsw, ring_size) used
567/// as scratch space to store decomposed Ring elements temporarily
568pub(crate) fn rlwe_by_rgsw<
569 Mmut: MatrixMut,
570 MT: Matrix<MatElement = Mmut::MatElement> + MatrixMut<MatElement = Mmut::MatElement> + IsTrivial,
571 D: Decomposer<Element = Mmut::MatElement>,
572 ModOp: VectorOps<Element = Mmut::MatElement>,
573 NttOp: Ntt<Element = Mmut::MatElement>,
574>(
575 rlwe_in: &mut MT,
576 rgsw_in: &Mmut,
577 scratch_matrix_dplus2_ring: &mut Mmut,
578 decomposer: &D,
579 ntt_op: &NttOp,
580 mod_op: &ModOp,
581) where
582 Mmut::MatElement: Copy + Zero,
583 <Mmut as Matrix>::R: RowMut,
584 <MT as Matrix>::R: RowMut,
585{
586 let d_rgsw = decomposer.d();
587 assert!(scratch_matrix_dplus2_ring.dimension() == (d_rgsw + 2, rlwe_in.dimension().1));
588 assert!(rgsw_in.dimension() == (d_rgsw * 4, rlwe_in.dimension().1));
589
590 // decomposed RLWE x RGSW
591 let (rlwe_dash_nsm, rlwe_dash_m) = rgsw_in.split_at_row(d_rgsw * 2);
592 let (scratch_matrix_d_ring, scratch_rlwe_out) =
593 scratch_matrix_dplus2_ring.split_at_row_mut(d_rgsw);
594 scratch_rlwe_out[0].as_mut().fill(Mmut::MatElement::zero());
595 scratch_rlwe_out[1].as_mut().fill(Mmut::MatElement::zero());
596 // RLWE_in = a_in, b_in; RLWE_out = a_out, b_out
597 if !rlwe_in.is_trivial() {
598 // a_in = 0 when RLWE_in is trivial RLWE ciphertext
599 // decomp<a_in>
600 decompose_r::<Mmut, D>(rlwe_in.get_row_slice(0), scratch_matrix_d_ring, decomposer);
601 scratch_matrix_d_ring
602 .iter_mut()
603 .for_each(|r| ntt_op.forward(r.as_mut()));
604 // a_out += decomp<a_in> \cdot RLWE_A'(-sm)
605 routine::<Mmut, ModOp>(
606 scratch_rlwe_out[0].as_mut(),
607 scratch_matrix_d_ring.as_ref(),
608 &rlwe_dash_nsm[..d_rgsw],
609 mod_op,
610 );
611 // b_out += decomp<a_in> \cdot RLWE_B'(-sm)
612 routine::<Mmut, ModOp>(
613 scratch_rlwe_out[1].as_mut(),
614 scratch_matrix_d_ring.as_ref(),
615 &rlwe_dash_nsm[d_rgsw..],
616 mod_op,
617 );
618 }
619 // decomp<b_in>
620 decompose_r::<Mmut, D>(rlwe_in.get_row_slice(1), scratch_matrix_d_ring, decomposer);
621 scratch_matrix_d_ring
622 .iter_mut()
623 .for_each(|r| ntt_op.forward(r.as_mut()));
624 // a_out += decomp<b_in> \cdot RLWE_A'(m)
625 routine::<Mmut, ModOp>(
626 scratch_rlwe_out[0].as_mut(),
627 scratch_matrix_d_ring.as_ref(),
628 &rlwe_dash_m[..d_rgsw],
629 mod_op,
630 );
631 // b_out += decomp<b_in> \cdot RLWE_B'(m)
632 routine::<Mmut, ModOp>(
633 scratch_rlwe_out[1].as_mut(),
634 scratch_matrix_d_ring.as_ref(),
635 &rlwe_dash_m[d_rgsw..],
636 mod_op,
637 );
638
639 // transform rlwe_out to coefficient domain
640 scratch_rlwe_out
641 .iter_mut()
642 .for_each(|r| ntt_op.backward(r.as_mut()));
643
644 rlwe_in
645 .get_row_mut(0)
646 .copy_from_slice(scratch_rlwe_out[0].as_mut());
647 rlwe_in
648 .get_row_mut(1)
649 .copy_from_slice(scratch_rlwe_out[1].as_mut());
650 rlwe_in.set_not_trivial();
651}
652
653/// Encrypts message m as a RGSW ciphertext.
654///
655/// - m_eval: is `m` is evaluation domain
656/// - out_rgsw: RGSW(m) is stored as single matrix of dimension (d_rgsw * 3,
657/// ring_size). The matrix has the following structure [RLWE'_A(-sm) ||
658/// RLWE'_B(-sm) || RLWE'_B(m)]^T and RLWE'_A(m) is generated via seed
659pub(crate) fn secret_key_encrypt_rgsw<
660 Mmut: MatrixMut + MatrixEntity,
661 S,
662 R: RandomGaussianDist<[Mmut::MatElement], Parameters = Mmut::MatElement>
663 + RandomUniformDist<[Mmut::MatElement], Parameters = Mmut::MatElement>
664 + NewWithSeed,
665 ModOp: VectorOps<Element = Mmut::MatElement>,
666 NttOp: Ntt<Element = Mmut::MatElement>,
667>(
668 out_rgsw: &mut Mmut,
669 m: &Mmut::R,
670 gadget_vector: &[Mmut::MatElement],
671 s: &[S],
672 mod_op: &ModOp,
673 ntt_op: &NttOp,
674 seed: R::Seed,
675 rng: &mut R,
676) where
677 <Mmut as Matrix>::R:
678 RowMut + RowEntity + TryConvertFrom<[S], Parameters = Mmut::MatElement> + Debug,
679 Mmut::MatElement: Copy + Debug,
680 Mmut: Debug,
681{
682 let d = gadget_vector.len();
683 let q = mod_op.modulus();
684 let ring_size = s.len();
685 assert!(out_rgsw.dimension() == (d * 3, ring_size));
686 assert!(m.as_ref().len() == ring_size);
687
688 // RLWE(-sm), RLWE(m)
689 let (rlwe_dash_nsm, b_rlwe_dash_m) = out_rgsw.split_at_row_mut(d * 2);
690
691 let mut s_eval = Mmut::R::try_convert_from(s, &q);
692 ntt_op.forward(s_eval.as_mut());
693
694 let mut scratch_space = Mmut::R::zeros(ring_size);
695
696 // RLWE'(-sm)
697 let (a_rlwe_dash_nsm, b_rlwe_dash_nsm) = rlwe_dash_nsm.split_at_mut(d);
698 izip!(
699 a_rlwe_dash_nsm.iter_mut(),
700 b_rlwe_dash_nsm.iter_mut(),
701 gadget_vector.iter()
702 )
703 .for_each(|(ai, bi, beta_i)| {
704 // Sample a_i
705 RandomUniformDist::random_fill(rng, &q, ai.as_mut());
706
707 // a_i * s
708 scratch_space.as_mut().copy_from_slice(ai.as_ref());
709 ntt_op.forward(scratch_space.as_mut());
710 mod_op.elwise_mul_mut(scratch_space.as_mut(), s_eval.as_ref());
711 ntt_op.backward(scratch_space.as_mut());
712
713 // b_i = e_i + a_i * s
714 RandomGaussianDist::random_fill(rng, &q, bi.as_mut());
715 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.as_ref());
716
717 // a_i + \beta_i * m
718 mod_op.elwise_scalar_mul(scratch_space.as_mut(), m.as_ref(), beta_i);
719 mod_op.elwise_add_mut(ai.as_mut(), scratch_space.as_ref());
720 });
721
722 // RLWE(m)
723 let mut a_rlwe_dash_m = {
724 // polynomials of part A of RLWE'(m) are sampled from seed
725 let mut p_rng = R::new_with_seed(seed);
726 let mut a = Mmut::zeros(d, ring_size);
727 a.iter_rows_mut()
728 .for_each(|ai| RandomUniformDist::random_fill(&mut p_rng, &q, ai.as_mut()));
729 a
730 };
731
732 izip!(
733 a_rlwe_dash_m.iter_rows_mut(),
734 b_rlwe_dash_m.iter_mut(),
735 gadget_vector.iter()
736 )
737 .for_each(|(ai, bi, beta_i)| {
738 // ai * s
739 ntt_op.forward(ai.as_mut());
740 mod_op.elwise_mul_mut(ai.as_mut(), s_eval.as_ref());
741 ntt_op.backward(ai.as_mut());
742
743 // beta_i * m
744 mod_op.elwise_scalar_mul(scratch_space.as_mut(), m.as_ref(), beta_i);
745
746 // Sample e_i
747 RandomGaussianDist::random_fill(rng, &q, bi.as_mut());
748 // e_i + beta_i * m + ai*s
749 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.as_ref());
750 mod_op.elwise_add_mut(bi.as_mut(), ai.as_ref());
751 });
752}
753
754/// Encrypt polynomial m(X) as RLWE ciphertext.
755///
756/// - rlwe_out: returned RLWE ciphertext RLWE(m) in coefficient domain. RLWE
757/// ciphertext is a matirx with first row consiting polynomial `a` and the
758/// second rows consting polynomial `b`
759pub(crate) fn secret_key_encrypt_rlwe<
760 Ro: Row + RowMut + RowEntity,
761 ModOp: VectorOps<Element = Ro::Element>,
762 NttOp: Ntt<Element = Ro::Element>,
763 S,
764 R: RandomUniformDist<[Ro::Element], Parameters = Ro::Element>
765 + RandomGaussianDist<[Ro::Element], Parameters = Ro::Element>
766 + NewWithSeed,
767>(
768 m: &Ro,
769 b_rlwe_out: &mut Ro,
770 s: &[S],
771 mod_op: &ModOp,
772 ntt_op: &NttOp,
773 seed: R::Seed,
774 rng: &mut R,
775) where
776 Ro: TryConvertFrom<[S], Parameters = Ro::Element> + Debug,
777{
778 let ring_size = s.len();
779 assert!(m.as_ref().len() == ring_size);
780 assert!(b_rlwe_out.as_ref().len() == ring_size);
781
782 let q = mod_op.modulus();
783
784 // sample a
785 let mut a = {
786 let mut a = Ro::zeros(ring_size);
787 let mut p_rng = R::new_with_seed(seed);
788 RandomUniformDist::random_fill(&mut p_rng, &q, a.as_mut());
789 a
790 };
791
792 // s * a
793 let mut sa = Ro::try_convert_from(s, &q);
794 ntt_op.forward(sa.as_mut());
795 ntt_op.forward(a.as_mut());
796 mod_op.elwise_mul_mut(sa.as_mut(), a.as_ref());
797 ntt_op.backward(sa.as_mut());
798
799 // sample e
800 RandomGaussianDist::random_fill(rng, &q, b_rlwe_out.as_mut());
801 mod_op.elwise_add_mut(b_rlwe_out.as_mut(), m.as_ref());
802 mod_op.elwise_add_mut(b_rlwe_out.as_mut(), sa.as_ref());
803}
804
805/// Decrypts degree 1 RLWE ciphertext RLWE(m) and returns m
806///
807/// - rlwe_ct: input degree 1 ciphertext RLWE(m).
808pub(crate) fn decrypt_rlwe<
809 R: RowMut,
810 M: Matrix<MatElement = R::Element>,
811 ModOp: VectorOps<Element = R::Element>,
812 NttOp: Ntt<Element = R::Element>,
813 S,
814>(
815 rlwe_ct: &M,
816 s: &[S],
817 m_out: &mut R,
818 ntt_op: &NttOp,
819 mod_op: &ModOp,
820) where
821 R: TryConvertFrom<[S], Parameters = R::Element>,
822 R::Element: Copy,
823{
824 let ring_size = s.len();
825 assert!(rlwe_ct.dimension() == (2, ring_size));
826 assert!(m_out.as_ref().len() == ring_size);
827
828 // transform a to evluation form
829 m_out.as_mut().copy_from_slice(rlwe_ct.get_row_slice(0));
830 ntt_op.forward(m_out.as_mut());
831
832 // -s*a
833 let mut s = R::try_convert_from(&s, &mod_op.modulus());
834 ntt_op.forward(s.as_mut());
835 mod_op.elwise_mul_mut(m_out.as_mut(), s.as_ref());
836 mod_op.elwise_neg_mut(m_out.as_mut());
837 ntt_op.backward(m_out.as_mut());
838
839 // m+e = b - s*a
840 mod_op.elwise_add_mut(m_out.as_mut(), rlwe_ct.get_row_slice(1));
841}
842
843// Measures noise in degree 1 RLWE ciphertext against encoded ideal message
844// encoded_m
845pub(crate) fn measure_noise<
846 Mmut: MatrixMut + Matrix + MatrixEntity,
847 ModOp: VectorOps<Element = Mmut::MatElement>,
848 NttOp: Ntt<Element = Mmut::MatElement>,
849 S: Secret,
850>(
851 rlwe_ct: &Mmut,
852 encoded_m_ideal: &Mmut,
853 ntt_op: &NttOp,
854 mod_op: &ModOp,
855 s: &S,
856) -> f64
857where
858 <Mmut as Matrix>::R: RowMut,
859 Mmut: TryConvertFrom<[S::Element], Parameters = Mmut::MatElement>,
860 Mmut::MatElement: PrimInt + ToPrimitive + Debug,
861{
862 let ring_size = s.values().len();
863 assert!(rlwe_ct.dimension() == (2, ring_size));
864 assert!(encoded_m_ideal.dimension() == (1, ring_size));
865
866 // -(s * a)
867 let q = VectorOps::modulus(mod_op);
868 let mut s = Mmut::try_convert_from(s.values(), &q);
869 ntt_op.forward(s.get_row_mut(0));
870 let mut a = Mmut::zeros(1, ring_size);
871 a.get_row_mut(0).copy_from_slice(rlwe_ct.get_row_slice(0));
872 ntt_op.forward(a.get_row_mut(0));
873 mod_op.elwise_mul_mut(s.get_row_mut(0), a.get_row_slice(0));
874 mod_op.elwise_neg_mut(s.get_row_mut(0));
875 ntt_op.backward(s.get_row_mut(0));
876
877 // m+e = b - s*a
878 let mut m_plus_e = s;
879 mod_op.elwise_add_mut(m_plus_e.get_row_mut(0), rlwe_ct.get_row_slice(1));
880
881 // difference
882 mod_op.elwise_sub_mut(m_plus_e.get_row_mut(0), encoded_m_ideal.get_row_slice(0));
883
884 let mut max_diff_bits = f64::MIN;
885 m_plus_e.get_row_slice(0).iter().for_each(|v| {
886 let mut v = *v;
887
888 if v >= (q >> 1) {
889 // v is -ve
890 v = q - v;
891 }
892
893 let bits = (v.to_f64().unwrap()).log2();
894
895 if max_diff_bits < bits {
896 max_diff_bits = bits;
897 }
898 });
899
900 return max_diff_bits;
901}
902
903#[cfg(test)]
904mod tests {
905 use std::vec;
906
907 use itertools::{izip, Itertools};
908 use rand::{thread_rng, Rng};
909
910 use crate::{
911 backend::{ModInit, ModularOpsU64},
912 decomposer::{gadget_vector, DefaultDecomposer},
913 ntt::{self, Ntt, NttBackendU64, NttInit},
914 random::{DefaultSecureRng, RandomUniformDist},
915 rgsw::{
916 measure_noise, RgswCiphertextEvaluationDomain, RlweCiphertext, SeededRgswCiphertext,
917 SeededRlweCiphertext,
918 },
919 utils::{generate_prime, negacyclic_mul},
920 Matrix, Secret,
921 };
922
923 use super::{
924 decrypt_rlwe, galois_auto, galois_key_gen, generate_auto_map, rlwe_by_rgsw,
925 secret_key_encrypt_rgsw, secret_key_encrypt_rlwe, RlweSecret,
926 };
927
928 #[test]
929 fn rlwe_encrypt_decryption() {
930 let logq = 50;
931 let logp = 2;
932 let ring_size = 1 << 4;
933 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
934 let p = 1u64 << logp;
935
936 let mut rng = DefaultSecureRng::new();
937
938 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
939
940 // sample m0
941 let mut m0 = vec![0u64; ring_size as usize];
942 RandomUniformDist::<[u64]>::random_fill(&mut rng, &(1u64 << logp), m0.as_mut_slice());
943
944 let ntt_op = NttBackendU64::new(q, ring_size as usize);
945 let mod_op = ModularOpsU64::new(q);
946
947 // encrypt m0
948 let mut rlwe_seed = [0u8; 32];
949 rng.fill_bytes(&mut rlwe_seed);
950 let mut seeded_rlwe_in_ct =
951 SeededRlweCiphertext::<_, [u8; 32]>::empty(ring_size as usize, rlwe_seed, q);
952 let encoded_m = m0
953 .iter()
954 .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
955 .collect_vec();
956 secret_key_encrypt_rlwe(
957 &encoded_m,
958 &mut seeded_rlwe_in_ct.data,
959 s.values(),
960 &mod_op,
961 &ntt_op,
962 seeded_rlwe_in_ct.seed,
963 &mut rng,
964 );
965 let rlwe_in_ct =
966 RlweCiphertext::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_rlwe_in_ct);
967
968 let mut encoded_m_back = vec![0u64; ring_size as usize];
969 decrypt_rlwe(
970 &rlwe_in_ct,
971 s.values(),
972 &mut encoded_m_back,
973 &ntt_op,
974 &mod_op,
975 );
976 let m_back = encoded_m_back
977 .iter()
978 .map(|v| ((*v as f64 * p as f64) / q as f64).round() as u64)
979 .collect_vec();
980 assert_eq!(m0, m_back);
981 }
982
983 #[test]
984 fn rlwe_by_rgsw_works() {
985 let logq = 24;
986 let logp = 2;
987 let ring_size = 1 << 4;
988 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
989 let p = 1u64 << logp;
990 let d_rgsw = 2;
991 let logb = 12;
992
993 let mut rng = DefaultSecureRng::new_seeded([0u8; 32]);
994
995 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
996
997 let mut m0 = vec![0u64; ring_size as usize];
998 RandomUniformDist::<[u64]>::random_fill(&mut rng, &(1u64 << logp), m0.as_mut_slice());
999 let mut m1 = vec![0u64; ring_size as usize];
1000 m1[thread_rng().gen_range(0..ring_size) as usize] = 1;
1001
1002 let ntt_op = NttBackendU64::new(q, ring_size as usize);
1003 let mod_op = ModularOpsU64::new(q);
1004
1005 // Encrypt m1 as RGSW(m1)
1006 let mut rgsw_seed = [0u8; 32];
1007 rng.fill_bytes(&mut rgsw_seed);
1008 let mut seeded_rgsw_ct = SeededRgswCiphertext::<Vec<Vec<u64>>, [u8; 32]>::empty(
1009 ring_size as usize,
1010 d_rgsw,
1011 rgsw_seed,
1012 q,
1013 );
1014 let gadget_vector = gadget_vector(logq, logb, d_rgsw);
1015 secret_key_encrypt_rgsw(
1016 &mut seeded_rgsw_ct.data,
1017 &m1,
1018 &gadget_vector,
1019 s.values(),
1020 &mod_op,
1021 &ntt_op,
1022 seeded_rgsw_ct.seed,
1023 &mut rng,
1024 );
1025 let rgsw_ct = RgswCiphertextEvaluationDomain::<_, DefaultSecureRng, NttBackendU64>::from(
1026 &seeded_rgsw_ct,
1027 );
1028
1029 // Encrypt m0 as RLWE(m0)
1030 let mut rlwe_seed = [0u8; 32];
1031 rng.fill_bytes(&mut rlwe_seed);
1032 let mut seeded_rlwe_in_ct =
1033 SeededRlweCiphertext::<_, [u8; 32]>::empty(ring_size as usize, rlwe_seed, q);
1034 let encoded_m = m0
1035 .iter()
1036 .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
1037 .collect_vec();
1038 secret_key_encrypt_rlwe(
1039 &encoded_m,
1040 &mut seeded_rlwe_in_ct.data,
1041 s.values(),
1042 &mod_op,
1043 &ntt_op,
1044 seeded_rlwe_in_ct.seed,
1045 &mut rng,
1046 );
1047 let mut rlwe_in_ct =
1048 RlweCiphertext::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_rlwe_in_ct);
1049
1050 // RLWE(m0m1) = RLWE(m0) x RGSW(m1)
1051 let mut scratch_space = vec![vec![0u64; ring_size as usize]; d_rgsw + 2];
1052 let decomposer = DefaultDecomposer::new(q, logb, d_rgsw);
1053 rlwe_by_rgsw(
1054 &mut rlwe_in_ct,
1055 &rgsw_ct.data,
1056 &mut scratch_space,
1057 &decomposer,
1058 &ntt_op,
1059 &mod_op,
1060 );
1061
1062 // Decrypt RLWE(m0m1)
1063 let mut encoded_m0m1_back = vec![0u64; ring_size as usize];
1064 decrypt_rlwe(
1065 &rlwe_in_ct,
1066 s.values(),
1067 &mut encoded_m0m1_back,
1068 &ntt_op,
1069 &mod_op,
1070 );
1071 let m0m1_back = encoded_m0m1_back
1072 .iter()
1073 .map(|v| (((*v as f64 * p as f64) / (q as f64)).round() as u64) % p)
1074 .collect_vec();
1075
1076 let mul_mod = |v0: &u64, v1: &u64| (v0 * v1) % p;
1077 let m0m1 = negacyclic_mul(&m0, &m1, mul_mod, p);
1078 assert!(
1079 m0m1 == m0m1_back,
1080 "Expected {:?} \n Got {:?}",
1081 m0m1,
1082 m0m1_back
1083 );
1084 }
1085
1086 // #[test]
1087 // fn galois_auto_works() {
1088 // let logq = 50;
1089 // let ring_size = 1 << 5;
1090 // let q = generate_prime(logq, 2 * ring_size, 1u64 << logq).unwrap();
1091 // let logp = 3;
1092 // let p = 1u64 << logp;
1093 // let d_rgsw = 10;
1094 // let logb = 5;
1095
1096 // let mut rng = DefaultSecureRng::new();
1097 // let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as
1098 // usize);
1099
1100 // let mut m = vec![0u64; ring_size as usize];
1101 // RandomUniformDist::random_fill(&mut rng, &p, m.as_mut_slice());
1102 // let encoded_m = m
1103 // .iter()
1104 // .map(|v| (((*v as f64 * q as f64) / (p as f64)).round() as u64))
1105 // .collect_vec();
1106
1107 // let ntt_op = NttBackendU64::new(q, ring_size as usize);
1108 // let mod_op = ModularOpsU64::new(q);
1109
1110 // // RLWE_{s}(m)
1111 // let mut rlwe_m = vec![vec![0u64; ring_size as usize]; 2];
1112 // secret_key_encrypt_rlwe(
1113 // &vec![encoded_m.clone()],
1114 // &mut rlwe_m,
1115 // &s,
1116 // &mod_op,
1117 // &ntt_op,
1118 // &mut rng,
1119 // );
1120
1121 // let auto_k = -5;
1122
1123 // // Generate galois key to key switch from s^k to s
1124 // let mut ksk_out = vec![vec![0u64; ring_size as usize]; d_rgsw * 2];
1125 // let gadget_vector = gadget_vector(logq, logb, d_rgsw);
1126 // galois_key_gen(
1127 // &mut ksk_out,
1128 // &s,
1129 // auto_k,
1130 // &gadget_vector,
1131 // &mod_op,
1132 // &ntt_op,
1133 // &mut rng,
1134 // );
1135
1136 // // Send RLWE_{s}(m) -> RLWE_{s}(m^k)
1137 // let mut rlwe_m = RlweCiphertext(rlwe_m, false);
1138 // let mut scratch_space = vec![vec![0u64; ring_size as usize]; d_rgsw +
1139 // 2]; let (auto_map_index, auto_map_sign) =
1140 // generate_auto_map(ring_size as usize, auto_k); let decomposer =
1141 // DefaultDecomposer::new(q, logb, d_rgsw); galois_auto(
1142 // &mut rlwe_m,
1143 // &ksk_out,
1144 // &mut scratch_space,
1145 // &auto_map_index,
1146 // &auto_map_sign,
1147 // &mod_op,
1148 // &ntt_op,
1149 // &decomposer,
1150 // );
1151
1152 // let rlwe_m_k = rlwe_m;
1153
1154 // // Decrypt RLWE_{s}(m^k) and check
1155 // let mut encoded_m_k_back = vec![vec![0u64; ring_size as usize]];
1156 // decrypt_rlwe(
1157 // &rlwe_m_k,
1158 // s.values(),
1159 // &mut encoded_m_k_back,
1160 // &ntt_op,
1161 // &mod_op,
1162 // );
1163 // let m_k_back = encoded_m_k_back[0]
1164 // .iter()
1165 // .map(|v| (((*v as f64 * p as f64) / q as f64).round() as u64) %
1166 // p) .collect_vec();
1167
1168 // let mut m_k = vec![0u64; ring_size as usize];
1169 // // Send \delta m -> \delta m^k
1170 // izip!(m.iter(), auto_map_index.iter(),
1171 // auto_map_sign.iter()).for_each( |(v, to_index, sign)| {
1172 // if !*sign {
1173 // m_k[*to_index] = (p - *v) % p;
1174 // } else {
1175 // m_k[*to_index] = *v;
1176 // }
1177 // },
1178 // );
1179
1180 // {
1181 // // let encoded_m_k = m_k
1182 // // .iter()
1183 // // .map(|v| ((*v as f64 * q as f64) / p as f64).round() as
1184 // u64) // .collect_vec();
1185
1186 // // let noise = measure_noise(&rlwe_m_k, &vec![encoded_m_k],
1187 // &ntt_op, // &mod_op, &s); println!("Ksk noise: {noise}");
1188 // }
1189
1190 // // FIXME(Jay): Galios autormophism will incur high error unless we
1191 // fix in // accurate decomoposition of Decomposer when q is prime
1192 // assert_eq!(m_k_back, m_k);
1193 // // dbg!(m_k_back, m_k, q);
1194 // }
1195}