Low-gate Quantum Golden Collision Finding
Low-gate Quantum Golden Collision Finding
复制标题
低门量子黄金碰撞发现
DOI：
10.1007/978-3-030-81652-0_13
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
André Schrottenloher
中科院分区：
文献类型：
--
作者：
Samuel Jaques;André Schrottenloher
黄金碰撞问题要求我们在一个伪随机函数的输出中找到一个单一的、特殊的碰撞。这概括了中间相遇问题，因此适用于许多情况，例如NIST后量子候选者SIKE的密码分析。这个问题的主要量子算法是内存密集型的，量子存储器的成本可能非常高。量子电路模型意味着随机访问的线性代价，这消除了以前的量子碰撞发现算法相对于Grover算法或经典货车Oorschot-Wiener算法的指数优势。假设量子存储器访问成本高，但免费维护，我们提供了新的量子算法的黄金碰撞问题与高存储器的要求，但低门成本。在二维连通性布局的假设下，我们提供了更好的量子并行化方法来寻找一般碰撞和黄金碰撞。这降低了黄金碰撞和中间相遇问题（包括SIKE）的量子安全性。
The golden collision problem asks us to find a single, special collision among the outputs of a pseudorandom function. This generalizes meet-in-the-middle problems, and is thus applicable in many contexts, such as cryptanalysis of the NIST post-quantum candidate SIKE. The main quantum algorithms for this problem are memory-intensive, and the costs of quantum memory may be very high. The quantum circuit model implies a linear cost for random access, which annihilates the exponential advantage of the previous quantum collision-finding algorithms over Grover's algorithm or classical van Oorschot-Wiener. Assuming that quantum memory is costly to access but free to maintain, we provide new quantum algorithms for the golden collision problem with high memory requirements but low gate costs. Under the assumption of a two-dimensional connectivity layout, we provide better quantum parallelization methods for generic and golden collision finding. This lowers the quantum security of the golden collision and meet-in-the-middle problems, including SIKE.
一个用于减少量子预言机开销的框架，与 Grover 算法一起使用，并应用于 SIKE 的密码分析
影响因子：
1.2
作者：
Biasse, Jean-François;Pring, Benjamin
通讯作者：
Pring, Benjamin