擬似乱数生成定理

計算複雑性理論と暗号学では、擬似乱数生成器の存在は、擬似乱数生成器定理と総称されるいくつかの定理を通じて一方向関数の存在と関連しています。

分布は、効率的な計算によって真の一様分布と無視できない利点で区別できない場合、擬似ランダムとみなされます。正式には、分布族D _nは、任意の多項式サイズの回路Cとnの任意の逆多項式εに対して擬似ランダムです。

|確率_{x ∈ U}  [ C ( x )=1] − 確率_{x ∈ D}  [ C ( x )=1] | ≤ ε。

関数G _l : {0,1} ^l → {0,1} ^m （ただしl  <  m ）は、次の条件を満たす擬似乱数ジェネレーターである。

• G _lはlの時間多項式で計算できる
• G _l ( x ) は、 xが均一ランダムな場合、疑似ランダムです。

擬似乱数生成器G _l : {0,1} ^l → {0,1} ^{l +1}、つまり擬似乱数ビットを1つだけ追加する生成器がある場合、任意のm  = poly ( l )に対して擬似乱数生成器G' _l : {0,1} ^l → {0,1} ^mが存在することが示されます。

証明の考え方は次のとおりです。まず、均一分布U _lからsビットが選択され、疑似乱数ジェネレーターとして知られるG _lの最初のインスタンスのシードとして使用されます。次に、 G _lの最初のインスタンスの出力が2 つの部分に分割されます。最初のlビットはG _lの 2 番目のインスタンスにシードとして入力され、最後のビットが出力の最初のビットになります。このプロセスをm回繰り返すと、 m疑似乱数ビット の出力が生成されます。

G _lのm個のインスタンスで構成されるG' _lが実際に疑似乱数ジェネレーターであることは、次のように ハイブリッドアプローチと背理法による証明を使用することで示せます。

m+1 個の中間分布H _i : 0 ≤ i ≤ mを考えます。ここで、最初のiビットは均一分布から選択され、最後のm − iビットはG' _lの出力から選択されます。したがって、H _{0 は}G' _lの完全な出力であり、H _mは真の均一分布U _mです。したがって、分布H _iとH _i+1は 1 ビット (ビット番号i +1)のみ異なります。

ここで、G' _{l が}疑似ランダム分布ではないと仮定します。つまり、G' _lとU _mをε   = 1/ poly ( l )の利点で区別できる回路C が存在します。言い換えると、この回路はH ₀とH _mを区別できます。したがって、回路C がH _iとH _i+1を少なくともε / mで区別できるi が存在します。 m はlの多項式であるため、ε / mもlの多項式であり、依然として無視できない利点である ことに注意してください。

ここで、G _lの出力または一様分布から抽出されたl+1ビットが与えられていると仮定します。G _lのインスタンスから大規模な疑似乱数生成器を構築するアプローチを再利用し、最初のlビットをシードとして使用して、上でG' _lが構築されたのと同じ方法で、長さm −i−1の疑似乱数ビットの文字列を構築します。次に、一様分布から抽出されたiビットと、与えられたビットの最後の 1 つを連結し、その後に作成されたm−i−1ビットで構成される文字列を作成します。結果の出力は、i+1ビットが一様分布から抽出されるか、G _lから抽出されるかのいずれかであるため、H _iまたはH i+1 のいずれかになります。仮定により、H i と H i+1 を無視できない利点で区別できるため_、 Uと_{G l}を区別できます。_これは、 G _{l が}疑似乱数生成器ではないことを意味しますが、これは仮説と矛盾します。QED

ここで、が存在する場合、 G _lとU _l+1を区別する回路はランダムにコインを投げる必要がないことを説明しましょう。上で示したように、G' _lとU _mを区別する回路C が存在する場合(m  =  poly ( l ))、 i 個のランダム ビットを使用してG _lとU _l+1を区別する回路C' が存在します。この回路C'の場合: | Prob _{u, s} [ C' ( u ₁ ,...,u _i ,G _l ( s )) = 1 ] − Prob _{u, y} [ C' ( u ₁ ,>,...,u _i ,y ) = 1] | ≥ ε / m、

ここで、uはi 個の均一ランダム ビットの文字列、s はl 個の均一ランダム ビットの文字列、y はl +1 個の均一ランダム ビットの文字列です。

それから、

問題_u [ | 問題_s [ C' ( u ₁ ,..., u _i ,G _l ( s )) = 1] - 問題_y [ C' ( u ₁ ,..., u _i ,y ) = 1] | ] ≥ ε / m ;

つまり、 G _lとU _l+1を区別するために回路C'への「アドバイス」として使用できるiビットの固定文字列u が存在するということです。

擬似乱数生成器の存在は、一方向関数とハードコア述語の存在に関連している。形式的には、擬似乱数生成器が存在するのは、一方向関数が存在する場合、または

PRG ↔ OWF

直感的に一方向性関数とは、計算が容易で逆関数が困難な関数のことである。言い換えれば、関数の複雑さ（または回路サイズ）は、その逆関数の複雑さよりもはるかに小さい。形式的には、関数ƒ: {0,1} ⁿ → {0,1} ⁿが ( S , ε )一方向性関数であるとは、サイズ ≤ Sの任意の回路Cに対して、

Prob[ƒ( C (ƒ( x ))) = ƒ( x )] ≤  ε。

さらに、ƒ は一方向性関数であるためには、

• ƒは多項式時間で計算できる
• ƒ は ( poly ( n )、1/ poly ( n )) 一方向

関数B : {0,1} ⁿ  → {0,1}は関数ƒの ハードコア述語であり、

• Bは多項式時間で計算できる
• 任意の多項式サイズの回路Cと任意の無視できないε  = 1/ poly ( n )に対して、確率_x~U  [ C (ƒ( x )) =  B ( x )] ≤ 1/2+ ε

言い換えれば、関数ƒ( x ) からB ( x )を予測することは困難です。

ここでは証明の概要を示します。詳細な証明については参考文献を参照してください。

疑似乱数生成器G _l : {0,1} ^l → {0,1} ^{2lを考えてみましょう。G} _lの出力の前半を出力として使用する次のような一方向性関数ƒ: {0,1} ⁿ → {0,1} ^nを作成しましょう。正式には、

ƒ( x , y ) → G _l ( x )

このような選択を正当化する重要な観察は、原像宇宙のサイズが 2 ^{nであり、サイズ 2 2n}の関数の像の無視できる割合であるということです。

ƒ が確かに一方向性関数であることを証明するために、背理法による議論を構築してみましょう。 ƒ をε のアドバンテージで反転する回路C が存在すると仮定します。

Prob[ƒ( C (ƒ( x , y ))) = ƒ( x , y )] >  ε

_次に、仮説に反するG _lと Uniform を区別する次のアルゴリズムを作成できます。アルゴリズムは2nビットzの入力を受け取り、( x , y ) =  C ( z ) を計算します。G l ( x ) =  zの場合、アルゴリズムは受け入れ、そうでない場合は拒否します。

ここで、zが一様分布から抽出された場合、前像のサイズが像のサイズの1/2 ^lであるため、上記のアルゴリズムが受け入れる確率は ≤ 1/2 ^lです。しかし、 z がG _lの出力から抽出された場合、回路Cが存在するという仮定により、受け入れる確率は > εです。したがって、回路C が一様UとG _lの出力を区別する利点は> ε − 1/2 ^lであり、これは無視できないため、G _{l が}疑似乱数ジェネレータであるという仮定と矛盾します。QED

この場合、定理の 弱いバージョンを証明します。

一方向順列→ 疑似乱数生成器

一方向の順列は、入力ビットの順列でもある一方向関数です。一方向の順列 ƒ から疑似乱数ジェネレーターを次のように構築できます。

G _l : {0,1} ^l →{0,1} ^{l +1}   = ƒ( x ). B ( x )、ここでBは ƒ のハードコア述語であり、 "." は連結演算子です。上で証明された定理により、疑似乱数ビットを 1 つだけ追加するジェネレーターの存在を示すだけでよいことに注意してください。

まず、 B がƒ のハードコア述語である場合、G _{l は}確かに疑似ランダムであることを示します。ここでも、背理法を使います。

G _{l は}擬似乱数生成器ではないと仮定する。つまり、 G _l ( x ) =ƒ( x ). B ( x ) とU _l+1をε以上の優位性で区別する多項式サイズの回路Cが存在する。ここでεは無視できない。ƒ( x ) は順列であるため、x が一様分布から抽出された場合は、ƒ( x ) もそうであることに注意する。したがって、U _l+1は ƒ( x ). bと同等であり、ここでbは一様分布から独立して抽出されたビットである。正式には、

確率_x~U  [ C ( G ( x ))=1] − 確率_x~U,b~U  [ C ( xb )=1] ≥  ε

次のアルゴリズムC'を構築してみましょう。

1. z=f(x) が与えられたとき、ビット b を推測する
2. zbでCを実行する
3. C(zb)=1の場合
4. 出力b
5. その他
6. 出力1-b

ƒ の出力が与えられると、アルゴリズムは最初にランダムなコインを投げてビットb を推測します。つまり、 Prob[ b =0] = Prob[ b =1] = 0.5 です。次に、アルゴリズム (回路) Cがf(x).bに対して実行され、結果が 1 の場合はbが出力され、それ以外の場合はbの逆が返されます。

C'がB ( x )を正しく 推測する確率は次のようになります。

問題_x~U  [ C' ( z )= B ( x )] =

問題[ b = B ( x ) ∧  C ( zb )=1] + 問題[ b ≠ B ( x ) ∧  C ( zb )=0] =

問題[ b = B ( x )]⋅問題[ C ( zb )=1 | b = B ( x )] + 問題[ b ≠ B ( x )]⋅問題[ C ( zb )=0 | b ≠ B ( x )] =

1/2⋅Prob[ C ( zb )=1 | b = B ( x )] + 1/2⋅Prob[ C ( zb )=0 | b ≠ B ( x )] =

(1−1/2)⋅Prob[ C ( zb )=1 | b = B ( x )] + 1/2⋅(1−Prob[ C ( zb )=1 | b ≠ B ( x )]) =

1/2+確率_z.b~G(x)  [ C ( zb )=1] − 1/2⋅(確率[ C ( zb )=1 | b = B ( x )]+確率[ C ( zb )=1 | b ≠ B ( x )]) =

1/2+Prob _z.b~G(x)  [ C ( zb )=1] − Prob _z.b~U  [ C ( zb )=1] ≥ 1/2+ ε

これは、回路C'が1/2 + εを超える確率でB ( x )を予測できることを意味し、Bはƒのハードコア述語にはなり得ず、仮説は矛盾していることを意味します。QED

証明の概要は次のとおりです。

ƒ{0,1} ⁿ →{0,1} ⁿが一方向の順列であるならば、ƒ'{0,1} ²ⁿ →{0,1} ²ⁿも一方向の順列である。ここで、ƒ'( x , y )=ƒ( x ) 。y は定義による。すると、B ( x , y )= x ⋅ yは、ƒ' のハードコア述語であり、⋅はベクトルのドット積である。これが確かにハードコアであることを証明するために、そうでないと仮定し、ƒ が一方向であるという仮説との矛盾を示してみよう。Bがハードコア述語でなければ、それを予測する回路C が存在するので、

確率_x,y [ C (ƒ( x ), y )= x ⋅ y ] ≥ 1/2+ ε 。この事実は、 x内のビットを分離する順列y を巧みに構築することでxを復元するために使用できます。実際、xの定数分数に対して、すべての有効なxを含むO (1/ ε ² )の候補をリストする多項式時間アルゴリズムが存在します。したがって、アルゴリズムはxの無視できない分数に対して多項式時間でƒ( x ) を反転することができ、これは仮説と矛盾します。

• W. Diffie、ME Hellman。「暗号化の新しい方向性」IEEE Transactions on Information Theory、IT-22、pp. 644–654、1976 年。
• AC Yao. 「トラップドア関数の理論と応用」第 23 回 IEEE コンピュータサイエンス基礎シンポジウム、pp. 80–91、1982 年。
• M. Blum およびS. Micali「暗号的に強力な疑似ランダム ビットのシーケンスを生成する方法」SIAM Journal on Computing、v13、pp. 850–864、1984 年。
• J. Hastad、R. Impagliazzo、LA L​​evin、M. Luby。「任意の一方向関数からの疑似乱数ジェネレーター」SIAM Journal on Computing、v28 n4、pp.-1364-1396、1999 年。