大文件的數字簽名算法 - 被雜湊函式瓶頸？
我是學習 ECDSA 和 EdDSA 等數字簽名的新手，並且對某些事情感到好奇。
假設我想創建數百萬個文件的數字簽名，總大小為 10TB。
據我了解，數字簽名算法是hash-then-sign，使用的散列函式必須是加密散列，例如SHA-2或SHA-3。但是，查看 SHA-2 和 SHA-3 的典型基準，它們的吞吐量（字節/秒）速度在現代筆記型電腦 CPU 上似乎遠低於每核 500MB/s，這還不錯。
但在沒有硬體加速的環境中，它可能至少慢 4 倍。在移動設備上，根據 javascript 基準，SHA-3 似乎在我的手機上執行 20MB/s。
似乎在某些環境中，雜湊函式將成為創建簽名和驗證簽名的瓶頸。特別是對於移動設備——簽署/驗證 10TB 的文件清單需要幾天時間。
是否有任何加密安全的數字簽名算法在吞吐量方面針對大文件進行了優化？還是我們總是被散列函式所限制？
是否有任何快速的非加密雜湊函式可以用於數字簽名，同時保持加密安全？
當您考慮對 10 TB 數據集進行身份驗證時，請考慮驗證者必須願意處理哪些偽造：如果您一次性簽署 10 TB 數據集，則驗證者必須願意做所有工作以散列最多10 TB即使數據集中的任何地方只有一個比特翻轉**，他們也有機會拒絕偽造。**並且計算不能真正並行化。
有幾種方法可以更好地並行化：
- 您可以獨立地對每條記錄進行簽名，並使用對記錄的唯一索引或鍵或路徑進行編碼的前綴，這樣一個記錄的簽名內容就不會被放入不打算使用的另一條記錄中，例如替換名為的文件
gpg-1.4.14.tar.gz並且gpg-1.4.14.tar.gz.asc由易受攻擊的那些gpg-1.4.13.tar.gz仍然gpg-1.4.13.tar.gz.asc是正確密鑰下的有效消息/簽名對。由於記錄都是獨立簽名的，因此您可以輕鬆地並行計算。然後，只要每條記錄都有一個有界的大小，比如兆字節或千兆字節，那麼在驗證者可以將偽造品扔到地板上之前，偽造者可以用來拒絕向驗證者提供服務的數據量就有一個合理的限制。
但是，這意味著控制您儲存它們的 Amazon S3 伺服器的對手可能會在您不通知的情況下回滾單個記錄。
- 您可以對每條記錄進行雜湊處理，並將每個記錄目錄雜湊為相應記錄的雜湊列表，並對每個目錄目錄進行雜湊處理，依此類推，當您到達根目錄時，對根雜湊進行簽名。
（為了更好的安全性：當你開始這個過程時，選擇一個隨機字元串 $ r $ ; 然後使用 $ m \mapsto H(r \mathbin| m) $ 作為您的雜湊函式，而不僅僅是 $ H $ , 並簽名 $ (r, h) $ 在哪裡 $ h $ 是根雜湊。那麼即使對手有離線碰撞攻擊 $ H $ , 如果他們無法預測 $ r $ 前面的碰撞攻擊是沒有用的，只要 $ H $ 表現出“目標碰撞阻力”的弱得多的特性。）
這稱為Merkle 樹，它也可以並行化，因為樹的每個分支都是獨立散列的。它還承認對每條記錄的快速驗證：驗證根雜湊、驗證目錄條目雜湊、驗證子目錄條目雜湊等，最後驗證記錄雜湊。例如， Tahoe-LAFS（一種加密能力安全分佈式文件系統）大致使用了這種結構。
對手可以回滾*整棵樹，但不能有選擇地*回滾記錄。** 而且，當然，您可以保留根雜湊本身，而不是依靠其他人來保留它的最新簽名版本，從而完全防止回滾。