判斷非線性布爾函式是否平衡

有什麼方法可以檢查非線性布爾函式是否平衡？

除了檢查所有輸入變數之外，我想不出任何其他方式。

如果$$ w_H(f)=#{x \in {0,1}^N:f(x)=1} $$表示布爾函式真值表的漢明權重 $ f $ 在 $ N $ 變數，函式平衡當且僅當 $ w_H(f)=2^{N-1}. $

等效地，如果我們定義 Walsh-Hadamard 變換係數 $ f $ 作為 $$ \widehat{f}(a)=\sum_{x\in {0,1}^N} (-1)^{f(x)+a\cdot x}, \quad a\in {0,1}^N, $$ 然後是一個函式 $ f $ 是平衡的當且僅當 $ \widehat{f}(0)=0. $

有一些已知的平衡的非線性布爾函式結構，例如，您可以在Tang、Zhang 和 Tang的論文Construction of Balanced Boolean Functions with High Nonlinearity and Good Autocorrelation Properties中找到一些最近的結構，可在此處的 eprint 伺服器上找到。

引用自：https://crypto.stackexchange.com/questions/70554