phantom-zone/src/rgsw/mod.rs
src/rgsw/mod.rsRaw
1use itertools::{izip, Itertools};
2use num_traits::{PrimInt, Signed, ToPrimitive, Zero};
3use std::{
4 clone,
5 fmt::Debug,
6 iter,
7 marker::PhantomData,
8 ops::{Div, Neg, Sub},
9};
10
11use crate::{
12 backend::Modulus,
13 decomposer::{Decomposer, RlweDecomposer},
14 ntt::{Ntt, NttInit},
15 random::{DefaultSecureRng, NewWithSeed, RandomFillUniformInModulus},
16 utils::{fill_random_ternary_secret_with_hamming_weight, ToShoup, WithLocal},
17 Matrix, MatrixEntity, MatrixMut, Row, RowEntity, RowMut, Secret,
18};
19
20mod keygen;
21mod runtime;
22
23pub(crate) use keygen::*;
24pub(crate) use runtime::*;
25
26pub struct SeededAutoKey<M, S, Mod>
27where
28 M: Matrix,
29{
30 data: M,
31 seed: S,
32 modulus: Mod,
33}
34
35impl<M: Matrix + MatrixEntity, S, Mod: Modulus<Element = M::MatElement>> SeededAutoKey<M, S, Mod> {
36 fn empty<D: Decomposer>(ring_size: usize, auto_decomposer: &D, seed: S, modulus: Mod) -> Self {
37 SeededAutoKey {
38 data: M::zeros(auto_decomposer.decomposition_count(), ring_size),
39 seed,
40 modulus,
41 }
42 }
43}
44
45pub struct AutoKeyEvaluationDomain<M: Matrix, Mod, R, N> {
46 data: M,
47 _phantom: PhantomData<(R, N)>,
48 modulus: Mod,
49}
50
51impl<
52 M: MatrixMut + MatrixEntity,
53 Mod: Modulus<Element = M::MatElement> + Clone,
54 R: RandomFillUniformInModulus<[M::MatElement], Mod> + NewWithSeed,
55 N: NttInit<Mod> + Ntt<Element = M::MatElement>,
56 > From<&SeededAutoKey<M, R::Seed, Mod>> for AutoKeyEvaluationDomain<M, Mod, R, N>
57where
58 <M as Matrix>::R: RowMut,
59 M::MatElement: Copy,
60
61 R::Seed: Clone,
62{
63 fn from(value: &SeededAutoKey<M, R::Seed, Mod>) -> Self {
64 let (d, ring_size) = value.data.dimension();
65 let mut data = M::zeros(2 * d, ring_size);
66
67 // sample RLWE'_A(-s(X^k))
68 let mut p_rng = R::new_with_seed(value.seed.clone());
69 data.iter_rows_mut().take(d).for_each(|r| {
70 RandomFillUniformInModulus::random_fill(&mut p_rng, &value.modulus, r.as_mut());
71 });
72
73 // copy over RLWE'_B(-s(X^k))
74 izip!(data.iter_rows_mut().skip(d), value.data.iter_rows()).for_each(|(to_r, from_r)| {
75 to_r.as_mut().copy_from_slice(from_r.as_ref());
76 });
77
78 // send RLWE'(-s(X^k)) polynomials to evaluation domain
79 let ntt_op = N::new(&value.modulus, ring_size);
80 data.iter_rows_mut()
81 .for_each(|r| ntt_op.forward(r.as_mut()));
82
83 AutoKeyEvaluationDomain {
84 data,
85 _phantom: PhantomData,
86 modulus: value.modulus.clone(),
87 }
88 }
89}
90
91pub struct ShoupAutoKeyEvaluationDomain<M> {
92 data: M,
93}
94
95impl<M: Matrix + ToShoup<Modulus = M::MatElement>, Mod: Modulus<Element = M::MatElement>, R, N>
96 From<&AutoKeyEvaluationDomain<M, Mod, R, N>> for ShoupAutoKeyEvaluationDomain<M>
97{
98 fn from(value: &AutoKeyEvaluationDomain<M, Mod, R, N>) -> Self {
99 Self {
100 data: M::to_shoup(&value.data, value.modulus.q().unwrap()),
101 }
102 }
103}
104
105pub struct RgswCiphertext<M: Matrix, Mod> {
106 /// Rgsw ciphertext polynomials
107 pub(crate) data: M,
108 modulus: Mod,
109 /// Decomposition for RLWE part A
110 d_a: usize,
111 /// Decomposition for RLWE part B
112 d_b: usize,
113}
114
115impl<M: MatrixEntity, Mod: Modulus<Element = M::MatElement>> RgswCiphertext<M, Mod> {
116 pub(crate) fn empty<D: RlweDecomposer>(
117 ring_size: usize,
118 decomposer: &D,
119 modulus: Mod,
120 ) -> RgswCiphertext<M, Mod> {
121 RgswCiphertext {
122 data: M::zeros(
123 decomposer.a().decomposition_count() * 2 + decomposer.b().decomposition_count() * 2,
124 ring_size,
125 ),
126 d_a: decomposer.a().decomposition_count(),
127 d_b: decomposer.b().decomposition_count(),
128 modulus,
129 }
130 }
131}
132
133pub struct SeededRgswCiphertext<M, S, Mod>
134where
135 M: Matrix,
136{
137 pub(crate) data: M,
138 seed: S,
139 modulus: Mod,
140 /// Decomposition for RLWE part A
141 d_a: usize,
142 /// Decomposition for RLWE part B
143 d_b: usize,
144}
145
146impl<M: Matrix + MatrixEntity, S, Mod> SeededRgswCiphertext<M, S, Mod> {
147 pub(crate) fn empty<D: RlweDecomposer>(
148 ring_size: usize,
149 decomposer: &D,
150 seed: S,
151 modulus: Mod,
152 ) -> SeededRgswCiphertext<M, S, Mod> {
153 SeededRgswCiphertext {
154 data: M::zeros(
155 decomposer.a().decomposition_count() * 2 + decomposer.b().decomposition_count(),
156 ring_size,
157 ),
158 seed,
159 modulus,
160 d_a: decomposer.a().decomposition_count(),
161 d_b: decomposer.b().decomposition_count(),
162 }
163 }
164}
165
166impl<M: Debug + Matrix, S: Debug, Mod: Debug> Debug for SeededRgswCiphertext<M, S, Mod>
167where
168 M::MatElement: Debug,
169{
170 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
171 f.debug_struct("SeededRgswCiphertext")
172 .field("data", &self.data)
173 .field("seed", &self.seed)
174 .field("modulus", &self.modulus)
175 .finish()
176 }
177}
178
179pub struct RgswCiphertextEvaluationDomain<M, Mod, R, N> {
180 pub(crate) data: M,
181 modulus: Mod,
182 _phantom: PhantomData<(R, N)>,
183}
184
185impl<
186 M: MatrixMut + MatrixEntity,
187 Mod: Modulus<Element = M::MatElement> + Clone,
188 R: NewWithSeed + RandomFillUniformInModulus<[M::MatElement], Mod>,
189 N: NttInit<Mod> + Ntt<Element = M::MatElement> + Debug,
190 > From<&SeededRgswCiphertext<M, R::Seed, Mod>> for RgswCiphertextEvaluationDomain<M, Mod, R, N>
191where
192 <M as Matrix>::R: RowMut,
193 M::MatElement: Copy,
194 R::Seed: Clone,
195 M: Debug,
196{
197 fn from(value: &SeededRgswCiphertext<M, R::Seed, Mod>) -> Self {
198 let mut data = M::zeros(value.d_a * 2 + value.d_b * 2, value.data.dimension().1);
199
200 // copy RLWE'(-sm)
201 izip!(
202 data.iter_rows_mut().take(value.d_a * 2),
203 value.data.iter_rows().take(value.d_a * 2)
204 )
205 .for_each(|(to_ri, from_ri)| {
206 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
207 });
208
209 // sample A polynomials of RLWE'(m) - RLWE'A(m)
210 let mut p_rng = R::new_with_seed(value.seed.clone());
211 izip!(data.iter_rows_mut().skip(value.d_a * 2).take(value.d_b * 1))
212 .for_each(|ri| p_rng.random_fill(&value.modulus, ri.as_mut()));
213
214 // RLWE'_B(m)
215 izip!(
216 data.iter_rows_mut().skip(value.d_a * 2 + value.d_b),
217 value.data.iter_rows().skip(value.d_a * 2)
218 )
219 .for_each(|(to_ri, from_ri)| {
220 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
221 });
222
223 // Send polynomials to evaluation domain
224 let ring_size = data.dimension().1;
225 let nttop = N::new(&value.modulus, ring_size);
226 data.iter_rows_mut()
227 .for_each(|ri| nttop.forward(ri.as_mut()));
228
229 Self {
230 data: data,
231 modulus: value.modulus.clone(),
232 _phantom: PhantomData,
233 }
234 }
235}
236
237impl<
238 M: MatrixMut + MatrixEntity,
239 Mod: Modulus<Element = M::MatElement> + Clone,
240 R,
241 N: NttInit<Mod> + Ntt<Element = M::MatElement>,
242 > From<&RgswCiphertext<M, Mod>> for RgswCiphertextEvaluationDomain<M, Mod, R, N>
243where
244 <M as Matrix>::R: RowMut,
245 M::MatElement: Copy,
246 M: Debug,
247{
248 fn from(value: &RgswCiphertext<M, Mod>) -> Self {
249 let mut data = M::zeros(value.d_a * 2 + value.d_b * 2, value.data.dimension().1);
250
251 // copy RLWE'(-sm)
252 izip!(
253 data.iter_rows_mut().take(value.d_a * 2),
254 value.data.iter_rows().take(value.d_a * 2)
255 )
256 .for_each(|(to_ri, from_ri)| {
257 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
258 });
259
260 // copy RLWE'(m)
261 izip!(
262 data.iter_rows_mut().skip(value.d_a * 2),
263 value.data.iter_rows().skip(value.d_a * 2)
264 )
265 .for_each(|(to_ri, from_ri)| {
266 to_ri.as_mut().copy_from_slice(from_ri.as_ref());
267 });
268
269 // Send polynomials to evaluation domain
270 let ring_size = data.dimension().1;
271 let nttop = N::new(&value.modulus, ring_size);
272 data.iter_rows_mut()
273 .for_each(|ri| nttop.forward(ri.as_mut()));
274
275 Self {
276 data: data,
277 modulus: value.modulus.clone(),
278 _phantom: PhantomData,
279 }
280 }
281}
282
283impl<M: Debug, Mod: Debug, R, N> Debug for RgswCiphertextEvaluationDomain<M, Mod, R, N> {
284 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
285 f.debug_struct("RgswCiphertextEvaluationDomain")
286 .field("data", &self.data)
287 .field("modulus", &self.modulus)
288 .field("_phantom", &self._phantom)
289 .finish()
290 }
291}
292
293impl<M: Matrix, Mod, R, N> Matrix for RgswCiphertextEvaluationDomain<M, Mod, R, N> {
294 type MatElement = M::MatElement;
295 type R = M::R;
296
297 fn dimension(&self) -> (usize, usize) {
298 self.data.dimension()
299 }
300
301 fn fits(&self, row: usize, col: usize) -> bool {
302 self.data.fits(row, col)
303 }
304}
305
306impl<M: Matrix, Mod, R, N> AsRef<[M::R]> for RgswCiphertextEvaluationDomain<M, Mod, R, N> {
307 fn as_ref(&self) -> &[M::R] {
308 self.data.as_ref()
309 }
310}
311
312pub struct ShoupRgswCiphertextEvaluationDomain<M> {
313 pub(crate) data: M,
314}
315
316impl<M: Matrix + ToShoup<Modulus = M::MatElement>, Mod: Modulus<Element = M::MatElement>, R, N>
317 From<&RgswCiphertextEvaluationDomain<M, Mod, R, N>> for ShoupRgswCiphertextEvaluationDomain<M>
318{
319 fn from(value: &RgswCiphertextEvaluationDomain<M, Mod, R, N>) -> Self {
320 Self {
321 data: M::to_shoup(&value.data, value.modulus.q().unwrap()),
322 }
323 }
324}
325
326pub struct SeededRlweCiphertext<R, S, Mod> {
327 pub(crate) data: R,
328 pub(crate) seed: S,
329 pub(crate) modulus: Mod,
330}
331
332impl<R: RowEntity, S, Mod> SeededRlweCiphertext<R, S, Mod> {
333 pub(crate) fn empty(ring_size: usize, seed: S, modulus: Mod) -> Self {
334 SeededRlweCiphertext {
335 data: R::zeros(ring_size),
336 seed,
337 modulus,
338 }
339 }
340}
341
342pub struct RlweCiphertext<M, Rng> {
343 pub(crate) data: M,
344 pub(crate) is_trivial: bool,
345 pub(crate) _phatom: PhantomData<Rng>,
346}
347
348impl<M, Rng> RlweCiphertext<M, Rng> {
349 pub(crate) fn new_trivial(data: M) -> Self {
350 RlweCiphertext {
351 data,
352 is_trivial: true,
353 _phatom: PhantomData,
354 }
355 }
356}
357
358impl<M: Matrix, Rng> Matrix for RlweCiphertext<M, Rng> {
359 type MatElement = M::MatElement;
360 type R = M::R;
361
362 fn dimension(&self) -> (usize, usize) {
363 self.data.dimension()
364 }
365
366 fn fits(&self, row: usize, col: usize) -> bool {
367 self.data.fits(row, col)
368 }
369}
370
371impl<M: MatrixMut, Rng> MatrixMut for RlweCiphertext<M, Rng> where <M as Matrix>::R: RowMut {}
372
373impl<M: Matrix, Rng> AsRef<[<M as Matrix>::R]> for RlweCiphertext<M, Rng> {
374 fn as_ref(&self) -> &[<M as Matrix>::R] {
375 self.data.as_ref()
376 }
377}
378
379impl<M: MatrixMut, Rng> AsMut<[<M as Matrix>::R]> for RlweCiphertext<M, Rng>
380where
381 <M as Matrix>::R: RowMut,
382{
383 fn as_mut(&mut self) -> &mut [<M as Matrix>::R] {
384 self.data.as_mut()
385 }
386}
387
388impl<M, Rng> IsTrivial for RlweCiphertext<M, Rng> {
389 fn is_trivial(&self) -> bool {
390 self.is_trivial
391 }
392 fn set_not_trivial(&mut self) {
393 self.is_trivial = false;
394 }
395}
396
397impl<
398 R: Row,
399 M: MatrixEntity<R = R, MatElement = R::Element> + MatrixMut,
400 Rng: NewWithSeed + RandomFillUniformInModulus<[M::MatElement], Mod>,
401 Mod: Modulus<Element = R::Element>,
402 > From<&SeededRlweCiphertext<R, Rng::Seed, Mod>> for RlweCiphertext<M, Rng>
403where
404 Rng::Seed: Clone,
405 <M as Matrix>::R: RowMut,
406 R::Element: Copy,
407{
408 fn from(value: &SeededRlweCiphertext<R, Rng::Seed, Mod>) -> Self {
409 let mut data = M::zeros(2, value.data.as_ref().len());
410
411 // sample a
412 let mut p_rng = Rng::new_with_seed(value.seed.clone());
413 RandomFillUniformInModulus::random_fill(&mut p_rng, &value.modulus, data.get_row_mut(0));
414
415 data.get_row_mut(1).copy_from_slice(value.data.as_ref());
416
417 RlweCiphertext {
418 data,
419 is_trivial: false,
420 _phatom: PhantomData,
421 }
422 }
423}
424
425pub trait IsTrivial {
426 fn is_trivial(&self) -> bool;
427 fn set_not_trivial(&mut self);
428}
429
430pub struct SeededRlwePublicKey<Ro: Row, S> {
431 data: Ro,
432 seed: S,
433 modulus: Ro::Element,
434}
435
436impl<Ro: RowEntity, S> SeededRlwePublicKey<Ro, S> {
437 pub(crate) fn empty(ring_size: usize, seed: S, modulus: Ro::Element) -> Self {
438 Self {
439 data: Ro::zeros(ring_size),
440 seed,
441 modulus,
442 }
443 }
444}
445
446pub struct RlwePublicKey<M, R> {
447 data: M,
448 _phantom: PhantomData<R>,
449}
450
451impl<
452 M: MatrixMut + MatrixEntity,
453 Rng: NewWithSeed + RandomFillUniformInModulus<[M::MatElement], M::MatElement>,
454 > From<&SeededRlwePublicKey<M::R, Rng::Seed>> for RlwePublicKey<M, Rng>
455where
456 <M as Matrix>::R: RowMut,
457 M::MatElement: Copy,
458 Rng::Seed: Copy,
459{
460 fn from(value: &SeededRlwePublicKey<M::R, Rng::Seed>) -> Self {
461 let mut data = M::zeros(2, value.data.as_ref().len());
462
463 // sample a
464 let mut p_rng = Rng::new_with_seed(value.seed);
465 RandomFillUniformInModulus::random_fill(&mut p_rng, &value.modulus, data.get_row_mut(0));
466
467 // copy over b
468 data.get_row_mut(1).copy_from_slice(value.data.as_ref());
469
470 Self {
471 data,
472 _phantom: PhantomData,
473 }
474 }
475}
476
477#[derive(Clone)]
478pub struct RlweSecret {
479 pub(crate) values: Vec<i32>,
480}
481
482impl Secret for RlweSecret {
483 type Element = i32;
484 fn values(&self) -> &[Self::Element] {
485 &self.values
486 }
487}
488
489impl RlweSecret {
490 pub fn random(hw: usize, n: usize) -> RlweSecret {
491 DefaultSecureRng::with_local_mut(|rng| {
492 let mut out = vec![0i32; n];
493 fill_random_ternary_secret_with_hamming_weight(&mut out, hw, rng);
494
495 RlweSecret { values: out }
496 })
497 }
498}
499
500#[cfg(test)]
501pub(crate) mod tests {
502 use std::{clone, marker::PhantomData, ops::Mul, vec};
503
504 use itertools::{izip, Itertools};
505 use rand::{thread_rng, Rng};
506
507 use crate::{
508 backend::{GetModulus, ModInit, ModularOpsU64, Modulus, VectorOps},
509 decomposer::{Decomposer, DefaultDecomposer, RlweDecomposer},
510 ntt::{Ntt, NttBackendU64, NttInit},
511 random::{DefaultSecureRng, RandomFillGaussianInModulus, RandomFillUniformInModulus},
512 rgsw::{
513 galois_auto_shoup, rlwe_by_rgsw_shoup, ShoupAutoKeyEvaluationDomain,
514 ShoupRgswCiphertextEvaluationDomain,
515 },
516 utils::{generate_prime, negacyclic_mul, tests::Stats, TryConvertFrom1},
517 Matrix, MatrixMut, Secret,
518 };
519
520 use super::{
521 keygen::{
522 decrypt_rlwe, generate_auto_map, measure_noise, public_key_encrypt_rgsw,
523 rlwe_public_key, secret_key_encrypt_rgsw, seeded_auto_key_gen,
524 seeded_secret_key_encrypt_rlwe,
525 },
526 runtime::{rgsw_by_rgsw_inplace, rlwe_auto, rlwe_by_rgsw},
527 AutoKeyEvaluationDomain, RgswCiphertext, RgswCiphertextEvaluationDomain, RlweCiphertext,
528 RlwePublicKey, RlweSecret, SeededAutoKey, SeededRgswCiphertext, SeededRlweCiphertext,
529 SeededRlwePublicKey,
530 };
531
532 pub(crate) fn _sk_encrypt_rlwe<T: Modulus<Element = u64> + Clone>(
533 m: &[u64],
534 s: &[i32],
535 ntt_op: &NttBackendU64,
536 mod_op: &ModularOpsU64<T>,
537 ) -> RlweCiphertext<Vec<Vec<u64>>, DefaultSecureRng> {
538 let ring_size = m.len();
539 let q = mod_op.modulus();
540 assert!(s.len() == ring_size);
541
542 let mut rng = DefaultSecureRng::new();
543 let mut rlwe_seed = [0u8; 32];
544 rng.fill_bytes(&mut rlwe_seed);
545 let mut seeded_rlwe_ct =
546 SeededRlweCiphertext::<_, [u8; 32], _>::empty(ring_size as usize, rlwe_seed, q.clone());
547 let mut p_rng = DefaultSecureRng::new_seeded(rlwe_seed);
548 seeded_secret_key_encrypt_rlwe(
549 &m,
550 &mut seeded_rlwe_ct.data,
551 s,
552 mod_op,
553 ntt_op,
554 &mut p_rng,
555 &mut rng,
556 );
557
558 RlweCiphertext::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_rlwe_ct)
559 }
560
561 // Encrypt m as RGSW ciphertext RGSW(m) using supplied public key
562 pub(crate) fn _pk_encrypt_rgsw<T: Modulus<Element = u64> + Clone>(
563 m: &[u64],
564 public_key: &RlwePublicKey<Vec<Vec<u64>>, DefaultSecureRng>,
565 decomposer: &(DefaultDecomposer<u64>, DefaultDecomposer<u64>),
566 mod_op: &ModularOpsU64<T>,
567 ntt_op: &NttBackendU64,
568 ) -> RgswCiphertext<Vec<Vec<u64>>, T> {
569 let (_, ring_size) = Matrix::dimension(&public_key.data);
570 let gadget_vector_a = decomposer.a().gadget_vector();
571 let gadget_vector_b = decomposer.b().gadget_vector();
572
573 let mut rng = DefaultSecureRng::new();
574
575 assert!(m.len() == ring_size);
576
577 // public key encrypt RGSW(m1)
578 let mut rgsw_ct = RgswCiphertext::empty(ring_size, decomposer, mod_op.modulus().clone());
579 public_key_encrypt_rgsw(
580 &mut rgsw_ct.data,
581 m,
582 &public_key.data,
583 &gadget_vector_a,
584 &gadget_vector_b,
585 mod_op,
586 ntt_op,
587 &mut rng,
588 );
589
590 rgsw_ct
591 }
592
593 /// Encrypts m as RGSW ciphertext RGSW(m) using supplied secret key. Returns
594 /// unseeded RGSW ciphertext in coefficient domain
595 pub(crate) fn _sk_encrypt_rgsw<T: Modulus<Element = u64> + Clone>(
596 m: &[u64],
597 s: &[i32],
598 decomposer: &(DefaultDecomposer<u64>, DefaultDecomposer<u64>),
599 mod_op: &ModularOpsU64<T>,
600 ntt_op: &NttBackendU64,
601 ) -> SeededRgswCiphertext<Vec<Vec<u64>>, [u8; 32], T> {
602 let ring_size = s.len();
603 assert!(m.len() == s.len());
604
605 let q = mod_op.modulus();
606
607 let gadget_vector_a = decomposer.a().gadget_vector();
608 let gadget_vector_b = decomposer.b().gadget_vector();
609
610 let mut rng = DefaultSecureRng::new();
611 let mut rgsw_seed = [0u8; 32];
612 rng.fill_bytes(&mut rgsw_seed);
613 let mut seeded_rgsw_ct = SeededRgswCiphertext::<Vec<Vec<u64>>, [u8; 32], T>::empty(
614 ring_size as usize,
615 decomposer,
616 rgsw_seed,
617 q.clone(),
618 );
619 let mut p_rng = DefaultSecureRng::new_seeded(rgsw_seed);
620 secret_key_encrypt_rgsw(
621 &mut seeded_rgsw_ct.data,
622 m,
623 &gadget_vector_a,
624 &gadget_vector_b,
625 s,
626 mod_op,
627 ntt_op,
628 &mut p_rng,
629 &mut rng,
630 );
631 seeded_rgsw_ct
632 }
633
634 #[test]
635 fn rlwe_encrypt_decryption() {
636 let logq = 50;
637 let logp = 2;
638 let ring_size = 1 << 4;
639 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
640 let p = 1u64 << logp;
641
642 let mut rng = DefaultSecureRng::new();
643
644 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
645
646 // sample m0
647 let mut m0 = vec![0u64; ring_size as usize];
648 RandomFillUniformInModulus::<[u64], u64>::random_fill(
649 &mut rng,
650 &(1u64 << logp),
651 m0.as_mut_slice(),
652 );
653
654 let ntt_op = NttBackendU64::new(&q, ring_size as usize);
655 let mod_op = ModularOpsU64::new(q);
656
657 // encrypt m0
658 let encoded_m = m0
659 .iter()
660 .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
661 .collect_vec();
662 let rlwe_in_ct = _sk_encrypt_rlwe(&encoded_m, s.values(), &ntt_op, &mod_op);
663
664 let mut encoded_m_back = vec![0u64; ring_size as usize];
665 decrypt_rlwe(
666 &rlwe_in_ct,
667 s.values(),
668 &mut encoded_m_back,
669 &ntt_op,
670 &mod_op,
671 );
672 let m_back = encoded_m_back
673 .iter()
674 .map(|v| (((*v as f64 * p as f64) / q as f64).round() as u64) % p)
675 .collect_vec();
676 assert_eq!(m0, m_back);
677 }
678
679 #[test]
680 fn rlwe_by_rgsw_works() {
681 let logq = 50;
682 let logp = 2;
683 let ring_size = 1 << 9;
684 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
685 let p: u64 = 1u64 << logp;
686
687 let mut rng = DefaultSecureRng::new_seeded([0u8; 32]);
688
689 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
690
691 let mut m0 = vec![0u64; ring_size as usize];
692 RandomFillUniformInModulus::<[u64], _>::random_fill(
693 &mut rng,
694 &(1u64 << logp),
695 m0.as_mut_slice(),
696 );
697 let mut m1 = vec![0u64; ring_size as usize];
698 m1[thread_rng().gen_range(0..ring_size) as usize] = 1;
699
700 let ntt_op = NttBackendU64::new(&q, ring_size as usize);
701 let mod_op = ModularOpsU64::new(q);
702 let d_rgsw = 10;
703 let logb = 5;
704 let decomposer = (
705 DefaultDecomposer::new(q, logb, d_rgsw),
706 DefaultDecomposer::new(q, logb, d_rgsw),
707 );
708
709 // create public key
710 let mut pk_seed = [0u8; 32];
711 rng.fill_bytes(&mut pk_seed);
712 let mut pk_prng = DefaultSecureRng::new_seeded(pk_seed);
713 let mut seeded_pk =
714 SeededRlwePublicKey::<Vec<u64>, _>::empty(ring_size as usize, pk_seed, q);
715 rlwe_public_key(
716 &mut seeded_pk.data,
717 s.values(),
718 &ntt_op,
719 &mod_op,
720 &mut pk_prng,
721 &mut rng,
722 );
723 let pk = RlwePublicKey::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_pk);
724
725 // Encrypt m1 as RGSW(m1)
726 let rgsw_ct = {
727 //TODO(Jay): Figure out better way to test secret key and public key variant of
728 // RGSW ciphertext encryption within the same test
729
730 if true {
731 // Encryption m1 as RGSW(m1) using secret key
732 let seeded_rgsw_ct =
733 _sk_encrypt_rgsw(&m1, s.values(), &decomposer, &mod_op, &ntt_op);
734 RgswCiphertextEvaluationDomain::<Vec<Vec<u64>>, _,DefaultSecureRng, NttBackendU64>::from(&seeded_rgsw_ct)
735 } else {
736 // Encrypt m1 as RGSW(m1) using public key
737 let rgsw_ct = _pk_encrypt_rgsw(&m1, &pk, &decomposer, &mod_op, &ntt_op);
738 RgswCiphertextEvaluationDomain::<_, _, DefaultSecureRng, NttBackendU64>::from(
739 &rgsw_ct,
740 )
741 }
742 };
743
744 // Encrypt m0 as RLWE(m0)
745 let mut rlwe_in_ct = {
746 let encoded_m = m0
747 .iter()
748 .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
749 .collect_vec();
750
751 _sk_encrypt_rlwe(&encoded_m, s.values(), &ntt_op, &mod_op)
752 };
753
754 // RLWE(m0m1) = RLWE(m0) x RGSW(m1)
755 let mut scratch_space = vec![
756 vec![0u64; ring_size as usize];
757 std::cmp::max(
758 decomposer.a().decomposition_count(),
759 decomposer.b().decomposition_count()
760 ) + 2
761 ];
762
763 // rlwe x rgsw with additional RGSW ciphertexts in shoup repr
764 let rlwe_in_ct_shoup = {
765 let mut rlwe_in_ct_shoup = rlwe_in_ct.data.clone();
766
767 let rgsw_ct_shoup = ShoupRgswCiphertextEvaluationDomain::from(&rgsw_ct);
768
769 rlwe_by_rgsw_shoup(
770 &mut rlwe_in_ct_shoup,
771 &rgsw_ct.data,
772 &rgsw_ct_shoup.data,
773 &mut scratch_space,
774 &decomposer,
775 &ntt_op,
776 &mod_op,
777 false,
778 );
779
780 rlwe_in_ct_shoup
781 };
782
783 // rlwe x rgsw normal
784 {
785 rlwe_by_rgsw(
786 &mut rlwe_in_ct,
787 &rgsw_ct.data,
788 &mut scratch_space,
789 &decomposer,
790 &ntt_op,
791 &mod_op,
792 );
793 }
794
795 // output from both functions must be equal
796 {
797 assert_eq!(rlwe_in_ct.data, rlwe_in_ct_shoup);
798 }
799
800 // Decrypt RLWE(m0m1)
801 let mut encoded_m0m1_back = vec![0u64; ring_size as usize];
802 decrypt_rlwe(
803 &rlwe_in_ct,
804 s.values(),
805 &mut encoded_m0m1_back,
806 &ntt_op,
807 &mod_op,
808 );
809 let m0m1_back = encoded_m0m1_back
810 .iter()
811 .map(|v| (((*v as f64 * p as f64) / (q as f64)).round() as u64) % p)
812 .collect_vec();
813
814 let mul_mod = |v0: &u64, v1: &u64| (v0 * v1) % p;
815 let m0m1 = negacyclic_mul(&m0, &m1, mul_mod, p);
816
817 // {
818 // // measure noise
819 // let encoded_m_ideal = m0m1
820 // .iter()
821 // .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
822 // .collect_vec();
823
824 // let noise = measure_noise(&rlwe_in_ct, &encoded_m_ideal, &ntt_op,
825 // &mod_op, s.values()); println!("Noise RLWE(m0m1)(=
826 // RLWE(m0)xRGSW(m1)) : {noise}"); }
827
828 assert!(
829 m0m1 == m0m1_back,
830 "Expected {:?} \n Got {:?}",
831 m0m1,
832 m0m1_back
833 );
834 }
835
836 #[test]
837 fn galois_auto_works() {
838 let logq = 55;
839 let ring_size = 1 << 11;
840 let q = generate_prime(logq, 2 * ring_size, 1u64 << logq).unwrap();
841 let logp = 3;
842 let p = 1u64 << logp;
843 let d_rgsw = 5;
844 let logb = 11;
845
846 let mut rng = DefaultSecureRng::new();
847 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
848
849 let mut m = vec![0u64; ring_size as usize];
850 RandomFillUniformInModulus::random_fill(&mut rng, &p, m.as_mut_slice());
851 let encoded_m = m
852 .iter()
853 .map(|v| (((*v as f64 * q as f64) / (p as f64)).round() as u64))
854 .collect_vec();
855
856 let ntt_op = NttBackendU64::new(&q, ring_size as usize);
857 let mod_op = ModularOpsU64::new(q);
858
859 // RLWE_{s}(m)
860 let mut seed_rlwe = [0u8; 32];
861 rng.fill_bytes(&mut seed_rlwe);
862 let mut seeded_rlwe_m = SeededRlweCiphertext::empty(ring_size as usize, seed_rlwe, q);
863 let mut p_rng = DefaultSecureRng::new_seeded(seed_rlwe);
864 seeded_secret_key_encrypt_rlwe(
865 &encoded_m,
866 &mut seeded_rlwe_m.data,
867 s.values(),
868 &mod_op,
869 &ntt_op,
870 &mut p_rng,
871 &mut rng,
872 );
873 let mut rlwe_m = RlweCiphertext::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_rlwe_m);
874
875 let auto_k = -125;
876
877 // Generate galois key to key switch from s^k to s
878 let decomposer = DefaultDecomposer::new(q, logb, d_rgsw);
879 let mut seed_auto = [0u8; 32];
880 rng.fill_bytes(&mut seed_auto);
881 let mut seeded_auto_key =
882 SeededAutoKey::empty(ring_size as usize, &decomposer, seed_auto, q);
883 let mut p_rng = DefaultSecureRng::new_seeded(seed_auto);
884 let gadget_vector = decomposer.gadget_vector();
885 seeded_auto_key_gen(
886 &mut seeded_auto_key.data,
887 s.values(),
888 auto_k,
889 &gadget_vector,
890 &mod_op,
891 &ntt_op,
892 &mut p_rng,
893 &mut rng,
894 );
895 let auto_key =
896 AutoKeyEvaluationDomain::<Vec<Vec<u64>>, _, DefaultSecureRng, NttBackendU64>::from(
897 &seeded_auto_key,
898 );
899
900 // Send RLWE_{s}(m) -> RLWE_{s}(m^k)
901 let mut scratch_space = vec![vec![0u64; ring_size as usize]; d_rgsw + 2];
902 let (auto_map_index, auto_map_sign) = generate_auto_map(ring_size as usize, auto_k);
903
904 // galois auto with additional auto key in shoup repr
905 let rlwe_m_shoup = {
906 let auto_key_shoup = ShoupAutoKeyEvaluationDomain::from(&auto_key);
907 let mut rlwe_m_shoup = rlwe_m.data.clone();
908 galois_auto_shoup(
909 &mut rlwe_m_shoup,
910 &auto_key.data,
911 &auto_key_shoup.data,
912 &mut scratch_space,
913 &auto_map_index,
914 &auto_map_sign,
915 &mod_op,
916 &ntt_op,
917 &decomposer,
918 false,
919 );
920 rlwe_m_shoup
921 };
922
923 // normal galois auto
924 {
925 rlwe_auto(
926 &mut rlwe_m,
927 &auto_key.data,
928 &mut scratch_space,
929 &auto_map_index,
930 &auto_map_sign,
931 &mod_op,
932 &ntt_op,
933 &decomposer,
934 );
935 }
936
937 // rlwe out from both functions must be same
938 assert_eq!(rlwe_m.data, rlwe_m_shoup);
939
940 let rlwe_m_k = rlwe_m;
941
942 // Decrypt RLWE_{s}(m^k) and check
943 let mut encoded_m_k_back = vec![0u64; ring_size as usize];
944 decrypt_rlwe(
945 &rlwe_m_k,
946 s.values(),
947 &mut encoded_m_k_back,
948 &ntt_op,
949 &mod_op,
950 );
951 let m_k_back = encoded_m_k_back
952 .iter()
953 .map(|v| (((*v as f64 * p as f64) / q as f64).round() as u64) % p)
954 .collect_vec();
955
956 let mut m_k = vec![0u64; ring_size as usize];
957 // Send \delta m -> \delta m^k
958 izip!(m.iter(), auto_map_index.iter(), auto_map_sign.iter()).for_each(
959 |(v, to_index, sign)| {
960 if !*sign {
961 m_k[*to_index] = (p - *v) % p;
962 } else {
963 m_k[*to_index] = *v;
964 }
965 },
966 );
967
968 {
969 let encoded_m_k = m_k
970 .iter()
971 .map(|v| ((*v as f64 * q as f64) / p as f64).round() as u64)
972 .collect_vec();
973
974 let noise = measure_noise(&rlwe_m_k, &encoded_m_k, &ntt_op, &mod_op, s.values());
975 println!("Ksk noise: {noise}");
976 }
977
978 assert_eq!(m_k_back, m_k);
979 }
980
981 #[test]
982 fn sk_rgsw_by_rgsw() {
983 let logq = 60;
984 let logp = 2;
985 let ring_size = 1 << 11;
986 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
987 let p = 1u64 << logp;
988 let d_rgsw = 12;
989 let logb = 5;
990
991 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
992
993 let mut rng = DefaultSecureRng::new();
994 let ntt_op = NttBackendU64::new(&q, ring_size as usize);
995 let mod_op = ModularOpsU64::new(q);
996 let decomposer = (
997 DefaultDecomposer::new(q, logb, d_rgsw),
998 DefaultDecomposer::new(q, logb, d_rgsw),
999 );
1000
1001 let mul_mod = |a: &u64, b: &u64| ((*a as u128 * *b as u128) % q as u128) as u64;
1002
1003 let mut carry_m = vec![0u64; ring_size as usize];
1004 carry_m[thread_rng().gen_range(0..ring_size) as usize] = 1;
1005
1006 // RGSW(carry_m)
1007 let mut rgsw_carrym = {
1008 let seeded_rgsw = _sk_encrypt_rgsw(&carry_m, s.values(), &decomposer, &mod_op, &ntt_op);
1009 let mut rgsw_eval =
1010 RgswCiphertextEvaluationDomain::<_, _, DefaultSecureRng, NttBackendU64>::from(
1011 &seeded_rgsw,
1012 );
1013 rgsw_eval
1014 .data
1015 .iter_mut()
1016 .for_each(|ri| ntt_op.backward(ri.as_mut()));
1017 rgsw_eval.data
1018 };
1019
1020 let mut scratch_matrix = vec![
1021 vec![0u64; ring_size as usize];
1022 decomposer.a().decomposition_count() * 2
1023 + decomposer.b().decomposition_count() * 2
1024 + std::cmp::max(
1025 decomposer.a().decomposition_count(),
1026 decomposer.b().decomposition_count()
1027 )
1028 ];
1029
1030 // _measure_noise_rgsw(&rgsw_carrym, &carry_m, s.values(), &decomposer, &q);
1031
1032 for i in 0..2 {
1033 let mut m = vec![0u64; ring_size as usize];
1034 m[thread_rng().gen_range(0..ring_size) as usize] = if (i & 1) == 1 { q - 1 } else { 1 };
1035 let rgsw_m =
1036 RgswCiphertextEvaluationDomain::<_, _, DefaultSecureRng, NttBackendU64>::from(
1037 &_sk_encrypt_rgsw(&m, s.values(), &decomposer, &mod_op, &ntt_op),
1038 );
1039 rgsw_by_rgsw_inplace(
1040 &mut rgsw_carrym,
1041 decomposer.a().decomposition_count(),
1042 decomposer.b().decomposition_count(),
1043 &rgsw_m.data,
1044 &decomposer,
1045 &mut scratch_matrix,
1046 &ntt_op,
1047 &mod_op,
1048 );
1049
1050 // measure noise
1051 carry_m = negacyclic_mul(&carry_m, &m, mul_mod, q);
1052 println!("########### Noise RGSW(carrym) in {i}^th loop ###########");
1053 // _measure_noise_rgsw(&rgsw_carrym, &carry_m, s.values(),
1054 // &decomposer, &q);
1055 }
1056 {
1057 // RLWE(m) x RGSW(carry_m)
1058 let mut m = vec![0u64; ring_size as usize];
1059 RandomFillUniformInModulus::random_fill(&mut rng, &q, m.as_mut_slice());
1060 let mut rlwe_ct = _sk_encrypt_rlwe(&m, s.values(), &ntt_op, &mod_op);
1061
1062 // send rgsw to evaluation domain
1063 rgsw_carrym
1064 .iter_mut()
1065 .for_each(|ri| ntt_op.forward(ri.as_mut_slice()));
1066
1067 rlwe_by_rgsw(
1068 &mut rlwe_ct,
1069 &rgsw_carrym,
1070 &mut scratch_matrix,
1071 &decomposer,
1072 &ntt_op,
1073 &mod_op,
1074 );
1075 let m_expected = negacyclic_mul(&carry_m, &m, mul_mod, q);
1076 let noise = measure_noise(&rlwe_ct, &m_expected, &ntt_op, &mod_op, s.values());
1077 println!("RLWE(m) x RGSW(carry_m): {noise}");
1078 }
1079 }
1080
1081 #[test]
1082 fn some_work() {
1083 let logq = 55;
1084 let ring_size = 1 << 11;
1085 let q = generate_prime(logq, ring_size as u64, 1u64 << logq).unwrap();
1086 let d = 2;
1087 let logb = 12;
1088 let decomposer = DefaultDecomposer::new(q, logb, d);
1089
1090 let ntt_op = NttBackendU64::new(&q, ring_size as usize);
1091 let mod_op = ModularOpsU64::new(q);
1092 let mut rng = DefaultSecureRng::new();
1093
1094 let mut stats = Stats::new();
1095
1096 for _ in 0..10 {
1097 let mut a = vec![0u64; ring_size];
1098 RandomFillUniformInModulus::random_fill(&mut rng, &q, a.as_mut());
1099 let mut m = vec![0u64; ring_size];
1100 RandomFillGaussianInModulus::random_fill(&mut rng, &q, m.as_mut());
1101
1102 let mut sk = vec![0u64; ring_size];
1103 RandomFillGaussianInModulus::random_fill(&mut rng, &q, sk.as_mut());
1104 let mut sk_eval = sk.clone();
1105 ntt_op.forward(sk_eval.as_mut_slice());
1106
1107 let gadget_vector = decomposer.gadget_vector();
1108
1109 // ksk (beta e)
1110 let mut ksk_part_b = vec![vec![0u64; ring_size]; decomposer.decomposition_count()];
1111 let mut ksk_part_a = vec![vec![0u64; ring_size]; decomposer.decomposition_count()];
1112 izip!(
1113 ksk_part_b.iter_rows_mut(),
1114 ksk_part_a.iter_rows_mut(),
1115 gadget_vector.iter()
1116 )
1117 .for_each(|(part_b, part_a, beta)| {
1118 RandomFillUniformInModulus::random_fill(&mut rng, &q, part_a.as_mut());
1119
1120 // a * s
1121 let mut tmp = part_a.to_vec();
1122 ntt_op.forward(tmp.as_mut());
1123 mod_op.elwise_mul_mut(tmp.as_mut(), sk_eval.as_ref());
1124 ntt_op.backward(tmp.as_mut());
1125
1126 // a*s + e + beta m
1127 RandomFillGaussianInModulus::random_fill(&mut rng, &q, part_b.as_mut());
1128 // println!("E: {:?}", &part_b);
1129 // a*s + e
1130 mod_op.elwise_add_mut(part_b.as_mut_slice(), tmp.as_ref());
1131 // a*s + e + beta m
1132 let mut tmp = m.to_vec();
1133 mod_op.elwise_scalar_mul_mut(tmp.as_mut_slice(), beta);
1134 mod_op.elwise_add_mut(part_b.as_mut_slice(), tmp.as_ref());
1135 });
1136
1137 // decompose a
1138 let mut decomposed_a = vec![vec![0u64; ring_size]; decomposer.decomposition_count()];
1139 a.iter().enumerate().for_each(|(ri, el)| {
1140 decomposer
1141 .decompose_iter(el)
1142 .into_iter()
1143 .enumerate()
1144 .for_each(|(j, d_el)| {
1145 decomposed_a[j][ri] = d_el;
1146 });
1147 });
1148
1149 // println!("Last limb");
1150
1151 // decomp_a * ksk(beta m)
1152 ksk_part_b
1153 .iter_mut()
1154 .for_each(|r| ntt_op.forward(r.as_mut_slice()));
1155 ksk_part_a
1156 .iter_mut()
1157 .for_each(|r| ntt_op.forward(r.as_mut_slice()));
1158 decomposed_a
1159 .iter_mut()
1160 .for_each(|r| ntt_op.forward(r.as_mut_slice()));
1161 let mut out = vec![vec![0u64; ring_size]; 2];
1162 izip!(decomposed_a.iter(), ksk_part_b.iter(), ksk_part_a.iter()).for_each(
1163 |(d_a, part_b, part_a)| {
1164 // out_a += d_a * part_a
1165 let mut d_a_clone = d_a.clone();
1166 mod_op.elwise_mul_mut(d_a_clone.as_mut_slice(), part_a.as_ref());
1167 mod_op.elwise_add_mut(out[0].as_mut_slice(), d_a_clone.as_ref());
1168
1169 // out_b += d_a * part_b
1170 let mut d_a_clone = d_a.clone();
1171 mod_op.elwise_mul_mut(d_a_clone.as_mut_slice(), part_b.as_ref());
1172 mod_op.elwise_add_mut(out[1].as_mut_slice(), d_a_clone.as_ref());
1173 },
1174 );
1175 out.iter_mut()
1176 .for_each(|r| ntt_op.backward(r.as_mut_slice()));
1177
1178 let out_back = {
1179 // decrypt
1180 // a*s
1181 ntt_op.forward(out[0].as_mut());
1182 mod_op.elwise_mul_mut(out[0].as_mut(), sk_eval.as_ref());
1183 ntt_op.backward(out[0].as_mut());
1184
1185 // b - a*s
1186 let tmp = (out[0]).clone();
1187 mod_op.elwise_sub_mut(out[1].as_mut(), tmp.as_ref());
1188 out.remove(1)
1189 };
1190
1191 let out_expected = {
1192 let mut a_clone = a.clone();
1193 let mut m_clone = m.clone();
1194
1195 ntt_op.forward(a_clone.as_mut_slice());
1196 ntt_op.forward(m_clone.as_mut_slice());
1197
1198 mod_op.elwise_mul_mut(a_clone.as_mut_slice(), m_clone.as_mut_slice());
1199 ntt_op.backward(a_clone.as_mut_slice());
1200 a_clone
1201 };
1202
1203 let mut diff = out_expected;
1204 mod_op.elwise_sub_mut(diff.as_mut_slice(), out_back.as_ref());
1205 stats.add_more(&Vec::<i64>::try_convert_from(diff.as_ref(), &q));
1206 }
1207
1208 println!("Std: {}", stats.std_dev().abs().log2());
1209 }
1210}