PRP 生成器的計算有效區分器
讓 $ n $ 是一個整數（激勵上下文有 $ n\approx2^{27} $ ）。所有其他小寫變數都是小於的非負整數 $ n $ （要點 $ \mathbb Z_n $ ）。所有大寫變數都是向量 $ n $ 不同的此類元素，或等價的排列 $ n $ 元素。
我們希望在預言機初始化的實驗中，用盡可能少的查詢有效地區分預言機，然後在查詢 $ j $ 輸出一個排列 $ V_j $ ，具有以下附加屬性： $ \forall i,\forall j,\forall k,;j\ne k\implies V_j[i]\ne V_k[i] $ .
- Oracle 1 使用早期輸出的空記憶體進行初始化，然後在每個查詢中輸出一個隨機排列，該排列均勻分佈在附加屬性仍然允許的那些之間。
- Oracle 2 通過選擇 3 個獨立的隨機均勻分佈排列進行初始化 $ P $ , $ Q $ , $ R $ ; 然後計算 $ V_j[i] $ 作為 $ R[(P[i]+Q[j])\bmod n] $ .
兩個預言機都履行了職責並可以回答 $ n $ 查詢。他們的每一個輸出，孤立地看，與隨機排列沒有區別。oracle 2 的方案和標準的格式保留加密技術允許建構一個滿足附加屬性的 PRP 生成器，具有 $ O(\ln n) $ 記憶體，並直接訪問任何輸出值。
通過計數論證，對於 $ n>4 $ ，如果我們不考慮效率，則可以使用 3 個查詢來區分。但是我們怎樣才能建立一個有效的區分器呢？
任何關於有效實施的 oracle 3 的建議，與 oracle 1 更難區分？
補充：
- 正如David Cary 所指出的，構造的東西被稱為拉丁方。Terry Ritter 進行了文獻調查，並討論了它們在密碼學中的用途。另請參閱Quasigroups and Related Systems 中的 Smile Markovski Design of crypto primitives based on quasigroups，2015。
- 可能的應用：決定如何借給參與者 $ i $ 在……之外 $ n $ , 在周 $ j $ , 樣本數 $ V_j[i] $ 在……之外 $ n $ ，另外以隨機方式，使得沒有參與者兩次獲得相同的樣本。在這種實踐中，可以使用格式保留加密將排列實現為密碼。
- 證明 Oracle 2 具有附加屬性：如果 $ j\ne k $ ，那麼（因為 $ Q $ 是一個排列，因此是單射的）它認為 $ Q[j]\ne Q[k] $ ， 因此 $ ((P[i]+Q[j])\bmod n)\ne((P[i]+Q[k])\bmod n) $ ， 因此 $ R[(P[i]+Q[j])\bmod n]\ne R[(P[i]+Q[k])\bmod n] $ ， 因此 $ V_j[i]\ne V_k[i] $ .
如果我們不考慮效率，則可以通過 3 個查詢來區分。但是我們怎樣才能建立一個有效的區分器呢？
我不確定你所說的高效是什麼意思（因為 $ n \approx 2^{27} $ 是一個小數字），但這裡是一個可能的建設性攻擊的草圖。我會讓你告訴我這是否滿足你對效率的想法。我想如果你有足夠的時間來接受一個長的（ $ n $ items）從oracle輸出，你有時間做我心目中的攻擊。為了保持符號更清晰，我不會在 $ R[ \alpha \bmod n ] $ .
查詢兩次，以獲得（假設 oracle #2）： $ V_1[i] = R[ P[1] + Q[j] ] $ 和 $ V_2[i] = R[ P[2] + Q[j] ] $ . 讓 $ \Delta = P[2] - P[1] \bmod n $ ，攻擊者不知道。不過，如果 $ V_1[i] = R[\alpha] $ 然後 $ V_2[i] = R[\alpha + \Delta] $ . 所以函式 $ F $ 映射所有 $ V_1[i] $ 至 $ V_2[i] $ （攻擊者可以計算）是一個映射所有 $ R[\alpha] $ 至 $ R[\alpha + \Delta] $ .
我認為循環結構 $ F $ 已經導致攻擊！例如，如果 $ n $ 那麼是素數 $ F $ *必須是一個簡單的循環。*這是因為序列 $ \alpha, \alpha+\Delta, \alpha+2\Delta, \ldots $ 生成所有數字 mod $ n $ 在重複之前（所以 $ F $ 訪問所有職位 $ R $ 在重複之前）。但我猜想在 oracle #1 下，攻擊者會得到 $ F $ 是一個隨機對合。所以這已經給出了具有合理偏差的攻擊，只有 2 個查詢。
一般來說，所有周期 $ F $ 必須具有劃分的周期長度 $ n $ （在 oracle #2 面前）。同樣，在 oracle #1 存在的情況下，這似乎不太可能發生。
好的，但是假設由於某種原因推理不成立。在這種情況下，請進行另一個查詢。攻擊者可以計算一個新的 $ F $ 現在再次使用 $ {V_2,V_3} $ 這次而不是 $ {V_1, V_2} $ . 如果我們幸運的話，並且 $ P[3]-P[2] = \Delta $ （這有可能發生 $ 1/n $ )，那麼攻擊者將*獲得相同的 $ F $ 和以前一樣！*同樣，我還沒有計算出機率，但是在 oracle #1 存在的情況下，這個事件的可能性似乎遠低於機率 $ 1/n $ .