ランダム性抽出器

ランダム性抽出器は、単に「抽出器」と呼ばれることが多く、弱いエントロピーソースからの出力に、短い一様ランダムシードとともに適用される関数であり、ソースから独立し、一様に分布しているように見える高度にランダムな出力を生成します。^[1] 弱いランダムソースの例には、放射性崩壊や熱雑音が含まれます。考えられるソースに対する唯一の制限は、それらを完全に制御、計算、または予測する方法がないことと、エントロピー率の下限を確立できることです。特定のソースの場合、ランダム性抽出器は真性乱数ジェネレーター ( TRNG ) と見なすこともできますが、あらゆる種類の弱いランダムソースから真にランダムな出力を生成することが証明されている単一の抽出器は存在しません。

「バイアス」という用語は、弱いランダム ソースの均一性からの逸脱を示すために使用されることがあります。古い文献では、一部の抽出器は、いわゆる「バイアス」ソースからランダム性を取得し、偏りのない分布を出力するため、バイアス除去アルゴリズムと呼ばれています。[ ^2]弱いランダム ソースは、抽出器の出力よりも常に長くなりますが、効率的な抽出器は、この長さの比率を可能な限り下げ、同時にシードの長さを低く保ちます。直感的には、これは、可能な限り多くのランダム性がソースから「抽出」されていることを意味します。

抽出器は擬似乱数生成器(PRG)と概念的に類似していますが、この 2 つの概念は同一ではありません。どちらも、小さな均一な乱数シードを入力として受け取り、均一なランダムに「見える」長い出力を生成する関数です。一部の擬似乱数生成器は、実際には抽出器でもあります。(PRG がハードコア述語の存在に基づいている場合、弱ランダム ソースをそのような述語の真理値表のセットとして考え、出力が統計的に均一に近いことを証明できます。^[3] ) ただし、一般的な PRG 定義では、弱ランダム ソースを使用する必要があるとは指定されておらず、抽出器の場合は出力が統計的に均一に近い必要がありますが、PRG では、計算上均一と区別がつかないことだけが要求されており、やや弱い概念です。

分布の最小エントロピー（ と表記）は、の範囲の任意の に対してとなる最大の実数です。本質的には、これは が最も可能性の高い値を取る可能性を測定し、ランダム性の出現頻度の最悪の境界を示します。上の一様分布をとすると、明らかに と なります。 ${\displaystyle X}$${\displaystyle H_{\infty }(X)}$${\displaystyle k}$${\displaystyle \Pr[X=x]\leq 2^{-k}}$${\displaystyle x}$${\displaystyle X}$${\displaystyle X}$${\displaystyle X}$${\displaystyle U_{\ell}}$${\displaystyle \{0,1\}^{\ell}}$${\displaystyle H_{\infty}(U_{\ell})=\ell}$

最小エントロピーkを持つnビットの分布の場合、 は分布であると言えます。 ${\displaystyle X}$${\displaystyle X}$${\displaystyle (n,k)}$

定義（抽出器）：（ k 、 ε  ）抽出器

を、分布 からのサンプルとからのdビットのシードを入力として受け取り、mビットの文字列を出力する関数とします。 は、すべての分布に対して、 の出力分布が にε近い場合、 ( k ,  ε )-抽出器です。 ${\displaystyle {\text{Ext}}:\{0,1\}^{n}\times \{0,1\}^{d}\to \{0,1\}^{m}}$${\displaystyle (n,k)}$${\displaystyle X}$${\displaystyle U_{d}}$${\displaystyle {\text{Ext}}}$${\displaystyle (n,k)}$${\displaystyle X}$${\displaystyle {\text{Ext}}}$${\displaystyle U_{m}}$

上記の定義では、 ε -close は統計距離を指します。

直感的に言えば、抽出器は弱いランダムなnビットの入力と短い均一ランダムなシードを受け取り、均一ランダムに見えるmビットの出力を生成します。目的は、 を低く(つまり、均一ランダム性をできるだけ少なくする)、 をできるだけ高く (つまり、できるだけ多くのランダムに近い出力ビットを得る) することです。 ${\displaystyle d}$${\displaystyle m}$

シードと抽出器の出力を連結しても均一に近い分布が生成される 場合、抽出器は強力です。

定義（強い抽出子）：強い抽出子は関数である ${\displaystyle (k,\epsilon )}$

${\displaystyle {\text{Ext}}:\{0,1\}^{n}\times \{0,1\}^{d}\rightarrow \{0,1\}^{m}\,}$

あらゆる分布に対して、分布（ の 2 つのコピーは同じランダム変数を表す）は上の一様分布に -近くなります。 ${\displaystyle (n,k)}$${\displaystyle X}$${\displaystyle U_{d}\circ {\text{Ext}}(X,U_{d})}$${\displaystyle U_{d}}$${\displaystyle \epsilon }$${\displaystyle U_{m+d}}$

確率的方法を使用すると、( k ,  ε )-抽出子が存在すること、つまり構築が可能であることを示すことができます。ただし、通常、抽出子が存在することを示すだけでは十分ではありません。次のように明示的な構築が必要です。

定義（明示的抽出器）：関数k ( n )、ε ( n )、d ( n )、m ( n )に対して、関数の 族Ext = {Ext _{n }}

${\displaystyle {\text{Ext}}_{n}:\{0,1\}^{n}\times \{0,1\}^{d(n)}\rightarrow \{0,1\}^{m(n)}}$

Ext( x ,  y ) が（入力長で）多項式時間で計算可能であり、すべてのnに対してExt _nが(  k ( n ),  ε ( n )) 抽出器である場合、は明示的な ( k , ε ) 抽出器です。

確率 的手法により、シード長が

${\displaystyle d=\log {(nk)}+2\log \left({\frac {1}{\varepsilon }}\right)+O(1)}$

出力長さ

${\displaystyle m=k+d-2\log \left({\frac {1}{\varepsilon }}\right)-O(1)}$^[4 ]

ランダム性抽出器のより弱い特性を持つ変形が分散器です。

暗号化の最も重要な側面の 1 つは、ランダムキーの生成です。^[5]半秘密またはある程度侵害される可能性のあるソースから秘密キーとランダム キーを生成する必要があることがよくあります。単一の短い (秘密の) ランダム キーをソースとして取得すると、抽出器を使用してより長い疑似ランダム キーを生成し、それを公開キー暗号化に使用できます。具体的には、強力な抽出器を使用すると、その出力は、ソースの一部 (すべてではない) を見た人にも均一にランダムであるように見えます。たとえば、ソースはわかっているがシードがわからない場合 (またはその逆) です。抽出器のこの特性は、一般にエクスポージャー耐性暗号化と呼ばれるもので特に役立ちます。エクスポージャー耐性暗号化では、目的の抽出器がエクスポージャー耐性関数(ERF) として使用されます。露出耐性暗号化では、暗号化アプリケーションの初期化中に頻繁に行われるデータの初期交換を秘密に保つことが困難であるという事実を考慮に入れています。たとえば、暗号化された情報の送信者は、受信者に復号化に必要な情報を提供する必要があります。

以下の段落では、 Exposure-Resilient 暗号化で有用な 2 種類の ERF ( k -ERFとk -APRF )を定義し、それらの間の重要な関係を確立します。

定義 ( k -ERF): 適応型 k-ERF は 、ランダムな入力 に対して、計算上無制限の攻撃者が、ある無視できる関数 (以下に定義) に対して、 ビットを除く のすべてを適応的に読み取ることができる関数です。 ${\displaystyle f}$ ${\displaystyle r}$ ${\displaystyle A}$ ${\displaystyle r}$ ${\displaystyle k}$ ${\displaystyle |\Pr\{A^{r}(f(r))=1\}-\Pr\{A^{r}(R)=1\}|\leq \epsilon (n)}$ ${\displaystyle \epsilon (n)}$

目標は、出力が非常にランダムで均一に分散された適応型 ERF を構築することです。ただし、すべての出力がほぼ均一な確率で発生する、より強力な条件が必要になることがよくあります。この目的のために、ほぼ完全な復元関数(APRF) が使用されます。APRF の定義は次のとおりです。

定義 (k-APRF): APRF は、入力のビットを任意の固定値に設定すると、残りのビットをランダムに選択した場合の出力の確率ベクトルが、すべてに対して、また無視できる関数に対してを満たす関数です。 ${\displaystyle k=k(n)}$ ${\displaystyle f}$ ${\displaystyle n-k}$ ${\displaystyle r}$ ${\displaystyle p}$ ${\displaystyle f(r)}$ ${\displaystyle k}$ ${\displaystyle |p_{i}-2^{-m}|<2^{-m}\epsilon (n)}$ ${\displaystyle i}$ ${\displaystyle \epsilon (n)}$

KampとZuckerman ^[6]は、関数がk -APRFであればk -ERFでもあるという定理を証明した。より具体的には、十分に小さい誤差を持ち、入力として忘却ビット固定ソースを取る抽出器はAPRFでもあり、したがってk -ERFでもある。より具体的な抽出器は、次の補題で表現される。 ${\displaystyle f}$${\displaystyle f}$

補題:が無視できる 、忘却ビット固定ソースの集合に対する任意の -抽出器も k-APRF です。${\displaystyle 2^{-m}\epsilon (n)}$ ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}$ ${\displaystyle (n,k)}$ ${\displaystyle \epsilon (n)}$

この補題はKampとZuckermanによって証明されている。^[6]この補題は出力のuniformからの距離を調べることによって証明されるが、-extractorでは明らかに最大で であり、APRFの条件を満たす。 ${\displaystyle 2^{-m}\epsilon (n)}$${\displaystyle 2^{-m}\epsilon (n)}$

この補題から次の定理が導かれ、実際に記述されているk -APRF 関数が存在することが示されます。

定理（存在）： 任意の正の定数 に対して、 およびビット文字列に対する線形数の算術演算で計算可能な明示的な k-APRF が存在する。 ${\displaystyle \gamma \leq {\frac {1}{2}}}$ ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}$ ${\displaystyle m}$ ${\displaystyle m=\Omega (n^{2\gamma })}$ ${\displaystyle k=n^{{\frac {1}{2}}+\gamma }}$

定義 (無視できる関数):この定理の証明には、無視できる関数の定義が必要です。関数は、すべての定数に対してである場合に無視できると定義されます 。 ${\displaystyle \epsilon (n)}$${\displaystyle \epsilon (n)=O\left({\frac {1}{n^{c}}}\right)}$${\displaystyle c}$

証明: 次の-抽出子を考えます。関数は、忘却ビット固定ソースの集合の抽出子です。には、、およびがあります。 ${\displaystyle \epsilon }$${\displaystyle f}$${\displaystyle (n,\delta n)}$${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}}$${\displaystyle f}$${\displaystyle m=\Omega (\delta ^{2}n)}$${\displaystyle \epsilon =2^{-cm}}$${\displaystyle c>1}$

この抽出子の存在の証明、およびそれが の長さで線形計算時間で計算可能であるという事実は、Jesse Kamp と David Zuckerman の論文 (p. 1240) に記載されています。 ${\displaystyle \delta \leq 1}$${\displaystyle m}$

この抽出器が補題の基準を満たすことは、無視できる関数であるのと同様に自明に真実です。 ${\displaystyle \epsilon =2^{-cm}}$

のサイズは次のとおりです: ${\displaystyle m}$

${\displaystyle m=\Omega (\delta ^{2}n)=\Omega (n)\geq \Omega (n^{2\gamma })}$

なので、 の下限はによって支配されることが分かっています。最後のステップでは、 という事実を使用します。これは、のべき乗が最大で であることを意味します。また、は正の整数なので、が最大で であることがわかります。 ${\displaystyle \delta \leq 1}$${\displaystyle m}$${\displaystyle n}$${\displaystyle \gamma \leq {\frac {1}{2}}}$${\displaystyle n}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle n^{2\gamma }}$${\displaystyle n}$

の値は、抽出子の定義を使用して計算されます。ここで、次の ことが分かっています。${\displaystyle k}$

${\displaystyle (n,k)=(n,\delta n)\Rightarrow k=\delta n}$

の値を使用すると次のようになります。 ${\displaystyle m}$

${\displaystyle m=\delta ^{2}n=n^{2\gamma }}$

この値を使用して、 がその下限にある 最悪のケースを説明します。代数計算により、次のようになります。${\displaystyle m}$${\displaystyle k}$

${\displaystyle \delta ^{2}n=n^{2\gamma }}$

${\displaystyle \Rightarrow \delta ^{2}=n^{2\gamma -1}}$

${\displaystyle \Rightarrow \delta =n^{\gamma -{\frac {1}{2}}}}$

の値に挿入すると、 ${\displaystyle k}$

${\displaystyle k=\delta n=n^{\gamma -{\frac {1}{2}}}n=n^{\gamma +{\frac {1}{2}}}}$、

これは、与えられた特性を持つ明示的な k-APRF 抽出器が存在することを証明します。${\displaystyle \Box }$

おそらく最も古い例は、ジョン・フォン・ノイマンによるものです。彼の抽出器は、入力ストリームから一度に 2 ビット (1 番目と 2 番目、3 番目と 4 番目、など) を取り出しました。2 つのビットが一致した場合、出力は生成されませんでした。ビットが異なる場合は、最初のビットの値が出力されました。フォン・ノイマン抽出器は、各ビットが 1 になる確率が同じで、連続するビット間に相関がない限り、入力ビットの分布が均一でなくても均一な出力を生成することが示されています。^[7]

したがって、 pが必ずしも 1/2 に等しいとは限らないベルヌーイ列を入力として受け取り、 のベルヌーイ列を出力します。 より一般的には、これは任意の交換可能な列に適用されます。つまり、任意のペアについて、01 と 10 が等しく発生する可能性があるという事実のみに依存します。独立した試行の場合、これらは確率 を持ちますが、交換可能な列の場合、確率はより複雑になる可能性がありますが、両方とも等しく発生する可能性があります。簡単に言うと、ビットは統計的に独立しており、乗算の交換法則により 、 が成立します。したがって、01 と 10 のペアをビット 0 と 1 にマッピングし、00 と 11 のペアを破棄すると、出力は一様分布になります。 ${\displaystyle p=1/2.}$${\displaystyle p\cdot (1-p)=(1-p)\cdot p}$${\displaystyle P(A\cap B)=P(A)P(B)=P(B)P(A)=P(B\cap A)}$

フォン・ノイマン抽出器の反復にはエリアス抽出器とペレス抽出器があり、後者はビットを再利用して、同じサイズの入力ストリームを与えられたフォン・ノイマン抽出器よりも大きな出力ストリームを生成します。^[8]

もう 1 つのアプローチは、入力ストリームに適用されたカオス マシンの出力を使用することです。このアプローチは、一般にカオス システムの特性に依存します。入力ビットがマシンにプッシュされ、複数の動的システムで軌道と軌跡を展開します。したがって、入力の小さな違いによって、非常に異なる出力が生成されます。このようなマシンは、入力ビットの分布が均一でなかったり、重大な欠陥があったりしても、出力が均一であるため、弱いエントロピー ソースを使用できます。さらに、このスキームでは、時間コスト、必要なメモリ、秘密鍵の 3 つのパラメーターを指定して制御し、出力ストリームの複雑さ、品質、セキュリティを向上させることができます。

真のカオスシステムは数学的にはエントロピーを「増幅」するのに適切ですが、これは無限精度の実数が利用できることを前提としています。IEEE 754浮動小数点を使用するカオスマシンのように、有限精度の数値表現を持つデジタルコンピュータに実装すると、周期性は特定のビット長の完全な空間にはるかに満たないことが示されています。^[9]

暗号ハッシュ関数をランダム性抽出器として使用することも可能です。ただし、すべてのハッシュ アルゴリズムがこの目的に適しているわけではありません。 ^{[引用が必要]}

ランダム性抽出器は暗号化アプリケーションで広く使用されており、暗号化ハッシュ関数をディスク ドライブのタイミング情報やキーボードの遅延などの高エントロピーだが均一でないソースに適用して、均一にランダムな結果を生成します。

乱数抽出器は、例えば量子乱数発生器からの生の出力をより短く、安全で均一にランダムな出力に抽出するなど、最近の量子暗号の開発において重要な役割を果たしてきました。 ^[10]

ランダム性抽出は、計算複雑性理論のいくつかの分野や、リストデコード可能な誤り訂正コードの構築にも使用されます。

• 非相関
• ハードウェア乱数ジェネレータ
• ランダム性の合併
• ファジー抽出器

• 独立ソースとアプリケーションのためのランダムネス抽出器、Anup Rao
• 抽出子の明示的構築における最近の進展、ロネン・シャルティエル
• CBC、カスケード、HMAC モードを使用したランダム性抽出とキー導出、Yevgeniy Dodis 他
• キー導出とランダム性抽出、Olivier Chevassut 他
• ビット固定ソースと露出耐性暗号のための決定論的抽出器、Jesse Kamp と David Zuckerman
• 偏ったコインを投げる（そして高度なマルチレベル戦略の最適性）（講義ノート）、マイケル・ミッツェンマッハー