phantom-zone/src/rgsw.rs
src/rgsw.rsRaw
1use std::{
2 clone,
3 fmt::Debug,
4 ops::{Neg, Sub},
5};
6
7use itertools::{izip, Itertools};
8use num_traits::{PrimInt, ToPrimitive, Zero};
9
10use crate::{
11 backend::{ArithmeticOps, VectorOps},
12 decomposer::{self, Decomposer},
13 ntt::{self, Ntt},
14 random::{DefaultSecureRng, RandomGaussianDist, RandomUniformDist},
15 utils::{fill_random_ternary_secret_with_hamming_weight, TryConvertFrom, WithLocal},
16 Matrix, MatrixEntity, MatrixMut, RowMut, Secret,
17};
18
19struct RlweCiphertext<M>(M, bool);
20
21impl<M: Matrix> Matrix for RlweCiphertext<M> {
22 type MatElement = M::MatElement;
23 type R = M::R;
24
25 fn dimension(&self) -> (usize, usize) {
26 self.0.dimension()
27 }
28}
29
30impl<M: MatrixMut> MatrixMut for RlweCiphertext<M> where <M as Matrix>::R: RowMut {}
31
32impl<M: Matrix> AsRef<[<M as Matrix>::R]> for RlweCiphertext<M> {
33 fn as_ref(&self) -> &[<M as Matrix>::R] {
34 self.0.as_ref()
35 }
36}
37
38impl<M: MatrixMut> AsMut<[<M as Matrix>::R]> for RlweCiphertext<M>
39where
40 <M as Matrix>::R: RowMut,
41{
42 fn as_mut(&mut self) -> &mut [<M as Matrix>::R] {
43 self.0.as_mut()
44 }
45}
46
47impl<M> IsTrivial for RlweCiphertext<M> {
48 fn is_trivial(&self) -> bool {
49 self.1
50 }
51 fn set_not_trivial(&mut self) {
52 self.1 = false;
53 }
54}
55
56pub trait IsTrivial {
57 fn is_trivial(&self) -> bool;
58 fn set_not_trivial(&mut self);
59}
60
61struct RlweSecret {
62 values: Vec<i32>,
63}
64
65impl Secret for RlweSecret {
66 type Element = i32;
67 fn values(&self) -> &[Self::Element] {
68 &self.values
69 }
70}
71
72impl RlweSecret {
73 fn random(hw: usize, n: usize) -> RlweSecret {
74 DefaultSecureRng::with_local_mut(|rng| {
75 let mut out = vec![0i32; n];
76 fill_random_ternary_secret_with_hamming_weight(&mut out, hw, rng);
77
78 RlweSecret { values: out }
79 })
80 }
81}
82
83fn generate_auto_map(ring_size: usize, k: usize) -> (Vec<usize>, Vec<bool>) {
84 assert!(k & 1 == 1, "Auto {k} must be odd");
85 let (auto_map_index, auto_sign_index): (Vec<usize>, Vec<bool>) = (0..ring_size)
86 .into_iter()
87 .map(|i| {
88 let mut to_index = (i * k) % (2 * ring_size);
89 let mut sign = true;
90
91 // wrap around. false implies negative
92 if to_index >= ring_size {
93 to_index = to_index - ring_size;
94 sign = false;
95 }
96
97 (to_index, sign)
98 })
99 .unzip();
100 (auto_map_index, auto_sign_index)
101}
102
103/// Generates RLWE Key switching key to key switch ciphertext RLWE_{from_s}(m)
104/// to RLWE_{to_s}(m).
105///
106/// Key switching equals
107/// \sum decompose(c_1)_i * RLWE_{to_s}(\beta^i -from_s)
108/// Hence, key switchin key equals RLWE'(-from_s) = RLWE(-from_s), RLWE(beta^1
109/// -from_s), ..., RLWE(beta^{d-1} -from_s).
110///
111/// - ksk_out: Output Key switching key. Key switching key stores RLWE
112/// ciphertexts as [RLWE'_A(-from_s) || RLWE'_B(-from_s)]
113/// - neg_from_s_eval: Negative of secret polynomial to key switch from in
114/// evaluation domain
115/// - to_s_eval: secret polynomial to key switch to in evalution domain.
116pub(crate) fn rlwe_ksk_gen<
117 Mmut: MatrixMut + MatrixEntity,
118 ModOp: ArithmeticOps<Element = Mmut::MatElement> + VectorOps<Element = Mmut::MatElement>,
119 NttOp: Ntt<Element = Mmut::MatElement>,
120 R: RandomGaussianDist<[Mmut::MatElement], Parameters = Mmut::MatElement>
121 + RandomUniformDist<[Mmut::MatElement], Parameters = Mmut::MatElement>,
122>(
123 ksk_out: &mut Mmut,
124 neg_from_s_eval: &Mmut,
125 to_s_eval: &Mmut,
126 gadget_vector: &[Mmut::MatElement],
127 mod_op: &ModOp,
128 ntt_op: &NttOp,
129 rng: &mut R,
130) where
131 <Mmut as Matrix>::R: RowMut,
132{
133 let ring_size = neg_from_s_eval.dimension().1;
134 let d = gadget_vector.len();
135 assert!(neg_from_s_eval.dimension().0 == 1);
136 assert!(ksk_out.dimension() == (d * 2, ring_size));
137 assert!(to_s_eval.dimension() == (1, ring_size));
138
139 let q = ArithmeticOps::modulus(mod_op);
140
141 let mut scratch_space = Mmut::zeros(1, ring_size);
142
143 // RLWE'_{to_s}(-from_s)
144 let (part_a, part_b) = ksk_out.split_at_row_mut(d);
145 izip!(part_a.iter_mut(), part_b.iter_mut(), gadget_vector.iter()).for_each(
146 |(ai, bi, beta_i)| {
147 // sample ai and transform to evaluation
148 RandomUniformDist::random_fill(rng, &q, ai.as_mut());
149 ntt_op.forward(ai.as_mut());
150
151 // to_s * ai
152 mod_op.elwise_mul(
153 scratch_space.get_row_mut(0),
154 ai.as_ref(),
155 to_s_eval.get_row_slice(0),
156 );
157
158 // ei + to_s*ai
159 RandomGaussianDist::random_fill(rng, &q, bi.as_mut());
160 ntt_op.forward(bi.as_mut());
161 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.get_row_slice(0));
162
163 // beta_i * -from_s
164 mod_op.elwise_scalar_mul(
165 scratch_space.get_row_mut(0),
166 neg_from_s_eval.get_row_slice(0),
167 beta_i,
168 );
169
170 // bi = ei + to_s*ai + beta_i*-from_s
171 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.get_row_slice(0));
172 },
173 );
174}
175
176pub(crate) fn galois_key_gen<
177 Mmut: MatrixMut + MatrixEntity,
178 ModOp: ArithmeticOps<Element = Mmut::MatElement> + VectorOps<Element = Mmut::MatElement>,
179 NttOp: Ntt<Element = Mmut::MatElement>,
180 S: Secret,
181 R: RandomGaussianDist<[Mmut::MatElement], Parameters = Mmut::MatElement>
182 + RandomUniformDist<[Mmut::MatElement], Parameters = Mmut::MatElement>,
183>(
184 ksk_out: &mut Mmut,
185 s: &S,
186 auto_k: usize,
187 gadget_vector: &[Mmut::MatElement],
188 mod_op: &ModOp,
189 ntt_op: &NttOp,
190 rng: &mut R,
191) where
192 <Mmut as Matrix>::R: RowMut,
193 Mmut: TryConvertFrom<[S::Element], Parameters = Mmut::MatElement>,
194 Mmut::MatElement: Copy + Sub<Output = Mmut::MatElement>,
195{
196 let ring_size = s.values().len();
197 let (auto_map_index, auto_map_sign) = generate_auto_map(ring_size, auto_k);
198
199 let q = ArithmeticOps::modulus(mod_op);
200
201 // s(X) -> -s(X^k)
202 let mut s = Mmut::try_convert_from(s.values(), &q);
203 let mut neg_s_auto = Mmut::zeros(1, s.dimension().1);
204 izip!(s.get_row(0), auto_map_index.iter(), auto_map_sign.iter()).for_each(
205 |(el, to_index, sign)| {
206 // if sign is +ve (true), then negate because we need -s(X) (i.e. do the
207 // opposite than the usual case)
208 if *sign {
209 neg_s_auto.set(0, *to_index, q - *el)
210 } else {
211 neg_s_auto.set(0, *to_index, *el)
212 }
213 },
214 );
215
216 // send both s(X) and -s(X^k) to evaluation domain
217 ntt_op.forward(s.get_row_mut(0));
218 ntt_op.forward(neg_s_auto.get_row_mut(0));
219
220 // Ksk from -s(X^k) to s(X)
221 rlwe_ksk_gen(ksk_out, &neg_s_auto, &s, gadget_vector, mod_op, ntt_op, rng);
222}
223
224/// Sends RLWE_{s}(X) -> RLWE_{s}(X^k) where k is some galois element
225pub(crate) fn galois_auto<
226 MT: Matrix + IsTrivial + MatrixMut,
227 Mmut: MatrixMut<MatElement = MT::MatElement>,
228 ModOp: ArithmeticOps<Element = MT::MatElement> + VectorOps<Element = MT::MatElement>,
229 NttOp: Ntt<Element = MT::MatElement>,
230 D: Decomposer<Element = MT::MatElement>,
231>(
232 rlwe_in: &mut MT,
233 ksk: &Mmut,
234 scratch_matrix_dplus2_ring: &mut Mmut,
235 auto_map_index: &[usize],
236 auto_map_sign: &[bool],
237 mod_op: &ModOp,
238 ntt_op: &NttOp,
239 decomposer: &D,
240) where
241 <Mmut as Matrix>::R: RowMut,
242 <MT as Matrix>::R: RowMut,
243 MT::MatElement: Copy + Zero,
244{
245 let d = decomposer.d();
246
247 let (scratch_matrix_d_ring, tmp_rlwe_out) = scratch_matrix_dplus2_ring.split_at_row_mut(d);
248
249 // send b(X) -> b(X^k)
250 izip!(
251 rlwe_in.get_row(1),
252 auto_map_index.iter(),
253 auto_map_sign.iter()
254 )
255 .for_each(|(el_in, to_index, sign)| {
256 if !*sign {
257 tmp_rlwe_out[1].as_mut()[*to_index] = mod_op.neg(el_in);
258 } else {
259 tmp_rlwe_out[1].as_mut()[*to_index] = *el_in;
260 // scratch_matrix_dplus2_ring.set(d + 1, *to_index, *el_in);
261 }
262 });
263
264 if !rlwe_in.is_trivial() {
265 // send a(X) -> a(X^k) and decompose a(X^k)
266 izip!(
267 rlwe_in.get_row(0),
268 auto_map_index.iter(),
269 auto_map_sign.iter()
270 )
271 .for_each(|(el_in, to_index, sign)| {
272 let el_out = if !*sign { mod_op.neg(el_in) } else { *el_in };
273
274 let el_out_decomposed = decomposer.decompose(&el_out);
275 for j in 0..d {
276 scratch_matrix_d_ring[j].as_mut()[*to_index] = el_out_decomposed[j];
277 }
278 });
279
280 // transform decomposed a(X^k) to evaluation domain
281 scratch_matrix_d_ring.iter_mut().for_each(|r| {
282 ntt_op.forward(r.as_mut());
283 });
284
285 // RLWE(m^k) = a', b'; RLWE(m) = a, b
286 // key switch: (a * RLWE'(s(X^k)))
287 let (ksk_a, ksk_b) = ksk.split_at_row(d);
288 tmp_rlwe_out[0].as_mut().fill(Mmut::MatElement::zero());
289 // a' = decomp<a> * RLWE'_A(s(X^k))
290 routine::<Mmut, ModOp>(
291 tmp_rlwe_out[0].as_mut(),
292 scratch_matrix_d_ring,
293 ksk_a,
294 mod_op,
295 );
296 // send b(X^k) to evaluation domain
297 ntt_op.forward(tmp_rlwe_out[1].as_mut());
298 // b' = b(X^k)
299 // b' += decomp<a(X^k)> * RLWE'_B(s(X^k))
300 routine::<Mmut, ModOp>(
301 tmp_rlwe_out[1].as_mut(),
302 scratch_matrix_d_ring,
303 ksk_b,
304 mod_op,
305 );
306
307 // transform RLWE(m^k) to coefficient domain
308 tmp_rlwe_out
309 .iter_mut()
310 .for_each(|r| ntt_op.backward(r.as_mut()));
311
312 rlwe_in
313 .get_row_mut(0)
314 .copy_from_slice(tmp_rlwe_out[0].as_ref());
315 }
316
317 rlwe_in
318 .get_row_mut(1)
319 .copy_from_slice(tmp_rlwe_out[1].as_ref());
320}
321
322/// Encrypts message m as a RGSW ciphertext.
323///
324/// - m_eval: is `m` is evaluation domain
325/// - out_rgsw: RGSW(m) is stored as single matrix of dimension (d_rgsw * 4,
326/// ring_size). The matrix has the following structure [RLWE'_A(-sm) ||
327/// RLWE'_B(-sm) || RLWE'_A(m) || RLWE'_B(m)]^T
328pub(crate) fn encrypt_rgsw<
329 Mmut: MatrixMut + MatrixEntity,
330 M: Matrix<MatElement = Mmut::MatElement> + Clone,
331 S: Secret,
332 R: RandomGaussianDist<[Mmut::MatElement], Parameters = Mmut::MatElement>
333 + RandomUniformDist<[Mmut::MatElement], Parameters = Mmut::MatElement>,
334 ModOp: VectorOps<Element = Mmut::MatElement>,
335 NttOp: Ntt<Element = Mmut::MatElement>,
336>(
337 out_rgsw: &mut Mmut,
338 m_eval: &M,
339 gadget_vector: &[Mmut::MatElement],
340 s: &S,
341 mod_op: &ModOp,
342 ntt_op: &NttOp,
343 rng: &mut R,
344) where
345 <Mmut as Matrix>::R: RowMut,
346 Mmut: TryConvertFrom<[S::Element], Parameters = Mmut::MatElement>,
347{
348 let d = gadget_vector.len();
349 let q = mod_op.modulus();
350 let ring_size = s.values().len();
351 assert!(out_rgsw.dimension() == (d * 4, ring_size));
352 assert!(m_eval.dimension() == (1, ring_size));
353
354 // RLWE(-sm), RLWE(-sm)
355 let (rlwe_dash_nsm, rlwe_dash_m) = out_rgsw.split_at_row_mut(d * 2);
356
357 let mut s_eval = Mmut::try_convert_from(s.values(), &q);
358 ntt_op.forward(s_eval.get_row_mut(0).as_mut());
359
360 let mut scratch_space = Mmut::zeros(1, ring_size);
361
362 // RLWE'(-sm)
363 let (a_rlwe_dash_nsm, b_rlwe_dash_nsm) = rlwe_dash_nsm.split_at_mut(d);
364 izip!(
365 a_rlwe_dash_nsm.iter_mut(),
366 b_rlwe_dash_nsm.iter_mut(),
367 gadget_vector.iter()
368 )
369 .for_each(|(ai, bi, beta_i)| {
370 // Sample a_i and transform to evaluation domain
371 RandomUniformDist::random_fill(rng, &q, ai.as_mut());
372 ntt_op.forward(ai.as_mut());
373
374 // a_i * s
375 mod_op.elwise_mul(
376 scratch_space.get_row_mut(0),
377 ai.as_ref(),
378 s_eval.get_row_slice(0),
379 );
380 // b_i = e_i + a_i * s
381 RandomGaussianDist::random_fill(rng, &q, bi.as_mut());
382 ntt_op.forward(bi.as_mut());
383 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.get_row_slice(0));
384
385 // a_i + \beta_i * m
386 mod_op.elwise_scalar_mul(
387 scratch_space.get_row_mut(0),
388 m_eval.get_row_slice(0),
389 beta_i,
390 );
391 mod_op.elwise_add_mut(ai.as_mut(), scratch_space.get_row_slice(0));
392 });
393
394 // RLWE(m)
395 let (a_rlwe_dash_m, b_rlwe_dash_m) = rlwe_dash_m.split_at_mut(d);
396 izip!(
397 a_rlwe_dash_m.iter_mut(),
398 b_rlwe_dash_m.iter_mut(),
399 gadget_vector.iter()
400 )
401 .for_each(|(ai, bi, beta_i)| {
402 // Sample e_i and transform to evaluation domain
403 RandomGaussianDist::random_fill(rng, &q, bi.as_mut());
404 ntt_op.forward(bi.as_mut());
405
406 // beta_i * m
407 mod_op.elwise_scalar_mul(
408 scratch_space.get_row_mut(0),
409 m_eval.get_row_slice(0),
410 beta_i,
411 );
412 // e_i + beta_i * m
413 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.get_row_slice(0));
414
415 // Sample a_i and transform to evaluation domain
416 RandomUniformDist::random_fill(rng, &q, ai.as_mut());
417 ntt_op.forward(ai.as_mut());
418
419 // ai * s
420 mod_op.elwise_mul(
421 scratch_space.get_row_mut(0),
422 ai.as_ref(),
423 s_eval.get_row_slice(0),
424 );
425
426 // b_i = a_i*s + e_i + beta_i*m
427 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.get_row_slice(0));
428 });
429}
430
431/// Returns RLWE(mm') = RLWE(m) x RGSW(m')
432///
433/// - rgsw_in: RGSW(m') in evaluation domain
434/// - rlwe_in_decomposed: decomposed RLWE(m) in evaluation domain
435/// - rlwe_out: returned RLWE(mm') in evaluation domain
436pub(crate) fn rlwe_in_decomposed_evaluation_domain_mul_rgsw_rlwe_out_evaluation_domain<
437 Mmut: MatrixMut + MatrixEntity,
438 M: Matrix<MatElement = Mmut::MatElement> + Clone,
439 ModOp: VectorOps<Element = Mmut::MatElement>,
440>(
441 rgsw_in: &M,
442 rlwe_in_decomposed_eval: &Mmut,
443 rlwe_out_eval: &mut Mmut,
444 mod_op: &ModOp,
445) where
446 <Mmut as Matrix>::R: RowMut,
447{
448 let ring_size = rgsw_in.dimension().1;
449 let d_rgsw = rgsw_in.dimension().0 / 4;
450 assert!(rlwe_in_decomposed_eval.dimension() == (2 * d_rgsw, ring_size));
451 assert!(rlwe_out_eval.dimension() == (2, ring_size));
452
453 let (a_rlwe_out, b_rlwe_out) = rlwe_out_eval.split_at_row_mut(1);
454
455 // a * RLWE'(-sm)
456 let a_rlwe_dash_nsm = rgsw_in.iter_rows().take(d_rgsw);
457 let b_rlwe_dash_nsm = rgsw_in.iter_rows().skip(d_rgsw).take(d_rgsw);
458 izip!(
459 rlwe_in_decomposed_eval.iter_rows().take(d_rgsw),
460 a_rlwe_dash_nsm
461 )
462 .for_each(|(a, b)| {
463 mod_op.elwise_fma_mut(a_rlwe_out[0].as_mut(), a.as_ref(), b.as_ref());
464 });
465 izip!(
466 rlwe_in_decomposed_eval.iter_rows().take(d_rgsw),
467 b_rlwe_dash_nsm
468 )
469 .for_each(|(a, b)| {
470 mod_op.elwise_fma_mut(b_rlwe_out[0].as_mut(), a.as_ref(), b.as_ref());
471 });
472
473 // b * RLWE'(m)
474 let a_rlwe_dash_m = rgsw_in.iter_rows().skip(d_rgsw * 2).take(d_rgsw);
475 let b_rlwe_dash_m = rgsw_in.iter_rows().skip(d_rgsw * 3);
476 izip!(
477 rlwe_in_decomposed_eval.iter_rows().skip(d_rgsw),
478 a_rlwe_dash_m
479 )
480 .for_each(|(a, b)| {
481 mod_op.elwise_fma_mut(a_rlwe_out[0].as_mut(), a.as_ref(), b.as_ref());
482 });
483 izip!(
484 rlwe_in_decomposed_eval.iter_rows().skip(d_rgsw),
485 b_rlwe_dash_m
486 )
487 .for_each(|(a, b)| {
488 mod_op.elwise_fma_mut(b_rlwe_out[0].as_mut(), a.as_ref(), b.as_ref());
489 });
490}
491
492pub(crate) fn routine<M: Matrix + ?Sized, ModOp: VectorOps<Element = M::MatElement>>(
493 write_to_row: &mut [M::MatElement],
494 matrix_a: &[M::R],
495 matrix_b: &[M::R],
496 mod_op: &ModOp,
497) {
498 izip!(matrix_a.iter(), matrix_b.iter()).for_each(|(a, b)| {
499 mod_op.elwise_fma_mut(write_to_row, a.as_ref(), b.as_ref());
500 });
501}
502
503// pub(crate) fn decompose_rlwe<
504// M: Matrix + Clone,
505// Mmut: MatrixMut<MatElement = M::MatElement> + MatrixEntity,
506// D: Decomposer<Element = M::MatElement>,
507// >(
508// rlwe_in: &M,
509// decomposer: &D,
510// rlwe_in_decomposed: &mut Mmut,
511// ) where
512// M::MatElement: Copy,
513// <Mmut as Matrix>::R: RowMut,
514// {
515// let d_rgsw = decomposer.d();
516// let ring_size = rlwe_in.dimension().1;
517// assert!(rlwe_in_decomposed.dimension() == (2 * d_rgsw, ring_size));
518
519// // Decompose rlwe_in
520// for ri in 0..ring_size {
521// // ai
522// let ai_decomposed = decomposer.decompose(rlwe_in.get(0, ri));
523// for j in 0..d_rgsw {
524// rlwe_in_decomposed.set(j, ri, ai_decomposed[j]);
525// }
526
527// // bi
528// let bi_decomposed = decomposer.decompose(rlwe_in.get(1, ri));
529// for j in 0..d_rgsw {
530// rlwe_in_decomposed.set(j + d_rgsw, ri, bi_decomposed[j]);
531// }
532// }
533// }
534
535/// Decomposes ring polynomial r(X) into d polynomials using decomposer into
536/// output matrix decomp_r
537///
538/// Note that decomposition of r(X) requires decomposition of each of
539/// coefficients.
540///
541/// - decomp_r: must have dimensions d x ring_size. i^th decomposed polynomial
542/// will be stored at i^th row.
543pub(crate) fn decompose_r<M: Matrix + MatrixMut, D: Decomposer<Element = M::MatElement>>(
544 r: &[M::MatElement],
545 decomp_r: &mut [M::R],
546 decomposer: &D,
547) where
548 <M as Matrix>::R: RowMut,
549 M::MatElement: Copy,
550{
551 let ring_size = r.len();
552 let d = decomposer.d();
553
554 for ri in 0..ring_size {
555 let el_decomposed = decomposer.decompose(&r[ri]);
556 for j in 0..d {
557 decomp_r[j].as_mut()[ri] = el_decomposed[j];
558 }
559 }
560}
561
562/// Returns RLWE(m0m1) = RLWE(m0) x RGSW(m1). Mutates rlwe_in inplace to equal
563/// RLWE(m0m1)
564///
565/// - rlwe_in: is RLWE(m0) with polynomials in coefficient domain
566/// - rgsw_in: is RGSW(m1) with polynomials in evaluation domain
567/// - scratch_matrix_d_ring: is a matrix of dimension (d_rgsw, ring_size) used
568/// as scratch space to store decomposed Ring elements temporarily
569pub(crate) fn rlwe_by_rgsw<
570 Mmut: MatrixMut,
571 MT: Matrix<MatElement = Mmut::MatElement> + MatrixMut<MatElement = Mmut::MatElement> + IsTrivial,
572 D: Decomposer<Element = Mmut::MatElement>,
573 ModOp: VectorOps<Element = Mmut::MatElement>,
574 NttOp: Ntt<Element = Mmut::MatElement>,
575>(
576 rlwe_in: &mut MT,
577 rgsw_in: &Mmut,
578 scratch_matrix_dplus2_ring: &mut Mmut,
579 decomposer: &D,
580 ntt_op: &NttOp,
581 mod_op: &ModOp,
582) where
583 Mmut::MatElement: Copy + Zero,
584 <Mmut as Matrix>::R: RowMut,
585 <MT as Matrix>::R: RowMut,
586{
587 let d_rgsw = decomposer.d();
588 assert!(scratch_matrix_dplus2_ring.dimension() == (d_rgsw + 2, 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/// Encrypt polynomial m(X) as RLWE ciphertext.
654///
655/// - rlwe_out: returned RLWE ciphertext RLWE(m) in coefficient domain. RLWE
656/// ciphertext is a matirx with first row consiting polynomial `a` and the
657/// second rows consting polynomial `b`
658pub(crate) fn encrypt_rlwe<
659 Mmut: Matrix + MatrixMut + Clone,
660 ModOp: VectorOps<Element = Mmut::MatElement>,
661 NttOp: Ntt<Element = Mmut::MatElement>,
662 S: Secret,
663 R: RandomUniformDist<[Mmut::MatElement], Parameters = Mmut::MatElement>
664 + RandomGaussianDist<[Mmut::MatElement], Parameters = Mmut::MatElement>,
665>(
666 m: &Mmut,
667 rlwe_out: &mut Mmut,
668 s: &S,
669 mod_op: &ModOp,
670 ntt_op: &NttOp,
671 rng: &mut R,
672) where
673 <Mmut as Matrix>::R: RowMut,
674 Mmut: TryConvertFrom<[S::Element], Parameters = Mmut::MatElement>,
675{
676 let ring_size = s.values().len();
677 assert!(rlwe_out.dimension() == (2, ring_size));
678 assert!(m.dimension() == (1, ring_size));
679
680 let q = mod_op.modulus();
681
682 // sample a
683 RandomUniformDist::random_fill(rng, &q, rlwe_out.get_row_mut(0));
684
685 // s * a
686 let mut sa = Mmut::try_convert_from(s.values(), &q);
687 ntt_op.forward(sa.get_row_mut(0));
688 ntt_op.forward(rlwe_out.get_row_mut(0));
689 mod_op.elwise_mul_mut(sa.get_row_mut(0), rlwe_out.get_row_slice(0));
690 ntt_op.backward(rlwe_out.get_row_mut(0));
691 ntt_op.backward(sa.get_row_mut(0));
692
693 // sample e
694 RandomGaussianDist::random_fill(rng, &q, rlwe_out.get_row_mut(1));
695 mod_op.elwise_add_mut(rlwe_out.get_row_mut(1), m.get_row_slice(0));
696 mod_op.elwise_add_mut(rlwe_out.get_row_mut(1), sa.get_row_slice(0));
697}
698
699/// Decrypts degree 1 RLWE ciphertext RLWE(m) and returns m
700///
701/// - rlwe_ct: input degree 1 ciphertext RLWE(m).
702pub(crate) fn decrypt_rlwe<
703 Mmut: MatrixMut + Clone,
704 M: Matrix<MatElement = Mmut::MatElement>,
705 ModOp: VectorOps<Element = Mmut::MatElement>,
706 NttOp: Ntt<Element = Mmut::MatElement>,
707 S: Secret,
708>(
709 rlwe_ct: &M,
710 s: &S,
711 m_out: &mut Mmut,
712 ntt_op: &NttOp,
713 mod_op: &ModOp,
714) where
715 <Mmut as Matrix>::R: RowMut,
716 Mmut: TryConvertFrom<[S::Element], Parameters = Mmut::MatElement>,
717 Mmut::MatElement: Copy,
718{
719 let ring_size = s.values().len();
720 assert!(rlwe_ct.dimension() == (2, ring_size));
721 assert!(m_out.dimension() == (1, ring_size));
722
723 // transform a to evluation form
724 m_out
725 .get_row_mut(0)
726 .copy_from_slice(rlwe_ct.get_row_slice(0));
727 ntt_op.forward(m_out.get_row_mut(0));
728
729 // -s*a
730 let mut s = Mmut::try_convert_from(&s.values(), &mod_op.modulus());
731 ntt_op.forward(s.get_row_mut(0));
732 mod_op.elwise_mul_mut(m_out.get_row_mut(0), s.get_row_slice(0));
733 mod_op.elwise_neg_mut(m_out.get_row_mut(0));
734 ntt_op.backward(m_out.get_row_mut(0));
735
736 // m+e = b - s*a
737 mod_op.elwise_add_mut(m_out.get_row_mut(0), rlwe_ct.get_row_slice(1));
738}
739
740// Measures noise in degree 1 RLWE ciphertext against encoded ideal message
741// encoded_m
742pub(crate) fn measure_noise<
743 Mmut: MatrixMut + Matrix + MatrixEntity,
744 ModOp: VectorOps<Element = Mmut::MatElement>,
745 NttOp: Ntt<Element = Mmut::MatElement>,
746 S: Secret,
747>(
748 rlwe_ct: &Mmut,
749 encoded_m_ideal: &Mmut,
750 ntt_op: &NttOp,
751 mod_op: &ModOp,
752 s: &S,
753) -> f64
754where
755 <Mmut as Matrix>::R: RowMut,
756 Mmut: TryConvertFrom<[S::Element], Parameters = Mmut::MatElement>,
757 Mmut::MatElement: PrimInt + ToPrimitive + Debug,
758{
759 let ring_size = s.values().len();
760 assert!(rlwe_ct.dimension() == (2, ring_size));
761 assert!(encoded_m_ideal.dimension() == (1, ring_size));
762
763 // -(s * a)
764 let q = VectorOps::modulus(mod_op);
765 let mut s = Mmut::try_convert_from(s.values(), &q);
766 ntt_op.forward(s.get_row_mut(0));
767 let mut a = Mmut::zeros(1, ring_size);
768 a.get_row_mut(0).copy_from_slice(rlwe_ct.get_row_slice(0));
769 ntt_op.forward(a.get_row_mut(0));
770 mod_op.elwise_mul_mut(s.get_row_mut(0), a.get_row_slice(0));
771 mod_op.elwise_neg_mut(s.get_row_mut(0));
772 ntt_op.backward(s.get_row_mut(0));
773
774 // m+e = b - s*a
775 let mut m_plus_e = s;
776 mod_op.elwise_add_mut(m_plus_e.get_row_mut(0), rlwe_ct.get_row_slice(1));
777
778 // difference
779 mod_op.elwise_sub_mut(m_plus_e.get_row_mut(0), encoded_m_ideal.get_row_slice(0));
780
781 let mut max_diff_bits = f64::MIN;
782 m_plus_e.get_row_slice(0).iter().for_each(|v| {
783 let mut v = *v;
784
785 if v >= (q >> 1) {
786 // v is -ve
787 v = q - v;
788 }
789
790 let bits = (v.to_f64().unwrap()).log2();
791
792 if max_diff_bits < bits {
793 max_diff_bits = bits;
794 }
795 });
796
797 return max_diff_bits;
798}
799
800#[cfg(test)]
801mod tests {
802 use std::vec;
803
804 use itertools::{izip, Itertools};
805 use rand::{thread_rng, Rng};
806
807 use crate::{
808 backend::ModularOpsU64,
809 decomposer::{gadget_vector, DefaultDecomposer},
810 ntt::{self, Ntt, NttBackendU64},
811 random::{DefaultSecureRng, RandomUniformDist},
812 rgsw::{measure_noise, RlweCiphertext},
813 utils::{generate_prime, negacyclic_mul},
814 Matrix,
815 };
816
817 use super::{
818 decrypt_rlwe, encrypt_rgsw, encrypt_rlwe, galois_auto, galois_key_gen, generate_auto_map,
819 rlwe_by_rgsw, RlweSecret,
820 };
821
822 #[test]
823 fn rlwe_by_rgsw_works() {
824 let logq = 50;
825 let logp = 3;
826 let ring_size = 1 << 10;
827 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
828 let p = 1u64 << logp;
829 let d_rgsw = 10;
830 let logb = 5;
831
832 let mut rng = DefaultSecureRng::new();
833
834 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
835
836 let mut m0 = vec![0u64; ring_size as usize];
837 RandomUniformDist::<[u64]>::random_fill(&mut rng, &(1u64 << logp), m0.as_mut_slice());
838 let mut m1 = vec![0u64; ring_size as usize];
839 m1[thread_rng().gen_range(0..ring_size) as usize] = 1;
840
841 let ntt_op = NttBackendU64::new(q, ring_size as usize);
842 let mod_op = ModularOpsU64::new(q);
843
844 // Encrypt m1 as RGSW(m1)
845 let mut rgsw_ct = vec![vec![0u64; ring_size as usize]; d_rgsw * 4];
846 let gadget_vector = gadget_vector(logq, logb, d_rgsw);
847 let mut m1_eval = m1.clone();
848 ntt_op.forward(&mut m1_eval);
849 encrypt_rgsw(
850 &mut rgsw_ct,
851 &vec![m1_eval],
852 &gadget_vector,
853 &s,
854 &mod_op,
855 &ntt_op,
856 &mut rng,
857 );
858 // println!("RGSW(m1): {:?}", &rgsw_ct);
859
860 // Encrypt m0 as RLWE(m0)
861 let mut rlwe_in_ct = vec![vec![0u64; ring_size as usize]; 2];
862 let encoded_m = m0
863 .iter()
864 .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
865 .collect_vec();
866 encrypt_rlwe(
867 &vec![encoded_m.clone()],
868 &mut rlwe_in_ct,
869 &s,
870 &mod_op,
871 &ntt_op,
872 &mut rng,
873 );
874 let mut rlwe_in_ct = RlweCiphertext(rlwe_in_ct, false);
875
876 // RLWE(m0m1) = RLWE(m0) x RGSW(m1)
877 let mut scratch_space = vec![vec![0u64; ring_size as usize]; d_rgsw + 2];
878 let decomposer = DefaultDecomposer::new(q, logb, d_rgsw);
879 rlwe_by_rgsw(
880 &mut rlwe_in_ct,
881 &rgsw_ct,
882 &mut scratch_space,
883 &decomposer,
884 &ntt_op,
885 &mod_op,
886 );
887
888 // Decrypt RLWE(m0m1)
889 let mut encoded_m0m1_back = vec![vec![0u64; ring_size as usize]];
890 decrypt_rlwe(&rlwe_in_ct, &s, &mut encoded_m0m1_back, &ntt_op, &mod_op);
891 let m0m1_back = encoded_m0m1_back[0]
892 .iter()
893 .map(|v| (((*v as f64 * p as f64) / (q as f64)).round() as u64) % p)
894 .collect_vec();
895
896 let mul_mod = |v0: &u64, v1: &u64| (v0 * v1) % p;
897 let m0m1 = negacyclic_mul(&m0, &m1, mul_mod, p);
898 assert_eq!(m0m1, m0m1_back, "Expected {:?} got {:?}", m0m1, m0m1_back);
899 // dbg!(&m0m1_back, m0m1, q);
900 }
901
902 #[test]
903 fn galois_auto_works() {
904 let logq = 50;
905 let ring_size = 1 << 5;
906 let q = generate_prime(logq, 2 * ring_size, 1u64 << logq).unwrap();
907 let logp = 3;
908 let p = 1u64 << logp;
909 let d_rgsw = 10;
910 let logb = 5;
911
912 let mut rng = DefaultSecureRng::new();
913 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
914
915 let mut m = vec![0u64; ring_size as usize];
916 RandomUniformDist::random_fill(&mut rng, &p, m.as_mut_slice());
917 let encoded_m = m
918 .iter()
919 .map(|v| (((*v as f64 * q as f64) / (p as f64)).round() as u64))
920 .collect_vec();
921
922 let ntt_op = NttBackendU64::new(q, ring_size as usize);
923 let mod_op = ModularOpsU64::new(q);
924
925 // RLWE_{s}(m)
926 let mut rlwe_m = vec![vec![0u64; ring_size as usize]; 2];
927 encrypt_rlwe(
928 &vec![encoded_m.clone()],
929 &mut rlwe_m,
930 &s,
931 &mod_op,
932 &ntt_op,
933 &mut rng,
934 );
935
936 let auto_k = 25;
937
938 // Generate galois key to key switch from s^k to s
939 let mut ksk_out = vec![vec![0u64; ring_size as usize]; d_rgsw * 2];
940 let gadget_vector = gadget_vector(logq, logb, d_rgsw);
941 galois_key_gen(
942 &mut ksk_out,
943 &s,
944 auto_k,
945 &gadget_vector,
946 &mod_op,
947 &ntt_op,
948 &mut rng,
949 );
950
951 // Send RLWE_{s}(m) -> RLWE_{s}(m^k)
952 let mut rlwe_m = RlweCiphertext(rlwe_m, false);
953 let mut scratch_space = vec![vec![0u64; ring_size as usize]; d_rgsw + 2];
954 let (auto_map_index, auto_map_sign) = generate_auto_map(ring_size as usize, auto_k);
955 let decomposer = DefaultDecomposer::new(q, logb, d_rgsw);
956 galois_auto(
957 &mut rlwe_m,
958 &ksk_out,
959 &mut scratch_space,
960 &auto_map_index,
961 &auto_map_sign,
962 &mod_op,
963 &ntt_op,
964 &decomposer,
965 );
966
967 let rlwe_m_k = rlwe_m;
968
969 // Decrypt RLWE_{s}(m^k) and check
970 let mut encoded_m_k_back = vec![vec![0u64; ring_size as usize]];
971 decrypt_rlwe(&rlwe_m_k, &s, &mut encoded_m_k_back, &ntt_op, &mod_op);
972 let m_k_back = encoded_m_k_back[0]
973 .iter()
974 .map(|v| (((*v as f64 * p as f64) / q as f64).round() as u64) % p)
975 .collect_vec();
976
977 let mut m_k = vec![0u64; ring_size as usize];
978 // Send \delta m -> \delta m^k
979 izip!(m.iter(), auto_map_index.iter(), auto_map_sign.iter()).for_each(
980 |(v, to_index, sign)| {
981 if !*sign {
982 m_k[*to_index] = (p - *v) % p;
983 } else {
984 m_k[*to_index] = *v;
985 }
986 },
987 );
988
989 {
990 // let encoded_m_k = m_k
991 // .iter()
992 // .map(|v| ((*v as f64 * q as f64) / p as f64).round() as u64)
993 // .collect_vec();
994
995 // let noise = measure_noise(&rlwe_m_k, &vec![encoded_m_k], &ntt_op,
996 // &mod_op, &s); println!("Ksk noise: {noise}");
997 }
998
999 // FIXME(Jay): Galios autormophism will incur high error unless we fix in
1000 // accurate decomoposition of Decomposer when q is prime
1001 assert_eq!(m_k_back, m_k);
1002 // dbg!(m_k_back, m_k, q);
1003 }
1004}