疑似乱数ジェネレータ

理論計算機科学および暗号学において、ある種の統計検定のための擬似乱数生成器 (PRG)は、ランダムシードをより長い擬似乱数文字列にマッピングする決定論的な手順であり、そのクラスの統計検定では生成器の出力と一様分布を区別できません。ランダムシード自体は通常、一様分布から抽出された短いバイナリ文字列です。

文献では、さまざまな統計テストのクラスが検討されていますが、その中には、特定のサイズのすべてのブール回路のクラスがあります。このクラスに適した疑似乱数ジェネレーターが存在するかどうかは不明ですが、その存在は、ある意味では計算複雑性理論における (証明されていない) 回路下限値と同等であることがわかっています。したがって、特定のサイズのブール回路のクラスの疑似乱数ジェネレーターの構築は、現在証明されていない困難性の仮定に基づいています。

を関数のクラスとします。これらの関数は、疑似乱数生成器が騙そうとする統計的検定であり、通常はアルゴリズムです。統計的検定は、敵対者または識別器と​​呼ばれることもあります。^[1]関数の共域の表記はクリーネスターです。 ${\displaystyle {\mathcal {A}}=\{A:\{0,1\}^{n}\to \{0,1\}^{*}\}}$

を持つ関数は、内の任意の に対して、分布と間の統計的距離が最大で であり、 が上の一様分布である場合、に対してバイアスを持つ疑似乱数生成器です。 ${\displaystyle G:\{0,1\}^{\ell }\to \{0,1\}^{n}}$${\displaystyle \ell <n}$${\displaystyle {\mathcal {A}}}$ ${\displaystyle \epsilon }$${\displaystyle A}$${\displaystyle {\mathcal {A}}}$${\displaystyle A(G(U_{\ell }))}$${\displaystyle A(U_{n})}$${\displaystyle \epsilon }$${\displaystyle U_{k}}$${\displaystyle \{0,1\}^{k}}$

この量はシード長と呼ばれ、この量は疑似乱数ジェネレータの 伸縮と呼ばれます。${\displaystyle \ell}$${\displaystyle n-\ell}$

バイアスを持つ敵対者の族に対する疑似乱数生成器は、疑似乱数生成器の族です。ここで、 はバイアスとシード長を持つ敵対者に対する疑似乱数生成器です。 ${\displaystyle ({\mathcal {A}}_{n})_{n\in \mathbb {N} }}$${\displaystyle \varepsilon (n)}$${\displaystyle (G_{n})_{n\in \mathbb{N}}}$${\displaystyle G_{n}:\{0,1\}^{\ell (n)}\to \{0,1\}^{n}}$${\displaystyle {\mathcal {A}}_{n}}$${\displaystyle \varepsilon (n)}$${\displaystyle \ell (n)}$

ほとんどのアプリケーションでは、ファミリは何らかの計算モデルまたは何らかのアルゴリズムのセットを表し、シード長とバイアスが小さく、ジェネレータの出力が同じ種類のアルゴリズムによって計算できる疑似乱数ジェネレータを設計することに関心があります。 ${\displaystyle {\mathcal {A}}}$

暗号学では、このクラスは通常、入力が多項式サイズで出力が 1 ビットの回路すべてで構成され、多項式時間アルゴリズムで計算可能で、回路サイズにおけるバイアスが無視できる擬似乱数生成器の設計に関心があります。これらの擬似乱数生成器は、暗号的に安全な擬似乱数生成器 (CSPRG)と呼ばれることもあります。 ${\displaystyle {\mathcal {A}}}$

暗号的に安全な疑似乱数生成器が存在するかどうかは知られていない。その存在はP ≠ NP を意味するため、その存在を証明することは困難であり、これは広く信じられているものの、よく知られた未解決問題である。暗号的に安全な疑似乱数生成器の存在は広く信じられている。これは、存在すると信じられている任意の一方向性関数から疑似乱数生成器を構成できることが証明されているためである。 ^{[2] [3]疑似乱数生成器は、}暗号の多くのアプリケーションに必要である。

疑似乱数生成器定理は、一方向関数が存在する場合にのみ、暗号的に安全な疑似乱数生成器が存在することを示しています。

疑似乱数生成器は、暗号化において数多くの用途があります。たとえば、疑似乱数生成器は、ワンタイム パッドの効率的な類似物を提供します。暗号文が平文に関する情報を提供しないようにメッセージm を暗号化するには、使用するキーkが長さ |m| の文字列に対してランダムでなければならないことはよく知られています。完全に安全な暗号化は、キーの長さの点で非常にコストがかかります。完全なセキュリティを意味的セキュリティに置き換えると、疑似乱数生成器を使用してキーの長さを大幅に削減できます。ストリーム暗号の一般的な構成は、疑似乱数生成器に基づいています。

擬似乱数ジェネレータは、多数のメッセージを同じ鍵で安全に暗号化できる対称鍵暗号システムの構築にも使用できます。このような構築は、擬似乱数ジェネレータの概念を一般化する擬似乱数関数ファミリに基づくことができます。

1980年代には、物理​​学のシミュレーションで擬似乱数生成器を使用して数十億の要素を持つシーケンスを生成するようになりました。1980年代後半までに、3Dイジングモデルの相転移特性や拡散制限集合体の形状などの場合に、いくつかの一般的な生成器が誤った結果を生成するという証拠が得られました。その後、1990年代には、ランダムウォーク、相関関数、固有状態の局在などに基づく物理シミュレーションのさまざまな理想化が擬似乱数生成器のテストとして使用されました。^[4]

NISTは、疑似乱数ジェネレータが高品質のランダムビットを生成するかどうかをテストするためのSP800-22ランダム性テストを発表しました。Yongge Wangは、NISTテストでは弱い疑似乱数ジェネレータを検出するのに十分ではないことを示して、統計距離に基づくテスト手法LILtestを開発しました。^[5]

擬似乱数ジェネレータの主な用途は、計算結果を損なわずに、ランダム性に依存する計算をデランダム化することです。物理的なコンピュータは決定論的なマシンであり、真のランダム性を得ることは困難な場合があります。擬似乱数ジェネレータを使用すると、ランダム性をほとんどまたはまったく使用せずに、ランダム化アルゴリズムを効率的にシミュレートできます。このようなアプリケーションでは、クラスはシミュレートするランダム化アルゴリズムまたはランダム化アルゴリズムのクラスを記述し、目標は、シード長が可能な限り短い「効率的に計算可能な」擬似乱数ジェネレータを設計することです。完全なデランダム化が必要な場合は、ランダム化アルゴリズムへのランダム入力を擬似乱数ジェネレータによって生成された擬似乱数文字列に置き換えることで、完全に決定論的なシミュレーションが進行します。シミュレーションは、すべての可能なシードに対してこれを実行し、ランダム化アルゴリズムのさまざまな実行の出力を適切な方法で平均化します。 ${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {A}}}$

計算複雑性理論における基本的な問題は、決定問題に対するすべての多項式時間 ランダム化アルゴリズムが多項式時間で決定論的にシミュレートできるかどうかです。このようなシミュレーションが存在するということは、 BPP = Pであることを意味します。このようなシミュレーションを実行するには、入力の長さがnで 1 ビットを出力するサイズs ( n ) のすべての回路のファミリFに対して疑似乱数ジェネレータを構築すれば十分です。ここで、 s ( n ) は任意の多項式、疑似乱数ジェネレータのシード長は O(logn )、バイアスは ⅓ です。

1991 年、Noam NisanとAvi Wigderson は、これらの特性を持つ擬似乱数生成器の候補を提供しました。1997 年、Russell ImpagliazzoとAvi Wigderson は、長さnの入力に対して 2 ^{O( n )}の時間で計算できるが、サイズ 2 ^{Ω( n )の}回路を必要とする決定問題が存在すると仮定すると、 Nisan と Wigdersonの構築は擬似乱数生成器であることを証明しました。

ニサン・ウィグダーソン生成器が時間制限のあるマシンで機能することを証明するには、回路の複雑さに関する証明されていない仮定が必要ですが、そのような証明されていない仮定に頼らなくてもよいように、統計的検定のクラスをさらに制限するのが自然です。これを行ったクラスの 1 つは、作業空間が で制限されるマシンのクラスです。サビッチの定理として知られる反復二乗トリックを使用すると、すべての確率的ログ空間計算を空間 でシミュレートできることは簡単に示すことができます。Noam Nisan (1992) は、このランダム化解除が、すべての -空間マシンを騙すシード長 の疑似乱数生成器で実際に達成できることを示しました。ニサンの生成器は、確率的ログ空間計算を空間 で決定論的にシミュレートできることを示すために、Saks と Zhou (1999) によって使用されました。この結果は、2021 年に William Hoza によって空間 に改善されました。 ${\displaystyle O(\log n)}$${\displaystyle O(\log^{2}n)}$${\displaystyle O(\log^{2}n)}$${\displaystyle O(\log n)}$${\displaystyle O(\log ^{1.5}n)}$${\displaystyle O(\log ^{1.5}n/{\sqrt {\log \log n}})}$

統計的検定が有限体上のすべての多変量線形関数で構成される場合、イプシロンバイアス生成器と呼ばれます。Naor & Naor (1990) の構築では、定数因子まで最適なシード長 が実現されます。線形関数の疑似乱数生成器は、より複雑な疑似乱数生成器の構成要素として使用されることがよくあります。 ${\displaystyle \mathbb {F} }$${\displaystyle \ell =\log n+O(\log(\epsilon ^{-1}))}$

Viola (2008) は、小さなバイアスを持つ生成子の合計を取ると次数 の多項式が騙されることを証明しています。シードの長さは です。 ${\displaystyle d}$${\displaystyle d}$${\displaystyle \ell =d\cdot \log n+O(2^{d}\cdot \log(\epsilon ^{-1}))}$

単一の出力ビットを生成する一定深度の回路。 ^[要出典]

暗号や普遍的アルゴリズムによるランダム化解除に使われる疑似乱数生成器は、その存在が広く信じられているものの、その存在は証明されていない^{[要出典] 。その存在を証明するには、特定の明示的な関数の}回路の複雑さの下限を証明する必要がある。このような回路の下限は、暗号疑似乱数生成器のより強力な変種の存在を前提とする自然証明の枠組みでは証明できない。^[6]

• Sanjeev Arora と Boaz Barak、「計算複雑性: 現代的アプローチ」、Cambridge University Press (2009)、ISBN 9780521424264。 
• Oded Goldreich、「計算複雑性：概念的観点」、Cambridge University Press (2008)、ISBN 978-0-521-88473-0。 
• Oded Goldreich、『暗号化の基礎：基本ツール』、Cambridge University Press (2001)、ISBN 9780521791724。 
• Naor, Joseph; Naor, Moni (1990)、「小さなバイアスの確率空間: 効率的な構築と応用」、第 22 回 ACM コンピューティング理論シンポジウム議事録 - STOC '90、pp. 213–223、CiteSeerX  10.1.1.421.2784、doi :10.1145/100216.100244、ISBN 978-0897913614、S2CID  14031194
• Viola, Emanuele ( 2008)。「d 個の小さなバイアス生成器の合計は次数 D の多項式をだます」。2008 年 23 回 IEEE 計算複雑性会議(PDF) 。pp . 124–127。CiteSeerX 10.1.1.220.1554。doi :  10.1109/CCC.2008.16。ISBN 978-0-7695-3169-4。
• この記事には、Creative Commons Attribution-Share-Alike Licenseに基づいてライセンスされているPlanetMathの擬似乱数ジェネレーターの資料が組み込まれています。