fancy_garbling/fancy/
crt.rs

1//! Module containing `CrtGadgets`, which are the CRT-based gadgets for `Fancy`.
2
3use super::HasModulus;
4use crate::{
5    FancyArithmetic, FancyBinary, FancyEncode, FancyOutput,
6    fancy::bundle::{Bundle, BundleGadgets},
7    util::{self},
8};
9use itertools::Itertools;
10use std::ops::{Deref, DerefMut};
11use swanky_channel::Channel;
12
13/// Bundle which is explicitly CRT-representation.
14#[derive(Clone)]
15pub struct CrtBundle<W>(Bundle<W>);
16
17impl<W: Clone + HasModulus> CrtBundle<W> {
18    /// Create a new CRT bundle from a vector of wires.
19    pub fn new(ws: Vec<W>) -> CrtBundle<W> {
20        CrtBundle(Bundle::new(ws))
21    }
22
23    /// Extract the underlying bundle from this CRT bundle.
24    pub fn extract(self) -> Bundle<W> {
25        self.0
26    }
27
28    /// Return the product of all the wires' moduli.
29    pub fn composite_modulus(&self) -> u128 {
30        util::product(&self.iter().map(HasModulus::modulus).collect_vec())
31    }
32}
33
34impl<W: Clone + HasModulus> Deref for CrtBundle<W> {
35    type Target = Bundle<W>;
36
37    fn deref(&self) -> &Bundle<W> {
38        &self.0
39    }
40}
41
42impl<W: Clone + HasModulus> DerefMut for CrtBundle<W> {
43    fn deref_mut(&mut self) -> &mut Bundle<W> {
44        &mut self.0
45    }
46}
47
48impl<W: Clone + HasModulus> From<Bundle<W>> for CrtBundle<W> {
49    fn from(b: Bundle<W>) -> CrtBundle<W> {
50        CrtBundle(b)
51    }
52}
53
54impl<F: FancyArithmetic + FancyBinary + FancyEncode + FancyOutput> CrtGadgets for F {}
55
56/// Extension trait for `Fancy` providing advanced CRT gadgets based on bundles of wires.
57pub trait CrtGadgets: BundleGadgets + FancyEncode {
58    /// Encode a CRT input bundle.
59    fn crt_encode(
60        &mut self,
61        value: u128,
62        modulus: u128,
63        channel: &mut Channel,
64    ) -> swanky_error::Result<CrtBundle<Self::Item>> {
65        let qs = util::factor(modulus);
66        let xs = util::crt(value, &qs);
67        self.encode_many(&xs, &qs, channel).map(CrtBundle::new)
68    }
69
70    /// Receive an CRT input bundle.
71    fn crt_receive(
72        &mut self,
73        modulus: u128,
74        channel: &mut Channel,
75    ) -> swanky_error::Result<CrtBundle<Self::Item>> {
76        let qs = util::factor(modulus);
77        self.receive_many(&qs, channel).map(CrtBundle::new)
78    }
79
80    /// Encode many CRT input bundles.
81    fn crt_encode_many(
82        &mut self,
83        values: &[u128],
84        modulus: u128,
85        channel: &mut Channel,
86    ) -> swanky_error::Result<Vec<CrtBundle<Self::Item>>> {
87        let mods = util::factor(modulus);
88        let nmods = mods.len();
89        let xs = values
90            .iter()
91            .flat_map(|x| util::crt(*x, &mods))
92            .collect_vec();
93        let qs = itertools::repeat_n(mods, values.len())
94            .flatten()
95            .collect_vec();
96        let mut wires = self.encode_many(&xs, &qs, channel)?;
97        let buns = (0..values.len())
98            .map(|_| {
99                let ws = wires.drain(0..nmods).collect_vec();
100                CrtBundle::new(ws)
101            })
102            .collect_vec();
103        Ok(buns)
104    }
105
106    /// Receive many CRT input bundles.
107    fn crt_receive_many(
108        &mut self,
109        n: usize,
110        modulus: u128,
111        channel: &mut Channel,
112    ) -> swanky_error::Result<Vec<CrtBundle<Self::Item>>> {
113        let mods = util::factor(modulus);
114        let nmods = mods.len();
115        let qs = itertools::repeat_n(mods, n).flatten().collect_vec();
116        let mut wires = self.receive_many(&qs, channel)?;
117        let buns = (0..n)
118            .map(|_| {
119                let ws = wires.drain(0..nmods).collect_vec();
120                CrtBundle::new(ws)
121            })
122            .collect_vec();
123        Ok(buns)
124    }
125
126    /// Output a CRT bundle and interpret it mod Q.
127    fn crt_output(
128        &mut self,
129        x: &CrtBundle<Self::Item>,
130        channel: &mut Channel,
131    ) -> swanky_error::Result<Option<u128>> {
132        let q = x.composite_modulus();
133        Ok(self
134            .output_bundle(x, channel)?
135            .map(|xs| util::crt_inv_factor(&xs, q)))
136    }
137
138    /// Output a slice of CRT bundles and interpret the outputs mod Q.
139    fn crt_outputs(
140        &mut self,
141        xs: &[CrtBundle<Self::Item>],
142        channel: &mut Channel,
143    ) -> swanky_error::Result<Option<Vec<u128>>> {
144        let mut zs = Vec::with_capacity(xs.len());
145        for x in xs.iter() {
146            let z = self.crt_output(x, channel)?;
147            zs.push(z);
148        }
149        Ok(zs.into_iter().collect())
150    }
151}
fancy_garbling/fancy/crt.rs

fancy_garbling/fancy/
crt.rs
