fancy_garbling/circuits/
gcd.rs

1use crate::{
2    BinaryBundle, FancyBinary,
3    circuit::Circuit,
4    circuits::binary::{BinaryEquality, BinaryMultiplex, BinarySubtraction, Mux},
5};
6use core::marker::PhantomData;
7use swanky_channel::Channel;
8use swanky_error::Result;
9
10/// Given [`BinaryBundle`]s `a` and `b`, output `GCD(a, b)`.
11#[derive(Default)]
12pub struct Gcd<'a> {
13    upper_bound: usize,
14    _phantom: PhantomData<&'a ()>,
15}
16
17impl<'a> Gcd<'a> {
18    /// Create a new [`Gcd`] circuit using a fixed upper bound.
19    ///
20    /// Since the circuit needs to be oblivious, we cannot terminate the GCD
21    /// algorithm by conditioning on the values of `a` or `b` as is the case in
22    /// the "standard" version of GCD. Instead, we rely on an upper bound on the
23    /// number of iterations we know the algorithm will terminate by. The
24    /// Euclidean algorithm based on subtractions will take no more than `N` steps
25    /// where `N` is the larger of the two numbers we are computing the GCD for.
26    pub fn new(upper_bound: usize) -> Self {
27        Self {
28            upper_bound,
29            _phantom: PhantomData,
30        }
31    }
32}
33
34impl<'a, F: FancyBinary> Circuit<F> for Gcd<'a>
35where
36    F::Item: 'a,
37{
38    type Input = (&'a BinaryBundle<F::Item>, &'a BinaryBundle<F::Item>);
39    type Output = BinaryBundle<F::Item>;
40
41    fn execute(
42        &self,
43        backend: &mut F,
44        inputs: Self::Input,
45        channel: &mut Channel,
46    ) -> Result<Self::Output> {
47        let (a_ref, b_ref) = inputs;
48        let mut a = (*a_ref).clone();
49        let mut b = (*b_ref).clone();
50        let zero = backend.constant(0, 2, channel)?;
51
52        for _ in 0..self.upper_bound {
53            // Since the circuit is non-branching, we don't know whether `a > b`
54            // and cannot branch computation based on that result of that
55            // conditional. Instead, we need to perform the computation that
56            // occurs for all cases of the predict "is a > b ?", i.e. (1) `a >
57            // b`, and (2) `b > a`. We consider the case where `a == b`
58            // separately since that is the case where we stop updating our
59            // variables and find the result of the computation `gcd(a,b)`.
60
61            // Compute `a := a - b` and check for an underflow that will help
62            // determine if `a > b`.
63            let (r_1, mut underflow_r_1) =
64                BinarySubtraction::new().execute(backend, (&a, &b), channel)?;
65            // Compute `b := b - a` and check for an underflow that will help
66            // determine if `b > a`.
67            let (r_2, mut underflow_r_2) =
68                BinarySubtraction::new().execute(backend, (&b, &a), channel)?;
69
70            let is_equal = BinaryEquality::new().execute(backend, (&a, &b), channel)?;
71
72            // The `underflow` bits act as dual purpose multiplexing bits:
73            // (1) If a > b then underflow_r_1 = 1 and underflow_r_2 = 0
74            // (2) If b > a then underflow_r_1 = 0 and underflow_r_2 = 1
75            // (3) If a == b then underflow_r_1 = underflow_r_2 = 0
76            underflow_r_1 =
77                Mux::new().execute(backend, (&is_equal, &underflow_r_1, &zero), channel)?;
78            underflow_r_2 =
79                Mux::new().execute(backend, (&is_equal, &underflow_r_2, &zero), channel)?;
80
81            // Using the `underflow` bits we multiplex in the following way:
82            // (1) If a > b, a := a - b and b := b
83            // (2) If b > a, a := a  and b := b - a
84            // (3) If a == b, a := a and b := b
85            a = BinaryMultiplex::new().execute(backend, (underflow_r_1, &a, &r_1), channel)?;
86            b = BinaryMultiplex::new().execute(backend, (underflow_r_2, &b, &r_2), channel)?;
87        }
88
89        Ok(a)
90    }
91}
fancy_garbling/circuits/gcd.rs

fancy_garbling/circuits/
gcd.rs
