Finding 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

One trivial possibility is to sets $m=2^n$, and defines $f(x)$ as the $m$-bit vector $y$ with $$y_j=\begin{cases} 1&\text{if }j=\displaystyle\sum_{i=0}^{n-1}x_i\,2^i\\ 0&\text{otherwise} \end{cases}$$ where subscripts denote bit index.

Is that "succinct"? I can't tell for lack of a definition. We sure can make an $O(n)$ representation of $y$; in essence, $x$ will do!

If there was not the restriction $|S|<n$, we could take $S=\mathbb{F}^n_2$, with $|S|=2^n$, thus there would no solution with $m<2^n$.

Kodlu's answer is about making use of $|S|<n$ in order to minimize $m$, using coding theory. Also it shows there can be cryptographic applications.

Answer 2

TL;DR

Translating the notation and letting $n',m'$ be the OP's variables, the result in the paper means that one can have (by manipulating the parameters $r,s$ to satisfy the given inequalities:

$$ n'=(s+1)n,\quad m'=Nn, $$ whenever $N$ satisfies the inequality given below. This seems to give polynomial complexity by fixing $s.$

Technical details:

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.

To clarify, these codes are polynomial evaluation codes, you evaluate all polynomials up to degree $s,$ to obtain an MDS code over $\mathbb{F}_{2^n}$ of dimension $s+1.$ So as a binary code its dimension is $n(s+1).$

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.