phantom-zone/src/utils.rs
src/utils.rsRaw
1use std::{fmt::Debug, usize};
2
3use itertools::Itertools;
4use num_traits::{FromPrimitive, PrimInt, Signed, Unsigned};
5
6use crate::{
7 backend::Modulus,
8 random::{RandomElement, RandomElementInModulus, RandomFill},
9};
10pub trait WithLocal {
11 fn with_local<F, R>(func: F) -> R
12 where
13 F: Fn(&Self) -> R;
14
15 fn with_local_mut<F, R>(func: F) -> R
16 where
17 F: Fn(&mut Self) -> R;
18
19 fn with_local_mut_mut<F, R>(func: &mut F) -> R
20 where
21 F: FnMut(&mut Self) -> R;
22}
23
24pub trait Global {
25 fn global() -> &'static Self;
26}
27
28pub trait ShoupMul {
29 fn representation(value: Self, q: Self) -> Self;
30 fn mul(a: Self, b: Self, b_shoup: Self, q: Self) -> Self;
31}
32
33impl ShoupMul for u64 {
34 #[inline]
35 fn representation(value: Self, q: Self) -> Self {
36 ((value as u128 * (1u128 << 64)) / q as u128) as u64
37 }
38
39 #[inline]
40 /// Returns a * b % q
41 fn mul(a: Self, b: Self, b_shoup: Self, q: Self) -> Self {
42 (b.wrapping_mul(a))
43 .wrapping_sub(q.wrapping_mul(((b_shoup as u128 * a as u128) >> 64) as u64))
44 }
45}
46
47pub fn fill_random_ternary_secret_with_hamming_weight<
48 T: Signed,
49 R: RandomFill<[u8]> + RandomElementInModulus<usize, usize>,
50>(
51 out: &mut [T],
52 hamming_weight: usize,
53 rng: &mut R,
54) {
55 let mut bytes = vec![0u8; hamming_weight.div_ceil(8)];
56 RandomFill::<[u8]>::random_fill(rng, &mut bytes);
57
58 let size = out.len();
59 let mut secret_indices = (0..size).into_iter().map(|i| i).collect_vec();
60 let mut bit_index = 0;
61 let mut byte_index = 0;
62 for _ in 0..hamming_weight {
63 let s_index = RandomElementInModulus::<usize, usize>::random(rng, &secret_indices.len());
64
65 let curr_bit = (bytes[byte_index] >> bit_index) & 1;
66 if curr_bit == 1 {
67 out[secret_indices[s_index]] = T::one();
68 } else {
69 out[secret_indices[s_index]] = -T::one();
70 }
71
72 secret_indices[s_index] = *secret_indices.last().unwrap();
73 secret_indices.truncate(secret_indices.len());
74
75 if bit_index == 7 {
76 bit_index = 0;
77 byte_index += 1;
78 } else {
79 bit_index += 1;
80 }
81 }
82}
83
84// TODO (Jay): this is only a workaround. Add a propoer way to perform primality
85// tests.
86fn is_probably_prime(candidate: u64) -> bool {
87 num_bigint_dig::prime::probably_prime(&num_bigint_dig::BigUint::from(candidate), 0)
88}
89
90/// Finds prime that satisfy
91/// - $prime \lt upper_bound$
92/// - $\log{prime} = num_bits$
93/// - `prime % modulo == 1`
94pub fn generate_prime(num_bits: usize, modulo: u64, upper_bound: u64) -> Option<u64> {
95 let leading_zeros = (64 - num_bits) as u32;
96
97 let mut tentative_prime = upper_bound - 1;
98 while tentative_prime % modulo != 1 && tentative_prime.leading_zeros() == leading_zeros {
99 tentative_prime -= 1;
100 }
101
102 while !is_probably_prime(tentative_prime)
103 && tentative_prime.leading_zeros() == leading_zeros
104 && tentative_prime >= modulo
105 {
106 tentative_prime -= modulo;
107 }
108
109 if is_probably_prime(tentative_prime) && tentative_prime.leading_zeros() == leading_zeros {
110 Some(tentative_prime)
111 } else {
112 None
113 }
114}
115
116/// Returns a^b mod q
117pub fn mod_exponent(a: u64, mut b: u64, q: u64) -> u64 {
118 let mod_mul = |v1: &u64, v2: &u64| {
119 let tmp = *v1 as u128 * *v2 as u128;
120 (tmp % q as u128) as u64
121 };
122
123 let mut acc = a;
124 let mut out = 1;
125 while b != 0 {
126 let flag = b & 1;
127
128 if flag == 1 {
129 out = mod_mul(&acc, &out);
130 }
131 acc = mod_mul(&acc, &acc);
132
133 b >>= 1;
134 }
135
136 out
137}
138
139pub fn mod_inverse(a: u64, q: u64) -> u64 {
140 mod_exponent(a, q - 2, q)
141}
142
143pub fn negacyclic_mul<T: PrimInt, F: Fn(&T, &T) -> T>(
144 a: &[T],
145 b: &[T],
146 mul: F,
147 modulus: T,
148) -> Vec<T> {
149 let mut r = vec![T::zero(); a.len()];
150 for i in 0..a.len() {
151 for j in 0..i + 1 {
152 // println!("i: {j} {}", i - j);
153 r[i] = (r[i] + mul(&a[j], &b[i - j])) % modulus;
154 }
155
156 for j in i + 1..a.len() {
157 // println!("i: {j} {}", a.len() - j + i);
158 r[i] = (r[i] + modulus - mul(&a[j], &b[a.len() - j + i])) % modulus;
159 }
160 // println!("")
161 }
162
163 return r;
164}
165
166pub trait TryConvertFrom1<T: ?Sized, P> {
167 fn try_convert_from(value: &T, parameters: &P) -> Self;
168}
169
170impl<P: Modulus<Element = u64>> TryConvertFrom1<[i64], P> for Vec<u64> {
171 fn try_convert_from(value: &[i64], parameters: &P) -> Self {
172 value
173 .iter()
174 .map(|v| parameters.map_element_from_i64(*v))
175 .collect_vec()
176 }
177}
178
179impl<P: Modulus<Element = u64>> TryConvertFrom1<[i32], P> for Vec<u64> {
180 fn try_convert_from(value: &[i32], parameters: &P) -> Self {
181 value
182 .iter()
183 .map(|v| parameters.map_element_from_i64(*v as i64))
184 .collect_vec()
185 }
186}
187
188impl<P: Modulus> TryConvertFrom1<[P::Element], P> for Vec<i64> {
189 fn try_convert_from(value: &[P::Element], parameters: &P) -> Self {
190 value
191 .iter()
192 .map(|v| parameters.map_element_to_i64(v))
193 .collect_vec()
194 }
195}
196
197// pub trait TryConvertFrom<T: ?Sized> {
198// type Parameters: ?Sized;
199
200// fn try_convert_from(value: &T, parameters: &Self::Parameters) -> Self;
201// }
202
203// impl TryConvertFrom1<[i32]> for Vec<Vec<u32>> {
204// type Parameters = u32;
205// fn try_convert_from(value: &[i32], parameters: &Self::Parameters) -> Self
206// { let row0 = value
207// .iter()
208// .map(|v| {
209// let is_neg = v.is_negative();
210// let v_u32 = v.abs() as u32;
211
212// assert!(v_u32 < *parameters);
213
214// if is_neg {
215// parameters - v_u32
216// } else {
217// v_u32
218// }
219// })
220// .collect_vec();
221
222// vec![row0]
223// }
224// }
225
226// impl TryConvertFrom1<[i32]> for Vec<Vec<u64>> {
227// type Parameters = u64;
228// fn try_convert_from(value: &[i32], parameters: &Self::Parameters) -> Self
229// { let row0 = value
230// .iter()
231// .map(|v| {
232// let is_neg = v.is_negative();
233// let v_u64 = v.abs() as u64;
234
235// assert!(v_u64 < *parameters);
236
237// if is_neg {
238// parameters - v_u64
239// } else {
240// v_u64
241// }
242// })
243// .collect_vec();
244
245// vec![row0]
246// }
247// }
248
249// impl TryConvertFrom1<[i32]> for Vec<u64> {
250// type Parameters = u64;
251// fn try_convert_from(value: &[i32], parameters: &Self::Parameters) -> Self
252// { value
253// .iter()
254// .map(|v| {
255// let is_neg = v.is_negative();
256// let v_u64 = v.abs() as u64;
257
258// assert!(v_u64 < *parameters);
259
260// if is_neg {
261// parameters - v_u64
262// } else {
263// v_u64
264// }
265// })
266// .collect_vec()
267// }
268// }
269
270// impl TryConvertFrom1<[u64]> for Vec<i64> {
271// type Parameters = u64;
272// fn try_convert_from(value: &[u64], parameters: &Self::Parameters) -> Self
273// { let q = *parameters;
274// let qby2 = q / 2;
275// value
276// .iter()
277// .map(|v| {
278// if *v > qby2 {
279// -((q - v) as i64)
280// } else {
281// *v as i64
282// }
283// })
284// .collect_vec()
285// }
286// }
287
288pub(crate) struct Stats<T> {
289 pub(crate) samples: Vec<T>,
290}
291
292impl<T: PrimInt + FromPrimitive + Debug> Stats<T>
293where
294 // T: for<'a> Sum<&'a T>,
295 T: for<'a> std::iter::Sum<&'a T> + std::iter::Sum<T>,
296{
297 pub(crate) fn new() -> Self {
298 Self { samples: vec![] }
299 }
300
301 pub(crate) fn mean(&self) -> f64 {
302 self.samples.iter().sum::<T>().to_f64().unwrap() / (self.samples.len() as f64)
303 }
304
305 pub(crate) fn std_dev(&self) -> f64 {
306 let mean = self.mean();
307
308 // diff
309 let diff_sq = self
310 .samples
311 .iter()
312 .map(|v| {
313 let t = v.to_f64().unwrap() - mean;
314 t * t
315 })
316 .into_iter()
317 .sum::<f64>();
318
319 (diff_sq / (self.samples.len() as f64)).sqrt()
320 }
321
322 pub(crate) fn add_more(&mut self, values: &[T]) {
323 self.samples.extend(values.iter());
324 }
325}