fancy_garbling/
util.rs

1//! Tools useful for interacting with `fancy-garbling`.
2//!
3//! Note: all number representations in this library are little-endian.
4
5use vectoreyes::U8x16;
6
7use crate::{Bundle, HasModulus};
8
9////////////////////////////////////////////////////////////////////////////////
10// tweak functions for garbling
11
12/// Tweak function for a single item.
13pub(crate) fn tweak(i: usize) -> u128 {
14    i as u128
15}
16
17/// Tweak function for two items.
18pub(crate) fn tweak2(i: u64, j: u64) -> u128 {
19    (j as u128) << 64 | (i as u128)
20}
21
22/// Compute the output tweak for a garbled gate where `i`` is the gate ID and
23/// `k` is the value.
24pub fn output_tweak(i: usize, k: u16) -> u128 {
25    let (left, _) = (i as u128).overflowing_shl(64);
26    left + k as u128
27}
28
29////////////////////////////////////////////////////////////////////////////////
30// mixed radix stuff
31
32/// Convert `x` into base `q`, building a vector of length `n`.
33#[cfg(test)]
34fn as_base_q(x: u128, q: u16, n: usize) -> Vec<u16> {
35    let ms = std::iter::repeat_n(q, n).collect::<Vec<_>>();
36    as_mixed_radix(x, &ms)
37}
38
39/// Determine how many `mod q` digits fit into a `u128` (includes the color
40/// digit).
41pub(crate) fn digits_per_u128(modulus: u16) -> usize {
42    debug_assert_ne!(modulus, 0);
43    debug_assert_ne!(modulus, 1);
44    if modulus == 2 {
45        128
46    } else if modulus <= 4 {
47        64
48    } else if modulus <= 8 {
49        42
50    } else if modulus <= 16 {
51        32
52    } else if modulus <= 32 {
53        25
54    } else if modulus <= 64 {
55        21
56    } else if modulus <= 128 {
57        18
58    } else if modulus <= 256 {
59        16
60    } else if modulus <= 512 {
61        14
62    } else {
63        (128.0 / (modulus as f64).log2().ceil()).floor() as usize
64    }
65}
66
67/// Convert `x` into base `q`.
68#[cfg(test)]
69pub(crate) fn as_base_q_u128(x: u128, q: u16) -> Vec<u16> {
70    as_base_q(x, q, digits_per_u128(q))
71}
72
73/// Convert `x` into mixed radix form using the provided `radii`.
74pub(crate) fn as_mixed_radix(x: u128, radii: &[u16]) -> Vec<u16> {
75    let mut x = x;
76    radii
77        .iter()
78        .map(|&m| {
79            if x >= m as u128 {
80                let d = x % m as u128;
81                x = (x - d) / m as u128;
82                d as u16
83            } else {
84                let d = x as u16;
85                x = 0;
86                d
87            }
88        })
89        .collect()
90}
91
92/// Convert little-endian base `q` digits into `u128`.
93pub(crate) fn from_base_q(ds: &[u16], q: u16) -> u128 {
94    let mut x = 0u128;
95    for &d in ds.iter().rev() {
96        let (xp, overflow) = x.overflowing_mul(q.into());
97        debug_assert!(!overflow, "overflow!!!! x={}", x);
98        x = xp + d as u128;
99    }
100    x
101}
102
103////////////////////////////////////////////////////////////////////////////////
104// bits
105
106/// Get the bits of a u128 encoded in 128 u16s, which is convenient for the rest of
107/// the library, which uses u16 as the base digit type in Wire.
108pub(crate) fn u128_to_bits(x: u128, n: usize) -> Vec<u16> {
109    let mut bits = Vec::with_capacity(n);
110    let mut y = x;
111    for _ in 0..n {
112        let b = y & 1;
113        bits.push(b as u16);
114        y -= b;
115        y /= 2;
116    }
117    bits
118}
119
120/// Convert into a u128 from the "bits" as u16. Assumes each "bit" is 0 or 1.
121pub fn u128_from_bits(bs: &[u16]) -> u128 {
122    let mut x = 0;
123    for &b in bs.iter().skip(1).rev() {
124        x += b as u128;
125        x *= 2;
126    }
127    x += bs[0] as u128;
128    x
129}
130
131////////////////////////////////////////////////////////////////////////////////
132// primes & crt
133
134/// Factor using the primes in the global `PRIMES` array. Fancy garbling only supports
135/// composites with small prime factors.
136///
137/// We are limited by the size of the digits in Wire, and besides, if need large moduli,
138/// you should use BundleGadgets and save.
139pub fn factor(inp: u128) -> Vec<u16> {
140    let mut x = inp;
141    let mut fs = Vec::new();
142    for &p in PRIMES.iter() {
143        let q = p as u128;
144        if x.is_multiple_of(q) {
145            fs.push(p);
146            x /= q;
147        }
148    }
149    if x != 1 {
150        panic!("can only factor numbers with unique prime factors");
151    }
152    fs
153}
154
155/// Compute the CRT representation of x with respect to the primes ps.
156pub fn crt(x: u128, ps: &[u16]) -> Vec<u16> {
157    ps.iter().map(|&p| (x % p as u128) as u16).collect()
158}
159
160/// Compute the CRT representation of `x` with respect to the factorization of
161/// `q`.
162pub fn crt_factor(x: u128, q: u128) -> Vec<u16> {
163    crt(x, &factor(q))
164}
165
166/// Compute the value x given a list of CRT primes and residues.
167pub fn crt_inv(xs: &[u16], ps: &[u16]) -> u128 {
168    let mut ret = 0;
169    let M = ps.iter().fold(1, |acc, &x| x as i128 * acc);
170    for (&p, &a) in ps.iter().zip(xs.iter()) {
171        let p = p as i128;
172        let q = M / p;
173        ret += a as i128 * inv(q, p) * q;
174        ret %= &M;
175    }
176    ret as u128
177}
178
179/// Compute the value `x` given a composite CRT modulus provided by `xs`.
180pub fn crt_inv_factor(xs: &[u16], q: u128) -> u128 {
181    crt_inv(xs, &factor(q))
182}
183
184/// Invert inp_a mod inp_b.
185pub(crate) fn inv(inp_a: i128, inp_b: i128) -> i128 {
186    let mut a = inp_a;
187    let mut b = inp_b;
188    let mut q;
189    let mut tmp;
190
191    let (mut x0, mut x1) = (0, 1);
192
193    if b == 1 {
194        return 1;
195    }
196
197    while a > 1 {
198        q = a / b;
199
200        // a, b = b, a%b
201        tmp = b;
202        b = a % b;
203        a = tmp;
204
205        tmp = x0;
206        x0 = x1 - q * x0;
207        x1 = tmp;
208    }
209
210    if x1 < 0 {
211        x1 += inp_b;
212    }
213
214    x1
215}
216
217const NPRIMES: usize = 29;
218
219/// Primes used in `fancy-garbling`.
220pub const PRIMES: [u16; NPRIMES] = [
221    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
222    101, 103, 107, 109,
223];
224
225/// Generate a CRT modulus using the `n` smallest primes in [`PRIMES`].
226pub fn modulus_with_nprimes(n: usize) -> u128 {
227    product(&PRIMES[0..n])
228}
229
230/// Generate a CRT modulus that support at least n-bit integers, using the built-in
231/// PRIMES.
232pub fn modulus_with_width(n: u32) -> u128 {
233    product(&base_primes_with_width(n, &PRIMES))
234}
235
236/// Generate the factors of a CRT modulus that support at least n-bit integers, using the
237/// built-in [`PRIMES`].
238pub fn primes_with_width(n: u32) -> Vec<u16> {
239    base_primes_with_width(n, &PRIMES)
240}
241
242/// Generate the factors of a CRT modulus that support at least n-bit integers,
243/// using provided primes.
244fn base_primes_with_width(nbits: u32, primes: &[u16]) -> Vec<u16> {
245    let mut res = 1;
246    let mut ps = Vec::new();
247    for &p in primes.iter() {
248        res *= u128::from(p);
249        ps.push(p);
250        if (res >> nbits) > 0 {
251            break;
252        }
253    }
254    assert!((res >> nbits) > 0, "not enough primes!");
255    ps
256}
257
258/// Compute the product of some `u16`s as a `u128`.
259pub fn product(xs: &[u16]) -> u128 {
260    xs.iter().fold(1, |acc, &x| acc * x as u128)
261}
262
263/// Compute the `ms` needed for the number of CRT primes in `x`, with accuracy
264/// `accuracy`.
265///
266/// Supported accuracy: ["100%", "99.9%", "99%"]
267pub(crate) fn get_ms<W: Clone + HasModulus>(x: &Bundle<W>, accuracy: &str) -> Vec<u16> {
268    match accuracy {
269        "100%" => match x.moduli().len() {
270            3 => vec![2; 5],
271            4 => vec![3, 26],
272            5 => vec![3, 4, 54],
273            6 => vec![5, 5, 5, 60],
274            7 => vec![5, 6, 6, 7, 86],
275            8 => vec![5, 7, 8, 8, 9, 98],
276            9 => vec![5, 5, 7, 7, 7, 7, 7, 76],
277            10 => vec![5, 5, 6, 6, 6, 6, 11, 11, 202],
278            11 => vec![5, 5, 5, 5, 5, 6, 6, 6, 7, 7, 8, 150],
279            n => panic!("unknown exact Ms for {} primes!", n),
280        },
281        "99.999%" => match x.moduli().len() {
282            8 => vec![5, 5, 6, 7, 102],
283            9 => vec![5, 5, 6, 7, 114],
284            10 => vec![5, 6, 6, 7, 102],
285            11 => vec![5, 5, 6, 7, 130],
286            n => panic!("unknown 99.999% accurate Ms for {} primes!", n),
287        },
288        "99.99%" => match x.moduli().len() {
289            6 => vec![5, 5, 5, 42],
290            7 => vec![4, 5, 6, 88],
291            8 => vec![4, 5, 7, 78],
292            9 => vec![5, 5, 6, 84],
293            10 => vec![4, 5, 6, 112],
294            11 => vec![7, 11, 174],
295            n => panic!("unknown 99.99% accurate Ms for {} primes!", n),
296        },
297        "99.9%" => match x.moduli().len() {
298            5 => vec![3, 5, 30],
299            6 => vec![4, 5, 48],
300            7 => vec![4, 5, 60],
301            8 => vec![3, 5, 78],
302            9 => vec![9, 140],
303            10 => vec![7, 190],
304            n => panic!("unknown 99.9% accurate Ms for {} primes!", n),
305        },
306        "99%" => match x.moduli().len() {
307            4 => vec![3, 18],
308            5 => vec![3, 36],
309            6 => vec![3, 40],
310            7 => vec![3, 40],
311            8 => vec![126],
312            9 => vec![138],
313            10 => vec![140],
314            n => panic!("unknown 99% accurate Ms for {} primes!", n),
315        },
316        _ => panic!("get_ms: unsupported accuracy {}", accuracy),
317    }
318}
319
320/// Extra Rng functionality, useful for `fancy-garbling`.
321pub trait RngExt: rand::Rng + Sized {
322    /// Randomly generate a `bool`.
323    fn gen_bool(&mut self) -> bool {
324        self.r#gen()
325    }
326    /// Randomly generate a `u16`.
327    fn gen_u16(&mut self) -> u16 {
328        self.r#gen()
329    }
330    /// Randomly generate a `u64`.
331    fn gen_u64(&mut self) -> u64 {
332        self.r#gen()
333    }
334    /// Randomly generate a `usize`.
335    fn gen_usize(&mut self) -> usize {
336        self.r#gen()
337    }
338    /// Randomly generate a `u128`.
339    fn gen_u128(&mut self) -> u128 {
340        self.r#gen()
341    }
342    /// Randomly generate a valid `Block`.
343    fn gen_usable_block(&mut self, modulus: u16) -> U8x16 {
344        if modulus.is_power_of_two() {
345            let nbits = (modulus - 1).count_ones();
346            if 128 % nbits == 0 {
347                return U8x16::from(self.gen_u128());
348            }
349        }
350        let n = digits_per_u128(modulus);
351        let max = (modulus as u128).pow(n as u32);
352        U8x16::from(self.gen_u128() % max)
353    }
354    /// Randomly generate a prime (among the set of supported primes).
355    fn gen_prime(&mut self) -> u16 {
356        PRIMES[self.r#gen::<usize>() % NPRIMES]
357    }
358    /// Randomly generate a (supported) modulus.
359    fn gen_modulus(&mut self) -> u16 {
360        2 + (self.r#gen::<u16>() % 111)
361    }
362    /// Randomly generate a valid composite modulus.
363    fn gen_usable_composite_modulus(&mut self) -> u128 {
364        product(&self.gen_usable_factors())
365    }
366    /// Randomly generate a vector of valid factor
367    fn gen_usable_factors(&mut self) -> Vec<u16> {
368        let mut x: u128 = 1;
369        PRIMES[..25]
370            .iter()
371            .cloned()
372            .filter(|_| self.r#gen()) // randomly take this prime
373            .take_while(|&q| {
374                // make sure that we don't overflow!
375                match x.checked_mul(q as u128) {
376                    None => false,
377                    Some(y) => {
378                        x = y;
379                        true
380                    }
381                }
382            })
383            .collect()
384    }
385}
386
387impl<R: rand::Rng + Sized> RngExt for R {}
388
389////////////////////////////////////////////////////////////////////////////////
390// tests
391
392#[cfg(test)]
393mod tests {
394    use super::*;
395    use crate::util::RngExt;
396    use rand::thread_rng;
397
398    #[test]
399    fn crt_conversion() {
400        let mut rng = thread_rng();
401        let ps = &PRIMES[..25];
402        let modulus = product(ps);
403
404        for _ in 0..128 {
405            let x = rng.gen_u128() % modulus;
406            assert_eq!(crt_inv(&crt(x, ps), ps), x);
407        }
408    }
409
410    #[test]
411    fn factoring() {
412        let mut rng = thread_rng();
413        for _ in 0..16 {
414            let mut ps = Vec::new();
415            let mut q: u128 = 1;
416            for &p in PRIMES.iter() {
417                if rng.gen_bool() {
418                    match q.checked_mul(p as u128) {
419                        None => break,
420                        Some(z) => q = z,
421                    }
422                    ps.push(p);
423                }
424            }
425            assert_eq!(factor(q), ps);
426        }
427    }
428
429    #[test]
430    fn bits() {
431        let mut rng = thread_rng();
432        for _ in 0..128 {
433            let x = rng.gen_u128();
434            assert_eq!(u128_from_bits(&u128_to_bits(x, 128)), x);
435        }
436    }
437
438    #[test]
439    fn base_q_conversion() {
440        let mut rng = thread_rng();
441        for _ in 0..1000 {
442            let q = 2 + (rng.gen_u16() % 111);
443            let x = u128::from(rng.gen_usable_block(q));
444            let y = as_base_q(x, q, digits_per_u128(q));
445            let z = from_base_q(&y, q);
446            assert_eq!(x, z);
447        }
448    }
449}
fancy_garbling/util.rs

fancy_garbling/
util.rs
