我們可以使用帶有 PRG 的 Pohlig-Hellman 指數密碼來實現不經意的 PRF
交換密碼設置
- Alice 和 Bob 就 2048 位安全素數達成一致 $ p $ ， 在哪裡 $ (p-1)/2 $ 也是素數。
- 雙方都有一個加密指數 $ e $ 在範圍內 $ (1, p-1) $ 和 $ gcd(e, p-1) = 1 $ . 和一個解密指數 $ d $ 選擇這樣 $ d * e ≡ 1\bmod (p-1) $ . 愛麗絲有 $ (e_A, d_A) $ 鮑勃有 $ (e_B, d_B) $ 作為他們的私鑰對。
注意： 我還發現@fgrieu 提出了 Pohlig-Hellman 的兩種變體，以解決模冪運算的一些問題。請假設密鑰生成是根據他們在兩者中的解釋完成的。變體 1變體2
我們期望，這種可交換密碼設置應該足夠安全以供使用。
議定書
愛麗絲有一條消息 $ m $ 並希望針對此消息與 Bob 執行不知情的 PRF。
步驟如下：
- 愛麗絲播種 PRG 與 $ m $ 並生成 2048（或 2047）位隨機輸出 $ r $
一個。對於屬性 $ r $ 滿足，請檢查@fgrieu的PH 變體 2. Alice 使用模冪計算以下加密隨機序列， $ E_A(r) = r^{e_A} \bmod p $ 並將結果發送給 Bob。 3. 鮑勃計算 $ E_B(E_A(r)) = (E_A(r))^{e_B}\bmod p = E_{A,B}(r) $ 並發送結果 $ E_{A,B}(r) $ 回到愛麗絲 4. 最後 Alice 計算 $ D_A(E_{A,B}(r))=(E_{A,B}(r))^{d_A}\bmod p = E_B(r) $ .
這應該是相同的值，其中 Bob：
- 使用消息播種相同的 PRG $ m $ 要得到 $ r $ （Alice 從她的 PRG 得到的序列相同）
- 併計算 $ E_B(r) = r^{e_B}\bmod p $
我相信這個協議應該滿足 Oblivious PRF 的要求。我假設，給定一個隨機輸入，我們可以使用模冪作為 PRF。使用模冪運算的交換性質，我相信我們可以實現 Oblivious PRF。但是我不確定這是否屬實，我也不知道如何證明這一點。
一旦 Alice 和 Bob 實現了 Oblivious PRF，我對這個 OPRF 的最終目標是將其用於 Private Set Intersection 協議。基於@Mikero 在問題中的回答：Alice 如何讓 Bob 在私有地圖中查找值
您是否在這裡看到任何漏洞，是否可能會洩露任何一方的密鑰或 Alice 的消息？如果有任何點可能不安全並且應該避免或修復，您是否發現我的假設和使用模冪運算有任何問題？
我相信這個協議應該滿足 Oblivious PRF 的要求。
該協議（幾乎）與OPAQUE 論文（附錄 A）中被證明是安全的 OPRF 相同。OPRF 描述如下（最多一些正式符號），我將在括號中註釋您的符號：
**參數：**乘法寫入的組 $ \mathbb G $ 有秩序的 $ q $ 其中離散對數很難。雜湊函式 $ H(\cdot,\cdot):{0,1}^\times \mathbb G\to{0,1}^l $ . 雜湊函式 $ H’(\cdot):{0,1}^\to\mathbb G $ .
（你打電話 $ H’ $ 一個“PRG”並使用 $ \mathbb Z_p $ ，即整數組取模 $ p $ 用乘法，如 $ \mathbb G $ . 這意味著如果它說 $ a^b $ 下面的意思是 $ a^b\bmod p $ 對於這個群體。如果您需要有關實例化任何這些雜湊函式的指導，請查看我為此準備的答案）
**設置：**伺服器 $ \mathsf{S} $ 精選 $ k\gets_R\mathbb Z_q $ ，即伺服器隨機選擇一個小於的非負整數 $ q $ .
執行：
$ \mathsf U $ 想學 $ F_k(x) $ 和 $ F:\mathbb Z_q\times {0,1}^*\to\mathbb {0,1}^l $ 沒有學習 $ k $ 也沒有 $ \mathsf S $ 學 $ x $ .
- $ \mathsf U\to\mathsf S: H’(x)^r $ ， 那是 $ \mathsf U $ 選擇一個 $ r\gets_R\mathbb Z_q $ ，儲存並發送 $ H’(x)^r $ . （這是協議的第 1 步和第 2 步。）
- $ \mathsf S\to\mathsf U: \left(H’(x)^r\right)^k $ ， 那是 $ \mathsf S $ 簡單地將給定的輸入與它的秘密值取冪並返回結果。（這是您協議中的第 3 步）
- $ \operatorname{return}\ H\left(x,\left(\left(H’(x)^r\right)^k\right)^{1/r}\right) $ 那是 $ \mathsf U $ 只需“揭開”接收到的值（即交換密碼中的解密）並通過另一個散列函式返回原始輸入和接收到的值。（最後一個散列步驟已失去）
附加說明：在 OPAQUE 中， $ x $ 是密碼，可以看到 $ H’(x)^k $ 作為“鹽”和 $ H(\text{pw},s) $ 作為基於密碼的密鑰派生函式，它在客戶端進行評估以解密伺服器儲存的長期 DH 密鑰對。然後這個帶有臨時密鑰對的密鑰對被用於標準的基於 DH 的密鑰交換計算（在本例中為 HMQV）。