ハードコア関数の誤解（その二） - 某理論計算機科学者の研究日誌

前回のポストの続きです．

前回紹介したGoldreich-Levinのハードコア関数はハードコア述語，つまり出力長が1ビットでした．ハードコア述語はある意味で1ビット分の擬似乱数を与えることになっています．しかし，たくさんのハードコアビットを同時に得られる方が都合が良いことが多々あります．この場合，Goldreich-Levinのハードコア述語を応用して，より長い擬似乱数列を得ることが可能です．

一番単純な方法は， $\ell$ 個の独立な付加的乱数 $r_1,r_2,...,r_\ell\in\{0,1\}^n$ と用意して， $h(x,r_1,...,r_\ell)=(\langle x,r_1\rangle,...,\langle x,r_\ell\rangle)$ とするものです．この $h$ は一方向性関数 $f'(x,r_1,...,r_\ell)=(f(x),r_1,...,r_\ell)$ に対するハードコア関数であることが示せます．

この場合には $\ell$ ビット長のハードコア関数の出力を得るために，種値である $n$ ビット乱数 $x$ 以外に $n\ell$ ビットの乱数が必要となります．なお， $\ell$ は $O(\log n)$ まで取ること，つまり出力長は $O(\log n)$ ビットまで伸ばすことが可能です．

できれば付加的に必要な乱数の量を減らした方が擬似乱数生成の観点からも嬉しいわけですが，GoldreichとLevinによって付加的乱数の量が少なくて済むハードコア関数のもっと賢い以下の構成方法が提案されています．

$h(x,r)= (\langle x,r_1\rangle,...,\langle x,r_\ell\rangle)$

ここで， $r$ は $n+\ell-1$ ビットで，各 $r_i\in\{0,1\}^n$ は $r$ の $i$ ビット目から連続した $n$ ビットです．証明はかなり複雑になりますが， $\ell\in O(\log n)$ ならばハードコアであることが示せます．（証明はGoldreichの教科書に載っています．）

前の構成方法だと $n\ell$ ビットの乱数が必要だったところをこの構成方法だと $n+\ell-1$ ビットまで減らすことができます．

次回に続きます．