Learning with Error (LWE) とは?
概要
Learning with Error (LWE) とはノイズが乗った線形方程式を解けという非常にシンプルな問題である。 ノイズが乗っていない場合はガウスの消去法などを用いて簡単に解けるが、ノイズが乗った設定では適切なパラメータ下では
- 情報理論的には最尤推定 (全探索) で解ける。
- しかし、多項式時間で解けるかどうかは不明
という状況になっている。 そして、これが情報論的なtractabilityと計算量的なtractabilityの間の非自明なギャップであろうと広く信じられている。
LWEの計算量的困難性を仮定すると学習理論や暗号などの分野において様々な計算量的下界が成り立ち、以下に挙げる様々な利点から次世代の暗号技術(特に耐量子暗号)の核になることが期待されている重要な問題である：
- 擬似乱数生成器[Blum, Furst, Kearns, Lipton(CRYPTO1993)], [Goldreich, Krawczyk, Luby(SICOMP1993)]や公開鍵暗号方式[Alekhnovich(FOCS2003)]など様々な暗号学的プリミティブを設計できる。
- 格子上の問題(最短ベクトル問題など)の最悪時困難性を仮定するとLWEの平均時困難性が成り立つという結果が知られている [Regev(JACM2009)]。
- 上記の格子上の問題を解く効率的な量子アルゴリズムの存在性は長年未解決。
詳細はRegevによるサーベイ論文(2010)を参照。
定義
行列 $A \in \mathbb{F}^{m\times d}$ とベクトル $b = As \in \mathbb{F}^m$（ただし $s \in \mathbb{F}^d$ は秘密のベクトル）が入力として与えられたときに $s$ を復元することはできるだろうか？この問題は単に連立一時方程式
\[\begin{align} As = b \end{align}\]を解くだけであるので、ガウスの消去法などを用いて多項式時間で解ける。
では、与えられるベクトル $b$ が 小さいノイズを含む 場合はどうだろうか？ 具体的には、入力として与えられるベクトル $b$ がノイズベクトル $e \in \mathbb{F}^m$ に対して $b=As + e$ を満たす場合を考える。 ここで $e$ はランダムなベクトルであり、各成分が独立に $\mathbb{F}$ 上の同じ分布に従って生成されるものとする。 このような設定は線形関数の学習を考えると（有限体であることを除けば）非常にありふれた自然な設定であろうことがわかる。 つまり、様々な評価点とその点におけるラベルが与えられたときに、未知の線形関数 $\mathbb{F}^d \ni x \mapsto s^\top x$ を学習する際、ラベルにノイズが乗る設定を考えると上記のような問題が自然に現れる。
Learning with Error（以下、LWE問題）は平均時の問題、すなわち入力が何かしらの分布に従って生成される問題であり、ここでは秘密のベクトル $s \in \mathbb{F}^d$ と係数行列 $A \in \mathbb{F}^{m\times d}$ が一様ランダムに選ばれたとき、行列 $A$ と $b=As+e$ が入力として与えられる。
$\mathbb{F}$ を有限体、 $m,d\in \mathbb{N}$ をパラメータ、そして $\chi$ を $\mathbb{F}$ 上の分布とする。 一様ランダムな$A\sim \mathbb{F}^{m\times d}$, $s\sim \mathbb{F}^d$, およびノイズベクトル$e \sim \chi^m$に対し, 三つ組$(A,As+e,s)$の周辺分布を$\mathsf{LWE}_{\mathbb{F},m,d,\chi}$で表す. ここで, $\chi^m$は$\mathbb{F}^m$上の分布であり, 各成分が$\chi$から独立に選ばれたベクトルの分布を表す. パラメータ$\mathbb{F},m,d,\chi$が明らかな場合は単に$\mathsf{LWE}$で表す.
パラメータ$m$をサンプル数, $d$を次元, $\chi^m$をノイズ分布, $s$を秘密のベクトル, $b$をラベルと呼ぶ.
代表的なノイズ分布としては以下の二つが挙げられる：
- ランダムスパースベクトル: 体として$\mathbb{F}=\mathbb{F}_2$を考え、$\chi$はパラメータ$\theta\in[0,1]$に対して$\Pr[\chi=1]=\theta$を満たすもの。パラメータ$\theta$が小さければ、ノイズベクトル$e\sim\chi^m$は非ゼロ要素数の個数がおおよそ$m\theta$となる。
- 離散ガウス分布: 位数が素数$p$であるような有限体$\mathbb{F}_p$に対し$\chi$は$\mathbb{F}_p$上の分布であり、パラメータ$\sigma$に対し、$\chi$は$\Pr[\chi = x] \propto \exp\left(-\frac{x^2}{2\sigma^2}\right)$で定まる分布を考える（ここの右辺では$x\in{0,1,\dots,p-1}$を非負整数として扱って確率を計算する）。
また、特殊ケース$\mathbb{F} = \mathbb{F}_2$におけるLWE問題は特にLPN問題と呼ばれる。
LWE問題では$(A,b,s) \sim \mathsf{LWE}$に対し、 $(A,b)$の情報から$s$を復元せよという問題を考える。 実際には様々な問題設定があり、代表的なものとして探索問題、判定問題などが考えられている。
探索問題
探索問題とは、その名の通り、秘密のベクトル$s$を復元せよという問題である。
分布$\mathsf{LWE}_{\mathbb{F},m,d,\chi}$に従って選ばれた$(A,b,s)$に対し, $(A,b)$を入力として受け取って$s$を出力せよという問題を探索LWE問題という.
アルゴリズム$\mathcal{A}$は
\[\begin{align*} \Pr_{(A,b,s) \sim \mathsf{LWE}} \left[ \mathcal{A}(A,b) = s \right] \ge \gamma \end{align*}\]を満たすとき, 探索LWE問題を成功確率$\gamma$で解くという.
サンプル数$m$が小さいと、与えられた$(A,b)$に対して $As \approx b$を満たす$s$は複数存在しえるため、秘密のベクトル$s$を復元することはできない。これを情報理論的に解けないと言うことがある。
一方で$m$が十分大きいとき、全てのありうる$s$を試して$As\approx b$を見れば、$(A,b,s) \sim \mathsf{LWE}$に関して非常に高確率で秘密のベクトル$s$を復元できる。 これを、サンプル数$m$が十分大きいときは情報理論的に解けるという言い方をする。 もちろん、情報理論的に解けるからといってそれが効率的に解けるかどうかは分からない。
判定問題
アルゴリズムは$(A,b) \in \mathbb{F}^{m\times d}\times \mathbb{F}^m$を与えられる。ただし入力$(A,b)$は以下の二つどちらかの分布に従って生成される：
- $(A,b,s) \sim \mathsf{LWE}$に対して$(A,b)$の周辺分布。
- $\mathbb{F}^{m\times d}\times \mathbb{F}^m$上の一様分布。
判定問題では、入力が上記どちらの分布に従って生成されたかを判別する問題である。
出力値が0または1のアルゴリズム $\mathcal{A}$ は
\[\begin{align*} \left| \Pr_{(A,b,s) \sim \mathsf{LWE}} \left[ \mathcal{A}(A,b)=1 \right] - \Pr_{\substack{A\sim \mathbb{F}^{m\times d} \\ b \sim \mathbb{F}^m}} \left[ \mathcal{A}(A,b) = 1 \right] \right| \ge \gamma \end{align*}\]を満たすとき, 判定LWE問題をアドバンテージ$\gamma$で解くという.
サンプル数$m$が十分大きいとき, 一様ランダムな$A\sim \mathbb{F}^{m\times d},b\sim \mathbb{F}^m$に対して$As\approx b$を満たす$s\in \mathbb{F}^d$は存在しない. 一方で$(A,b)$が$\mathsf{LWE}$の分布から生成された場合はそのような$s$は必ず存在する. 従って与えられた$(A,b)$が$\mathsf{LWE}$から来たのか, 一様分布から来たのかは秘密のベクトルの存在性を解けば判定できることになる. このような背景で, $\mathsf{LWE}$と一様分布の識別を判定問題と呼んでいる.
学習としてのLWE問題
LWE問題はなぜLearningなのでしょうか? 実は, LWE問題は線形関数をノイズ下で学習するタスクとみなすこともできます.
大雑把に言えば学習とは, 何かしら未知の関数 $f\colon \mathcal{X} \to \mathcal{L}$ があって, サンプルと呼ばれる幾つかの点の集合$(x_1,f(x_1)),\dots,(x_m,f(x_m))$が与えられたとき, この関数$f$を模倣する関数$\tilde{f}$を構成せよというタスクを意味し, このタスクを行うアルゴリズムを学習アルゴリズムといいます. 基本的には任意の関数を扱うことはせず, $f$は何かしらの性質(例えば線形性)を持つことを仮定します. ここでは学習の概念については深掘りせず, ひとまずLWE問題を学習タスクとして捉えられることを説明します.
LWE問題では未知のベクトル$s\in \mathbb{F}^n$に対して, 一様ランダムな$A \sim \mathbb{F}^{m\times n}$とノイズベクトル$e \in \mathbb{F}^m$に対して$b=As+e$および$A$が入力として与えられ, $s$を求めることを目標としていました. そこで$a_1,\dots,a_m$を$A$の行ベクトルとすると, この問題は未知の線形関数$f\colon x \mapsto s^\top x$のノイズ付きのサンプル$(a_1,f(a_1)+e_1),\dots,(a_m,f(a_m)+e_m)$が与えられたときに, 未知の線形関数$f$を復元せよという問題と捉えることができます.