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