fancy_garbling/garble/
garbler.rs

1use crate::{
2    AllWire, ArithmeticWire, WireLabel, WireMod2,
3    garble::binary_and::BinaryWireLabel,
4    hash_wires,
5    util::{output_tweak, tweak, tweak2},
6};
7use fancy_traits::{
8    Fancy, FancyArithmetic, FancyBinary, FancyBinaryConstant, FancyConstant, FancyEncode,
9    FancyOutput, FancyProj, HasModulus, is_binary,
10};
11use rand::{CryptoRng, Rng, RngExt};
12#[cfg(feature = "serde")]
13use serde::de::DeserializeOwned;
14use std::collections::HashMap;
15use swanky_channel::Channel;
16use swanky_field_binary::F2;
17use vectoreyes::U8x16;
18
19use super::security_warning::warn_proj;
20
21/// Streams garbled circuit ciphertexts through a callback.
22pub struct Garbler<RNG, Wire> {
23    // Zero wirelabel used for binary negation.
24    zero: Wire,
25    // Map from modulus to associated delta wirelabel.
26    deltas: HashMap<u16, Wire>,
27    current_output: usize,
28    current_gate: usize,
29    rng: RNG,
30}
31
32#[cfg(feature = "serde")]
33impl<RNG: CryptoRng + Rng, Wire: WireLabel + DeserializeOwned> Garbler<RNG, Wire> {
34    /// Load pre-chosen deltas from a file
35    pub fn load_deltas(&mut self, filename: &str) -> Result<(), Box<dyn std::error::Error>> {
36        let f = std::fs::File::open(filename)?;
37        let reader = std::io::BufReader::new(f);
38        let deltas: HashMap<u16, Wire> = serde_json::from_reader(reader)?;
39        self.deltas.extend(deltas);
40        Ok(())
41    }
42}
43
44impl<RNG: CryptoRng + Rng, Wire: WireLabel> Garbler<RNG, Wire> {
45    /// Create a new [`Garbler`].
46    pub fn new(mut rng: RNG) -> Self {
47        let delta = Wire::rand_delta(&mut rng, 2);
48        // We fix the constant `1` value to `1`, and derive the zero wirelabel
49        // as that value XORed with `Δ`.
50        let one = Wire::from_repr(U8x16::from(1u128), 2);
51        let zero = delta.clone() + one;
52        let mut deltas = HashMap::new();
53        deltas.insert(2, delta);
54        Garbler {
55            zero,
56            deltas,
57            current_gate: 0,
58            current_output: 0,
59            rng,
60        }
61    }
62
63    /// The current non-free gate index of the garbling computation
64    fn current_gate(&mut self) -> usize {
65        let current = self.current_gate;
66        self.current_gate += 1;
67        current
68    }
69
70    /// Create a delta if it has not been created yet for this modulus, otherwise just
71    /// return the existing one.
72    pub fn delta(&mut self, q: u16) -> Wire {
73        if let Some(delta) = self.deltas.get(&q) {
74            return delta.clone();
75        }
76        let w = Wire::rand_delta(&mut self.rng, q);
77        self.deltas.insert(q, w.clone());
78        w
79    }
80
81    /// The current output index of the garbling computation.
82    fn current_output(&mut self) -> usize {
83        let current = self.current_output;
84        self.current_output += 1;
85        current
86    }
87
88    /// Get the deltas, consuming the Garbler.
89    ///
90    /// This is useful for reusing wires in multiple garbled circuit instances.
91    pub fn get_deltas(self) -> HashMap<u16, Wire> {
92        self.deltas
93    }
94
95    /// Output a fresh zero wirelabel associated with the provided modulus.
96    pub fn encode_zero(&mut self, modulus: u16) -> Wire {
97        Wire::rand(&mut self.rng, modulus)
98    }
99}
100
101impl<RNG: Rng + CryptoRng, W: BinaryWireLabel> FancyBinary for Garbler<RNG, W> {
102    fn and(
103        &mut self,
104        A: &Self::Item,
105        B: &Self::Item,
106        channel: &mut Channel,
107    ) -> swanky_error::Result<Self::Item> {
108        let delta = self.delta(2);
109        let gate_num = self.current_gate();
110        let (gate0, gate1, C) = W::garble_and_gate(gate_num, A, B, &delta);
111        channel.write(&gate0)?;
112        channel.write(&gate1)?;
113        Ok(C)
114    }
115
116    fn xor(&mut self, x: &Self::Item, y: &Self::Item) -> Self::Item {
117        *x + *y
118    }
119
120    /// We can negate by having garbler xor wire with Delta
121    ///
122    /// Since we treat all garbler wires as zero,
123    /// xoring with delta conceptually negates the value of the wire
124    fn negate(&mut self, x: &Self::Item) -> Self::Item {
125        self.zero + *x
126    }
127}
128
129impl<RNG: Rng + CryptoRng> FancyBinary for Garbler<RNG, AllWire> {
130    /// We can negate by having garbler xor wire with Delta
131    ///
132    /// Since we treat all garbler wires as zero,
133    /// xoring with delta conceptually negates the value of the wire
134    fn negate(&mut self, x: &Self::Item) -> Self::Item {
135        is_binary!(x);
136
137        let zero = self.zero.clone();
138        self.xor(&zero, x)
139    }
140
141    /// Xor is just addition
142    fn xor(&mut self, x: &Self::Item, y: &Self::Item) -> Self::Item {
143        is_binary!(x);
144        is_binary!(y);
145
146        self.add(x, y)
147    }
148
149    /// Use binary and_gate
150    fn and(
151        &mut self,
152        x: &Self::Item,
153        y: &Self::Item,
154        channel: &mut Channel,
155    ) -> swanky_error::Result<Self::Item> {
156        if let (AllWire::Mod2(A), AllWire::Mod2(B), AllWire::Mod2(ref delta)) =
157            (x, y, self.delta(2))
158        {
159            let gate_num = self.current_gate();
160            let (gate0, gate1, C) = WireMod2::garble_and_gate(gate_num, A, B, delta);
161            channel.write(&gate0)?;
162            channel.write(&gate1)?;
163            return Ok(AllWire::Mod2(C));
164        }
165        // If we got here, one of the wires isn't binary
166        is_binary!(x);
167        is_binary!(y);
168
169        // Shouldn't be reachable, unless the wire has modulus 2 but is not AllWire::Mod2()
170        unreachable!()
171    }
172}
173
174impl<RNG: Rng + CryptoRng, Wire: WireLabel + ArithmeticWire> FancyArithmetic
175    for Garbler<RNG, Wire>
176{
177    fn add(&mut self, x: &Wire, y: &Wire) -> Wire {
178        assert_eq!(x.modulus(), y.modulus());
179        x.clone() + y.clone()
180    }
181
182    fn sub(&mut self, x: &Wire, y: &Wire) -> Wire {
183        assert_eq!(x.modulus(), y.modulus());
184        x.clone() - y.clone()
185    }
186
187    fn cmul(&mut self, x: &Wire, c: u16) -> Wire {
188        x.clone() * c
189    }
190
191    fn mul(&mut self, A: &Wire, B: &Wire, channel: &mut Channel) -> swanky_error::Result<Wire> {
192        if A.modulus() < B.modulus() {
193            return self.mul(B, A, channel);
194        }
195
196        let q = A.modulus();
197        let qb = B.modulus();
198        let gate_num = self.current_gate();
199
200        let D = self.delta(q);
201        let Db = self.delta(qb);
202
203        let r;
204        let mut gate = vec![Default::default(); q as usize + qb as usize - 2];
205
206        // hack for unequal moduli
207        if q != qb {
208            // would need to pack minitable into more than one u128 to support qb > 8
209            assert!(
210                qb <= 8,
211                "`B.modulus()` with asymmetric moduli is capped at 8"
212            );
213
214            r = self.rng.random::<u16>() % q;
215            let t = tweak2(gate_num as u64, 1);
216
217            let mut minitable = vec![u128::default(); qb as usize];
218            let mut B_ = B.clone();
219            for b in 0..qb {
220                if b > 0 {
221                    B_ += Db.clone();
222                }
223                let new_color = ((r + b) % q) as u128;
224                let ct = (u128::from(B_.hash(t)) & 0xFFFF) ^ new_color;
225                minitable[B_.color() as usize] = ct;
226            }
227
228            let mut packed = 0;
229            for (i, item) in minitable.iter().enumerate().take(qb as usize) {
230                packed += item << (16 * i);
231            }
232            gate.push(packed.into());
233        } else {
234            r = B.color(); // secret value known only to the garbler (ev knows r+b)
235        }
236
237        let g = tweak2(gate_num as u64, 0);
238
239        // X = H(A+aD) + arD such that a + A.color == 0
240        let alpha = (q - A.color()) % q; // alpha = -A.color
241        let X1 = A.clone() + D.clone() * alpha;
242
243        // Y = H(B + bD) + (b + r)A such that b + B.color == 0
244        let beta = (qb - B.color()) % qb;
245        let Y1 = B.clone() + Db.clone() * beta;
246
247        let [hashX, hashY] = hash_wires([&X1, &Y1], g);
248
249        let X = Wire::hash_to_mod(hashX, q) + D.clone() * (alpha * r % q);
250        let Y = Wire::hash_to_mod(hashY, q) + A.clone() * ((beta + r) % q);
251
252        let mut precomp = Vec::with_capacity(q as usize);
253        // precompute a lookup table of X.minus(&D_cmul[(a * r % q)])
254        //                            = X.plus(&D_cmul[((q - (a * r % q)) % q)])
255        let mut X_ = X.clone();
256        precomp.push(X_.to_repr());
257        for _ in 1..q {
258            X_ += D.clone();
259            precomp.push(X_.to_repr());
260        }
261
262        // We can vectorize the hashes here too, but then we need to precompute all `q` sums of A
263        // with delta [A, A + D, A + D + D, etc.]
264        // Would probably need another alloc which isn't great
265        let mut A_ = A.clone();
266        for a in 0..q {
267            if a > 0 {
268                A_ += D.clone();
269            }
270            // garbler's half-gate: outputs X-arD
271            // G = H(A+aD) ^ X+a(-r)D = H(A+aD) ^ X-arD
272            if A_.color() != 0 {
273                gate[A_.color() as usize - 1] =
274                    A_.hash(g) ^ precomp[((q - (a * r % q)) % q) as usize];
275            }
276        }
277        precomp.clear();
278
279        // precompute a lookup table of Y.minus(&A_cmul[((b+r) % q)])
280        //                            = Y.plus(&A_cmul[((q - ((b+r) % q)) % q)])
281        let mut Y_ = Y.clone();
282        precomp.push(Y_.to_repr());
283        for _ in 1..q {
284            Y_ += A.clone();
285            precomp.push(Y_.to_repr());
286        }
287
288        // Same note about vectorization as A
289        let mut B_ = B.clone();
290        for b in 0..qb {
291            if b > 0 {
292                B_ += Db.clone();
293            }
294            // evaluator's half-gate: outputs Y-(b+r)D
295            // G = H(B+bD) + Y-(b+r)A
296            if B_.color() != 0 {
297                gate[q as usize - 1 + B_.color() as usize - 1] =
298                    B_.hash(g) ^ precomp[((q - ((b + r) % q)) % q) as usize];
299            }
300        }
301
302        for block in gate.iter() {
303            channel.write(block)?;
304        }
305        Ok(X + Y)
306    }
307}
308
309impl<RNG: Rng + CryptoRng, Wire: WireLabel + ArithmeticWire> FancyProj for Garbler<RNG, Wire> {
310    fn proj(
311        &mut self,
312        A: &Wire,
313        q_out: u16,
314        tt: Option<Vec<u16>>,
315        channel: &mut Channel,
316    ) -> swanky_error::Result<Wire> {
317        warn_proj();
318        assert!(tt.is_some(), "`tt` must not be `None`");
319        let tt = tt.unwrap();
320
321        let q_in = A.modulus();
322        let mut gate = vec![Default::default(); q_in as usize - 1];
323
324        let tao = A.color();
325        let g = tweak(self.current_gate());
326
327        let Din = self.delta(q_in);
328        let Dout = self.delta(q_out);
329
330        // output zero-wire
331        // W_g^0 <- -H(g, W_{a_1}^0 - \tao\Delta_m) - \phi(-\tao)\Delta_n
332        let C = (A.clone() + Din.clone() * ((q_in - tao) % q_in)).hashback(g, q_out)
333            + Dout.clone() * ((q_out - tt[((q_in - tao) % q_in) as usize]) % q_out);
334
335        // precompute `let C_ = C.plus(&Dout.cmul(tt[x as usize]))`
336        let C_precomputed = {
337            let mut C_ = C.clone();
338            (0..q_out)
339                .map(|x| {
340                    if x > 0 {
341                        C_ += Dout.clone();
342                    }
343                    C_.to_repr()
344                })
345                .collect::<Vec<_>>()
346        };
347
348        let mut A_ = A.clone();
349        for x in 0..q_in {
350            if x > 0 {
351                A_ += Din.clone(); // avoiding expensive cmul for `A_ = A.plus(&Din.cmul(x))`
352            }
353
354            let ix = (tao as usize + x as usize) % q_in as usize;
355            if ix == 0 {
356                continue;
357            }
358
359            let ct = A_.hash(g) ^ C_precomputed[tt[x as usize] as usize];
360            gate[ix - 1] = ct;
361        }
362
363        for block in gate.iter() {
364            channel.write(block)?;
365        }
366        Ok(C)
367    }
368}
369
370impl<RNG: Rng + CryptoRng, Wire: WireLabel> Fancy for Garbler<RNG, Wire> {
371    type Item = Wire;
372}
373
374impl<RNG: CryptoRng, Wire: WireLabel> FancyConstant for Garbler<RNG, Wire> {
375    fn constant(&mut self, x: u16, q: u16, channel: &mut Channel) -> swanky_error::Result<Wire> {
376        let (zero, wire) = Wire::constant(x, q, &self.delta(q), &mut self.rng);
377        channel.write(&wire.to_repr())?;
378        Ok(zero)
379    }
380}
381
382impl<RNG: CryptoRng, Wire: WireLabel> FancyBinaryConstant for Garbler<RNG, Wire> {
383    fn constant(&mut self, x: F2) -> Self::Item {
384        if x.into() {
385            // `self.zero` corresponds to the zero wirelabel associated with the
386            // "one" wirelabel set to `F128b::ONE`.
387            self.zero.clone()
388        } else {
389            // Otherwise, the garbler uses the "null" wirelabel to represent zero.
390            Default::default()
391        }
392    }
393}
394
395impl<RNG: Rng + CryptoRng, Wire: WireLabel> FancyEncode for Garbler<RNG, Wire> {
396    fn encode_many(
397        &mut self,
398        values: &[u16],
399        moduli: &[u16],
400        channel: &mut Channel,
401    ) -> swanky_error::Result<Vec<Self::Item>> {
402        assert_eq!(values.len(), moduli.len());
403
404        let mut zeros = Vec::with_capacity(values.len());
405        for (x, q) in values.iter().zip(moduli.iter()) {
406            let delta = self.delta(*q);
407            let zero = self.encode_zero(*q);
408            let encoded = zero.clone() + delta * *x;
409            channel.write(&encoded.to_repr())?;
410            zeros.push(zero);
411        }
412        Ok(zeros)
413    }
414
415    fn receive_many(
416        &mut self,
417        _moduli: &[u16],
418        _: &mut Channel,
419    ) -> swanky_error::Result<Vec<Self::Item>> {
420        unimplemented!("Garbler cannot receive values")
421    }
422}
423
424impl<RNG: Rng + CryptoRng, Wire: WireLabel> FancyOutput for Garbler<RNG, Wire> {
425    fn output(&mut self, X: &Wire, channel: &mut Channel) -> swanky_error::Result<Option<u16>> {
426        let q = X.modulus();
427        let i = self.current_output();
428        let D = self.delta(q);
429        for k in 0..q {
430            let block = (X.clone() + D.clone() * k).hash(output_tweak(i, k));
431            channel.write(&block)?;
432        }
433        Ok(None)
434    }
435}
fancy_garbling/garble/garbler.rs

fancy_garbling/garble/
garbler.rs
