如何比較基於格和基於配對的 IBE 方案的性能
我嘗試使用格（LWE 硬度假設）或配對（Diffie-Hellman 硬度假設）來比較 IBE 方案的性能（Enc、Dec、…密鑰大小、密文…）。
我觀察到基於格的方案的性能通常用以下形式表示 $ n $ （晶格的維度）而配對問題使用位大小 $ |G| $ 基礎組的元素 $ G $ （以及求冪或配對等基本運算的成本）。
這兩個數量是“等價的”嗎？例如，是否有必要說：
- 長度鍵 $ O(n) $ （在格子方案中）和 $ O(|G|) $ （在配對方案中）在實踐中將具有大致相同的大小
- 成本加密 $ O(n^2) $ （在晶格方案中）比 $ O(|G|^3) $ （在配對方案中）
- …
很難對基於格的和基於配對的 IBE 方案進行具體的“逐一比較”。原因有很多：圍繞 LWE 的具體安全參數的研究仍在發展，基於格的 IBE（例如，離散高斯採樣）中使用的操作的有效實現仍在進行中，可以考慮更有效的基於環的類似物，等等等等
然而，在關於晶格和配對的合理硬度猜想下，可以給出有意義的漸近比較，至少到多對數因子（以便我們標準化到等效的安全級別）。
對於您的具體問題：不，維度 $ n $ 對於 LWE 和位大小 $ \log |G| $ 不等價。然而，它們在以下意義上是漸近接近的，直到多對數因子：對於猜想 $ 2^\lambda $ 安全性，我們可以設置 $ \log |G| = O(\lambda) $ 和 $ n = \tilde{O}(\lambda) $ . 對於配對，這意味著所有密鑰大小都是 $ O(\lambda) $ . 對於格子，它意味著：
- 大小的主公鑰 $ \tilde{O}(n^2) $
$$ plain LWE $$， 或者 $ \tilde{O}(n) $ $$ ring LWE $$.
- 大小的使用者密鑰 $ \tilde{O}(n \cdot \ell) $ 為了 $ \ell $ 位消息
$$ plain LWE $$， 或者 $ \tilde{O}(n) $ $$ ring LWE $$為了 $ \ell = O(n) $ .
- 加密時間 $ \tilde{O}(n^2) $
$$ plain LWE $$， 或者 $ \tilde{O}(n) $ $$ ring LWE $$.
- ETC ETC
簡而言之，對於 ring-LWE，可以製作所有相關的尺寸和執行時間 $ \tilde{O}(n) $ ，儘管隱藏的多對數因子在實踐中可能很重要。
不。關鍵因素是安全級別——一個方案有 n 位安全性，如果它大約需要 $ 2^n $ 工作 （ $ \approx $ 時間x空間）打破。因此，可以比較例如有限域中的 Diffie-Hellman 密鑰交換和 128 位安全級別的橢圓曲線，並得出結論認為 EC 更有效（畢竟這就是它們被發明的原因）。
對於基於配對的方案，您可以在常見的地方找到非常好的標準化啟發式方法，例如 ENISA 密鑰長度報告。這也取決於您使用的曲線類型。
對於格 - 我個人認為所有基於格的密碼學都是高度實驗性的，因為我們還沒有一套公認的標準來定義那裡的安全級別。我希望對於任何合理的定義，ECC 在效率方面都勝過格子。