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

fancy_garbling/
util.rs
