Randomness extractor とは

「抽出器」と呼ばれることが多いランダム性抽出器は、弱くランダムなエントロピー源からの出力に適用され、短く均一にランダムなシードと一緒に、ソースから一様に見え、配布されます。弱いランダムな放射源の例には、放射能崩壊または熱騒音が含まれる。可能な情報源に対する唯一の制限は、それらを完全に制御、計算、または予測する方法がなく、エントロピー率の下限を確立できることである。与えられたソースに対して、ランダム性抽出器は真の乱数生成器(TRNG)であるとみなすこともできます。どのようなタイプの弱いランダムソースからも本当にランダムな出力を生成することが証明された単一の抽出器は存在しません。
「バイアス」という用語は、弱いランダムな情報源が一貫性から逸脱していることを示すために使用されることがあり、古い文献では、いわゆるバイバイアスされた情報源からのランダム性を取り、偏っている。弱いランダムな線源は抽出器の出力よりも常に長くなるが、効率的な抽出器は、この長さの比をできるだけ小さくし、同時にシードの長さを低く保つものである。直感的に言えば、これは可能な限りランダム性がソースから「抽出」されたことを意味します。
抽出器は、擬似乱数発生器(PRG)といくつかの概念上の類似点を有するが、2つの概念は同一ではないことに留意されたい。両方とも、小さな均一なランダムシードを入力として受け取り、一様にランダムに「見える」より長い出力を生成する関数です。いくつかの疑似乱数生成器は、実際には抽出器でもあります。 (PRGがハードコア述語の存在に基づいている場合、弱ランダム・ソースをそのような述語の真理値表の集合と考えることができ、出力が統計的に均一に近いことを証明することができる)。しかし、一般的なPRG定義弱い無作為のソースを使用しなければならないと規定しておらず、抽出器の場合、出力は統計的に均一に近くなければならず、PRGでは計算上は均一ではなく、若干弱い概念である。
NIST Special Publication 800-90B(ドラフト)は、SHAハッシュファミリーを含むいくつかの抽出器を推奨し、エントロピー入力の量がそれらから出力されるビットの数の2倍である場合、その出力は本質的に完全にランダムであると考えることができると述べている。