Skip to main content
MathOverflow

Return to Question

Question edited so as to avoid trivial answers based on taking an exponential large $m$. Also I have made clear that I am interested in an algorithm/construction to (effectively) build $f$. Same question posted on cryptostackexchange <https://crypto.stackexchange.com/questions/63665/finding-nonline>
Source Link
Michele
Michele
  • 333
  • 1
  • 6

Let ${\bf F_2}$ denote$\mathbb{F}_2=\{0,1\}$ be the field with two elements and $f:{\bf F}^n_2\rightarrow {\bf F}_2^m$. I wonder if there is any known algorithm/construction that, withgiven any $m\geq n$$n\geq 1$, be an injectivereturns 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$).

I am looking for sufficient conditions on $f$ andBoth $m$ to guarantee the following: for each $S\subseteq {\bf F}^n_2$, $|S|<n$,and the imagereturned representation of $S$ under $f$, $f(S)$ should be "succinct", that is a set, of linearly independent vectorssize polynomial in ${\bf F}_2^m$ (as a vector space over ${\bf F}_2$)$n$.

Or, at leastThe algorithm might also be probabilistic, conditionsin the sense that guarantee this to be the case "with hightwo required properties might hold with "high probability", depending on a random choice of $S$ of fixed size(possibly approaching 1 as $m-n$ grows).

Let ${\bf F_2}$ denote the field with two elements and $f:{\bf F}^n_2\rightarrow {\bf F}_2^m$, with $m\geq n$, be an injective function.

I am looking for sufficient conditions on $f$ and $m$ to guarantee the following: for each $S\subseteq {\bf F}^n_2$, $|S|<n$, the image of $S$ under $f$, $f(S)$, is a set of linearly independent vectors in ${\bf F}_2^m$ (as a vector space over ${\bf F}_2$).

Or, at least, conditions that guarantee this to be the case "with high probability", depending on a random choice of $S$ of fixed size.

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).

added 1 character in body
Source Link
Michele
Michele
  • 333
  • 1
  • 6

Let ${\bf F_2}$ denote the field with two elements and $f:{\bf F}^n_2\rightarrow {\bf F}_2^m$, with $m\geq n$, be an injective function.

I am looking for sufficient conditions on $f$ and $m$ to guarantee the following: for anyeach $S\subseteq {\bf F}^n_2$, $|S|<n$, the image of $S$ under $f$, $f(S)$, is a set of linearly independent vectors in ${\bf F}_2^m$ (as a vector space over ${\bf F}_2$).

Or, at least, conditions that guarantee this to be the case "with high probability", depending on a random choice of $S$ of fixed size.

Let ${\bf F_2}$ denote the field with two elements and $f:{\bf F}^n_2\rightarrow {\bf F}_2^m$, with $m\geq n$, be an injective function.

I am looking for sufficient conditions on $f$ and $m$ to guarantee the following: for any $S\subseteq {\bf F}^n_2$, $|S|<n$, the image of $S$ under $f$, $f(S)$, is a set of linearly independent vectors in ${\bf F}_2^m$ (as a vector space over ${\bf F}_2$).

Or, at least, conditions that guarantee this to be the case "with high probability", depending on a random choice of $S$ of fixed size.

Let ${\bf F_2}$ denote the field with two elements and $f:{\bf F}^n_2\rightarrow {\bf F}_2^m$, with $m\geq n$, be an injective function.

I am looking for sufficient conditions on $f$ and $m$ to guarantee the following: for each $S\subseteq {\bf F}^n_2$, $|S|<n$, the image of $S$ under $f$, $f(S)$, is a set of linearly independent vectors in ${\bf F}_2^m$ (as a vector space over ${\bf F}_2$).

Or, at least, conditions that guarantee this to be the case "with high probability", depending on a random choice of $S$ of fixed size.

Source Link
Michele
Michele
  • 333
  • 1
  • 6

Nonlinear boolean functions

Let ${\bf F_2}$ denote the field with two elements and $f:{\bf F}^n_2\rightarrow {\bf F}_2^m$, with $m\geq n$, be an injective function.

I am looking for sufficient conditions on $f$ and $m$ to guarantee the following: for any $S\subseteq {\bf F}^n_2$, $|S|<n$, the image of $S$ under $f$, $f(S)$, is a set of linearly independent vectors in ${\bf F}_2^m$ (as a vector space over ${\bf F}_2$).

Or, at least, conditions that guarantee this to be the case "with high probability", depending on a random choice of $S$ of fixed size.