如何檢查排列是否是隨機的
想像一下我的朋友給了我排列 $ \pi $ . 他假裝排列是完全隨機產生的。
我很懷疑和擔心，因為排列（例如）看起來像： $ \pi(x) = ax + b \pmod n $ 對於一些 $ a $ , $ b $ . 我的朋友對我說，這是偶然發生的。
當然，我不可能真正證明排列不是隨機的，因為我們總是可以偶然產生這個排列。
有沒有什麼策略可以讓我嚴格地說（作為數學陳述）這個事件是非常不可信的？
我可以嘗試這樣說：嗯，有一個結構，隨機排列具有這種結構的機會非常小。但是結構可能更棘手（例如，具有某些輪函式等的某個組上的 k 輪 Feistel 網路）。我的朋友告訴我：你總是可以發明一些棘手的公式並得到我的每一個排列。但這並不表示排列不是隨機的。
所以問題是：如果我在“隨機”對像中發現一些“隱藏”結構，是否表明該對像不太可能是隨機的，或者我總能在朋友給我的每個對像中找到結構？如何在嚴格的數學意義上量化這種“可疑性”？
最多有 $ n \cdot (n - 1) $ 的排列 $ \mathbb Z/n\mathbb Z $ 形式的 $ x \mapsto ax + b $ ： 如果 $ n $ 是素數，有 $ n - 1 $ 選擇 $ a $ 和 $ n $ 選擇 $ b $ 這是一個排列。有 $ n! $ 的排列 $ \mathbb Z/n\mathbb Z $ 共。所以均勻隨機排列具有這種形式的機率可以忽略不計，如果 $ n $ 規模甚至適中——機率最多為 $ n \cdot (n - 1)/n! = 1/(n - 2)! $ ，它很快變得非常小，因為 $ n $ 成長。例如，對於 $ n = 64 $ ，這個機率已經小於 $ 1/2^{256} $ ，在密碼學術語中，它不會發生平方。
- 您可以自信地驗證它是否具有這種形式，只要在兩個不同的輸入上查詢它並求解 $ a $ 和 $ b $ ，然後在第三點和第四點等上檢查它，看看它們是否匹配。
練習：計算這個測試的誤報率作為確認點數的函式的均勻隨機排列。形式的備擇假設下檢驗的統計功效 $ x \mapsto ax + b $ ，當然，是最大可能的：1。
- 您可以自信地說，如果您的朋友有這種形式（例如，它是一個 8 位的排列，您可以驗證所有 256 個輸出），他們不會完全坦白他們如何選擇排列，但他們聲稱他們是隨機選擇的。
對於 8 位排列，如果您的朋友確實隨機均勻地選擇排列，則錯誤地指責他們的機率（誤報率或“統計顯著性”）低於 $ 1/2^{256} $ , 相當於 ’ $ p < .0000…00001 $ ‘（77 個零）。
但是，這僅適用於這個特定的測試，如果你在不知道排列的情況下設計了測試。如果您的朋友給了您一個排列，並且您根據該排列設計了一個失敗的測試，那可能沒有任何意義——對於任何特定的排列選擇，有許多低誤報率的測試會失敗。如果你把許多測試串在一起，讓其中任何一個都會發出警報，那麼誤報率就會上升——這是“ $ p $ -value hacking”或“分叉花園”。
這個問題類似於圍繞散列函式 Стрибог (Streebog) 的問題，來自俄羅斯聯邦政府標準ГОСТ Р 34.11-2012（也是RFC 6986），以及塊密碼 Кузнечик (Kuznyechik)，來自ГОСТ Р 34.12-2015（英語; 還有RFC 7801）。
2015 年，Alex Biryukov、Léo Perrin 和 Aleksei Udovenko 在 S-box 中發現了一個非凡的結構——Streebog 設計師維護的 8 位字元串的排列是通過對均勻隨機 S-box 的拒絕抽樣隨機選擇的（存檔） .
當 Perrin*等人。*確定了結構，他們推斷設計師的故事是不可信的，因為有 $ 256! \approx \sqrt{2\pi,256,} (256/e)^{256} \approx 2^{1684} $ 可能的 S-box，其中只有大約 $ 2^{82} $ 承認具有特殊結構的簡潔明了的描述。
“但是，”你反對，“知道我的排列，你可以發明任何包含我的排列的微小排列，即使我確實是隨機選擇的。然後，您可以使用您班級的低機率聲稱我一定是故意從該班級中選擇了我的排列，而不是靠運氣猜測！這並不意味著什麼！（根據 Léo Perrin的說法，這基本上是設計師聲稱他們不是在撒謊，就在幾週前的 ISO 標準化會議上。）
因此Perrin 將其送出給 codegolf.SE，其參與者提出了各種關於排列的簡短描述，包括 78 字節或 624 位 AMD64 指令序列。
打程式碼練習很有趣，因為可以發明更短的程序（例如，如果程序為 0，則計算 S-box 的機器的 1 位程序，如果**程序返回零，則是 1)，但是因為AMD64 指令集可能是在不知道所選擇的 S-box 的情況下設計的——而且如果 Streebog 的設計者真的確實從排列中均勻隨機抽樣來選擇 S-box，那麼得到一個允許 S-box 的機率AMD64指令集中的78字節/624位描述最多為 $ 2^{624}!/2^{1684} = 1/2^{1060} $ . 當然，Streebog 的設計者有一些拒絕抽樣的標準，但即使他們以這種方式通過了5 億個候選者（小規模，大約 $ 2^{60} $ )，機率將保持小於 $ 1/2^{1000} $ .
另一種看待它的方式是：
- 想像一下寫下所有的序列 $ {\approx}2^{1684} $ 8位排列，標記它們 $ 1, $ $ 2, $ $ \dotsc, $ $ 2^{1684} - \mathit{whatever} $ . 你把它們放在什麼順序都沒有關係。你可以把它們按你想要的任何順序排列，只要你在沒有預見到我將要做的事情的未來的情況下這樣做。
如果我然後隨機選擇一個排列，那麼它有 1/2 的機會出現在序列的前半部分。有 1/4 的機會出現在你序列的前半部分的前半部分——也就是第一節。更一般地說，有一個 $ 1/2^n $ 可能會在上半場上半場的上半場……上半場（ $ n $ 次）——與擲硬幣的機率相同 $ n $ 次，並且每次都會出現。如果我想通過隨機均勻地嘗試它們直到一個有效的方式在該區域中找到一個排列，那麼我必須嘗試的預期排列數約為 $ 2^n $ .
- 現在想像寫出所有字節字元串：（空）、、、、、……
0x00、、、、、、、……0x01、、、、……等等。其中一些是有效的 AMD64 指令序列。一些有效的 AMD64 指令序列實現了排列（例如，排列 AL 的值，忽略所有其他架構狀態）。0x02``0xff``0x00 0x00``0x01 0x00``0x02 0x00``0x00 0x01``0x01 0x01``0x02 0x01您當然需要至少 211 個字節才能以這種方式覆蓋所有排列，因為只有 210 個字節 = 1680 位，所以 8 位排列比 210 個字節的序列多。您幾乎肯定也需要超過211 個字節，因為大多數 AMD64 指令序列不計算排列——但您不需要超過 256 個字節，因為您可以使用 ROM 中所有輸入和輸出的 256 字節表，並且然後是一兩條 MOV 指令來使用它。
因此，您現在已經通過列舉 AMD64 指令序列佈置了所有 8 位排列的序列。不知何故，據稱通過對 8 位排列的統一隨機選擇進行拒絕採樣，設計人員發現了一個位於前半部分前半部分的前半部分……該序列前半部分的前半部分，迭代了一千多次，機率小於的事件 $ 1/2^{1000} $ ——即使他們首先拒絕了五億候選人。
如果你寫出任何一千次拋硬幣結果的序列——THTTHHHTHT……——然後看著一個賭徒擲硬幣一千次，在看它的同時得出你的序列，你會相信他們在進行公平的拋硬幣嗎？你會開始懷疑他們可能非常擅長翻轉硬幣以達到他們想要的方式嗎？
當然，原則上，這仍然可能是僥倖：通過在分岔路的花園里四處尋找不同的語言，我們也許可以找到一種語言，其中這種排列碰巧在序列的早期出現……通過購物關於 $ 2^{990} $ 不同的程式語言來提高誤報的機率 $ 2^{-1000} $ 到千分之一 $ 2^{-10} $ . 但是（a）codegolf.SE 嘗試過是不合理的 $ 2^{990} $ 不同的程式語言，以及 (b) 除了 AMD64 指令外，現在還有許多語言對同一個 S-box 的描述，這些語言的時鐘都遠低於 200 字節，包括 C、C#、JavaScript、Rust 和 Python。
還有另一種假設：就像賭徒可以按照他們想要的方式製造硬幣（這實際上很容易！），Streebog 的設計者可能使用了一種生成 S-box 的方法，該方法能夠實現緊湊、高效的實現，他們只是沒有告訴任何人。這種方法的結果——即使是隨機的——更有可能在現有的程式語言中有許多簡短的描述。在貝氏分析中，無論我們分配給假設的先驗勝算比如何 $ \text{structured} $ 和 $ \text{uniform random} $ （即**先驗的兩個假設的相對合理性），我們可以根據先驗勝算比和概似比，通過貝氏規則將後驗勝算比寫為：
$$ \begin{multline*} \frac{\Pr[\text{structured} \mid \text{78-byte code golf}]} {\Pr[\text{uniform random} \mid \text{78-byte code golf}]} \ = \frac{\Pr[\text{structured}]}{\Pr[\text{uniform random}]} \cdot \frac{\Pr[\text{78-byte code golf} \mid \text{structured}]} {\Pr[\text{78-byte code golf} \mid \text{uniform random}]}. \end{multline*} $$
顯然很難量化什麼 $ \Pr[\text{78-byte code golf} \mid \text{structured}] $ 對 Streebog 設計師可能考慮過的結構沒有更清晰的認識，但假設有一個單一的 googol ( $ 10^{100} \approx 2^{332} $ ) 很有可能在 Streebog 設計者使用的方法中，有一個 78 字節程式碼高爾夫解決方案，該解決方案採用廣為人知的廣泛使用的程式語言。在這種情況下，我們可以測量程式碼高爾夫的大小，作為結構化假設的證據，而不是統一隨機假設——概似比，即後驗勝算比與先驗勝算比的比率，以分貝為單位——如
$$ \begin{multline*} 10 \log_{10} \frac{\Pr[\text{78-byte code golf} \mid \text{structured}]} {\Pr[\text{78-byte code golf} \mid \text{uniform random}]} \ \leq 10 \log_{10} \frac{2^{-332}}{2^{-1000}} = 10 \log_{10} 2^{790} \approx 2000,\mathrm{dB}. \end{multline*} $$
從這個數字的角度來看，我們在接受典型消息身份驗證程式碼中的消息之前在密碼學中要求的證據量，而不是因為偽造而拒絕它已經結束 $ 300,\mathrm{dB} $ ——請記住，分貝是對數刻度。（有關以分貝為單位測量兩個假設之間的證據權重的更多資訊，請參閱Jaynes 的書，特別是第 4 章。）
當然，這是對證據的一種非常啟發式的量化——它實際上應該主要被視為貝氏推理形式的說明。也可能存在此分析未考慮的其他假設——例如，也許 Streebog 設計者在據稱執行 Fisher-Yates shuffle 以生成排列時只是使用了一個特別糟糕的 PRNG，並且沒有意識到他們正在探索一個與 AMD64 指令集有有趣關係的子空間。
練習：假設 Streebog 設計者可能使用的似是而非的 PRNG，並將其擴展到多假設貝氏分析。
有關背景和參考資料的更多資訊，請參閱Léo Perrin 的網站和迄今為止在 ASIACRYPT 2019 上的故事。