First Systematic Construction of Cryptographically Non-Linear All-or-Nothing Transforms

A paper that distinguishes three flavors of non-linearity in AONTs and gives the first general construction method — but stays in small-parameter territory.

Imagine a paper shredder that guarantees something stronger than just cutting your document into strips: unless you recover every single strip, you learn absolutely nothing about any part of the original. That's an all-or-nothing transform (AONT) — a bijection on s elements where seeing any s−t outputs reveals zero information about any t inputs. Linear AONTs are well-understood, but non-linear ones have been a blind spot. This paper maps that blind spot. The committed claim: the authors provide the first systematic framework for constructing and measuring cryptographically non-linear AONTs. They carefully distinguish three levels — non-additive, non-affine, and cryptographically non-linear (measured by differential uniformity and Walsh magnitude) — arguing that prior work conflated these categories. They then enumerate all (t, 3, 3)-AONTs for t = 1 and t = 2 computationally, proving that non-additive AONTs exist. The construction itself is elegant in its simplicity: take a known linear AONT and apply coordinate-wise symbol permutations. This is the cryptographic equivalent of remapping the alphabet on each output wire independently. The result is always an AONT (bijectivity is preserved), but the interesting question is how non-linear the output actually is. The authors measure this using ΔF-uniformity (lower is better — further from a linear function) and Walsh spectrum magnitude. The ladder context matters. Prior work on AONTs — Stinson (2001), D'Arco et al. — focused on linear constructions or existence bounds. Esfahani & Stinson (2018) established combinatorial frameworks. This paper extends that lineage but doesn't compare against any alternative non-linear construction because, well, there isn't one. That makes the ladder easy to climb but also means the paper is less of a race result and more of a territory claim. Integrity is mixed. The computational enumeration for (t, 3, 3) cases is exhaustive — they counted all valid AONTs at that parameter size, which is verifiable in principle. The statistical analysis of ΔF-uniformity reduction under random coordinate permutations is empirical rather than proved in general, though they do establish some theoretical sufficient conditions. No code release is mentioned, and the parameter sizes (s = 3, v = 3) are tiny — the real question is whether these constructions and measurements scale. The milestone gap is the paper's main limitation. The authors work with alphabet size v = 3 and s = 3 output elements. Real cryptographic deployment (think block cipher S-boxes, secret sharing, package transforms for disk encryption) operates at v = 256 and s in the dozens to hundreds. The paper acknowledges this implicitly by focusing on existence and construction principles rather than deployment-scale results. Getting the enumeration and non-linearity analysis to work at v = 16 or v = 256 would be the proof that this line of research has engineering legs. The obvious next experiment not run: apply the coordinate-permutation construction to larger linear AONTs (say, s = 8, v = 256, which are practical for block-cipher modes) and measure whether ΔF-uniformity actually improves enough to matter for differential cryptanalysis resistance. The honest read is (a) compute budget — exhaustive enumeration explodes combinatorially, and the statistical analysis gets expensive fast — combined with (c) this is a foundations paper establishing the framework for that exact follow-up.