格子基底簡約アルゴリズムの改良とRSA暗号安全性解析への応用

従来は公開鍵暗号方式の主流として、RSA暗号と楕円曲線暗号が広く使用されてきたが、これらの暗号方式は量子計算機によって破られることが示されている。昨今、量子計算機の実現の可能性が高まりを見せるにつれて、RSA暗号と楕円曲線暗号の代替となる暗号方式の必要性がより強く指摘されるようになってきた。この状況を受けて、2016年に米国標準研究所（NIST）が耐量子計算機暗号の公募を開始し、2022年に4つの方式を代替暗号の標準として選定した。4つの方式のうち3つが格子暗号で、今後の格子暗号の標準化・実用化に向けて、格子暗号の安全性評価が一層重要である。格子基底簡約アルゴリズムは格子暗号の安全性評価において必要不可欠となる道具であり、適切な安全性評価のためには格子基底簡約アルゴリズムの高速化が重要である。格子基底簡約アルゴリズムにおいては、基底簡約の処理を進行させるために多数の格子短ベクトルを生成する必要がある。前年度までの研究において、短ベクトルを求めるために、進化的計算手法により短ベクトルを求めるアルゴリズムを改良し、計算機実験によって既存の手法より高速に短ベクトルが求まることを確認した。当該年度においては、改良型アルゴリズムの探索空間生成初期化法の改良、探索空間構成法の拡張、及び、基底更新の手法の改良に着手し、これらの改良・拡張の効果を検証するための計算機実験を実施した。また、進化的手法におけるサブルーチンのそれぞれを分析して、対応する格子空間における演算との対応を明らかにした。

従来は公開鍵暗号方式の主流として、RSA暗号と楕円曲線暗号が広く使用されてきたが、これらの暗号方式は量子計算機によって破られることが示されている。昨今、量子計算機の実現の可能性が高まりを見せるにつれて、RSA暗号と楕円曲線暗号の代替となる暗号方式の必要性がより強く指摘されるようになってきた。この状況を受けて、2016年に米国標準研究所（NIST）が耐量子計算機暗号の公募を開始し、2022年に4つの方式を代替暗号の標準として選定した。4つの方式のうち3つが格子暗号で、今後の格子暗号の標準化・実用化に向けて、格子暗号の安全性評価が一層重要である。格子基底簡約アルゴリズムは格子暗号の安全性評価において必要不可欠となる道具であり、適切な安全性評価のためには格子基底簡約アルゴリズムの高速化が重要である。格子基底簡約アルゴリズムにおいては、基底簡約の処理を進行させるために多数の格子短ベクトルを生成する必要がある。前年度までの研究において、短ベクトルを求めるために、進化的計算手法により短ベクトルを求めるアルゴリズムを改良し、計算機実験によって既存の手法より高速に短ベクトルが求まることを確認した。当該年度においては、改良型アルゴリズムの探索空間生成初期化法の改良、探索空間構成法の拡張、及び、基底更新の手法の改良に着手し、これらの改良・拡張の効果を検証するための計算機実験を実施した。また、進化的手法におけるサブルーチンのそれぞれを分析して、対応する格子空間における演算との対応を明らかにした。