phantom-zone/src/lwe.rs
src/lwe.rsRaw
1use std::{
2 cell::RefCell,
3 collections::btree_map::Values,
4 fmt::{Debug, Display},
5 marker::PhantomData,
6};
7
8use itertools::{izip, Itertools};
9use num_traits::{abs, PrimInt, ToPrimitive, Zero};
10
11use crate::{
12 backend::{ArithmeticOps, VectorOps},
13 decomposer::Decomposer,
14 lwe,
15 num::UnsignedInteger,
16 random::{DefaultSecureRng, NewWithSeed, RandomGaussianDist, RandomUniformDist, DEFAULT_RNG},
17 utils::{fill_random_ternary_secret_with_hamming_weight, TryConvertFrom, WithLocal},
18 Matrix, MatrixEntity, MatrixMut, Row, RowEntity, RowMut, Secret,
19};
20
21struct SeededLweKeySwitchingKey<Ro, S>
22where
23 Ro: Row,
24{
25 data: Ro,
26 seed: S,
27 to_lwe_n: usize,
28 modulus: Ro::Element,
29}
30
31impl<Ro: RowEntity, S> SeededLweKeySwitchingKey<Ro, S> {
32 pub(crate) fn empty(
33 from_lwe_n: usize,
34 to_lwe_n: usize,
35 d: usize,
36 seed: S,
37 modulus: Ro::Element,
38 ) -> Self {
39 let data = Ro::zeros(from_lwe_n * d);
40 SeededLweKeySwitchingKey {
41 data,
42 to_lwe_n,
43 seed,
44 modulus,
45 }
46 }
47}
48
49struct LweKeySwitchingKey<M, R> {
50 data: M,
51 _phantom: PhantomData<R>,
52}
53
54impl<
55 M: MatrixMut + MatrixEntity,
56 R: NewWithSeed + RandomUniformDist<[M::MatElement], Parameters = M::MatElement>,
57 > From<&SeededLweKeySwitchingKey<M::R, R::Seed>> for LweKeySwitchingKey<M, R>
58where
59 M::R: RowMut,
60 R::Seed: Clone,
61 M::MatElement: Copy,
62{
63 fn from(value: &SeededLweKeySwitchingKey<M::R, R::Seed>) -> Self {
64 let mut p_rng = R::new_with_seed(value.seed.clone());
65 let mut data = M::zeros(value.data.as_ref().len(), value.to_lwe_n + 1);
66 izip!(value.data.as_ref().iter(), data.iter_rows_mut()).for_each(|(bi, lwe_i)| {
67 RandomUniformDist::random_fill(&mut p_rng, &value.modulus, &mut lwe_i.as_mut()[1..]);
68 lwe_i.as_mut()[0] = *bi;
69 });
70 LweKeySwitchingKey {
71 data,
72 _phantom: PhantomData,
73 }
74 }
75}
76
77trait LweCiphertext<M: Matrix> {}
78
79#[derive(Clone)]
80pub struct LweSecret {
81 pub(crate) values: Vec<i32>,
82}
83
84impl Secret for LweSecret {
85 type Element = i32;
86 fn values(&self) -> &[Self::Element] {
87 &self.values
88 }
89}
90
91impl LweSecret {
92 pub(crate) fn random(hw: usize, n: usize) -> LweSecret {
93 DefaultSecureRng::with_local_mut(|rng| {
94 let mut out = vec![0i32; n];
95 fill_random_ternary_secret_with_hamming_weight(&mut out, hw, rng);
96
97 LweSecret { values: out }
98 })
99 }
100}
101
102pub(crate) fn lwe_key_switch<
103 M: Matrix,
104 Ro: AsMut<[M::MatElement]> + AsRef<[M::MatElement]>,
105 Op: VectorOps<Element = M::MatElement> + ArithmeticOps<Element = M::MatElement>,
106 D: Decomposer<Element = M::MatElement>,
107>(
108 lwe_out: &mut Ro,
109 lwe_in: &Ro,
110 lwe_ksk: &M,
111 operator: &Op,
112 decomposer: &D,
113) {
114 assert!(
115 lwe_ksk.dimension().0 == ((lwe_in.as_ref().len() - 1) * decomposer.decomposition_count())
116 );
117 assert!(lwe_out.as_ref().len() == lwe_ksk.dimension().1);
118
119 let lwe_in_a_decomposed = lwe_in
120 .as_ref()
121 .iter()
122 .skip(1)
123 .flat_map(|ai| decomposer.decompose(ai));
124 izip!(lwe_in_a_decomposed, lwe_ksk.iter_rows()).for_each(|(ai_j, beta_ij_lwe)| {
125 operator.elwise_fma_scalar_mut(lwe_out.as_mut(), beta_ij_lwe.as_ref(), &ai_j);
126 });
127
128 let out_b = operator.add(&lwe_out.as_ref()[0], &lwe_in.as_ref()[0]);
129 lwe_out.as_mut()[0] = out_b;
130}
131
132pub fn lwe_ksk_keygen<
133 Ro: Row + RowMut + RowEntity,
134 S,
135 Op: VectorOps<Element = Ro::Element> + ArithmeticOps<Element = Ro::Element>,
136 R: RandomGaussianDist<Ro::Element, Parameters = Ro::Element>,
137 PR: RandomUniformDist<[Ro::Element], Parameters = Ro::Element>,
138>(
139 from_lwe_sk: &[S],
140 to_lwe_sk: &[S],
141 ksk_out: &mut Ro,
142 gadget: &[Ro::Element],
143 operator: &Op,
144 p_rng: &mut PR,
145 rng: &mut R,
146) where
147 Ro: TryConvertFrom<[S], Parameters = Ro::Element>,
148 Ro::Element: Zero + Debug,
149{
150 assert!(ksk_out.as_ref().len() == (from_lwe_sk.len() * gadget.len()));
151
152 let d = gadget.len();
153
154 let modulus = VectorOps::modulus(operator);
155 let mut neg_sk_in_m = Ro::try_convert_from(from_lwe_sk, &modulus);
156 operator.elwise_neg_mut(neg_sk_in_m.as_mut());
157 let sk_out_m = Ro::try_convert_from(to_lwe_sk, &modulus);
158
159 let mut scratch = Ro::zeros(to_lwe_sk.len());
160
161 izip!(neg_sk_in_m.as_ref(), ksk_out.as_mut().chunks_mut(d)).for_each(
162 |(neg_sk_in_si, d_lwes_partb)| {
163 izip!(gadget.iter(), d_lwes_partb.into_iter()).for_each(|(f, lwe_b)| {
164 // sample `a`
165 RandomUniformDist::random_fill(p_rng, &modulus, scratch.as_mut());
166
167 // a * z
168 let mut az = Ro::Element::zero();
169 izip!(scratch.as_ref().iter(), sk_out_m.as_ref()).for_each(|(ai, si)| {
170 let ai_si = operator.mul(ai, si);
171 az = operator.add(&az, &ai_si);
172 });
173
174 // a*z + (-s_i)*\beta^j + e
175 let mut b = operator.add(&az, &operator.mul(f, neg_sk_in_si));
176 let mut e = Ro::Element::zero();
177 RandomGaussianDist::random_fill(rng, &modulus, &mut e);
178 b = operator.add(&b, &e);
179
180 *lwe_b = b;
181 })
182 },
183 );
184}
185
186/// Encrypts encoded message m as LWE ciphertext
187pub fn encrypt_lwe<
188 Ro: Row + RowMut,
189 R: RandomGaussianDist<Ro::Element, Parameters = Ro::Element>
190 + RandomUniformDist<[Ro::Element], Parameters = Ro::Element>,
191 S,
192 Op: ArithmeticOps<Element = Ro::Element>,
193>(
194 lwe_out: &mut Ro,
195 m: &Ro::Element,
196 s: &[S],
197 operator: &Op,
198 rng: &mut R,
199) where
200 Ro: TryConvertFrom<[S], Parameters = Ro::Element>,
201 Ro::Element: Zero,
202{
203 let s = Ro::try_convert_from(s, &operator.modulus());
204 assert!(s.as_ref().len() == (lwe_out.as_ref().len() - 1));
205
206 // a*s
207 RandomUniformDist::random_fill(rng, &operator.modulus(), &mut lwe_out.as_mut()[1..]);
208 let mut sa = Ro::Element::zero();
209 izip!(lwe_out.as_mut().iter().skip(1), s.as_ref()).for_each(|(ai, si)| {
210 let tmp = operator.mul(ai, si);
211 sa = operator.add(&tmp, &sa);
212 });
213
214 // b = a*s + e + m
215 let mut e = Ro::Element::zero();
216 RandomGaussianDist::random_fill(rng, &operator.modulus(), &mut e);
217 let b = operator.add(&operator.add(&sa, &e), m);
218 lwe_out.as_mut()[0] = b;
219}
220
221pub fn decrypt_lwe<Ro: Row, Op: ArithmeticOps<Element = Ro::Element>, S>(
222 lwe_ct: &Ro,
223 s: &[S],
224 operator: &Op,
225) -> Ro::Element
226where
227 Ro: TryConvertFrom<[S], Parameters = Ro::Element>,
228 Ro::Element: Zero,
229{
230 let s = Ro::try_convert_from(s, &operator.modulus());
231
232 let mut sa = Ro::Element::zero();
233 izip!(lwe_ct.as_ref().iter().skip(1), s.as_ref()).for_each(|(ai, si)| {
234 let tmp = operator.mul(ai, si);
235 sa = operator.add(&tmp, &sa);
236 });
237
238 let b = &lwe_ct.as_ref()[0];
239 operator.sub(b, &sa)
240}
241
242/// Measures noise in input LWE ciphertext with reference of `ideal_m`
243///
244/// - ct: Input LWE ciphertext
245/// - s: corresponding secret
246/// - ideal_m: Ideal `encoded` message
247pub(crate) fn measure_noise_lwe<Ro: Row, Op: ArithmeticOps<Element = Ro::Element>, S>(
248 ct: &Ro,
249 s: &[S],
250 operator: &Op,
251 ideal_m: &Ro::Element,
252) -> f64
253where
254 Ro: TryConvertFrom<[S], Parameters = Ro::Element>,
255 Ro::Element: Zero + ToPrimitive + PrimInt + Display,
256{
257 assert!(s.len() == ct.as_ref().len() - 1,);
258
259 let s = Ro::try_convert_from(s, &operator.modulus());
260 let mut sa = Ro::Element::zero();
261 izip!(s.as_ref().iter(), ct.as_ref().iter().skip(1)).for_each(|(si, ai)| {
262 sa = operator.add(&sa, &operator.mul(si, ai));
263 });
264 let m = operator.sub(&ct.as_ref()[0], &sa);
265
266 let mut diff = operator.sub(&m, ideal_m);
267 let q = operator.modulus();
268 if diff > (q >> 1) {
269 diff = q - diff;
270 }
271 return diff.to_f64().unwrap().log2();
272}
273
274#[cfg(test)]
275mod tests {
276
277 use crate::{
278 backend::{ModInit, ModularOpsU64},
279 decomposer::{Decomposer, DefaultDecomposer},
280 lwe::{lwe_key_switch, measure_noise_lwe},
281 random::DefaultSecureRng,
282 rgsw::measure_noise,
283 Secret,
284 };
285
286 use super::{
287 decrypt_lwe, encrypt_lwe, lwe_ksk_keygen, LweKeySwitchingKey, LweSecret,
288 SeededLweKeySwitchingKey,
289 };
290
291 const K: usize = 50;
292
293 #[test]
294 fn encrypt_decrypt_works() {
295 let logq = 16;
296 let q = 1u64 << logq;
297 let lwe_n = 1024;
298 let logp = 3;
299
300 let modq_op = ModularOpsU64::new(q);
301 let lwe_sk = LweSecret::random(lwe_n >> 1, lwe_n);
302
303 let mut rng = DefaultSecureRng::new();
304
305 // encrypt
306 for m in 0..1u64 << logp {
307 let encoded_m = m << (logq - logp);
308 let mut lwe_ct = vec![0u64; lwe_n + 1];
309 encrypt_lwe(
310 &mut lwe_ct,
311 &encoded_m,
312 &lwe_sk.values(),
313 &modq_op,
314 &mut rng,
315 );
316 let encoded_m_back = decrypt_lwe(&lwe_ct, &lwe_sk.values(), &modq_op);
317 let m_back = ((((encoded_m_back as f64) * ((1 << logp) as f64)) / q as f64).round()
318 as u64)
319 % (1u64 << logp);
320 assert_eq!(m, m_back, "Expected {m} but got {m_back}");
321 }
322 }
323
324 #[test]
325 fn key_switch_works() {
326 let logq = 18;
327 let logp = 2;
328 let q = 1u64 << logq;
329 let lwe_in_n = 2048;
330 let lwe_out_n = 493;
331 let d_ks = 3;
332 let logb = 6;
333
334 let lwe_sk_in = LweSecret::random(lwe_in_n >> 1, lwe_in_n);
335 let lwe_sk_out = LweSecret::random(lwe_out_n >> 1, lwe_out_n);
336
337 let mut rng = DefaultSecureRng::new();
338 let modq_op = ModularOpsU64::new(q);
339
340 // genrate ksk
341 for _ in 0..K {
342 let mut ksk_seed = [0u8; 32];
343 rng.fill_bytes(&mut ksk_seed);
344 let mut seeded_ksk =
345 SeededLweKeySwitchingKey::empty(lwe_in_n, lwe_out_n, d_ks, ksk_seed, q);
346 let mut p_rng = DefaultSecureRng::new_seeded(ksk_seed);
347 let decomposer = DefaultDecomposer::new(q, logb, d_ks);
348 let gadget = decomposer.gadget_vector();
349 lwe_ksk_keygen(
350 &lwe_sk_in.values(),
351 &lwe_sk_out.values(),
352 &mut seeded_ksk.data,
353 &gadget,
354 &modq_op,
355 &mut p_rng,
356 &mut rng,
357 );
358 // println!("{:?}", ksk);
359 let ksk = LweKeySwitchingKey::<Vec<Vec<u64>>, DefaultSecureRng>::from(&seeded_ksk);
360
361 for m in 0..(1 << logp) {
362 // encrypt using lwe_sk_in
363 let encoded_m = m << (logq - logp);
364 let mut lwe_in_ct = vec![0u64; lwe_in_n + 1];
365 encrypt_lwe(
366 &mut lwe_in_ct,
367 &encoded_m,
368 lwe_sk_in.values(),
369 &modq_op,
370 &mut rng,
371 );
372
373 // key switch from lwe_sk_in to lwe_sk_out
374 let decomposer = DefaultDecomposer::new(1u64 << logq, logb, d_ks);
375 let mut lwe_out_ct = vec![0u64; lwe_out_n + 1];
376 lwe_key_switch(
377 &mut lwe_out_ct,
378 &lwe_in_ct,
379 &ksk.data,
380 &modq_op,
381 &decomposer,
382 );
383
384 // decrypt lwe_out_ct using lwe_sk_out
385 let encoded_m_back = decrypt_lwe(&lwe_out_ct, &lwe_sk_out.values(), &modq_op);
386 let m_back = ((((encoded_m_back as f64) * ((1 << logp) as f64)) / q as f64).round()
387 as u64)
388 % (1u64 << logp);
389 let noise =
390 measure_noise_lwe(&lwe_out_ct, lwe_sk_out.values(), &modq_op, &encoded_m);
391 println!("Noise: {noise}");
392 assert_eq!(m, m_back, "Expected {m} but got {m_back}");
393 // dbg!(m, m_back);
394 // dbg!(encoded_m, encoded_m_back);
395 }
396 }
397 }
398}