你能把橢圓曲線私鑰壓縮成兩半嗎？
據此，一 $ n $ -bit key 提供關於 $ n/2 $ 位安全。這讓我想知道，你能把密鑰壓縮成兩半嗎？
乍一看，不，因為密鑰本質上是一個隨機數，因此無法壓縮。
但是讓我們看一下相對於公鑰的私鑰。從資訊論的角度來看，私鑰相對於公鑰的熵為零。
所以，給定一個 $ n $ -bit 私鑰 $ x $ , 你能產生一個 $ n/2 $ 秘密 $ s $ , 這樣使用 $ s $ 和公鑰 $ X $ ，你能高效地計算出私鑰嗎？
這不是您想要的方向，但是我相信這是您要問的問題的答案：
據此，一 $ n $ -bit key 提供關於 $ n/2 $ 位安全。這讓我想知道，你能把密鑰壓縮成兩半嗎？
一個明顯的方法是選擇一個 $ n/2 $ 位機密 $ s $ ，並將其儲存為您的長期私鑰；然後，當你準備好開始使用它時，你首先計算 $ \text{SHAKE}(s, u) $ （在哪裡 $ u $ 是一些公共標識符字元串
$$ 1 $$)，並使用第一個 $ n $ 其中的一部分作為您的私人乘數（我們將其稱為 $ t $ ，所以你的公鑰是 $ tG $ ) 看起來攻擊者有兩種可能的方法來對付這個：
- 蠻力 $ s $ ; 預期努力 $ O(2^{n/2}) $
- 使用離散對數算法恢復 $ t $ （這和 $ s $ 給攻擊者）；預期努力 $ O(2^{n/2}) $
似乎沒有將這兩者結合起來的可行攻擊；您無法判斷潛在乘數是否為 $ t $ 沒有暴力破解 SHAKE；一旦你這樣做了，你還不如堅持攻擊一。
$$ 1 $$: 我們插入 $ u $ 在 SHAKE 呼叫中嘗試避免多密鑰攻擊（攻擊者被賦予多個公鑰，並嘗試恢復其中任何一個的私鑰）；它類似於密碼雜湊中的鹽。
修正曲線 $ E $ 和一個標準基點 $ G $ 有秩序的 $ \ell \approx 2^{256} $ . 讓 $ n \in \mathbb Z/\ell\mathbb Z $ 是一個統一的隨機秘密標量，並讓 $ P = [n]G $ 是對應的公鑰。如果儲存 128 位數量 $ \tilde n = \lfloor n/2^{128}\rfloor $ 除了 256 位數量 $ P $ , 你可以恢復 $ n $ 通過應用Pollard’s kangaroo ( paywall-free ) 到 $ P $ 去尋找 $ n $ 在區間 $ [2^{128} \cdot \tilde n, 2^{129} \cdot \tilde n] $ , 按成本 $ {\sim}2^{64} $ .
但是現在你必須儲存一個 384 位的數量 $ (\tilde n, P) $ 並花費 $ 2^{64} $ 在波拉德的袋鼠上騎自行車減壓 $ n $ , 而不是儲存 256 位的數量 $ n $ 和支出 $ {\sim}2^{16} $ 標量乘法上的循環以解壓縮 $ P $ （如果你需要 $ P $ 完全）。所以很難想像這是一個優勢。