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