擬似乱数生成器(pseudorandom generator)とは、短い一様な乱数の種を決定的な多項式時間の計算で長い列に引き伸ばし、その出力が多項式時間のどの識別者にも一様な乱数と見分けられない写像である。Yao の定理により、この性質は、先頭の何ビットかから次のビットを当てられないことと同値になる。擬似乱数生成器は一方向関数であり、逆に一方向置換とその内積によるハードコアビットを使うと、繰り返しの適用で擬似乱数生成器が作れる。存在すれば $\mathrm{P}\ne\mathrm{NP}$ が従うので、暗号や乱択アルゴリズムの理論では存在を仮定として使う。
擬似乱数生成器(pseudorandom generator)とは、短い一様な乱数の列(種)を、決定的な多項式時間の計算で長い列に引き伸ばし、しかもその出力が、多項式時間で動くどの検定にも一様な乱数の列と見分けられないものである。暗号や乱択アルゴリズムで、乱数の代わりに使える列の数学的な定義を与える。線形合同法のように状態を更新して数を作る規則そのものも擬似乱数生成器と呼ぶことがある(擬似乱数)が、この記事では上の計算量的な意味に限る。
シミュレーションで使う線形合同法などの 擬似乱数 は、統計的な検定には通っても、少数の出力から以後の値が予測できてしまう。計算の手間を制限しない検定は、種が出力より短いどの生成器も見分けてしまう(擬似乱数 の定理「計算の手間を制限しない検定」)。そこで検定を多項式時間のものに限るのが Yao の定義である。Blum と Micali は代わりに「先頭の何ビットかから次のビットを当てられない」ことを要求した。Yao の定理は、この 2 つの定義が同値であることを主張する。
擬似乱数生成器が存在するかどうかは、AB07(2007 年の版)の時点で分かっていない。存在すれば $\mathrm{P}\ne\mathrm{NP}$ が従うからである(thm-prg-owf の後の注意)。存在は 一方向関数(計算は易しいが逆は難しい関数)の存在と同値であることが知られている。この記事では、定義を述べ、Yao の定理と、擬似乱数生成器が一方向関数であることを証明し、一方向置換とハードコアビットから擬似乱数生成器を作る構成を、ハードコアビットの存在(Goldreich–Levin の定理)を認めて証明する。
以下、$U_m$ は $\{0,1\}^m$ 上の一様分布に従う列を表し、同じ式に現れる $U$ どうしと算法の乱数は独立とする。算法は乱数を使ってよく、時間が入力の長さの多項式でおさえられるものを 確率的な多項式時間の算法 という(確率的アルゴリズム)。各算法には、長さの目安 $n$ を $1^n$($1$ を $n$ 個並べた列)として入力に添える。
関数 $\varepsilon\colon\mathbb N\to[0,1]$ が 無視できる とは、どの正の整数 $c$ についても、十分大きなすべての $n$ で $\varepsilon(n)< n^{-c}$ となることをいう。
$\varepsilon$ が無視できないとは、ある $c$ について $\varepsilon(n)\ge n^{-c}$ となる $n$ が無限にあることである。無視できる関数の和や、多項式を掛けたものも無視できる。
$\ell\colon\mathbb N\to\mathbb N$ を $\ell(n)>n$ を満たす関数とする。各 $s\in\{0,1\}^n$ に $G(s)\in\{0,1\}^{\ell(n)}$ を対応させる写像 $G$ で、決定的な多項式時間の算法で計算できるものを考える。確率的な多項式時間の算法 $D$(識別者)について
$$
\mathrm{Adv}_D(n):=\bigl|\Pr[D(1^n,G(U_n))=1]-\Pr[D(1^n,U_{\ell(n)})=1]\bigr|
$$
を $D$ の 優位度 という。どの識別者についても優位度が無視できるとき、$G$ を 擬似乱数生成器 といい、$\ell$ をその 伸長 という(AB07 Definition 10.11、pp. 193–194)。
$G$ は多項式時間で計算できるので、伸長 $\ell(n)$ は $n$ の多項式以下である。
$G$ を def-prg-def の写像とする。確率的な多項式時間の算法 $A$(予測者)は、$1^n$、位置 $i$、$\ell(n)$ ビットの列の先頭 $i$ ビットを受け取り、1 ビットを出力する。$I$ を $\{0,1,\dots,\ell(n)-1\}$ 上の一様分布に従う位置、$y:=G(U_n)$ とし、
$$
\Pr\bigl[A(1^n,I,y_1\cdots y_I)=y_{I+1}\bigr]\le\frac12+\varepsilon_A(n)
$$
となる無視できる $\varepsilon_A$ がどの予測者 $A$ にもあるとき、$G$ は 次ビット予測不能 であるという(Blum–Micali。AB07 Definition 10.9、p. 193)。
各 $x\in\{0,1\}^n$ に列 $f(x)$ を対応させる写像 $f$ で、決定的な多項式時間の算法で計算できるものが 一方向関数 であるとは、どの確率的な多項式時間の算法 $I$(逆算者)についても
$$
\Pr\bigl[f(I(1^n,f(U_n)))=f(U_n)\bigr]
$$
(ここで 2 つの $U_n$ は同じもの。$I$ の出力が長さ $n$ でなければ失敗と数える)が無視できることをいう。$f$ が各 $\{0,1\}^n$ の全単射でもあるとき 一方向置換 という(AB07 Definition 10.1、p. 189)。
逆算者は $f(x)$ の逆像のどれか 1 つを見つければ成功とする。一方向関数の候補として、2 つの $n$ ビットの素数の積をとる関数(逆は 素因数分解)や、法 $p$ の冪 $x\mapsto g^x\bmod p$(逆は 離散対数)がある。これらが一方向であることは AB07(2007 年の版)の時点で証明されておらず、それぞれの問題が難しいという仮定に依存する(AB07 §10.1、pp. 189–191)。
def-prg-def の写像 $G$ について、$G$ が擬似乱数生成器であることと、$G$ が次ビット予測不能であることは同値である(AB07 Theorem 10.12、pp. 194–196)。
「予測できる」から「見分けられる」を出すのは易しい。逆向きの証明の要は、出力の先頭 $i$ ビットだけを本物にし、残りを一様な乱数にした 混成分布 を $i=0,1,\dots,\ell$ と並べ、隣どうしの差に優位度を割り振ることである。この論法を 混成論法(hybrid argument)という。
擬似乱数生成器なら予測不能。 対偶を示す。予測者 $A$ が確率 $\frac12+\varepsilon(n)$ で当たり、$\varepsilon$ が無視できないとする。識別者 $D(1^n,y)$ を次で定める:位置 $i\in\{0,\dots,\ell(n)-1\}$ を一様に選び、$A(1^n,i,y_1\cdots y_i)$ が $y_{i+1}$ に等しければ $1$ を出力する。$y=G(U_n)$ のとき、$D$ が $1$ を出す確率は $A$ の当たる確率 $\frac12+\varepsilon(n)$ そのものである。$y=U_{\ell(n)}$ のとき、$y_{i+1}$ は $A$ に渡す入力とも $A$ の乱数とも独立な一様なビットなので、$D$ が $1$ を出す確率は $\frac12$ である。よって $\mathrm{Adv}_D(n)=\varepsilon(n)$ は無視できず、$G$ は擬似乱数生成器でない。
予測不能なら擬似乱数生成器。 これも対偶を示す。識別者 $D$ の優位度が無視できないとし、$\ell=\ell(n)$ と書く。$s$ を $\{0,1\}^n$ 上一様、$u_1,\dots,u_\ell$ を一様なビットとし(すべて独立)、$y=G(s)$ とおく。$i=0,\dots,\ell$ について 混成分布
$$
H_i:=(y_1,\dots,y_i,\,u_{i+1},\dots,u_\ell)
$$
を考え、$q_i:=\Pr[D(1^n,H_i)=1]$ とおく。$H_0$ は $U_\ell$、$H_\ell$ は $G(U_n)$ と同じ分布なので、$\mathrm{Adv}_D(n)=\lvert q_\ell-q_0\rvert$ である。
まず符号をそろえる。ある正の整数 $c$ について $\lvert q_\ell-q_0\rvert\ge n^{-c}$ となる $n$ が無限にある。そのうち $q_\ell-q_0\ge n^{-c}$ となる $n$ が無限にあるか、$q_0-q_\ell\ge n^{-c}$ となる $n$ が無限にあるかのどちらかである。後者なら $D$ を「$D$ の出力を反転したもの」に取り替えると、$q_i$ が $1-q_i$ に変わり前者になる。以下、前者とする。
予測者 $A(1^n,i,y_1\cdots y_i)$ を次で定める:一様なビット $u_{i+1},\dots,u_\ell$ を選び、$z:=(y_1,\dots,y_i,u_{i+1},\dots,u_\ell)$ について $D(1^n,z)=1$ なら $u_{i+1}$ を、$D(1^n,z)=0$ なら $1-u_{i+1}$ を出力する。つまり「$D$ が本物らしいと判定したら、自分の置いた $u_{i+1}$ が正しかったとみなす」。
位置 $i$ を固定して当たる確率を計算する。$u_{i+1}$ は $s$ とほかのビットと独立なので、事象 $u_{i+1}=y_{i+1}$ の確率は $\frac12$ で、この事象のもとで $z$ は $H_{i+1}$ と同じ分布に従う。事象 $u_{i+1}\ne y_{i+1}$ のもとで $z$ は、$H_{i+1}$ の第 $i+1$ ビットを反転した分布 $H_{i+1}'$ に従う。$q_{i+1}':=\Pr[D(1^n,H_{i+1}')=1]$ とおくと
$$
\Pr[A\text{ が当たる}\mid i]=\frac12q_{i+1}+\frac12\bigl(1-q_{i+1}'\bigr).
$$
一方 $H_i$ は、確率 $\frac12$ ずつで $H_{i+1}$ と $H_{i+1}'$ を混ぜた分布なので $q_i=\frac12q_{i+1}+\frac12q_{i+1}'$、すなわち $q_{i+1}'=2q_i-q_{i+1}$ である。代入して
$$
\Pr[A\text{ が当たる}\mid i]=\frac12+q_{i+1}-q_i.
$$
$i$ は $\{0,\dots,\ell-1\}$ 上一様なので、平均をとると和が打ち消し合い
$$
\Pr[A\text{ が当たる}]=\frac12+\frac1\ell\sum_{i=0}^{\ell-1}(q_{i+1}-q_i)=\frac12+\frac{q_\ell-q_0}{\ell}.
$$
これは無限に多くの $n$ で $\frac12+n^{-c}/\ell(n)$ 以上である。$\ell(n)$ は $n$ の多項式以下なので、この超過分は無視できない。$A$ は $D$ を 1 回呼ぶだけなので確率的な多項式時間で動く。よって $G$ は次ビット予測不能でない。
識別者を予測者に変えると、優位度は $\ell(n)$ 分の 1 に減る。この損失は多項式なので、無視できるかどうかには影響しない。
$G$ を伸長 $\ell(n)\ge2n$ の擬似乱数生成器とする。$G$ を各 $\{0,1\}^n$ 上の写像とみると、$G$ は一方向関数である(AB07 §10.3、p. 196 で Theorem 10.13 の易しい向きとして述べられている)。
逆算者 $I$ が確率 $\varepsilon(n)$ で $G$ の逆像を見つけ、$\varepsilon$ が無視できないとする。識別者 $D(1^n,y)$ を、$x:=I(1^n,y)$ を求め、$x$ の長さが $n$ で $G(x)=y$ なら $1$ を出力するものと定める。$y=G(U_n)$ のとき $D$ が $1$ を出す確率は $\varepsilon(n)$ である。$y=U_{\ell(n)}$ のとき、$D$ が $1$ を出すには $y$ が $G$ の像に入る必要があり、像の元は高々 $2^n$ 個なので、その確率は $2^n/2^{\ell(n)}\le2^{-n}$ 以下である。よって $\mathrm{Adv}_D(n)\ge\varepsilon(n)-2^{-n}$ で、$2^{-n}$ は無視できるから、この優位度は無視できない。これは $G$ が擬似乱数生成器であることに反する。
伸長が $n+1$ のように短い擬似乱数生成器からも、出力の一部を種として繰り返し使うことで伸長 $2n$ の擬似乱数生成器が作れる(BS23 Theorem 3.3、p. 59)。この記事では証明しない。これと thm-prg-owf を合わせると、擬似乱数生成器が 1 つでも存在すれば一方向関数が存在する。逆に一方向関数が存在すれば擬似乱数生成器が存在する(Håstad–Impagliazzo–Levin–Luby。AB07 Theorem 10.13、p. 196)。この向きはこの記事では証明せず、次節で一方向「置換」からの易しい場合を扱う。
注意($\mathrm{P}=\mathrm{NP}$ なら擬似乱数生成器はない)。 $G$ を伸長 $\ell(n)>n$ の写像とする。言語 $\{(1^n,y):\text{ある }x\in\{0,1\}^n\text{ で }G(x)=y\}$ は NP に属する($x$ が証拠になる)。$\mathrm{P}=\mathrm{NP}$ なら、この言語を判定する決定的な多項式時間の算法 $D$ がある。$D$ は $G(U_n)$ には必ず $1$ を出し、$U_{\ell(n)}$ には確率 $2^{n-\ell(n)}\le\frac12$ 以下でしか $1$ を出さないので、優位度は $\frac12$ 以上である。よって擬似乱数生成器が存在すれば $\mathrm{P}\ne\mathrm{NP}$ である(P対NP問題)。$\mathrm{P}\ne\mathrm{NP}$ は AB07(2007 年の版)の時点で証明されておらず、したがって擬似乱数生成器の存在もその時点で証明されていない。暗号や乱択アルゴリズムの理論では、存在を仮定として使う。
$x,r\in\{0,1\}^n$ の 内積 を $x\odot r:=\sum_{k=1}^nx_kr_k\bmod2$ と書く(内積 の $\mathbb F_2$ 版)。$f$ が一方向置換なら、$f(x)$ と $r$ から $x$ は求められない。しかし $x$ の特定のビット、たとえば $x_1$ は $f(x)$ から読めてしまうかもしれない(ex-prg-why-inner)。ところが、乱数 $r$ で選んだビットの和 $x\odot r$ は予測できない。これが次の定理である。
$f$ を一方向置換とする。どの確率的な多項式時間の算法 $B$ についても、$x,r$ を $\{0,1\}^n$ 上一様かつ独立にとるとき
$$
\Pr\bigl[B(1^n,f(x),r)=x\odot r\bigr]\le\frac12+\varepsilon_B(n)
$$
となる無視できる $\varepsilon_B$ がある(AB07 Theorem 10.14、p. 197 の漸近的な形)。
この定理はこの記事では証明しない(証明は AB07 §10.3.1、pp. 197–199)。$x\odot r$ のように、$f(x)$ から予測できないビットを $f$ の ハードコアビット という。これを認めると、一方向置換を繰り返し適用して擬似乱数生成器が作れる。
$f$ を一方向置換、$N=N(n)\ge n$ を $n$ の多項式とする。$x,r\in\{0,1\}^n$ に対し
$$
G(x,r):=\bigl(r,\ f^N(x)\odot r,\ f^{N-1}(x)\odot r,\ \dots,\ f(x)\odot r,\ x\odot r\bigr)
$$
と定める($f^j$ は $f$ の $j$ 回の合成、$f^0(x)=x$)。$G$ は長さ $2n$ の種を長さ $n+N+1>2n$ の列に写す擬似乱数生成器である(AB07 Theorem 10.16、p. 199。同書の定理は出力を逆の順に並べた形で、証明の中でこの記事の形に直している)。
種の長さが奇数 $2n+1$ のときは、最後の 1 ビットを出力の末尾にそのまま付け足す。識別者は付け足したビットを自分で一様に作れるので、擬似乱数性は変わらない。
$G$ は $f$ を $N$ 回計算するだけなので多項式時間で計算できる。thm-prg-yao により、$G$ が次ビット予測不能であることを示せばよい。予測者 $A$ が、一様な位置 $i\in\{0,\dots,n+N\}$ で確率 $\frac12+\varepsilon(n)$ で当たるとし、$\varepsilon$ が無視できないとして矛盾を導く。
出力の位置を数える。位置 $0,\dots,n-1$ の次のビットは $r$ のビットで、それより前のビットは $r$ の先頭部分だけである。$r$ の各ビットは先頭部分と独立に一様なので、これらの位置では $A$ は確率ちょうど $\frac12$ で当たる。位置 $n+j$($j=0,\dots,N$)の次のビットは $f^{N-j}(x)\odot r$ で、それより前は $r$ と $f^N(x)\odot r,\dots,f^{N-j+1}(x)\odot r$ である。位置 $n+j$ で当たる確率を $\frac12+\varepsilon_j$ と書くと、位置の選び方は一様なので
$$
\varepsilon(n)=\frac{1}{n+N+1}\sum_{j=0}^{N}\varepsilon_j.
$$
$f(x')$ と $r$ から $x'\odot r$ を当てる算法 $B(1^n,w,r)$ を作る($w=f(x')$)。$B$ は $j\in\{0,\dots,N\}$ を一様に選び、
$$
r,\quad f^{j-1}(w)\odot r,\quad f^{j-2}(w)\odot r,\quad\dots,\quad f^{0}(w)\odot r
$$
($j=0$ なら $r$ だけ)を作って $A$ に位置 $n+j$ の先頭部分として渡し、$A$ の答えを出力する。$w$ に $f$ を高々 $N$ 回適用するだけなので、$B$ は多項式時間で動く。
$B$ の入力の分布を調べる。$x'$ を一様とし、$x:=f^{-(N-j)}(x')$ とおく。$f$ は各 $\{0,1\}^n$ の全単射なので $x$ も一様で、$r$ と独立である。$t=1,\dots,j$ について $f^{N-j+t}(x)=f^t(x')=f^{t-1}(w)$ なので、$B$ が作った列は $G(x,r)$ の位置 $n+j$ より前の部分そのもので、当てるべきビットは $f^{N-j}(x)\odot r=x'\odot r$ である。よって
$$
\Pr[B\text{ が当たる}]=\frac{1}{N+1}\sum_{j=0}^{N}\Bigl(\frac12+\varepsilon_j\Bigr)=\frac12+\frac{n+N+1}{N+1}\varepsilon(n)\ge\frac12+\varepsilon(n).
$$
$\varepsilon$ は無視できないので、これは thm-prg-gl に反する。
$f$ の逆像を $B$ が計算する必要はない点が要である。$B$ は $x'$ より「後」の値 $f(x'),f^2(x'),\dots$ だけを使い、出力では後の値ほど前に並べてある。だから予測者に渡す先頭部分は前向きの計算で作れる。
$g$ を長さ $n-1$ の列の一方向置換とし、$f(x):=x_1\,g(x_2\cdots x_n)$(先頭のビットはそのまま、残りに $g$ を適用)とおく。$f$ も一方向置換である。実際、$f$ の逆算者があれば、$y$ の前に一様なビットを付けて渡すことで $g$ の逆算者が作れる。ところが $f^k(x)$ の先頭のビットはつねに $x_1$ なので、ハードコアビットの代わりに「先頭のビット」を使った列 $(f^N(x)_1,\dots,f(x)_1,x_1)$ は同じビットの繰り返しになり、2 番目以降のビットは確率 $1$ で予測できる。$f(x)$ から $x$ の何かが漏れていても、乱数 $r$ との内積はその漏れを避ける。
Kolmogorov複雑性 の意味では、擬似乱数生成器の出力 $G(s)$ は少しもランダムでない。$G$ を固定すると、$G(s)$ は $s$ から計算できるので、その複雑性は $n+O(1)$ 以下で、長さ $\ell(n)$ よりずっと小さい。短い記述があるかどうかを調べる検定は、時間に制限がなければ擬似乱数を見破る。擬似乱数生成器の定義は「乱数らしさ」を観測者の計算能力に相対化したもので、多項式時間の観測者には圧縮できる構造が見えない、という主張である。
| 外す仮定 | 反例 | 成り立たなくなること |
|---|---|---|
| 識別者が多項式時間(def-prg-def) | 「$y$ が $G$ の像に入れば $1$」という識別者 | 伸長 $\ell(n)>n$ のどの $G$ も優位度 $1-2^{n-\ell(n)}$ 以上($\frac12$ 以上)で見分けられ、擬似乱数生成器が 1 つもなくなる |
| 伸長 $\ell(n)\ge2n$(thm-prg-owf。def-prg-def の $\ell(n)>n$ も外れ、見分けられないことだけが残る) | 恒等写像 $G(s)=s$($\ell(n)=n$) | 出力は一様分布そのもので、どの識別者の優位度も $0$ だが、$I(1^n,y)=y$ が逆算するので一方向関数でない。結論が成り立たない |
| 全位置で予測できない(thm-prg-yao) | $G(s)=0\,s$ で、最後の位置だけを予測させる | 最後のビット $s_n$ は先頭部分と独立で当たる確率は $\frac12$ だが、先頭が $0$ かを見る識別者の優位度は $\frac12$。結論の擬似乱数性が成り立たない |
| $f$ が一方向(thm-prg-construction) | $f$ を恒等写像にする | 出力は $(r,x\odot r,\dots,x\odot r)$ で、位置 $n+1$ 以降は直前のビットの写しなので確率 $1$ で予測できる。結論が成り立たない |
| ハードコアビットに内積を使う(thm-prg-construction) | ex-prg-why-inner の $f$ と先頭のビット | $f$ は一方向置換のまま($g$ の存在を仮定した反例)だが、出力は同じビットの繰り返しで予測できる。結論が成り立たない |
位置 $n+1,\dots,n+N$ では直前のビットを答えれば確率 $1$ で当たり、ほかの $n+1$ 個の位置($r$ のビットと位置 $n$)では $0$ を答えて確率 $\frac12$ 以上で当たる(位置 $n$ の $x\odot r$ は $r=0$ のとき必ず $0$ なので、ちょうど $\frac12$ より少し大きい)。位置は $n+N+1$ 個から一様に選ぶので、当たる確率は $\frac12+\frac{N}{2(n+N+1)}$ 以上で、$N\ge n$ なら $\frac12+\frac16$ 以上($n\ge1$)である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する