Permutation
雙射隨機預言機和隨機排列有什麼區別？
認為
- $ S $ 是一個有限集
- $ O $ 成為隨機預言機 $ S $ 到 $ S $ , 這樣 $ O $ 是雙射的
- $ f $ 是一個隨機排列 $ S $
有沒有區別 $ O $ 和 $ f $ ?
如果有的話有什麼區別嗎 $ S $ 是不是有限的？
在某種程度上，沒有本質區別。當然，隨機變數的分佈沒有差異 $ O $ 對比 $ f $ .
但是，這些術語的通常使用方式存在潛在差異。
- 如果我們這麼說 $ O $ 是一個隨機（雙射）預言機，那麼我們通常暗示它對每個人都可用：合法方、攻擊者、每個人——任何人都可以提供 $ x $ 然後回來 $ O(x) $ .
- 相反，如果我們這樣說 $ f $ 是一個隨機排列，我們尚未對它是否作為預言機提供給所有人或是否被密切持有做出任何承諾。
希望能夠訪問的各方 $ O $ / $ f $ 應該在其他地方明確說明（例如，在安全的形式化中），因此不存在嚴重混淆的真正危險，但這可能會作為提示讓讀者知道會發生什麼。