fancy_garbling/wire/
modq.rs

1use crate::{ArithmeticWire, WireLabel, util, wire::_unrank};
2use fancy_traits::HasModulus;
3use rand::{CryptoRng, Rng, RngExt};
4use vectoreyes::U8x16;
5
6/// Intermediate struct to deserialize WireModQ to
7///
8/// Checks that modulus is at least 2
9#[cfg(feature = "serde")]
10#[derive(serde::Deserialize)]
11struct UntrustedWireModQ {
12    /// The modulus of the wire label
13    q: u16, // Assuming mod can fit in u16
14    /// A list of `mod-q` digits.
15    ds: Vec<u16>,
16}
17
18#[cfg(feature = "serde")]
19impl TryFrom<UntrustedWireModQ> for WireModQ {
20    type Error = swanky_error::Error;
21
22    fn try_from(wire: UntrustedWireModQ) -> Result<Self, Self::Error> {
23        swanky_error::ensure!(
24            wire.q >= 2,
25            swanky_error::ErrorKind::OtherError,
26            "Modulus must be at least two",
27        );
28
29        // Check correct length and make sure all values are less than the modulus
30        let expected_len = crate::util::digits_per_u128(wire.q);
31        let given_len = wire.ds.len();
32        swanky_error::ensure!(
33            given_len == expected_len,
34            swanky_error::ErrorKind::OtherError,
35            "Invalid number of digits. Expected: {expected_len}. Got: {given_len}"
36        );
37        if let Some(i) = wire.ds.iter().position(|&x| x >= wire.q) {
38            swanky_error::bail!(
39                swanky_error::ErrorKind::OtherError,
40                "Digit {i} is greater than the modulus",
41            );
42        }
43        Ok(WireModQ {
44            q: wire.q,
45            ds: wire.ds,
46        })
47    }
48}
49
50// Assuming mod can fit in u16
51/// Representation of a `mod-q` wire.
52///
53/// We represent a `mod-q` wire for `q > 3` by the modulus`q` alongside a
54/// list of `mod-q` digits.
55#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
56#[cfg_attr(feature = "serde", serde(try_from = "UntrustedWireModQ"))]
57#[derive(Debug, Clone, PartialEq, Default)]
58pub struct WireModQ {
59    /// The modulus of the wire label
60    q: u16,
61    /// A list of `mod-q` digits.
62    pub(crate) ds: Vec<u16>,
63}
64
65impl HasModulus for WireModQ {
66    fn modulus(&self) -> u16 {
67        self.q
68    }
69}
70
71impl core::ops::Add for WireModQ {
72    type Output = Self;
73
74    fn add(self, rhs: Self) -> Self::Output {
75        assert_eq!(self.q, rhs.q);
76
77        let mut xs = self.ds.clone();
78        let ys = &rhs.ds;
79        let q = self.q;
80
81        debug_assert_eq!(xs.len(), ys.len());
82        xs.iter_mut().zip(ys.iter()).for_each(|(x, &y)| {
83            let (zp, overflow) = (*x + y).overflowing_sub(q);
84            *x = if overflow { *x + y } else { zp }
85        });
86        Self { ds: xs, q }
87    }
88}
89
90impl core::ops::AddAssign for WireModQ {
91    fn add_assign(&mut self, rhs: Self) {
92        assert_eq!(self.q, rhs.q);
93
94        let q = self.q;
95
96        debug_assert_eq!(self.ds.len(), rhs.ds.len());
97        self.ds.iter_mut().zip(rhs.ds.iter()).for_each(|(x, &y)| {
98            let (zp, overflow) = (*x + y).overflowing_sub(q);
99            *x = if overflow { *x + y } else { zp }
100        });
101    }
102}
103
104impl core::ops::Sub for WireModQ {
105    type Output = Self;
106
107    fn sub(self, rhs: Self) -> Self::Output {
108        self + -rhs
109    }
110}
111
112impl core::ops::SubAssign for WireModQ {
113    fn sub_assign(&mut self, rhs: Self) {
114        *self = self.clone() - rhs;
115    }
116}
117
118impl core::ops::Neg for WireModQ {
119    type Output = Self;
120
121    fn neg(self) -> Self::Output {
122        let q = self.q;
123        let mut ds = self.ds.clone();
124        ds.iter_mut().for_each(|d| {
125            if *d > 0 {
126                *d = q - *d;
127            } else {
128                *d = 0;
129            }
130        });
131        Self { q, ds }
132    }
133}
134
135impl core::ops::Mul<u16> for WireModQ {
136    type Output = Self;
137
138    fn mul(self, rhs: u16) -> Self::Output {
139        let q = self.q;
140        let mut ds = self.ds.clone();
141        ds.iter_mut()
142            .for_each(|d| *d = (*d as u32 * rhs as u32 % q as u32) as u16);
143        Self { ds, q }
144    }
145}
146
147impl core::ops::MulAssign<u16> for WireModQ {
148    fn mul_assign(&mut self, rhs: u16) {
149        let q = self.q;
150        self.ds
151            .iter_mut()
152            .for_each(|d| *d = (*d as u32 * rhs as u32 % q as u32) as u16);
153    }
154}
155
156impl WireLabel for WireModQ {
157    fn rand_delta<R: CryptoRng + Rng>(rng: &mut R, q: u16) -> Self {
158        if q < 2 {
159            panic!(
160                "[WireModQ::rand_delta] Modulus must be at least 2. Got {}",
161                q
162            );
163        }
164        let mut w = Self::rand(rng, q);
165        w.ds[0] = 1;
166        w
167    }
168
169    fn to_repr(&self) -> U8x16 {
170        // This function converts a [`WireMod3`] into its [`Block`] representation.
171        // The values stored in [`WireModQ`] are repacked depending on q
172        // into a 128b value as a [`Block`].
173        util::from_base_q(&self.ds, self.q).into()
174    }
175
176    fn color(&self) -> u16 {
177        let color = self.ds[0];
178        debug_assert!(color < self.q);
179        color
180    }
181
182    fn from_repr(inp: U8x16, q: u16) -> Self {
183        if q < 2 {
184            panic!(
185                "[WireModQ::from_block] Modulus must be at least 2. Got {}",
186                q
187            );
188        }
189        // This function converts a Block into its WireLabel representation
190        // by splitting the Block into several digits mod q that can each fit
191        // into 128b.
192        let ds = if q.is_power_of_two() {
193            // It's a power of 2, just split the digits.
194            let ndigits = util::digits_per_u128(q);
195            let width = 128 / ndigits;
196            let mask = (1 << width) - 1;
197            let x = u128::from(inp);
198            (0..ndigits)
199                .map(|i| ((x >> (width * i)) & mask) as u16)
200                .collect::<Vec<u16>>()
201        } else if q <= 23 {
202            _unrank(u128::from(inp), q)
203        } else {
204            // If all else fails, do unrank using naive division.
205            _unrank(u128::from(inp), q)
206        };
207        Self { q, ds }
208    }
209
210    fn rand<R: CryptoRng + Rng>(rng: &mut R, q: u16) -> Self {
211        if q < 2 {
212            panic!("[WireModQ::rand] Modulus must be at least 2. Got {}", q);
213        }
214        let ds = (0..util::digits_per_u128(q))
215            .map(|_| rng.random::<u16>() % q)
216            .collect();
217        Self { q, ds }
218    }
219
220    fn hash_to_mod(hash: U8x16, q: u16) -> Self {
221        if q < 2 {
222            panic!(
223                "[WireModQ::hash_to_mod] Modulus must be at least 2. Got {}",
224                q
225            );
226        }
227        Self::from_repr(hash, q)
228    }
229}
230
231impl ArithmeticWire for WireModQ {}
232
233#[cfg(test)]
234mod tests {
235    #[cfg(feature = "serde")]
236    use super::WireModQ;
237    #[cfg(feature = "serde")]
238    use crate::WireLabel;
239    #[cfg(feature = "serde")]
240    use rand::RngExt;
241    #[cfg(feature = "serde")]
242    use rand::rng;
243
244    #[cfg(feature = "serde")]
245    #[test]
246    fn test_serialize_good_modQ() {
247        let mut rng = rng();
248
249        for _ in 0..16 {
250            let mut q: u16 = rng.random();
251            while q < 2 {
252                q = rng.random();
253            }
254            let w = WireModQ::rand(&mut rng, q);
255            let serialized = serde_json::to_string(&w).unwrap();
256
257            let deserialized: WireModQ = serde_json::from_str(&serialized).unwrap();
258
259            assert_eq!(w, deserialized);
260        }
261    }
262    #[cfg(feature = "serde")]
263    #[test]
264    fn test_serialize_bad_modQ_mod() {
265        let mut rng = rng();
266        let mut q: u16 = rng.random();
267        while q < 2 {
268            q = rng.random();
269        }
270
271        let mut w = WireModQ::rand(&mut rng, q);
272
273        // Manually mess with the modulus
274        w.q = 1;
275        let serialized = serde_json::to_string(&w).unwrap();
276
277        let deserialized: Result<WireModQ, _> = serde_json::from_str(&serialized);
278        assert!(deserialized.is_err());
279    }
280    #[cfg(feature = "serde")]
281    #[test]
282    fn test_serialize_bad_modQ_ds_mod() {
283        let serialized: String = "{\"q\":2,\"ds\":[1,1,0,1,0,5,1,0,0,0,1,1,1,0,0,1,1,0,1,1,1,0,0,0,1,1,0,0,1,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,0,0,0,0,1,0,1,1,0,0,1,1,0,1,0,1,0,0,1,1,1,1,1,0,1,0,0,0,0,1,1,1,1,1,1,1,1,0,1,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,1,0,1,0,1,0,0,1,1,0,0,0,0,0,0,1,1,1,0,1,1,1,1,1,1,0,0,0,0,0]}".to_string();
284
285        let deserialized: Result<WireModQ, _> = serde_json::from_str(&serialized);
286        assert!(deserialized.is_err());
287    }
288
289    #[cfg(feature = "serde")]
290    #[test]
291    fn test_serialize_bad_modQ_ds_count() {
292        let serialized: String = "{\"q\":2,\"ds\":[1,1,0,1,0,1,0,0,0,1,1,1,0,0,1,1,0,1,1,1,0,0,0,1,1,0,0,1,1,0,0,0,1,0,1,1,0,1,1,0,0,0,0,0,0,0,0,1,0,1,1,0,0,1,1,0,1,0,1,0,0,1,1,1,1,1,0,1,0,0,0,0,1,1,1,1,1,1,1,1,0,1,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,1,0,1,0,1,0,0,1,1,0,0,0,0,0,0,1,1,1,0,1,1,1,1,1,1,0,0,0,0,0]}".to_string();
293
294        let deserialized: Result<WireModQ, _> = serde_json::from_str(&serialized);
295        assert!(deserialized.is_err());
296    }
297}
fancy_garbling/wire/modq.rs

fancy_garbling/wire/
modq.rs
