One-Way-Function
隨機排列是否“隱藏”？
假設我告訴你 $ G: \mathbb{F} \rightarrow \mathbb{F} $ 是一個隨機排列（一些有限域）。這是否意味著：
- $ G $ 是單向的，所以如果我給你 $ G(x) $ , 無法確定原像 $ x $ ?
- 是 $ G $ 隱藏在你無法弄清楚任何事情的意義上 $ x $ 給定 $ G(x) $ ? 例如，您可以確定是否 $ x $ 偶數/奇數？
如果第二個問題是真的，我如何在遊戲中捕捉到這一點？
如果您有權訪問 $ G $ 通過一個預言機，那麼你就有一個隨機排列預言機，這是對理想化單向排列建模的常用方法。特別是，它因此是一種單向函式。
然而，正如 fgrieu 所指出的，隨機單向排列通常不會隱藏。捕捉一些原始的隱藏屬性的自然遊戲 $ P $ 如下：對手挑 $ (x_0,x_1) $ 任意，並將它們發送給您。然後，你隨機選擇一個位 $ b $ 並返回 $ P(x_b) $ ; 如果他發現對手獲勝 $ b $ . 一個方案 $ P $ 如果對手的獲勝機率幾乎可以忽略不計，則隱藏 $ 1/2 $ .
當然，隨機排列不能滿足這一點：只要對手發送不同的值，他總是可以計算 $ G(x_0), G(x_1) $ 他自己，並檢查哪一個是他從你那裡得到的價值。通常，確定性函式不能隱藏。
但是，可以從單向排列*建構可證明安全的隱藏承諾方案 - 在您的情況下，它將完全隱藏，因為您可以訪問理想的隨機排列。*標準構造通過 Goldreich-Levin 定理，它顯示瞭如何從單向排列中提取“harcore 位”，這樣找到這個 hardcore 位就像反轉排列一樣困難，並使用這個 hardcore 位來掩蓋你想要承諾的位（有一個關於這個結構的維基百科條目）。