超奇異同源方案中的密鑰大小與其安全級別有何關係？
我正在查看 De Feo、Jao 和 Plût 2014 年的論文：
我對第 3.2 節 Key Exchange 的理解是，Alice 的私鑰是同源的 $ \phi_A : E \rightarrow E_A $ ，可以用2個整數表示；私鑰： $ (m_A, n_A) $ .
她的公鑰由曲線組成 $ E_A $ ，由多項式表示 $ a,b $ 從它的 Weierstrass 方程 $ E_A: y^2 = x^3 + ax + b $ ，以及兩個扭力基座的圖像 $ P_B, Q_B $ 在她的私人同源下，這似乎是 2 個複點，每個 = 8 個整數。公鑰： $ (E_A, \phi_A(P_B), \phi_A(Q_B) ) $ . 所以我的模糊理解認為公鑰應該包含大約 10 - 16 條資訊，具體取決於這些多項式的表示方式。
在實驗部分，第 7 部分，有一個表格比較了 512 位、768 位和 1024 位密鑰大小的密鑰交換算法的執行時間。
我的問題：這些密鑰大小來自哪裡？他們是否曾經說明公鑰的不同組件的位寬，以及他們改變哪些（哪些）來改變密鑰大小？更好的是，我是否錯過了對密鑰大小和系統安全級別之間關係的分析？
這些密鑰大小的數字來自為有限域選擇的素數的位長度 $ F_p $ . 為了澄清，根本沒有使用複數。橢圓曲線在二次擴展上 $ F_p $ ， IE $ K = F_{p^2} $ , 和一個根 $ i $ 的 $ x^2+1 $ 被選中，使得元素 $ K $ 可以唯一地表示為 $ F_p \oplus i\cdot F_p $ ， IE $ a+ib $ 為了 $ a,b\in F_p $ . 如果 $ p $ 是 $ N $ 位長，然後是一般元素 $ K $ 是 $ 2N $ 位長。積分 $ (x,y) $ 在橢圓曲線上 $ E $ 有 $ x,y \in K $ ，所以他們是 $ 2\cdot2N = 4N $ 位長。的係數 $ E $ 也是元素 $ K $ ，所以他們也是 $ 2N $ 位長。
公鑰由兩部分組成 $ K $ 表示橢圓曲線的係數 $ E_A $ （所以 $ 4N $ 位），以及中的兩個點 $ E_A $ , $ \phi_A(P_B) $ 和 $ \phi_A(Q_B) $ , 分別是 $ 4N $ 位長。那麼公鑰的總長度為 $ 12N $ 位。但是，可以對其進行壓縮，正如您在Costello-Longa-Naehrig中看到的那樣，他們將其歸結為 $ 6N $ 用一些巧妙的技巧。後來的工作將其改進為大約 $ 3.5N $ 同時減少計算工作量。
5.1 節介紹了密鑰大小和安全級別之間的關係。到目前為止，最好的經典攻擊是 $ O(\sqrt[4]{p}) $ ， 所以 $ N/4 $ 位經典安全，最好的量子攻擊是 $ O(\sqrt[6]{p}) $ ， 所以 $ N/6 $ 位量子安全。這就是為什麼 768 位 p 具有 768/6 = 128 位的量子安全性。我真的建議閱讀Costello-Longa-Naehrig，因為其中一些細節更加明確。
超奇異同源圖的底層問題定義了協議的安全級別。簡單來說，hard問題可以定義如下：
給出兩點 $ P, Q $ 上 $ E_1 $ 和他們的圖像 $ \phi(P), \phi(Q) $ 上 $ E_2 $ ，找到秘密同源圖 $ \phi $ . 針對這個問題最著名的攻擊是 Claw find 攻擊，它具有以下複雜性： $ \mathcal{O}(\ell^{1/2}) $ 和 $ \mathcal{O}(\ell^{1/3}) $ 分別針對經典攻擊和量子攻擊，其中 $ \ell $ 是同源度。因此，如果您只有 2 個不同的扭轉子群（SIKE 和 SIDH）具有大致相同的位長（平衡安全性），則您的有限域定義在形式的素數上 $ p=\ell_A^{e_A}\ell_B^{e_B}-1 $ ，因此由於素數位長度僅分為兩部分，因此安全級別可以描述為 $ \mathcal{O}(p^{1/4}) $ 和 $ \mathcal{O}(p^{1/6}) $ 分別針對經典攻擊和量子攻擊。然而，考慮到其他基於同源的密碼學方案，例如基於三個不同扭轉子群的超奇異同源不可否認簽名，即 $ p=\ell_A^{e_A}\ell_B^{e_B}\ell_C^{e_C}-1 $ ，安全級別為 $ \mathcal{O}(p^{1/6}) $ 和 $ \mathcal{O}(p^{1/9}) $ 分別針對經典攻擊和量子攻擊！