Nonlinear boolean functions

Question

Let $\mathbb{F}_2=\{0,1\}$ be the field with two elements. I wonder if there is any known algorithm/construction that, given any $n\geq 1$, returns a boolean function $f:\mathbb{F}^n_2\rightarrow \mathbb{F}_2^m$ (for some $m\geq 1$) such that:

1. $f$ is injective;

2. for each $S\subseteq \mathbb{F}^n_2$, with $|S|<n$, the image of $S$ under $f$, $f(S)$, is a set of linearly independent vectors in $\mathbb{F}_2^m$ (seen as a vector space over $\mathbb{F}_2$).

Both $m$ and the returned representation of $f$ should be "succinct", that is, of size polynomial in $n$.

The algorithm might also be probabilistic, in the sense that the two required properties might hold with "high probability" (possibly approaching 1 as $m-n$ grows).

Answer 1

A relatively obvious, but possibly inefficient construction would be to identify the space $\Bbb{F}_2^n$ with the extension field $K=\Bbb{F}_{2^n}$. With $m=n^2$ we can then similarly identify $\Bbb{F}_2^m$ with $K^n$.

The mapping $$ f:K\to K^n, x\mapsto (1,x,x^2,\ldots,x^{n-1}) $$ will then work. The reason is that if $x_1,x_2,\ldots,x_n$ are distinct elements of $K$ the matrix $\in M_{n\times n}(K)$ with rows $f(x_i),i=1,2,\ldots,n$, is a Vandermonde matrix known to have a non-vanishing determinant. That last piece implies that $\{f(x_1),f(x_2),\ldots,f(x_n)\}$ will be linearly independent.

But, it will even be linearly independent over $K$ rather than just $\Bbb{F}_2$. That's why there is likely to be room for improvement. Particularly when linear dependence with high probability suffices.

Answer 2

Simon McNicol et al, in Traitor tracing against powerful attacks, IEEE ISIT Proceedings 2005 (sorry can't find a free link yet) have defined $\delta-$nonlinear codes, as a code where for any collection of $\leq \delta$ codewords, the sum is not a codeword.

They take generalized Reed Solomon codes and use a concatenated construction together with a permutation of the codewords of the GRS.

The GRS code has alphabet $\mathbb{F}_{2^n}$ a permutation polynomial in $\mathbb{F}_{2^n}[x]$ is specified, and if the following conditions hold, there exists a code with the property you want. This code is over $\mathbb{F}_{2^n}$ so you'd need to represent codewords as $n-$ vectors which will multiply codeword length by $n$.

Theorem: If $2^n>r(s+1)-1,$ and $$N>\binom{\delta+1}{2} s,$$ then a $\delta-$nonlinear code derived from a GRS code exists. Here $r$ is the degree of the permutation polynomial used in the construction.

Conversion to binary means that the blocklength (your $m$) of the code is actually $nN.$

It would be interesting to look at randomized constructions which wouldn't have the structure in their construction (they wanted the distance distribution of the GRS code to be preserved) which would probably be more efficient.

I will give more details later when I have more time.