XEdDSA 和 VXEdDSA 簽名方案中的性能考慮

有人可以解釋XEdDSA 和 VXEdDSA 簽名方案第 7 節中的以下段落嗎？

下面的段落指出我們正在雜湊兩次（我無法得到那個）。在這種情況下，預散列將如何提供幫助。

預散列：除 XEdDSA 驗證外，簽名和驗證算法對輸入消息進行兩次散列。對於大型消息，這可能會很昂貴，並且需要大型緩衝區或更複雜的 API。

為了防止這種情況，API 可能希望指定所有實現必須能夠緩衝的最大消息大小。協議設計者可以指定消息欄位的“預散列”以適應此。鼓勵設計人員有選擇地使用預散列，以限制衝突攻擊的潛在影響（例如，對消息的附件進行預散列，而不是對消息頭或正文進行預散列）。

請注意 XEdDSA 中的以下三行： $ \newcommand{\opn}{\operatorname} $

1. $ r=\opn{hash}(a\parallel M\parallel Z)\bmod q $
2. $ R=rB $
3. $ h=\opn{hash}(R\parallel A\parallel M)\bmod q $

如您所見，第三條指令的雜湊輸入取決於第一條指令的雜湊輸出。更糟糕的是，你不能“只是附加”所說的輸出，它是第一位的。

現在假設您有一條大消息（如 1 GB 大小）。雖然您可以輕鬆地對第一個雜湊進行流式處理，但您必須緩沖完整的消息，以便您可以將其提供給第二個雜湊呼叫，這要求您要麼 a) 擁有一個愚蠢的大型靜態分配緩衝區，要麼 b) 顯著限制消息大小或 c）使用動態分配（這真的很慢）。

那麼我們該如何解決這個問題呢？**預雜湊。**假設“ $ M $ " 因為簽名算法實際上不是 1GB M，而是固定大小 $ \opn{hash}(M) $ . 現在我們可以使用一個小的、恆定大小的緩衝區來儲存“ $ M $ “我們可以流式計算 $ \opn{hash}(M) $ ，這意味著我們在那裡也不需要不必要的大緩衝區。然而，進行預散列的明顯缺點是散列上的衝突很容易轉化為對簽名方案的偽造攻擊（如 $ \opn{hash}(M) $ 和 $ \opn{hash}(M’) $ 具有相同的雜湊，對於簽名算法，它們本質上是相同的消息，即使 $ M\neq M’ $ ).

---

我在這裡多次提到“流處理”，所以我會讓你快速理解它的含義。在雜湊函式的實際實現中，您通常會發現以下三個函式：

hash_init(context*)
hash_update(context*,byte* data)
hash_final(context*,byte* digest)

因此，您通常會為雜湊初始化一些上下文，然後用數據更新上下文幾次，最後從上下文中提取雜湊值（摘要）。大多數雜湊函式旨在支持這種實現風格並允許context成為編譯時大小的結構，因此如果您獲得數據流，您可以不斷呼叫hash_update然後丟棄消息部分的緩衝區（如果您沒有進一步使用為此，就是）。所以在這種情況下，你最終會得到一個小的上下文結構，一個小的消息部分緩衝區，而不​​是一個巨大的完整消息緩衝區。

引用自：https://crypto.stackexchange.com/questions/47724