Multicollision発見問題を解く量子アルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2019-05-03
• タイトル: Multicollision発見問題を解く量子アルゴリズム
• タイトル / 言語: en
• タイトル: Improved Quantum Multicollision-Finding Algorithm
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 日本電信電話株式会社NTTセキユアプラツトフオーム研究所／名古屋大学大学院工学研究科情報・通信工学専攻
• 著者所属: 日本電信電話株式会社NTTセキユアプラツトフオーム研究所
• 著者所属: 日本電信電話株式会社NTTコミュニケーション科学基礎研究所
• 著者所属: 日本電信電話株式会社NTTセキユアプラツトフオーム研究所
• 著者所属(英): en
• 著者所属(英): NTT Secure Platform Laboratories, NTT Corporation / Department of Information and Communication Engineering Graduate School of Engineering, Nagoya University
• 著者所属(英): en
• 著者所属(英): NTT Secure Platform Laboratories, NTT Corporation
• 著者所属(英): en
• 著者所属(英): NTT Communication Science Laboratories, NTT Corporation
• 著者所属(英): en
• 著者所属(英): NTT Secure Platform Laboratories, NTT Corporation.
• 著者名: 細山田, 光倫; 佐々木, 悠; 谷, 誠一郎; 草川, 恵太
• 著者名(英): Akinori, Hosoyamada; Yu, Sasaki; Seiichiro, Tani; Keita, Xagawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2019-AL-173, 号 9, p. 1-7, 発行日 2019-05-03
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会