尋找非線性布爾函式
讓 $ \mathbb{F}_2={0,1} $ 是具有兩個元素的欄位。我想知道是否有任何已知的算法/構造，給定任何 $ n\geq 1 $ , 返回一個布爾函式 $ f:\mathbb{F}^n_2\rightarrow \mathbb{F}_2^m $ （對於一些 $ m\geq 1 $ ) 使得：
- $ f $ 是單射的；
- 對於每個 $ S\subseteq \mathbb{F}^n_2 $ ， 和 $ |S|<n $ , 的圖像 $ S $ 在下面 $ f $ , $ f(S) $ , 是一組線性獨立的向量 $ \mathbb{F}_2^m $ （被視為一個向量空間 $ \mathbb{F}_2 $ ).
兩個都 $ m $ 和返回的表示 $ f $ 應該是“簡潔的”，即大小為多項式 $ n $ .
該算法也可能是機率性的，因為這兩個必需的屬性可能具有“高機率”（可能接近 1 作為 $ m-n $ 增長）。
一種微不足道的可能性是設置 $ m=2^n $ , 並定義 $ f(x) $ 作為 $ m $ 位向量 $ y $ 和 $$ y_j=\begin{cases} 1&\text{if }j=\displaystyle\sum_{i=0}^{n-1}x_i,2^i\ 0&\text{otherwise} \end{cases} $$ 其中下標表示位索引。
這是“簡潔”嗎？由於缺乏定義，我無法判斷。我們肯定可以製作一個 $ O(n) $ 的代表 $ y $ ; 在本質上， $ x $ 會做！
如果沒有限制 $ |S|<n $ ，我們可以取 $ S=\mathbb{F}^n_2 $ ， 和 $ |S|=2^n $ ，因此沒有解決方案 $ m<2^n $ .
Kodlu 的回答是關於利用 $ |S|<n $ 為了盡量減少 $ m $ ，使用編碼理論。它還表明可能存在加密應用程序。
TL;博士
翻譯符號並讓 $ n’,m’ $ 是OP的變數，論文中的結果意味著可以擁有（通過操縱參數 $ r,s $ 滿足給定的不等式：
$$ n’=(s+1)n,\quad m’=Nn, $$ 每當 $ N $ 滿足下面給出的不等式。這似乎通過修復給出多項式複雜性 $ s. $
技術細節：
Simon McNicol 等人，在Traitor tracking against strong attack中，IEEE ISIT Proceedings 2005（抱歉，還沒有找到免費連結）已經定義 $ \delta- $ 非線性程式碼，作為任何集合的程式碼 $ \leq \delta $ 碼字，總和不是碼字。
他們採用廣義的 Reed Solomon 碼，並使用連接結構和 GRS 碼字的排列。
澄清一下，這些程式碼是多項式評估程式碼，您可以評估所有多項式 $ s, $ 獲取 MDS 程式碼 $ \mathbb{F}_{2^n} $ 維度的 $ s+1. $ 所以作為一個二進制程式碼，它的維度是 $ n(s+1). $
GRS 程式碼有字母 $ \mathbb{F}{2^n} $ 置換多項式 $ \mathbb{F}{2^n}[x] $ 指定，並且如果以下條件成立，則存在具有您想要的屬性的程式碼。這段程式碼結束了 $ \mathbb{F}_{2^n} $ 所以你需要將程式碼字表示為 $ n- $ 將碼字長度乘以的向量 $ n $ .
定理： 如果 $ 2^n>r(s+1)-1, $ 和$$ N>\binom{\delta+1}{2} s, $$然後一個 $ \delta- $ 存在從 GRS 碼派生的非線性碼。這裡 $ r $ 是構造中使用的置換多項式的次數。
轉換為二進制意味著塊長度（您的 $ m $ ) 的程式碼實際上是 $ nN. $
查看在其構造中沒有結構的隨機構造（他們希望保留 GRS 程式碼的距離分佈）可能會更有效，這會很有趣。