Cryptographic Sponges 針對通用量子攻擊提供什麼安全性？
面對非量子攻擊者，Keccak
$$ r=1088,c=512 $$512 位輸出提供：
- 碰撞阻力高達 $ 2^{256} $ 操作
- 原像電阻高達 $ 2^{256} $ 操作
- 第二原像電阻高達 $ 2^{256} $ 操作
然而，總的來說，使用量子計算，特別是Grover 算法，可以更有效地攻擊散列函式。Daniel J. Bernstein 撰寫了關於針對所有第二輪 SHA-3 候選者的量子攻擊的文章。然而，在那篇論文中，所有針對 Keccak 變體的攻擊都是針對內部容量是雜湊長度兩倍的截斷雜湊，例如 Keccak
$$ r=1152,c=448 $$具有 224 位輸出。 我的問題是，如果 Keccak 的完整 512 位雜湊輸出長度
$$ r=1088,c=512 $$被使用，這是否提供安全性高達 $ 2^{256} $ 使用 Grover 算法對量子攻擊者進行操作，或者安全性限制為原像強度的一半，即僅 $ 2^{128} $ 操作？
除非 Keccak 有我不知道的結構性弱點，否則答案既不是 128 也不是 256！
Gilles Brassard、Peter Høyer 和 Alain Tapp 在他們的論文“Hash and Claw-Free Functions 的量子密碼分析”中描述了一種量子生日攻擊，該攻擊通過創建一個大小表有效地工作 $ \sqrt[3]{2^b} $ （相對於 $ \sqrt{2^b} $ 對於經典的生日攻擊），然後利用 Grover 算法找到碰撞。
雖然經典的生日攻擊因此需要 $ {\mathcal O}\left(\sqrt{2^b}\right) $ 時間和記憶，量子生日攻擊只需要 $ {\mathcal O}\left(\sqrt[3]{2^b}\right) $ 時間和記憶。
這意味著提供一個 $ b $ 針對量子對手的比特安全級別，雜湊函式必須至少提供 $ 3b $ 位輸出。
在您的 512 位 Keccak 的情況下，您的安全級別將是 $ 170\frac{2}{3} $ .