證明偽隨機生成的密鑰在語義上是安全的
讓 $ G: {0,1}^s \rightarrow {0,1}^r $ 在哪裡 $ r > s ; $ 是一個安全的偽隨機生成器。
讓 $ \xi = (E,D) $ 一種語義安全的密碼，其密鑰空間為 $ {0,1}^r $
讓 $ \xi’ = (E’,D’) $ 一個密碼，其密鑰空間是 $ {0,1}^s $ 並且這樣：
- $ E’(k, m) = E(G(k), m) $
- $ D’(k,;c); = D(G(k),;c) $
我怎樣才能證明 $ \xi’ $ 在語義上是安全的嗎？
我想我應該使用語義安全密碼使用隨機密鑰這一事實，因此使用偽隨機密鑰只會增加對手猜測密鑰的微不足道的優勢，因此語義安全的可忽略優勢和偽隨機密鑰可忽略的優勢也可以忽略不計，但我不確定如何建立證明。
為了回答這個問題，讓我們記住安全 PRG 的定義：
讓 $ G: k \to {0, 1}^n $ 成為PRG。 $ G $ 被認為是安全 PRG 當且僅當 $ G(k) $ 無法區分 $ r $ ， 在哪裡 $ r $ 是一個真正的隨機字元串 $ {0, 1}^n $
不可區分是指沒有統計測試可以區分 $ G(k) $ ， 在哪裡 $ k $ 從集合中隨機選擇 $ K $ ，來自一個真正隨機的字元串 $ r $ , $ r \in {0, 1}^n $ .
這說的很容易看出，如果 $ G $ 是一個安全的 PRG，任何對手都無法以不可忽略的優勢區分從生成的密文 $ E $ 和 $ E’ $ . 所以你的證明想法是正確的。
大多數時候這應該足以證明它……但是下面我使用攻擊遊戲和統計測試提出一個證明
為了幫助進行實際證明，可以將問題定義為：
如果 G 是一個安全 PRG，那麼 $ \xi’ $ 在語義上是安全的。
然後，我們可以用反證法來證明它：
如果 $ \xi’ $ 在語義上不安全，則 G 不是安全 PRG。
為了證明，給定一個對手 $ A $ 這可能會破壞語義安全性 $ \xi’ $ ，我們需要能夠建立一個對手 $ B $ 使用 $ A $ 可以區分的 $ G(k) $ 從 $ r $ ，再次，在哪裡 $ r $ 是一個真正的隨機字元串 $ {0, 1}^n $ .
所以，我們這樣做的方法是使用 $ B $ 同時作為挑戰者 $ A $ 並作為統計檢驗來區分 $ G(k) $ 從 $ r $ .
- $ A $ 將提供 $ B $ 兩條消息 $ m_0 $ 和 $ m_1 $ ;
- 然後 $ B $ 會從他的挑戰者那裡得到一根繩子 $ s $ 那可以是 $ G(k) $ 或者 $ r $ ;
- 然後 $ B $ 加密 $ m_0 $ 使用 $ E $ 和字元串 $ s $ 作為關鍵（本質上，他正在使用 $ E’ $ 什麼時候 $ s = G(k) $ 和 $ E $ 什麼時候 $ s = r $ ).
- 最後， $ B $ 發送加密 $ c $ 至 $ A $ 那答案 $ 1 $ 如果他認為 $ c $ 來自加密 $ m_1 $ ， 和 $ 0 $ 否則。
- $ B $ 向他的挑戰者輸出任何答案 $ A $
請注意，如果 $ B $ 回答他的挑戰者 $ 0 $ ， 然後 $ s = G(k) $ ; 如果他回答 $ 1 $ ， 然後 $ s = r $ .
鑑於 $ A $ 可以破壞語義安全 $ \xi’ $ 他會輸出 $ 0 $ （猜對了）無論何時 $ s = G(k) $ ，正如我們所見， $ B $ 回答這個也是正確的 $ s $ 實際上是 $ G(k) $ .
這將打破安全 PRG 的定義，從而證明 $ G $ 不安全。 $ \square $
只是為了一個完整的問題：
您所要求的也是使 OTP 實用化的想法，其想法是使用偽隨機密鑰而不是真正的隨機密鑰，因此我們可以使用小種子來生成更大的密鑰。
我還應該注意，使用 PRG 生成其密鑰的密碼不能稱為
perfectly secure密碼。這就是為什麼安全性的定義被延伸，因此安全性屬性取決於特定的生成器。這就是語義安全定義出現的地方。