Pseudo-Random-Generator
加密安全 PRBG 和前一位測試
我正在閱讀Junod關於 Blum-Blum-Shub PRBG (BBS) 的論文，我無法按照他在第 15 頁的推理，他認為也可以對位序列中的前一位執行下一位測試 $ b_0b_1 \ldots b_k $ ，即攻擊者也可以嘗試預測 $ b_{-1} $ . 如果我正確理解他，他認為這很明顯，因為下一位測試等同於多項式時間統計測試，後者顯然對給定位序列的反轉無動於衷。
但我不明白這應該如何適用，因為（在我看來）隨機數生成器在任何情況下都只能建構“在一個方向上無限延伸”的序列，因為它們必須有某種起點和前一個位測試不能應用在起始位 $ b_0 $ ，因為沒有前一位。所以 wgat 是 $ b_{-1} $ 應該是什麼意思？
你能給我解釋一下嗎？
如果您只有一個不包含第一位的輸出子序列，則可以標記子序列的位 $ b_0 $ , $ b_1 $ , $ \dots $ . 然後將標記從中獲取它們的整個序列的位 $ \dots $ , $ b_{-1} $ , $ b_0 $ , $ b_1 $ , $ \dots $ .
換句話說，您不必在生成器輸出的開頭開始標記位，而是在稍後的某個時間點開始標記位。在這種情況下，存在前一位，並且適用前一位測試。