Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part V
Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part V
复制标题
密码学进展 - EUROCRYPT 2023 - 第 42 届密码技术理论与应用国际会议，法国里昂，2023 年 4 月 23-27 日，会议记录，第五部分
DOI：
10.1007/978-3-031-30589-4_8
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Bonnetain X
中科院分区：
文献类型：
--
作者：
Bonnetain X
给定一个带有区域和共域的随机函数，碰撞是一对具有相同图像的截然不同的输入。碰撞发现是密码分析中普遍存在的问题，已有经典算法和量子算法对其进行了较好的研究。事实上，这个问题的量子查询复杂性是众所周知的，匹配算法对于任何m值都是已知的。当人们寻找公式冲突对时，情况就变得不同了。这里，对于碰撞，Liu和Zhandry(Eurocrypt，2019)给出了一个查询下界。当存在许多冲突时，匹配算法是已知的，但仅用于Fm的相对较小的值。在这篇文章中，我们改进了这个问题的算法，特别是在满足下界的情况下，扩展了可允许参数的范围。我们的新方法依赖于可能独立感兴趣的链式量子漫游算法。它允许提取MNRS式量子行走的多个解，而不必完全重新计算：在找到并输出一个解后，当前状态被重用作为另一次行走的初始状态。作为应用，我们改进了求解最短向量问题(SVP)的量子筛选算法，其复杂性取代了以前的算法。
Given a random functionfwith domainand codomain, with, a collision offis a pair of distinct inputs with the same image. Collision finding is an ubiquitous problem in cryptanalysis, and it has been well studied using both classical and quantum algorithms. Indeed, the quantum query complexity of the problem is well known to be, and matching algorithms are known for any value ofm.The situation becomes different when one is looking formultiplecollision pairs. Here, forcollisions, a query lower bound ofwas shown by Liu and Zhandry (EUROCRYPT 2019). A matching algorithm is known, but only for relatively small values ofm, when many collisions exist. In this paper, we improve the algorithms for this problem and, in particular, extend the range of admissible parameters where the lower bound is met.Our new method relies on achained quantum walkalgorithm, which might be of independent interest. It allows to extract multiple solutions of an MNRS-style quantum walk, without having to recompute it entirely: after finding and outputting a solution, the current state is reused as the initial state of another walk.As an application, we improve the quantum sieving algorithms for the shortest vector problem (SVP), with a complexity ofinstead of the previous.