為什麼我們不使用可擴展輸出函式在標準格上有效地儲存 Regev 的基於 LWE 的加密方案的公鑰？

在基於 LWE 的方案中，公鑰是通過選擇隨機矩陣（或多項式）生成的 $ A $ ，並輸出對 $ (A, b = A\cdot s + e) $ ， 在哪裡 $ s $ 和 $ e $ 是向量/多項式，其係數取自某些誤差分佈。

在Kyber 加密方案中，第一部分（矩陣/多項式 $ A $ ) 不是公鑰的一部分。相反，他們將種子保存到（眾所周知的）可擴展輸出函式（EOF），該函式用於生成 $ A $ . 如果有人想知道公鑰，那麼他可以只要求種子並生成 $ A $ 自己。這樣可以節省很多空間。

為什麼不針對基於一般格（標準 LWE）的方案提出此建議？這些標準 LWE 方案的大問題是巨大的公鑰大小，但這個 EOF 解決方案可以解決這個問題。但是，在我發現的任何實現中都沒有提到它，比如這個。

我相信它也用於其他使用標準 LWE 的基於格的方案。例如，佛羅多論文。他們使用了一個 $ seed_A $ 和一個 Gen( $ \cdot $ ) 計算函式 $ A $ . 然後 Alice 發送 $ seed_A $ 代替 $ A $ 為實際交換。根( $ \cdot $ ) 是一個預先商定的偽隨機函式，用於提取和擴展種子。

引用自：https://crypto.stackexchange.com/questions/54110