The distance from a vectorial Boolean function to the affine functions: certified values for n ≤ 4, and maximizers that are not APN
Abstract
For an (n,m)-function F:𝔽₂ⁿ → 𝔽₂ᵐ let d_(A)(F) be the minimum Hamming distance from F to an affine function, and let M(n)=max{d_(A)(F)} over (n,n)-functions. Problem 11 of the Eighth International Olympiad in Cryptography (NSUCRYPTO'2021) asks for functions in a fixed number of variables whose distance to the affine functions is as large as possible, and the organisers' status table still records the problem as unsolved. For n=4 it is not. Carlet's interpolation bound d_(A)(F) ≤ 2ⁿ-n-1 is strict for (n,n)-functions with n ≥ 4 — proved by Carlet, and proved again by Biryukov, Tureček and Udovenko at EUROCRYPT 2026, whose introduction names the olympiad problem — while Ryabov computes d_(A)(f)=10 for every APN function in four variables and states that this value is the maximum over all (4,4)-functions. So M(4)=10 is in print. We state that attribution first, and then contribute two things. First, a complete machine-checked account of the range n ≤ 4: the interpolation bound for all n and m with no hypothesis on F, the exact values M(2)=1 and M(3)=4 over all functions rather than the APN ones, an explicit (4,4)-function at distance at least 10 from every one of the 2²⁰ affine maps and exactly 10 from one of them, and a third proof of the matching upper bound at n=4 — a finite search of 52 six-point certificates over 1 374 496 assignments, confined to the even-weight subspace, using neither character sums nor a counting argument. Second, one statement the sources do not make: at n=4 the maximum is attained by functions that are not APN. An explicit F_(w) of differential uniformity 4 and image size 10 has d_(A)(F_(w))=10, while x³ over 𝔽₁₆ is APN, has image size 6, and reaches the same 10; with Ryabov's theorem the set of maximizers at n=4 therefore contains the APN functions strictly. Every assertion below, apart from the computations explicitly labelled as lying outside the formal development, is machine-checked in Lean 4.
Open review
This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.
Archived files
- Version 1 · current (opens in a new tab)
Source snapshot 2026-09-07 03:53 UTC
File fingerprint
98c8d13d1b386377f0eb04ef54a500541fbddca6c7cafc43cbb6a7e339946504
Claim ledger
Stated results
VD1known2026-09-03
An explicit (4,4)-function at Hamming distance exactly 10 from every one of the 2²0 affine functions F₂⁴ -> F₂⁴: F_w = [0,12,11,0,10,2,0,0,3,4,5,7,1,2,4,2] agrees with none of them at more than 6 of the 16 points, and the affine map with linear part (3,5,1,0) and constant term 0 agrees at exactly 6
VD2known2026-09-03
Every (4,4)-function agrees with some affine function at 6 or more of the 16 points, i.e. is at Hamming distance at most 10 = 2⁴ - 4 - 2 from an affine function; with VD1 this gives max_F min_A d_H(F,A) = 10 at n = 4
VD3known2026-09-03
Carlet's interpolation bound for every n and every m, with no hypothesis on F: the affine map with constant term F(0) and basis images F(eᵢ) + F(0) agrees with F at the n+1 points 0, e₁,..., eₙ, so min_A d_H(F,A) <= 2ⁿ - n - 1
VD4known2026-09-03
max_F min_A d_H(F,A) = 1 at n = 2 and = 4 at n = 3, over ALL functions F₂ⁿ -> F₂ⁿ and not only the APN ones: Carlet's bound 2ⁿ - n - 1 is attained there, which is the non-vacuity control for its strictness from n = 4 on
VD5candidate2026-09-03
The maximum distance 10 at n = 4 is attained by functions that are NOT APN: the witness F_w has differential uniformity 4 and image size 10, while x³ over GF(16) = F₂[x]/(x⁴+x+1) is APN (differential uniformity 2) and reaches the same distance 10. So the set of maximizers strictly contains the APN functions
VD6routine2026-09-03
Negative controls: an affine function is at distance 0 from itself; the witness does NOT reach Carlet's unsharpened bound 11; changing the single value F(7) from 0 to 1 drops the minimum distance to 9; the certificate list fires on the normalised witness (a genuine six-point agreement) and on the zero function, but not on every assignment
VD7known data2026-09-03
Remark 1 of IACR ePrint 2026/913 kernel-checked: the 4-bit S-box S = [3,7,4,8,6,11,0,5,13,10,9,1,12,2,14,15] has vectorial linearity 7 (minimum distance 9 to the affine functions) while its inverse has vectorial linearity 8 (minimum distance 8), so the parameter is not preserved by inversion
VD8measurement2026-09-03
MEASURED PRICE of the 4-bit S-box question: is there a permutation of F₂⁴ at Hamming distance 10 from every affine function (vectorial linearity 6)? 400,000 uniformly random 4-bit permutations all have vectorial linearity >= 7, while a random (4,4)-function reaches 6 about once in 3,000; an exhaustive depth-first search with the incremental 65,536-linear-part prune covered 3,532,644 nodes in 42 CPU-minutes and reached only 7 of the several thousand depth-6 branches, so the full search prices at roughly 700 CPU-hours – far over the cap, and PARKED
This ledger entry is reported in prose and is not bound to a Lean theorem.Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- An (n,m)-function is a map F: F₂ⁿ → F₂ᵐ. Its Hamming distance to another such map is the number of inputs where they differ, so its distance to the affine functions is
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7