http://swrc.ontoware.org/ontology#TechnicalReport
Improved Quantum Multicollision-Finding Algorithm
en
日本電信電話株式会社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-173
9
1-7
2019-05-03
2188-8566