fancy_garbling/
wire.rs

1//! Wirelabels for use in garbled circuits.
2//!
3//! This module contains a [`WireLabel`] trait, alongside various instantiations
4//! of this trait. The [`WireLabel`] trait is the core underlying primitive used
5//! in garbled circuits, and represents an encoding of the value on any given
6//! wire of the circuit.
7
8use crate::util;
9use fancy_traits::HasModulus;
10use rand::CryptoRng;
11use subtle::ConditionallySelectable;
12use swanky_cr_hash::TweakableCircularCorrelationRobustHash;
13use vectoreyes::{
14    U8x16,
15    array_utils::{ArrayUnrolledExt, ArrayUnrolledOps, UnrollableArraySize},
16};
17
18mod all;
19pub use all::AllWire;
20mod mod2;
21pub use mod2::WireMod2;
22mod mod3;
23pub use mod3::WireMod3;
24mod modq;
25pub use modq::WireModQ;
26mod npaths_tab;
27
28/// Hash a batch of wires, using the same tweak for each wire.
29pub fn hash_wires<const Q: usize, W: WireLabel>(wires: [&W; Q], tweak: u128) -> [U8x16; Q]
30where
31    ArrayUnrolledOps: UnrollableArraySize<Q>,
32{
33    let batch = wires.array_map(|x| x.to_repr());
34    TweakableCircularCorrelationRobustHash::fixed_key().hash_many(batch, tweak)
35}
36
37/// A marker trait indicating that the given [`WireLabel`] instantiation
38/// supports arithmetic operations.
39pub trait ArithmeticWireLabel: WireLabel {}
40
41/// The [`BinaryWireLabel`] provides the subroutines to implement AND gates
42/// for the garbler and evaluator in [`fancy_traits::FancyBinary`].
43pub trait BinaryWireLabel: WireLabel + ConditionallySelectable {
44    /// Garbles an 'and' gate given two input wires and the delta.
45    ///
46    /// Outputs a tuple consisting of the two gates (that should be transfered to the evaluator)
47    /// and the next wirelabel for the garbler.
48    fn garble_and_gate(gate_num: usize, A: &Self, B: &Self, delta: &Self) -> (U8x16, U8x16, Self);
49
50    /// Evaluates an 'and' gate given two inputs wires and two half-gates from the garbler.
51    ///
52    /// Outputs C = A & B
53    fn evaluate_and_gate(gate_num: usize, A: &Self, B: &Self, gate0: &U8x16, gate1: &U8x16)
54    -> Self;
55}
56
57/// A trait that defines a wirelabel as used in garbled circuits.
58///
59/// At its core, a [`WireLabel`] is a way of encoding values, and operating on
60/// those encoded values.
61pub trait WireLabel:
62    Clone
63    + core::fmt::Debug
64    + core::default::Default
65    + HasModulus
66    + core::ops::Add<Output = Self>
67    + core::ops::AddAssign
68    + core::ops::Sub<Output = Self>
69    + core::ops::SubAssign
70    + core::ops::Neg<Output = Self>
71    + core::ops::Mul<u16, Output = Self>
72    + core::ops::MulAssign<u16>
73{
74    /// Converts a [`WireLabel`] into its [`U8x16`] representation.
75    fn to_repr(&self) -> U8x16;
76
77    /// The color digit of the wire.
78    fn color(&self) -> u16;
79
80    /// Converts a [`U8x16`] into its [`WireLabel`] representation, based on the
81    /// modulus `q`.
82    ///
83    /// # Panics
84    /// This panics if `q` does not align with the modulus supported by the
85    /// [`WireLabel`].
86    fn from_repr(inp: U8x16, q: u16) -> Self;
87
88    /// A random [`WireLabel`] `mod q`, with the first digit set to `1`.
89    ///
90    /// # Panics
91    /// This panics if `q` does not align with the modulus supported by the
92    /// [`WireLabel`].
93    fn rand_delta<R: CryptoRng>(rng: &mut R, q: u16) -> Self;
94
95    /// A random [`WireLabel`] `mod q`.
96    ///
97    /// # Panics
98    /// This panics if `q` does not align with the modulus supported by the
99    /// [`WireLabel`].
100    fn rand<R: CryptoRng>(rng: &mut R, q: u16) -> Self;
101
102    /// Converts a hashed block into a valid wire of the given modulus `q`.
103    ///
104    /// # Panics
105    /// This panics if `q` does not align with the modulus supported by the
106    /// [`WireLabel`].
107    fn hash_to_mod(hash: U8x16, q: u16) -> Self;
108
109    /// Computes the hash of the [`WireLabel`].
110    fn hash(&self, tweak: u128) -> U8x16 {
111        TweakableCircularCorrelationRobustHash::fixed_key().hash(self.to_repr(), tweak)
112    }
113
114    /// Computes a [`WireLabel`] for `x % q`, returning both the zero
115    /// [`WireLabel`] as well as the [`WireLabel`] for `x % q`.
116    fn constant<RNG: CryptoRng>(x: u16, q: u16, delta: &Self, rng: &mut RNG) -> (Self, Self) {
117        let zero = Self::rand(rng, q);
118        let wire = zero.clone() + delta.clone() * x;
119        (zero, wire)
120    }
121}
122
123fn _unrank(inp: u128, q: u16) -> Vec<u16> {
124    let mut x = inp;
125    let ndigits = util::digits_per_u128(q);
126    let npaths_tab = npaths_tab::lookup(q);
127    x %= npaths_tab[ndigits - 1] * q as u128;
128
129    let mut ds = vec![0; ndigits];
130    for i in (0..ndigits).rev() {
131        let npaths = npaths_tab[i];
132
133        if q <= 23 {
134            // linear search
135            let mut acc = 0;
136            for j in 0..q {
137                acc += npaths;
138                if acc > x {
139                    x -= acc - npaths;
140                    ds[i] = j;
141                    break;
142                }
143            }
144        } else {
145            // naive division
146            let d = x / npaths;
147            ds[i] = d as u16;
148            x -= d * npaths;
149        }
150        // } else {
151        //     // binary search
152        //     let mut low = 0;
153        //     let mut high = q;
154        //     loop {
155        //         let cur = (low + high) / 2;
156        //         let l = npaths * cur as u128;
157        //         let r = npaths * (cur as u128 + 1);
158        //         if x >= l && x < r {
159        //             x -= l;
160        //             ds[i] = cur;
161        //             break;
162        //         }
163        //         if x < l {
164        //             high = cur;
165        //         } else {
166        //             // x >= r
167        //             low = cur;
168        //         }
169        //     }
170        // }
171    }
172    ds
173}
fancy_garbling/wire.rs

fancy_garbling/
wire.rs
