Miyaji Laboratory

近年，古典計算機では実現しえない規模の並列計算に特化している量子コンピュータの研究が進んでおり，量子コンピュータを用いることで素因数分解問題や離散対数問題を多項式時間で解くことができるとされている．RSA 暗号や楕円曲線暗号など現在広く用いられる公開鍵暗号方式暗号は上記のような計算問題をベースとするため，現実的な時間で解読される可能性がある．そのため，量子コンピュータでの解読にも耐えうる耐量子計算機暗号（PQC）の需要が高まっており，なかでも，米国国立標準技術研究所（NIST）のPQC 標準化プロジェクトにおいて最も多く選出された格子暗号が注目されている．一般に，格子暗号に基づく暗号システムでは，計算の高速化・鍵サイズ縮小のためにイデアルの性質をもつイデアル格子が利用されている．本研究では，格子暗号の安全性の根拠である最短ベクトル問題(SVP) について検討する．現在最も高速にSVP を解読するアルゴリズムの1 つであるSieve アルゴリズムを改良することで，SVP の計算困難性の解析を行う．特に，格子ベクトルに対する乗算も同一格子上の格子ベクトルとなるイデアル格子の性質を利用することで，Sieve アルゴリズムの課題である空間計算量の削減を図る．