phantom-zone/src/rgsw.rs
src/rgsw.rsRaw
1use itertools::izip;
2
3use crate::{
4 backend::VectorOps,
5 decomposer::{self, Decomposer},
6 ntt::Ntt,
7 random::{DefaultSecureRng, RandomGaussianDist, RandomUniformDist},
8 utils::{fill_random_ternary_secret_with_hamming_weight, TryConvertFrom, WithLocal},
9 Matrix, MatrixEntity, MatrixMut, RowMut, Secret,
10};
11
12struct RlweSecret {
13 values: Vec<i32>,
14}
15
16impl Secret for RlweSecret {
17 type Element = i32;
18 fn values(&self) -> &[Self::Element] {
19 &self.values
20 }
21}
22
23impl RlweSecret {
24 fn random(hw: usize, n: usize) -> RlweSecret {
25 DefaultSecureRng::with_local_mut(|rng| {
26 let mut out = vec![0i32; n];
27 fill_random_ternary_secret_with_hamming_weight(&mut out, hw, rng);
28
29 RlweSecret { values: out }
30 })
31 }
32}
33
34/// Encrypts message m as a RGSW ciphertext.
35///
36/// - m_eval: is `m` is evaluation domain
37/// - out_rgsw: RGSW(m) is stored as single matrix of dimension (d_rgsw * 4,
38/// ring_size). The matrix has the following structure [RLWE'_A(-sm) ||
39/// RLWE'_B(-sm) || RLWE'_A(m) || RLWE'_B(m)]^T
40fn encrypt_rgsw<
41 Mmut: MatrixMut + MatrixEntity,
42 M: Matrix<MatElement = Mmut::MatElement> + Clone,
43 S: Secret,
44 R: RandomGaussianDist<[Mmut::MatElement], Parameters = Mmut::MatElement>
45 + RandomUniformDist<[Mmut::MatElement], Parameters = Mmut::MatElement>,
46 ModOp: VectorOps<Element = Mmut::MatElement>,
47 NttOp: Ntt<Element = Mmut::MatElement>,
48>(
49 out_rgsw: &mut Mmut,
50 m_eval: &M,
51 gadget_vector: &[Mmut::MatElement],
52 s: &S,
53 mod_op: &ModOp,
54 ntt_op: &NttOp,
55 rng: &mut R,
56) where
57 <Mmut as Matrix>::R: RowMut,
58 Mmut: TryConvertFrom<[S::Element], Parameters = Mmut::MatElement>,
59{
60 let d = gadget_vector.len();
61 let q = mod_op.modulus();
62 let ring_size = s.values().len();
63 assert!(out_rgsw.dimension() == (d * 4, ring_size));
64 assert!(m_eval.dimension() == (1, ring_size));
65
66 // RLWE(-sm), RLWE(-sm)
67 let (rlwe_dash_nsm, rlwe_dash_m) = out_rgsw.split_at_row(d * 2);
68
69 let mut s_eval = Mmut::try_convert_from(s.values(), &q);
70 ntt_op.forward(s_eval.get_row_mut(0).as_mut());
71
72 let mut scratch_space = Mmut::zeros(1, ring_size);
73
74 // RLWE'(-sm)
75 let (a_rlwe_dash_nsm, b_rlwe_dash_nsm) = rlwe_dash_nsm.split_at_mut(d);
76 izip!(
77 a_rlwe_dash_nsm.iter_mut(),
78 b_rlwe_dash_nsm.iter_mut(),
79 gadget_vector.iter()
80 )
81 .for_each(|(ai, bi, beta_i)| {
82 // Sample a_i and transform to evaluation domain
83 RandomUniformDist::random_fill(rng, &q, ai.as_mut());
84 ntt_op.forward(ai.as_mut());
85
86 // a_i * s
87 mod_op.elwise_mul(
88 scratch_space.get_row_mut(0),
89 ai.as_ref(),
90 s_eval.get_row_slice(0),
91 );
92 // b_i = e_i + a_i * s
93 RandomGaussianDist::random_fill(rng, &q, bi.as_mut());
94 ntt_op.forward(bi.as_mut());
95 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.get_row_slice(0));
96
97 // a_i + \beta_i * m
98 mod_op.elwise_scalar_mul(
99 scratch_space.get_row_mut(0),
100 m_eval.get_row_slice(0),
101 beta_i,
102 );
103 mod_op.elwise_add_mut(ai.as_mut(), scratch_space.get_row_slice(0));
104 });
105
106 // RLWE(m)
107 let (a_rlwe_dash_m, b_rlwe_dash_m) = rlwe_dash_m.split_at_mut(d);
108 izip!(
109 a_rlwe_dash_m.iter_mut(),
110 b_rlwe_dash_m.iter_mut(),
111 gadget_vector.iter()
112 )
113 .for_each(|(ai, bi, beta_i)| {
114 // Sample e_i and transform to evaluation domain
115 RandomGaussianDist::random_fill(rng, &q, bi.as_mut());
116 ntt_op.forward(bi.as_mut());
117
118 // beta_i * m
119 mod_op.elwise_scalar_mul(
120 scratch_space.get_row_mut(0),
121 m_eval.get_row_slice(0),
122 beta_i,
123 );
124 // e_i + beta_i * m
125 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.get_row_slice(0));
126
127 // Sample a_i and transform to evaluation domain
128 RandomUniformDist::random_fill(rng, &q, ai.as_mut());
129 ntt_op.forward(ai.as_mut());
130
131 // ai * s
132 mod_op.elwise_mul(
133 scratch_space.get_row_mut(0),
134 ai.as_ref(),
135 s_eval.get_row_slice(0),
136 );
137
138 // b_i = a_i*s + e_i + beta_i*m
139 mod_op.elwise_add_mut(bi.as_mut(), scratch_space.get_row_slice(0));
140 });
141}
142
143/// Returns RLWE(mm') = RLWE(m) x RGSW(m')
144///
145/// - rgsw_in: RGSW(m') in evaluation domain
146/// - rlwe_in_decomposed: decomposed RLWE(m) in evaluation domain
147/// - rlwe_out: returned RLWE(mm') in evaluation domain
148fn rlwe_in_decomposed_evaluation_domain_mul_rgsw_rlwe_out_evaluation_domain<
149 Mmut: MatrixMut + MatrixEntity,
150 M: Matrix<MatElement = Mmut::MatElement> + Clone,
151 ModOp: VectorOps<Element = Mmut::MatElement>,
152>(
153 rgsw_in: &M,
154 rlwe_in_decomposed_eval: &Mmut,
155 rlwe_out_eval: &mut Mmut,
156 mod_op: &ModOp,
157) where
158 <Mmut as Matrix>::R: RowMut,
159{
160 let ring_size = rgsw_in.dimension().1;
161 let d_rgsw = rgsw_in.dimension().0 / 4;
162 assert!(rlwe_in_decomposed_eval.dimension() == (2 * d_rgsw, ring_size));
163 assert!(rlwe_out_eval.dimension() == (2, ring_size));
164
165 let (a_rlwe_out, b_rlwe_out) = rlwe_out_eval.split_at_row(1);
166
167 // a * RLWE'(-sm)
168 let a_rlwe_dash_nsm = rgsw_in.iter_rows().take(d_rgsw);
169 let b_rlwe_dash_nsm = rgsw_in.iter_rows().skip(d_rgsw).take(d_rgsw);
170 izip!(
171 rlwe_in_decomposed_eval.iter_rows().take(d_rgsw),
172 a_rlwe_dash_nsm
173 )
174 .for_each(|(a, b)| {
175 mod_op.elwise_fma_mut(a_rlwe_out[0].as_mut(), a.as_ref(), b.as_ref());
176 });
177 izip!(
178 rlwe_in_decomposed_eval.iter_rows().take(d_rgsw),
179 b_rlwe_dash_nsm
180 )
181 .for_each(|(a, b)| {
182 mod_op.elwise_fma_mut(b_rlwe_out[0].as_mut(), a.as_ref(), b.as_ref());
183 });
184
185 // b * RLWE'(m)
186 let a_rlwe_dash_m = rgsw_in.iter_rows().skip(d_rgsw * 2).take(d_rgsw);
187 let b_rlwe_dash_m = rgsw_in.iter_rows().skip(d_rgsw * 3);
188 izip!(
189 rlwe_in_decomposed_eval.iter_rows().skip(d_rgsw),
190 a_rlwe_dash_m
191 )
192 .for_each(|(a, b)| {
193 mod_op.elwise_fma_mut(a_rlwe_out[0].as_mut(), a.as_ref(), b.as_ref());
194 });
195 izip!(
196 rlwe_in_decomposed_eval.iter_rows().skip(d_rgsw),
197 b_rlwe_dash_m
198 )
199 .for_each(|(a, b)| {
200 mod_op.elwise_fma_mut(b_rlwe_out[0].as_mut(), a.as_ref(), b.as_ref());
201 });
202}
203
204fn decompose_rlwe<
205 M: Matrix + Clone,
206 Mmut: MatrixMut<MatElement = M::MatElement> + MatrixEntity,
207 D: Decomposer<Element = M::MatElement>,
208>(
209 rlwe_in: &M,
210 decomposer: &D,
211 rlwe_in_decomposed: &mut Mmut,
212) where
213 M::MatElement: Copy,
214 <Mmut as Matrix>::R: RowMut,
215{
216 let d_rgsw = decomposer.d();
217 let ring_size = rlwe_in.dimension().1;
218 assert!(rlwe_in_decomposed.dimension() == (2 * d_rgsw, ring_size));
219
220 // Decompose rlwe_in
221 for ri in 0..ring_size {
222 // ai
223 let ai_decomposed = decomposer.decompose(rlwe_in.get(0, ri));
224 for j in 0..d_rgsw {
225 rlwe_in_decomposed.set(j, ri, ai_decomposed[j]);
226 }
227
228 // bi
229 let bi_decomposed = decomposer.decompose(rlwe_in.get(1, ri));
230 for j in 0..d_rgsw {
231 rlwe_in_decomposed.set(j + d_rgsw, ri, bi_decomposed[j]);
232 }
233 }
234}
235
236/// Returns RLWE(m0m1) = RLWE(m0) x RGSW(m1)
237///
238/// - rlwe_in: is RLWE(m0) with polynomials in coefficient domain
239/// - rgsw_in: is RGSW(m1) with polynomials in evaluation domain
240/// - rlwe_out: is output RLWE(m0m1) with polynomials in coefficient domain
241/// - rlwe_in_decomposed: is a matrix of dimension (d_rgsw * 2, ring_size) used
242/// as scratch space to store decomposed RLWE(m0)
243fn rlwe_by_rgsw<
244 M: Matrix + Clone,
245 Mmut: MatrixMut<MatElement = M::MatElement> + MatrixEntity,
246 D: Decomposer<Element = M::MatElement>,
247 ModOp: VectorOps<Element = M::MatElement>,
248 NttOp: Ntt<Element = M::MatElement>,
249>(
250 rlwe_in: &M,
251 rgsw_in: &M,
252 rlwe_out: &mut Mmut,
253 rlwe_in_decomposed: &mut Mmut,
254 decomposer: &D,
255 ntt_op: &NttOp,
256 mod_op: &ModOp,
257) where
258 M::MatElement: Copy,
259 <Mmut as Matrix>::R: RowMut,
260{
261 decompose_rlwe(rlwe_in, decomposer, rlwe_in_decomposed);
262
263 // transform rlwe_in decomposed to evaluation domain
264 rlwe_in_decomposed
265 .iter_rows_mut()
266 .for_each(|r| ntt_op.forward(r.as_mut()));
267
268 // decomposed RLWE x RGSW
269 rlwe_in_decomposed_evaluation_domain_mul_rgsw_rlwe_out_evaluation_domain(
270 rgsw_in,
271 rlwe_in_decomposed,
272 rlwe_out,
273 mod_op,
274 );
275
276 // transform rlwe_out to coefficient domain
277 rlwe_out
278 .iter_rows_mut()
279 .for_each(|r| ntt_op.backward(r.as_mut()));
280}
281
282/// Encrypt polynomial m(X) as RLWE ciphertext.
283///
284/// - rlwe_out: returned RLWE ciphertext RLWE(m) in coefficient domain. RLWE
285/// ciphertext is a matirx with first row consiting polynomial `a` and the
286/// second rows consting polynomial `b`
287fn encrypt_rlwe<
288 Mmut: Matrix + MatrixMut + Clone,
289 ModOp: VectorOps<Element = Mmut::MatElement>,
290 NttOp: Ntt<Element = Mmut::MatElement>,
291 S: Secret,
292 R: RandomUniformDist<[Mmut::MatElement], Parameters = Mmut::MatElement>
293 + RandomGaussianDist<[Mmut::MatElement], Parameters = Mmut::MatElement>,
294>(
295 m: &Mmut,
296 rlwe_out: &mut Mmut,
297 s: &S,
298 mod_op: &ModOp,
299 ntt_op: &NttOp,
300 rng: &mut R,
301) where
302 <Mmut as Matrix>::R: RowMut,
303 Mmut: TryConvertFrom<[S::Element], Parameters = Mmut::MatElement>,
304{
305 let ring_size = s.values().len();
306 assert!(rlwe_out.dimension() == (2, ring_size));
307 assert!(m.dimension() == (1, ring_size));
308
309 let q = mod_op.modulus();
310
311 // sample a
312 RandomUniformDist::random_fill(rng, &q, rlwe_out.get_row_mut(0));
313
314 // s * a
315 let mut sa = Mmut::try_convert_from(s.values(), &q);
316 ntt_op.forward(sa.get_row_mut(0));
317 ntt_op.forward(rlwe_out.get_row_mut(0));
318 mod_op.elwise_mul_mut(sa.get_row_mut(0), rlwe_out.get_row_slice(0));
319 ntt_op.backward(rlwe_out.get_row_mut(0));
320 ntt_op.backward(sa.get_row_mut(0));
321
322 // sample e
323 RandomGaussianDist::random_fill(rng, &q, rlwe_out.get_row_mut(1));
324 mod_op.elwise_add_mut(rlwe_out.get_row_mut(1), m.get_row_slice(0));
325 mod_op.elwise_add_mut(rlwe_out.get_row_mut(1), sa.get_row_slice(0));
326}
327
328/// Decrypts degree 1 RLWE ciphertext RLWE(m) and returns m
329///
330/// - rlwe_ct: input degree 1 ciphertext RLWE(m).
331fn decrypt_rlwe<
332 Mmut: MatrixMut + Clone,
333 M: Matrix<MatElement = Mmut::MatElement>,
334 ModOp: VectorOps<Element = Mmut::MatElement>,
335 NttOp: Ntt<Element = Mmut::MatElement>,
336 S: Secret,
337>(
338 rlwe_ct: &M,
339 s: &S,
340 m_out: &mut Mmut,
341 ntt_op: &NttOp,
342 mod_op: &ModOp,
343) where
344 <Mmut as Matrix>::R: RowMut,
345 Mmut: TryConvertFrom<[S::Element], Parameters = Mmut::MatElement>,
346 Mmut::MatElement: Copy,
347{
348 let ring_size = s.values().len();
349 assert!(rlwe_ct.dimension() == (2, ring_size));
350 assert!(m_out.dimension() == (1, ring_size));
351
352 // transform a to evluation form
353 m_out
354 .get_row_mut(0)
355 .copy_from_slice(rlwe_ct.get_row_slice(0));
356 ntt_op.forward(m_out.get_row_mut(0));
357
358 // -s*a
359 let mut s = Mmut::try_convert_from(&s.values(), &mod_op.modulus());
360 ntt_op.forward(s.get_row_mut(0));
361 mod_op.elwise_mul_mut(m_out.get_row_mut(0), s.get_row_slice(0));
362 mod_op.elwise_neg_mut(m_out.get_row_mut(0));
363 ntt_op.backward(m_out.get_row_mut(0));
364
365 // m+e = b - s*a
366 mod_op.elwise_add_mut(m_out.get_row_mut(0), rlwe_ct.get_row_slice(1));
367}
368
369#[cfg(test)]
370mod tests {
371 use std::vec;
372
373 use itertools::Itertools;
374 use rand::{thread_rng, Rng};
375
376 use crate::{
377 backend::ModularOpsU64,
378 decomposer::{gadget_vector, DefaultDecomposer},
379 ntt::{self, Ntt, NttBackendU64},
380 random::{DefaultSecureRng, RandomUniformDist},
381 utils::{generate_prime, negacyclic_mul},
382 };
383
384 use super::{decrypt_rlwe, encrypt_rgsw, encrypt_rlwe, rlwe_by_rgsw, RlweSecret};
385
386 #[test]
387 fn rlwe_by_rgsw_works() {
388 let logq = 50;
389 let logp = 3;
390 let ring_size = 1 << 10;
391 let q = generate_prime(logq, ring_size, 1u64 << logq).unwrap();
392 let p = 1u64 << logp;
393 let d_rgsw = 10;
394 let logb = 5;
395
396 let mut rng = DefaultSecureRng::new();
397
398 let s = RlweSecret::random((ring_size >> 1) as usize, ring_size as usize);
399
400 let mut m0 = vec![0u64; ring_size as usize];
401 RandomUniformDist::<[u64]>::random_fill(&mut rng, &(1u64 << logp), m0.as_mut_slice());
402 let mut m1 = vec![0u64; ring_size as usize];
403 m1[thread_rng().gen_range(0..ring_size) as usize] = 1;
404
405 let ntt_op = NttBackendU64::new(q, ring_size as usize);
406 let mod_op = ModularOpsU64::new(q);
407
408 // Encrypt m1 as RGSW(m1)
409 let mut rgsw_ct = vec![vec![0u64; ring_size as usize]; d_rgsw * 4];
410 let gadget_vector = gadget_vector(logq, logb, d_rgsw);
411 let mut m1_eval = m1.clone();
412 ntt_op.forward(&mut m1_eval);
413 encrypt_rgsw(
414 &mut rgsw_ct,
415 &vec![m1_eval],
416 &gadget_vector,
417 &s,
418 &mod_op,
419 &ntt_op,
420 &mut rng,
421 );
422 // println!("RGSW(m1): {:?}", &rgsw_ct);
423
424 // Encrypt m0 as RLWE(m0)
425 let mut rlwe_in_ct = vec![vec![0u64; ring_size as usize]; 2];
426 let encoded_m = m0
427 .iter()
428 .map(|v| (((*v as f64) * q as f64) / (p as f64)).round() as u64)
429 .collect_vec();
430 encrypt_rlwe(
431 &vec![encoded_m.clone()],
432 &mut rlwe_in_ct,
433 &s,
434 &mod_op,
435 &ntt_op,
436 &mut rng,
437 );
438
439 // RLWE(m0m1) = RLWE(m0) x RGSW(m1)
440 let mut rlwe_out_ct = vec![vec![0u64; ring_size as usize]; 2];
441 let mut scratch_space = vec![vec![0u64; ring_size as usize]; d_rgsw * 2];
442 let decomposer = DefaultDecomposer::new(q, logb, d_rgsw);
443 rlwe_by_rgsw(
444 &rlwe_in_ct,
445 &rgsw_ct,
446 &mut rlwe_out_ct,
447 &mut scratch_space,
448 &decomposer,
449 &ntt_op,
450 &mod_op,
451 );
452
453 // Decrypt RLWE(m0m1)
454 let mut encoded_m0m1_back = vec![vec![0u64; ring_size as usize]];
455 decrypt_rlwe(&rlwe_out_ct, &s, &mut encoded_m0m1_back, &ntt_op, &mod_op);
456 let m0m1_back = encoded_m0m1_back[0]
457 .iter()
458 .map(|v| (((*v as f64 * p as f64) / (q as f64)).round() as u64) % p)
459 .collect_vec();
460
461 let mul_mod = |v0: &u64, v1: &u64| (v0 * v1) % p;
462 let m0m1 = negacyclic_mul(&m0, &m1, mul_mod, p);
463 assert_eq!(m0m1, m0m1_back, "Expected {:?} got {:?}", m0m1, m0m1_back);
464 // dbg!(&m0m1_back, m0m1, q);
465 }
466}