完美保密 -> 一次性語義安全 -> 安全 PRG
我想我對完美安全的含義，甚至是語義安全有一定的了解，但我正在與隨機性作鬥爭，所以我將通過前兩個來問一個關於 CSPRG（加密安全 PRG）的問題。
據我了解，導致完美安全概念的基本思想是給定密文 $ c $ , 和一條消息 $ m $ , 有一定數量的鍵可能會轉動 $ m $ 進入 $ c $ . 如果有人給我看 $ c, $ 並告訴我鍵是在某個空間中統一選擇的，然後是一條消息 $ m $ 有許多密鑰可以將其加密成 $ c $ 比消息更有可能是原始的 $ m’ $ 很少有鑰匙可以把它變成 $ c $ . 這樣，一些關於原始消息性質的機率資訊可能會被洩露。完全保密通過說給定一個 $ c $ ，鍵的數量必須始終相同，無論 $ m $ .
**有一次，“語義安全”**將其編碼為一種遊戲。我給你 $ m $ 和 $ m’ $ ， 你給我 $ c $ ，並且我嘗試猜測您是否更有可能加密 $ m $ 或者 $ m’ $ . 如果很多鍵會改變 $ m $ 進入 $ c $ ，但只有少數人會將其更改為 $ m’ $ ，那麼我在猜測您加密了哪個方面具有優勢。
所以現在讓我們假設我們有一個函式 $ G $ 這需要一個種子並給我一個密鑰，我想將其用作流密碼，計算 $ c = G(s) \oplus m $ . 讓我們玩語義安全遊戲 $ m $ , $ m’ $ . 一旦給予 $ c $ ，攻擊者現在知道密鑰是 $ m \oplus c $ 或者 $ m’ \oplus c $ . 所以攻擊者會問自己的問題是：
有沒有更多的種子 $ s $ , 這樣 $ G(s) = m \oplus c $ ? 或者， $ G(s) = m’ \oplus c $ ?
如果他們能回答這個問題，那麼他們可能會獲得優勢。我現在要回答的問題是：什麼特性 $ G $ 非得讓攻擊者無法獲得優勢嗎？
好吧，假設是 $ m $ 這是加密的，但攻擊者還不知道這一點。然後：
$$ s = G^{-1}(m \oplus c) $$ 同時，攻擊者將進行檢查 $ G^{-1}(m’ \oplus c) $ 看看這是否可能是種子。由於密鑰空間是消息空間是密文空間，而且都比種子空間大很多， $ m’ \oplus c $ 將覆蓋未映射到的事物 $ G $ . 所以有以下選擇 $ m’ $ ，甚至有很多選擇，為此 $ G^{-1}(m’ \oplus c) = \emptyset $ . 因此，我們不能希望找到，就像我們在完全安全的情況下所做的那樣，當我們改變消息時，種子的數量是不變的。
我能看到的唯一其他選擇是我們必須希望沒有有效的方法來反轉函式 $ G $ . 如果有，那麼我們就迷路了，因為攻擊者有一種有效的方法來確定他們是否有種子；並且有很多選擇 $ m’ $ 他/她不會。這將給攻擊者一個非常大的優勢。
所以，我的問題是**，我們如何將缺乏有效逆的這一要求與加密安全 PRG 的通常定義聯繫起來？事實上，CSPRG 的定義是什麼？** Dan Boneh 將其描述為兩種測度（關鍵空間上的統一測度和種子空間上的統一測度的推進）的一種“計算不可區分性”。他聲稱，姚明認為這相當於“不可預測性”的概念。有人可以為我將這三種不同的東西混合在一起嗎？最後，在這個問題中，DW 提到了 PRG 與“具體安全”定義的“漸近”（而且不是很好）定義。他或某人能否澄清這些是什麼？
還有，有人提到姚明嗎？
首先，關於完美安全和語義安全的區別。這兩個定義都涉及機密性，所以讓我們首先定義機密性的含義。
首先請注意，對手作為消息的一些先驗知識。我們可以通過例如讓對手選擇兩條消息然後擲一枚公平的硬幣來決定加密哪一條來擷取這一點。
接下來，請注意對手想從密文中學習一些東西，即他對消息的後驗知識。我們通過讓對手猜測哪條消息被加密來捕捉到這一點。
如果對手無法正確猜測哪條消息被加密的機率顯著不同 $ 1/2 $ ，那麼我們就有了保密性。
這就是保密的定義。
（使用機率空間和從消息空間到 0 和 1 的函式可以進行更複雜的定義，但我們忽略了這一點，因為它對目前的討論並不重要。）
完美的安全性是針對任意對手的機密性。現在我們可以證明許多關於完美安全性的定理，其中一個是關於將給定消息轉換為給定密文的密鑰數量（如您所描述的）。
語義安全是針對計算受限的對手的機密性。與完美安全不同，我們可以證明的關於語義安全的定理並不多，這意味著我們對實現語義安全所需的知識知之甚少。
因此，完美安全和語義安全之間的區別僅在於我們考慮哪些對手，僅此而已。這兩個概念通常以表面上不同的方式呈現，但是，看起來它們在其他方面是不同的。
關於計算有界的對手。傳統方法（基於計算複雜性理論）是談論密鑰長度增加的密碼系統系列，並讓對手的努力受到密鑰長度中的某個多項式的限制。具體的安全方法說我們有一個具有固定密鑰長度的具體密碼系統，並讓對手的努力受到固定數量的計算步驟的限制（可能相對於一些固定的通用圖靈機或其他東西，這裡有一些基礎問題） .
其次，關於偽隨機生成器。偽隨機生成器是將短字元串“擴展”為長字元串的函式。如上所述，我們首先定義了一個類似於機密性的安全目標，然後我們可以針對該目標考慮不同的對手。
一個短字元串被採樣並擴展成一個長字元串。對第二個長字元串進行採樣。對手得到第一個或第二個長字元串，由公平的硬幣翻轉決定。
如果對手不能正確猜出他得到的兩個字元串中的哪一個，其機率顯著不同於 $ 1/2 $ ，那麼我們就有了安全性。
（這相當於 Boneh 的不可區分機率分佈的概念。）
完美的安全考慮任意對手。使用您在問題中概述的論點，很容易證明偽隨機生成器的完美安全性是不可能的。
計算安全考慮計算有界的對手。顯然，這裡沒有不可能的證據。相反，我們有充分的理由相信，對於“計算有界”的有用價值，這是可能實現的。
由於完美的安全性是不可能的，所以一直談論“計算”是沒有意義的，所以我們通常忽略它而談論“安全的偽隨機生成器”。由於在許多科學領域都使用了偽隨機生成器，因此我們經常在前面加上“密碼學”以明確表示我們在這裡談論的是密碼學，而不是（說）統計數據。
偽隨機生成器是一個函式 $ G $ 從短字元串集合到長字元串集合。如果您可以反轉函式（或者如果它不是單射的，則找到原像），那么生成器顯然不安全，正如您所觀察到的。
第三，關於不可預測性。很明顯，如果我對一個長字元串進行採樣並向您顯示一個前綴，那麼您就無法說出字元串的其餘部分，尤其是下一個符號。
假設如果給你一個偽隨機發生器輸出的前綴，你可以預測輸出的下一個符號。在上述設置中，您可以獲取生成器的輸出或隨機字元串，您可以辨識偽隨機生成器的輸出。
以下是您辨識輸出的方式：您得到一個長字元串。暫時，您忘記了字元串的前綴以外的所有內容，並假裝它是生成器輸出的某些內容的前綴（它可能是）。現在您可以利用自己的能力預測下一個符號。然後你會記住整個長字元串，特別是下一個符號。如果您預測正確，那麼很可能是生成器輸出了長字元串。如果您的預測不正確，那麼長字元串可能是隨機的。
由於您可以辨識生成器的輸出，因此生成器並不安全。因此，如果你有一個安全的生成器，它是不可預測的。這很好。
（另一個方向更複雜。基本上，這個想法是，如果給定一個前綴，你不能說下一個符號是什麼，那麼你就無法區分生成器的輸出和生成器的輸出，最終的符號是隨機的。但是你無法將後者與生成器的輸出區分開來，最後兩個符號隨機化。等等。由於不可區分性是傳遞性的，因此您無法將生成器的輸出與隨機字元串區分開來。）