2024-06-21T14:37:50Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:001955262024-03-29T05:26:34Z01164:02592:09674:09784
Improved Quantum Multicollision-Finding AlgorithmMulticollision発見問題を解く量子アルゴリズムenghttp://id.nii.ac.jp/1001/00195437/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=195526&item_no=1&attribute_id=1&file_no=1Copyright (c) 2019 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG.日本電信電話株式会社NTTセキユアプラツトフオーム研究所／名古屋大学大学院工学研究科情報・通信工学専攻日本電信電話株式会社NTTセキユアプラツトフオーム研究所日本電信電話株式会社NTTコミュニケーション科学基礎研究所日本電信電話株式会社NTTセキユアプラツトフオーム研究所細山田, 光倫佐々木, 悠谷, 誠一郎草川, 恵太The current paper improves the number of queries of the previous quantum multi-collision finding algo rithms presented by Hosoyamada et al. at Asiacrypt 2017. Let an l -collision be a tuple of l distinct inputs that result in the same output of a target function. In cryptology, it is important to study how many queries are required to find l-collisions for random functions of which domains are larger than ranges. The previous algorithm finds an l -collision for a random function by recursively calling the algorithm for finding ( l — 1)-collisions, and it achieves the average quantum query complexity of O (N (3l-1 -1) / (2･3l-1)),where N is the range size of target functions. The new algorithm removes the redundancy of the previous recursive algorithm so that different recursive calls can share a part of computations. The new algorithm finds an l-collision for random functions with the average quantum query complexity of O (N(2l-1) / (2l-1)), which improves the previous bound for all l ≧ 3 ( the new and previous algorithms achieve the optimal bound for l = 2). More generally, the new algorithm achieves the average quantum query complexity of O ( C3/2N N 2l-1-1/2l-1 ) for a random function f: X→Y such that The current paper improves the number of queries of the previous quantum multi-collision finding algo rithms presented by Hosoyamada et al. at Asiacrypt 2017. Let an l -collision be a tuple of l distinct inputs that result in the same output of a target function. In cryptology, it is important to study how many queries are required to find l-collisions for random functions of which domains are larger than ranges. The previous algorithm finds an l -collision for a random function by recursively calling the algorithm for finding ( l — 1)-collisions, and it achieves the average quantum query complexity of O (N (3l-1 -1) / (2･3l-1)),where N is the range size of target functions. The new algorithm removes the redundancy of the previous recursive algorithm so that different recursive calls can share a part of computations. The new algorithm finds an l-collision for random functions with the average quantum query complexity of O (N(2l-1) / (2l-1)), which improves the previous bound for all l ≧ 3 ( the new and previous algorithms achieve the optimal bound for l = 2). More generally, the new algorithm achieves the average quantum query complexity of O ( C3/2N N 2l-1-1/2l-1 ) for a random function f: X→Y such that AN1009593X研究報告アルゴリズム（AL）2019-AL-1739172019-05-032188-85662019-04-16