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

fancy_garbling/garble/
garbler.rs
