在假設量子電腦簽名後，基於雜湊的簽名方案有多安全？
考慮一個基於雜湊的簽名方案，它需要 $ k $ - 要簽名的任意長度消息的位散列（例如 Lamport 一次性簽名方案）。我的理解是，假設這一步是簽名方案的最薄弱環節，並且使用的雜湊函式是抗碰撞的，這個簽名方案提供 $ k $ - 簽名前的位安全性和 $ k/2 $ - 簽名後的位安全性（因為任何試圖偽造簽名的人在獲取他們試圖簽名的任何消息的雜湊值時平均會免費獲得一半的位）。
那麼，我的問題是，如果對手試圖使用目前已知的用於查找雜湊衝突的最佳量子算法來查找與量子電腦的雜湊衝突，那麼這種簽名方案的安全性是什麼？
這個問題的答案：
基於散列的簽名方案 XMSS/LMS 易受原像/第二原像攻擊？
提供有用的資訊並暗示該計劃仍將提供 $ k/2 $ -位安全性
“格羅弗的算法使我們能夠找到復雜度為 $ Θ(2^{𝑛/2}) $ 然而，在量子世界中，生日悖論已經限制了經典世界中碰撞阻力的複雜性。（而且我們不知道在量子世界中有更好的方法來繞過它……”
引用這篇論文：
$$ 1 $$ https://cr.yp.to/hash/collisioncost-20090517.pdf 這似乎揭穿了本文的主張：
$$ 2 $$ http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.55.5265&rep=rep1&type=pdf 它提出了一種量子算法來更有效地發現碰撞。
提出的論點
$$ 1 $$似乎是有道理的（即在$$ 2 $$做出了不切實際的假設，即通信本質上是免費的），但我在這方面的知識還不夠，無法更徹底地分析它。對於那些是：這個論點有效嗎？量子密碼學研究人員的普遍共識是什麼？ 最後，作者在
$$ 1 $$還聲明如下： “其實，時間 $ 2b/3 $ 已經由大小為剛剛的非量子機器實現了 $ 2b/6 $ , 和更小的時間 $ 2b/4 $ 已經由大小的非量子機器實現了 $ 2b/4 $ . 任何害怕量子雜湊衝突算法的人已經對非量子雜湊衝突算法有更多的恐懼。”
作者在這裡指的是什麼算法？這是否意味著使用 k 位雜湊函式的簽名方案的簽名後安全性已經小於 $ k/2 $ 即使沒有量子電腦，比特？
兩件事情：
- “量子電腦基於預言機的碰撞發現問題有多難”這個問題是一個懸而未決的問題。我們知道它介於兩者之間 $ O(\sqrt[3]{n}) $ 和 $ O(\sqrt{n}) $ 努力（我記得有一篇論文表明 $ O(\sqrt[3]{n}) $ Oracle 查詢是下限，但我忘記了那是什麼論文）——我們不知道它實際上在哪個範圍內。Brassard 等人展示了一種發現與 $ O(\sqrt[3]{n}) $ 甲骨文查詢；然而 Dan 指出，與該算法相關的其他成本使得它實際上比僅並行執行大量的第二原像查找器更昂貴
$$ 1 $$. 目前未知是否存在另一種算法使用 $ o(\sqrt{n}) $ 甲骨文查詢$$ 2 $$，並且沒有 Brassard 算法所具有的其他費用…
- 目前的三個“基於散列的簽名標準”，即 LMS、XMSS 和 Sphincs+，實際上並不依賴於抗碰撞性，即使在對消息進行初始散列時也是如此。這三個人所做的是，當簽名者收到消息時 $ M $ , 簽名者選擇了一個不可預測的 $ R $ 然後計算 $ \text{Hash}(R + M) $ （然後將該雜湊用於其餘的簽名操作）。如果對手送出要簽名的消息，他不知道該值是什麼 $ R $ 簽名者將選擇；相反，為了執行碰撞攻擊，他需要選擇兩個不同的消息 $ M, M’ $ 為此 $ \text{Hash}(R + M) = \text{Hash}(R + M’) $ 具有非平凡機率（給定機率分佈 $ R $ )，這似乎比找到碰撞要困難得多。
$$ 1 $$Brassard 算法本質上是一種大型多目標二次原像攻擊，Dan 的抱怨是，在大型稀疏非結構化空間上進行辨識的量子邏輯非常昂貴。在未發表的作品中，我查看了 Brassard 算法，並根據已發布的 SHA-256 量子電路和草圖目標搜尋“每個搜尋者的目標數”和“搜尋者數”之間的“最佳位置”我繪製了辨識器電路，我得出的結論是，這使得該問題的攻擊成本比單個原像問題低大約 1000 倍（最佳點是每個搜尋器大約有一百萬個目標）。 $$ 2 $$對於那些不熟悉 little-oh 符號的人， $ o(\sqrt{n}) $ 意思是“少於 $ c\sqrt{n} $ 查詢，對於任何 $ c > 0 $ （只要 $ n $ 足夠大，“足夠大”的含義取決於 $ c $ ）。更通俗地說， $ o(\sqrt{n}) $ 意思是’增長慢於 $ \sqrt{n} $ '