phantom-zone/src/rgsw/mod.rs
src/rgsw/mod.rsRaw
1mod keygen;
2mod runtime;
3
4pub(crate) use keygen::*;
5pub(crate) use runtime::*;
6
7#[cfg(test)]
8pub(crate) mod tests {
9 use std::{fmt::Debug, marker::PhantomData, vec};
10
11 use itertools::{izip, Itertools};
12 use rand::{thread_rng, Rng};
13
14 use crate::{
15 backend::{GetModulus, ModInit, ModularOpsU64, Modulus, VectorOps},
16 decomposer::{Decomposer, DefaultDecomposer, RlweDecomposer},
17 ntt::{Ntt, NttBackendU64, NttInit},
18 random::{DefaultSecureRng, NewWithSeed, RandomFillUniformInModulus},
19 rgsw::{
20 rlwe_auto_scratch_rows, rlwe_auto_shoup, rlwe_by_rgsw_shoup, rlwe_x_rgsw_scratch_rows,
21 RgswCiphertextRef, RlweCiphertextMutRef, RlweKskRef, RuntimeScratchMutRef,
22 },
23 utils::{
24 fill_random_ternary_secret_with_hamming_weight, generate_prime, negacyclic_mul,
25 tests::Stats, ToShoup, TryConvertFrom1, WithLocal,
26 },
27 Matrix, MatrixEntity, MatrixMut, Row, RowEntity, RowMut,
28 };
29
30 use super::{
31 keygen::{
32 decrypt_rlwe, generate_auto_map, rlwe_public_key, secret_key_encrypt_rgsw,
33 seeded_auto_key_gen, seeded_secret_key_encrypt_rlwe,
34 },
35 rgsw_x_rgsw_scratch_rows,
36 runtime::{rgsw_by_rgsw_inplace, rlwe_auto, rlwe_by_rgsw},
37 RgswCiphertextMutRef,
38 };
39
40 struct SeededAutoKey<M, S, Mod>
41 where
42 M: Matrix,
43 {
44 data: M,
45 seed: S,
46 modulus: Mod,
47 }
48
49 impl<M: Matrix + MatrixEntity, S, Mod: Modulus<Element = M::MatElement>> SeededAutoKey<M, S, Mod> {
50 fn empty<D: Decomposer>(
51 ring_size: usize,
52 auto_decomposer: &D,
53 seed: S,
54 modulus: Mod,
55 ) -> Self {
56 SeededAutoKey {
57 data: M::zeros(auto_decomposer.decomposition_count().0, ring_size),
58 seed,
59 modulus,
60 }
61 }
62 }
63
64 struct AutoKeyEvaluationDomain<M: Matrix, R, N> {
65 data: M,
66 _phantom: PhantomData<(R, N)>,
67 }
68
69 impl<
70 M: MatrixMut + MatrixEntity,
71 Mod: Modulus<Element = M::MatElement> + Clone,
72 R: RandomFillUniformInModulus<[M::MatElement], Mod> + NewWithSeed,
73 N: NttInit<Mod> + Ntt<Element = M::MatElement>,
74 > From<&SeededAutoKey<M, R::Seed, Mod>> for AutoKeyEvaluationDomain<M, R, N>
75 where
76 <M as Matrix>::R: RowMut,
77 M::MatElement: Copy,
78
79 R::Seed: Clone,
80 {
81 fn from(value: &SeededAutoKey<M, R::Seed, Mod>) -> Self {
82 let (d, ring_size) = value.data.dimension();
83 let mut data = M::zeros(2 * d, ring_size);
84
85 // sample RLWE'_A(-s(X^k))
86 let mut p_rng = R::new_with_seed(value.seed.clone());
87 data.iter_rows_mut().take(d).for_each(|r| {
88 RandomFillUniformInModulus::random_fill(&mut p_rng, &value.modulus, r.as_mut());
89 });
90
91 // copy over RLWE'_B(-s(X^k))
92 izip!(data.iter_rows_mut().skip(d), value.data.iter_rows()).for_each(
93 |(to_r, from_r)| {
94 to_r.as_mut().copy_from_slice(from_r.as_ref());
95 },
96 );
97
98 // send RLWE'(-s(X^k)) polynomials to evaluation domain
99 let ntt_op = N::new(&value.modulus, ring_size);
100 data.iter_rows_mut()
101 .for_each(|r| ntt_op.forward(r.as_mut()));
102
103 AutoKeyEvaluationDomain {
104 data,
105 _phantom: PhantomData,
106 }
107 }
108 }
109
110 struct RgswCiphertext<M: Matrix, Mod> {
111 /// Rgsw ciphertext polynomials
112 data: M,
113 modulus: Mod,
114 /// Decomposition for RLWE part A
115 d_a: usize,
116 /// Decomposition for RLWE part B
117 d_b: usize,
118 }
119
120 impl<M: MatrixEntity, Mod: Modulus<Element = M::MatElement>> RgswCiphertext<M, Mod> {
121 pub(crate) fn empty<D: RlweDecomposer>(
122 ring_size: usize,
123 decomposer: &D,
124 modulus: Mod,
125 ) -> RgswCiphertext<M, Mod> {
126 RgswCiphertext {
127 data: M::zeros(
128 decomposer.a().decomposition_count().0 * 2
129 + decomposer.b().decomposition_count().0 * 2,
130 ring_size,
131 ),
132 d_a: decomposer.a().decomposition_count().0,
133 d_b: decomposer.b().decomposition_count().0,
134 modulus,
135 }
136 }
137 }
138
139 pub struct SeededRgswCiphertext<M, S, Mod>
140 where
141 M: Matrix,
142 {
143 pub(crate) data: M,
144 seed: S,
145 modulus: Mod,
146 /// Decomposition for RLWE part A
147 d_a: usize,
148 /// Decomposition for RLWE part B
149 d_b: usize,
150 }
151
152 impl<M: Matrix + MatrixEntity, S, Mod> SeededRgswCiphertext<M, S, Mod> {
153 pub(crate) fn empty<D: RlweDecomposer>(
154 ring_size: usize,
155 decomposer: &D,
156 seed: S,
157 modulus: Mod,
158 ) -> SeededRgswCiphertext<M, S, Mod> {
159 SeededRgswCiphertext {
160 data: M::zeros(
161 decomposer.a().decomposition_count().0 * 2
162 + decomposer.b().decomposition_count().0,
163 ring_size,
164 ),
165 seed,
166 modulus,
167 d_a: decomposer.a().decomposition_count().0,
168 d_b: decomposer.b().decomposition_count().0,
169 }
170 }
171 }
172
173 impl<M: Debug + Matrix, S: Debug, Mod: Debug> Debug for SeededRgswCiphertext<M, S, Mod>
174 where
175 M::MatElement: Debug,
176 {
177 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
178 f.debug_struct("SeededRgswCiphertext")
179 .field("data", &self.data)
180 .field("seed", &self.seed)
181 .field("modulus", &self.modulus)
182 .finish()
183 }
184 }
185
186 pub struct RgswCiphertextEvaluationDomain<M, Mod, R, N> {
187 pub(crate) data: M,
188 modulus: Mod,
189 _phantom: PhantomData<(R, N)>,
190 }
191
192 impl<
193 M: MatrixMut + MatrixEntity,
194 Mod: Modulus<Element = M::MatElement> + Clone,
195 R: NewWithSeed + RandomFillUniformInModulus<[M::MatElement], Mod>,
196 N: NttInit<Mod> + Ntt<Element = M::MatElement> + Debug,
197 > From<&SeededRgswCiphertext<M, R::Seed, Mod>>
198 for RgswCiphertextEvaluationDomain<M, Mod, R, N>
199 where
200 <M as Matrix>::R: RowMut,
201 M::MatElement: Copy,
202 R::Seed: Clone,
203 M: Debug,
204 {
205 fn from(value: &SeededRgswCiphertext<M, R::Seed, Mod>) -> Self {
206 let mut data = M::zeros(value.d_a * 2 + value.d_b * 2, value.data.dimension().1);
207
208 // copy RLWE'(-sm)
209 izip!(
210 data.iter_rows_mut().take(value.d_a * 2),
211 value.data.iter_rows().take(value.d_a * 2)
212 )
213 .for_each(|(to_ri, from_ri)| {
214 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
215 });
216
217 // sample A polynomials of RLWE'(m) - RLWE'A(m)
218 let mut p_rng = R::new_with_seed(value.seed.clone());
219 izip!(data.iter_rows_mut().skip(value.d_a * 2).take(value.d_b * 1))
220 .for_each(|ri| p_rng.random_fill(&value.modulus, ri.as_mut()));
221
222 // RLWE'_B(m)
223 izip!(
224 data.iter_rows_mut().skip(value.d_a * 2 + value.d_b),
225 value.data.iter_rows().skip(value.d_a * 2)
226 )
227 .for_each(|(to_ri, from_ri)| {
228 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
229 });
230
231 // Send polynomials to evaluation domain
232 let ring_size = data.dimension().1;
233 let nttop = N::new(&value.modulus, ring_size);
234 data.iter_rows_mut()
235 .for_each(|ri| nttop.forward(ri.as_mut()));
236
237 Self {
238 data: data,
239 modulus: value.modulus.clone(),
240 _phantom: PhantomData,
241 }
242 }
243 }
244
245 impl<
246 M: MatrixMut + MatrixEntity,
247 Mod: Modulus<Element = M::MatElement> + Clone,
248 R,
249 N: NttInit<Mod> + Ntt<Element = M::MatElement>,
250 > From<&RgswCiphertext<M, Mod>> for RgswCiphertextEvaluationDomain<M, Mod, R, N>
251 where
252 <M as Matrix>::R: RowMut,
253 M::MatElement: Copy,
254 M: Debug,
255 {
256 fn from(value: &RgswCiphertext<M, Mod>) -> Self {
257 let mut data = M::zeros(value.d_a * 2 + value.d_b * 2, value.data.dimension().1);
258
259 // copy RLWE'(-sm)
260 izip!(
261 data.iter_rows_mut().take(value.d_a * 2),
262 value.data.iter_rows().take(value.d_a * 2)
263 )
264 .for_each(|(to_ri, from_ri)| {
265 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
266 });
267
268 // copy RLWE'(m)
269 izip!(
270 data.iter_rows_mut().skip(value.d_a * 2),
271 value.data.iter_rows().skip(value.d_a * 2)
272 )
273 .for_each(|(to_ri, from_ri)| {
274 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
275 });
276
277 // Send polynomials to evaluation domain
278 let ring_size = data.dimension().1;
279 let nttop = N::new(&value.modulus, ring_size);
280 data.iter_rows_mut()
281 .for_each(|ri| nttop.forward(ri.as_mut()));
282
283 Self {
284 data: data,
285 modulus: value.modulus.clone(),
286 _phantom: PhantomData,
287 }
288 }
289 }
290
291 impl<M: Debug, Mod: Debug, R, N> Debug for RgswCiphertextEvaluationDomain<M, Mod, R, N> {
292 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
293 f.debug_struct("RgswCiphertextEvaluationDomain")
294 .field("data", &self.data)
295 .field("modulus", &self.modulus)
296 .field("_phantom", &self._phantom)
297 .finish()
298 }
299 }
300
301 struct SeededRlweCiphertext<R, S, Mod> {
302 data: R,
303 seed: S,
304 modulus: Mod,
305 }
306
307 impl<R: RowEntity, S, Mod> SeededRlweCiphertext<R, S, Mod> {
308 fn empty(ring_size: usize, seed: S, modulus: Mod) -> Self {
309 SeededRlweCiphertext {
310 data: R::zeros(ring_size),
311 seed,
312 modulus,
313 }
314 }
315 }
316
317 pub struct RlweCiphertext<M, Rng> {
318 data: M,
319 _phatom: PhantomData<Rng>,
320 }
321
322 impl<
323 R: Row,
324 M: MatrixEntity<R = R, MatElement = R::Element> + MatrixMut,
325 Rng: NewWithSeed + RandomFillUniformInModulus<[M::MatElement], Mod>,
326 Mod: Modulus<Element = R::Element>,
327 > From<&SeededRlweCiphertext<R, Rng::Seed, Mod>> for RlweCiphertext<M, Rng>
328 where
329 Rng::Seed: Clone,
330 <M as Matrix>::R: RowMut,
331 R::Element: Copy,
332 {
333 fn from(value: &SeededRlweCiphertext<R, Rng::Seed, Mod>) -> Self {
334 let mut data = M::zeros(2, value.data.as_ref().len());
335
336 // sample a
337 let mut p_rng = Rng::new_with_seed(value.seed.clone());
338 RandomFillUniformInModulus::random_fill(
339 &mut p_rng,
340 &value.modulus,
341 data.get_row_mut(0),
342 );
343
344 data.get_row_mut(1).copy_from_slice(value.data.as_ref());
345
346 RlweCiphertext {
347 data,
348 _phatom: PhantomData,
349 }
350 }
351 }
352
353 struct SeededRlwePublicKey<Ro: Row, S> {
354 data: Ro,
355 seed: S,
356 modulus: Ro::Element,
357 }
358
359 impl<Ro: RowEntity, S> SeededRlwePublicKey<Ro, S> {
360 pub(crate) fn empty(ring_size: usize, seed: S, modulus: Ro::Element) -> Self {
361 Self {
362 data: Ro::zeros(ring_size),
363 seed,
364 modulus,
365 }
366 }
367 }
368
369 struct RlwePublicKey<M, R> {
370 data: M,
371 _phantom: PhantomData<R>,
372 }
373
374 impl<
375 M: MatrixMut + MatrixEntity,
376 Rng: NewWithSeed + RandomFillUniformInModulus<[M::MatElement], M::MatElement>,
377 > From<&SeededRlwePublicKey<M::R, Rng::Seed>> for RlwePublicKey<M, Rng>
378 where
379 <M as Matrix>::R: RowMut,
380 M::MatElement: Copy,
381 Rng::Seed: Copy,
382 {
383 fn from(value: &SeededRlwePublicKey<M::R, Rng::Seed>) -> Self {
384 let mut data = M::zeros(2, value.data.as_ref().len());
385
386 // sample a
387 let mut p_rng = Rng::new_with_seed(value.seed);
388 RandomFillUniformInModulus::random_fill(
389 &mut p_rng,
390 &value.modulus,
391 data.get_row_mut(0),
392 );
393
394 // copy over b
395 data.get_row_mut(1).copy_from_slice(value.data.as_ref());
396
397 Self {
398 data,
399 _phantom: PhantomData,
400 }
401 }
402 }
403
404 #[derive(Clone)]
405 struct RlweSecret {
406 pub(crate) values: Vec<i32>,
407 }
408
409 impl RlweSecret {
410 pub fn random(hw: usize, n: usize) -> RlweSecret {
411 DefaultSecureRng::with_local_mut(|rng| {
412 let mut out = vec![0i32; n];
413 fill_random_ternary_secret_with_hamming_weight(&mut out, hw, rng);
414
415 RlweSecret { values: out }
416 })
417 }
418
419 fn values(&self) -> &[i32] {
420 &self.values
421 }
422 }
423
424 fn random_seed() -> [u8; 32] {
425 let mut rng = DefaultSecureRng::new();
426 let mut seed = [0u8; 32];
427 rng.fill_bytes(&mut seed);
428 seed
429 }
430
431 /// Encrypts m as RGSW ciphertext RGSW(m) using supplied secret key. Returns
432 /// seeded RGSW ciphertext in coefficient domain
433 fn sk_encrypt_rgsw<T: Modulus<Element = u64> + Clone>(
434 m: &[u64],
435 s: &[i32],
436 decomposer: &(DefaultDecomposer<u64>, DefaultDecomposer<u64>),
437 mod_op: &ModularOpsU64<T>,
438 ntt_op: &NttBackendU64,
439 ) -> SeededRgswCiphertext<Vec<Vec<u64>>, [u8; 32], T> {
440 let ring_size = s.len();
441 assert!(m.len() == s.len());
442
443 let mut rng = DefaultSecureRng::new();
444
445 let q = mod_op.modulus();
446 let rgsw_seed = random_seed();
447 let mut seeded_rgsw_ct = SeededRgswCiphertext::<Vec<Vec<u64>>, [u8; 32], T>::empty(
448 ring_size as usize,
449 decomposer,
450 rgsw_seed,
451 q.clone(),
452 );
453 let mut p_rng = DefaultSecureRng::new_seeded(rgsw_seed);
454 secret_key_encrypt_rgsw(
455 &mut seeded_rgsw_ct.data,
456 m,
457 &decomposer.a().gadget_vector(),
458 &decomposer.b().gadget_vector(),
459 s,
460 mod_op,
461 ntt_op,
462 &mut p_rng,
463 &mut rng,
464 );
465 seeded_rgsw_ct
466 }
467
468 #[test]
469 fn rlwe_encrypt_decryption() {
470 let logq = 50;
471 let logp = 2;
472 let ring_size = 1 << 4;
473 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
474 let p = 1u64 << logp;
475
476 let mut rng = DefaultSecureRng::new();
477
478 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
479
480 // sample m0
481 let mut m0 = vec![0u64; ring_size as usize];
482 RandomFillUniformInModulus::<[u64], u64>::random_fill(
483 &mut rng,
484 &(1u64 << logp),
485 m0.as_mut_slice(),
486 );
487
488 let ntt_op = NttBackendU64::new(&q, ring_size as usize);
489 let mod_op = ModularOpsU64::new(q);
490
491 // encrypt m0
492 let encoded_m = m0
493 .iter()
494 .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
495 .collect_vec();
496 let seed = random_seed();
497 let mut rlwe_in_ct =
498 SeededRlweCiphertext::<Vec<u64>, _, _>::empty(ring_size as usize, seed, q);
499 let mut p_rng = DefaultSecureRng::new_seeded(seed);
500 seeded_secret_key_encrypt_rlwe(
501 &encoded_m,
502 &mut rlwe_in_ct.data,
503 s.values(),
504 &mod_op,
505 &ntt_op,
506 &mut p_rng,
507 &mut rng,
508 );
509 let rlwe_in_ct = RlweCiphertext::<Vec<Vec<u64>>, DefaultSecureRng>::from(&rlwe_in_ct);
510
511 let mut encoded_m_back = vec![0u64; ring_size as usize];
512 decrypt_rlwe(
513 &rlwe_in_ct.data,
514 s.values(),
515 &mut encoded_m_back,
516 &ntt_op,
517 &mod_op,
518 );
519 let m_back = encoded_m_back
520 .iter()
521 .map(|v| (((*v as f64 * p as f64) / q as f64).round() as u64) % p)
522 .collect_vec();
523 assert_eq!(m0, m_back);
524 }
525
526 #[test]
527 fn rlwe_by_rgsw_works() {
528 let logq = 50;
529 let logp = 2;
530 let ring_size = 1 << 4;
531 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
532 let p: u64 = 1u64 << logp;
533
534 let mut rng = DefaultSecureRng::new_seeded([0u8; 32]);
535
536 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
537
538 let mut m0 = vec![0u64; ring_size as usize];
539 RandomFillUniformInModulus::<[u64], _>::random_fill(
540 &mut rng,
541 &(1u64 << logp),
542 m0.as_mut_slice(),
543 );
544 let mut m1 = vec![0u64; ring_size as usize];
545 m1[thread_rng().gen_range(0..ring_size) as usize] = 1;
546
547 let ntt_op = NttBackendU64::new(&q, ring_size as usize);
548 let mod_op = ModularOpsU64::new(q);
549 let d_rgsw = 10;
550 let logb = 5;
551 let decomposer = (
552 DefaultDecomposer::new(q, logb, d_rgsw),
553 DefaultDecomposer::new(q, logb, d_rgsw),
554 );
555
556 // create public key
557 let pk_seed = random_seed();
558 let mut pk_prng = DefaultSecureRng::new_seeded(pk_seed);
559 let mut seeded_pk =
560 SeededRlwePublicKey::<Vec<u64>, _>::empty(ring_size as usize, pk_seed, q);
561 rlwe_public_key(
562 &mut seeded_pk.data,
563 s.values(),
564 &ntt_op,
565 &mod_op,
566 &mut pk_prng,
567 &mut rng,
568 );
569 // let pk = RlwePublicKey::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_pk);
570
571 // Encrypt m1 as RGSW(m1)
572 let rgsw_ct = {
573 // Encryption m1 as RGSW(m1) using secret key
574 let seeded_rgsw_ct = sk_encrypt_rgsw(&m1, s.values(), &decomposer, &mod_op, &ntt_op);
575 RgswCiphertextEvaluationDomain::<Vec<Vec<u64>>, _,DefaultSecureRng, NttBackendU64>::from(&seeded_rgsw_ct)
576 };
577
578 // Encrypt m0 as RLWE(m0)
579 let mut rlwe_in_ct = {
580 let encoded_m = m0
581 .iter()
582 .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
583 .collect_vec();
584
585 let seed = random_seed();
586 let mut p_rng = DefaultSecureRng::new_seeded(seed);
587 let mut seeded_rlwe = SeededRlweCiphertext::empty(ring_size as usize, seed, q);
588 seeded_secret_key_encrypt_rlwe(
589 &encoded_m,
590 &mut seeded_rlwe.data,
591 s.values(),
592 &mod_op,
593 &ntt_op,
594 &mut p_rng,
595 &mut rng,
596 );
597 RlweCiphertext::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_rlwe)
598 };
599
600 // RLWE(m0m1) = RLWE(m0) x RGSW(m1)
601 let mut scratch_space =
602 vec![vec![0u64; ring_size as usize]; rlwe_x_rgsw_scratch_rows(&decomposer)];
603
604 // rlwe x rgsw with with soup repr
605 let rlwe_in_ct_shoup = {
606 let mut rlwe_in_ct_shoup = rlwe_in_ct.data.clone();
607
608 let rgsw_ct_shoup = ToShoup::to_shoup(&rgsw_ct.data, q);
609
610 rlwe_by_rgsw_shoup(
611 &mut RlweCiphertextMutRef::new(rlwe_in_ct_shoup.as_mut()),
612 &RgswCiphertextRef::new(
613 rgsw_ct.data.as_ref(),
614 decomposer.a().decomposition_count().0,
615 decomposer.b().decomposition_count().0,
616 ),
617 &RgswCiphertextRef::new(
618 rgsw_ct_shoup.as_ref(),
619 decomposer.a().decomposition_count().0,
620 decomposer.b().decomposition_count().0,
621 ),
622 &mut RuntimeScratchMutRef::new(scratch_space.as_mut()),
623 &decomposer,
624 &ntt_op,
625 &mod_op,
626 false,
627 );
628
629 rlwe_in_ct_shoup
630 };
631
632 // rlwe x rgsw normal
633 {
634 rlwe_by_rgsw(
635 &mut RlweCiphertextMutRef::new(rlwe_in_ct.data.as_mut()),
636 &RgswCiphertextRef::new(
637 rgsw_ct.data.as_ref(),
638 decomposer.a().decomposition_count().0,
639 decomposer.b().decomposition_count().0,
640 ),
641 &mut RuntimeScratchMutRef::new(scratch_space.as_mut()),
642 &decomposer,
643 &ntt_op,
644 &mod_op,
645 false,
646 );
647 }
648
649 // output from both functions must be equal
650 assert_eq!(rlwe_in_ct.data, rlwe_in_ct_shoup);
651
652 // Decrypt RLWE(m0m1)
653 let mut encoded_m0m1_back = vec![0u64; ring_size as usize];
654 decrypt_rlwe(
655 &rlwe_in_ct_shoup,
656 s.values(),
657 &mut encoded_m0m1_back,
658 &ntt_op,
659 &mod_op,
660 );
661 let m0m1_back = encoded_m0m1_back
662 .iter()
663 .map(|v| (((*v as f64 * p as f64) / (q as f64)).round() as u64) % p)
664 .collect_vec();
665
666 let mul_mod = |v0: &u64, v1: &u64| (v0 * v1) % p;
667 let m0m1 = negacyclic_mul(&m0, &m1, mul_mod, p);
668
669 // {
670 // // measure noise
671 // let encoded_m_ideal = m0m1
672 // .iter()
673 // .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
674 // .collect_vec();
675
676 // let noise = measure_noise(&rlwe_in_ct, &encoded_m_ideal, &ntt_op,
677 // &mod_op, s.values()); println!("Noise RLWE(m0m1)(=
678 // RLWE(m0)xRGSW(m1)) : {noise}"); }
679
680 assert!(
681 m0m1 == m0m1_back,
682 "Expected {:?} \n Got {:?}",
683 m0m1,
684 m0m1_back
685 );
686 }
687
688 #[test]
689 fn rlwe_auto_works() {
690 let logq = 55;
691 let ring_size = 1 << 11;
692 let q = generate_prime(logq, 2 * ring_size, 1u64 << logq).unwrap();
693 let logp = 3;
694 let p = 1u64 << logp;
695 let d_rgsw = 5;
696 let logb = 11;
697
698 let mut rng = DefaultSecureRng::new();
699 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
700
701 let mut m = vec![0u64; ring_size as usize];
702 RandomFillUniformInModulus::random_fill(&mut rng, &p, m.as_mut_slice());
703 let encoded_m = m
704 .iter()
705 .map(|v| (((*v as f64 * q as f64) / (p as f64)).round() as u64))
706 .collect_vec();
707
708 let ntt_op = NttBackendU64::new(&q, ring_size as usize);
709 let mod_op = ModularOpsU64::new(q);
710
711 // RLWE_{s}(m)
712 let seed_rlwe = random_seed();
713 let mut seeded_rlwe_m = SeededRlweCiphertext::empty(ring_size as usize, seed_rlwe, q);
714 let mut p_rng = DefaultSecureRng::new_seeded(seed_rlwe);
715 seeded_secret_key_encrypt_rlwe(
716 &encoded_m,
717 &mut seeded_rlwe_m.data,
718 s.values(),
719 &mod_op,
720 &ntt_op,
721 &mut p_rng,
722 &mut rng,
723 );
724 let mut rlwe_m = RlweCiphertext::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_rlwe_m);
725
726 let auto_k = -125;
727
728 // Generate auto key to key switch from s^k to s
729 let decomposer = DefaultDecomposer::new(q, logb, d_rgsw);
730 let seed_auto = random_seed();
731 let mut seeded_auto_key =
732 SeededAutoKey::empty(ring_size as usize, &decomposer, seed_auto, q);
733 let mut p_rng = DefaultSecureRng::new_seeded(seed_auto);
734 let gadget_vector = decomposer.gadget_vector();
735 seeded_auto_key_gen(
736 &mut seeded_auto_key.data,
737 s.values(),
738 auto_k,
739 &gadget_vector,
740 &mod_op,
741 &ntt_op,
742 &mut p_rng,
743 &mut rng,
744 );
745 let auto_key =
746 AutoKeyEvaluationDomain::<Vec<Vec<u64>>, DefaultSecureRng, NttBackendU64>::from(
747 &seeded_auto_key,
748 );
749
750 // Send RLWE_{s}(m) -> RLWE_{s}(m^k)
751 let mut scratch_space =
752 vec![vec![0; ring_size as usize]; rlwe_auto_scratch_rows(&decomposer)];
753 let (auto_map_index, auto_map_sign) = generate_auto_map(ring_size as usize, auto_k);
754
755 // galois auto with auto key in shoup repr
756 let rlwe_m_shoup = {
757 let auto_key_shoup = ToShoup::to_shoup(&auto_key.data, q);
758 let mut rlwe_m_shoup = rlwe_m.data.clone();
759 rlwe_auto_shoup(
760 &mut RlweCiphertextMutRef::new(&mut rlwe_m_shoup),
761 &RlweKskRef::new(&auto_key.data, decomposer.decomposition_count().0),
762 &RlweKskRef::new(&auto_key_shoup, decomposer.decomposition_count().0),
763 &mut RuntimeScratchMutRef::new(&mut scratch_space),
764 &auto_map_index,
765 &auto_map_sign,
766 &mod_op,
767 &ntt_op,
768 &decomposer,
769 false,
770 );
771 rlwe_m_shoup
772 };
773
774 // normal galois auto
775 {
776 rlwe_auto(
777 &mut RlweCiphertextMutRef::new(rlwe_m.data.as_mut()),
778 &RlweKskRef::new(auto_key.data.as_ref(), decomposer.decomposition_count().0),
779 &mut RuntimeScratchMutRef::new(scratch_space.as_mut()),
780 &auto_map_index,
781 &auto_map_sign,
782 &mod_op,
783 &ntt_op,
784 &decomposer,
785 false,
786 );
787 }
788
789 // rlwe out from both functions must be same
790 assert_eq!(rlwe_m.data, rlwe_m_shoup);
791
792 let rlwe_m_k = rlwe_m;
793
794 // Decrypt RLWE_{s}(m^k) and check
795 let mut encoded_m_k_back = vec![0u64; ring_size as usize];
796 decrypt_rlwe(
797 &rlwe_m_k.data,
798 s.values(),
799 &mut encoded_m_k_back,
800 &ntt_op,
801 &mod_op,
802 );
803 let m_k_back = encoded_m_k_back
804 .iter()
805 .map(|v| (((*v as f64 * p as f64) / q as f64).round() as u64) % p)
806 .collect_vec();
807
808 let mut m_k = vec![0u64; ring_size as usize];
809 // Send \delta m -> \delta m^k
810 izip!(m.iter(), auto_map_index.iter(), auto_map_sign.iter()).for_each(
811 |(v, to_index, sign)| {
812 if !*sign {
813 m_k[*to_index] = (p - *v) % p;
814 } else {
815 m_k[*to_index] = *v;
816 }
817 },
818 );
819
820 // {
821 // let encoded_m_k = m_k
822 // .iter()
823 // .map(|v| ((*v as f64 * q as f64) / p as f64).round() as u64)
824 // .collect_vec();
825
826 // let noise = measure_noise(&rlwe_m_k, &encoded_m_k, &ntt_op, &mod_op,
827 // s.values()); println!("Ksk noise: {noise}");
828 // }
829
830 assert_eq!(m_k_back, m_k);
831 }
832
833 /// Collect noise stats of RGSW ciphertext
834 ///
835 /// - rgsw_ct: RGSW ciphertext must be in coefficient domain
836 fn rgsw_noise_stats<T: Modulus<Element = u64> + Clone>(
837 rgsw_ct: &[Vec<u64>],
838 m: &[u64],
839 s: &[i32],
840 decomposer: &(DefaultDecomposer<u64>, DefaultDecomposer<u64>),
841 q: &T,
842 ) -> Stats<i64> {
843 let gadget_vector_a = decomposer.a().gadget_vector();
844 let gadget_vector_b = decomposer.b().gadget_vector();
845 let d_a = gadget_vector_a.len();
846 let d_b = gadget_vector_b.len();
847 let ring_size = s.len();
848 assert!(Matrix::dimension(&rgsw_ct) == (d_a * 2 + d_b * 2, ring_size));
849 assert!(m.len() == ring_size);
850
851 let mod_op = ModularOpsU64::new(q.clone());
852 let ntt_op = NttBackendU64::new(q, ring_size);
853
854 let mul_mod =
855 |a: &u64, b: &u64| ((*a as u128 * *b as u128) % q.q().unwrap() as u128) as u64;
856 let s_poly = Vec::<u64>::try_convert_from(s, q);
857 let mut neg_s = s_poly.clone();
858 mod_op.elwise_neg_mut(neg_s.as_mut());
859 let neg_sm0m1 = negacyclic_mul(&neg_s, &m, mul_mod, q.q().unwrap());
860
861 let mut stats = Stats::new();
862
863 // RLWE(\beta^j -s * m)
864 for j in 0..d_a {
865 let want_m = {
866 // RLWE(\beta^j -s * m)
867 let mut beta_neg_sm0m1 = vec![0u64; ring_size as usize];
868 mod_op.elwise_scalar_mul(beta_neg_sm0m1.as_mut(), &neg_sm0m1, &gadget_vector_a[j]);
869 beta_neg_sm0m1
870 };
871
872 let mut rlwe = vec![vec![0u64; ring_size as usize]; 2];
873 rlwe[0].copy_from_slice(rgsw_ct.get_row_slice(j));
874 rlwe[1].copy_from_slice(rgsw_ct.get_row_slice(d_a + j));
875
876 let mut got_m = vec![0; ring_size];
877 decrypt_rlwe(&rlwe, s, &mut got_m, &ntt_op, &mod_op);
878
879 let mut diff = want_m;
880 mod_op.elwise_sub_mut(diff.as_mut(), got_m.as_ref());
881 stats.add_many_samples(&Vec::<i64>::try_convert_from(&diff, q));
882 }
883
884 // RLWE(\beta^j m)
885 for j in 0..d_b {
886 let want_m = {
887 // RLWE(\beta^j m)
888 let mut beta_m0m1 = vec![0u64; ring_size as usize];
889 mod_op.elwise_scalar_mul(beta_m0m1.as_mut(), &m, &gadget_vector_b[j]);
890 beta_m0m1
891 };
892
893 let mut rlwe = vec![vec![0u64; ring_size as usize]; 2];
894 rlwe[0].copy_from_slice(rgsw_ct.get_row_slice(d_a * 2 + j));
895 rlwe[1].copy_from_slice(rgsw_ct.get_row_slice(d_a * 2 + d_b + j));
896
897 let mut got_m = vec![0; ring_size];
898 decrypt_rlwe(&rlwe, s, &mut got_m, &ntt_op, &mod_op);
899
900 let mut diff = want_m;
901 mod_op.elwise_sub_mut(diff.as_mut(), got_m.as_ref());
902 stats.add_many_samples(&Vec::<i64>::try_convert_from(&diff, q));
903 }
904
905 stats
906 }
907
908 #[test]
909 fn print_noise_stats_rgsw_x_rgsw() {
910 let logq = 60;
911 let logp = 2;
912 let ring_size = 1 << 11;
913 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
914 let d_rgsw = 12;
915 let logb = 5;
916
917 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
918
919 let ntt_op = NttBackendU64::new(&q, ring_size as usize);
920 let mod_op = ModularOpsU64::new(q);
921 let decomposer = (
922 DefaultDecomposer::new(q, logb, d_rgsw),
923 DefaultDecomposer::new(q, logb, d_rgsw),
924 );
925
926 let d_a = decomposer.a().decomposition_count().0;
927 let d_b = decomposer.b().decomposition_count().0;
928
929 let mul_mod = |a: &u64, b: &u64| ((*a as u128 * *b as u128) % q as u128) as u64;
930
931 let mut carry_m = vec![0u64; ring_size as usize];
932 carry_m[thread_rng().gen_range(0..ring_size) as usize] = 1 << logp;
933
934 // RGSW(carry_m)
935 let mut rgsw_carrym = {
936 let seeded_rgsw = sk_encrypt_rgsw(&carry_m, s.values(), &decomposer, &mod_op, &ntt_op);
937 let mut rgsw_eval =
938 RgswCiphertextEvaluationDomain::<_, _, DefaultSecureRng, NttBackendU64>::from(
939 &seeded_rgsw,
940 );
941 rgsw_eval
942 .data
943 .iter_mut()
944 .for_each(|ri| ntt_op.backward(ri.as_mut()));
945 rgsw_eval.data
946 };
947
948 let mut scratch_matrix = vec![
949 vec![0u64; ring_size as usize];
950 rgsw_x_rgsw_scratch_rows(&decomposer, &decomposer)
951 ];
952
953 rgsw_noise_stats(&rgsw_carrym, &carry_m, s.values(), &decomposer, &q);
954
955 for i in 0..8 {
956 let mut m = vec![0u64; ring_size as usize];
957 m[thread_rng().gen_range(0..ring_size) as usize] = if (i & 1) == 1 { q - 1 } else { 1 };
958 let rgsw_m =
959 RgswCiphertextEvaluationDomain::<_, _, DefaultSecureRng, NttBackendU64>::from(
960 &sk_encrypt_rgsw(&m, s.values(), &decomposer, &mod_op, &ntt_op),
961 );
962
963 rgsw_by_rgsw_inplace(
964 &mut RgswCiphertextMutRef::new(rgsw_carrym.as_mut(), d_a, d_b),
965 &RgswCiphertextRef::new(rgsw_m.data.as_ref(), d_a, d_b),
966 &decomposer,
967 &decomposer,
968 &mut RuntimeScratchMutRef::new(scratch_matrix.as_mut()),
969 &ntt_op,
970 &mod_op,
971 );
972
973 // measure noise
974 carry_m = negacyclic_mul(&carry_m, &m, mul_mod, q);
975 let stats = rgsw_noise_stats(&rgsw_carrym, &carry_m, s.values(), &decomposer, &q);
976 println!(
977 "Log2 of noise std after {i} RGSW x RGSW: {}",
978 stats.std_dev().abs().log2()
979 );
980 }
981 }
982}