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