跳到主要内容
ecdsa.com

Grover 算法

Lov Grover 于1996年提出的量子搜索算法,能在约 √N 步内从 N 个元素中找到被标记的一个,因此最多使对称密钥和哈希原像的有效安全位数减半。
其他写法Grover's algorithmGrover searchquantum search

攻击 AES-128 需要约 2⁶⁴ 次串行的量子迭代,而每次迭代都是一个深度很大、经过纠错的 AES 电路;这种加速也难以并行化(把搜索分到 k 台机器上只能获得 √k 的收益)。因此 NIST 将 AES-128 归入安全类别 1,也不要求把对称密钥长度加倍;NIST IR 8547 继续保留 AES-128、SHA-256 和 SHA-3。

在碰撞搜索上,一旦计入内存成本,量子算法相对经典算法几乎没有实际优势。正因为 Grover 算法,后量子安全类别以 AES 和 SHA-2/SHA-3 的强度为基准,AES-256 也成为保护极长期秘密值的保守选择。

标准与参考资料

全部术语