Schnorr 簽名與 DSA 和 DLP 的安全性
Schnorr 簽名方案是一種帶有附錄的隨機簽名方案。簽名是 $ 3t $ - 推測的位 $ t $ - 選擇消息設置中的位安全性，最多具有 $ 2^{t/2} $ 對簽名者的查詢；忠實於參考論文的描述在問題的後面。
它很簡單，比 DSA 簽名或我能找到的任何其他帶有附錄的簽名方案緊湊 25%。據我所知，沒有任何基於 DL 的具有消息恢復功能的簽名方案（DL-MR 參考書目的子集）在與任意非冗餘消息一起使用時在緊湊性方面勝過它。
問題：
它對競爭對手有什麼缺點（除了長期存在的專利問題）？
為什麼大多數後來的論述都默默地使用 $ 2t $ -位雜湊因此 $ 4t $ 位簽名，包括學者
$$ HAC1996 $$和現行的國際標準$$ ISO14888 $$（除了對原始散列的狹窄程度的模糊不安之外）？ 是否有一種安全性可以說等同於 DSA（或更好的 DLP 或相關）的方案，但具有原始 Schnorr 簽名方案的緊湊性？如果不是，那麼用最後提出的小修改來證明一些東西呢，它使每個消息秘密的生成去隨機化，使用公鑰相關的散列，以及散列使用於驗證的指數的寬度加倍？
Schnorr 簽名參考書目
$$ Sc89a $$：Claus-Peter Schnorr，在數據交換系統中辨識使用者以及生成和驗證電子簽名的方法，歐洲專利登記簿中的EP0383985，1989年；
$$ Sc89b $$: id., Efficient Identification and Signatures for Smart Cards , 在Crypto 1989 的程序中；
$$ Sc90a $$: id., Method for Subscriber Identification and for the generation and verifying in a data exchange system , EP0384475 in European Patent Register, 1990 ;
$$ Sc90b $$: id.，在數據交換系統中辨識訂戶以及生成和驗證電子簽名的方法，美國專利 4,995,082；
$$ Sc91 $$: id., Efficient Signature Generation by Smart Cards , in Journal of cryptology, 1991 (alternative version ). $$ HAC96 $$：Alfred J. Menezes、Paul C. van Oorschot、Scott A. Vanstone 應用密碼學手冊，1996 年，第11.5.3節。 $$ PS96 $$：David Pointcheval，Jacques Stern，簽名方案的安全證明，在Crypto 1996 的程序中；
$$ PS00 $$: id.，數字簽名和盲簽名的安全參數，密碼學雜誌，2000 年。 $$ BN06 $$: Mihir Bellare, Gregory Neven,普通公鑰模型中的多重簽名和一般分叉引理，在ACM 的 CCS 2006 程序中。 $$ NSW09 $$：Gregory Neven、Nigel Smart、Bogdan Warinschi，Schnorr 簽名的雜湊函式要求，在數學密碼學雜誌，2009 年。 $$ Br15 $$：Daniel RL Brown，Short Schnorr signatures requires a hash function with more than just random-prefix resistance，ePrint 2015。 $$ Be15 $$：Daniel J. Bernstein，多使用者 Schnorr 安全性，在作者網站上重新訪問，2015 年。 $$ KMP16 $$: Eike Kiltz, Daniel Masny, Jiaxin Pan, Optimal Security Proofs for Signatures from Identification Schemes，在Crypto 2016 的會議記錄中。 $$ ISO14888 $$：ISO/IEC 14888-3（目前第 3 版，2016 年），資訊技術 - 安全技術 - 帶附錄的數字簽名 - 第 3 部分：基於離散對數的機制，ISO（預覽版）和IEC（預覽版）。
原創 Schnorr 簽名方案
基於
$$ Sc91 $$. 該方案被指出適用於任何訂單組 $ q $ 其中 DL 問題很難解決，但我們使用原始表示法，並以推測的安全複雜性為例 $ t=72 $ -bit 在選擇的消息設置中。 一次性初始化：
- 主要 $ q $ 的 $ \approx2t $ 位（例如 $ q $ 超過 140 位）
- 主要 $ p $ 和 $ q $ 劃分 $ p-1 $ （例如 $ p $ 超過 512 位，有警告）
- 發電機 $ \alpha $ 有秩序的 $ q $ ; IE， $ \alpha^q\equiv1\pmod p $ , $ \alpha\ne1\pmod q $
- 單向雜湊函式 $ h:\mathbb Z_p^\times{0,1}^\to{0,1}^t $
雜湊 $ h $ 必須是這樣的，對於任何固定 $ x $ ， 功能 $ m\to h(x,m) $ 是單向的（對於固定的抗原像 $ x $ ). $ h(x,m) $ 應該是大約均勻分佈的，至少有 $ \lceil\log_2q\rceil $ 的 $ x $ 考慮到（現代加密雜湊滿足這些要求）。
密鑰設置（每個使用者）：
- 選擇私鑰 $ s $ （均勻地）隨機地 $ {1,2,\dots,q} $
- 發佈公鑰 $ v\gets\alpha^{-s}\bmod p $
消息簽名 $ m $ :
- 挑選 $ r $ （均勻地）隨機地 $ {1,2,\dots,q} $
- $ x\gets\alpha^r\bmod p $
- $ e\gets h(x,m) $
- $ y\gets r+s,e\bmod q $
- 輸出簽名 $ (e,y) $
對涉嫌消息的驗證 $ m $ ， 簽名 $ (e,y) $ , 驗證公鑰 $ v $
- $ \bar x\gets\alpha^y,v^e\bmod p $
- 檢查 $ e=h(\bar x,m) $
正版簽名檢查是因為 $ \bar x\equiv\alpha^y,v^e\equiv\alpha^{r+s,e},\alpha^{-s,e}\equiv\alpha^r\equiv x\pmod p $ .
和 $ r $ 秘密且均勻隨機，以及 $ y=r+s,e\bmod q $ ， 的知識 $ (y,e) $ 本身並沒有洩露任何關於 $ s $ . 有關其他安全論點，請參閱該文章，所有這些都基於：看似合理的攻擊有效，但至少要付出代價 $ 2^t $ 散列或破壞 DLP 或顯然更複雜的問題，另外還涉及 $ h $ .
筆記：
$$ Sc89a $$,$$ Sc90a $$， 和$$ Sc91 $$（但不是$$ Sc89b $$) 提到系統可以轉置到其他組，例如橢圓曲線組。
暫定：強化 Schnorr 簽名方案
我提出了三個獨立的更改，它們保持相同的簽名大小。總體目標是提高安全性，並可能在使用的組中將其簡化為 DLP。
- 更換揀貨 $ r $ 隨機輸入 $ {1,2,\dots,q} $ 在簽名時，由 $ r=\operatorname{mac}(s,m) $ 和 $ \operatorname{mac}:{1,2,\dots,q}\times {0,1}^*\to{1,2\dots,q} $ .
基本原理：消除對 RNG 的需求，這種失敗是 (EC)DSA 中久經考驗的災難配方。這種去隨機化技術用於許多現代簽名方案，包括Ed25519（歸屬於 George Barwood，1997 年 2 月，sci.crypt）。 2. 製作 $ h $ 依賴於公鑰 $ v $ ，並針對 ROM 中的安全性；因此
$ h:\mathbb Z_p^\times\mathbb Z_p^\times{0,1}^*\to{0,1}^t $ , 並註明結果 $ h_v(x,m) $
理由：更好地支持安全聲明 $ 2^{t/2} $ 每個公鑰選擇的簽名；不要玩雜湊屬性的遊戲，因為雜湊已經變得相對便宜。 3. 添加雜湊函式 $ h’ $ 依賴於公鑰 $ v $ 和留言 $ m $ , 展開 $ e $ 到寬度 $ q $ 使用前。
$ h’:{1,2,\dots,q}\times{0,1}^t\times{0,1}^*\to{1,2,\dots,2^{\left\lfloor\log_2(q)\right\rfloor}} $ , 並註明結果 $ h_v’(e,m) $
簽名修改為執行 $ y\gets r+s,h_v’(e,m)\bmod q $
驗證修改為執行 $ \bar x\gets\alpha^y,v^{h_v’(e,m)}\bmod p $
理由：
- 介紹 $ h’ $ 做指數 $ v $ 在驗證到達大部分指數域時 $ m $ 變化，而不是一小部分 $ 2^{-t} $ 其中，希望有助於在$$ PS96 $$或者$$ NSW09 $$.
- 當使用組合兩個模冪的“Shamir 技巧”時，由於額外的寬度而增加的簽名驗證成本很低 $ \alpha^y,v^{h_v’(e,m)}\bmod p $ .
- 第二次原像攻擊 $ h $ 單獨不再導致偽造（沒有 $ h’ $ , 這種攻擊可以通過具有預期的蠻力 $ 2^t $ 呼叫 $ h $ 與改變 $ m $ ，並且沒有分組操作）。
- 比較窄的 $ e $ 在兩個雜湊之間被屏蔽。
注意：散列大容量的成本 $ m $ 之間可以共享 $ \operatorname{mac}(s,m) $ （僅適用於簽名者）， $ h_v(x,m) $ ， 和 $ h_v’(e,m) $ ，通過使用一個常見的抗碰撞雜湊 $ m $ 過寬 $ \ge2t $ 作為中間的共同步驟。
你的文章讓我有點困惑，我認為你從錯誤的角度思考這個問題。
是否有一種安全性可以說等同於 DSA（或更好的 DLP 或相關）的方案，但具有原始 Schnorr 簽名方案的緊湊性？
是的，施諾爾簽名。他們真的是你應該做的。與可怕的 (EC)DSA 方案相反，這在理論上和直覺上都是正確的做法。Schnorr 簽名確實降低了基礎組中的 DLP（參見$$ PS96 $$)，雖然不是很緊。我的感覺是，DSA 只是繞過 Schnorr 專利的一種手段，現在它已經消失了，DSA 應該繼續使用它。讓我試著在某種程度上支持這些說法。
讓我們先看看 Schnorr 簽名。我們首先考慮 Schnorr辨識方案來定義它們。在 DLP 困難的組中，它允許我們以互動方式證明離散日誌的知識，而無需透露有關離散日誌本身的任何資訊。它在數學上是正確的，您可以降低其對 DLP 的安全性。它是一個互動式協議，但我們可以通過應用 Fiat-Shamir 啟發式使其非互動式。同樣，對 DLP 的減少仍然存在。通過在挑戰中包含一條消息，我們獲得了一個簽名方案。
現在讓我們以 ECDSA 為例。我們在有限域上的橢圓曲線上工作 $ \mathbb{F}_p $ , 對於素數 $ p $ ，假設我們有一個基點 $ G $ 有訂單 $ n $ . 協議是這樣的
- 選擇一個均勻隨機的 $ k $ 從 $ [1,n-1] $
- 計算 $ (x_1,y_1) = k\times G $
- 計算 $ r = x_1 \bmod n $ .
讓我們想想這裡發生了什麼。選擇 $ k $ 從 $ [1,n-1] $ 有道理，因為它將是一些秘密的離散日誌。然後取冪 $ G $ 和 $ k $ 也有道理，因為 $ G $ 有訂單 $ n $ . 然後我們計算 $ r = x_1 \bmod n $ . 想想你在這裡做什麼，然後意識到這毫無意義。元素 $ x_1 $ 在 $ \mathbb{F}p $ , 那麼我們為什麼要減少這個模數 $ n $ ? 從數學上講，這完全是愚蠢的。如果 $ x_1 $ 在 $ \mathbb{F}{p^2} $ 還是更大的領域？那麼操作就更沒有意義了。因為這沒有任何意義，所以幾乎不可能為這個方案提供安全證明（據我所知，沒有人有）。
總而言之，真正的問題應該是為什麼人們仍在使用 (EC)DSA（是的，我意識到可能存在遺留問題）？這是對 Schnorr 的畸形改編，應該成為過去的錯誤。
讓我試著回答你的其他問題。
它對競爭對手有什麼缺點（除了長期存在的專利問題）？
這裡有一些話要說。首先，您描述方案的方式不一定是它必須如何完成。簽名可以是 $ (x,y) $ 相反，大小 $ 4t $ . 事實上，在我看來，這是自然的起點，而採用散列是一種“壓縮”版本。我相信這實際上是更常見的做法，因為它允許批量簽名驗證（而散列版本則不允許）。
此外，要獲得足夠的隨機性來挑選可能並不容易 $ r $ 均勻隨機。相反，您可以選擇偽隨機，作為一些適當事物的雜湊。最後，您可以在計算中包含公鑰 $ e $ ， 所以 $ e\leftarrow h(x,m,v) $ 以防止多目標攻擊。
我所做的只是描述EdDSA簽名方案。它本質上只是一個 Schnorr 簽名，應用了上述更改。根據上下文，這可以說是要走的路。
為什麼大多數後來的說明都默默地使用 2t 位散列，因此使用 4 位簽名
我無法對此給出明確的答案，但我相信有一段時間不清楚雜湊應該多長時間才能提供適當的安全級別。但是，正如我上面所說， $ 4t $ -bit 簽名大小可能是最常見的。
我提出了三個獨立的更改，它們保持相同的簽名大小。
前兩個應用於 EdDSA。我不確定第三個的意義是什麼。價值 $ e $ 和 $ v $ 是公開的，我們為什麼要關心它們的結構？