fancy_garbling/circuits/binary/
binary_equality.rs

1use crate::{BinaryBundle, FancyBinary, circuit::Circuit, circuits::binary::AndMany};
2use core::marker::PhantomData;
3use swanky_channel::Channel;
4use swanky_error::Result;
5
6/// Binary equality.
7///
8/// For [`BinaryBundle`]s `x` and `y`, return `x == y`.
9#[derive(Default)]
10pub struct BinaryEquality<'a>(PhantomData<&'a ()>);
11
12impl<'a> BinaryEquality<'a> {
13    /// Create a new [`BinaryEquality`] circuit.
14    pub fn new() -> Self {
15        Default::default()
16    }
17}
18
19impl<'a, F: FancyBinary> Circuit<F> for BinaryEquality<'a>
20where
21    F::Item: 'a,
22{
23    type Input = (&'a BinaryBundle<F::Item>, &'a BinaryBundle<F::Item>);
24    type Output = F::Item;
25
26    fn execute(
27        &self,
28        backend: &mut F,
29        inputs: Self::Input,
30        channel: &mut Channel,
31    ) -> Result<Self::Output> {
32        assert_eq!(inputs.0.moduli(), inputs.1.moduli());
33        let (x, y) = inputs;
34        let zs = x
35            .wires()
36            .iter()
37            .zip(y.wires().iter())
38            .map(|(x, y)| {
39                let xy = backend.xor(x, y);
40                backend.negate(&xy)
41            })
42            .collect::<Vec<_>>();
43
44        // If any negated XOR is 0, then the values are not equal
45        AndMany::new().execute(backend, zs.as_slice(), channel)
46    }
47}
48
49pub mod test {
50    use super::*;
51    use crate::circuit::CircuitInputMapper;
52
53    /// Circuit for testing [`BinaryEquality`].
54    pub struct TestBinaryEquality(pub usize);
55    impl<F: FancyBinary> Circuit<F> for TestBinaryEquality {
56        type Input = (BinaryBundle<F::Item>, BinaryBundle<F::Item>);
57        type Output = F::Item;
58
59        fn execute(
60            &self,
61            backend: &mut F,
62            inputs: Self::Input,
63            channel: &mut Channel,
64        ) -> Result<Self::Output> {
65            BinaryEquality::new().execute(backend, (&inputs.0, &inputs.1), channel)
66        }
67    }
68
69    impl<F: FancyBinary> CircuitInputMapper<F> for TestBinaryEquality {
70        fn map(&self, inputs: Vec<<F as crate::Fancy>::Item>) -> Self::Input {
71            assert_eq!(inputs.len(), self.0 * 2);
72            let (x, y) = inputs.split_at(self.0);
73            (BinaryBundle::new(x.to_vec()), BinaryBundle::new(y.to_vec()))
74        }
75
76        fn ninputs(&self) -> usize {
77            self.0 * 2
78        }
79
80        fn modulus(&self, _: usize) -> u16 {
81            2
82        }
83    }
84
85    #[test]
86    fn binary_equality() {
87        use crate::dummy::{Dummy, DummyVal};
88        use rand::Rng;
89
90        let mut rng = rand::thread_rng();
91        let nbits = 64;
92        let q = 1 << nbits;
93        let c = TestBinaryEquality(nbits);
94
95        for _ in 0..16 {
96            let x = rng.r#gen::<u128>() % q;
97            let y = rng.r#gen::<u128>() % q;
98            let x_input = DummyVal::to_binary(x, nbits);
99            let y_input = DummyVal::to_binary(y, nbits);
100            let output = Dummy::eval(&c, (x_input, y_input)).unwrap();
101            assert_eq!(output.val() > 0, x == y);
102        }
103
104        // Test specifically for equal values
105        for _ in 0..8 {
106            let x = rng.r#gen::<u128>() % q;
107            let x_input = DummyVal::to_binary(x, nbits);
108            let output = Dummy::eval(&c, (x_input.clone(), x_input)).unwrap();
109            assert_eq!(output.val(), 1);
110        }
111    }
112}
fancy_garbling/circuits/binary/binary_equality.rs

fancy_garbling/circuits/binary/
binary_equality.rs
