用橢圓曲線 Schnorr 簽名限制私鑰空間的含義是什麼？
給定一條曲線，我試圖限制私鑰空間以最終減少 Schnorr 簽名大小，如下所示：
假設一條橢圓曲線 $ E $ 在一個領域 $ F $ 帶發電機點 $ G $ 並且主要子組的順序是 $ \ell $ . 場地 $ F $ 可以認為是安全的。（為了舉例，可以假設參數是 Curve25519 的參數，但我正在尋找一個通用的、規範的答案。）
我特別關注 Schnorr 簽名，但我的問題的答案可能會擴展到 EdDSA 及其變體。總結私鑰的簽名過程 $ k $ （標量）和消息 $ M $ （字節序列）
- 隨機選擇一個標量值 $ r $ (nonce) 作為範圍內的臨時隨機標量 $ 0 < r < \ell $ .
- 生成臨時曲線點 $ R = [r]G $ .
- 生成雜湊值 $ c = H(\underline{R} || M) $ ， 在哪裡 $ H $ 是一個密碼散列函式， $ \underline{R} $ 表示點的序列化形式 $ R $ 作為字節序列和 $ || $ 表示連接。解釋字節序列 $ c $ 作為標量整數。
- 計算標量值 $ S = r + ck \mod \ell $ .
- 簽名現在是元組 $ (c, S) $ .
注意如何 $ S $ 是加法和乘法取模的結果 $ \ell $ . 通過限制私鑰空間（即人為地減少可能的範圍 $ k $ )，因此也可以限制結果的大小 $ S $ .
現在假設上限為 $ k $ 從減少 $ \ell $ 至 $ 2^n $ ; 在這個縮小的空間內， $ k $ 仍然是隨機均勻挑選的。隨機值 $ r $ 在正常空間中被挑選 $ 0 < r < \ell $ 任何狀況之下。
鑑於此背景，我的問題是：
- 如何降低上限 $ k $ 提高攻擊者的學習機會 $ k $ 除了任何給定的蠻力搜尋空間明顯減少 $ n \le \log_2 \ell $ ?
- **如何降低上限 $ k $ 從 $ \ell $ 至 $ 2^n $ 與短 Schnorr 簽名互動？**我用“短 Schnorr 簽名”來表示修剪雜湊值 $ c $ 被修剪為 $ b $ ， 在哪裡 $ b $ 是以位為單位的橢圓曲線的強度（例如，對於 Curve25519，這意味著使用 128 位雜湊值 $ c $ ; 另見 Schnorr 的原始論文，第 頁。242 尤其是Gregory Neven、Nigel P. Smart、Bogdan Warinschi的後續分析。Schnorr 簽名的雜湊函式要求，Journal of Mathematical Cryptology 3(1)，2009，第 69-87 頁，以令人不安的鬆散安全性降低結尾，但出於本問題的目的，應假定它是安全的）。
- 假設在素數域上有一條曲線 $ F_q $ ， 在哪裡 $ q $ 是一個 256 位的數字，空間可以容納多少 $ k $ 減少並且仍然滿足 80 位對稱等效強度的目標安全級別？
出於效率原因，這很有趣：如果空間 $ k $ 可以顯著降低，最終計算 $ \mod \ell $ 可以完全跳過或至少簡化，從而在簽名時提高速度。
我知道 BLS 簽名存在並產生短簽名（例如 BLS12-381 提供 48 字節簽名），但它們的實現和計算要復雜得多。同樣，我知道一些多元加密方案會產生非常短的簽名（我想到了 Gui，儘管已獲得專利）。如果我只想要非常短的簽名，我會研究不是 Schnorr 簽名的方案。
之前也發布過類似的問題；“ 64 位橢圓曲線鍵”。但是，那裡的答案通常假設在 64 位欄位上創建新曲線或截斷公鑰，這兩者都不適用，因為我正在減少私鑰的範圍，將公鑰和欄位保留為-是。
如何降低上限 $ k $ （至 $ 2^n $ ) 提高攻擊者的學習機會 $ k $
安全至多變成 $ n/2 $ 位。嬰兒步 - 巨步發現 $ k $ 給定公鑰 $ \underline{[k]G} $ 計算成本 $ \mathcal O(2^{n/2}) $ . Pollard 的 Rho可以適應相同的漸近成本，記憶體少且並行化效率高。為了保持安全級別 $ \mathcal O(\sqrt\ell) $ 正常的 EC-Schnorr，我們不能有 $ n $ 大大低於 $ \log_2\ell $ .
如何降低上限 $ k $ 從 $ \ell $ 至 $ 2^n $ 與短 Schnorr 簽名互動？
由於上述原因，它降低了安全性。
另外，如果我們保留，我看不到它如何減少問題簽名方案中的簽名大小 $ r $ 隨機輸入 $ [0,\ell) $ 和 $ \ell $ 不變，因為那時 $ S $ 也是隨機的 $ [0,\ell) $ ，因此我們需要傳輸 $ \left\lceil\log_2\ell\right\rceil $ 位為 $ S $ .
為了 $ n $ -位對稱安全性（問題中為 80 位），以及盡可能小的 Schnorr 簽名，我們可以
- 使用縮小尺寸的橢圓曲線組 $ \ell\approx 2^{2n} $ . 這正是我們在sec2-v2中有 secp192r1 和 secp192k1 的原因，它們有望提供 96 位安全性。但是，這些使用基本欄位 $ \Bbb F_q $ 大小大致相同 $ \ell $ ，而且我不知道我們是否可以建構一個安全的橢圓曲線組，更不用說如何基於 $ \Bbb F_q $ 更大的尺寸（例如 $ \log_2 q\approx256 $ 如所問）。
- 從通常/現代減少雜湊寬度 $ 2n $ 對原來的 $ n $ ， 為一個 $ 3n $ 位簽名與 1 結合使用。原始的 Schnorr 簽名方案就是這樣工作的，其啟發式的安全性參數至少經受住了時間的考驗。
- 作為 2. 的替代方案，以及在對位大小的消息進行簽名時 $ m\ge n $ ，使用 Schnorr 方案的變體，提供帶有消息恢復的簽名方案（參見那裡的列表），它可以嵌入 $ n $ 消息位成 $ 4n $ 位簽名，從而實現有效 $ 3n $ -bit 成本，就像應用程序中的原始 Schnorr 簽名方案一樣，其中消息沿著簽名發送並且至少是 $ n $ -少量。主要優點是對安全性的更積極的論點。缺點是簽名不再與消息分離，一些最佳方案受專利保護，並且（因此）很少使用。
注意：如果只有簽名大小（而不是公鑰大小或性能）是一個問題，則沒有理由使用橢圓曲線組。原始的 Schnorr 簽名方案使用 Schnoor 群在素數階的子群上 $ \ell $ 構造為一個子群 $ \Bbb Z_p^* $ 為素數 $ p=2,r,\ell+1 $ ，並且簽名大小不受大 $ p $ （為了現代安全性，它需要以數千位為單位）。
如果有人（像我一樣）對原始 Schnoor 簽名方案的啟發式安全論點（以及某些有限模型中的複雜現代證明）謹慎謹慎，則可以冒險進行改進：
- 去隨機化選擇 $ r $ 通過使其成為確定性 PRF，由 $ 2n $ -位私鑰，消息的（寬的，安全的）主散列： $ r=\operatorname{PRF}k(H\text{wide}(M)) $ . 它消除了對不可預測的 RNG 的要求（眾所周知，很難獲得），並且只能通過側通道造成傷害。這是 EdDSA 使用的。
- 建構 $ n $ -bit（因此狹窄得令人不舒服）散列 $ c $ 簽名的一部分使用故意慢速散列（如 Argon2）以增加其對第二原像的抵抗力，這是 Schnorr 簽名中安全性的限制因素之一（並且可以說是主要的）。它不能傷害。即使參數化對整體性能的影響可以忽略不計，它也可以將針對特定攻擊的抵抗力提高至少 8 位，這很不錯。
- 使公鑰輸入的一部分說 $ n $ 位雜湊 $ c $ . 這是一種針對多目標攻擊的帶吊帶方法。它的成本可以忽略不計，而且不會造成傷害。結合以上，使得 $ c $ 簽名的一部分 $ c=H_{n\text{-bit, slow}}(\underline{R}\mathbin|H_\text{wide}(M)\mathbin|K_\text{pub}) $
- $$ my personal fad $$而不是直接使用 $ n $ -少量 $ c $ 簽名的一部分 $ (c,S) $ 在計算中 $ S=r+c,k\bmod\ell $ ，我們可以把它恢復到完整的狀態 $ 2n $ - 一點 $ \ell $ （如在具有最強安全參數的 Schnorr 簽名的現代變體中使用的）通過使用公共轉換，例如散列。有了最大的腰帶和吊帶，那就是 $ S=r+c’,k\bmod\ell $ 和 $ c’=H_{2n\text{-bit, slow}}(c\mathbin|H_\text{wide}(M)\mathbin|K_\text{pub}) $ . 可以說，它不會造成傷害，並為各種可能的攻擊增加了障礙。
上面的簽名大小為 $ 3n $ -bit，只需要對簽名驗證進行微不足道的調整，並略微減慢簽名生成或驗證的速度。對於大消息， $ H_\text{wide} $ 是限制速度因素，我們可以為此使案例如 SHA-512。可以將慢速散列的參數化設置為低於一次標量乘法的成本，在建構的慢速散列中可能有 3/4 $ c $ ，其餘為 $ c’ $ .