完全エントロピー

暗号学において、完全エントロピーとは乱数生成器の出力の特性です。出力が理論上の完全乱数源（nビットの出力に対してほぼnビットのエントロピーを持つ）の出力と実質的に区別できない場合、その出力は完全エントロピーを持ちます。^{[ 1 ]}

この用語は、NIST乱数生成器の標準規格であるNIST SP 800-90AおよびNIST SP 800-90Bで広く使用されています。完全なエントロピーでは、乱数生成器の出力におけるビットあたりのエントロピーは1に近くなります：、ここでNISTの実用的な です。^{[ 1 ]}${\displaystyle 1-\epsilon}$ ${\displaystyle \epsilon <2^{-32}}$

いくつかの文献では、この用語は理想的なランダムビット列（出力1ビットあたり1ビットのエントロピー）を定義するために使用されています。この意味では、現実世界では「100%のエントロピーを達成することは不可能」です。^{[ 2 ]}

定義

数学的な定義は「識別ゲーム」に基づいています。無制限の計算能力を持つ敵対者に、長さnのW個の要素を含む2つの乱数集合が提供されます。1つの集合は理想的なもので、理論的に完全な乱数生成器からのビット文字列を含みます。もう1つの集合は実際のもので、乱数抽出器を通った後の実用的な乱数源からのビット文字列を含みます。Wと正のパラメータδの特定の値に対する完全なエントロピーは、敵対者が実際の集合をより高い確率で推測できない場合に達成されます。^{[ 3 ]}${\displaystyle {\frac {1}{2}}+\delta }$

追加エントロピー

完全なエントロピーを達成する実用的な方法は、エントロピーソースからnビットより長いビット文字列を取得し、それらにnビットの結果を生成する高品質の乱数抽出器を適用し、これらの結果から実集合を構築することです。理想元は本質的にエントロピー値nを持ちます。条件付け関数の入力は、完全なエントロピーの定義を満たすために、より高い最小エントロピー値Hを持つ必要があります。追加エントロピービットの数はWとδに依存します。次の表にはいくつかの代表的な値が含まれています。^{[ 4 ]}${\displaystyle Hn}$

追加エントロピーの最小値${\displaystyle Hn}$

西	${\displaystyle \delta =2^{-20}}$	${\displaystyle \delta =2^{-10}}$
${\displaystyle 2^{32}}$	67.3	47.3
${\displaystyle 2^{48}}$	83.3	63.3
${\displaystyle 2^{56}}$	91.3	71.3

乱数抽出器の要件

すべての乱数抽出器が望ましい結果を生み出すわけではありません。例えば、フォン・ノイマン抽出器は、偏りのない出力を提供しますが、ビット群の相関を解消しません。そのため、多くのエントロピー源で典型的に見られるように、直列相関のある入力に対しては、出力ビットは独立ではありません。^{[ 5 ]}そのため、NISTはNIST SP 800-90B標準において、 AES - CBC-MACを含む「検証済み調整コンポーネント」を定義しています。^{[ 5 ]}

参考文献

1. Buller et al. 2023 , p. i
2. ジョンストン 2018、18ページ。
3. Buller et al. 2023、p.1。
4. Buller et al. 2023、p.2。
5. ジョンストン 2018、p. 16。

出典

• ブラー、ダリル、カウファー、アーロン、ロギンスキー、トゥラン、メルテム・ソンメズ（2023年4月）。「NIST機関間報告書 NIST IR 8427 SP 800-90シリーズの完全エントロピー仮定に関する議論」（PDF）。NIST。doi : 10.6028/NIST.IR.8427.ipd 。2023年11月1日閲覧
• ジョンストン、D. (2018). 『乱数ジェネレーター ― 原理と実践：エンジニアとプログラマのためのガイド』 De Gruyter. ISBN 978-1-5015-0606-22023年11月1日閲覧。