筒井 大揮
現在広く普及している RSA 暗号や楕円曲線暗号は, 大規模な量子計算機によって多項式時間で解読されることが知られている. そのため, 耐量子計算機暗号の有力な候補として, 格子理論に基づく格子暗号の研究が盛んに行われている. 格子暗号の安全性の根拠となる数学的計算困難な問題の一つに, Ring Learning
with Errors (Ring-LWE) 問題と呼ばれる代数体の整数環上における誤差付きの多元連立一次方程式を解く問題がある. これを一般の整環へと拡張した問題が Order Learning with Errors (Order-LWE) 問題である. Ring-LWE では代数体として円分体がよく利用されるが, 新たな攻撃の発見により, 現在利用され
ている円分体に基づく Ring-LWE が脆弱になる可能性がある. そのため, 円分体以外の代数体を利用した Ring-LWE の安全性解析は重要である. 格子暗号を実装する際, 代数体の要素をベクトルとして扱うために環の整基底を特定する必要がある. しかし, 一般的に高次の代数体において整数環の整基底を計算するには膨大な計算を要する. 一方, 整環の整基底は比較的容易に構成可能である. そのため, 暗号実装が容易である Order-LWE の解析は重要である. 暗号を実装する際には, 計算効率の観点から, エラーやシークレットを公開伴と同じ環で定義し, そのことを双対を用いない形式と呼ぶ. 双対を用いない形式の Order-LWE に対する解析は行われていない. そこで, 本研究では, 代表的な格子攻撃手法である Kannan の埋め込み法および双対攻撃を用い, 様々な整環における双対を用いない形式の Order-LWE 問題に対して困難性を評価および解析することを目的とする.
