如何解釋我的教授關於“種子”和“對稱密鑰加密”的說法？
在密碼學課程中，教授說：
如今對於對稱密鑰加密，Alice 不再發送密鑰，而是將種子發送給 Bob，然後 Bob 可以根據該種子獲取密鑰。
我並沒有真正理解種子的作用，另外，如果 Bob 可以根據種子生成密鑰，那麼 Eve 也可以這樣做，對嗎？
種子是隨機數生成器中使用的術語，對於對稱密鑰加密，我們談論密鑰。
如果你的教授的意思是：
我們沒有發送完整的一次性墊，而是發送了一個種子。
然後他在談論流密碼，其中交換密鑰以用於加密。
另一種可能性是他試圖為您簡化“密鑰交換”的概念。密鑰交換是一種通過公共不安全通道在兩方（或多方）之間建立公共密鑰的方法。Diffie-Hellman 是密鑰交換算法的典型範例。
你的教授說的是下面比較常見的優化
讓 $ \mathcal{K} $ 是一個集合，並且讓 $ \mathsf{Sample} : {0,1}^r\to\mathcal{K} $ 是一種算法，在輸入時 $ r $ 均勻隨機位，輸出一個元素 $ k\in \mathcal{K} $ .
如果 $ \mathsf{PRG} : {0,1}^s\to{0,1}^r $ 是一個 PRG，那麼對於 $ s\leftarrow{0,1}^s, r\leftarrow{0,1}^r $ , 的分佈 $$ \mathsf{Sample}(\mathsf{PRG}(s))\approx_c \mathsf{Sample}(r) $$ 在計算上是無法區分的。
這一點的證明大致是微不足道的。在 PRG 的保障下， $ \mathsf{PRG}(s) \approx_c r $ . 應用（高效）算法 $ \mathsf{Sample} $ 保持計算不可區分性（否則 $ \mathsf{Sample} $ 將是對抗 PRG 的有效對手）。
本質上，如果您的最終構造需要 $ s $ -bit 密鑰，通常將密鑰設置為 $ r $ -bit PRG 種子，然後將其拉伸到 $ s $ 位與 PRG。
上面有一些具體的細節需要指出：
- 生成的最終密鑰 $ \mathsf{Sample}(r) $ 本身不必是均勻隨機的（儘管這是迄今為止最常見的情況）。
- 人們可以進一步削弱對上述結果的假設——通過訴諸隨機提取器，輸入 $ r $ 本身不需要是統一的，而是需要以一種可以精確的方式“足夠的最小熵”。
- 您仍然需要密鑰交換。PRG 的安全遊戲要求 PRG 的種子保密以確保安全，因此您仍然需要確保 Eve 無法訪問種子（正如您提到的）。
所有這些優化都在說，使用 PRG 可以使密鑰交換的“有效負載”更小（特別是，它可以 $ r $ 位而不是 $ s $ 位）。
有一個相關的優化（以一種微妙的方式不同）可能也值得討論。通常在密碼學中（特別是在基於格和編碼的密碼學中），必須傳輸一個大的、均勻隨機的元素。特別是，Learning with Errors 假設是關於 LWE “樣本”：
$$ (A, As+e) $$
我不會費心定義這個範例中的所有內容，而是說 $ A $ 通常是一個均勻隨機矩陣，大小為 $ \approx 1-10kb $ ，取決於特定的方案。
您可能很想用 PRG 種子替換這個均勻隨機的對象 $ s $ ，然後可以確定性地擴展為隨機值 $ A $ 之後。由於 PRG 種子的順序為 $ \approx 128 $ 位，這是一個顯著的（潛在的）增益。
不過，這不是一個有效的優化，因為上面的第 3 點 — 如果您的方案稍後公開這個統一隨機值，您不能使用 PRG 以這種方式將統一隨機值“壓縮”為短種子。或者你可以，但是對於特定的 PRG，這可能會完全破壞安全性。
您仍然可以使用稱為可擴展輸出函式的東西做類似的事情（無論出於何種原因，首字母縮寫詞是 XOF）。這些是基於散列的原語，（大致）用於當人們想要類似 PRG 的屬性但具有公共種子時使用。
無論如何，使用 XOF 壓縮一個大的均勻隨機值是一種非常常見的優化。我很確定基於 LPR 的 NIST PQC 決賽入圍者（Saber/Kyber）都使用了這種優化，儘管任何特定的實現都可能稍微偏離規範並且包含/未能包含優化。