概要

大規模な量子計算機が実現できると、現在利用されている RSA 暗号や楕円曲線暗号等の公開鍵暗号は解読可能となる。このため、量子計算機を用いても解読が困難となる暗号(耐量子暗号)方式の研究が活発になってきている。
耐量子暗号の候補として、SAC2017 において秋山らは不定方程式暗号Giophantusを発表した。Giophantusは環 Fq[t]/(t^n − 1) 上の不定方程式の最小解を求める問題を安全性の根拠とする。LWE 問題の一種であるIE Ring-LWE(Indeterminate Equation version of Ring-Learning With Error) 問題が識別困難であれば、Giophantus 暗号も IND-CPA 安全である。
SAC2019 において、代入攻撃と格子攻撃を組み合わせることにより、IE Ring-LWE 問題が容易に解かれてしまうことが室井、奥村、宮地らにより示された。このため、秋山らは環を Fq[t]/(t^n + 1) に変換したGiophantus+ を提案した。
本研究では、不定方程式の項集合や次数などのパラメータを変えて実験を行うことで、Giophantus+ に対する最適な攻撃手法を検討する。

Top