是F(x)=Ax+bF(X)=一個X+bF(x) =Ax+b一個偽隨機函式與否？

考慮以下鍵控函式 $ F $ : 用於安全參數 $ n, $ 關鍵是一個 $ n\times n $ 布爾矩陣 $ A $ 和 $ n- $ 位布爾向量 $ b $ . 定義 $ F_{A,b} : {0, 1}^n->{0, 1}^n $ 經過 $ F_{A,b}(x) = Ax + b $ , 其中所有操作都是模數完成的 $ 2. $ 顯示 $ F $ 不是偽隨機函式。

我想了一整天，但無法克服它，所以希望在這裡得到解決方案。謝謝。

我在網路中搜尋了類似的問題並得出瞭如下解決方案：

讓我們考慮區分器 $ D $ 查詢它的神諭 $ \mathcal{O} $ 在任意。一開始，讓 $ x=0^n $ ， 我們可以得到 $ b=\mathcal{O}(0^n) $ . 然後，我們訪問 $ \mathcal{O} $ 和 $ x_1 $ , $ x_2 $ , $ x_1+x_2 $ ， 輸出 $ 1 $ 當且僅當 $ \mathcal{O}(x_1 )+\mathcal{O}(x_2 )-b=\mathcal{O}(x_1+x_2) $ .

• 如果 $ \mathcal{O}=F $ , $ Pr⁡\left[D^F{^{(\cdot)}} (1^n)=1\right]=1 $ .
• 如果 $ \mathcal{O}=F $ 對於f從 $ Func_n $ , $ Pr⁡[D^{f(\cdot)} (1^n )=1]=2^{-n} $ .

不同的是 $ |1-2^{-n}| $ ，這是不可忽略的。因此，F 不是偽隨機函式。

F 驗證了大量的等式，例如 $ F(2x) = (F(x) + F(3x)) / 2 $ . 它是高度非隨機的。

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