關於 Banerjee、Peikert 和 Rosen 的偽隨機函式構造的問題
假設 LWE 的硬度，我試圖理解 Banerjee、Peikert 和 Rosen 在本文中建構的以下偽隨機函式。考慮以下基於 LWE/LWR 的偽隨機函式：
$$ F_{A, S_1,\dots, S_k}(x_1,\dots,x_k) = \left\lfloor A\prod_{i =1}^k S_i^{x_i}\right\rceil_p, $$
在哪裡 $ A \in \mathbb{Z}_q^{m\times n} $ 並且每個 $ S_i \in \mathbb{Z}_q^{n\times n} $ .
我對這個結構有一些疑問。
- 之間有什麼關係 $ k $ , $ n $ 和 $ m $ ? 有多大 $ p $ 和 $ q $ 不得不？
- 最著名的算法破壞此函式的安全性所花費的時間將如何擴展 $ k $ , $ n $ ， 和 $ m $ ?
- 在第 22 頁的連結文件中，提到，
為了避免有效的攻擊（如介紹中所述），分佈 $ \psi $ 應該選擇這樣的許多產品 $ S_i \rightarrow \psi $ 不會顯著降低熵 $$ \begin{equation} A\prod_{i =1}^k S_i. \end{equation} $$
的輸出 $ F $ 是一個矩陣。矩陣的熵是什麼意思？而且，這句話是否表明 $ F $ 是一對一的功能嗎？
首先，BPR 有後續工作，包括實用的PRF和PRG。這裡的“實用”意味著非常快——每字節約 5 個週期（對於 PRG iirc，小至約 3 個）。這在使用 AES-NI 的 AES 的 10 倍以內。不過，有一些警告：
- 鑰匙非常大
- 我相信使用了AVX指令，所以使用了一些硬體加速
- 選擇非常小的參數。
這些小參數使得 LWR/LWE 等價不再成立
$$ 1 $$，而且對於硬格問題並沒有真正有意義的簡化。因此，通過分析少數已知攻擊來具體選擇安全/參數。這聽起來你會感興趣。
- k，n和m之間的關係是什麼？p 和 q 必須有多大？
這取決於您是否希望它是可證明安全的或啟發式安全的。為了可證明的安全性，您連結的論文的定理 5.2 似乎準確地為您提供了您想要的關係。對於啟發式安全性（使用較小的參數），需要注意的相關事項是：
- PRF 文件的第 4 節，以及
- PRG 文件的第 3 節。
但它們並沒有給出你可能想要的很好的不等式，因為這樣的不等式是未知的。相反，他們針對特定參數選擇評估少數已知攻擊。
- 最知名的算法破壞這個函式的安全性所花費的時間與 k、n 和 m 相比如何？
請參閱 PRF 論文的第 4 節和 PRG 論文的第 3 節，其中完成了幾個相關的計算。
3.a F的輸出是一個矩陣。矩陣的熵是什麼意思？
嚴格來說，什麼都沒有。熵是機率分佈的一個屬性，所以只有當人們看到時，這種說法才有意義。 $ F $ 不是作為矩陣，而是作為矩陣上的分佈。為了了解作者的意思，讓 $ q = p_0 p_1 $ 是一個半素數。那麼，如果 $ A, S_1,\dots S_k $ 分佈使得（機率為 1）：
- $ A\bmod p_0 \equiv 0 $ ， 和
- $ S_i\bmod p_1\equiv 0 $ 對所有人 $ i $ ,
然後 $ F(A, S_1,\dots, S_k) \equiv 0\bmod q $ 不斷，因此 PRF 將是可預測的。限制為 $ A, S_i $ 可逆的 $ \bmod q $ 停止這個特定的（潛在的）問題（也許更多）。
3.b 而且，這個陳述是否表明 F 是一對一的函式？
不，但預計不會。我們想要 $ F $ 與隨機函式無法區分。請注意，隨機函式不是 1-1（您可以通過一種稱為“PRP-PRF 切換”的技術對此進行量化，但這並不是特別相關）。
$$ 1 $$請注意，對於大多數“實用的”基於晶格的原語來說，情況已經如此——例如，SABER 以小模數 MLWR 的具體安全性為基礎，儘管它的模數為 $ 2^{13}\approx 8k $ 遠大於模量 $ q = 257 $ 這些 PRF/PRG 使用。這有點相關，因為最近討論過小模量 LWR 的密碼分析不是特別好。請參閱此 NIST PQC Google組執行緒。自從~12 月的這個執行緒以來，人們進行了一些實驗（並沒有發現任何意外），但從執行緒看來，人們似乎直到一兩個月前才嘗試直接對小模量 LWR 進行密碼分析。 在某些情況下，可以使用基於 LWR 的實用原語並基於格問題獲得可證明的安全性，但我所知道的唯一“標準”是 Sam Kim （Key Homomorphic）基於格的 PRF。Hart Montgomery 還有一個他可以證明其安全性的非標準版本的 LWR 。