Randomness
從隨機函式構造隨機排列？
我們如何從（偽）隨機函式構造（偽）隨機排列？
我從 Luby-Rackoff 看到了一種方法，它允許構造一個長度的 PRP $ 2N $ 從輸入/輸出長度的 PRF $ N $ . 有沒有保持相同長度的方法 $ N $ ?
我正在尋找一種比截斷輸出具有更好安全範圍的方法 $ N $ -bits 輸出偽隨機函式以獲取輸出[數學處理錯誤] $ N/2 $ -bits 並使用 Luby-Rackoff 結構。
這裡有很多可能的解決方案。如果不更仔細地給出您的要求，就不可能說出什麼是有效的解決方案。這裡有一堆方案提供了比簡單截斷更好的安全性[數學處理錯誤] $ N/2 $ 位並應用 4 輪 Luby-Rackoff：
- 例如，一種方法是將隨機函式截斷為[數學處理錯誤] $ N/2 $ 位，然後使用 6 輪或更多輪 Luby-Rackoff 結構。Paterin 在 1998 年的 FSE 上有一篇論文，顯然證明 6 輪可以提供高達 $ O(2^{3N/8}) $ 選擇明文/密文查詢。他後來在 Crypto 2003 上也有一篇論文，顯然證明了 10 輪足夠安全[數學處理錯誤] $ O(2^{N(1-\epsilon)/2}) $ 選擇明文/密文查詢。不要讓我解釋證明；我不明白他們。我不知道這些結果的任何具體安全版本，因此很難確切知道這在實踐中為您提供了多少安全性。
- 另一種方法是將隨機函式截斷為 1 位輸出（和 $ N-1 $ 輸入位），然後建構一個最大不平衡的 Feistel 網路，該網路使用 $ 4N $ 回合。Naor 和 Reingold表明（Journal of Cryptology，1999 年 1 月），這將為多達 $ O(2^{N/2}) $ 選擇明文/密文查詢。（從技術上講，他們的結果假設您使用了成對獨立排列，然後 $ 2N $ 不平衡的Feistel輪次，而不是另一個成對獨立排列，所以如果你真的關心可證明的安全性，你可以使用它：但我懷疑他們的結果可能適用於 $ 4N $ 還有幾輪不平衡的Feistel。）
- 更好的是，如果你做了足夠多的最大不平衡 Feistel 網路，你可以任意接近 $ O(2^N) $ 安全。將隨機函式截斷為一個 $ N-1 $ 輸入位和1個輸出位，並在不平衡Feistel網路中使用。Morris、Rogaway 和 Stegers在 Crypto 2009 上證明，如果你這樣做了 $ 4RN $ 這幾輪，你得到的安全性高達[數學處理錯誤] $ O(2^{N(1-1/R)}) $ 選擇明文/密文查詢。例如，如果你這樣做 $ 40N $ 回合，您可以獲得類似的安全性 $ O(2^{0.9N}) $ 選擇明文/密文查詢。這是一個非常令人印象深刻的結果。如果最大限度地提高安全性是您的目標，那麼這可能是您最好的選擇。
- 另一種方法是將隨機函式截斷為一個 $ N/2 $ 位，然後應用合適的 Benes 網路建構。Aiello 和 Venkatesan 在 Eurocrypt 1996 中證明，通過四輪，這可以為您提供高達[數學處理錯誤] $ O(2^{N/2}) $ 選擇明文/密文查詢。
一個可以幫助您找到更多結果的關鍵字是“超出生日界限的 Luby-Rackoff”。
有一種稱為 Permutator的通用結構，它可以將可搜尋的隨機位流轉換為排列。通過將 PRF 應用於輸入索引，從 PRF 獲得“可搜尋流”。
此構造適用於任何目標空間（它生成大小空間的排列[數學處理錯誤] $ n $ 在哪裡[數學處理錯誤] $ n $ 不一定是 2) 的冪。它也是“完美的”，這意味著空間大小的每一種可能排列[數學處理錯誤] $ n $ 可以選擇，機率正好 $ 1/n! $ ，例如，與必須僅實現偶數排列的 Feistel 方案相反。當針對小域中的排列（例如，所有 8 位十進制數字序列的排列）時，這可能具有一些重要性。
不幸的是，如文章中所述，實現 Permutator 意味著以任意精度算術進行一些計算，這是可行的，但速度很慢。這是我們使用的超幾何分佈的採樣方法（基於拒絕）的結果：該方法無偏但昂貴。