# A Hybrid Lattice Basis Reduction and Quantum Search Attack on LWE

{%pdf https://eprint.iacr.org/2017/221.pdf %}

この記事は[情報セキュリティ系論文紹介 Advent Calendar 2017](https://adventar.org/calendars/2295)の11日目の記事である。

- 論文(https://eprint.iacr.org/2017/221.pdf)

なお、本稿では手法の計算量に関する詳細な解説は行わないため、その辺の詳細は元論文を参照されたし。

## TL;DR

この論文は、LWE格子暗号の安全性を保証するLWE問題(Learning with Error Problem)についての新しい攻撃手法に関する論文である。LWE格子暗号についての大まかな説明は例えば以下の記事にある。

- http://inaz2.hatenablog.com/entry/2017/05/27/003343

本手法の概略は以下のとおりである。

- LWE問題を格子に関する別の問題である**最短ベクトル問題**(**Shortest Vector Problem, SVP**)に帰着する。
- SVPを**Bounded Distance Decoding Problem**(**BDD**)という問題(これも格子に関する問題である)に帰着する。
- BDDとは**格子の基底**と**格子に近いベクトル**(これを**標的ベクトル**と呼ぶ)が与えられ、この標的ベクトルに最も近い格子点を求める問題である
- 今回の手法ではBDDに帰着した後、その標的ベクトルを推測し、それに対してBDD問題を解くことで秘密を求める。
- この標的ベクトルを推測するために、量子アルゴリズムであるGroverの探索アルゴリズムを修正したものを用いる。

## 背景
近年、量子計算機を用いても簡単に解けない暗号(耐量子暗号, Post-Quantum Cryptography)への注目が高まっている。

格子に関する問題を利用した暗号は耐量子暗号の中でも近年活発に研究されて来ており、その問題への解法の研究も盛んに行われている。それらの解法の研究は、推奨されるパラメータを決定するのに貢献している。

LWE格子暗号は耐量子暗号の一つで、LWE問題を安全性の根拠としている。このLWE問題の解法として、格子の基底簡約と量子探索を組み合わせたHybrid Attackを提案した。

## 前提知識

はじめに格子、LWE問題、格子に関する数学的な問題に関して定義をしておこう。

### 格子(Lattice)

ここでは格子の定義を行う。(ここでは、整数の要素のみを持つ格子について考える)

${\bf B} \in \mathbb Z^{m \times n}$を基底とする格子$\Lambda ({\bf B})$とは以下のような点の集合である。

$$
\Lambda({\bf B}) = \{ {\bf Bx} \colon {\bf x} \in \mathbb Z^n\}
$$

ここで、基底$B$とは、$m$次元の線形独立なベクトル$b_1, \ldots, b_n$を列ベクトルとして${\bf B}=[{\bf b}_1 \ldots {\bf b}_n]$である。

より幾何学的に考えるなら、格子点は$m$次元の空間にある線形独立な$n$本のベクトルの整数線形結合で表される点の集合である。

LWEにおいては、$q \in \mathbb N$の剰余を取った以下の格子を考える。

$$
\Lambda({\bf B}) = \{ {\bf Bx} \mod q \colon {\bf x} \in \mathbb Z^n\} \\
%\Lambda^\bot({\bf B}) = \{ {\bf x} \colon {\bf Bx} = {\bf 0} \mod q \}
$$

### Learning with Errors 問題(LWE)

$n,m,q \in \mathbb N, \alpha > 0$として、${\bf s} \in \mathbb Z_q^n$の各要素を離散ガウス分布に従って選ぶ。

$\alpha$は、離散ガウス分布の誤差に関するパラメータで、離散ガウス分布は平均が$0$、標準偏差$\sigma = \frac{\alpha q}{\sqrt{2 \pi}}$となる。

行列${\bf A} \in \mathbb Z^{m \times n}$を$\mathbb Z_q^{n \times m}$から一様ランダムに選び、${\bf e} \in \mathbb Z_q^{m}$を離散ガウス分布に従って選ぶ。

Learning with Errors問題とは、$({\bf A}, {\bf b} = {\bf As + e})$が与えられたときに、${\bf s}$を求める問題である。

暗号化を行う際には、正規のユーザーは秘密情報として$({\bf s, e})$を知っているためこれを簡単に解くことができるが、秘密を知らないユーザーは解くのが難しい。なお、誤差項$\bf e$がない場合は、ガウスの消去法によって多項式時間で解くことが可能である。

### 格子に関する問題

次に本論文で登場する格子に関する問題(SVP, BDD)について紹介する。

#### 最短ベクトル問題(Shortest Vector Problem, SVP)
最短ベクトル問題は、格子基底${\bf B}$が与えられたときに、格子$\Lambda({\bf B})$の最も短いベクトル${\bf v}\in \Lambda({\bf B}) \; \mathrm{s.t.}\; \|{\bf v}\| = \lambda_1(\Lambda)$を求める問題である。$\lambda_1(\Lambda)$は格子$\Lambda$における最も短いベクトルの長さである。

#### Bounded Distance Decoding Problem(BDD)

格子$\Lambda({\bf B})$と標的ベクトル${\bf t} \in \mathbb Z^{m}$とする。標的ベクトルと格子との距離の関係は$\mu < \frac{1}{2}$というパラメータに対して$\mathrm{dist}({\bf t}, \Lambda) < \mu \lambda_1(\Lambda)$の関係がある。

BDD問題とは、格子基底${\bf B}$と標的ベクトル${\bf t}$が与えられたときに格子$\Lambda$に最も近い格子点${\bf v} \in \Lambda$を求める問題である。

## 手法の概要

### LWE から SVP へ
ここでは、LWE問題を前述の最短ベクトル問題(SVP)に帰着させる。

$$
{\bf b} = {\bf As + e}
$$

ここで、攻撃者が知っているのは${\bf A}$と${\bf b}$,それから$n,m,q$と誤差に関するパラメータ$\alpha$である。

注意すべきこととして、攻撃が成り立つには秘密の情報である${\bf s, e}$がそれぞれ短いベクトルである必要がある。[^2]

ここで、以下のような$d = n + m + 1$次元の格子を考える。(先ほど与えた定義と形式が違うため戸惑うかも知れないが、これも格子である)

$$
\Lambda^\bot = \{ {\bf x} \in \mathbb Z^d \colon \left[\begin{array}{ccc}{\bf A} & {\bf I}_m & {\bf -b} \end{array}\right]{\bf x} = {\bf 0} \mod q\}
$$

${\bf I}_m$は$m \times m$の単位行列である。

ここで、元のLWE問題において${\bf s, e}$の関係より、${\bf v} = ({\bf s}, {\bf e}, 1)$は格子$\Lambda^\bot$の格子ベクトルである。この${\bf v}$が極端に短いベクトルであるなら、この格子$\Lambda^\bot$の最短ベクトルを求めることによって秘密${\bf s, e}$がわかるはずである。

よって、この格子$\Lambda^\bot$のSVPを解くことを考える。

### SVP から BDD へ

ここでは、先程のSVPからBDDに帰着させる。

格子$\Lambda^\bot$の基底${\bf B^\prime}$を、$r < m, n$を満たす$r \in \mathbb N$として以下のように得られたとする。

$$
{\bf B^\prime} = \left[
\begin{array}{cc}
{\bf B} & {\bf C} \\
{\bf 0} & {\bf I}_r
\end{array}
\right] \in \mathbb Z^{d \times d}
$$

(一旦何かしらの基底が得られれば、あとはこのような形にできればよい)

では、先程のベクトル${\bf v} = ({\bf s},{\bf e}, 1)$を${\bf v} = ({\bf v}_l, {\bf v}_g)$のように分けてみよう。イメージとしてはこんな感じ


この${\bf v}$を基底${\bf B}^\prime$とその係数${\bf x} = ({\bf x}_{d -r}, {\bf x}_r)$を使って表すと、

$$
{\bf v} = \left[\begin{array}{c}
{\bf v}_l \\
{\bf v}_g
\end{array}\right] = {\bf B}^\prime {\bf x} = \left[ \begin{array}{cc}
{\bf B} & {\bf C} \\
{\bf 0} & {\bf I}_r
\end{array}\right] \left[\begin{array}{c}
{\bf x}_{d-r} \\
{\bf x}_{r}
\end{array}\right] = \left[ \begin{array}{cc}
{\bf Bx}_{d-r} + {\bf Cx}_{r} \\
{\bf x}_{r}
\end{array}\right]
$$

${\bf x}_r$を消して${\bf v}_l,{\bf v}_g$の式にすると以下の式が得られる。

$$
{\bf Bx}_{d-r} + {\bf Cv}_g = {\bf v}_l
$$

ここで、${\bf Bx}_{d-r}$は基底${\bf B}$で貼られる格子の格子点としてみることができる。また、先程の${\bf s}, {\bf e}$がとても短いベクトルになっているという仮定より、${\bf v}_{l}$は短いベクトルである。

もし${\bf v}_g$がわかれば、格子$\Lambda({\bf B})$と標的ベクトル${\bf Cv}_g$としてBDDを解くことで、つまり標的ベクトルに最も近い格子ベクトル${\bf Bx}_{d-r}$を求めることで${\bf v}_l$を得られる。

### ${\bf v}_g$を推測する(Quantum Search)
ここでは、先程の標的ベクトルを決める${\bf v}_g$を推測するために量子アルゴリズムを用いる。

つまり、推測するのはこの部分である。


量子探索アルゴリズムといえば、Groverのアルゴリズムが有名である。Groverのアルゴリズムについて簡単に書くと、$N$項目ある構造化されていないデータベースから一つの目標の項目を$O(\sqrt{N})$で見つけるアルゴリズムである。

一般に、目標の項目が複数個(ここでは$k$個とする)有る場合には、$O(\sqrt{N/k})$で目的の項目を見つけることができるのだが[^1]、Groverのアルゴリズムでは*構造化されていないデータベース*と書いたとおり、目的の項目が全体の探索空間の中でどのように分布しているか等の情報を利用できないという欠点がある。

今回の手法ではLWE問題の秘密情報、つまり$({\bf s},{\bf e})$の分布に関する情報をもちいることができないため、効率が悪い。そこで、観測を行わず、探索空間からある分布に従ってサンプリングを行うアルゴリズム$\mathcal{A}$と、$\mathcal{A}$を一度行ったときに目標の項目を得られる確率$a$を用いる。

ここで、解かどうかを判別する2値関数$f$として以下のような関数を構成する。

- 得られたベクトル${\bf v}_g$に関して前述のBDDを解き、
- それによって得られる${\bf v}_l$と合わせて短いベクトルとなっていれば1
- そうでないなら0を返す

この$\mathcal{A}, f$を$\Theta(1/\sqrt{a})$くらい適用すると求めたいベクトルを見つけることができる。[^3]

最後に、ここで得られた$({\bf v}_l, {\bf v}_g)$が求めたい$({\bf s}, {\bf e}, 1)$となっているので、秘密の情報を求められたことになる。

Groverのアルゴリズムを用いたときとの反復回数の比較も本論文ではされており、実際にGroverのアルゴリズムよりも高速化されていることがわかる。興味が有る人は見てみるとよい。

## 既存の攻撃手法との比較

ここでは実際にLWE問題のパラメータを設定したときに、既存のLWE解法との計算量の比較を行う。

以下の表はNew HopeとFrodo-592, Frodo-752, Frodo-864の4種類の鍵交換方式に用いられているパラメータのLWE問題に関してDual Embedding, Decoding Attack, 今回のQuantum Hybridを適用したときに推定される計算量の$\log_2$をとった結果である。いずれも既存の手法よりも小さいか、それと同等の計算量になっている。



また、既存研究での2値、3値誤差における中間一致攻撃を用いた手法と比較しても、計算量を減らすことに成功していることがわかる。


論文中には他のインスタンスに対しても比較している。いずれも計算量は今回の手法がより小さいか、それに匹敵するくらいの計算量になっている。

## 何が嬉しいんですか
既存研究[^4][^5]ではLWE問題の誤差項が{0,1}の2値、もしくは{-1, 0, 1}の3値の場合に中間一致攻撃を用いて標的ベクトルを推測していた。この手法は、以下の3つの問題がある。

- 誤差項が2値、3値の場合にしか実用的でない
- 膨大なサイズのメモリを必要とする
- 成功確率がとても低い

今回の手法では、中間一致攻撃の代わりに量子探索アルゴリズムを用いることで、上の3つの問題を解決することができた。

## コメント

New Hopeといえば2016年にGoogleが試験的に導入した鍵交換方式である。この論文ではNew Hopeに対しても計算量の推定値を評価しているが、それでも十分に計算量は大きく、安全が担保されていると言える。

ここらへんまでまとめて気づいたんですが、この論文は量子アルゴリズムを用いていたり、そもそも格子暗号はまだ研究段階の話が多く、practicalな話ではないため今回のアドベントカレンダーの雰囲気とちょっと外れているかもしれない。近いうちにもうちょっとpracticalな話題もまとめて記事にしたいと思っている。

はてなブログではtexの記法が記述し辛くてこっちに書いてしまった。春休みらへんの時間を使ってブログを別の場所に移行しようと思います。

## 参考文献
- http://staff.cs.kyushu-u.ac.jp/data/event/2016/04/160229_Rachel_Player.pdf
- https://eprint.iacr.org/2017/221.pdf
- http://www.cryptrec.go.jp/estimation/techrep_id2404.pdf
- https://arxiv.org/abs/quant-ph/9605043
- https://arxiv.org/abs/quant-ph/0005055

[^1]: Groverのアルゴリズムの原論文では解が一つの場合についてしか言及しておらず、出典ははっきりしてない
[^2]: どれくらいの大きさである必要があるのかについては言及されていないが、元論文ではこの条件はLWEのインスタンスにおいて一般的なことであるとしている。ほんまか？？
[^3]: https://arxiv.org/abs/quant-ph/0005055 のaが未知のときの場合を参照
[^4]: [Revisiting the Hybrid Attack: Improved Analysis and Refined Security Estimates by *Thomas Wunderer*](https://eprint.iacr.org/2016/733)
[^5]: [On the Hardness of LWE with Binary Error: Revisiting the Hybrid Lattice-Reduction and Meet-in-the-Middle Attack by *Buchmann and Göpfert et al.*](https://eprint.iacr.org/2016/089)