fancy_garbling/wire/
mod3.rs

1use crate::{ArithmeticWire, WireLabel, wire::_unrank};
2use fancy_traits::HasModulus;
3use rand::{CryptoRng, Rng, RngExt};
4use vectoreyes::U8x16;
5
6/// Intermediate struct to deserialize WireMod3 to
7///
8/// Checks that both lsb and msb are not set before allowing to convert to WireMod3
9#[cfg(feature = "serde")]
10#[derive(serde::Deserialize)]
11struct UntrustedWireMod3 {
12    /// The least-significant bits of each `mod-3` element.
13    lsb: u64,
14    /// The most-significant bits of each `mod-3` element.
15    msb: u64,
16}
17
18#[cfg(feature = "serde")]
19impl TryFrom<UntrustedWireMod3> for WireMod3 {
20    type Error = swanky_error::Error;
21
22    fn try_from(wire: UntrustedWireMod3) -> Result<Self, Self::Error> {
23        swanky_error::ensure!(
24            wire.lsb & wire.msb == 0,
25            swanky_error::ErrorKind::OtherError,
26            "Mod 3 wire is ill-formed",
27        );
28        Ok(WireMod3 {
29            lsb: wire.lsb,
30            msb: wire.msb,
31        })
32    }
33}
34
35/// Representation of a `mod-3` wire.
36///
37/// We represent a `mod-3` wire by 64 `mod-3` elements. These elements are
38/// stored as follows: the least-significant bits of each element are stored
39/// in `lsb` and the most-significant bits of each element are stored in
40/// `msb`. This representation allows for efficient addition and
41/// multiplication as described here by the paper "Hardware Implementation
42/// of Finite Fields of Characteristic Three." D. Page, N.P. Smart. CHES
43/// 2002. Link:
44/// <https://link.springer.com/content/pdf/10.1007/3-540-36400-5_38.pdf>.
45#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
46#[cfg_attr(feature = "serde", serde(try_from = "UntrustedWireMod3"))]
47#[derive(Debug, Clone, Copy, PartialEq, Default)]
48pub struct WireMod3 {
49    /// The least-significant bits of each `mod-3` element.
50    pub(crate) lsb: u64,
51    /// The most-significant bits of each `mod-3` element.
52    pub(crate) msb: u64,
53}
54
55impl HasModulus for WireMod3 {
56    fn modulus(&self) -> u16 {
57        3
58    }
59}
60
61impl core::ops::Add for WireMod3 {
62    type Output = Self;
63
64    fn add(self, rhs: Self) -> Self::Output {
65        let a1 = self.lsb;
66        let a2 = self.msb;
67        let b1 = rhs.lsb;
68        let b2 = rhs.msb;
69
70        let t = (a1 | b2) ^ (a2 | b1);
71        let c1 = (a2 | b2) ^ t;
72        let c2 = (a1 | b1) ^ t;
73        Self { lsb: c1, msb: c2 }
74    }
75}
76
77impl core::ops::AddAssign for WireMod3 {
78    fn add_assign(&mut self, rhs: Self) {
79        *self = *self + rhs;
80    }
81}
82
83impl core::ops::Sub for WireMod3 {
84    type Output = Self;
85
86    fn sub(self, rhs: Self) -> Self::Output {
87        self + -rhs
88    }
89}
90
91impl core::ops::SubAssign for WireMod3 {
92    fn sub_assign(&mut self, rhs: Self) {
93        *self = *self - rhs;
94    }
95}
96
97impl core::ops::Neg for WireMod3 {
98    type Output = Self;
99
100    fn neg(self) -> Self::Output {
101        // Negation just involves swapping `lsb` and `msb`.
102        let mut output = self;
103        std::mem::swap(&mut output.lsb, &mut output.msb);
104        output
105    }
106}
107
108impl core::ops::Mul<u16> for WireMod3 {
109    type Output = Self;
110
111    #[allow(clippy::suspicious_arithmetic_impl)]
112    fn mul(self, rhs: u16) -> Self::Output {
113        let c = rhs % 3;
114        match c {
115            0 => Self { msb: 0, lsb: 0 },
116            1 => self,
117            2 => Self {
118                msb: self.lsb,
119                lsb: self.msb,
120            },
121            _ => unreachable!("Due to initial `rhs % 3`"),
122        }
123    }
124}
125
126impl core::ops::MulAssign<u16> for WireMod3 {
127    #[allow(clippy::suspicious_op_assign_impl)]
128    fn mul_assign(&mut self, rhs: u16) {
129        let c = rhs % 3;
130        match c {
131            0 => {
132                self.msb = 0;
133                self.lsb = 0;
134            }
135            1 => {}
136            2 => {
137                std::mem::swap(&mut self.lsb, &mut self.msb);
138            }
139            _ => unreachable!("Due to initial `rhs % 3`"),
140        }
141    }
142}
143
144impl WireMod3 {
145    /// We have to convert `block` into a valid `Mod3` encoding.
146    ///
147    /// We do this by computing the `Mod3` digits using `_unrank`,
148    /// and then map these to a `Mod3` encoding.
149    pub(crate) fn encode_block_mod3(block: U8x16) -> Self {
150        let mut lsb = 0u64;
151        let mut msb = 0u64;
152        let mut ds = _unrank(u128::from(block), 3);
153        for (i, v) in ds.drain(..64).enumerate() {
154            lsb |= ((v & 1) as u64) << i;
155            msb |= (((v >> 1) & 1u16) as u64) << i;
156        }
157        debug_assert_eq!(lsb & msb, 0);
158        Self { lsb, msb }
159    }
160}
161
162impl WireLabel for WireMod3 {
163    fn rand_delta<R: CryptoRng + Rng>(rng: &mut R, q: u16) -> Self {
164        if q != 3 {
165            panic!("[WireMod3::rand_delta] Expected modulo 3. Got {}", q);
166        }
167        let mut w = Self::rand(rng, 3);
168        w.lsb |= 1;
169        w.msb &= 0xFFFF_FFFF_FFFF_FFFE;
170        w
171    }
172
173    fn to_repr(&self) -> U8x16 {
174        // This function converts a [`WireMod3`] into its [`Block`] representation.
175        // The two 64b values stored in [`WireMod3`], i.e. the lsb and msb, and packed
176        // into a 128b value as a [`Block`].
177        (((self.msb as u128) << 64) | (self.lsb as u128)).into()
178    }
179
180    fn color(&self) -> u16 {
181        let color = (((self.msb & 1) as u16) << 1) | ((self.lsb & 1) as u16);
182        debug_assert_ne!(color, 3);
183        color
184    }
185
186    fn from_repr(inp: U8x16, q: u16) -> Self {
187        if q != 3 {
188            panic!("[WireMod3::from_block] Expected mod 3. Got mod {}", q)
189        }
190        // This function converts a Block into its WireLabel representation
191        // by splitting the Block into two u64, its least significant bits and
192        // its most significant bits.
193        let inp = u128::from(inp);
194        let lsb = inp as u64;
195        let msb = (inp >> 64) as u64;
196        debug_assert_eq!(lsb & msb, 0);
197        Self { lsb, msb }
198    }
199
200    fn rand<R: CryptoRng + Rng>(rng: &mut R, q: u16) -> Self {
201        if q != 3 {
202            panic!("[WireMod3::rand] Expected mod 3. Got mod {}", q)
203        }
204        let mut lsb = 0u64;
205        let mut msb = 0u64;
206        for (i, v) in (0..64).map(|_| rng.random::<u8>() % 3).enumerate() {
207            lsb |= ((v & 1) as u64) << i;
208            msb |= (((v >> 1) & 1) as u64) << i;
209        }
210        debug_assert_eq!(lsb & msb, 0);
211        Self { lsb, msb }
212    }
213
214    fn hash_to_mod(hash: U8x16, q: u16) -> Self {
215        if q != 3 {
216            panic!("[WireMod3::hash_to_mod] Expected mod 3. Got mod {}", q)
217        }
218        Self::encode_block_mod3(hash)
219    }
220}
221
222impl ArithmeticWire for WireMod3 {}
223
224#[cfg(test)]
225mod tests {
226    #[cfg(feature = "serde")]
227    #[test]
228    fn test_serialize_good_mod3() {
229        use crate::{WireLabel, WireMod3};
230        use rand::rng;
231
232        let mut rng = rng();
233        let w = WireMod3::rand(&mut rng, 3);
234        let serialized = serde_json::to_string(&w).unwrap();
235
236        let deserialized: WireMod3 = serde_json::from_str(&serialized).unwrap();
237
238        assert_eq!(w, deserialized);
239    }
240
241    #[cfg(feature = "serde")]
242    #[test]
243    fn test_serialize_bad_mod3() {
244        use crate::{WireLabel, WireMod3};
245        use rand::rng;
246
247        let mut rng = rng();
248        let mut w = WireMod3::rand(&mut rng, 3);
249
250        // lsb and msb can't both be set
251        w.lsb |= 1;
252        w.msb |= 1;
253        let serialized = serde_json::to_string(&w).unwrap();
254
255        let deserialized: Result<WireMod3, _> = serde_json::from_str(&serialized);
256        assert!(deserialized.is_err());
257    }
258}
fancy_garbling/wire/mod3.rs

fancy_garbling/wire/
mod3.rs
