phantom-zone/src/bool.rs
src/bool.rsRaw
1use std::collections::HashMap;
2
3use num_traits::{FromPrimitive, One, PrimInt, ToPrimitive, Zero};
4
5use crate::{
6 backend::{ArithmeticOps, VectorOps},
7 decomposer::Decomposer,
8 lwe::lwe_key_switch,
9 ntt::Ntt,
10 rgsw::{galois_auto, rlwe_by_rgsw, IsTrivial},
11 Matrix, MatrixEntity, MatrixMut, Row, RowMut,
12};
13
14struct BoolEvaluator {}
15
16impl BoolEvaluator {}
17
18trait PbsKey {
19 type M: Matrix;
20
21 fn rgsw_ct_secret_el(&self, si: usize) -> &Self::M;
22 fn galois_key_for_auto(&self, k: isize) -> &Self::M;
23 fn auto_map_index(&self, k: isize) -> &[usize];
24 fn auto_map_sign(&self, k: isize) -> &[bool];
25}
26
27/// LMKCY+ Blind rotation
28///
29/// gk_to_si: [-g^0, -g^1, .., -g^{q/2-1}, g^0, ..., g^{q/2-1}]
30fn blind_rotation<
31 MT: IsTrivial + MatrixMut,
32 Mmut: MatrixMut<MatElement = MT::MatElement> + Matrix,
33 D: Decomposer<Element = MT::MatElement>,
34 NttOp: Ntt<Element = MT::MatElement>,
35 ModOp: ArithmeticOps<Element = MT::MatElement> + VectorOps<Element = MT::MatElement>,
36 K: PbsKey<M = Mmut>,
37>(
38 trivial_rlwe_test_poly: &mut MT,
39 scratch_matrix_dplus2_ring: &mut Mmut,
40 g: isize,
41 w: usize,
42 q: usize,
43 gk_to_si: &[Vec<usize>],
44 decomposer: &D,
45 ntt_op: &NttOp,
46 mod_op: &ModOp,
47 pbs_key: &K,
48) where
49 <Mmut as Matrix>::R: RowMut,
50 Mmut::MatElement: Copy + Zero,
51 <MT as Matrix>::R: RowMut,
52{
53 let q_by_2 = q / 2;
54
55 // -(g^k)
56 for i in 1..q_by_2 {
57 gk_to_si[q_by_2 + i].iter().for_each(|s_index| {
58 rlwe_by_rgsw(
59 trivial_rlwe_test_poly,
60 pbs_key.rgsw_ct_secret_el(*s_index),
61 scratch_matrix_dplus2_ring,
62 decomposer,
63 ntt_op,
64 mod_op,
65 );
66 });
67
68 galois_auto(
69 trivial_rlwe_test_poly,
70 pbs_key.galois_key_for_auto(g),
71 scratch_matrix_dplus2_ring,
72 pbs_key.auto_map_index(g),
73 pbs_key.auto_map_sign(g),
74 mod_op,
75 ntt_op,
76 decomposer,
77 );
78 }
79
80 // -(g^0)
81 gk_to_si[q_by_2].iter().for_each(|s_index| {
82 rlwe_by_rgsw(
83 trivial_rlwe_test_poly,
84 pbs_key.rgsw_ct_secret_el(*s_index),
85 scratch_matrix_dplus2_ring,
86 decomposer,
87 ntt_op,
88 mod_op,
89 );
90 });
91 galois_auto(
92 trivial_rlwe_test_poly,
93 pbs_key.galois_key_for_auto(-g),
94 scratch_matrix_dplus2_ring,
95 pbs_key.auto_map_index(-g),
96 pbs_key.auto_map_sign(-g),
97 mod_op,
98 ntt_op,
99 decomposer,
100 );
101
102 // +(g^k)
103 for i in 1..q_by_2 {
104 gk_to_si[i].iter().for_each(|s_index| {
105 rlwe_by_rgsw(
106 trivial_rlwe_test_poly,
107 pbs_key.rgsw_ct_secret_el(*s_index),
108 scratch_matrix_dplus2_ring,
109 decomposer,
110 ntt_op,
111 mod_op,
112 );
113 });
114
115 galois_auto(
116 trivial_rlwe_test_poly,
117 pbs_key.galois_key_for_auto(g),
118 scratch_matrix_dplus2_ring,
119 pbs_key.auto_map_index(g),
120 pbs_key.auto_map_sign(g),
121 mod_op,
122 ntt_op,
123 decomposer,
124 );
125 }
126
127 // +(g^0)
128 gk_to_si[0].iter().for_each(|s_index| {
129 rlwe_by_rgsw(
130 trivial_rlwe_test_poly,
131 pbs_key.rgsw_ct_secret_el(gk_to_si[q_by_2][*s_index]),
132 scratch_matrix_dplus2_ring,
133 decomposer,
134 ntt_op,
135 mod_op,
136 );
137 });
138}
139
140trait Parameters {
141 type Element;
142 type D: Decomposer<Element = Self::Element>;
143 fn rlwe_q(&self) -> Self::Element;
144 fn lwe_q(&self) -> Self::Element;
145 fn br_q(&self) -> usize;
146 fn d_rgsw(&self) -> usize;
147 fn d_lwe(&self) -> usize;
148 fn rlwe_n(&self) -> usize;
149 fn lwe_n(&self) -> usize;
150 // Embedding fator for ring X^{q}+1 inside
151 fn embedding_factor(&self) -> usize;
152 // generator g
153 fn g(&self) -> isize;
154 fn decomoposer_lwe(&self) -> &Self::D;
155 fn decomoposer_rlwe(&self) -> &Self::D;
156 /// Maps a \in Z^*_{2q} to discrete log k, with generator g (i.e. g^k =
157 /// a). Returned vector is of size q that stores dlog of a at `vec[a]`.
158 /// For any a, k is s.t. a = g^{k}, then k is expressed as k. If k is s.t a
159 /// = -g^{k/2}, then k is expressed as k=k+q/2
160 fn g_k_dlog_map(&self) -> &[usize];
161}
162
163/// - Mod down
164/// - key switching
165/// - mod down
166/// - blind rotate
167fn pbs<
168 M: Matrix + MatrixMut + MatrixEntity,
169 MT: MatrixMut<MatElement = M::MatElement, R = M::R> + IsTrivial + MatrixEntity,
170 P: Parameters<Element = M::MatElement>,
171 NttOp: Ntt<Element = M::MatElement>,
172 ModOp: ArithmeticOps<Element = M::MatElement> + VectorOps<Element = M::MatElement>,
173 K: PbsKey<M = M>,
174>(
175 parameters: &P,
176 test_vec: &M::R,
177 lwe_in: &mut M::R,
178 lwe_ksk: &M,
179 scratch_lwen_plus1: &mut M::R,
180 scratch_matrix_dplus2_ring: &mut M,
181 modop_lweq: &ModOp,
182 modop_rlweq: &ModOp,
183 nttop_rlweq: &NttOp,
184 pbs_key: K,
185) where
186 <M as Matrix>::R: RowMut,
187 <MT as Matrix>::R: RowMut,
188 M::MatElement: PrimInt + ToPrimitive + FromPrimitive + One + Copy + Zero,
189{
190 let rlwe_q = parameters.rlwe_q();
191 let lwe_q = parameters.lwe_q();
192 let br_q = parameters.br_q();
193 let rlwe_qf64 = rlwe_q.to_f64().unwrap();
194 let lwe_qf64 = lwe_q.to_f64().unwrap();
195 let br_qf64 = br_q.to_f64().unwrap();
196 let rlwe_n = parameters.rlwe_n();
197
198 // moddown Q -> Q_ks
199 lwe_in.as_mut().iter_mut().for_each(|v| {
200 *v =
201 M::MatElement::from_f64(((v.to_f64().unwrap() * lwe_qf64) / rlwe_qf64).round()).unwrap()
202 });
203
204 // key switch
205 // let mut lwe_out = M::zeros(1, parameters.lwe_n() + 1);
206 scratch_lwen_plus1.as_mut().fill(M::MatElement::zero());
207 lwe_key_switch(
208 scratch_lwen_plus1,
209 lwe_in,
210 lwe_ksk,
211 modop_lweq,
212 parameters.decomoposer_lwe(),
213 );
214
215 // odd mowdown Q_ks -> q
216 let g_k_dlog_map = parameters.g_k_dlog_map();
217 let mut g_k_si = vec![vec![]; br_q];
218 scratch_lwen_plus1
219 .as_ref()
220 .iter()
221 .skip(1)
222 .enumerate()
223 .for_each(|(index, v)| {
224 let odd_v = mod_switch_odd(v.to_f64().unwrap(), lwe_qf64, br_qf64);
225 let k = g_k_dlog_map[odd_v];
226 g_k_si[k].push(index);
227 });
228
229 // handle b and set trivial test RLWE
230 let g = parameters.g() as usize;
231 let g_times_b = (g * mod_switch_odd(
232 scratch_lwen_plus1.as_ref()[0].to_f64().unwrap(),
233 lwe_qf64,
234 br_qf64,
235 )) % (br_q);
236 // v = (v(X) * X^{g*b}) mod X^{q/2}+1
237 let br_qby2 = br_q / 2;
238 let mut gb_monomial_sign = true;
239 let mut gb_monomial_exp = g_times_b;
240 // X^{g*b} mod X^{q}+1
241 if gb_monomial_exp > br_qby2 {
242 gb_monomial_exp -= br_qby2;
243 gb_monomial_sign = false
244 }
245 // monomial mul
246 let mut trivial_rlwe_test_poly = MT::zeros(2, rlwe_n);
247 if parameters.embedding_factor() == 1 {
248 monomial_mul(
249 test_vec.as_ref(),
250 trivial_rlwe_test_poly.get_row_mut(1).as_mut(),
251 gb_monomial_exp,
252 gb_monomial_sign,
253 br_q,
254 modop_rlweq,
255 );
256 } else {
257 // use lwe_in to store the `t = v(X) * X^{g*2} mod X^{q/2}+1` temporarily. This
258 // works because q/2 < N (where N is lwe_in LWE dimension) always.
259 monomial_mul(
260 test_vec.as_ref(),
261 &mut lwe_in.as_mut()[..br_qby2],
262 gb_monomial_exp,
263 gb_monomial_sign,
264 br_q,
265 modop_rlweq,
266 );
267
268 // emebed poly `t` in ring X^{q/2}+1 inside the bigger ring X^{N}+1
269 let partb_trivial_rlwe = trivial_rlwe_test_poly.get_row_mut(1);
270 lwe_in.as_ref()[..br_qby2]
271 .iter()
272 .enumerate()
273 .for_each(|(index, v)| {
274 partb_trivial_rlwe[2 * index] = *v;
275 });
276 }
277 // TODO Rotate test input
278
279 // blind rotate
280 blind_rotation(
281 &mut trivial_rlwe_test_poly,
282 scratch_matrix_dplus2_ring,
283 parameters.g(),
284 1,
285 br_q,
286 &g_k_si,
287 parameters.decomoposer_rlwe(),
288 nttop_rlweq,
289 modop_rlweq,
290 &pbs_key,
291 );
292
293 // sample extract
294 sample_extract(lwe_in, &trivial_rlwe_test_poly, modop_rlweq, 0);
295}
296
297fn mod_switch_odd(v: f64, from_q: f64, to_q: f64) -> usize {
298 let odd_v = (((v.to_f64().unwrap() * to_q) / (from_q)).floor())
299 .to_usize()
300 .unwrap();
301 //TODO(Jay): check correctness of this
302 odd_v + (odd_v ^ (usize::one()))
303}
304
305fn sample_extract<M: Matrix + MatrixMut, ModOp: ArithmeticOps<Element = M::MatElement>>(
306 lwe_out: &mut M::R,
307 rlwe_in: &M,
308 mod_op: &ModOp,
309 index: usize,
310) where
311 <M as Matrix>::R: RowMut,
312 M::MatElement: Copy,
313{
314 let ring_size = rlwe_in.dimension().1;
315
316 // index..=0
317 let to = &mut lwe_out.as_mut()[1..];
318 let from = rlwe_in.get_row_slice(0);
319 for i in 0..index + 1 {
320 to[i] = from[index - i];
321 }
322
323 // -(N..index)
324 for i in index + 1..ring_size {
325 to[i] = mod_op.neg(&from[ring_size + index - i]);
326 }
327
328 // set b
329 lwe_out.as_mut()[0] = *rlwe_in.get(1, index);
330}
331
332fn monomial_mul<El, ModOp: ArithmeticOps<Element = El>>(
333 p_in: &[El],
334 p_out: &mut [El],
335 mon_exp: usize,
336 mon_sign: bool,
337 ring_size: usize,
338 mod_op: &ModOp,
339) where
340 El: Copy,
341{
342 debug_assert!(p_in.as_ref().len() == ring_size);
343 debug_assert!(p_in.as_ref().len() == p_out.as_ref().len());
344 debug_assert!(mon_exp < ring_size);
345
346 p_in.as_ref().iter().enumerate().for_each(|(index, v)| {
347 let mut to_index = index + mon_exp;
348 let mut to_sign = mon_sign;
349 if to_index >= ring_size {
350 to_index = to_index - ring_size;
351 to_sign = !to_sign;
352 }
353
354 if !to_sign {
355 p_out.as_mut()[to_index] = mod_op.neg(v);
356 } else {
357 p_out.as_mut()[to_index] = *v;
358 }
359 });
360}