fancy_garbling/garble/
binary_and.rs

1use crate::{HasModulus, WireLabel, WireMod2, hash_wires, util::tweak2};
2use subtle::ConditionallySelectable;
3use vectoreyes::U8x16;
4
5/// The [`BinaryWireLabel`] provides the subroutines to implement AND gates
6/// for the garbler and evaluator in [`crate::fancy::FancyBinary`].
7pub trait BinaryWireLabel: WireLabel + ConditionallySelectable {
8    /// Garbles an 'and' gate given two input wires and the delta.
9    ///
10    /// Outputs a tuple consisting of the two gates (that should be transfered to the evaluator)
11    /// and the next wirelabel for the garbler.
12    fn garble_and_gate(gate_num: usize, A: &Self, B: &Self, delta: &Self) -> (U8x16, U8x16, Self);
13
14    /// Evaluates an 'and' gate given two inputs wires and two half-gates from the garbler.
15    ///
16    /// Outputs C = A & B
17    fn evaluate_and_gate(gate_num: usize, A: &Self, B: &Self, gate0: &U8x16, gate1: &U8x16)
18    -> Self;
19}
20
21impl BinaryWireLabel for WireMod2 {
22    fn garble_and_gate(gate_num: usize, A: &Self, B: &Self, delta: &Self) -> (U8x16, U8x16, Self) {
23        let q = A.modulus();
24        let D = delta;
25
26        let r = B.color(); // secret value known only to the garbler (ev knows r+b)
27
28        let g = tweak2(gate_num as u64, 0);
29
30        // X = H(A+aD) + arD such that a + A.color == 0
31        let alpha = A.color(); // alpha = -A.color
32        let X1 = *A + *D * alpha;
33
34        // Y = H(B + bD) + (b + r)A such that b + B.color == 0
35        let beta = (q - B.color()) % q;
36        let Y1 = *B + *D * beta;
37
38        let AD = *A + *D;
39        let BD = *B + *D;
40
41        // idx is always boolean for binary gates, so it can be represented as a `u8`
42        let a_selector = (A.color() as u8).into();
43        let b_selector = (B.color() as u8).into();
44
45        let B = Self::conditional_select(&BD, B, b_selector);
46        let newA = Self::conditional_select(&AD, A, a_selector);
47        let idx = u8::conditional_select(&(r as u8), &0u8, a_selector);
48
49        let [hashA, hashB, hashX, hashY] = hash_wires([&newA, &B, &X1, &Y1], g);
50
51        let X = Self::hash_to_mod(hashX, q) + *D * (alpha * r % q);
52        let Y = Self::hash_to_mod(hashY, q);
53
54        let gate0 =
55            hashA ^ U8x16::conditional_select(&X.to_repr(), &(X + *D).to_repr(), idx.into());
56        let gate1 = hashB ^ (Y + *A).to_repr();
57
58        (gate0, gate1, X + Y)
59    }
60
61    fn evaluate_and_gate(
62        gate_num: usize,
63        A: &Self,
64        B: &Self,
65        gate0: &U8x16,
66        gate1: &U8x16,
67    ) -> Self {
68        let g = tweak2(gate_num as u64, 0);
69
70        let [hashA, hashB] = hash_wires([A, B], g);
71
72        // garbler's half gate
73        let L = Self::from_repr(
74            U8x16::conditional_select(&hashA, &(hashA ^ *gate0), (A.color() as u8).into()),
75            2,
76        );
77
78        // evaluator's half gate
79        let R = Self::from_repr(
80            U8x16::conditional_select(&hashB, &(hashB ^ *gate1), (B.color() as u8).into()),
81            2,
82        );
83
84        L + R + *A * B.color()
85    }
86}
fancy_garbling/garble/binary_and.rs

fancy_garbling/garble/
binary_and.rs
