擬似ランダム生成器と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と呼ばれ, 平均時計算量の理論で近年も活発に研究されています.

関数の平均時困難性と分布の識別不可能性

1. 関数の平均時困難性

平均時計算量の理論ではランダムな入力に対する問題の計算複雑性を議論します. 具体的には, 関数$f\colon\{0,1\}^k\to\{0,1\}$が任意のサイズ$s$の回路$C$に対して

\begin{align*}
\Pr_{x\sim\{0,1\}^k}[C(x)=f(x)]\leq 1-\delta
\end{align*}

を満たすとき, $f$はサイズ$s$に対して$\delta$-困難であるといいます. つまり効率的に$f(x)$を計算できる入力$x$の量によってその問題$f$の複雑性を評価します (回路の代わりに効率的なアルゴリズムを考えても似たような定義を与えることができます). 回路$C$が正解する入力の割合を成功確率と呼ぶことにします. すなわち$C$の$f$に対する成功確率は$$\Pr_{x\sim\{0,1\}^k}[C(x)=f(x)]$$

で与えられます.

$f$がBoolean関数ならば, 「常に$0$を出力する回路」もしくは「常に$1$を出力する回路」の少なくとも一方は成功確率$1/2$以上になります. 従って関数$f$は$\delta$-困難であるといった場合は基本的には$\delta\leq 1/2$を仮定し, $\delta$が$1/2$に近いほど$f$の困難性は強いということになります. 

コメント.

非常に細かいことですが, 入力長ごとに「常に0を出力すべきか」「常に1を出力すべきか」が変わりうるので, 決定的アルゴリズムを用いて困難性を定義した場合は$\delta\leq 1/2$は一般には言えません. このように入力長ごとに違うアルゴリズムを採用する場合は非一様モデル(=回路)で議論した方が良いと思います (一概には言えませんが).

2. 分布の識別不可能性

2.1. 統計的な識別不可能性

一方で, 平均時計算量の理論では分布のランダムっぽさ(擬似ランダム性)が計算量の概念を使って定義されています.

 確率論や機械学習などの文脈では分布の近さを統計距離(total variation distance)で評価し, 一様分布に近い分布を「ランダムっぽい」分布とみなすことができます. この文脈でいうと, 「分布$D$はランダムっぽい」という主張は(統計距離の定義に基づいて考えると)「分布$D$と一様分布を識別できる事象は存在しない」ことを意味します. もう少しフォーマルに述べます. 分布$D$を有限集合$\Omega$上の分布だと仮定します. ある関数$E\colon\Omega\to\{0,1\}$が存在して

\begin{align*}
|\mathbf{E}_{x\sim D}[E(x)] - \mathbf{E}_{x\sim \Omega}[E(x)]| > \epsilon
\end{align*}

を満たすとき, 分布$D$は一様分布から(統計距離の意味で)$\epsilon$だけ離れているといいます (ここで$x\sim\Omega$は$x$が$\Omega$上の一様分布に従って選ばれることを意味する). 従って, 関数$E$を使って$D$を一様分布から$\epsilon$のアドバンテージで識別することができます. このことを統計的に識別できるといいます. 逆に, そのような$E$が存在しないとき, 分布$D$はいかなる事象でも一様分布と区別がつきません.

2.2. 識別不可能性の恩恵: 暗号

あるメッセージを暗号化して送信するとしましょう. 暗号化された文は敵対者に対してその内容がわからないようになっている必要があります. 文の構造に何かしらの特徴があるとそこから何かしらの情報が引き出されてしまうため, 暗号文は何も特徴を持たないものであることが望ましいです. もしも暗号文は敵対者にとって「ランダム文字列」と識別できないという性質を持つならばこの課題はクリアされます (完全にランダムな文字列からは長さ意外の情報を何も抜き出せないいため). 例えば長さ$n$の文字列$x\in\{0,1\}^n$に対して, 長さ$n$の一様ランダムな文字列$r\in\{0,1\}^n$を生成して$x\oplus r$を暗号文としてみましょう ($x\oplus r$は各ビットごとにXORをとって得られる文字列). $r$が一様ランダムなので$x\oplus r$も一様ランダムとなり, もし敵対者が$r$を知らないとするとこの暗号化は条件をクリアしています.

しかし受信者は$n$ビットの文字列$r$をあらかじめ知っている必要があり, そもそも$r$を敵対者に知られずに共有できるならば$x$そのものを共有すれば良いことになるので, この手法は用途が非常に限られてしまいます. 実は, 統計距離を用いた識別不可能性を満たす暗号を構成するにはメッセージと同じ長さのランダムネスが必要となることが知られており, この問題点は解消できません.

2.3. 計算論的な識別不可能性

このような統計距離に基づく識別不可能性の現実味を削ぐ要因の一つには, 任意の識別者(=関数$E$)を考えるという点にあります. 実際には, 敵対者の計算能力は無限ではない(例えば多項式時間アルゴリズム)を想定すれば良いです. 従って分布の識別可能性を

ある効率的に計算できる関数$E\colon\Omega\to\{0,1\}$が存在して

\begin{align*}
|\mathbf{E}_{x\sim D}[E(x)] - \mathbf{E}_{x\sim \Omega}[E(x)]| > \epsilon
\end{align*}

によって定義すれば異なる結果が期待されます. このことを計算論的に識別できるといい, 計算論的に一様分布と区別できない分布を擬似ランダムであるといいます.

もう少しフォーマルに述べるしょう. 空間として$\Omega=\{0,1\}^k$を考え, $\{0,1\}^k$上の一様分布に従って選ばれた確率変数を$U_k$とします. 分布$D$と回路$C\colon\{0,1\}^k\to\{0,1\}$が

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

を満たすとき, $C$はアドバンテージ$\epsilon$で$D$と$U_k$を識別するといいます. また, そのような回路であってサイズ$s$であるものが存在しないとき, $D$はサイズ$s$に対して$\epsilon$-擬似ランダムであるといいます.

3. 平均時困難性と識別不可能性の関係

統計的な識別不可能性から計算論的な識別不可能性への転換は, 本質的には敵対者(=識別者$E$)の範囲を限定するということに他なりません. しかしながらこの単純な転換が実に多くの(この記事に書ききれないほど)非自明な定理を生み出します.

実はこの両者の概念はBoolean関数においてはある意味で等価であるという結果が知られており, 今回はYaoのnext-bit predictorと呼ばれる結果を紹介します.

定理 ([Yao, 1982]).

関数$f\colon \{0,1\}^k\to\{0,1\}$がサイズ$s$に対して$(1/2-\epsilon)$-困難であるとする. このとき, $z=U_k$に対して分布$(z,f(z))$はサイズ$s-O(1)$に対して$\epsilon$-擬似ランダムである.

コメント1. 逆方向 ($(z,f(z))$が擬似ランダムならば$f$は$(1/2-\epsilon)$-困難)は簡単に示せます. 実際, $f$を成功確率$1/2+\epsilon$で計算するサイズ$s$の回路を$C$とすると, 「与えられた入力$(z,b)$に対して$b\oplus f(z)$を出力する回路を考えれば$(z,b)=(z,f(z))$か$(z,b)=(z,U_1)$かどうかを$\epsilon$のアドバンテージで識別することができます.

コメント2. 興味深いことに, 関数$G\colon z\mapsto (z,f(z))$を考えると, 定理よりこの関数はランダムな$k$ビットを受け取り, 擬似ランダムな$k+1$ビットを返す関数になっています. このように, 短いランダム文字列を受け取り長い擬似ランダム文字列を返す関数を擬似乱数生成器といいます (フォーマルな定義は本記事では割愛). これは統計的な識別不可能性に基づく枠組みでは不可能です. 実際, $G$は決定的な関数なので$G(z)$のランダムネス(=エントロピー)は高々$k$ビットであり, 統計的な意味ではランダムネスを増やすことはできないからです. 計算論的な識別不可能性を考えるとある意味で「エントロピーを増やす」ことができるのが重要な利点であり, 乱択アルゴリズムの脱乱択化や弱い仮定に基づく安全な暗号プリミティブの構成に応用されています. 再度述べますが, 敵対者を効率的なアルゴリズムに限定したからこそこのようなことが可能になっているのです.

定理の証明.

対偶を示します. $(z,f(z))$と$U_{k+1}$をアドバンテージ$\epsilon$で識別するサイズ$s'$の回路を$C\colon\{0,1\}^{k+1}\to\{0,1\}$とします. 識別するので

\begin{align*}
\mathbf{E}_{z,U_1}[C(z,f(z))-C(z,U_1)] > \epsilon
\end{align*}

です (必要があれば出力ビットを反転することにより絶対値を外すことができます). 特に$U_1$は$z$とは独立な確率変数なので, 確率$1/2$で$U_1=f(z)$になったときは差が$0$になります. 従って上式を書き換えると

\begin{align*}
\mathbf{E}_z[C(z,f(z))] - \mathbf{E}_z[C(z,\overline{f(z)})] > 2\epsilon
\end{align*}

を得ます ($\overline{b}=1\oplus b$はビットの反転).

回路$P(z,r)$を$P(z,r)=C(z,r)\oplus r \oplus 1$とすると, 以下で示すように$\Pr_{z,r\sim U_1}[P(z,r)=f(z)]> 1/2+\epsilon$を得ます. これを得ると$P(z,0)$と$P(z,1)$の少なくとも一方が$f$を成功確率$>1/2+\epsilon$で計算するサイズ$s'+O(1)$の回路になっており, 証明が完了します.

$r\sim U_1$より, 確率$1/2$で$r=f(z)$となります. したがって

\begin{align*}
\Pr_{z,r}[P(z,r)=f(z)] &= \mathbf{E}_{z,r}[P(z,r)\oplus f(z)\oplus 1] \\
&= \mathbf{E}_{z,r}[C(z,r)\oplus r \oplus f(z)] \\
&= \frac{1}{2}\mathbf{E}_z[C(z,f(z))] + \frac{1}{2}\mathbf{E}_z[1-D(z,\overline{f(z)})] \\
&> \frac{1}{2}+\epsilon
\end{align*}

を得ます (3番目の等式では$r=f(z)$と$r=\overline{f(z)}$の場合分けを行っています).

(証明終)