Pseudo-Random-Function
關於 PRF 的問題
定義三個雜湊函式：
- $ H_1: {0, 1}^* \rightarrow \mathbb{G} $ 映射 $ x $ 到組 $ \mathbb{G} $ 素數的 $ q $
- $ H_2: \mathbb{G} \rightarrow {0, 1}^\tau $
- $ H_3: {0, 1}^* \times \mathbb{G} \rightarrow {0, 1}^\tau $
在隨機預言模型和 DDH 假設下，我注意到 PRF $ H_2(H_1(x)^k) $ 在本文中定義 $ k $ 是 PRF 密鑰。此外，我還看到了其他 PRF 變體，例如 $ H_3(x, H_1(x)^k) $ 在PAKE 論文和 $ H_1(x)^k $ 在Private Set Intersection 論文中（另見相關的先前問題）。
我有以下問題：
- 是否有任何正式證據證明它們是 PRF？
- 如果它們都是 DDH 假設下的隨機預言機模型中的 PRF，那麼這三種構造之間有什麼區別，特別是 $ H_2(H_1(x)^k) $ 和 $ H_3(x, H_1(x)^k) $ ?
是否有任何正式證據證明它們是 PRF？
在這些應用程序（PSI、PAKE）中，通常不需要證明獨立的 PRF 安全性。有時，您可以例如從比 PRF 稍弱的東西（例如，用於有限數量查詢的 PRF）中獲得安全 PSI。
在這種情況下，構造是獨立的 PRF，並且證明將遵循與 PSI/PAKE 安全證明相同的邏輯。我可以給出一個證明的想法 $ H(x)^k $ （在素數循環群中）：
- 考慮一個約簡算法 $ R $ 將三個組元素作為輸入 $ (K,A,B) $ 並執行以下操作： $ R $ 在內部執行一個 PRF 對手並扮演隨機預言機的角色 $ H $ 和建設 $ F(k,x) = H(x)^k $ . 每當 $ A $ 查詢 $ H(x) $ , 回應 $ A^{r_x} $ ; 每當 $ A $ 查詢 $ F(x) $ , 回應 $ B^{r_x} $ . 這裡 $ r_x $ 對於每個不同的 $ x $ .
- 如果 $ (K=g^k, A=g^a, B=g^{ak}) $ 然後 $ B^{r_x} = (g^{ak})^{r_x} = ((g^a)^{r_x})^k = H(x)^k $ 因此 PRF 對手看到了 PRF 的真實輸出。
- 如果 $ B $ 是均勻的 $ (K,A, B) $ ，那麼每個 $ B^{r_x} $ 是統一的，因此 PRF 對手看到來自其 PRF 預言機的隨機輸出。
- 兩種情況 $ R $ 的輸入 $ (K,A,B) $ 通過 DDH 假設無法區分，這表明 PRF 構造是安全的。
如果它們都是 DDH 假設下的隨機預言機模型中的 PRF，那麼這三種構造有什麼區別？
PSI/PAKE 應用程序是互動式協議。當我們需要針對惡意對手的安全性時，必須有一個模擬器來監視對手的行為並“解釋”它（提取輸入以代表對手發送到理想的 PSI/PAKE 功能）。在隨機預言機模型中，模擬器還可以觀察對手對隨機預言機的所有查詢。
所以使用類似的東西的原因 $ H(x,stuff) $ 代替 $ H(stuff) $ 在這樣的協議中是幫助模擬器提取的。如果 $ x $ 就在那裡（作為隨機預言的輸入），那麼模擬器的工作就容易多了。這是惡意安全 PSI 中的標準技巧（在隨機預言模型中）。