What is the link between the parity check matrix, double-error-correcting codes and APN permutations?

Question

I am currently reading a research paper (linked below) which mentions that a map $f:V:=GF(2^{m}) \rightarrow V$ which vanishes at 0 is APN if it satisfies the condition that it is a binary code $C_{f}$ with parity check matrix $H_{f} = \begin{bmatrix} \dots & \omega^{j} & \dots \\ \dots & f(\omega^{j}) & \dots \end{bmatrix}$ that is double-error-correcting (i.e. no fewer than 5 columns sum to 0).

From other sources that I found double-error-correcting also means that the minimum distance of the code should be 5.

However, I do not understand how all these definitions tie in together. Specifically, I do not understand how "no fewer than 5 columns sum to 0" ties in with the minimum distance of the code should be 5". Further, it would be great if anyone could clarify what "minimum distance 5" means.

An APN Permutation in Dimension 6

Answer 1

This quite technical connection was ultimately proved in the paper

C. Carlet, P. Charpin and V. Zinoviev. Codes, bent functions and permutations suitable for DES-like cryptosystems. Designs, Codes and Cryptography 15(2), pp. 125–156, 1998.

See also the paper by the same authors plus Dobbertin in the IEEE Transactions on Information Theory, around the same time. I'll give an executive summary in its classical form without all the equivalences discovered later.

In pseudorandom sequence design, the Gold Sequences have the form $$ g_t=T(a z^t)+ T(z^{(2^k+1)t}), \quad t\geq 0 $$ where $T$ is the trace map from $\mathbb{F}_{2^n}$ to $\mathbb{F}_{2},$ $z$ is a primitive element in $\mathbb{F}_{2^n}$ and $gcd(n,k)=1.$

The sequence $T(az^t)$ is generated by a primitive LFSR corresponding to the characteristic polynomial $M_z(x)$ of $z$ and has period $2^n-1.$ The sequence $g_t$ is a sum of this sequence with its decimation by $2^k+1.$

Sequences taken with all their shifts form cyclic codes.

The Gold sequences viewed as a cyclic code in classical form have $k=1$, thus they are generated by the product $M_z(x)M_{z^3}(x).$

This means that the zeroes of this code are the union of those of $M_z$ $$ \{z,z^2,z^4,\ldots z^{2^{n-1}}\}, $$ and of $M_{z^3}:$ $$ \{z^3,z^6,z^{12},\ldots z^{3\cdot 2^{n-1}}\}, $$ thus have the 4 consecutive zeroes $\{z,z^2,z^3,z^4\}$ giving a cyclic BCH code of minimum distance $d=4+1=5.$