從 Santha-Vazirani（半隨機）源中提取隨機性
為了更好地理解隨機提取器（在 TRNG 後處理的背景下），我閱讀了一些關於von Neumann Extractor和Santha-Vazirani (SV-) 來源的論文。馮諾依曼提取器是一種簡單的算法，適用於獨立的、有偏見的來源，例如有偏見的硬幣。然而，可用的隨機性物理來源是不完善的，並且是有偏差的和相關的。Santha 和 Vazirani 定義了這樣一個源，稱為 SV 源。
Santha-Vazirani 論文顯然表明不可能（確定地）從 SV 源中提取幾乎均勻的隨機位。我沒有理解展示所需的數學背景，但這種說法確實讓我感到困惑。例如，我希望雜湊函式能夠從 SV 源中產生統一的隨機位。
這個展示的真正含義是什麼？是否不可能從一個（這不適用於多個）有偏見和相關的來源創建一個好的 TRNG？
然而，可用的隨機性物理來源是不完善的，並且是有偏差的和相關的。
不，他們不是。源實際上不會產生任何熵。沒有任何。想像一下您面前的齊納二極體或環形振盪器電路。他們只是坐在那裡看起來迂迴。
觀察者在對源進行採樣時生成熵。來源沒有。這就引出了概念 $ (\epsilon, \tau) $ -單位時間的熵，其中*“ $ (\epsilon, \tau) $ -熵是單位時間產生的資訊量，在不同的尺度 $ \tau $ 時間和 $ \epsilon $ 有效的採樣率和解析度。* 這意味著觀察者可以根據自己的判斷無限地改變源的熵率，通過改變 $ \tau $ 或者 $ \epsilon $ .
這進一步導致了一個不對稱的雙邊問題：我們如何測量 $ H_{\infty} $ 對於相關來源？有兩種不對稱的解決方案：-
- 嘗試確定 $ H_{\infty} $ 對於確定性非常低的相關源。
- 調整你的 $ (\epsilon, \tau) $ 抽樣制度以產生高確定性的不相關數據。
幾乎沒有人做到 #1，甚至 NIST都說這幾乎是不可能的（Kerry McKay 毫無防備的評論）。我無法想像什麼 $ H_{\infty} $ 實際上意味著在相關的情況下。#2 也是如此，正如絕大多數人所做的那樣，獲得 $ H_{\infty} $ 作為 $ -\log_2{(p_{\text{max}})} $ 並提取。
因此，可以從有
偏見和相關的來源創建一個好的 TRNG。Santha-Vazirani 論文顯然表明不可能（確定地）從 SV 源中提取幾乎均勻的隨機位。
不完全的。它實際上是說*“相比之下，我們證明沒有算法可以從半隨機源中提取甚至是一個無偏的位（實際上，不比 1 - $ \delta $ 偏位）。”* 這是既定的知識，出現在各種“提取器”論文中。它只是意味著任何提取的隨機性總是有一個 1 - $ \delta $ 偏見。NIST 只是建議您將其保留在下方 $ 2^{-64} $ 這很容易。
參考：Pierre Gaspard 和 Xiao-Jing Wang，噪音、混亂和 $ (\epsilon, \tau) $ -每單位時間的熵，PHYSICS REPORTS（物理快報的評論部分）235，No. 6 (1993) 291-343。北荷蘭。