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

通过高性能下一代密码大规模解码实验进行安全评估

基本信息

批准号：
19F19378
负责人：
高木剛
金额：
$ 1.47万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2019
资助国家：
日本
起止时间：
2019-11-08 至 2022-03-31
项目状态：
已结题

项目摘要

高機能な次世代暗号の安全性評価では，安全性根拠となる数学的問題の困難性の解析が重要な研究課題である．本研究では，次世代暗号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に採録されている．

在高性能下一代密码的安全评估中，一个重要的研究课题是对为安全提供基础的数学问题的难度分析。在本研究中，我们评估了 Giophantus 提出的密码参数的强度，旨在评估针对下一代密码 Giophantus 的混合攻击的安全性。具体来说，我们构建了一个混合攻击模拟器，用于分析基于 Howgrave-Graham 混合攻击的格最短向量问题（SVP），该攻击结合了格约化算法和中间匹配攻击。该模拟器使得可以考虑格简化算法的计算复杂性和中间匹配攻击的计算复杂性之间的权衡。该成果已被ACM主办的国际会议AsiaPKC 2020接受。格密码 NewHope 是美国国家标准与技术研究院 (NIST) 推动的抗量子密码学标准化项目的主要候选者之一。针对NewHope的密钥错配攻击由Bauer等人在国际会议CT-RSA 2019上首次公布，Qin等人在国际会议ESORICS 2019上进一步改进了Bauer等人的密钥错配攻击。在这项研究中，我们改进了生成攻击者发送到服务器的查询的方法，使得使用 Bauer 等人和qin 等人的攻击方法无法恢复的私钥成为可能。通过考虑作为密钥的多项式系数的决定性准则，在不增加查询次数的情况下，提高了密钥恢复的成功率，扩大了Qin等人攻击中密钥的搜索范围。我们成功地扩展了它。该成果已在澳大利亚珀斯举行的国际会议 ACISP 2020 上被接受。