可變長度偽隨機生成器的前綴屬性
我目前正在閱讀 Katz & Lindell 的*《現代密碼學簡介》*。在 3.4.2 節中，他們介紹了可變輸出長度偽隨機生成器的定義 $ G $ . 的定義 $ G(s,1^l) $ 是這樣的輸出是長度 $ l $ .
使用這樣的偽隨機生成器，他們定義了一個可變長度的加密方案（這裡，稱為 $ \pi_{VarPRG} $ ) 以自然方式處理可變長度消息：
加密： $ Enc:\mathcal{K}\times\mathcal{M}\to\mathcal{C} $ 在哪裡 $ C=Enc(K,M)=G(K,1^{|M|})\oplus M $
解密：密文長度的加密逆 $ |C| $ .
但是，它們繼續包括附帶條件：
對全部 $ s $ , $ l $ , $ l’ $ 和 $ l<l’ $ , 字元串 $ G(s,1^l) $ 是前綴 $ G(s,1^{l’}) $ .
他們聲稱這是在存在竊聽者的情況下證明上述可變長度加密方案的不可區分加密的“技術”。在盯著這個看了一個小時的大部分時間之後，我不完全理解這種微妙之處在哪裡出現。（畢竟，這是一種微妙之處。）
我第一次嘗試深入了解這個問題：
在證明 $ PrivK^{eav}{\mathcal{A},\pi{VarPRG}}(l) $ 對於上面顯示的加密方案，我們假設 $ G $ 是一個安全的偽隨機生成器，然後假設，為了矛盾， $ \pi_{VarPRG} $ 在存在竊聽者的情況下是不安全的。換句話說，存在一些對手 $ \mathcal{A} $ 為此
$ Pr(PrivK^{eav}_{\mathcal{A},\pi}(l)=1)\not\leq \frac{1}{2} + negl(l) $
我們繼續使用對手 $ \mathcal{A} $ 建立一個（機率，多項式時間）區分器 $ \mathcal{D} $ 對於可變輸出長度 PRG $ G $ ，並表明這與假設的偽隨機性相矛盾 $ G $ .
到目前為止一切順利。對手 $ \mathcal{A} $ 將在呼叫時輸出兩條消息 $ m_0 $ 和 $ m_1 $ ，其中一個假設可以是不同的長度（ $ |m_0|\not=|m_1| $ ）。在這一點上，我卡住了：
上面提到的關於前綴屬性的微妙之處在哪裡？ $ G $ 為了 $ 1^l<1^{l’} $ ，進入這個？
回想一下，Katz-Lindell 將可變輸出長度的偽隨機生成器定義為具有三個屬性的確定性多項式時間算法 G：
- 讓 $ s $ 一個字元串和 $ n>0 $ 一個整數。然後 $ G(s,1^n) $ 輸出一個長度的字元串 $ n $
- 對全部 $ s,n,n’ $ 和 $ n<n’ $ , 字元串 $ G(s,1^n) $ 是前綴 $ G(s,1^{n’}) $
- 定義 $ G_{\ell}:=G(s,1^{\ell(|s|)}) $ . 那麼對於每個多項式 $ \ell(\cdot) $ 它認為 $ G_{\ell} $ 是具有擴展因子的偽隨機生成器 $ \ell $ .
（我改變了一些 $ \ell $ 到 $ n $ s 以避免變數碰撞）。
第二個條件是必要的，因為沒有它，這個定義並沒有說明任何關於 $ G(s,1^n) $ 在這種情況下 $ |s|>n $ . 這是因為 Katz-Lindell 定義了一個偽隨機生成器（第 70 頁） $ \textit{expansion} $ 屬性——偽隨機生成器的輸出比種子長——所以上面的屬性 3（本身）並沒有告訴我們關於 $ |s|>n $ .
這是一個問題，因為（如第 63 頁所定義）竊聽不可區分性實驗的第一步是“對手 $ \mathcal{A} $ 給定輸入 $ 1^n $ ，並輸出一對消息 $ m_0,m_1 $ 一樣長。”
加密中使用的種子是有長度的 $ n $ ，所以對手可以選擇長度小於 $ n $ . 然後消息將使用以下輸出加密 $ G(k,1^{|m_0|}) $ 如上所述，不保證沒有屬性 2 的偽隨機。
然而，證明偽隨機字元串的截斷也是偽隨機是一個簡單的引理。這與屬性 2 和 3 一起，讓我們知道可變輸出長度偽隨機生成器的所有輸出都是偽隨機的，並且安全證明正常進行。