為什麼基於格的密碼方案通常不具有頻寬效率？
這個問題主要在標題中說明。我是格子的新手，我對格子有基本的了解，但不是很深入。我正在觀看一個使用基於格的加密的 VSS（可驗證秘密共享）方案的展示文稿，他們提到“我們正在使用基於格的加密，這可能會令人驚訝，因為我們的協議與大多數基於格的協議相比具有良好的頻寬方案”。
問題：
- 我想知道使格密碼方案沒有頻寬效率的關鍵因素是什麼？
- 作為後續問題，還有其他資源對它們無效嗎？
效率當然是一個相對的術語。通常，與密碼通常分別為 1000 和 100 位的 RSA 和橢圓曲線系統相比，基於格的系統被認為頻寬效率低。例如，對於一個名義上的安全級別，其中破解密碼的工作量與使用經典電腦破解 AES-128 的工作量一樣多（128 位的耗盡工作），人們普遍認為 3072 位的 RSA 模數或橢圓曲線需要一組 256 位。
關於評估格系統攻擊成本的正確方法存在一些爭論，但人們可以粗略地討論增加的頻寬需求來自何處。本質上，幾乎所有基於格的密碼學都會有一個密碼，其中的形式是 $ n $ - 大小小於某個值的整數的長向量 $ q $ . 這樣的密碼至少是 $ n\lg q $ -位大小。系統的安全性將取決於在由類似大小的向量生成的格中找到短向量的難度。在漸近且不太可靠的意義上，許多人認為有可能找到這樣的向量 $ 0.292n $ - 一些工作（參見Albrecht 等人的The General Sieve Kernel 和 New Records in Lattice Reduction進行深入的技術調查）。這個粗略的估計表明 $ n $ 對於 AES-128 安全級別，至少應採用 438（如果我們查看諸如 Kyber、NTRU 和 SABRE 等旨在達到他們通常擁有的安全級別的提案） $ n=500-512 $ ).
的選擇 $ q $ 也有些神秘。早期的建議建議採取 $ n^2<q<2n^2 $ ，儘管最近的參數集更接近 $ q\approx n\log n $ . 我不記得曾經見過與 $ q $ 少於 $ n $ （ETA：Mark指出NIST第2輪候选和中國CACR選擇算法LAC確實有 $ q<n $ ）。對於上述系統 $ q $ 介於 11 和 13 位之間。單個向量的頻寬現在看起來像 7144 位，任何渴望達到與 AES-128 相同級別（經典）安全性的方案（這些數字都非常接近，不應被誤認為是嚴格的分析）。這是 RSA 頻寬的兩倍多，許多人已經認為在頻寬方面相當重量級。或許值得注意的是，對於更高級別的安全性，RSA 的頻寬需求比格系統增長得更快，但與橢圓曲線相比，兩者看起來都非常低效。
該分析僅適用於密碼，並且還存在關於傳輸公鑰或系統的成本的問題，其中需要比單個向量更多的資訊。但是，它應該對這些問題有所了解。