田川 雄大
米国国立標準技術研究所による耐量子計算機暗号の標準化プロジェクトにより格子暗号は大きな注目を集めている．Middle-Product Learning with Errors (MP-LWE) 問題は格子暗号の安全性仮定に用いられる問題の1 つであり，Polynomial LWE (PLWE) 問題の安全性が特定の多項式に依存するというセキュリティ上のリスクを軽減することができる．MP-LWE 問題はLWE 問題の特別な場合と見なすことができ，LWE問題に対する手法を適用してMP-LWE 問題を攻撃する手法が提案されている．1 つはPrimal Attack を適用する手法，もう1 つはKannan の埋め込み法を適用する手法である．本研究ではMP-LWE 問題に対する新たな攻撃手法を提案する．1 つ目はPrimal Attack を適用する手法を改良した重み付きPrimal Attack である．実験の結果，多項式を2 倍したものをエラーとして用いるMP-LWE 問題は重み付きPrimal Attackに対して脆弱性を持つことが示唆された．2 つ目はMP-LWE 問題を脆弱なPLWE 問題に帰着する手法である．この攻撃手法は次元の多項式時間で実行することができる．また，MP-LWE 問題が脆弱なPLWE 問題に帰着できる条件を示し，条件を満たすMP-LWE 問題が解読できることを実験により確認した．
