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