ソシャゲのガチャ、宝くじの当選番号と変動する株価、日常生活は「乱数」で満ち溢れている。「乱数」というただの2文字は想像以上に奥が深い。前回の記事ではシミュレーションなどに用いられる「疑似乱数」について紹介しました。しかし、それらの「疑似乱数」は暗号利用に適さないものでした。暗号利用する「疑似乱数」に求められる性質はどのようなものでしょうか？決定的な動作しかできないコンピュータはどのようにその「疑似乱数」を生成するのでしょうか？こういった疑問を解くために、疑似乱数の歴史を一緒に振り返りましょう。

ランダム性を定義する

疑似乱数を考えるにあたり、どのような数列を生成すれば「ランダムのように見える」かという問題に人々は直面した。1963年にKolmogorovがKolmogorov複雑性（Kolmogorov Complexity）を次のように定義した[1]。

📎 文字列$s$ の複雑性は$s$ を出力するための一番短いプログラムの長さである。

さらに、Kolmogorov複雑性が文字列 $s$ の長さ以上な場合に $s$ をランダムと呼ぶ。1951年にすでに線形合同法が提案されていたが、ランダム性の最初の定義は10年遅れてやっと現れた。線形合同法で疑似乱数列を生成する方法は擬似乱数への道のり(1) で紹介している。

例えば、pythonで0101011100を出力するには、次のように文字列0101011100をプログラムに書き込む以外ほかない（無理やり他の書き方をするとプログラムはより長くなってしまうであろう）ため0101011100はランダムな列と呼べる。

print("0101011100")

しかしKolmogorov複雑性は評価が難しく、疑似乱数を作るにはもっと使い勝手のいいランダム性の定義が必要となる。BlumとMicaliが暗号論的な疑似乱数（cryptographically strong pseudo-random bits; CSPRB）を提案した[2]。本稿では、これ以降暗号論疑似乱数を単に疑似乱数と言う。BlumとMicaliの定義は次の実験にまとめられる。

$n$ ビットの2進数を $p(n)$ ビットに伸ばす $G:\{0,1\}^n\rightarrow\{0,1\}^{p(n)}$ を決定的なアルゴリズムとする。

1. Aliceが $m\in [0,p(n))$ と $x\in \{0,1\}^n$ を一様分布にしたがってサンプリングする。
2. Aliceが $x$ を入力として $s=G(x)$ を生成して最初の $m$ ビットをBobに送る
3. Bobが１ビットの情報 $b$ を出力。

$b^\prime$を$G(x)$の $m+1$ ビット目とした場合に、$\Pr[b^\prime = b]\le\frac12+negl(n)$を満たしていれば $G$ を疑似乱数生成器と呼ぶ。

そしてYaoは独立にBlumとMicaliと同値な疑似乱数の定義を提唱した[3]。Yaoの定義は次の実験にまとめられる。

1. Aliceがコインを投げてその結果を$b\in\{0,1\}$とする。
2. Aliceが $s$ を次のルールにしたがって決める
   1. $b=0$ の場合に $s$ は一応分布にしたがってランダムに取る
   2. $b=1$ の場合にシード $x$ を一様分布にしたがってサンプリングして $G(x)$を $s$ とする
3. Aliceが $s$ をBobに送って、Bobが $b^\prime\in\{0,1\}$ を出力

$\Pr[b=b^\prime]\le \frac12+negl(n)$ を満たす時に $G$ は疑似乱数生成器と呼ぶ。

この二つの定義はYao のハイブリッド論法（hybrid argument）によって同値だと示された。Yao の定義では疑似乱数と真性乱数を見分けられないことに注目している。一方、Blum とMicali は各ビットの相関が検出できないことに注目している。

📖 Yaoの定義から「真性乱数を使う多項式時間なプログラムの中の真性乱数を使っているところを全部暗号論的な疑似乱数に置き換えても多項式時間で検証できる動作の違いがない」ことが分かる。例えばクイック・ソートのランダムにピボットを決める時に、暗号論的な疑似乱数を使ってピボットを選んでも実行時間に目立つ影響がない。

一方向性から擬似ランダム性まで

疑似乱数を作るには一方向性関数（one-way function; OWF）があれば十分である。OWF は、次の2つの条件を満たす関数 $f:\{0,1\}^n \rightarrow \{0,1\}^{poly(n)}$のことを指す。

1. 計算可能性（計算は容易である）: 任意の $x \in \{0,1\}^n$ に対して、$f(x)$ を多項式時間で計算できる。
2. 一方向性（逆関数の計算が困難である）: 任意の多項式時間アルゴリズム$A$に対して、$y=f(x)$を入力として与えた時に$y=f(x^\prime)$となるような$x^\prime$を出力する確率は$negl(n)$ を超えない。

例えば、合成数 $p$ 及び $p$ と互いに素な $q$ について、$f(x)=q^x\,\text{mod}\,p$ はOWF だと考えられている。暗号などが十分に強いと証明するために、一般的に難しいと思われる問題に暗号を解くタスクを帰着させる。例で示した関数 $f(x)$ から $x$ を復元する問題は離散対数問題そのものなためOWFだと考えられている。

しかし、OWF だけでは疑似乱数を作れない。OWF の計算的な難しさを利用して予測困難な１ビットを作りだすにはハードコア述語が役立つ。

📎 述語関数$B:\{0,1\}^*\rightarrow \{0,1\}$が 関数$f$ のハードコア述語であるとは次の二つの条件を満たしていることをいう

1. 決定性チューリングマシン $A$ が存在して、$x$ が与えられた時に $B(x)$ を多項式時間で出力できる
2. 任意の多項式時間のチューリングマシン $A$ に対して、一方向性関数 $f$ を一様ランダムに選んだ $x$ に適用した $f(x)$ を入力して $B(x)$ を正しく出力する確率は高々$\frac{1}{2}+negl(|x|)$ 。

ハードコア述語はOWF の入力に関する述語なので、OWF を適用した後その述語の値を知ることができない。

初めての疑似乱数

Blum とMicali は疑似乱数を定義したと同時に最初の疑似乱数を提案した[2]。彼らの構成では一方向性置換（OWP）という特別なOWFを利用している。置換の入力と出力は同じ集合に限定されて、分かりやすく言うと入力集合の並び替えなのだ。 $n$ ビットの入力$x$ を$poly(n)$ ビットに伸ばすには次のプロセスを行えばいい。

1. 系列$S=f^{poly(n)-1}(x),f^{poly(n)-2}(x),\dots ,f(x), x$ を生成
2. $S$ の各項に対して順次に$f$ のハードコア述語$B$ を計算して出力する

ただし$f$ はOWPとして$f^i$ は$f$ を$i$ 回適用することとする。

BlumとMicaliの疑似乱数は暗号論的に強い

仮にある$i\in [0,poly(n))$ に対して$i+1$ ビット目を$\frac{1}{2}+\frac{1}{poly(n)}$ の確率で当てられるとする。このとき、とある未知の$n$ ビットの2進数$x$ に対して$y=f(x)$ が与えられた時に次の手順で$B(x)$ が計算できてしまう。

1. $y$ にさらに$f$ を$i-1$ 回適用して毎回の計算結果を集めて$S=f^i(x),f^{i-1}(x),\dots,y$ という系列を生成する。ただし$i=0$ の時に$S$ は空列とする
2. $S$の各項について$f$ のハードコア述語を計算してビット列$S^\prime$ を生成する
3. $S^\prime$の次の１ビットを予測して$B(x)$ の推測値とする

観察によると$S$ は$f^i(x),f^{i-1}(x),\dots ,f(x),x,\dots ,f^{i-poly(n)+1}(x)$ の前から$i$ 項です。つまり$S^\prime$ は$f^{i-poly(n)+1}(x)$ を入力として$poly(n)$ ビット伸ばした擬似ランダム列の前から$i$ 項になる。したがって、$S’$ の$i+1$ ビット目は$B(x)$ であり、仮定からこれは$\frac{1}{2}+\frac{1}{poly(n)}$ の確率で求められる。ここで述べた手順は多項式時間で実行できるため、ハードコア述語の定義と矛盾する。

この議論によって彼らが提案した疑似乱数はハードコア述語が安全な限り破られないことが分かる。

全ての一方向性関数にはハードコア述語がある

Blum とMicali が提案したフレームワークは疑似乱数生成器の設計に重要なイノベーションを与えたが、ハードコア述語（hard-core predicate）の存在を前提にしている。幸いなことに、Goldreich とLevin によって全ての一方向性関数$f$ からハードコア述語が存在する一方向性関数が構成できることが明らかにされている。

1. $g(x,y)=(f(x),y)$ と新しく一方向性関数を定義する
2. $B(x,y)$ を$x$ と$y$ を2進数で表した時の2進数内積とする。つまり$x$ と$y$ が同時に1のビットの数のパリティとする。
   1. $x=1100,y=0110$の時、2ビット目しか同時に1ではない。そのため$B(1100,0110)=1$
   2. $x=1110,y=0110$の時、2ビット目と3ビット目しか同時に1ではない。そのため$B(1110,0110)=0$

📖 2進数 $x$ と $y$ の内積は $x$ と $y$ の各ビットで論理積（AND）をとった計算結果の1のビットの数のパリティとする。例えば$x=1011$かつ$y=1001$の場合、$x$と$y$のビットごとの論理積は$1001$で$1$の数は偶数のため$x$と$y$の内積は$0$である。ビットごとの論理積の$1$の数が奇数であれば内積は$1$である。

このように少しの変形で一方向性関数$g$ と$g$ のハードコア述語が作れる。$B$ が$g$ のハードコア述語であることは次のようにして確認できる。

もし$B$ がハードコア述語でなければ、あるチューリングマシン$A$ が存在してある多項式$p(x)$に対して

$$ \text{Pr}_{x,y}[A((f(x),y))=x\cdot y] \ge\frac12+\frac1{p(n)} $$

が成り立つ。これは$A$ が$f(x)$ をみて$x$ のパリティを当てられることを意味している。仮に$A$ が100%の確率で$x$ のパリティを当てられるならば、$y=1,2,4\dots2^{n-1}$ を代入することで$x$ の各ビットが分かるので$A$ を使って一方向性関数$f$ を復元できてしまう。

しかし、実際には$A$ は100%の確率で$x$ のパリティを当てられるとは限らない。その場合の証明にはアダマール符号（Hardmard Coding）が深く関連している。

📖 アダマール符号は$n$ ビットの情報を$2^n$ ビットに符号化してビット反転エラーを訂正する誤り訂正符号の1種である。任意の$x$は$s_1,s_2,\dots ,s_{2^n}$ に符号化される。ただし$s_i=i\cdot x$ とする。

もし$A$ が$B(x,y)$ を$\frac{1}{2}+\frac{1}{p(n)}$ で当てられるなら、$y=0,1,\dots,2^{n}-1$ を代入して仮想的なビット列$S=\{S_i=B(x,i)\}$ を得られる。これは、$A$ が間違った予測をした時にビット反転が起こったと考えることもできる。したがって、$S$ は次の手順で生成した列と同じであることがわかる。

1. $x$ をアダマール符号で符号化する
2. ステップ1で生成した列の各ビットを$\frac12-\frac{1}{p(n)}$ の確率で反転する

Goldreich とLevin らはlist decoding と呼ばれる復号法を提案したことによって$B$ が$g$ のハードコア述語だと証明した。list decoding を用いると $S$ の $poly(n)$ 個のビットの値だけで符号化前の $x$ を復元できる。

ここまでの議論で任意の一方向性関数$f$ から別の一方向性関数$g$ を作れて、$g$ にはハードコア述語$B$ が存在することが分かる。ハードコア述語の定義より、ハードコア述語$B$ を計算することは$f$ の逆関数を計算することより難しい。この計算複雑さによって、$g$ とハードコア述語$B$ を用いて擬似乱数が作れる。

まとめ

擬似ランダム性に関する研究は計算機が発明されたころから行われてきた。しかし、Micali とBlum が計算モデルに基づいた擬似ランダム性の定義を与えるまで、疑似乱数の設計に役立つ定義はなかった。また、その時に提案されたMicali とBlum の（暗号学的）疑似乱数とハードコア述語はのちの研究にも生かされることとなった。そして40年近くの研究の末にGoldreich とLevin がOWFを使って疑似乱数を構成することに成功した。

参考文献

1. Goldreich, O., Goldwasser, S., & Micali, S. (1986). How to construct random functions. Journal of the ACM (JACM), 33(4), 792-807.
2. Blum, M., & Micali, S. (2019). How to generate cryptographically strong sequences of pseudo random bits. In Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali (pp. 227-240).
3. Yao, A. C. (1982, November). Theory and application of trapdoor functions. In 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982) (pp. 80-91). IEEE.