擬似ランダム生成器とNisan-Wigderson生成器

1. 擬似ランダム生成器

平均時計算量では分布のランダムっぽさを, その分布が任意の効率的な敵対者(=アルゴリズム)に対して一様分布と識別できないという性質によって定義する定式化があります. ここでは主に敵対者としてサイズ$s$の回路を考えます. 前回の記事でも紹介しましたが分布の擬似ランダム性を以下で定義します:

定義1 (擬似ランダム性).

$\{0,1\}^\ell$上の分布$D$がサイズ$s$に対して$\epsilon$-擬似ランダムであるとは, 任意のサイズ$s$の回路$C$に対して

$$\begin{align*} |\mathbf{E}_{x\sim D}[C(x)]-\mathbf{E}_{x\sim U_n}[C(x)]| \leq \epsilon \end{align*}$$

が成り立つことをいう (ここで$U_n$は$\{0,1\}^n$上の一様分布). 

定義2 (擬似ランダム生成器).

関数$G\colon \{0,1\}^n\to\{0,1\}^\ell$は, $\{0,1\}^\ell$上の分布$G(U_n)$がサイズ$s$に対して$\epsilon$-擬似ランダムであるとき, サイズ$s$に対する$\epsilon$-擬似ランダム生成器であるという.

擬似ランダム生成器は短いランダム文字列を受け取って長い擬似ランダム文字列を返す関数です. 例えば$\ell$ビットのランダム文字列$r$を使う乱択アルゴリズム$\mathcal{A}(x;r)$を考えたとき, $r$としてランダム文字列の代わりに$G(U_n)$を用いたアルゴリズム$\mathcal{A}(x;G(U_n))$もまた元の乱択アルゴリズム$\mathcal{A}(x;r)$とほぼ同じ振る舞いをすることが示せます (そうでないとすると, $\mathcal{A}(x;\cdot)$を使って$G(U_n)$と$U_\ell$を識別できるので). 全ての$n$ビットのシードを列挙すれば, $2^n$倍のオーバーヘッドでアルゴリズムを脱乱択することができます. このように考えると, $\ell$が大きいかつ$\epsilon$が小さいほど擬似ランダム生成器は良いということになります.

2. 簡単な例

2.1. 1ビットだけ伸ばす

前回の記事の定理(Yaoのnext-bit predictor)により, 関数$f\colon\{0,1\}^n\to\{0,1\}$がサイズ$s$に対して$(1/2-\epsilon)$困難であるならば, 関数$G\colon x\mapsto (x,f(x))$はサイズ$s-O(1)$に対して$\epsilon$-擬似ランダム生成器になります. この関数$G$は$\ell=n+1$なので, 1ビットだけ伸ばす擬似ランダム生成器です.

定理1.

関数$f\colon\{0,1\}^n\to\{0,1\}$がサイズ$s$に対して$(1/2-\epsilon)$-困難ならば, 関数$G\colon x\mapsto (x,f(x))$はサイズ$s-O(1)$に対して$\epsilon$-擬似ランダム生成器である.

2.2. 2ビットだけ伸ばす

関数$G\colon \{0,1\}^{2n}\to \{0,1\}^{2n+2}$を

$$\begin{align*} G(x,y)=(x,f(x),y,f(y)) \end{align*}$$

としてみます (ここでは入力を前半と後半の$n$ビットずつに区切り, それぞれを$x,y\in\{0,1\}^n$としている). 同様の議論を使うとこれは2ビットだけ伸ばす擬似ランダム生成器になることが示せます.

定理2.

関数$f\colon\{0,1\}^n\to\{0,1\}$がサイズ$s$に対して$(1/2-\epsilon/2)$-困難ならば, 関数$G\colon (x,y)\mapsto (x,f(x),y,f(y))$はサイズ$s-O(1)$に対して$\epsilon$-擬似ランダム生成器である.

証明:

背理法で示す. あるサイズ$s'$の回路$C$が存在して

$$\begin{align*} \mathbf{E}_{(x,y)\sim U_{2n}}[C(x,f(x),y,f(y)] - \mathbf{E}_{(z,w)\sim U_{2n+2}}[C(z,w)]>\epsilon \end{align*}$$

となるとする (必要があれば出力ビットを反転することで絶対値を外せる). 期待値の線形性およびランダム文字列をそれぞれ$z=(x,b),w=(y,c)$と書き直すと

$$\begin{align*} \mathbf{E}_{(x,b,y,c)\sim U_{2n+2}}[C(x,f(x),y,f(y)) - C(x,b,y,c)] > \epsilon \end{align*}$$

を得ます. この式の左辺は, 同じ値を足したり引いたりすることで

$$\begin{align*} \mathrm{(LHS)} &= \mathbf{E}[C(x,f(x),y,f(y))] - \mathbf{E}[C(x,f(x),y,c)] \\ &\hspace{1em}+ \mathbf{E}[C(x,f(x),y,c)] - \mathbf{E}[C(x,b,y,c)] > \epsilon \end{align*}$$

を得ます. よって, 前半の差と後半の差の少なくとも一方は$>\epsilon/2$です. すなわち

$$\begin{align*} &\mathbf{E}[C(x,f(x),y,f(y))] - \mathbf{E}[C(x,f(x),y,c)] > \epsilon/2 \\ &\hspace{10em}\text{ or }\\ &\mathbf{E}[C(x,f(x),y,c)] - \mathbf{E}[C(x,b,y,c)] > \epsilon/2 \end{align*}$$

です. もし前者が成り立つならば, ある$x^*\in\{0,1\}^n$が存在して回路$C'(y,c):=C(x^*,f(x^*),y,c)$を考えると, これは二つの分布$(y,f(y))$と$U_{n+1}$をアドバンテージ$>\epsilon/2$で識別する. これは定理1に反する. 後者が成り立つ場合でも同様に, 回路$C$においてうまく$(y,c)\in\{0,1\}^{n+1}$を選んで固定して得られる回路$C'$は定理1に反する.

(証明終)

コメント1. 上記の証明において, 回路の入力を部分的にうまく選んで固定して新しい回路を得ていました. 例えば前半のケースでは$x$を固定していましたが, このときの$x$の選び方は$(y,c)$の選び方には依存しないことに注意してください. また, $x$を固定すると$f(x)\in\{0,1\}$も自動的に固定されます. このように回路の入力を部分的にうまく選んだ値に固定することをハードワイヤ (hardwire)するといいます.

コメント2(適当に読み飛ばしてください). 上記の証明においては同じ値を足したり引いたりしてうまく式変形した後に, 二つのケースに分けてそれぞれについて$(U_n,f(U_n))$と$U_{n+1}$を識別する回路$C'$を構成しました. このときの式変形では, 

$$\begin{align*} \mathbf{E}[C(D)]-\mathbf{E}[C(D')]>\epsilon \end{align*}$$

の形をした左辺を二つの差分の和として表現していて, それぞれの差分では構成要素が一つしか異ならないテレスコープサムのような形に変形しています. このように, 二つの$D$と$D'$を補間するような分布列$D_0=D,D_1,\dots,D_k=D'$を用意して

$$\begin{align*}\mathbf{E}[C(D)]-\mathbf{E}[C(D')]=\sum_{i=1}^k \mathbf{E}[C(D_{i-1})-C(D_i)] >\epsilon \end{align*}$$

と式変形して議論することをハイブリッド議論 (hybrid argument)と呼び, 分布列$D_0,\dots,D_k$をハイブリッド分布と呼びます (平均時計算量の脱乱の分野では頻出です).

コメント3. 上記の証明ではあくまでも回路の存在性のみをいっていて, その回路が効率的に構築できるかどうか (つまり元となる回路$C$を入力として受け取って所望の回路$C'$を出力するアルゴリズムの存在性) については何も言っていないことに注意してください. 例えば$x=x^*$にハードワイヤする際に$f(x^*)$も同時にハードワイヤしましたが, このとき$f(x^*)$を計算する手間は考えていません ($x^*$を固定したら一意に定まるから).

2.3. 2ビット伸ばす (続)

2.2節では$2n$ビットのランダム文字列を受け取って$2n+2$ビットの擬似ランダム文字列を出力する擬似ランダム生成器を紹介しました. ここでは, 次の章のために別の擬似ランダム生成機$G\colon \{0,1\}^{2n-d} \to \{0,1\}^{2n-d+2}$を紹介します ($d$はパラメータ).

まず, $2n-d$ビットの入力$z\in\{0,1\}^{2n-d}$の前半$n$ビットを$x$, 後半$n$ビットを$y$とします. 関数$G(z)$は$(z,f(x),f(y))$を出力します.

$d=0$のときは2.2節と同じになりますが, ここでは$x$と$y$の取り方にオーバーラップを許している点が異なります. このように構成された$G''$も$d$が小さければ擬似ランダム生成器になることが示せます:

定理3.

関数$f\colon\{0,1\}^n\to\{0,1\}$がサイズ$s$に対して$(1/2-\epsilon/2)$-困難であるならば,上記で定義された関数$G$はサイズ$s-2^{O(d)}$に対して$\epsilon$-擬似ランダム生成器である.

証明する前にまず, そもそも2.2節の議論で示せないか考えてみましょう. 2.2節の議論では, 二つの分布$(x,f(x),y,f(y))$と$(x,b,y,c)\sim U_{2n+2}$が識別できるならばうまく$(y,c)\in\{0,1\}^{n+1}$をハードワイヤすることで$(x,f(x))$と$U_{n+1}$を識別する回路が作れて定理1に反するという方針でした. つまり, 入力を部分的に固定することで$(x,f(x))$と$U_{n+1}$を識別する回路が作れてしまうというのが2.2節の議論のミソでした (下図).

2.2節の議論で構成した回路$C'$ (二つ目のケースを図示).

今回の$G''$にこの議論を適用してみましょう. つまり, $(z,f(x),f(y))$と$(z,b,c)$を識別する回路$C$が作れたとします. 本来であれば$(y,c)$をうまくハードワイヤして得られた回路$C'$は$(x,f(x))$と$U_{n+1}$を識別することを言いたいのですが, $x$と$y$にはサイズ$d$のオーバーラップがあるので, $y$に該当する$n$ビットを固定してしまうと$x$の最後の$d$ビットも巻き込まれてハードワイヤされてしまいます. 従って, $(y,c)$をハードワイヤして得られる回路は$C'\colon \{0,1\}^{n-d+1}\to\{0,1\}$となっており, そもそも入力として$(x,f(x))$を受付けてくれません.

単純なアイデアですが, この問題点は$x$とオーバーラップしていない部分をハードワイヤすることによって解決できます. 

命題2の証明.

ビット列$w\in\{0,1\}^\ell$および$1\leq a\leq b\leq \ell$に対して$w[a:b]$を$w$の第$a$番目から$b$番目までの部分文字列とする.

$G(U_{2n-d})$と$U_{2n-d+2}$をアドバンテージ$>\epsilon$で識別する回路を$C$とする. 与えられた$z\in\{0,1\}^{2n-d}$に対し, 前の$n$ビットを$x=z[1:n]$, 後ろの$n$ビットを$y=z[n-d,2n-d]$とする. 定義より, $b,c\sim U_1$とすると,

$$\begin{align*} \mathbf{E}[C(z,f(x),f(y)) - C(z,b,c) > \epsilon. \end{align*}$$

この式の左辺は

$$\begin{align*} (\mathrm{LHS}) &= \mathbf{E}[C(z,f(x),f(y))] - \mathbf{E}[C(z,f(x),c)] \\ &\hspace{1em}+\mathbf{E}[C(z,f(x),c)]-\mathbf{E}[C(z,b.c)] > \epsilon \end{align*}$$

より,

$$\begin{align*} &\mathbf{E}[C(z,f(x),f(y))] - \mathbf{E}[C(z,f(x),c)] > \epsilon/2 \\&\hspace{10em}\text{ or }\\&\mathbf{E}[C(z,f(x),c)]-\mathbf{E}[C(z,b,c)] > \epsilon/2\end{align*}$$

を得る. 

(i). 前者が成り立つ場合, $x$の前から$n-d$ビット$x[1:n-d]$をある$w^*\in\{0,1\}^{n-d}$にハードワイヤする. このとき, $x$は$w^*$と$y[1:d]$を結合した文字列となるので, $f(x)=f(w^*,y[1:d])$の形で書くことができる. $y$が変数ならばこの値は$d$個の変数にしか依存しない値なので, サイズ$2^{O(d)}$の回路で計算できる (つまり, 固定した$w^*$に対して関数$(w^*,y[1:d])\mapsto f(w^*,y[1:d])$を計算するサイズ$2^{O(d)}$が存在する). この回路を$C$の$f(x)$を受け取る部分にくっつけます(下図).

このようにして得られた回路を$D(y,c)$とすると, $D$のサイズは$s'+2^{O(d)}$となり, $(y,f(y))$と$(y,U_1)$をアドバンテージ$>\epsilon/2$で識別する.

(ii). 後者が成り立つ場合も同様にして$(x,f(x))$と$(x,U_1)$をアドバンテージ$>\epsilon/2$で識別する回路を構成できる. こちらは単純に$y$の後ろ$n-d$ビットと$c$をハードワイヤすればよい.

ケース(i),(ii)どちらにしても所望の回路が構成できたので, 主張を得る.

(証明終)

3. Nisan-Wigderson生成器

ここまで定義した擬似ランダム生成機は2ビット程度しか伸ばさない, 少々心許ないものでしたが, 実は次数的に伸ばせることが知られています. NisanとWigdersonによるとても格好良いタイトルの論文「Hardness vs Randomness」は, 非常に困難な関数$f$を使って擬似ランダム生成器を構成する手法を提案しています. この手法によって構成された擬似ランダム生成器はNisan-Wigderson生成器と呼ばれ, 非常に強力なツールとして知られています.

2.2節と2.3節で紹介した擬似ランダム生成器$G$はどれも入力$z$から$n$ビットの文字列$x,y$を二つ取り出し, $(z,f(x),f(y))$を出力するというものでした. また, $x$と$y$のオーバーラップの長さ$d$が小さくてもサイズ$2^{O(d)}$の回路をくっつければ$G$の擬似ランダム性を示せることを2.3節で示しました. ここで, そもそも取り出す文字列は二つでなく三つ以上でも同様の証明が機能するという点に着目します. これをもとに設計されたのがNisan-Wigderson生成器です.

3.1. Combinatorial Design

定義4.

台集合$[m]$上の部分集合族$\mathcal{S}=\{S_1,\dots,S_\ell\}$が以下を満たすとき, $(m,n,d)$-デザインと呼ぶ:

(1). 各$S_i$は$|S_i|=n$.

(2). 全ての$1\leq i<j\leq \ell$に対し, $|S_i\cap S_j|\leq d$.

$(m,n,d)$-デザインは2.3節で考えた部分文字列の取り出し方を一般化したものになっています.

定理5 (Nisan-Wigderson生成器).

$\mathcal{S}=\{S_1,\dots,S_\ell\}$を$(m,n,d)$-デザインとし, $f\colon\{0,1\}^n\to\{0,1\}$を$(1/2-\epsilon/\ell)$-困難であるとする. 関数$G^f_{\mathcal{S}}\colon \{0,1\}^m\to\{0,1\}^\ell$を

$$\begin{align*} G^f_\mathcal{S}(x) = (f(x|_{S_1}), \dots, f(x|_{S_\ell})) \end{align*}$$

で定義する ($x|_S\in\{0,1\}^{|S|}$は$x$の$S$への制限. このとき, $G$はサイズ$s-\ell 2^{O(d)}$に対し$\epsilon$-擬似ランダム生成器である.

証明は定理3と同様なので, 概略だけ記します.

証明概略. $G^f_{\mathcal{S}}(U_m)$と$U_\ell$をアドバンテージ$>\epsilon$で識別する回路を$C$とします. 簡単のため, $x_i=x|_{S_i}$と表します. $b_1,\dots,b_\ell\sim U_1$とします. 定義より

$$\begin{align*} \mathbf{E}[C(f(x_1),\dots,f(x_\ell))] - \mathbf{E}[C(b_1,\dots,b_\ell)]>\epsilon. \end{align*}$$

ハイブリッド議論を見据えて式変形しましょう. $D_i=(f(x_1),\dots,f(x_i),b_{i+1},\dots,U_\ell)$とすると, $D_0=(b_1,\dots,b_\ell)$かつ$D_\ell=(f(x_1),\dots,f(x_\ell))$なので

$$\begin{align*}(\mathrm{LHS})&= \mathbf{E}[C(D_\ell)]-\mathbf{E}[C(D_0)] \\&=\sum_{i=1}^\ell\mathbf{E}[C(D_i)-C(D_{i-1})] > \epsilon\end{align*}$$

より, ある$i\in[\ell]$に対して

$$\begin{align*} &\mathbf{E}[C(f(x_1),\dots,f(x_{i-1}),f(x_i),b_{i+1},\dots,b_\ell)] - \\ &\mathbf{E}[C(f(x_1),\dots,f(x_{i-1}),b_i,b_{i+1},\dots,b_\ell)] > \epsilon/\ell \end{align*}$$

です. $C$の引数は$i$番目だけ異なっていることに注意してください. 変数名を$x_i=y$と変えて, $y$に対応する部分以外全てのビットをハードワイヤします (つまり$x|_{[m]\setminus S_i}=w^*$と固定する). さらに, $b_{i+1},\dots,b_\ell$もハードワイヤします. すると, $f(x_1),\dots,f(x_{i-1})$はそれぞれ, $y\in\{0,1\}^n$のうち高々$d$ビットにしか依存しません ($\mathcal{S}$が$(m,n,d)$-デザインだから). よってこれらはサイズ$2^{O(d)}$の回路で計算できるので, これらを$C$にくっつけることによって$(y,f(y))$と$(y,U_1)$をアドバンテージ$>\epsilon/\ell$で識別する回路を得ました.

(証明終).

3.2. デザインの存在性

以前の記事で証明しましたが, パラメータ$n,d\in\mathbb{N}$に対し, $\ell=n^{d+1}$個の集合からなる$(n^2,n,d)$-デザイン$\mathcal{S}=\{S_1,\dots,S_\ell\}$が存在します. このデザインを使うとNisan-Wigderson生成器は

$$\begin{align*} G\colon \{0,1\}^{n^2}\to \{0,1\}^{n^{d+1}} \end{align*}$$

となります.

4. Hardness vs Randomness

ここまでの定理では

$\exists$平均的に非常に困難な関数 $\Rightarrow$ $\exists$擬似ランダム生成器

という形の結果を証明しました. このように, 関数の困難性を利用して擬似ランダムネスを生み出す枠組みはHardness vs Randomnessと呼ばれ, 平均時計算量の理論で近年も活発に研究されています.