BKWアルゴリズム
概要
BKWアルゴリズムとは, $\mathbb{F}_2$上のLWE探索問題(LPN探索問題)を$2^{O(n/\log n)}$時間で解くアルゴリズムであり, その名は提案した論文Blum, Kalai, Wasserman (2003)の著者名の頭文字からとられています.
ここではパラメータ$n\in\mathbb{N},\rho\in[0,1/2)$に対して以下の問題設定を考え, 便宜上LPN学習問題と呼ぶことにします:
問題 (LPN学習問題).
- 未知のベクトル$s\in \mathbb{F}_2^n$を考える.
- ランダムサンプルオラクル$\mathcal{O}$へアクセスする権利が与えられる. オラクル$\mathcal{O}$に一回アクセスすると, 一様ランダムな$a\sim \mathbb{F}_2^n$, ベルヌーイ試行$e\sim \mathrm{Ber}(\rho)$および$b=s^\top a + e \in \mathbb{F}_2$に対し, 組$(a,b) \in \mathbb{F}_2^n \times \mathbb{F}_2$を取得できる. ここでベルヌーイ試行$\mathrm{Ber}(\rho)$とは, 他の全てのランダムネスとは独立に確率$\rho$で$1$, 確率$1-\rho$で$0$をとる確率変数である.
- ランダムサンプルオラクルを使って未知のベクトル$s$を計算せよ.
アルゴリズムの効率性は
- ランダムサンプルオラクル$\mathcal{O}$へのアクセス回数 (クエリ計算量)
- 時間計算量
によって評価できます. クエリの回数も計算量にカウントされるため, クエリ計算量は時間計算量で上から抑えられます. 従ってここでは単純化して時間計算量のみを考えます.
ランダムサンプルクエリは非適応的(nonadaptive)なので, クエリの回数$m$の上界がわかっている場合は, アルゴリズムの実行時, 一番最初に$m$回クエリを行なってもそのアルゴリズムの実行に影響を与えません. このことを使ってLPN学習問題は行列の形式で定義されたLWE探索問題と(時間計算量の意味で)同値であることが簡単に示せます. 実際, $(A,As+b)$を受け取って$s$を出力するアルゴリズム$A_0$がある場合, $A$の行数を$m$とすると, まず$m$回の$\mathcal{O}$へのクエリを使ってその応答を$(A,b)$の形にまとめ, それを$A_0$に渡すことでLPN学習問題を解くことができます. 逆にクエリ計算量$m$で解くアルゴリズムがある場合, そのアルゴリズムは$m$回のクエリに対するオラクルの応答をまとめた$(A,b)$を入力として受け取って未知のベクトル$s$を返すアルゴリズムと見做せるため, そのまま転用することで行列形式のLWE探索問題を解くことができます.
賢いアルゴリズムを見る前にまずLPN学習問題を解く自明なアルゴリズムについて考えてみましょう. そもそも未知のベクトル$s \in \mathbb{F}_2^n$は$2^n$通りしかないので, 全てのありうる$s$を試して最尤推定を行えば$2^{n}\cdot \mathrm{poly}(n)$時間でLPN学習問題を解くことができます. BKWアルゴリズムはこの自明なアルゴリズムよりも効率的にLPN学習問題を解くことができます.
定理 (BKWアルゴリズム).
任意の定数$\rho\in[0,1/2)$に対し, LPN学習問題を時間計算量$2^{O(n/\log n)}$で解くアルゴリズムが存在する.
なお, BKWアルゴリズムのクエリ計算量は時間計算量とほぼ同程度のオーダーになります.
アルゴリズムの中身
BKWアルゴリズムでは二つのパラメータ$g,h$ (ただし$g\cdot h \ge n$) に対し, $n$次元ベクトル$v\in \mathbb{F}_2^n$を$h$個の連続する長さ$g$のブロックに分割し, それぞれのブロックは$g$次元ベクトルとして扱います. 以後では簡単のため$n=gh$とします (そうでない場合, ベクトル$s$の後ろに$0$を適当な個数だけ連結してベクトル長を$g$または$h$の倍数にしておきます. 追加した部分は全て成分が$0$なのでラベル$b$に影響を与えることはありません).
鍵となる補題
アルゴリズムとその解析を述べるのに有用な以下の概念を導入します:
定義 ($i$-サンプル).
ベクトル$v \in \mathbb{F}_2^n$であって, 後ろ$i$個の全てのブロックに対応する成分が全て$0$であるようなものの集合を$V_i \subseteq \mathbb{F}_2^n$で表し, $V_i$から一様ランダムに選ばれたベクトルを$i$-サンプルと呼ぶ.
特に, オラクル$\mathcal{O}$の出力$(a,b)$に対して$a \sim \mathbb{F}_2^n$は$0$-サンプルであると言えます. BKWアルゴリズムの核となるアイデアは, $i$-サンプルを用いて$i+1$-サンプルを効率的に計算できるという以下の補題に基づいています.
補題1.
$L$個の独立$i$-サンプルが与えられたとき, それらを使って$L-2^g$個の独立な$(i+1)$-サンプルを出力する$O(L\cdot 2^g)$時間アルゴリズムが存在する. さらに, このアルゴリズムで得られる各$(i+1)$-サンプルは, 入力で与えられれた$L$個の$i$-サンプルから二つを選んでその和を取ることで得られる.
図: 補題1のアルゴリズム適用後はサンプルの個数が減るが, $0$のブロックは一つ増える.
証明
証明のアイデアは非常に単純で, $L$個 の$i$-サンプルを$2^g$個のクラスと呼ばれる部分集合に分割し, それぞれのクラス内で二つのベクトルを選んで和を取ることで$(i+1)$-サンプルを得るというものです.
まず, $i$-サンプル$v \in V_i$は後ろ$i$個のブロックが全て$0$であるようなベクトルであるため, 後ろから$i+1$個目のブロックは非ゼロであることがわかります (本当は各成分がランダムに決まるのでものすごく小さい確率でこのブロックの全ての成分$0$になりますが, ここでは無視します). この非ゼロのブロックは$g$ビット文字列であり$2^g$通り存在します. 従ってこのブロックに基づいて与えられた$i$-サンプルを$2^g$個のクラスに分割することができます.
各クラス$S$に対し, 一様ランダムに$x \sim S$を選び, 多重集合$S’=\{x + y \colon y \in S\}$を構成します. これらのベクトル$x,y$は同じクラスに属するため, その和$x+y$は後ろから$i+1$個目のブロックの全成分が$0$となるため, $V_{i+1}$の元になります. なお, $S’$の全ての元は共通の$x$に対して$x + y$という形で表されますが, $y$は先頭$h-i$個のブロックが全て独立一様ランダムなブロックであるため, 各$x+y$は$(i+1)$-サンプルとなり, しかも$y$の独立性から$S’$の元もまた独立です.
アルゴリズムは 全てのクラスに対してこの操作を繰り返し, $S’$の和集合を出力します. 先ほどの議論から, 確かにこれは$(i+1)$-サンプルとなります. なお, 各クラスに対し$\left| S’ \right| = \left| S \right| - 1$であり, クラスは$2^g$個あるため, この操作は$O(L\cdot 2^g)$時間で完了し, アルゴリズムの出力は$ |S| - 2^g$ 個の$(i+1)$-サンプルとなります. $\square$
アルゴリズムの記述
BKWアルゴリズムではまず, $h \cdot 2^g$回のクエリを使って$h\cdot 2^g$個の$0$-サンプルを取得します. これらのサンプルに対して補題1を適用すると, $(h-1)\cdot 2^g$個の$1$-サンプルを得ることができ, これらに対して改めて補題1を適用することで$(h-2)\cdot 2^g$個の$2$-サンプルを得ます. この$(h-1)$回繰り返すと最終的に$2^g$個の$(h-1)$-サンプルを得ることができます.
ここで, $(h-1)$-サンプルは先頭のブロックのみが非ゼロとなっているベクトルであることに注意しましょう. さらに, これらの先頭ブロックは$\mathbb{F}_2^g$から独立一様ランダムに選ばれているので, 確率$(1-2^{-g})^{2^g}\approx 1-1/\mathrm{e}$で単位ベクトル$e_1:=[1,0,0,\dots,0]$を含んでいるはずです. もし含まれていなければ再びクエリと補題1を使って探索することで, この単位ベクトルを高確率で見つけることができます. さらに, 補題1からこの単位ベクトルは元の$0$-サンプルのうち$2^h$個の和で表せます. これを
\[\begin{align*} e_1 = a_1 + \dots + a_{2^h} \end{align*}\]と書きましょう (ここでは$\mathbb{F}_2$上のベクトルとしての演算を考える). 右辺の各ベクトル$a_i$に対応するラベル$b_i$は$b_i = s^\top a_i + e_i$を満たすので, 上式の両辺に対し$s^\top$との内積をとると
\[\begin{align*} s_1 = b_1 + \dots + b_{2^h} + \underbrace{e_1 + \dots + e_{2^h}}_{\mathrm{Ber}(\rho) \oplus \dots \oplus \mathrm{Ber}(\rho)} \tag{*} \end{align*}\]を得ます. ここでノイズに対応する部分は$2^h$個の独立なベルヌーイ試行$\mathrm{Ber}(\rho)$のXORとなっています. このノイズ部分を抑える次の情報理論的な補題を使うことで, $s_1$を求めることができます.
補題2.
\[\begin{align*} \Pr\left[ \underbrace{\mathrm{Ber}(\rho) \oplus \cdots \oplus \mathrm{Ber}(\rho)}_{\text{$\ell$個}} = 0 \right] = \frac{1}{2} + \frac{1}{2} \left(1 - 2\rho\right)^\ell. \end{align*}\]
証明
証明は$\ell$に関する帰納法で示します. 記法の簡単のため, 主張の左辺を$p_\ell$とおきます.
1. ベースステップ ($\ell=1$の場合):
\[p_1 = 1 - \rho = \frac{1}{2} + \frac{1}{2}(1 - 2\rho)\]より, $\ell=1$の場合に主張は確かに成り立ちます.
2. 帰納ステップ: 一般の$\ell \ge 2$に対しては, $p_{\ell-1}$に対する帰納法の仮定を使って
\[\begin{align*} p_\ell &= (1-\rho)\cdot p_{\ell-1} + \rho\cdot (1-p_{\ell-1}) \\ &= (1-\rho)\left( \frac{1}{2} + \frac{1}{2} \left(1 - 2\rho\right)^{\ell-1} \right) + \rho\left( \frac{1}{2} - \frac{1}{2} \left(1 - 2\rho\right)^{\ell-1} \right) \\ &= \text{(右辺)} \end{align*}\]より主張を得ます. $\square$
補題2より, (*)において$s_1=b_1+\dots+b_{2^h}$が成り立つ確率は$1/2 + (1-2\rho)^{2^h}/2$となります. つまり, 単位行列$e_1$の和に使われたサンプルのラベルを足し合わせると$1/2$より少し大きい確率で未知のベクトルの第一成分が得られることになります. この操作は$((1-2\rho)^{-2^h})^2\cdot O(\log n)$回繰り返すことによって成功確率を$1-n^{-100}$程度まで増幅できます. $s$の他の成分に関してはベクトルの成分をシャッフルして同じことを繰り返しせば, それらも同様に求めることができます.
以上より, (補題1の計算量も考慮すると)LPN学習問題は$gh\ge n$を満たす任意の$g,h$に対して計算量 $\mathrm{poly}\left(n,\left(\frac{1}{1-2\rho}\right)^{2^h},2^g\right)$で解くことができます.
パラメータ$g,h$の設定
BKWアルゴリズムの効率性はパラメータ$g,h$の選択に大きく依存しますが, 特に$\rho<1/2$が定数の場合の計算量は
\[\begin{align*} \mathrm{poly}\left(n,\left(\frac{1}{1-2\rho}\right)^{2^h},2^g\right) &= \mathrm{poly}\left(n,2^{O(2^h)},2^g\right) \\ &= 2^{O(2^h+g)}\cdot \mathrm{poly}(n) \end{align*}\]となります. 制約$gh=n$に留意して
- $h = \frac{\log_2 n}{2}$
- $g = n/h = \frac{2n}{\log_2 n}$ とすると, 計算量は$2^{O(n/\log n)}$となります.