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