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