Hash
NOTS 是有效的一次簽名方案嗎？
我剛剛了解了NOTS，這是一種基於散列函式的抗量子簽名方案，它聲稱具有更短的簽名和密鑰大小。這個簽名方案是否已知是安全的？通過查看論文，我懷疑它使用索引模數的方式（對手不能只生成具有相同字元數的雜湊嗎？）。合法嗎？
合法嗎？
不，你找到了原因 - 該算法將消息轉換為從 1 到 128 的 16 個值的系列，然後僅基於該值進行簽名。總共有 112 位；實際上，它比這更糟糕，因為他們用來將消息雜湊轉換為 16 個值系列的算法將生成總和（mod 128）到 64 的值；。這意味著使用有效的消息/簽名對，您可以找到第二張圖像，該圖像可以轉換為相同的前 15 個值
$$ 1 $$（因此對於相同的簽名來說是一條有效的消息），具有預期的 $ O(2^{105}) $ 努力。更糟糕的是，由於翻譯不涉及任何隨機化，您可能會發現與預期的衝突（然後要求對一條消息進行簽名；具有相同簽名的第二條消息將是偽造的） $ O(2^{52.5}) $ 努力。 該論文還提出了一系列錯誤的陳述；以下是那些讓我印象深刻的：
- 他們聲稱“除非向驗證者提供大量附加資訊，否則其他類型的 OTS/FTS 方案（WOTS 及其變體除外）無法允許從簽名計算公鑰。”；這是不正確的。對於我見過的每一個基於散列的簽名方案，驗證過程本質上是“從公鑰中獲取消息、簽名和可能的少量數據，計算一系列散列，如果結果與公鑰，你贏了”。也就是說，重建公鑰所需的只是這個“可能少量的數據”，而不是“大量的附加資訊”。一個小點，除了他們反復強調這一點。
- 他們的評估，包括與一些選定的其他基於散列的簽名方案的比較（但沒有大 W 參數）；然而，他們堅持認為他們執行具有不切實際的大散列大小（n 值）的競爭方案 - 他們注意到他們的方案（確實具有較大的 W 參數和較小的 n 值）導致較小的簽名；當他們把拇指放在秤上時，這並不奇怪。
- 他們還聲明“最終，NOTS 已經在不影響安全級別的情況下實現了密鑰和簽名大小的所有這些減少”；即使看一眼他們的表格表明他們聲稱 NOTS 的安全級別明顯較低（不包括我在上面提出的關於它甚至沒有實現這一點的觀點）。
- 至於他們的安全證明，那是由他們提供的算法組成的，這些算法需要偽造並產生衝突；然而，通過算法表明，即使給出了偽造，它也可能失敗（也就是說，不會產生碰撞）；因此作為證明無效。
$$ 1 $$: 一旦你第一次在前 15 場比賽，你總是會在第 16 場比賽。