中島 克也
現在のインターネットやクラウドには様々な機密性の高い情報がやり取りされている。これらの情報を秘匿にするための基盤技術が暗号技術（公開鍵暗号，共通鍵暗号，デジタル署名など）である。公開鍵暗号やデジタル署名の中でも現在広く使われているのが、素因数分解問題や離散対数問題の困難性に基づく暗号アルゴリズム(DSA など) である．近年，これらの問題を効率良く解き，暗号技術の安全性をに対して脅威となりうる新たな計算技術として，量子コンピュータの研究が進展している. 量子コンピュータを用いても解読や偽造ができないような暗号技術として様々な耐量子暗号技術の研究・開発・標準化が進んでいる．中でも応用範囲が広く安全性が高いのが格子暗号である．しかし, この新しい暗号技術の実応用に安全性を評価するためには, 格子に対する効率的な攻撃アルゴリズムの研究が不可欠だ．格子暗号の安全性は，格子の最も短い非零のベクトルを見つける問題である最短ベクトル問題の困難性に安全性の根拠を置いている．SVP に対してこれまで様々な格子基底簡約アルゴリズムが提案されており，代表的なアルゴリズムとしてLLL(Lenstra-Lenstra-Lovasz) 簡約アルゴリズムやBKZ(block Korkin-Zolotarev) 簡約アルゴリズムが挙げられる. 格子基底簡約アルゴリズムの中で，BKZ 簡約アルゴリズムは計算量を無視すればもっとも強力なアルゴリズムである．BKZ 簡約アルゴリズムの計算量は，サブルーチンであるENUM と呼ばれる格子点の列挙探索アルゴリズムの計算量に大きく依存する．本研究では,SCIS 2021 で山村らが発表した，入力基底の順序変更によってENUM の計算量を削減するメカニズムを改善した．特に，入力基底を更新を繰り返すことによるENUM への影響を分析し, 様々なBKZ アルゴリズムに適用して, その効果を考察した．
