Finding Nonlinear boolean functions 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:


$f$ is injective;
for each $S\subseteq \mathbb{F}^n_2$, with $|S|&lt;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).
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&amp;\text{if }j=\displaystyle\sum_{i=0}^{n-1}x_i\,2^i\\
0&amp;\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|&lt;n$, we could take $S=\mathbb{F}^n_2$, with $|S|=2^n$, thus there would no solution with $m&lt;2^n$.

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