PRP、PRF 和模運算
是否有任何算術或數學函式可以用作 PRP 或 PRF？因為，像 AES 這樣的傳統分組密碼被證明是好的 PRP 不是基於數學，而是基於其他原理，如混淆和擴散等。
您想要基於 DDH/RSA 的 PRF 嗎？如果是這樣，我們有他們，我會回答。——夏川
@xagawa 是的，我想要那個 :-) – Dingo13
我列出了基於數論假設的 PRF。它們是“算術或數學函式”。理論上，您可以使用 Feistel 網路從 PRF 中獲得 (S)PRP。
從 DDH 假設
Naor-Reingold 偽隨機函式是基於 DDH 假設的 PRF 。讓 $ \mathbb{G} $ 是階素數的有限群 $ q $ 帶發電機 $ g $ , DDH 問題很難解決。讓 $ {0,1}^\ell $ 成為一個域。函式定義為
$$ \mathrm{PRF_{NR}}(k, x) = g^{a_0 \prod_{i=1}^{\ell} a_i^{x_i}}, $$ 在哪裡 $ k = (a_0,a_1\dots,a_{\ell}) \in \mathbb{Z}_q^{\ell} $ . 有關證明，請參閱J. ACM 中的原始文章。 Lewko 和 Waters 在 CCS 2009（和ePrint 2009/486）中推廣了 NR PRF。他們的 PRF 基於決策線性假設（及其較弱的變體）。
最高效的一個
在 DHI 假設等更強大的假設下，我們有一個可愛的 PRF，比如說， Dodis-Yampolskiy PRF作為 可驗證隨機函式 (VRF)提出。
讓 $ {0,1}^{\ell} $ 是 PRF 的域。假設 $ 2^{\ell} $ 是安全參數的多項式。DY PRF 在對稱雙線性群上定義如下：
$$ \mathrm{PRF}_{DY}(k,x) = e(g,g)^{1/(x+k)}, $$ 在哪裡 $ k \in \mathbb{Z}_q $ . 從保理假設
這是通過組合來自任何 PRG 的 Blum-Blum-Shub PRG 和 Goldreich-Goldwasser-Micali PRF 獲得的經典結果。 Naor、Reingold 和 Rosen提高了基於因子的 PRF 的效率。請參閱ECCC TR 2001-064上的原始文章，
從晶格的硬度問題
如今，格問題經常被用來構造密碼原語。您可以從 Banerjee、Peikert 和 Rosen (EUROCRYPT 2012)、 Alwen、Krenn、Pietrzak 和 Wichs (CRYPTO 2013)以及Banerjee 和 Peikert (ePrint 2014/074)的格中找到 PRF 。