Even-Mansour Cipher：用於對隨機排列進行採樣的高效算法
我對 Even-Mansour 密碼的理解如下：
- 我們畫一個隨機排列 $ P $ 從所有排列的集合 $ P: {0,1}^n \rightarrow {0,1}^n $ . 這種排列是公開的。
- 我們生成兩個隨機密鑰 $ k_1, k_2 \in {0,1}^n $ .
- 加密消息 $ m \in {0,1}^n $ , 我們計算 $ E_{k_1, k_2} = P(m \oplus k_1) \oplus k_2 $ .
存在什麼樣的算法可以讓我們有效地採樣（和表示）排列 $ P $ 從所有排列的集合中 $ n $ 位串到 $ n $ 位串？
Even-Mansour 是一個證明安全結果的理論模型。需要對以下排列進行採樣 $ n $ 位，說 $ n=128, $ 因為由此產生的空間 $ N=2^n $ 對象太大而無法儲存或操作。這類似於在現代密碼學中沒有人在 OTP 模式中使用純隨機的等分佈和 iid 比特序列作為密鑰流的事實。它太慢了。
然而，下面的算法給出了一個隨機排列 $ {1,2,\ldots, N}. $ 這裡沒有聲稱最佳效率。
小列表隨機排列程式碼
**輸入：**列表 $ A=[1,2,\ldots, N] $ 的 $ N=2^n $ 項目。
**任務：**置換中的值 $ A $ 隨機。
讓 $ S:={u: u \in A}. $ 讓 $ B:=A $
對於每個 $ i=1,\ldots,N $ 做
$ \quad $ 選擇一個隨機整數 $ j \in S $
$ \quad $ 更改數組 $ B $ 通過 $ B[j]:=A[i] $
$ \quad $ 消除 $ j $ 從集合 $ S $
結束 這個算法選擇 $ N, $ 然後 $ N-1 $ ， 然後 $ N-2 $ 等對像一致並且可以以相等的可能性生成每個排列，因為它使 $ N! $ 選擇。 **輸出：**列表 $ A $ 現在是隨機的。
有更有效的隨機排列採樣方法，例如參見 Jens Gustedt，“隨機排列的有效採樣”，離散算法雜誌，卷。6, Issue 1, 2006. 也看看 Fisher-Yates shuffle 和 Knuth Shuffle，google 是你的朋友。
下面的算法並沒有完全到達那裡，感謝@kelalaka 的更正
**輸入：**列表 $ A={1,2,\ldots, N} $ 的 $ N=2^n $ 項目。
**任務：**置換中的值 $ A $ 隨機。
對於每個 $ i=0,\ldots,N-1 $ 做
$ \quad $ 選擇一個隨機整數 $ j $ 和 $ i<j<N. $
$ \quad $ 交換條目 $ A[i] $ 和 $ A[j]. $
結束
**輸出：**列表 $ A $ 現在是隨機的。