乱数抽出器
偏りがあり部分的に予測可能なエントロピー源を、より少ないビット数のほぼ完全に一様な列へ煮詰める関数。
ダイオードの雑音、クロックジッタ、Diffie–Hellmanの共有値といった生の源は、エントロピーは十分でも形が悪いことが多い。特定の値が他より頻繁に現れるのだ。最古の抽出器は1951年のジョン・フォン・ノイマンによるもので、ビットを2つずつ読み、「01」なら0、「10」なら1を出力し、残りは捨てる。偏ったコインは直せるが、各回の結果に相関があるコインには効かない。
一般論の土台はleftover hash lemma(Impagliazzo、Levin、Luby、1989年)である。源が十分なmin-entropyを持つなら、ランダムに選んだユニバーサルハッシュ関数でほぼ一様な出力が得られる。実務上、HKDFが二段構えなのはこのためだ。Extractは偏った共有秘密を一様な鍵にする抽出器で、Expandはそれを必要な数の鍵へ引き伸ばす。