fancy_garbling/
fancy.rs

1//! Traits for representing specific kinds of garbled circuit computations.
2//!
3//! The core trait of this module is [`Fancy`], which represents the basic set
4//! of operations possible by a garbled circuit. There are also extension
5//! traits, in particular [`FancyBinary`] and [`FancyArithmetic`] that further
6//! extend the core [`Fancy`] trait to provide binary and arithmetic operations,
7//! respectively.
8
9use swanky_channel::Channel;
10
11mod binary;
12mod bundle;
13mod crt;
14pub use binary::{BinaryBundle, BinaryGadgets};
15pub use bundle::{
16    ArithmeticBundleGadgets, ArithmeticProjBundleGadgets, BinaryBundleGadgets, Bundle,
17    BundleGadgets,
18};
19pub use crt::{CrtBundle, CrtGadgets, CrtProjGadgets};
20
21/// An object that has a modulus.
22pub trait HasModulus {
23    /// The modulus of the wire.
24    fn modulus(&self) -> u16;
25}
26
27/// The `Fancy` trait provides the basic set of operations possible in a garbled
28/// circuit.
29///
30/// The trait contains an associated type, [`Fancy::Item`], which defines the
31/// underlying wirelabel representation. The trait then defines several methods
32/// for:
33/// 1. Encoding a value into a wirelabel ([`Fancy::encode`] and
34///    [`Fancy::encode_many`]).
35/// 2. Receiving a wirelabel for an unknown value ([`Fancy::receive`] and
36///    [`Fancy::receive_many`]).
37/// 3. Creating a wirelabel for a fixed (public) constant value
38///    ([`Fancy::constant`]).
39/// 4. Outputting a wirelabel as its underlying value ([`Fancy::output`] and
40///    [`Fancy::outputs`]).
41///
42/// This trait can be further extended to support binary, arithmetic, and/or
43/// projections by using the [`FancyBinary`], [`FancyArithmetic`], or
44/// [`FancyProj`] extension traits, respectively.
45pub trait Fancy {
46    /// The underlying wirelabel representation of this [`Fancy`] object.
47    type Item: Clone + HasModulus;
48
49    /// Encode many wirelabels for known values.
50    ///
51    /// When writing a garbler, the return value must correspond to the zero
52    /// wire label.
53    fn encode_many(
54        &mut self,
55        values: &[u16],
56        moduli: &[u16],
57        channel: &mut Channel,
58    ) -> swanky_error::Result<Vec<Self::Item>>;
59
60    /// Receive many wirelabels for unknown values.
61    fn receive_many(
62        &mut self,
63        moduli: &[u16],
64        channel: &mut Channel,
65    ) -> swanky_error::Result<Vec<Self::Item>>;
66
67    /// Encode a constant `x` with modulus `q`.
68    fn constant(
69        &mut self,
70        x: u16,
71        q: u16,
72        channel: &mut Channel,
73    ) -> swanky_error::Result<Self::Item>;
74
75    /// Output the value associated with wirelabel `x`.
76    ///
77    /// Some [`Fancy`] implementers don't actually *return* output, but they
78    /// need to be involved in the process, so they can return `None`.
79    fn output(
80        &mut self,
81        x: &Self::Item,
82        channel: &mut Channel,
83    ) -> swanky_error::Result<Option<u16>>;
84
85    /// Output the values associated with a slice of wirelabels.
86    ///
87    /// Some [`Fancy`] implementers don't actually *return* output, but they
88    /// need to be involved in the process, so they can return `None`.
89    fn outputs(
90        &mut self,
91        xs: &[Self::Item],
92        channel: &mut Channel,
93    ) -> swanky_error::Result<Option<Vec<u16>>> {
94        let mut zs = Vec::with_capacity(xs.len());
95        for x in xs.iter() {
96            zs.push(self.output(x, channel)?);
97        }
98        Ok(zs.into_iter().collect())
99    }
100
101    /// Encode a wirelabel for a known value.
102    ///
103    /// When writing a garbler, the return value must correspond to the zero
104    /// wire label.
105    fn encode(
106        &mut self,
107        value: u16,
108        modulus: u16,
109        channel: &mut Channel,
110    ) -> swanky_error::Result<Self::Item> {
111        let mut xs = self.encode_many(&[value], &[modulus], channel)?;
112        Ok(xs.remove(0))
113    }
114
115    /// Receive a wirelabel for an unknown value.
116    fn receive(&mut self, modulus: u16, channel: &mut Channel) -> swanky_error::Result<Self::Item> {
117        let mut xs = self.receive_many(&[modulus], channel)?;
118        Ok(xs.remove(0))
119    }
120}
121
122/// Extension trait for [`Fancy`] that provides binary operations.
123pub trait FancyBinary: Fancy {
124    /// Binary XOR.
125    fn xor(&mut self, x: &Self::Item, y: &Self::Item) -> Self::Item;
126
127    /// Binary AND.
128    fn and(
129        &mut self,
130        x: &Self::Item,
131        y: &Self::Item,
132        channel: &mut Channel,
133    ) -> swanky_error::Result<Self::Item>;
134
135    /// Binary negation.
136    fn negate(&mut self, x: &Self::Item) -> Self::Item;
137
138    /// Binary OR.
139    fn or(
140        &mut self,
141        x: &Self::Item,
142        y: &Self::Item,
143        channel: &mut Channel,
144    ) -> swanky_error::Result<Self::Item> {
145        let notx = self.negate(x);
146        let noty = self.negate(y);
147        let z = self.and(&notx, &noty, channel)?;
148        Ok(self.negate(&z))
149    }
150
151    /// Binary adder. Returns the result and the carry.
152    fn adder(
153        &mut self,
154        x: &Self::Item,
155        y: &Self::Item,
156        carry_in: Option<&Self::Item>,
157        channel: &mut Channel,
158    ) -> swanky_error::Result<(Self::Item, Self::Item)> {
159        if let Some(c) = carry_in {
160            let z1 = self.xor(x, y);
161            let z2 = self.xor(&z1, c);
162            let z3 = self.xor(x, c);
163            let z4 = self.and(&z1, &z3, channel)?;
164            let carry = self.xor(&z4, x);
165            Ok((z2, carry))
166        } else {
167            let z = self.xor(x, y);
168            let carry = self.and(x, y, channel)?;
169            Ok((z, carry))
170        }
171    }
172    /// Return 1 if all wirelabels equal 1.
173    ///
174    /// # Panics
175    /// Panics if `args` is empty.
176    fn and_many(
177        &mut self,
178        args: &[Self::Item],
179        channel: &mut Channel,
180    ) -> swanky_error::Result<Self::Item> {
181        assert!(!args.is_empty(), "`args` cannot be empty");
182        args.iter()
183            .skip(1)
184            .try_fold(args[0].clone(), |acc, x| self.and(&acc, x, channel))
185    }
186
187    /// Return 1 if any wirelabel equals 1.
188    ///
189    /// # Panics
190    /// Panics if `args` is empty.
191    fn or_many(
192        &mut self,
193        args: &[Self::Item],
194        channel: &mut Channel,
195    ) -> swanky_error::Result<Self::Item> {
196        assert!(!args.is_empty(), "`args` cannot be empty");
197        args.iter()
198            .skip(1)
199            .try_fold(args[0].clone(), |acc, x| self.or(&acc, x, channel))
200    }
201
202    /// XOR many wirelabels together.
203    ///
204    /// # Panics
205    /// Panics if `args.len() < 2`.
206    fn xor_many(&mut self, args: &[Self::Item]) -> Self::Item {
207        assert!(args.len() >= 2, "`args.len()` must be two or more");
208        args.iter()
209            .skip(1)
210            .fold(args[0].clone(), |acc, x| self.xor(&acc, x))
211    }
212
213    /// If `x = 0` return the constant `b1`, otherwise return `b2`.
214    fn mux_constant_bits(
215        &mut self,
216        x: &Self::Item,
217        b1: bool,
218        b2: bool,
219        channel: &mut Channel,
220    ) -> swanky_error::Result<Self::Item> {
221        match (b1, b2) {
222            (false, true) => Ok(x.clone()),
223            (true, false) => Ok(self.negate(x)),
224            (false, false) => self.constant(0, 2, channel),
225            (true, true) => self.constant(1, 2, channel),
226        }
227    }
228
229    /// If `b = 0` return `x`, otherwise return `y`.
230    fn mux(
231        &mut self,
232        b: &Self::Item,
233        x: &Self::Item,
234        y: &Self::Item,
235        channel: &mut Channel,
236    ) -> swanky_error::Result<Self::Item> {
237        let xor = self.xor(x, y);
238        let and = self.and(b, &xor, channel)?;
239        Ok(self.xor(&and, x))
240    }
241}
242
243/// Extension trait for [`Fancy`] that provides arithmetic operations.
244pub trait FancyArithmetic: Fancy {
245    /// Add `x` and `y`.
246    ///
247    /// # Panics
248    /// This panics if `x` and `y` do not have equal moduli.
249    fn add(&mut self, x: &Self::Item, y: &Self::Item) -> Self::Item;
250
251    /// Subtract `x` and `y`.
252    ///
253    /// # Panics
254    /// This panics if `x` and `y` do not have equal moduli.
255    fn sub(&mut self, x: &Self::Item, y: &Self::Item) -> Self::Item;
256
257    /// Multiply `x` with the constant `c`.
258    fn cmul(&mut self, x: &Self::Item, c: u16) -> Self::Item;
259
260    /// Multiply `x` and `y`.
261    fn mul(
262        &mut self,
263        x: &Self::Item,
264        y: &Self::Item,
265        channel: &mut Channel,
266    ) -> swanky_error::Result<Self::Item>;
267
268    /// Sum up a slice of wires.
269    ///
270    /// # Panics
271    /// Panics if `args.len() < 2`.
272    fn add_many(&mut self, args: &[Self::Item]) -> Self::Item {
273        assert!(args.len() >= 2, "`args.len()` must be two or more");
274        let mut z = args[0].clone();
275        for x in args.iter().skip(1) {
276            z = self.add(&z, x);
277        }
278        z
279    }
280}
281
282/// Extension trait for [`Fancy`] that provides a projection gate, alongside
283/// methods that utilize projection gates.
284///
285/// # Security Warning
286/// In its current form, using projection gates in arithmetic garbling is
287/// **insecure**.
288pub trait FancyProj: Fancy {
289    /// Project `x` according to the truth table `tt`. Resulting wire has modulus `q`.
290    ///
291    /// Optional `tt` is useful for hiding the gate from the evaluator.
292    ///
293    /// # Panics
294    /// This may panic in certain implementations if `tt` is `None` when it
295    /// should be `Some`. In addition, it may panic if `tt` is improperly
296    /// formed: either the length of `tt` is smaller than `x`s modulus, or the
297    /// values in `tt` are larger than `q`.
298    fn proj(
299        &mut self,
300        x: &Self::Item,
301        q: u16,
302        tt: Option<Vec<u16>>,
303        channel: &mut Channel,
304    ) -> swanky_error::Result<Self::Item>;
305
306    /// Change the modulus of `x` to `to_modulus` using a projection gate.
307    fn mod_change(
308        &mut self,
309        x: &Self::Item,
310        to_modulus: u16,
311        channel: &mut Channel,
312    ) -> swanky_error::Result<Self::Item> {
313        let from_modulus = x.modulus();
314        if from_modulus == to_modulus {
315            return Ok(x.clone());
316        }
317        let tab = (0..from_modulus)
318            .map(|x| x % to_modulus)
319            .collect::<Vec<_>>();
320        self.proj(x, to_modulus, Some(tab), channel)
321    }
322}
323
324macro_rules! check_binary {
325    ($x:ident) => {
326        assert_eq!($x.modulus(), 2);
327    };
328}
329
330pub(crate) use check_binary;
fancy_garbling/fancy.rs

fancy_garbling/
fancy.rs
