Crate hekate_math

Expand description

Binary tower fields GF(2^8) through GF(2^256), each with a second, polynomial basis for carry-less multiplication hardware.

Every level is a quadratic extension of the one below: GF(2^(2m)) = GF(2^m)[X] / (X^2 + X + τ), τ the lower level’s TowerField::EXTENSION_TAU. Block8 is the AES field, GF(2)[x] / (x^8 + x^4 + x^3 + x + 1) (FIPS-197 §4.2), and Bit is GF(2) inside it. A level stores its (lo, hi) pair as one integer, Block16(u16) to Block128(u128); Block256 holds [u128; 2].

§Two bases

Tower elements have type F. The same field in the flat basis has type Flat<F>, and the two types never mix in arithmetic. HardwareField::to_hardware maps tower to flat and HardwareField::from_hardware maps back. The flat basis is GF(2)[x] modulo:

Field	Flat modulus
GF(2^8)	x^8 + x^4 + x^3 + x + 1
GF(2^16)	x^16 + x^5 + x^3 + x + 1
GF(2^32)	x^32 + x^7 + x^3 + x^2 + 1
GF(2^64)	x^64 + x^4 + x^3 + x + 1
GF(2^128)	x^128 + x^7 + x^2 + x + 1

Flat<Block256> extends the GF(2^128) flat basis by y^2 + y + φ(τ), φ the tower-to-flat map.

PackableField groups WIDTH elements into one packed value and PackedFlat<F> is its flat form. FlatPromote embeds a flat subfield element into a flat superfield.

§Timing

By default the basis maps are bit-sliced matrix products: no branch or memory access depends on the value. Timing is not formally verified. The table-math feature swaps in lookup tables for the basis maps, the subfield lifts and GF(2^8) arithmetic; their memory access depends on the operands, for public data only.

Flat multiplication from GF(2^32) up uses PMULL on aarch64 with the aes target feature, which aarch64-unknown-linux-gnu leaves off by default (-C target-feature=+aes). Other targets take a software path with the same results.

§Features

Feature	Default	Effect
`std`	yes	without it: `no_std` with `alloc`
`parallel`	yes	Rayon for FFT buffers of 1 MiB and up
`table-math`	no	variable-time lookup tables, above

§Contents

fft holds the additive FFT over the Cantor basis (AdditiveFft, CantorBasis) and a systematic Reed-Solomon encoder (ReedSolomon). BinaryFieldExtras adds square, Frobenius, trace and a root of x^2 + x = c, for Block16 through Block256.

§Examples

§Isomorphic workflow

use hekate_math::{Block128, HardwareField, TowerField};

let a = Block128::from_uniform_bytes(&[0xaa; 32]);
let b = Block128::from_uniform_bytes(&[0xbb; 32]);

let product = (a.to_hardware() * b.to_hardware()).to_tower();
assert_eq!(product, a * b);

§SIMD vectorization

use hekate_math::{Block32, Flat, HardwareField, PackableField};

let data: Vec<Flat<Block32>> = (1..=8u32)
    .map(|i| Block32::from(i).to_hardware())
    .collect();

let a = Flat::<Block32>::pack(&data[..4]);
let b = Flat::<Block32>::pack(&data[4..]);

let mut out = [Flat::<Block32>::default(); 4];
Flat::<Block32>::unpack(a * b, &mut out);

for (i, lane) in out.iter().enumerate() {
    let expected = data[i].to_tower() * data[4 + i].to_tower();
    assert_eq!(lane.to_tower(), expected);
}

§Additive FFT

use hekate_math::{AdditiveFft, Block16, Flat, HardwareField};

let log_n = 10;
let fft = AdditiveFft::<Block16>::new(log_n)?;

let coeffs: Vec<Flat<Block16>> = (0..1u32 << log_n)
    .map(|i| Block16::from(i).to_hardware())
    .collect();

let mut data = coeffs.clone();
fft.forward_scalar(&mut data)?;
fft.inverse_scalar(&mut data)?;

assert_eq!(data, coeffs);

§Formal verification

Tower mul and invert, the NEON kernels, the constant-time basis maps and the additive FFT have Verus proofs against a GF(2^k) model, kept outside the crate build in verus/.

Re-exports§

pub use fft::AdditiveFft;
pub use fft::CantorBasis;
pub use fft::CantorError;
pub use fft::FftError;
pub use fft::ReedSolomon;
pub use fft::RsError;

Modules§

fft: Additive FFT over the Cantor basis of a binary tower field (Gao–Mateer 2010), evaluation at chosen domain points, and a systematic Reed–Solomon encoder.

Structs§

Bit: GF(2) element; the inner byte is invariantly 0 or 1.
Block8: GF(2^8) in the tower basis: bit i is the coefficient of x^i modulo x^8 + x^4 + x^3 + x + 1, as in AES (FIPS-197 §4.2). The flat basis has the same modulus, and φ(a) = a^32.
Block16: GF(2^16) in the tower basis: lo + hi·X over Block8, lo in the low 8 bits.
Block32: GF(2^32) in the tower basis: lo + hi·X over Block16, lo in the low 16 bits.
Block64: GF(2^64) in the tower basis: lo + hi·X over Block32, lo in the low 32 bits.
Block128: GF(2^128) in the tower basis: lo + hi·X over Block64, lo in the low 64 bits.
Block256: GF(2^256) in the tower basis: lo + hi·X over Block128, stored as [lo, hi].
Flat: An element of F in the flat basis; +, - and * compute in that basis.
PackedBit: 64 Bit lanes, one byte each; operators act lane by lane.
PackedBlock8: 16 Block8 lanes; operators act lane by lane.
PackedBlock16: Eight Block16 lanes; operators act lane by lane.
PackedBlock32: Four Block32 lanes; operators act lane by lane.
PackedBlock64: Two Block64 lanes; operators act lane by lane.
PackedBlock128: Four Block128 lanes; operators act lane by lane. 32-byte alignment matches the AVX2 load width.
PackedBlock256: Two Block256 lanes; operators run the scalar operation per lane.
PackedFlat: F::WIDTH flat-basis elements of F in one packed value; operators act lane by lane.

Constants§

PACKED_WIDTH_8: Lanes in PackedBlock8.
PACKED_WIDTH_16: Lanes in PackedBlock16.
PACKED_WIDTH_32: Lanes in PackedBlock32.
PACKED_WIDTH_64: Lanes in PackedBlock64.
PACKED_WIDTH_128: Lanes in PackedBlock128.
PACKED_WIDTH_256: Lanes in PackedBlock256.
PACKED_WIDTH_BIT: Lanes in PackedBit.

Traits§

BinaryFieldExtras: Square, Frobenius, absolute trace and the Artin–Schreier solver of a binary field; the solver builds the Cantor basis of the additive FFT.
CanonicalDeserialize: The inverse of CanonicalSerialize.
CanonicalSerialize: Fixed-size little-endian encoding of the tower bits: BITS / 8 bytes, one byte for Bit.
FlatPromote: Embedding of a flat subfield FromF into the flat basis of Self: promote_flat(x.to_hardware()) equals Self::from(x).to_hardware().
HardwareField: A TowerField with a flat basis: the isomorphism φ and the flat arithmetic behind Flat operators.
PackableField: A scalar type with a packed form of WIDTH lanes.
TowerField: GF(2^BITS) in the tower basis: Bit and Block8 through Block256. Addition and subtraction are XOR.