primitives/algebra/field/binary/
gf2_128_field.rs

1use std::{
2    iter::{Product, Sum},
3    ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
4};
5
6use ff::Field;
7use hybrid_array::Array;
8use rand::RngCore;
9use serde::{Deserialize, Serialize};
10use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
11use typenum::{U1, U128, U16};
12use wincode::{SchemaRead, SchemaWrite};
13
14use crate::{
15    algebra::{
16        field::{
17            binary::{
18                gf2_ext::{Gf2LimbsWide, MulWide},
19                Gf2_128,
20            },
21            FieldExtension,
22        },
23        ops::{AccReduce, DefaultDotProduct, IntoWide, MulAccReduce, ReduceWide},
24        uniform_bytes::FromUniformBytes,
25    },
26    random::{CryptoRngCore, Random},
27    types::{HeapArray, Positive},
28};
29
30/// GF(2^128) presented as a standalone field (`Subfield = Self`).
31///
32/// Unlike [`Gf2_128`], whose `FieldExtension` impl has `Subfield = Gf2` (so
33/// `FieldShare<Gf2_128>` = `BitShare` authenticates a single bit), this wrapper is its own
34/// subfield: `FieldShare<Gf2_128Field>` authenticates a full 128-bit secret.
35///
36/// Caveat:
37/// - Order-dependent plaintext circuit ops (`Gt`/`Ge`, signed `BitExtract`, `EuclDiv`/`Mod`) are
38///   well-defined on the byte representation but carry no algebraic meaning in char 2.
39#[derive(
40    Copy,
41    Clone,
42    Default,
43    Debug,
44    PartialEq,
45    Eq,
46    Hash,
47    PartialOrd,
48    Ord,
49    Serialize,
50    Deserialize,
51    SchemaRead,
52    SchemaWrite,
53)]
54#[serde(transparent)]
55#[repr(transparent)]
56pub struct Gf2_128Field(pub Gf2_128);
57
58///////////////////////////////////////////////////////////////////////////////////////////////////
59// Arithmetic ops
60///////////////////////////////////////////////////////////////////////////////////////////////////
61
62#[macros::op_variants(owned)]
63impl<'a> MulAssign<&'a Gf2_128Field> for Gf2_128Field {
64    #[inline]
65    fn mul_assign(&mut self, rhs: &'a Gf2_128Field) {
66        self.0 *= rhs.0;
67    }
68}
69
70#[macros::op_variants(owned)]
71impl<'a> Mul<&'a Gf2_128Field> for Gf2_128Field {
72    type Output = Self;
73
74    #[inline]
75    fn mul(mut self, rhs: &'a Gf2_128Field) -> Self::Output {
76        self.mul_assign(rhs);
77        self
78    }
79}
80
81#[macros::op_variants(owned)]
82impl<'a> AddAssign<&'a Gf2_128Field> for Gf2_128Field {
83    #[inline]
84    fn add_assign(&mut self, rhs: &'a Gf2_128Field) {
85        self.0 += rhs.0;
86    }
87}
88
89#[macros::op_variants(owned)]
90impl<'a> Add<&'a Gf2_128Field> for Gf2_128Field {
91    type Output = Self;
92
93    #[inline]
94    fn add(mut self, rhs: &'a Gf2_128Field) -> Self::Output {
95        self.add_assign(rhs);
96        self
97    }
98}
99
100#[macros::op_variants(owned)]
101impl<'a> SubAssign<&'a Gf2_128Field> for Gf2_128Field {
102    #[inline]
103    fn sub_assign(&mut self, rhs: &'a Gf2_128Field) {
104        self.0 -= rhs.0;
105    }
106}
107
108#[macros::op_variants(owned)]
109impl<'a> Sub<&'a Gf2_128Field> for Gf2_128Field {
110    type Output = Self;
111
112    #[inline]
113    fn sub(mut self, rhs: &'a Gf2_128Field) -> Self::Output {
114        self.sub_assign(rhs);
115        self
116    }
117}
118
119#[macros::op_variants(borrowed)]
120impl Neg for Gf2_128Field {
121    type Output = Gf2_128Field;
122
123    #[inline]
124    fn neg(self) -> Self::Output {
125        self
126    }
127}
128
129impl Sum for Gf2_128Field {
130    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
131        iter.fold(<Self as Field>::ZERO, |acc, x| acc + x)
132    }
133}
134
135impl<'a> Sum<&'a Self> for Gf2_128Field {
136    fn sum<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
137        iter.fold(<Self as Field>::ZERO, |acc, x| acc + x)
138    }
139}
140
141impl Product for Gf2_128Field {
142    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
143        iter.fold(<Self as Field>::ONE, |acc, x| acc * x)
144    }
145}
146
147impl<'a> Product<&'a Self> for Gf2_128Field {
148    fn product<I: Iterator<Item = &'a Self>>(iter: I) -> Self {
149        iter.fold(<Self as Field>::ONE, |acc, x| acc * x)
150    }
151}
152
153///////////////////////////////////////////////////////////////////////////////////////////////////
154// Constant time
155///////////////////////////////////////////////////////////////////////////////////////////////////
156
157impl ConditionallySelectable for Gf2_128Field {
158    #[inline]
159    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
160        Self(Gf2_128::conditional_select(&a.0, &b.0, choice))
161    }
162}
163
164impl ConstantTimeEq for Gf2_128Field {
165    #[inline]
166    fn ct_eq(&self, other: &Self) -> Choice {
167        self.0.ct_eq(&other.0)
168    }
169}
170
171///////////////////////////////////////////////////////////////////////////////////////////////////
172// Field traits
173///////////////////////////////////////////////////////////////////////////////////////////////////
174
175impl Field for Gf2_128Field {
176    const ZERO: Self = Self(<Gf2_128 as Field>::ZERO);
177    const ONE: Self = Self(<Gf2_128 as Field>::ONE);
178
179    fn random(rng: impl RngCore) -> Self {
180        Self(<Gf2_128 as Field>::random(rng))
181    }
182
183    fn square(&self) -> Self {
184        Self(self.0.square())
185    }
186
187    fn double(&self) -> Self {
188        Self(self.0.double())
189    }
190
191    fn invert(&self) -> CtOption<Self> {
192        self.0.invert().map(Self)
193    }
194
195    fn sqrt_ratio(num: &Self, div: &Self) -> (Choice, Self) {
196        let (is_valid, root) = Gf2_128::sqrt_ratio(&num.0, &div.0);
197        (is_valid, Self(root))
198    }
199
200    fn sqrt(&self) -> CtOption<Self> {
201        self.0.sqrt().map(Self)
202    }
203}
204
205impl FieldExtension for Gf2_128Field {
206    type Subfield = Self;
207    type Degree = U1;
208    type FieldBitSize = U128;
209    type FieldBytesSize = U16;
210
211    fn to_subfield_elements(&self) -> Array<Self::Subfield, Self::Degree> {
212        Array([*self])
213    }
214
215    fn from_subfield_elements(elems: Array<Self::Subfield, Self::Degree>) -> Self {
216        elems[0]
217    }
218
219    fn to_le_bytes(&self) -> Array<u8, Self::FieldBytesSize> {
220        self.0.to_le_bytes()
221    }
222
223    fn from_le_bytes(bytes: &[u8]) -> Option<Self> {
224        Gf2_128::from_le_bytes(bytes).map(Self)
225    }
226
227    fn mul_by_subfield(&self, other: &Self::Subfield) -> Self {
228        *self * other
229    }
230
231    fn generator() -> Self {
232        Self(Gf2_128::generator())
233    }
234
235    // Must delegate to the char-2 override: the trait default `*self * 2` is the zero map in a
236    // binary field.
237    fn linear_orthomorphism(&self) -> Self {
238        Self(self.0.linear_orthomorphism())
239    }
240}
241
242impl Random for Gf2_128Field {
243    fn random(rng: impl CryptoRngCore) -> Self {
244        Self(Random::random(rng))
245    }
246
247    fn random_array<M: Positive>(mut rng: impl CryptoRngCore) -> HeapArray<Self, M> {
248        let mut buf = HeapArray::<Self, M>::default().into_box_bytes();
249        rng.fill_bytes(&mut buf);
250        HeapArray::from_box_bytes(buf)
251    }
252}
253
254unsafe impl bytemuck::Zeroable for Gf2_128Field {}
255unsafe impl bytemuck::Pod for Gf2_128Field {}
256
257impl FromUniformBytes for Gf2_128Field {
258    type UniformBytes = U16;
259
260    fn from_uniform_bytes(bytes: &Array<u8, Self::UniformBytes>) -> Self {
261        Self(Gf2_128::from_uniform_bytes(bytes))
262    }
263}
264
265impl From<u64> for Gf2_128Field {
266    fn from(val: u64) -> Self {
267        Self(Gf2_128::from(val))
268    }
269}
270
271impl From<u128> for Gf2_128Field {
272    fn from(val: u128) -> Self {
273        Self(Gf2_128::from(val))
274    }
275}
276
277///////////////////////////////////////////////////////////////////////////////////////////////////
278// Wide ops
279///////////////////////////////////////////////////////////////////////////////////////////////////
280
281impl IntoWide<Gf2LimbsWide<2>> for Gf2_128Field {
282    #[inline]
283    fn to_wide(&self) -> Gf2LimbsWide<2> {
284        <Gf2_128 as IntoWide<Gf2LimbsWide<2>>>::to_wide(&self.0)
285    }
286
287    #[inline]
288    fn zero_wide() -> Gf2LimbsWide<2> {
289        <Gf2_128 as IntoWide<Gf2LimbsWide<2>>>::zero_wide()
290    }
291}
292
293impl ReduceWide<Gf2LimbsWide<2>> for Gf2_128Field {
294    #[inline]
295    fn reduce_mod_order(a: Gf2LimbsWide<2>) -> Self {
296        Self(Gf2_128::reduce_mod_order(a))
297    }
298}
299
300impl IntoWide for Gf2_128Field {
301    #[inline]
302    fn to_wide(&self) -> Self {
303        *self
304    }
305
306    #[inline]
307    fn zero_wide() -> Self {
308        <Self as Field>::ZERO
309    }
310}
311
312impl ReduceWide for Gf2_128Field {
313    #[inline]
314    fn reduce_mod_order(a: Self) -> Self {
315        a
316    }
317}
318
319impl MulAccReduce for Gf2_128Field {
320    type WideType = Gf2LimbsWide<2>;
321
322    #[inline]
323    fn mul_acc(acc: &mut Self::WideType, a: Self, b: Self) {
324        *acc += a.0.mul_wide(b.0);
325    }
326}
327
328impl MulAccReduce<Self, &Self> for Gf2_128Field {
329    type WideType = Gf2LimbsWide<2>;
330
331    #[inline]
332    fn mul_acc(acc: &mut Self::WideType, a: Self, b: &Self) {
333        <Self as MulAccReduce>::mul_acc(acc, a, *b);
334    }
335}
336
337impl MulAccReduce<&Self, Self> for Gf2_128Field {
338    type WideType = Gf2LimbsWide<2>;
339
340    #[inline]
341    fn mul_acc(acc: &mut Self::WideType, a: &Self, b: Self) {
342        <Self as MulAccReduce>::mul_acc(acc, *a, b);
343    }
344}
345
346impl MulAccReduce<&Self, &Self> for Gf2_128Field {
347    type WideType = Gf2LimbsWide<2>;
348
349    #[inline]
350    fn mul_acc(acc: &mut Self::WideType, a: &Self, b: &Self) {
351        <Self as MulAccReduce>::mul_acc(acc, *a, *b);
352    }
353}
354
355impl AccReduce for Gf2_128Field {
356    type WideType = Self;
357
358    #[inline]
359    fn acc(acc: &mut Self, a: Self) {
360        *acc += a;
361    }
362}
363
364impl AccReduce<&Self> for Gf2_128Field {
365    type WideType = Self;
366
367    #[inline]
368    fn acc(acc: &mut Self, a: &Self) {
369        *acc += a;
370    }
371}
372
373impl DefaultDotProduct for Gf2_128Field {}
374impl DefaultDotProduct<Self, &Self> for Gf2_128Field {}
375impl DefaultDotProduct<&Self, Self> for Gf2_128Field {}
376impl DefaultDotProduct<&Self, &Self> for Gf2_128Field {}
377
378#[cfg(test)]
379mod test {
380    use ff::Field;
381    use subtle::ConstantTimeEq;
382    use typenum::Unsigned;
383
384    use super::Gf2_128Field;
385    use crate::{
386        algebra::{field::FieldExtension, ops::DotProduct},
387        random::{test_rng, Random},
388    };
389
390    type M = typenum::U100;
391
392    #[test]
393    fn test_field_axioms() {
394        let mut rng = test_rng();
395        for _ in 0..M::to_usize() {
396            let a: Gf2_128Field = Random::random(&mut rng);
397            let b: Gf2_128Field = Random::random(&mut rng);
398
399            // Char 2: a + a = 0, -a = a
400            assert_eq!(a + a, Gf2_128Field::ZERO);
401            assert_eq!(-a, a);
402            assert_eq!(a - b, a + b);
403
404            // Distributivity
405            assert_eq!(a * (a + b), a * a + a * b);
406
407            // Frobenius: a^(2^128) = a
408            let mut cumul = a;
409            for _ in 0..128 {
410                cumul *= cumul;
411            }
412            assert_eq!(a, cumul);
413        }
414    }
415
416    #[test]
417    fn test_invert_and_sqrt() {
418        let mut rng = test_rng();
419
420        assert!(bool::from(Gf2_128Field::ZERO.invert().is_none()));
421
422        for _ in 0..M::to_usize() {
423            let a: Gf2_128Field = Random::random(&mut rng);
424            if bool::from(a.is_zero()) {
425                continue;
426            }
427            assert_eq!(a * a.invert().unwrap(), Gf2_128Field::ONE);
428
429            let root = a.sqrt().unwrap();
430            assert_eq!(root * root, a);
431
432            let (is_valid, ratio_root) = Gf2_128Field::sqrt_ratio_ext(&Gf2_128Field::ONE, &a);
433            assert!(bool::from(is_valid));
434            assert_eq!(ratio_root * ratio_root * a, Gf2_128Field::ONE);
435        }
436    }
437
438    #[test]
439    fn test_linear_orthomorphism() {
440        // σ and σ'(x) = σ(x) + x must both be permutations; in particular neither may be the zero
441        // map (the trait default `x * 2` is zero in char 2).
442        let mut rng = test_rng();
443        for _ in 0..M::to_usize() {
444            let a: Gf2_128Field = Random::random(&mut rng);
445            if bool::from(a.is_zero()) {
446                continue;
447            }
448            let sigma = a.linear_orthomorphism();
449            assert_ne!(sigma, Gf2_128Field::ZERO);
450            assert_ne!(sigma + a, Gf2_128Field::ZERO);
451        }
452    }
453
454    #[test]
455    fn test_byte_roundtrips() {
456        let mut rng = test_rng();
457        for _ in 0..M::to_usize() {
458            let a: Gf2_128Field = Random::random(&mut rng);
459
460            let bytes = a.to_le_bytes();
461            assert_eq!(Gf2_128Field::from_le_bytes(&bytes), Some(a));
462
463            let serialized = bincode::serialize(&a).unwrap();
464            assert_eq!(
465                bincode::deserialize::<Gf2_128Field>(&serialized).unwrap(),
466                a
467            );
468
469            let written = wincode::serialize(&a).unwrap();
470            assert_eq!(wincode::deserialize::<Gf2_128Field>(&written).unwrap(), a);
471        }
472    }
473
474    #[test]
475    fn test_dot_product() {
476        let mut rng = test_rng();
477        let a = Gf2_128Field::random_array::<typenum::U13>(&mut rng);
478        let b = Gf2_128Field::random_array::<typenum::U13>(&mut rng);
479
480        let expected = a
481            .iter()
482            .zip(b.iter())
483            .fold(Gf2_128Field::ZERO, |acc, (x, y)| acc + *x * y);
484        let actual = Gf2_128Field::dot(a, b);
485        assert_eq!(expected, actual);
486
487        assert_eq!(
488            Gf2_128Field::ZERO,
489            Gf2_128Field::dot(
490                std::iter::empty::<Gf2_128Field>(),
491                std::iter::empty::<Gf2_128Field>()
492            )
493        );
494    }
495
496    #[test]
497    fn test_constant_time_eq() {
498        let a = Gf2_128Field::from(42u64);
499        assert!(bool::from(a.ct_eq(&Gf2_128Field::from(42u64))));
500        assert!(!bool::from(a.ct_eq(&Gf2_128Field::from(43u64))));
501    }
502}
primitives/algebra/field/binary/gf2_128_field.rs

primitives/algebra/field/binary/
gf2_128_field.rs
