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