出生日限界より小さい確率を持つ微分軌跡を用いた量子コンピュータによるハッシュ衝突の発見【JST・京大機械翻訳】

Hosoyamada Akinori; Hosoyamada Akinori; Sasaki Yu

文献

J-GLOBAL ID：202002279372034699 整理番号：20A1196434

出生日限界より小さい確率を持つ微分軌跡を用いた量子コンピュータによるハッシュ衝突の発見【JST・京大機械翻訳】

Finding Hash Collisions with Quantum Computers by Using Differential Trails with Smaller Probability than Birthday Bound

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=20A1196434&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=20A1196434&from=J-GLOBAL&jstjournalNo=H0078D") }}

著者 (3件)： , ,
資料名：
巻： 12106 ページ： 249-279 発行年： 2020年
JST資料番号： H0078D ISSN： 0302-9743 資料種別：会議録 (C)
記事区分：原著論文発行国：ドイツ (DEU) 言語：英語 (EN)

本論文では,これまであまり注目されていなかった,具体的なハッシュ関数上の専用の量子衝突攻撃に光を当てた。古典的な設定において,nビットハッシュ関数の衝突を見つけるための一般的複雑性は[数式:原文を参照]であり,したがって,リバウンド攻撃のような微分暗号解析に基づく古典的衝突攻撃は,[数式:原文を参照]より高い確率を有する微分軌跡を構築する。同じ類推により,BHTアルゴリズムのような一般的な量子アルゴリズムは複雑性[数式:原文を参照]との衝突を見出す。量子アルゴリズムを用いて,確率pを有する微分トレイルを満たす一対のメッセージを,複雑性[数式:原文を参照]を用いて生成することができた。したがって,量子設定において,古典的設定において利用できない[数式:原文を参照]までの確率を有するいくつかの微分軌跡が,量子設定における衝突攻撃を実装するために利用される可能性がある。特に,攻撃されたラウンドの数は増加する可能性がある。本論文では,2つの国際ハッシュ関数標準を攻撃した。AES-MMOに対して,確率[数式:原文を参照]を用いて7ラウンド微分トレイルを提示し,それを用いてリバウンド攻撃の量子バージョンとの衝突を見出し,一方,6ラウンドのみが古典的設定において攻撃され得ることを示した。Whirプールに対して,筆者らは,出生日境界よりも高い複雑さを持つ古典的リバウンド識別器からの6ラウンド微分トレールに基づく衝突攻撃を実装した。これは,1によって5ラウンドに関して最良の古典的アタックを改良した。また,これらの軌跡が著者らのアプローチにおいて最適であることを示した。結果は2つの重要な意味を持つ。第一に,古典的に安全なハッシュ関数が量子敵に対して安全なままであるという共通の信念が存在すると思われる。実際に,NISTポスト量子競合におけるいくつかの第二ラウンド候補は,量子安全なものとして,既存のハッシュ関数,すなわちSHA-3を使用する。著者らの結果はこの一般的信念を証明した。2番目に,著者らの観察は,微分トレイル探索が確率[数式:原文を参照]で停止しなければならないが,[数式:原文を参照]まで考慮すべきであることを示唆する。したがって,それは以前の差動的なトレール探索活動を再訪問するのに価値がある。Copyright International Association for Cryptologic Research 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

, , , , , ,
, , , 【Automatic Indexing@JST】

著者キーワード (8件)： , , , , , , ,

符号理論 , データ保護

, , , , , , ,

前のページに戻る