理解eevarepsilon- 在加密安全確定性 RNG 方面的優勢
Vazirani & Vazirani在Efficient and Secure Pseudo-Random Number Generation by Vazirani & Vazirani 中指出，每個滿足XOR 條件的偽隨機數生成器都可以安全地輸出 $ \log n $ 位（其中 $ \ n = |N| $ ）。Blum-Blum-Shub（其陷門基於二次剩餘性假設）滿足了這樣的條件，因此高達 $ \log \log N $ 可以提取每個步驟的位。
我的問題是關於資訊論的興趣：當他們聲明布爾謂詞（輸出位）時，它們到底是什麼意思 $ b_1,\ldots,b_k $ 如果存在一個在機率多時執行的拉斯維加斯算法 T，那麼反演是安全的，即 $ T^{O_{b_{i},N}}[i, E_{N}(x)] = x $ （和 $ E_{N}(x) $ 單向函式），其中 $ O_{b_{i},N} $ 是一個 $ \frac{1}{2} + \frac{1}{poly(n)} $ 優勢預言機 $ b_i $ 關於 N? 為什麼機率超過 1/2 加上那個 $ \varepsilon $ -advantage，我假設它限制了整體機率？因此，如果這些謂詞的每個非空子集的 XOR 是反轉安全的，則布爾謂詞滿足 XOR 條件。
我認為這與 Rabin 函式所說的非常接近：
如果對於一個 $ \frac{1}{logN} $ 二次殘差的分數 $ q\pmod N $ 可以找到一個平方根 $ q $ ，那麼可以考慮 $ N $ 在隨機多項式時間內。
仍然，在哪裡 $ 1/(\log N) $ 來自？
花了一些時間來掌握它，但在朋友的幫助下，我們得出了結論（事實證明這很容易）。
回想一下一個函式 $ f_n : {0,1}^{n} \mapsto {0,1}^{m(n)} $ 如果對於正多項式，則稱其為單向 $ poly(\cdot) $ ，在機率多項式時間中執行的每個隨機算法都會反轉 $ f_n $ 機率可以忽略不計，即 $ \Pr[A:inverting: f_n] < \frac{1}{poly(n)} $ ， 和 $ n $ 輸入的大小。這個多項式來自這樣一個事實：對於每一個可能的計算路徑，算法都會以機率跟隨它 $ 2^{-n} $ , 由 $ \mathcal O(\frac{1}{n^c}) $ 對於每一個常數 $ c $ . 顯然，我們希望對手的優勢盡可能地小。