Module xl 

XL — algebraic cryptanalysis of multivariate quadratic (MQ) systems by linearization.

Multivariate signatures (Oil-and-Vinegar, Rainbow, HFE) hide a secret behind a system of quadratic equations over a finite field; forging a signature or recovering a key reduces to solving such a system. XL does it by linearization: multiply every equation by every monomial up to a chosen degree D, treat each distinct monomial (including the quadratics) as an independent unknown, and solve the resulting linear system. When the equations are dense enough — past the degree of regularity Prof. Ding formalized — the linear system pins the original variables and the secret falls out.

The engine is field-generic over Field: Gf2 (the multilinear ring where x² = x) and Gf256 (the field multivariate signatures actually use, delegating to the pit-of-success-tested logicaffeine_base::gf256). The linear algebra is exact Gaussian elimination — no floating point.

Contract: xl_solve returns Some(x) only after verifying x satisfies the original system. It can therefore never report a spurious break — at worst it misses (needs a higher degree) and returns None. A returned solution is a genuine preimage/forgery.

Structs

Gf2

GF(2) as the multilinear ring: elements 0/1, addition is XOR, multiplication is AND.

Gf256

GF(2^8) — the field of the multivariate-signature attack surface. All arithmetic delegates to logicaffeine_base::gf256 (the exhaustively-verified shared field substrate).

MQSystem

A multivariate quadratic system in n variables: solutions are the common zeros of polys.

Traits

Field

A finite field small enough to enumerate — the arithmetic XL runs its linear algebra over.

Functions

eval

Evaluate a polynomial at an assignment x (length ≥ every variable index used).

xl_solve

Solve an MQ system by XL: linearize at increasing degrees d up to max_degree, and at each degree read the linear variables off the linear solution and verify them against the original system. Returns a verified common zero, or None if none was found by max_degree.

Type Aliases

Poly

A polynomial: monomial → coefficient, only non-zero terms stored.