高機能次世代暗号の大規模解読実験による安全性評価

点击翻译按钮获取中文摘要

高機能な次世代暗号の安全性評価では，安全性根拠となる数学的問題の困難性の解析が重要な研究課題である．本研究では，次世代暗号Giophantusに対して，ハイブリッド攻撃の安全性評価を目的とし，Giophantusが提案した暗号パラメータの強度評価を行った．具体的には，格子簡約アルゴリズムと中間一致攻撃を組み合わせたHowgrave-Grahamのハイブリッド攻撃に基づき，格子最短ベクトル問題(SVP)の解析に対するハイブリッド攻撃のシミュレータを構成した．本シミュレータでは，格子簡約アルゴリズムの計算量と中間一致攻撃の計算量のトレードオフを考慮することが可能となった．本成果は，ACM主催の国際会議AsiaPKC 2020に採録されている．格子暗号NewHopeは米国標準技術研究所NISTが進める耐量子暗号標準化プロジェクトにおいて有力な候補の１つである．NewHopeに対する鍵不一致攻撃はBauerらによって国際会議CT-RSA 2019において初めて発表され，更にQinらにより国際会議ESORICS 2019にてBauerらの鍵不一致攻撃が改良された．本研究では，攻撃者がサーバに送信するクエリの生成方法に改良を施し，BauerらやQinらの攻撃方法では復元が不可能であった秘密鍵に対しても攻撃可能とした．そして，秘密鍵となる多項式の係数の決定的な判定条件を考察することにより，秘密鍵の復元成功率を上昇させたと共に，Qinらの攻撃における秘密鍵の検索範囲をクエリ数の増加なしで拡張することに成功した．本成果は，オーストラリアのPerthで開催される国際会議ACISP 2020に採録されている．