田村 昂輔
現代の情報社会ではRSA暗号や楕円曲線暗号が暗号技術の根幹を担っている. しかし,着実に開発が進め られている大規模な量子コンピュータによってこれらの暗号は容易に解読できるということが証明されてい る. そこで,大規模な量子コンピュータを用いても解読が困難であるとされている格子暗号が注目されている. 実際に格子暗号を数学的に解くことができるアルゴリズムは発見されておらず,NIST-PQCで標準化が決定 したCRYSTALS-KYBERとCRYSTALS-Dilithiumという2つのアルゴリズムではModule-LWE(Lerning with Errors) 問題という格子問題が利用されている. しかし, 安全性の根拠が証明されたというわけではな いため様々な手法により安全性の解析・検証が行われている. Module-LWE問題は,Ring-LWE問題のサン プルaとシークレットsを階数dのベクトルに一般化したものである. 既存研究のModule-LWE問題の解 析では, 格子問題で利用されるKannanの埋め込み法を2冪の円分体上のRing-LWE問題に対して拡張し, さらに2冪の円分体の部分体や他の円分体上のRing-LWE問題に対して拡張した手法による安全性検証が 行われている,また,2冪の円分体やその部分体上で定義されたModule-LWE問題の解析では,BKZ基底簡 約アルゴリズムとは異なる,ブロックサイズを変化させながら攻撃を行うProgressive-BKZ基底簡約アルゴ リズムによる安全性検証が行われており,Kannanの埋め込み法は2冪の円分体上のModule-LWE問題に 対しても拡張されている. そこで本研究では以下の2つを目的として実験を行った.Kannanの埋め込み法 の拡張を様々な代数体上のModule-LWE 問題に対して適用可能にする. 次に, 様々な代数体上で定義した Module-LWE問題に対して, 拡張されたKannanの埋め込み法をModule-LWE問題の階数を変化させなが ら攻撃することで,Module-LWE問題の階数や代数体の違いによる安全性を検証する.
