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 rand::RngExt as _;
6
7use fancy_circuits::util::as_mixed_radix;
8use vectoreyes::U8x16;
9
10/// Tweak function for a single item.
11pub(crate) fn tweak(i: usize) -> u128 {
12    i as u128
13}
14
15/// Tweak function for two items.
16pub(crate) fn tweak2(i: u64, j: u64) -> u128 {
17    (j as u128) << 64 | (i as u128)
18}
19
20/// Compute the output tweak for a garbled gate where `i`` is the gate ID and
21/// `k` is the value.
22pub fn output_tweak(i: usize, k: u16) -> u128 {
23    let (left, _) = (i as u128).overflowing_shl(64);
24    left + k as u128
25}
26
27/// Determine how many `mod q` digits fit into a `u128` (includes the color
28/// digit).
29pub(crate) fn digits_per_u128(modulus: u16) -> usize {
30    debug_assert_ne!(modulus, 0);
31    debug_assert_ne!(modulus, 1);
32    if modulus == 2 {
33        128
34    } else if modulus <= 4 {
35        64
36    } else if modulus <= 8 {
37        42
38    } else if modulus <= 16 {
39        32
40    } else if modulus <= 32 {
41        25
42    } else if modulus <= 64 {
43        21
44    } else if modulus <= 128 {
45        18
46    } else if modulus <= 256 {
47        16
48    } else if modulus <= 512 {
49        14
50    } else {
51        (128.0 / (modulus as f64).log2().ceil()).floor() as usize
52    }
53}
54
55/// Convert little-endian base `q` digits into `u128`.
56pub(crate) fn from_base_q(ds: &[u16], q: u16) -> u128 {
57    let mut x = 0u128;
58    for &d in ds.iter().rev() {
59        let (xp, overflow) = x.overflowing_mul(q.into());
60        debug_assert!(!overflow, "overflow!!!! x={}", x);
61        x = xp + d as u128;
62    }
63    x
64}
65
66/// Convert `x` into base `q`, building a vector of length `n`.
67fn as_base_q(x: u128, q: u16, n: usize) -> Vec<u16> {
68    let ms = core::iter::repeat_n(q, n).collect::<Vec<_>>();
69    as_mixed_radix(x, &ms)
70}
71
72/// Convert `x` into base `q`.
73pub fn as_base_q_u128(x: u128, q: u16) -> Vec<u16> {
74    as_base_q(x, q, digits_per_u128(q))
75}
76
77/// Extra [`rand::Rng`] functionality, useful for testing.
78pub trait RngExt: rand::Rng + Sized {
79    /// Randomly generate a valid `Block`.
80    fn gen_usable_block(&mut self, modulus: u16) -> U8x16 {
81        if modulus.is_power_of_two() {
82            let nbits = (modulus - 1).count_ones();
83            if 128 % nbits == 0 {
84                return U8x16::from(self.random::<u128>());
85            }
86        }
87        let n = digits_per_u128(modulus);
88        let max = (modulus as u128).pow(n as u32);
89        U8x16::from(self.random::<u128>() % max)
90    }
91}
92
93impl<R: rand::Rng + Sized> RngExt for R {}
94
95#[cfg(test)]
96mod tests {
97    use super::*;
98    use fancy_circuits::util::RngExt as _;
99    use rand::rng;
100
101    #[test]
102    fn base_q_conversion() {
103        let mut rng = rng();
104        for _ in 0..1000 {
105            let q = rng.gen_modulus();
106            let x = u128::from(rng.gen_usable_block(q));
107            let y = as_base_q(x, q, digits_per_u128(q));
108            let z = from_base_q(&y, q);
109            assert_eq!(x, z);
110        }
111    }
112}
fancy_garbling/util.rs

fancy_garbling/
util.rs
