情報
IMIシリーズ：進化する産業数学 第3巻
格子暗号解読のための数学的基礎格子基底簡約アルゴリズム入門
次世代暗号理論の最有力！
本書では、ポスト量子暗号の最右翼と目される格子暗号の数学とその実装方法について解説する。
現代の情報社会を支えるRSA暗号や楕円曲線暗号は、ノイマン型コンピュータの計算困難性を利用している。しかしこれらは、量子コンピュータにより簡単に解読されることが分かっており、ポスト量子暗号の実現が叫ばれている。
格子暗号は「格子問題」と呼ばれる、量子コンピュータでも解き方が分かっていない問題を基礎とする。本書はその数学的性質のほか、格子問題を解くための「格子基底簡約アルゴリズム」について紹介していく。
電子書籍¥4,400 小売希望価格（税込）
紙の書籍¥4,400定価（税込）
基本情報
| 発売日 | 2019年9月24日 |
|---|---|
| 本体価格 | 4,000円 |
| ページ数 | 216 ページ ※印刷物 |
| サイズ | B5 変形 |
| ISBN | 9784764905986 |
| ジャンル | 情報 |
| タグ | 暗号・セキュリティ |
| 電子書籍形式 | 固定型 |
主要目次
1 格子の数学的基礎
1.1 格子
1.1.1 格子と基底
1.1.2 格子の体積
1.1.3 部分格子
1.2 格子と Gram-Schmidtの直交化
1.2.1 格子基底に対する Gram-Schmidtの直交化 (GSO)
1.2.2 射影格子
1.3 格子の離散性
1.3.1 格子の離散性とその性質
1.3.2 補足：離散加法部分群における基底の存在性
1.4 格子の逐次最小と逐次最小ベクトル
1.4.1 格子の逐次最小
1.4.2 格子の逐次最小ベクトルと逐次最小基底
1.5 Minkowskiの定理と Hermiteの定数
1.5.1 Minkowskiの定理
1.5.2 Hermiteの定数と Hermiteの不等式
1.5.3 補足：4次元以下の格子における逐次最小基底の存在性
1.6 補足：双対格子とMordellの不等式の紹介
1.6.1 双対格子とその性質
1.6.2 Mordellの不等式
1.7 格子問題の紹介
2 LLL基底簡約とその改良
2.1 2次元格子における SVP解法
2.1.1 Lagrange簡約基底とその性質
2.1.2 Lagrange基底簡約アルゴリズム
2.1.3 Lagrange基底簡約アルゴリズムと Euclidの互除法
2.2 サイズ基底簡約
2.3 LLL基底簡約
2.3.1 LLL簡約基底とその性質
2.3.2 LLL基底簡約アルゴリズム
2.3.3 LLL基底簡約における効率的な GSO更新
2.4 DeepLLL基底簡約
2.4.1 DeepLLL基底簡約アルゴリズム
2.4.2 DeepLLL基底簡約における効率的な GSO更新
2.5 一次従属ベクトルに対する LLL基底簡約
2.5.1 MLLL基底簡約における GSO情報の計算
2.5.2 MLLL基底簡約アルゴリズム
3 さらなる格子基底簡約アルゴリズム
3.1 HKZ簡約基底とその性質
3.2 格子上の最短ベクトルの数え上げ
3.2.1 最短ベクトルの数え上げ原理
3.2.2 最短ベクトルの数え上げアルゴリズム
3.2.3 数え上げアルゴリズムの計算量
3.3 BKZ基底簡約アルゴリズム
3.3.1 BKZ簡約基底とその性質
3.3.2 BKZ基底簡約アルゴリズム
3.3.3 BKZ基底簡約で利用可能な効率的な GSO更新公式
3.4 スライド基底簡約アルゴリズム
3.4.1 Mordell簡約基底とその性質
3.4.2 ブロックMordell簡約基底とその性質
3.4.3 スライド基底簡約アルゴリズム
3.5 SVPチャレンジにおける計算機実験
4 ランダムサンプリングアルゴリズムとその解析
4.1 本章の道案内
4.2 解析のための準備
4.2.1 集合と確率変数
4.2.2 積一定条件における和の最小化
4.3 ランダムサンプリングアルゴリズム
4.3.1 ランダムサンプリングアルゴリズムの定義
4.3.2 サンプリング基底簡約アルゴリズム
4.4 ランダムサンプリングアルゴリズムの解析
4.4.1 解析で用いられる仮定
4.4.2 成功確率の定義
4.4.3 一様分布仮定と平均値中央値仮定からの帰結
4.4.4 定理 4.4.3の応用
4.4.5 幾何級数仮定を用いた解析
4.4.6 定理 4.4.5の発展と数値例
4.5 ランダムサンプリングアルゴリズムの実験例
4.5.1 関連研究と発展的な課題
4.6 Small Vector Sum 問題 (VSSP)とその解法アルゴリズム
4.6.1 VSSPの定義
4.6.2 t = 1の場合の VSSPの解法
4.6.3 リストのマージアルゴリズム
4.6.4 一般の t ≥ 2に対する VSSPの解法
4.7 VSSP解法アルゴリズムとランダムサンプリングアルゴリズムとの組合せ
4.7.1 アルゴリズムが出力するベクトルの長さ
4.7.2 アルゴリズムの計算時間
5 近似版CVP解法とLWE問題への適用
5.1 近似版の CVPに対する解法
5.1.1 Babaiの最近平面アルゴリズム
5.1.2 目標ベクトルに近い格子ベクトルの数え上げ
5.1.3 埋め込み法
5.2 LWE問題と代表的な求解法の紹介
5.2.1 LLWE問題の紹介と定式化
5.2.2 q-ary格子
5.2.3 判定 LWE問題に対する求解法
5.2.4 探索 LWE問題に対する求解法
5.2.5 LWEチャレンジに対する計算機実験