目次
開催案内
格子アルゴリズムと暗号解読への応用
日時
2024年11月21日（木）16:45〜18:15
開催形式
対面(北部構内)とオンライン(Zoom)のハイブリッド
参加登録 https://forms.gle/L3WMKkBmYfgEFU9e7
登録されたアドレスに教室の場所とZoomの接続情報を送付いたします。
講師
安田 雅哉 氏（立教大学理学研究科数学専攻 教授）
概要
格子暗号は、量子計算機を利用した暗号解読に耐性を持つ耐量子計算機暗号技術として注目されている。本講演では、格子基底簡約などの格子アルゴリズムを紹介すると共に、LWEやNTRUなどの格子暗号方式の解読への応用について説明する。
備考
◎問い合わせ先：itami.masato.7u ＊ kyoto-u.ac.jp（＊を@に変えてください）
活動報告
立教大学の安田雅哉さんに「格子アルゴリズムと暗号解読への応用」というタイトルで講演していただきました。
講演は格子の説明から始まりました。格子とは、一次独立なベクトルの整数係数の線形結合全体の集合のことです。格子上の最短な非零ベクトルを見つける問題のことを最短ベクトル問題(SVP)と呼びます。SVPはNP困難で、高次元格子上のSVPを効率的に解く方法は現在でも知られていません。SVPやそれに類する問題は格子問題と呼ばれており、耐量子計算機暗号の一つである格子暗号の安全性を支えているため、格子問題を解く格子アルゴリズムの研究は重要なテーマとなっているようです。
次に、格子アルゴリズムについて説明していただきました。低次元格子上のSVPは求解法が知られています。そこで、2次元格子上のSVPの求解法であり、Euclidの互除法に類似しているLagrange基底簡約アルゴリズムについて解説していだき、具体的なSageのコードや、その挙動も見せていただきました。続いて、高次元格子上の近似版SVPを効率的に解く手法として知られているLLL基底簡約アルゴリズムについて説明していただきました。これは、Gram-Schimidtの直交化から得られる情報を用いたサイズ基底簡約と、Lovász条件を満たすように基底ベクトルの順番を入れ替える操作から構成されています。セミナーでは、LLL基底簡約アルゴリズムのSageによる実装と、その挙動も見せていただきました。さらに、40次元程度までのSVPを解ける最短ベクトルの数え上げアルゴリズムと、LLL基底簡約アルゴリズムを組み合わせることで、LLL基底簡約アルゴリズムよりも短い格子ベクトルを探索可能にしたBKZ基底簡約アルゴリズムについても解説していただき、Sageのコードと挙動を見せていただきました。BKZ基底簡約アルゴリズムは、格子暗号の安全性解析でも頻繁に登場する強力な手法とのことでした。
最後に、耐量子計算機暗号だけではなく、完全準同型暗号を含む様々な格子暗号方式の安全性を支えているLWE問題の求解について説明していただきました。LWE問題とは、有限体上の連立線形近似方程式を解く問題のことです。q-ary格子を考えるとLWE問題は特殊な場合の最近ベクトル問題(CVP)に帰着し、さらにKannanの埋め込み法によってCVPを特殊な場合のSVPに帰着することができるため、LWE問題の求解に先述の格子アルゴリズムを使うことができるとのことでした。
講演中も講演後も多くの質問が出て、安田さんが研究されていたDeepLLL基底簡約の亜種などに関しても活発な議論が行われました。 （文責：伊丹將人）