An Efficient Quantum Multi-Collision Search Algorithm

IEEE Access

Jian Zou¹  Yongyang Liu¹  Le Dong² 

[1] Department of Mathematics and Computer Science, Fuzhou University, Fuzhou, China;Henan Engineering Laboratory for Big Data Statistical Analysis and Optimal Control, Henan Normal University, Xinxiang, China;

关键词: Grover's algorithm;    k-collision;    post-quantum cryptography;    symmetric cryptography;   

DOI  :  10.1109/ACCESS.2020.3028736

来源: DOAJ

【 摘 要 】

In this article, we propose an efficient quantum k-collision search algorithm with low quantum memory O(n). The previous quantum k-collision algorithms can not be converted into a low quantum memory k-collision algorithm directly, because the time complexity of the converted algorithm is larger than the basic k-collision algorithm. To solve this problem, we shall not only divide our low memory quantum k-collision algorithm into several subroutines, but also need to achieve some balances between these subrou tines. The time complexity of our k-collision search algorithm is O(2(2^k-2)n/2^k+1-3 ), and the classical memory and quantum memory complexities are O(2(2^k-2)n/2^k+1-3 ) and O(n) respectively. In addition, we propose an efficient k-claw search algorithm, which can output a k-claw with O(n) qubits. Given 2^s quantum processors, we can construct our quantum k-collision and k-claw parallel algorithm with the time of O(2(2^k-2)n-(2^k+1-2^k-1-3)s/2^k+1-3 )while the classical memory and quantum memory complexities are O(2(2^k-1-1)n+s-2^k-2/2^k+1-3 ) and O(n), respectively.

【 授权许可】

Unknown