我可以通過對 PRF 的結果進行排序來建構 PRP 嗎？
我使用 HMAC-SHA256 作為偽隨機函式係列 (PRF)。我在某處讀到，可以通過應用 PRF 並對輸出進行排序來實現偽隨機排列族 (PRP)。
例如，如果 $ x_1 $ 映射到 $ 4 $ 在 PRF 中的特定鍵下，以及 $ x_2 $ 映射到 $ 2 $ ，那麼 PRP 為 $ {x_1, x_2} $ 將會 $ {x_2, x_1} $ 在同一把鑰匙下。
那有意義嗎？這個 PRP 結構是否安全，還是我必須使用 PRF 實施 Luby-Rackoff 結構？
即使這在原則上有效，我也不認為這對於除了最小的集合之外的任何集合都是可行的，因為它需要您列舉（和排序）您想要置換的集合。
另外，在我看來，除非 PRF 的共域比它的域大得多，否則你會遇到關係問題，即輸入 $ x_1 \ne x_2 $ 為此 $ {\rm PRF}(x_1) = {\rm PRF}(x_2) $ . 我看不出有任何明顯的方法可以打破無法潛在地用於將生成的 PRP 與隨機排列區分開來的這種聯繫。
綜上所述，如果您真的只是想偽隨機地打亂一小組值，將它們中的每一個饋送到具有足夠大域（如 HMAC-SHA256）的 PRF 並按結果對值進行排序應該是一個非常好的和安全的解決方案。具體來說，考慮一個試圖將您的偽隨機洗牌與真正隨機洗牌區分開來的對手。對於這樣的對手要成功（機率大於 ½），他們必須：
- 以某種方式將 PRF 與隨機函式區分開來，或
- 觀察 PRF 輸出之間的衝突。
選項 1 的機率將取決於 PRF（以及假設的攻擊者能力），但對於所有實際攻擊者來說，PRF 被認為是安全的，它必須小到可以忽略不計。另一方面，假設 PRF與隨機函式不可區分，則可以計算出第二個機率：
具體來說，給定 $ k $ 輸入到一個 PRF 與 $ n $ -元素共域（例如 $ n = 2^{256} $ 對於 HMAC-SHA256)，機率 $ p $ 至少觀察一次碰撞的次數小於預期的碰撞次數，後者本身等於 $ \frac{k^2 - k}{2n} < \frac{k^2}{2n} $ . 因此，例如，如果 $ k \le 2^{64} $ 和 $ n = 2^{256} $ ， 然後 $ p < \frac{(2^{64})^2}{2\cdot2^{256}} = 2^{-129} $ .