擬似乱数生成器から乱数抽出器へ - 某理論計算機科学者の研究日誌

今，Emanuele Viola の論文(Computational Complexity, 2004)を読んでいるのですが，その中に Trevisan の有名な結果*1，擬似乱数生成器(pseudorandom generator: PRG)から乱数抽出器(extractor)を構成できることの証明の解説が載っていました．案外単純だったので紹介しようと思います．この擬似乱数生成器は所謂暗号論的なものではなくて，Nisan-Wigderson タイプの derandomization に利用するためのものです．このタイプの擬似乱数生成器はクラス $E$ で計算可能な難しい関数 $f$ を利用して擬似乱数生成器 $G^f$ を構成します．まずいくつかの定義から始めましょう．以下， $U_n$ でnビットの一様乱数に従う確率変数を表すとします．

定義 1. 擬似乱数生成器(Pseudorandom Generator; PRG)

${\cal C}$ を回路集合とする．サイズが $n$ 以下の任意の $C\in{\cal C}$ に対して，
$\left|\Pr(C(G(U_u))=1)-\Pr(C(U_n)=1)\right|\le\varepsilon$
ならば関数 $G:\{0,1\}^u\rightarrow\{0,1\}^n$ を ${\cal C}$ に対する $(n,\varepsilon)$ -擬似乱数生成器と呼ぶ．

定義 2. 乱数抽出機(Extractor)

もし最小エントロピーが $k$ 以上の任意の確率変数 $X$ と任意の $T\subseteq\{0,1\}^n$ に対して
$\left|\Pr(E(X,U_u)\in T)-\Pr(U_n\in T)\right|\le\varepsilon$
が成立するならば $E:\{0,1\}^m\times\{0,1\}^u\rightarrow\{0,1\}^n$ を $(k,\varepsilon)$ -乱数抽出器と呼ぶ．

定義 3. blackbox PRG 構成

$\left|\Pr(A(G^f(U_u))=1)-\Pr(A(U_n)=1)\right|\ge\varepsilon$
を満たす任意の関数 $f:\{0,1\}^l\rightarrow\{0,1\}$ と任意のアルゴリズム $A:\{0,1\}^n\rightarrow\{0,1\}$ に対して，サイズ $s$ 以下のオラクル回路 $C$ が存在して $C^A(x)=f(x)$ となるならば， $G^f:\{0,1\}^u\rightarrow\{0,1\}^n$ を $(l,s,\varepsilon)$ -blackbox PRG 構成であるという．

定理 (Trevisan, 2001)

$G^f:\{0,1\}^u\rightarrow\{0,1\}^n$ を $(l,s,\varepsilon)$ -blackbox PRG 構成とする． $E:\{0,1\}^{2^l}\times\{0,1\}^u\rightarrow\{0,1\}^n$ を $E(x,y):=G^x(y)$ で定義する．このとき， $E$ は $(O(s\log{s})+\log(1/\varepsilon),2\varepsilon)$ -乱数抽出器である．

証明対偶をとって証明する．つまり，ある $T\subseteq\{0,1\}^n$ が存在して $\left|\Pr_{U_u}(E(X,U_u)\in T)-\Pr_{U_n}(U_n\in T)\right|>2\varepsilon$ を満たす確率変数 $X$ を考え， $X$ の最小エントロピーが $O(s\log{s})+\log{1/\varepsilon}$ 未満であることを示す．

$X$ の性質から
$\Pr_X\left(\left|\Pr_{U_u}(E(X,U_u)\in T)-\Pr_{U_n}(U_n\in T)\right|\ge\varepsilon\right)>\varepsilon$
であることは直ちに分かる． $\left|\Pr_{X,U_u}(E(X,U_u)\in T)-\Pr_{U_n}(U_n\in T)\right|\ge\varepsilon$ を満たす任意の $x$ について blackbox PRG 構成の性質よりサイズ $s$ 以下のオラクル回路 $C$ が存在して $C^T=x$ が成り立つ．（つまり $x$ と $T$ を関数としてみたときに任意の $z$ に対して $C^T(z)=x(z)$ ．）

そのような $x$ の数はサイズ $s$ 以下の回路の数で押さえられる．その回路数の上界は $2^{O(s\log{s})}$ で与えられる．したがって，確率変数 $X$ は $\varepsilon$ 以上の確率でサイズ $2^{O(s\log{s})}$ 以下の集合に属する．最小エントロピーの定義より，このことは $X$ の最小エントロピーが $O(s\log{s})+\log{1/\varepsilon}$ 未満であることを意味する．■

この定理の主張が面白いところは擬似乱数生成器という計算量理論的概念と乱数抽出器という情報理論的概念を上手く結びつけたところにあると思います． blackbox PRG 構成の定義で識別器 $A$ の計算量は考えていないという点では計算量的なところをある程度捨ててはいますが，オラクル回路のサイズと集合のサイズを対応付けるというのは非常に優れたアイデアです．

*1:Fortnow の Favorite Theorems Recap(2004年)の一つにも選ばれています．