情報処理学会 第87回全国大会

2ZD-08
格子攻撃によるModule-LWE問題に対する安全性解析の再考
○田村昂輔,宮地充子,奥村伸也(阪大)
格子暗号の一種であるModule-LWE(MLWE)はNIST-PQCで標準化が決定したアルゴリズムにおいて2冪の円分体上で定義されたものが利用されている.既存研究では2冪の円分体の部分体上で定義された階数2のMLWEについて,Kannanの埋め込み法とProgressive-BKZアルゴリズムを用いて攻撃が行われており,部分体を利用したほうが攻撃の成功率が低くなる可能性があることが分っている.そこで,本研究では2冪の円分体とその部分体に加えて,素数次の円分体や3冪の円分体上で定義したMLWEに対して階数を変化させながらsagemathで実装されているBKZアルゴリズムで攻撃を行い,それらの代数体の安全性と階数の変化による影響を検証することを目的とする.