目次

NIST IR 8427 日本語訳

英語タイトル : Discussion on the Full Entropy Assumption of the SP 800-90 Series
日本語タイトル : SP 800-90 シリーズにおける完全エントロピーの仮定に関する考察
公開日 : 2023-04-14
原文URL : https://csrc.nist.gov/pubs/ir/8427/final
翻訳編集 : 自動生成(有志による非公式の日本語訳), 原文取得日 : 2026-10-31, 訳文 : 150 / 151 ブロック

[要約] NIST IR 8427 は、NIST SP 800-90 シリーズにおける完全エントロピーの仮定に関して、誤差の値 ε を選定した根拠を示す報告書です。SP 800-90 シリーズでは、1 ビットあたりのエントロピーの量が少なくとも 1 − ε(ε は高々 2^-32)であれば、そのビット列は完全エントロピーを持つと仮定します。乱数ビット生成器やサンプルデータ列の解析によって完全エントロピーを確保することは困難であるため、本報告書は完全エントロピーの代替的な定義を用います。そして、この定義が満たされるときに得られるエントロピーの水準を計算することで、その根拠を示します。

NIST Interagency Report

NIST 省庁間報告書

NIST IR 8427

NIST IR 8427

Discussion on the Full Entropy Assumption of the SP 800-90 Series

SP 800-90 シリーズにおける完全エントロピーの仮定に関する考察

Darryl Buller Aaron Kaufer Allen Roginsky Meltem Sönmez Turan

Darryl Buller Aaron Kaufer Allen Roginsky Meltem Sönmez Turan

This publication is available free of charge from: https://doi.org/10.6028/NIST.IR.8427.ipd

本刊行物は次のURLから無料で入手できます: https://doi.org/10.6028/NIST.IR.8427.ipd

NIST Interagency Report

NIST 省庁間報告書

NIST IR 8427

NIST IR 8427

Discussion on the Full Entropy Assumption of the SP 800-90 Series

SP 800-90 シリーズにおける完全エントロピーの仮定に関する考察

Darryl Buller Aaron Kaufer Cybersecurity Directorate National Security Agency

Darryl Buller Aaron Kaufer Cybersecurity Directorate National Security Agency

Allen Roginsky Meltem Sönmez Turan Computer Security Division Information Technology Laboratory

Allen Roginsky Meltem Sönmez Turan Computer Security Division Information Technology Laboratory

This publication is available free of charge from: https://doi.org/10.6028/NIST.IR.8427

本刊行物は次のURLから無料で入手できます: https://doi.org/10.6028/NIST.IR.8427

April 2023

2023年4月

図表
[U.S. Department of Commerce seal — not reproduced on this unofficial site]

[米国商務省の紋章。公的な標章のため、この非公式サイトには掲載していません。原本 PDF を参照してください。]

U.S. Department of Commerce Gina M. Raimondo, Secretary

米国商務省 Gina M. Raimondo 長官

National Institute of Standards and Technology Laurie E. Locascio, NIST Director and Under Secretary of Commerce for Standards and Technology

国立標準技術研究所 Laurie E. Locascio、NIST 所長兼商務次官(標準・技術担当)

Certain commercial equipment, instruments, software, or materials, commercial or non-commercial, are identified in this paper in order to specify the experimental procedure adequately. Such identification does not imply recommendation or endorsement of any product or service by NIST, nor does it imply that the materials or equipment identified are necessarily the best available for the purpose.

本論文では、実験手順を十分に特定するために、商用・非商用を問わず、機器、計器、ソフトウェア、または材料を挙げている場合があります。このような記載は、NIST がいかなる製品やサービスも推奨または是認することを意味せず、挙げた材料や機器がその目的に最適であると必ずしも認めることを意味するものでもありません。

There may be references in this publication to other publications currently under development by NIST in accordance with its assigned statutory responsibilities. The information in this publication, including concepts and methodologies, may be used by federal agencies even before the completion of such companion publications. Thus, until each publication is completed, current requirements, guidelines, and procedures, where they exist, remain operative. For planning and transition purposes, federal agencies may wish to closely follow the development of these new publications by NIST.

本刊行物には、NIST が法令で定められた責務に従って現在策定中の他の刊行物への言及が含まれる場合があります。概念や方法論を含む本刊行物の情報は、そうした関連刊行物の完成前であっても、連邦機関が利用してかまいません。したがって、各刊行物が完成するまでは、既存の要件、ガイドライン、手順がある場合は、それらが引き続き有効です。計画および移行のため、連邦機関は、NIST によるこれらの新しい刊行物の策定状況を注意深く追うことを検討してもよいです。

Organizations are encouraged to review all draft publications during public comment periods and provide feedback to NIST. Many NIST cybersecurity publications, other than the ones noted above, are available at https://csrc.nist.gov/publications.

各組織は、パブリックコメントの期間中にすべてのドラフト刊行物を確認し、NIST にフィードバックを提供することが推奨されます。上記以外の NIST のサイバーセキュリティ関連刊行物の多くは、https://csrc.nist.gov/publications で入手できます。

NIST Technical Series Policies
Copyright, Use, and Licensing Statements
NIST Technical Series Publication Identifier Syntax

NIST Technical Series Policies
Copyright, Use, and Licensing Statements
NIST Technical Series Publication Identifier Syntax

Publication History
Approved by the NIST Editorial Review Board on 2023-03-30

刊行履歴
2023-03-30 に NIST Editorial Review Board によって承認されました

How to Cite this NIST Technical Series Publication:
Buller D, Kaufer A, Roginsky A, Sönmez Turan M (2023) Discussion on the Full Entropy Assumption of the SP 800-90 Series. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) NIST IR 8427. https://doi.org/10.6028/NIST.IR.8427

本 NIST Technical Series 刊行物の引用方法:
Buller D, Kaufer A, Roginsky A, Sönmez Turan M (2023) Discussion on the Full Entropy Assumption of the SP 800-90 Series. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Interagency or Internal Report (IR) NIST IR 8427. https://doi.org/10.6028/NIST.IR.8427

Author ORCID iDs
Roginsky, Allen: 0000-0003-2684-6736
Meltem Sönmez Turan: 0000-0002-1950-7130

著者の ORCID iD
Roginsky, Allen: 0000-0003-2684-6736
Meltem Sönmez Turan: 0000-0002-1950-7130

Submit Comments
rbg_comments@nist.gov

コメントの送付先
rbg_comments@nist.gov

All comments are subject to release under the Freedom of Information Act (FOIA).

すべてのコメントは、情報自由法(FOIA)に基づいて公開される場合があります。

Abstract

概要

The NIST Special Publication (SP) 800-90 series supports the generation of high-quality random bits for cryptographic and non-cryptographic use. The security strength of a random number generator depends on the unpredictability of its outputs. This unpredictability can be measured in terms of entropy, which the NIST SP 800-90 series measures using min-entropy. A full-entropy bitstring has an amount of entropy equal to its length. Full-entropy bitstrings are important for cryptographic applications, as these bitstrings have ideal randomness properties and may be used for any cryptographic purpose. Due to the difficulty of generating and testing full-entropy bitstrings, the SP 800-90 series assumes that a bitstring has full entropy if the amount of entropy per bit is at least \(1 - \varepsilon\), where \(\varepsilon\) is at most \(2^{-32}\). This report provides a justification for the selection of this value of \(\varepsilon\).

NIST Special Publication(SP)800-90 シリーズは、暗号用途および非暗号用途に使う高品質な乱数ビットの生成を支援します。乱数生成器のセキュリティ強度は、その出力の予測不可能性に依存します。この予測不可能性はエントロピーで測ることができ、NIST SP 800-90 シリーズでは最小エントロピーを用いて予測不可能性を測定します。完全エントロピーのビット列とは、エントロピーの量がその長さに等しいビット列です。完全エントロピーのビット列は理想的な乱数性を備え、あらゆる暗号用途に使用できるため、暗号アプリケーションにとって重要です。ただし、完全エントロピーのビット列は生成も検査も困難であることから、SP 800-90 シリーズでは、1ビットあたりのエントロピーの量が少なくとも \(1 - \varepsilon\)(\(\varepsilon\) は高々 \(2^{-32}\))であれば、そのビット列は完全エントロピーを持つと仮定します。本報告書は、この \(\varepsilon\) の値を選定した根拠を示します。

Keywords

キーワード

entropy; min-entropy; random number generation.

entropy; min-entropy; random number generation.

Reports on Computer Systems Technology

コンピューターシステム技術に関する報告書

The Information Technology Laboratory (ITL) at the National Institute of Standards and Technology (NIST) promotes the U.S. economy and public welfare by providing technical leadership for the Nation’s measurement and standards infrastructure. ITL develops tests, test methods, reference data, proof of concept implementations, and technical analyses to advance the development and productive use of information technology. ITL’s responsibilities include the development of management, administrative, technical, and physical standards and guidelines for the cost-effective security and privacy of other than national security-related information in federal information systems.

米国国立標準技術研究所(NIST)の情報技術研究所(ITL)は、国の計測・標準インフラに対する技術的なリーダーシップを提供することで、米国経済と公共の福祉を促進しています。ITL は、情報技術の開発と生産的な利用を進めるため、試験、試験方法、参照データ、概念実証の実装、技術分析を開発しています。ITL の責務には、連邦情報システムにおける国家安全保障に関係しない情報のセキュリティとプライバシーについて、費用対効果の高い管理、運営、技術および物理的な標準ならびにガイドラインを策定することが含まれます。

Table of Contents

目次

1. Introduction

1. はじめに

The NIST Special Publication (SP) 800-90 series [1][2][3] supports the generation of high-quality random bits for cryptographic and non-cryptographic use. The security strength of a random number generator depends on the unpredictability of its outputs. This unpredictability can be measured in terms of entropy, which the NIST SP 800-90 series measures using min-entropy. The SP 800-90 series refers to certain bitstrings as having full entropy, meaning that they have an amount of entropy equal to their length. Such bitstrings are important for cryptographic applications since they have the highest level of unpredictability and may therefore be used for any cryptographic purpose. The SP 800-90 series assumes that a bitstring has full entropy if the amount of entropy per bit is at least \(1 - \varepsilon\), where \(\varepsilon\) is at most \(2^{-32}\). This report provides a justification for the selection of this value of \(\varepsilon\). Due to the difficulty of ensuring full entropy through the analysis of random bit generators and sample data sequences, this is accomplished by using an alternative definition of full entropy and calculating the resulting entropy level when this definition is satisfied.

NIST Special Publication(SP)800-90 シリーズ [1][2][3] は、暗号用途および非暗号用途に使う高品質な乱数ビットの生成を支援します。乱数生成器のセキュリティ強度は、その出力の予測不可能性に依存します。この予測不可能性はエントロピーで測ることができ、NIST SP 800-90 シリーズでは最小エントロピーを用いて測定します。SP 800-90 シリーズでは、エントロピーの量がその長さに等しいビット列を、完全エントロピーを持つビット列と呼びます。このようなビット列は予測不可能性が最も高く、あらゆる暗号用途に使用できるため、暗号アプリケーションにとって重要です。SP 800-90 シリーズでは、1ビットあたりのエントロピーの量が少なくとも \(1 - \varepsilon\)(\(\varepsilon\) は高々 \(2^{-32}\))であれば、そのビット列は完全エントロピーを持つと仮定します。本報告書は、この \(\varepsilon\) の値を選定した根拠を示します。乱数ビット生成器やサンプルデータ列の解析によって完全エントロピーを確保することは困難であるため、完全エントロピーの代替的な定義を用い、この定義が満たされるときに得られるエントロピーの水準を計算することで、この根拠を示します。

2. Problem Statement

2. 問題の定式化

The SP 800-90 series uses a definition of full entropy that prescribes a numerical threshold on the entropy per bit (at least \(1 - \varepsilon\), where \(\varepsilon\) is at most \(2^{-32}\)). However, although this is an intuitive way to define full entropy, it is generally not possible to ensure sufficient entropy within this tolerance by analyzing a Random Bit Generator (RBG) or estimating entropy from a data sample. It is, therefore, necessary to use a different definition from which a practical approach to ensuring full entropy can be derived. The report begins by defining full entropy in terms of a hypothetical distinguishing game. The report then presents and proves two results following from this definition. First, it is shown how output satisfying this definition can be generated using a vetted conditioning function (see [2]) acting on data having an entropy level that meets or exceeds a certain value. Second, it is shown that the entropy level of output produced by such a process satisfies the full entropy threshold used in the SP 800-90 series, thereby demonstrating a connection between these two definitions.

SP 800-90 シリーズは、1ビットあたりのエントロピーに数値のしきい値(少なくとも \(1 - \varepsilon\)、ここで \(\varepsilon\) は高々 \(2^{-32}\))を定める完全エントロピーの定義を用いています。しかし、これは完全エントロピーを定義する直感的な方法ではあるものの、乱数ビット生成器(RBG)を解析したり、データサンプルからエントロピーを推定したりして、この許容範囲内で十分なエントロピーを確保することは、一般に不可能です。そのため、完全エントロピーを確保する実用的な方法を導ける別の定義を用いる必要があります。本報告書はまず、仮想的な識別ゲームによって完全エントロピーを定義します。次に、この定義から導かれる二つの結果を示して証明します。第一に、この定義を満たす出力を、一定値以上のエントロピー水準を持つデータに対して審査済みコンディショニング関数([2] を参照)を適用することで生成できることを示します。第二に、このような処理で生成した出力のエントロピー水準が、SP 800-90 シリーズで用いる完全エントロピーのしきい値を満たすことを示し、二つの定義の間の関係を明らかにします。

3. Full Entropy Definition

3. 完全エントロピーの定義

Full entropy will be defined as follows. Consider a distinguishing game where an adversary attempts to distinguish between two cases – REAL and IDEAL. Assume that the adversary is provided with \(W\) \(n\)-bit outputs \(b_1, b_2, \ldots, b_W\). In the REAL case, each output is generated by a cryptographic conditioning function operating on an output from a real-life entropy source. In the IDEAL case, the outputs are generated by an idealized randomness source that produces independent \(n\)-bit outputs with each output value having a probability of \(2^{-n}\). One of the two cases is chosen at random with each being equally likely. Outputs of length \(n\) bits generated in the REAL case are defined as having full entropy with respect to \(W\) and \(\delta\) (where \(\delta > 0\)) if a computationally unlimited adversary cannot correctly distinguish between the REAL and IDEAL cases with probability higher than \(\frac{1}{2} + \delta\).

完全エントロピーを次のように定義します。攻撃者が二つの場合、すなわち REAL と IDEAL を識別しようとする識別ゲームを考えます。攻撃者に、\(n\) ビットの出力 \(W\) 個 \(b_1, b_2, \ldots, b_W\) が与えられるものとします。REAL の場合、各出力は、現実のエントロピー源の出力に暗号学的コンディショニング関数を適用して生成されます。IDEAL の場合、各出力は、各出力値の確率が \(2^{-n}\) である独立な \(n\) ビットの出力を生成する理想化された乱数源によって生成されます。二つの場合のうち一方が、等しい確率でランダムに選ばれます。REAL の場合に生成された長さ \(n\) ビットの出力は、計算能力に制限のない攻撃者が REAL と IDEAL を \(\frac{1}{2} + \delta\) より高い確率で正しく識別できないとき、\(W\) と \(\delta\)(\(\delta > 0\))に関して完全エントロピーを持つと定義します。

4. Claims

4. 主張

4.1. Claim 1

4.1. 主張1

Output from a vetted conditioning function with sufficient input entropy satisfies the full entropy definition.

十分な入力エントロピーを持つ審査済みコンディショニング関数の出力は、完全エントロピーの定義を満たします。

Suppose that values for the \(W\) and \(\delta\) parameters used in the definition of full entropy are given and that a vetted conditioning function generates an \(n\)-bit output by processing an entropy sequence having min-entropy \(H\). Then if \(H \ge n + \log_2\left(\frac{W}{\delta^2}\right) - \log_2 \pi - 3\), the \(n\)-bit output satisfies the definition of full entropy with respect to \(W\) and \(\delta\). The proof of this claim is given in A.1.

完全エントロピーの定義で用いる \(W\) と \(\delta\) のパラメーターの値が与えられ、審査済みコンディショニング関数が、最小エントロピー \(H\) を持つエントロピー列を処理して \(n\) ビットの出力を生成するとします。このとき、\(H \ge n + \log_2\left(\frac{W}{\delta^2}\right) - \log_2 \pi - 3\) であれば、その \(n\) ビットの出力は、\(W\) と \(\delta\) に関して完全エントロピーの定義を満たします。この主張の証明は A.1 に示します。

From the above inequality, \(H - n\) represents the minimum required amount by which the input entropy must exceed \(n\) in order to ensure full entropy. The following table shows this minimum value for various values of \(W\) and \(\delta\).

上の不等式から、\(H - n\) は、完全エントロピーを確保するために入力エントロピーが \(n\) を超えていなければならない最小量を表します。次の表は、さまざまな \(W\) と \(\delta\) の値に対するこの最小値を示します。

Table 1. Minimum value of additional entropy \(H - n\) required for various values of \(W\) and \(\delta\)

表1. さまざまな \(W\) と \(\delta\) の値に対して必要な追加エントロピー \(H - n\) の最小値

\(\delta\)
\(W\)\(2^{-20}\)\(2^{-18}\)\(2^{-16}\)\(2^{-14}\)\(2^{-12}\)\(2^{-10}\)\(2^{-8}\)
\(2^{32}\)67.363.359.355.351.347.343.3
\(2^{40}\)75.371.367.363.359.355.351.3
\(2^{48}\)83.379.375.371.367.363.359.3
\(2^{56}\)91.387.383.379.375.371.367.3
\(\delta\)
\(W\)\(2^{-20}\)\(2^{-18}\)\(2^{-16}\)\(2^{-14}\)\(2^{-12}\)\(2^{-10}\)\(2^{-8}\)
\(2^{32}\)67.363.359.355.351.347.343.3
\(2^{40}\)75.371.367.363.359.355.351.3
\(2^{48}\)83.379.375.371.367.363.359.3
\(2^{56}\)91.387.383.379.375.371.367.3

It is assumed in SP 800-90C that there is an upper bound of \(2^{64}\) bits on the amount of output that an adversary attempting a distinguishing attack can obtain. Consider the combination \(W = 2^{48}\) and \(\delta = 2^{-10}\). Given \(W = 2^{48}\) \(n\)-bit RBG outputs, each output can be up to \(2^{16} = 65536\) bits long without exceeding the \(2^{64}\) data-quantity bound. Note that 10000 RBGs –each producing 1000 outputs per second– would require nearly a year to produce \(W = 2^{48}\) outputs. According to the table above, an adversary who obtains \(W = 2^{48}\) \(n\)-bit outputs has a distinguishing probability no greater than \(\frac{1}{2} + \delta = \frac{1}{2} + 2^{-10} \cong 0.501\) when \(H\), the conditioning function input min-entropy for each \(n\)-bit output, is at least \(n + 63.3\). This minimum value, rounded up to \(n + 64\), is used in this document and in SP 800-90C as the condition for satisfying the full entropy definition.

SP 800-90C では、識別攻撃を試みる攻撃者が取得できる出力量に \(2^{64}\) ビットの上限があると仮定しています。\(W = 2^{48}\)、\(\delta = 2^{-10}\) の組み合わせを考えます。\(n\) ビットの RBG 出力 \(W = 2^{48}\) 個が与えられるとき、データ量の上限 \(2^{64}\) を超えないためには、各出力の長さは最大で \(2^{16} = 65536\) ビットとなります。なお、1秒あたり1000個の出力を生成する RBG 10000台でも、\(W = 2^{48}\) 個の出力を生成するには1年近くを要します。上の表によると、\(W = 2^{48}\) 個の \(n\) ビット出力を取得した攻撃者の識別確率は、各 \(n\) ビット出力に対するコンディショニング関数の入力最小エントロピー \(H\) が少なくとも \(n + 63.3\) であれば、\(\frac{1}{2} + \delta = \frac{1}{2} + 2^{-10} \cong 0.501\) 以下です。この最小値を切り上げた \(n + 64\) を、本書および SP 800-90C では、完全エントロピーの定義を満たす条件として用います。

4.2. Claim 2

4.2. 主張2

Outputs that satisfy the definition of full entropy in Section 3 also satisfy the full entropy threshold in SP 800-90C.

第3節の完全エントロピーの定義を満たす出力は、SP 800-90C の完全エントロピーのしきい値も満たします。

Suppose that \(W = 2^{48}\) and \(\delta = 2^{-10}\). According to Claim 1, if the input min-entropy satisfies \(H \ge n + 64\), then the conditioning function output satisfies the definition of full entropy. In this case, it can also be shown that the average per-bit min-entropy of the resulting \(n\)-bit output is at least \(1 - 2^{-32}\). The proof of this claim is given in A.3. It is interesting to note that if a process generates outputs satisfying the definition of full entropy based on the distinguishing game, the outputs also satisfy the more intuitive definition in terms of an actual numerical entropy threshold. The resulting value \(\varepsilon = 2^{-32}\) is the value given in SP 800-90C as the threshold for full entropy.

\(W = 2^{48}\)、\(\delta = 2^{-10}\) とします。主張1によれば、入力の最小エントロピーが \(H \ge n + 64\) を満たすとき、コンディショニング関数の出力は完全エントロピーの定義を満たします。この場合、得られる \(n\) ビット出力の1ビットあたりの平均最小エントロピーが少なくとも \(1 - 2^{-32}\) であることも示せます。この主張の証明は A.3 に示します。注目すべきは、識別ゲームに基づく完全エントロピーの定義を満たす出力を生成する処理は、その出力が、実際の数値のエントロピーしきい値に基づく、より直感的な定義も満たすという点です。このとき得られる値 \(\varepsilon = 2^{-32}\) は、SP 800-90C が完全エントロピーのしきい値として示している値です。

5. Assumptions

5. 仮定

The proofs of the two claims made in this paper require some assumptions. These assumptions are presented and explained below.

本論文の二つの主張の証明には、いくつかの仮定が必要です。以下に、これらの仮定を示して説明します。

5.1. Assumption 1: The Test Statistic is Normally Distributed

5.1. 仮定1: 検定統計量は正規分布に従う

The proof of Claim 1 uses a test statistic \(X\) computed from data values generated in either the REAL or the IDEAL case. It will be assumed that \(X\) is approximately normally distributed. This statistic is of the form \(X = \sum_{i=1}^{W} x_i\), where the variables \(x_i\) are independent and identically distributed, and depend on the observed values \(b_i\). If \(\mu_x\) and \(\sigma_x^2\) are the true mean and variance of the individual variables \(x_i\), respectively (\(\mu_x\) and \(\sigma_x^2\) are derived in A.1), then \(\frac{\frac{X}{W} - \mu_x}{\left(\sigma_x / \sqrt{W}\right)} = \frac{\frac{\sum_{i=1}^{W} x_i}{W} - \mu_x}{\left(\sigma_x / \sqrt{W}\right)}\) is approximately normally distributed by the Central Limit Theorem when \(W\) is large (we assume \(W = 2^{48}\)). Since \(X\) can be obtained from \(\frac{\frac{X}{W} - \mu_x}{\left(\sigma_x / \sqrt{W}\right)}\) by a linear transformation, \(X\) is also approximately normally distributed.

主張1の証明では、REAL の場合または IDEAL の場合のいずれかで生成されたデータ値から計算される検定統計量 \(X\) を用います。\(X\) はおおよそ正規分布に従うと仮定します。この統計量は \(X = \sum_{i=1}^{W} x_i\) の形をしており、変数 \(x_i\) は独立同分布で、観測値 \(b_i\) に依存します。\(\mu_x\) と \(\sigma_x^2\) をそれぞれ個々の変数 \(x_i\) の真の平均と分散とすると(\(\mu_x\) と \(\sigma_x^2\) は A.1 で導出します)、\(W\) が大きい場合(\(W = 2^{48}\) と仮定します)、\(\frac{\frac{X}{W} - \mu_x}{\left(\sigma_x / \sqrt{W}\right)} = \frac{\frac{\sum_{i=1}^{W} x_i}{W} - \mu_x}{\left(\sigma_x / \sqrt{W}\right)}\) は、中心極限定理によりおおよそ正規分布に従います。\(X\) は \(\frac{\frac{X}{W} - \mu_x}{\left(\sigma_x / \sqrt{W}\right)}\) から線形変換によって得られるため、\(X\) もおおよそ正規分布に従います。

5.2. Assumption 2: The Conditioning Function Output Probabilities are Random Variables

5.2. 仮定2: コンディショニング関数の出力確率は確率変数である

The discussion of full entropy in this paper is in the context of the SP 800-90 series, where bit sequences having full entropy are to be generated by processing entropy source output sequences (that generally do not have full entropy) with a vetted conditioning function or a Deterministic Random Bit Generator (DRBG). The assumption below is made in that context.

本論文における完全エントロピーの議論は SP 800-90 シリーズの文脈におけるものであり、そこでは、完全エントロピーを持つビット列は、(一般には完全エントロピーを持たない)エントロピー源の出力列を、審査済みコンディショニング関数または決定論的乱数ビット生成器(DRBG)で処理して生成されます。以下の仮定は、この文脈で置くものです。

Suppose that a conditioning function generates an \(n\)-bit output by processing a sequence from an entropy source. Consider the probability \(p_j\) for the \(j^{th}\) possible output value from the conditioning function. These probabilities are determined by the interaction between the specific conditioning function used and the space of possible inputs to that function. In the distinguishing game used in the full entropy definition, the adversary has complete knowledge of the conditioning function and its input space, and—being computationally unlimited—can determine the probabilities \(p_j\). For the purposes of this paper, determining the values of these probabilities is infeasible. However, it is useful to consider the \(p_j\) as random variables rather than fixed values and use statistics associated with these random variables to find the probability distribution of the test statistic \(X\). This can be justified as follows. Consider the application of the conditioning function to the input space of entropy source sequences to obtain the conditioning function output. The resulting mapping depends on both the selected input domain and the details of the conditioning function. The domain of this function is determined by the characteristics of the entropy source and the length of the entropy source sequences that are input to the conditioning function. These details effectively select from a large number of possible domains for the function. A consequence of the cryptographic properties of conditioning functions used in RBGs is that there is no simple pattern in the mapping from elements of the domain to elements of the range of the function, and there is no discernible bias in the assignment of outputs to inputs. Therefore, although the conditioning function is deterministic, this report will assume that it is effectively a mapping that assigns an \(n\)-bit output to each value in the domain with a uniform distribution so that each possible output value has a probability of \(2^{-n}\) of being the output value assigned to a given input value. (Note that multiple input values can be assigned a given output value.) Under this assumption, since probability \(p_j\) is the sum of the probabilities of the inputs mapped to the \(j^{th}\) output value, the probability \(p_j\) can be treated as a random variable.

コンディショニング関数が、エントロピー源からの列を処理して \(n\) ビットの出力を生成するとします。コンディショニング関数の \(j\) 番目の出力値の確率 \(p_j\) を考えます。これらの確率は、使用する具体的なコンディショニング関数と、その関数への入力として可能な空間との相互作用によって決まります。完全エントロピーの定義で用いる識別ゲームでは、攻撃者はコンディショニング関数とその入力空間を完全に知っており、計算能力に制限がないため、確率 \(p_j\) を求めることができます。本論文の目的上、これらの確率の値を求めることは実行不可能です。しかし、\(p_j\) を固定値ではなく確率変数とみなし、これらの確率変数に関する統計量を用いて検定統計量 \(X\) の確率分布を求めることは有用です。これは次のように正当化できます。エントロピー源の列からなる入力空間にコンディショニング関数を適用して、コンディショニング関数の出力を得ることを考えます。得られる写像は、選択した入力の定義域と、コンディショニング関数の詳細の両方に依存します。この関数の定義域は、エントロピー源の特性と、コンディショニング関数に入力されるエントロピー源の列の長さによって決まります。これらの詳細は、この関数の非常に多くの可能な定義域の中から一つを事実上選択します。RBG で使用されるコンディショニング関数の暗号学的性質の帰結として、定義域の要素から関数の値域の要素への写像には単純なパターンがなく、入力への出力の割り当てに識別できる偏りもありません。したがって、コンディショニング関数は決定論的ではあるものの、本報告書では、これは定義域の各値に対して一様分布で \(n\) ビットの出力を割り当てる写像と事実上みなせるものとし、各出力値が、与えられた入力値に割り当てられる出力値となる確率は \(2^{-n}\) であるとします(複数の入力値に同じ出力値が割り当てられる場合があることに注意してください)。この仮定の下では、確率 \(p_j\) は \(j\) 番目の出力値に写像される入力の確率の総和であるため、\(p_j\) は確率変数として扱えます。

5.3. Assumption 3: The Conditioning Function Output Probabilities are Normally Distributed

5.3. 仮定3: コンディショニング関数の出力確率は正規分布に従う

Consider that \(p_j\) is treated as a random variable as explained in Assumption 2. Suppose that there are \(M\) possible inputs to the conditioning function, with probabilities \(\{q_1, q_2, \ldots, q_M\}\). (Note that no assumptions will be made on the input probability distribution.) The output probability \(p_j\) can then be written as \(p_j = \sum_{i=1}^{M} q_i I_{i,j}\), where \(I_{i,j} = 1\) if the conditioning function maps the \(i^{\text{th}}\) input to the \(j^{\text{th}}\) output, and \(I_{i,j} = 0\) otherwise. Under Assumption 2, the assignment of inputs to outputs is done independently for each input, so for each value of \(j\), the variables \(q_i I_{i,j}\) are independent. The value of \(M\) is dependent on the characteristics of the entropy source outputs and the bit length of the conditioning function input. However, it is reasonable to assume that \(M\) is at least \(2^n\), the number of possible conditioning function outputs (it would be difficult to achieve a level of output entropy near \(n\) otherwise). Given the above statements, \(p_j\) is of a similar form to that of \(X\) in Assumption 1 and, according to a version of the Central Limit Theorem applying to independent random variables not having the same distribution, can be assumed to be approximately normally distributed.

仮定2で説明したとおり、\(p_j\) を確率変数として扱うことを考えます。コンディショニング関数への可能な入力が \(M\) 個あり、その確率が \(\{q_1, q_2, \ldots, q_M\}\) であるとします(入力の確率分布には何の仮定も置かないことに注意してください)。このとき、出力確率 \(p_j\) は \(p_j = \sum_{i=1}^{M} q_i I_{i,j}\) と書けます。ここで、\(I_{i,j} = 1\) はコンディショニング関数が \(i\) 番目の入力を \(j\) 番目の出力に写像する場合、\(I_{i,j} = 0\) はそれ以外の場合です。仮定2の下では、入力への出力の割り当ては入力ごとに独立に行われるため、各 \(j\) の値について、変数 \(q_i I_{i,j}\) は独立です。\(M\) の値は、エントロピー源の出力の特性と、コンディショニング関数の入力のビット長に依存します。しかし、\(M\) は少なくとも、コンディショニング関数の可能な出力の数である \(2^n\) であると仮定するのが妥当です(そうでなければ、出力エントロピーを \(n\) に近い水準にすることは困難です)。以上から、\(p_j\) は仮定1の \(X\) と同様の形をしており、同一分布に従わない独立な確率変数に適用される中心極限定理の一形式により、おおよそ正規分布に従うと仮定できます。

References

参考文献

[1] Barker EB, Kelsey JM (2015) Recommendation for Random Number Generation Using Deterministic Random Bit Generators. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) NIST SP 800-90Ar1. https://doi.org/10.6028/NIST.SP.800-90Ar1

[1] Barker EB, Kelsey JM (2015) Recommendation for Random Number Generation Using Deterministic Random Bit Generators. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) NIST SP 800-90Ar1. https://doi.org/10.6028/NIST.SP.800-90Ar1

[2] Sönmez Turan M, Barker EB, Kelsey JM, McKay KA, Baish ML, Boyle M (2018) Recommendation for the Entropy Sources Used for Random Bit Generation. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) NIST SP 800-90B. https://doi.org/10.6028/NIST.SP.800-90B

[2] Sönmez Turan M, Barker EB, Kelsey JM, McKay KA, Baish ML, Boyle M (2018) Recommendation for the Entropy Sources Used for Random Bit Generation. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) NIST SP 800-90B. https://doi.org/10.6028/NIST.SP.800-90B

[3] Barker EB, Kelsey JM, McKay K, Roginsky A, Sönmez Turan M (2022) Recommendation for Random Bit Generator (RBG) Constructions. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) NIST SP 800-90C 3pd, Third public draft. https://doi.org/10.6028/NIST.SP.800-90C.3pd

[3] Barker EB, Kelsey JM, McKay K, Roginsky A, Sönmez Turan M (2022) Recommendation for Random Bit Generator (RBG) Constructions. (National Institute of Standards and Technology, Gaithersburg, MD), NIST Special Publication (SP) NIST SP 800-90C 3pd, Third public draft. https://doi.org/10.6028/NIST.SP.800-90C.3pd

[4] Handbook of Mathematical Functions, with Formulas, Graphs, and Mathematical Tables, Milton Abramowitz and Irene A. Stegun, editors, Dover Publications, New York, 1972.

[4] Handbook of Mathematical Functions, with Formulas, Graphs, and Mathematical Tables, Milton Abramowitz and Irene A. Stegun, editors, Dover Publications, New York, 1972.

Appendix A. Proofs

付録A 証明

A.1. Proof of Claim 1

A.1. 主張1の証明

Suppose that random output is generated by processing a quantity of entropy data using a conditioning function. The claim is that given values of \(W\) and \(\delta\), it is possible to find a threshold such that if the min-entropy of the input to the conditioning function meets or exceeds that threshold, the conditioning function output will satisfy the definition of full entropy.

ある量のエントロピーデータをコンディショニング関数で処理して乱数出力を生成するとします。この主張は、\(W\) と \(\delta\) の値が与えられたとき、コンディショニング関数への入力の最小エントロピーがあるしきい値以上であれば、コンディショニング関数の出力が完全エントロピーの定義を満たすような、しきい値を見つけられる、というものです。

Let \(B = \{b_1, b_2, \ldots, b_W\}\) be the set of observed \(n\)-bit outputs, \(p_j\) be the probability of the \(j^{\text{th}}\) possible output from the conditioning function applied to the specified quantity of entropy data, and \(p_{b_i}\) be the probability of the \(i^{\text{th}}\) observed output in the REAL case. Note that each \(p_{b_i}\) corresponds to some \(p_j\).

\(B = \{b_1, b_2, \ldots, b_W\}\) を観測された \(n\) ビット出力の集合、\(p_j\) を、指定された量のエントロピーデータにコンディショニング関数を適用して得られる \(j\) 番目の可能な出力の確率、\(p_{b_i}\) を REAL の場合に \(i\) 番目に観測された出力の確率とします。各 \(p_{b_i}\) はいずれかの \(p_j\) に対応することに注意してください。

Now consider the likelihood ratio \(\frac{\mathit{Pr}[\mathit{REAL}|B]}{\mathit{Pr}[\mathit{IDEAL}|B]}\). Clearly, the adversary will conclude that \(B\) was produced by the REAL case if this likelihood ratio is greater than one and by the IDEAL case otherwise (there would be no reason to guess the less likely case). Since the REAL and IDEAL cases are equally likely, this likelihood ratio can be rewritten as \(\frac{\mathit{Pr}[B|\text{REAL}]}{\mathit{Pr}[B|\text{IDEAL}]}\) using Bayes Theorem. For ease of computation, compute the base-2 log of the likelihood ratio and denote the resulting statistic as \(X\). The adversary will conclude that \(B\) was produced by the REAL case if \(X > 0\) and by the IDEAL case otherwise. Then the following is true:

ここで、尤度比 \(\frac{\mathit{Pr}[\mathit{REAL}|B]}{\mathit{Pr}[\mathit{IDEAL}|B]}\) を考えます。攻撃者は、この尤度比が1より大きければ \(B\) は REAL の場合によって生成されたと結論し、そうでなければ IDEAL の場合によって生成されたと結論することは明らかです(可能性の低い方の場合を推測する理由はありません)。REAL の場合と IDEAL の場合は等確率であるため、この尤度比はベイズの定理により \(\frac{\mathit{Pr}[B|\text{REAL}]}{\mathit{Pr}[B|\text{IDEAL}]}\) と書き換えられます。計算を容易にするため、尤度比の2を底とする対数を計算し、得られた統計量を \(X\) と表します。攻撃者は、\(X > 0\) であれば \(B\) は REAL の場合によって生成されたと結論し、そうでなければ IDEAL の場合によって生成されたと結論します。このとき、次が成り立ちます。

\[ \begin{aligned} X &= \log_2\left(\frac{\mathit{Pr}[B|\text{REAL}]}{\mathit{Pr}[B|\text{IDEAL}]}\right) \\ &= \log_2(\mathit{Pr}[B|\text{REAL}]) - \log_2(\mathit{Pr}[B|\text{IDEAL}]) \\ &= \log_2\left(\prod_{i=1}^{W} p_{b_i}\right) - \log_2\left(2^{-nW}\right) \\ &= \sum_{i=1}^{W} \left(n + \log_2 p_{b_i}\right) \end{aligned} \]
\[ \begin{aligned} X &= \log_2\left(\frac{\mathit{Pr}[B|\text{REAL}]}{\mathit{Pr}[B|\text{IDEAL}]}\right) \\ &= \log_2(\mathit{Pr}[B|\text{REAL}]) - \log_2(\mathit{Pr}[B|\text{IDEAL}]) \\ &= \log_2\left(\prod_{i=1}^{W} p_{b_i}\right) - \log_2\left(2^{-nW}\right) \\ &= \sum_{i=1}^{W} \left(n + \log_2 p_{b_i}\right) \end{aligned} \]

The statistic \(X\) is a random variable that depends on the set \(B\) of observed \(n\)-bit outputs \(b_i\) and the probabilities \(p_{b_i}\) of those outputs in the REAL case. To assess the adversary’s distinguishing success probability, the probability distribution of \(X\) in both the REAL and IDEAL cases is required. Note that \(X\) is the sum of \(W\) individual random variables \(x_i = n + \log_2 p_{b_i}\). These variables, being determined by the generation of independent outputs \(b_i\), are independent and identically distributed. (In the IDEAL case, this is clearly true. In the REAL case, it follows from the assumed properties of the conditioning function.) As noted in Assumption 1, it is assumed that \(X\) is approximately normally distributed.

統計量 \(X\) は、観測された \(n\) ビット出力 \(b_i\) の集合 \(B\) と、REAL の場合のそれらの出力の確率 \(p_{b_i}\) に依存する確率変数です。攻撃者の識別成功確率を評価するには、REAL の場合と IDEAL の場合の両方における \(X\) の確率分布が必要です。\(X\) は、\(W\) 個の個別の確率変数 \(x_i = n + \log_2 p_{b_i}\) の和であることに注意してください。これらの変数は、独立な出力 \(b_i\) の生成によって決まるため、独立同分布です(IDEAL の場合、これは明らかに成り立ちます。REAL の場合は、コンディショニング関数について仮定した性質から導かれます)。仮定1で述べたとおり、\(X\) はおおよそ正規分布に従うと仮定します。

Consider that \(p_j\) is treated as a random variable as explained in Assumption 2. Then \(E[p_j] = \sum_{i=1}^{M} q_i E[I_{i,j}] = \sum_{i=1}^{M} 2^{-n} q_i = 2^{-n}\). Similarly,

仮定2で説明したとおり、\(p_j\) を確率変数として扱うことを考えます。すると、\(E[p_j] = \sum_{i=1}^{M} q_i E[I_{i,j}] = \sum_{i=1}^{M} 2^{-n} q_i = 2^{-n}\) です。同様に、

\[ \begin{aligned} \mathit{VAR}[p_j] &= \sum_{i=1}^{M} \mathit{VAR}[q_i I_{i,j}] \\ &= \sum_{i=1}^{M} \left(E\left[(q_i I_{i,j})^2\right] - \left(E[q_i I_{i,j}]\right)^2\right) \\ &= \sum_{i=1}^{M} \left(2^{-n} q_i^2 - 2^{-2n} q_i^2\right) \\ &= \left(2^{-n} - 2^{-2n}\right) \sum_{i=1}^{M} q_i^2 \end{aligned} \]
\[ \begin{aligned} \mathit{VAR}[p_j] &= \sum_{i=1}^{M} \mathit{VAR}[q_i I_{i,j}] \\ &= \sum_{i=1}^{M} \left(E\left[(q_i I_{i,j})^2\right] - \left(E[q_i I_{i,j}]\right)^2\right) \\ &= \sum_{i=1}^{M} \left(2^{-n} q_i^2 - 2^{-2n} q_i^2\right) \\ &= \left(2^{-n} - 2^{-2n}\right) \sum_{i=1}^{M} q_i^2 \end{aligned} \]

Now write \(p_j\) as \(p_j = 2^{-n}(1 + \theta_j)\). Then \(\theta_j = 2^n p_j - 1\), so \(E[\theta_j] = 2^n E[p_j] - 1 = 0\) and \(\mathit{VAR}[\theta_j] = 2^{2n} \mathit{VAR}[p_j] = (2^n - 1) \sum_{i=1}^{M} q_i^2\). Since the input collision entropy \(H_2 = -\log_2 \sum_{i=1}^{M} q_i^2\), \(\mathit{VAR}[\theta_j] = (2^n - 1) 2^{-H_2}\). Note that since \(p_j\) is assumed to be normally distributed as explained in Assumption 3, \(\theta_j = 2^n p_j - 1\) is also normally distributed.

次に、\(p_j\) を \(p_j = 2^{-n}(1 + \theta_j)\) と書きます。すると \(\theta_j = 2^n p_j - 1\) なので、\(E[\theta_j] = 2^n E[p_j] - 1 = 0\) であり、\(\mathit{VAR}[\theta_j] = 2^{2n} \mathit{VAR}[p_j] = (2^n - 1) \sum_{i=1}^{M} q_i^2\) です。入力の衝突エントロピーは \(H_2 = -\log_2 \sum_{i=1}^{M} q_i^2\) なので、\(\mathit{VAR}[\theta_j] = (2^n - 1) 2^{-H_2}\) です。仮定3で説明したとおり \(p_j\) は正規分布に従うと仮定しているため、\(\theta_j = 2^n p_j - 1\) も正規分布に従うことに注意してください。

The mean and variance of \(X\) depend on whether the source is REAL or IDEAL. Let \(\mu_R = E[x_i|\text{REAL}]\), \(\mu_I = E[x_i|\text{IDEAL}]\), \(\sigma_R^2 = \mathit{VAR}[x_i|\text{REAL}]\), and \(\sigma_I^2 = \mathit{VAR}[x_i|\text{IDEAL}]\).

\(X\) の平均と分散は、乱数源が REAL か IDEAL かによって異なります。\(\mu_R = E[x_i|\text{REAL}]\)、\(\mu_I = E[x_i|\text{IDEAL}]\)、\(\sigma_R^2 = \mathit{VAR}[x_i|\text{REAL}]\)、\(\sigma_I^2 = \mathit{VAR}[x_i|\text{IDEAL}]\) とします。

Now derive \(\mu_R\), \(\mu_I\), \(\sigma_R^2\), and \(\sigma_I^2\). Each of these values is computed by summing over the relevant expression using \(2^{-n}\) or \(p_j\) as the probability weighting factors for the IDEAL and REAL cases, respectively. Thus,

次に、\(\mu_R\)、\(\mu_I\)、\(\sigma_R^2\)、\(\sigma_I^2\) を導出します。これらの値はそれぞれ、IDEAL の場合は \(2^{-n}\)、REAL の場合は \(p_j\) を確率の重み係数として、該当する式を総和して計算します。したがって、

\[ \begin{aligned} E[x_i|\text{IDEAL}] &= E\left[n + \log_2 p_{b_i} | \text{IDEAL}\right] \\ &= \sum_{j=1}^{2^n} \left(n + \log_2 p_j\right) 2^{-n} \\ &= \sum_{j=1}^{2^n} \left(n + \frac{\ln\left(2^{-n}(1 + \theta_j)\right)}{\ln 2}\right) 2^{-n} \\ &= \sum_{j=1}^{2^n} \frac{\ln(1 + \theta_j)}{\ln 2} 2^{-n} \end{aligned} \]
\[ \begin{aligned} E[x_i|\text{IDEAL}] &= E\left[n + \log_2 p_{b_i} | \text{IDEAL}\right] \\ &= \sum_{j=1}^{2^n} \left(n + \log_2 p_j\right) 2^{-n} \\ &= \sum_{j=1}^{2^n} \left(n + \frac{\ln\left(2^{-n}(1 + \theta_j)\right)}{\ln 2}\right) 2^{-n} \\ &= \sum_{j=1}^{2^n} \frac{\ln(1 + \theta_j)}{\ln 2} 2^{-n} \end{aligned} \]

The Taylor series for \(\ln(1 + \theta_j)\) is \(\theta_j - \frac{{\theta_j}^2}{2} + \frac{{\theta_j}^3}{3} - \frac{{\theta_j}^4}{4} + \cdots\). It is shown in A.2 that for cases of interest, \(|\theta_j|\) is on the order of \(10^{-8}\) or smaller. For such values of \(\theta_j\), \(\ln(1 + \theta_j) \cong \theta_j - \frac{{\theta_j}^2}{2}\), and omitting the terms beyond \({\theta_j}^2\) results in a relative error in \(\ln(1 + \theta_j)\) on the order of \(10^{-16}\). The sum above is therefore approximately

\(\ln(1 + \theta_j)\) のテイラー級数は \(\theta_j - \frac{{\theta_j}^2}{2} + \frac{{\theta_j}^3}{3} - \frac{{\theta_j}^4}{4} + \cdots\) です。対象とする場合には \(|\theta_j|\) が \(10^{-8}\) 程度以下であることが A.2 で示されます。このような \(\theta_j\) の値に対しては \(\ln(1 + \theta_j) \cong \theta_j - \frac{{\theta_j}^2}{2}\) であり、\({\theta_j}^2\) を超える項を省略したときの \(\ln(1 + \theta_j)\) の相対誤差は \(10^{-16}\) 程度です。したがって、上の和はおおよそ次のとおりです。

\[ \sum_{j=1}^{2^n} \frac{\theta_j - \frac{\theta_j^2}{2}}{\ln 2} 2^{-n} = \frac{1}{\ln 2} \frac{\sum_{j=1}^{2^n} \theta_j}{2^n} - \frac{1}{2\ln 2} \frac{\sum_{j=1}^{2^n} \theta_j^2}{2^n}. \]
\[ \sum_{j=1}^{2^n} \frac{\theta_j - \frac{\theta_j^2}{2}}{\ln 2} 2^{-n} = \frac{1}{\ln 2} \frac{\sum_{j=1}^{2^n} \theta_j}{2^n} - \frac{1}{2\ln 2} \frac{\sum_{j=1}^{2^n} \theta_j^2}{2^n}. \]

The first sum in this expression is zero, by the definition of \(\theta_j\). To evaluate the second sum, note that the sum is computed over the \(2^n\) values of \(\theta_j\). Each of these \(2^n\) values can be considered as a specific value of the corresponding random variable. Since these random variables have the same distribution, the \(2^n\) values can also be treated as a sample of size \(2^n\) from any one of these random variables. By definition, \(\mathit{VAR}[\theta_j] = E[\theta_j^2] - E[\theta_j]^2\). The term \(\frac{\sum_{j=1}^{2^n} \theta_j^2}{2^n}\) is the sample mean of \(\theta_j^2\) and is, therefore, approximately \(\mathit{VAR}[\theta_j] + E[\theta_j]^2\). Substituting the values of \(E[\theta_j]\) and \(\mathit{VAR}[\theta_j]\) found above, the following is obtained:

この式の第1の和は、\(\theta_j\) の定義によりゼロです。第2の和を評価するために、この和が \(2^n\) 個の \(\theta_j\) の値について計算されることに注意します。これら \(2^n\) 個の値は、それぞれ対応する確率変数の具体的な値とみなせます。これらの確率変数は同じ分布に従うため、\(2^n\) 個の値は、これらの確率変数のいずれか一つからの大きさ \(2^n\) の標本としても扱えます。定義により \(\mathit{VAR}[\theta_j] = E[\theta_j^2] - E[\theta_j]^2\) です。項 \(\frac{\sum_{j=1}^{2^n} \theta_j^2}{2^n}\) は \(\theta_j^2\) の標本平均であり、したがって、おおよそ \(\mathit{VAR}[\theta_j] + E[\theta_j]^2\) です。上で求めた \(E[\theta_j]\) と \(\mathit{VAR}[\theta_j]\) の値を代入すると、次が得られます。

\[ \begin{aligned} E[x_i|\text{IDEAL}] &\cong -\frac{1}{2\ln 2}\left(\mathit{VAR}[\theta_j] + E[\theta_j]^2\right) \\ &= -\frac{1}{2\ln 2}(2^n - 1)2^{-H_2} \end{aligned} \]
\[ \begin{aligned} E[x_i|\text{IDEAL}] &\cong -\frac{1}{2\ln 2}\left(\mathit{VAR}[\theta_j] + E[\theta_j]^2\right) \\ &= -\frac{1}{2\ln 2}(2^n - 1)2^{-H_2} \end{aligned} \]

The derivation of \(E[x_i|\text{REAL}]\) is similar and is as follows (again omitting powers of \(\theta_j\) beyond \({\theta_j}^2\)).

\(E[x_i|\text{REAL}]\) の導出も同様で、次のとおりです(ここでも \({\theta_j}^2\) を超える \(\theta_j\) の冪は省略します)。

\[ \begin{aligned} E[x_i|\text{REAL}] &= E\left[n + \log_2 p_{b_i} |\text{REAL}\right] \\ &= \sum_{j=1}^{2^n} \left(n + \log_2 p_j\right) p_j \\ &= \sum_{j=1}^{2^n} \left(n + \frac{\ln\left(2^{-n}(1 + \theta_j)\right)}{\ln 2}\right) p_j \\ &= \sum_{j=1}^{2^n} \frac{\ln(1 + \theta_j)}{\ln 2} p_j \\ &= \sum_{j=1}^{2^n} \frac{\ln(1 + \theta_j)}{\ln 2} 2^{-n}(1 + \theta_j) \\ &\cong \sum_{j=1}^{2^n} \frac{\theta_j - \frac{\theta_j^2}{2}}{\ln 2} 2^{-n}(1 + \theta_j) \\ &\cong \frac{1}{\ln 2} \frac{\sum_{j=1}^{2^n} \theta_j}{2^n} + \frac{1}{2\ln 2} \frac{\sum_{j=1}^{2^n} \theta_j^2}{2^n} \\ &\cong \frac{1}{2\ln 2}\left(\mathit{VAR}[\theta_j] + E[\theta_j]^2\right) \\ &= \frac{1}{2\ln 2}(2^n - 1)2^{-H_2} \end{aligned} \]
\[ \begin{aligned} E[x_i|\text{REAL}] &= E\left[n + \log_2 p_{b_i} |\text{REAL}\right] \\ &= \sum_{j=1}^{2^n} \left(n + \log_2 p_j\right) p_j \\ &= \sum_{j=1}^{2^n} \left(n + \frac{\ln\left(2^{-n}(1 + \theta_j)\right)}{\ln 2}\right) p_j \\ &= \sum_{j=1}^{2^n} \frac{\ln(1 + \theta_j)}{\ln 2} p_j \\ &= \sum_{j=1}^{2^n} \frac{\ln(1 + \theta_j)}{\ln 2} 2^{-n}(1 + \theta_j) \\ &\cong \sum_{j=1}^{2^n} \frac{\theta_j - \frac{\theta_j^2}{2}}{\ln 2} 2^{-n}(1 + \theta_j) \\ &\cong \frac{1}{\ln 2} \frac{\sum_{j=1}^{2^n} \theta_j}{2^n} + \frac{1}{2\ln 2} \frac{\sum_{j=1}^{2^n} \theta_j^2}{2^n} \\ &\cong \frac{1}{2\ln 2}\left(\mathit{VAR}[\theta_j] + E[\theta_j]^2\right) \\ &= \frac{1}{2\ln 2}(2^n - 1)2^{-H_2} \end{aligned} \]

Reusing portions of these calculations, the variance of \(x_i\) in the IDEAL case is obtained as follows:

これらの計算の一部を再利用すると、IDEAL の場合の \(x_i\) の分散は次のように得られます。

\[ \begin{aligned} \mathit{VAR}[x_i|\text{IDEAL}] &= E\left[\left(n + \log_2 p_{b_i}\right)^2 |\text{IDEAL}\right] - E\left[n + \log_2 p_{b_i} |\text{IDEAL}\right]^2 \\ &\cong \sum_{j=1}^{2^n} \left(\frac{\theta_j - \frac{\theta_j^2}{2}}{\ln 2}\right)^2 2^{-n} - \left(-\frac{1}{2\ln 2}(2^n - 1)2^{-H_2}\right)^2 \\ &\cong \frac{1}{(\ln 2)^2} \frac{\sum_{j=1}^{2^n} \theta_j^2}{2^n} - \left(\frac{1}{2\ln 2}(2^n - 1)2^{-H_2}\right)^2 \\ &= \frac{1}{(\ln 2)^2}(2^n - 1)2^{-H_2} - \left(\frac{1}{2\ln 2}(2^n - 1)2^{-H_2}\right)^2 \\ &= \frac{1}{(\ln 2)^2}(2^n - 1)2^{-H_2}\left(1 - \frac{1}{4}(2^n - 1)2^{-H_2}\right) \end{aligned} \]
\[ \begin{aligned} \mathit{VAR}[x_i|\text{IDEAL}] &= E\left[\left(n + \log_2 p_{b_i}\right)^2 |\text{IDEAL}\right] - E\left[n + \log_2 p_{b_i} |\text{IDEAL}\right]^2 \\ &\cong \sum_{j=1}^{2^n} \left(\frac{\theta_j - \frac{\theta_j^2}{2}}{\ln 2}\right)^2 2^{-n} - \left(-\frac{1}{2\ln 2}(2^n - 1)2^{-H_2}\right)^2 \\ &\cong \frac{1}{(\ln 2)^2} \frac{\sum_{j=1}^{2^n} \theta_j^2}{2^n} - \left(\frac{1}{2\ln 2}(2^n - 1)2^{-H_2}\right)^2 \\ &= \frac{1}{(\ln 2)^2}(2^n - 1)2^{-H_2} - \left(\frac{1}{2\ln 2}(2^n - 1)2^{-H_2}\right)^2 \\ &= \frac{1}{(\ln 2)^2}(2^n - 1)2^{-H_2}\left(1 - \frac{1}{4}(2^n - 1)2^{-H_2}\right) \end{aligned} \]

Similarly, the variance of \(x_i\) in the REAL case is obtained as follows:

同様に、REAL の場合の \(x_i\) の分散は次のように得られます。

\[ \begin{aligned} \mathit{VAR}[x_i|\text{REAL}] &= E\left[\left(n + \log_2 p_{b_i}\right)^2 |\text{REAL}\right] - E\left[n + \log_2 p_{b_i} |\text{REAL}\right]^2 \\ &\cong \sum_{j=1}^{2^n} \left(\frac{\theta_j - \frac{\theta_j^2}{2}}{\ln 2}\right)^2 2^{-n} (1 + \theta_j) - \left(\frac{1}{2\ln 2}(2^n - 1)2^{-H_2}\right)^2 \\ &\cong \frac{1}{(\ln 2)^2} \frac{\sum_{j=1}^{2^n} \theta_j^2}{2^n} - \left(\frac{1}{2\ln 2}(2^n - 1)2^{-H_2}\right)^2 \\ &= \frac{1}{(\ln 2)^2}(2^n - 1)2^{-H_2} - \left(\frac{1}{2\ln 2}(2^n - 1)2^{-H_2}\right)^2 \\ &= \frac{1}{(\ln 2)^2}(2^n - 1)2^{-H_2}\left(1 - \frac{1}{4}(2^n - 1)2^{-H_2}\right) \end{aligned} \]
\[ \begin{aligned} \mathit{VAR}[x_i|\text{REAL}] &= E\left[\left(n + \log_2 p_{b_i}\right)^2 |\text{REAL}\right] - E\left[n + \log_2 p_{b_i} |\text{REAL}\right]^2 \\ &\cong \sum_{j=1}^{2^n} \left(\frac{\theta_j - \frac{\theta_j^2}{2}}{\ln 2}\right)^2 2^{-n} (1 + \theta_j) - \left(\frac{1}{2\ln 2}(2^n - 1)2^{-H_2}\right)^2 \\ &\cong \frac{1}{(\ln 2)^2} \frac{\sum_{j=1}^{2^n} \theta_j^2}{2^n} - \left(\frac{1}{2\ln 2}(2^n - 1)2^{-H_2}\right)^2 \\ &= \frac{1}{(\ln 2)^2}(2^n - 1)2^{-H_2} - \left(\frac{1}{2\ln 2}(2^n - 1)2^{-H_2}\right)^2 \\ &= \frac{1}{(\ln 2)^2}(2^n - 1)2^{-H_2}\left(1 - \frac{1}{4}(2^n - 1)2^{-H_2}\right) \end{aligned} \]

Note that for typical values of \(n\), \(\mu_I\) and \(\mu_R\) are closely approximated as \(-\frac{1}{2\ln 2} 2^{n-H_2}\) and \(\frac{1}{2\ln 2} 2^{n-H_2}\), respectively. Also, assuming that \(H_2\) will need to exceed \(n\) by at least a moderate amount in order to satisfy the definition of full entropy, \(\sigma_I^2 = \sigma_R^2\) can be closely approximated as \(\sigma^2 = \frac{1}{(\ln 2)^2} 2^{n-H_2}\). The statistic \(X\) is therefore approximately normally distributed with means and variance as follows:

\(n\) が典型的な値であれば、\(\mu_I\) と \(\mu_R\) はそれぞれ \(-\frac{1}{2\ln 2} 2^{n-H_2}\) と \(\frac{1}{2\ln 2} 2^{n-H_2}\) によってよく近似されることに注意してください。また、完全エントロピーの定義を満たすためには \(H_2\) が \(n\) を少なくともある程度は上回る必要があると仮定すると、\(\sigma_I^2 = \sigma_R^2\) は \(\sigma^2 = \frac{1}{(\ln 2)^2} 2^{n-H_2}\) としてよく近似できます。したがって、統計量 \(X\) はおおよそ正規分布に従い、その平均と分散は次のとおりです。

\[ \begin{gathered} E[X|\text{REAL}] = -E[X|\text{IDEAL}] = -W\mu_I \cong \frac{W}{2\ln 2} 2^{n-H_2} \\ \mathit{VAR}[X|\text{REAL}] = \mathit{VAR}[X|\text{IDEAL}] = W\sigma^2 \cong \frac{W}{(\ln 2)^2} 2^{n-H_2} \end{gathered} \]
\[ \begin{gathered} E[X|\text{REAL}] = -E[X|\text{IDEAL}] = -W\mu_I \cong \frac{W}{2\ln 2} 2^{n-H_2} \\ \mathit{VAR}[X|\text{REAL}] = \mathit{VAR}[X|\text{IDEAL}] = W\sigma^2 \cong \frac{W}{(\ln 2)^2} 2^{n-H_2} \end{gathered} \]

Now consider the probability that the adversary correctly determines whether the REAL or IDEAL case produced the observed sample \(B\). This probability is as follows:

次に、攻撃者が、観測された標本 \(B\) が REAL の場合と IDEAL の場合のどちらによって生成されたかを正しく判定する確率を考えます。この確率は次のとおりです。

\[ \begin{aligned} \mathit{Pr}[\text{Correct}] &= \mathit{Pr}[\text{IDEAL}]\,\mathit{Pr}[\text{Correct}|\text{IDEAL}] + \mathit{Pr}[\text{REAL}]\,\mathit{Pr}[\text{Correct}|\text{REAL}] \\ &= \frac{1}{2}\mathit{Pr}[X < 0|\text{IDEAL}] + \frac{1}{2}\mathit{Pr}[X > 0|\text{REAL}] \end{aligned} \]
\[ \begin{aligned} \mathit{Pr}[\text{Correct}] &= \mathit{Pr}[\text{IDEAL}]\,\mathit{Pr}[\text{Correct}|\text{IDEAL}] + \mathit{Pr}[\text{REAL}]\,\mathit{Pr}[\text{Correct}|\text{REAL}] \\ &= \frac{1}{2}\mathit{Pr}[X < 0|\text{IDEAL}] + \frac{1}{2}\mathit{Pr}[X > 0|\text{REAL}] \end{aligned} \]

Note that because of the symmetry resulting from \(X\) having a normal distribution with variance \(W\sigma^2\) in both the REAL and IDEAL cases and expected values that are negatives of each other in these two cases, \(\mathit{Pr}[X < 0|\text{IDEAL}] = \mathit{Pr}[X > 0|\text{REAL}]\), which gives the following:

REAL の場合と IDEAL の場合のどちらでも \(X\) は分散 \(W\sigma^2\) の正規分布に従い、期待値は両者で符号が逆であるという対称性から、\(\mathit{Pr}[X < 0|\text{IDEAL}] = \mathit{Pr}[X > 0|\text{REAL}]\) となることに注意してください。これにより、次が得られます。

\[ \begin{aligned} \mathit{Pr}[\text{Correct}] &= \mathit{Pr}[X < 0|\text{IDEAL}] \\ &= \mathit{Pr}\left[\frac{X - W\mu_I}{\sqrt{W\sigma^2}} < \frac{0 - W\mu_I}{\sqrt{W\sigma^2}} |\text{IDEAL}\right] \end{aligned} \]
\[ \begin{aligned} \mathit{Pr}[\text{Correct}] &= \mathit{Pr}[X < 0|\text{IDEAL}] \\ &= \mathit{Pr}\left[\frac{X - W\mu_I}{\sqrt{W\sigma^2}} < \frac{0 - W\mu_I}{\sqrt{W\sigma^2}} |\text{IDEAL}\right] \end{aligned} \]

Since in the IDEAL case, \(X\) is normally distributed with mean \(W\mu_I\) and variance \(W\sigma^2\), the value \(z = \frac{X - W\mu_I}{\sqrt{W\sigma^2}}\) is a standard normal random variable, so this probability is \(F\left(\frac{-W\mu_I}{\sqrt{W\sigma^2}}\right)\), where \(F\) is the cumulative distribution function of the standard normal distribution. \(F(x) \le \frac{1}{2} + \frac{1}{2}\sqrt{1 - e^{-2x^2/\pi}}\) when \(x > 0\) (see Section 26.2.24 of [4]). Thus, \(\mathit{Pr}[\text{Correct}] = F\left(\frac{-W\mu_I}{\sqrt{W\sigma^2}}\right) \le \frac{1}{2} + \delta\) if the following inequality is satisfied:

IDEAL の場合、\(X\) は平均 \(W\mu_I\)、分散 \(W\sigma^2\) の正規分布に従うため、値 \(z = \frac{X - W\mu_I}{\sqrt{W\sigma^2}}\) は標準正規確率変数であり、この確率は \(F\left(\frac{-W\mu_I}{\sqrt{W\sigma^2}}\right)\) です。ここで \(F\) は標準正規分布の累積分布関数です。\(x > 0\) のとき \(F(x) \le \frac{1}{2} + \frac{1}{2}\sqrt{1 - e^{-2x^2/\pi}}\) です([4] の Section 26.2.24 を参照)。したがって、次の不等式が満たされるならば、\(\mathit{Pr}[\text{Correct}] = F\left(\frac{-W\mu_I}{\sqrt{W\sigma^2}}\right) \le \frac{1}{2} + \delta\) です。

\[ \frac{1}{2} + \frac{1}{2}\sqrt{1 - e^{-2\left(\frac{-W\mu_I}{\sqrt{W\sigma^2}}\right)^2/\pi}} \le \frac{1}{2} + \delta \]
\[ \frac{1}{2} + \frac{1}{2}\sqrt{1 - e^{-2\left(\frac{-W\mu_I}{\sqrt{W\sigma^2}}\right)^2/\pi}} \le \frac{1}{2} + \delta \]

From the derivations above, \(\frac{-W\mu_I}{\sqrt{W\sigma^2}} = \frac{1}{2}\sqrt{W} \cdot 2^{\frac{n-H_2}{2}}\), giving the following sequence of inequalities:

上の導出から \(\frac{-W\mu_I}{\sqrt{W\sigma^2}} = \frac{1}{2}\sqrt{W} \cdot 2^{\frac{n-H_2}{2}}\) となり、次の一連の不等式が得られます。

\[ \begin{gathered} \frac{1}{2}\sqrt{1 - e^{-2\left(\frac{1}{4}W \cdot 2^{n-H_2}\right)/\pi}} \le \delta \\ 1 - e^{-\frac{1}{2}W \cdot 2^{n-H_2}/\pi} \le 4\delta^2 \\ 1 - 4\delta^2 \le e^{-\frac{1}{2}W \cdot 2^{n-H_2}/\pi} \\ \ln(1 - 4\delta^2) \le -\frac{1}{2}W \cdot 2^{n-H_2}/\pi \\ -2\pi\ln(1 - 4\delta^2) \ge W \cdot 2^{n-H_2} \\ \log_2(2\pi) + \log_2(-\ln(1 - 4\delta^2)) \ge \log_2 W + n - H_2 \\ H_2 \ge n + \log_2 W - \log_2(2\pi) - \log_2(-\ln(1 - 4\delta^2)) \end{gathered} \]
\[ \begin{gathered} \frac{1}{2}\sqrt{1 - e^{-2\left(\frac{1}{4}W \cdot 2^{n-H_2}\right)/\pi}} \le \delta \\ 1 - e^{-\frac{1}{2}W \cdot 2^{n-H_2}/\pi} \le 4\delta^2 \\ 1 - 4\delta^2 \le e^{-\frac{1}{2}W \cdot 2^{n-H_2}/\pi} \\ \ln(1 - 4\delta^2) \le -\frac{1}{2}W \cdot 2^{n-H_2}/\pi \\ -2\pi\ln(1 - 4\delta^2) \ge W \cdot 2^{n-H_2} \\ \log_2(2\pi) + \log_2(-\ln(1 - 4\delta^2)) \ge \log_2 W + n - H_2 \\ H_2 \ge n + \log_2 W - \log_2(2\pi) - \log_2(-\ln(1 - 4\delta^2)) \end{gathered} \]

Since \(4\delta^2 \cong 0\) when \(\delta \cong 0\), \(-\ln(1 - 4\delta^2)\) is closely approximated by \(4\delta^2\), so the inequality can be written as:

\(\delta \cong 0\) のとき \(4\delta^2 \cong 0\) なので、\(-\ln(1 - 4\delta^2)\) は \(4\delta^2\) によってよく近似され、不等式は次のように書けます。

\[ H_2 \ge n + \log_2\left(\frac{W}{\delta^2}\right) - \log_2 \pi - 3 \]
\[ H_2 \ge n + \log_2\left(\frac{W}{\delta^2}\right) - \log_2 \pi - 3 \]

This derivation has shown that if the above inequality is satisfied by a sufficiently high value of \(H_2\), then the distinguishing probability \(\mathit{Pr}[\text{Correct}] \le \frac{1}{2} + \delta\). Now note that min-entropy \(H\) is a lower bound on collision-entropy \(H_2\) and consider the following inequality where collision-entropy \(H_2\) is replaced with min-entropy \(H\):

この導出により、上の不等式が十分に高い \(H_2\) の値によって満たされるならば、識別確率は \(\mathit{Pr}[\text{Correct}] \le \frac{1}{2} + \delta\) となることが示されました。ここで、最小エントロピー \(H\) は衝突エントロピー \(H_2\) の下界であることに注意し、衝突エントロピー \(H_2\) を最小エントロピー \(H\) に置き換えた次の不等式を考えます。

\[ H \ge n + \log_2\left(\frac{W}{\delta^2}\right) - \log_2 \pi - 3 \]
\[ H \ge n + \log_2\left(\frac{W}{\delta^2}\right) - \log_2 \pi - 3 \]

If this inequality is satisfied by a sufficiently high value of min-entropy \(H\), then the previous inequality involving collision-entropy \(H_2\) is also satisfied, and \(\mathit{Pr}[\text{Correct}] \le \frac{1}{2} + \delta\).

この不等式が十分に高い最小エントロピー \(H\) の値によって満たされるならば、衝突エントロピー \(H_2\) に関する先の不等式も満たされ、\(\mathit{Pr}[\text{Correct}] \le \frac{1}{2} + \delta\) となります。

証明終。

A.2. Justification of the Claim on Higher Powers of \(\theta_j\)

A.2. \(\theta_j\) の高次の冪に関する主張の正当化

In the proof of Claim 1, sums of the powers of \(\theta_j\) higher than \(\theta_j^2\) were omitted. This does not affect the validity of the conclusion if \(\theta_j\) is sufficiently near zero. This is established as follows. Recall that there are \(2^n\) values of \(\theta_j\), each of which is approximately normally distributed with mean zero and variance approximately \(2^{n-H_2}\). Consider the largest \(\theta_j\): \(\theta_{max} = \max_j\{\theta_j\}\). \(\theta_{max}\) is \(z = \frac{\theta_{max}}{2^{\frac{n-H_2}{2}}}\) standard deviations away from zero (which was shown in A.1 to be the mean of \(\theta_j\)). The value of \(z\) is expected to be such that in a collection of \(2^n\) standard normal random variates, approximately one of the variates is greater than or equal to this value of \(z\). If \(f(z)\) and \(F(z)\) are the density function and the cumulative distribution function of the standard normal distribution, respectively, then for large \(z\), \(1 - F(z) \cong \frac{f(z)}{z}\) (see Section 26.2.12 of [4]). The desired value of \(z\), therefore, gives \((1 - F(z))2^n \cong 1\), which leads to \(\frac{2^n}{z\sqrt{2\pi}} e^{-\frac{z^2}{2}} = 1\), or \(z^2 + 2\ln z = 2n\ln 2 - \ln(2\pi)\). Since \(z^2\) dominates the left side of this equation for moderately large values of \(z\), the desired value of \(z\) is approximately \(\sqrt{2n\ln 2 - \ln(2\pi)}\). The value of \(\theta_{max}\) is then expected to be approximately \(2^{\frac{n-H_2}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}\). For any of the typical values of \(n\) and a value of \(H_2\) given by the lower bound established in Claim 1, \(H_2 \ge n + 64\), so \(2^{\frac{n-H_2}{2}} \le 2^{-32}\), and it can be calculated that \(\theta_{max}\) is a positive value that is likely to be less than \(10^{-8}\). A similar argument leads to \(\theta_{min}\) being approximately \(-\theta_{max}\), so it is expected that \(|\theta_j| \le 10^{-8}\) for all \(j\). Therefore, it is safe to omit powers of \(\theta_j\) higher than \(\theta_j^2\), since it is shown in A.1 that doing so has a negligible effect.

主張1の証明では、\(\theta_j^2\) より高次の \(\theta_j\) の冪の和を省略しました。\(\theta_j\) が十分にゼロに近ければ、これは結論の妥当性に影響しません。これは次のように示せます。\(\theta_j\) の値が \(2^n\) 個あり、それぞれがおおよそ平均ゼロ、分散がおおよそ \(2^{n-H_2}\) の正規分布に従うことを思い出してください。最大の \(\theta_j\)、すなわち \(\theta_{max} = \max_j\{\theta_j\}\) を考えます。\(\theta_{max}\) は、ゼロ(A.1 で \(\theta_j\) の平均であることが示されました)から \(z = \frac{\theta_{max}}{2^{\frac{n-H_2}{2}}}\) 標準偏差分だけ離れています。\(z\) の値は、\(2^n\) 個の標準正規確率変量の集まりの中で、おおよそ1個の変量がこの \(z\) の値以上になるような値であると期待されます。\(f(z)\) と \(F(z)\) をそれぞれ標準正規分布の密度関数と累積分布関数とすると、\(z\) が大きいとき \(1 - F(z) \cong \frac{f(z)}{z}\) です([4] の Section 26.2.12 を参照)。したがって、求める \(z\) の値は \((1 - F(z))2^n \cong 1\) を満たし、これより \(\frac{2^n}{z\sqrt{2\pi}} e^{-\frac{z^2}{2}} = 1\)、すなわち \(z^2 + 2\ln z = 2n\ln 2 - \ln(2\pi)\) が得られます。\(z\) がある程度大きい値であれば、この式の左辺では \(z^2\) が支配的であるため、求める \(z\) の値はおおよそ \(\sqrt{2n\ln 2 - \ln(2\pi)}\) です。すると、\(\theta_{max}\) はおおよそ \(2^{\frac{n-H_2}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}\) であると期待されます。典型的な \(n\) の値と、主張1で確立した下界 \(H_2 \ge n + 64\) を満たす \(H_2\) の値については、\(2^{\frac{n-H_2}{2}} \le 2^{-32}\) であり、\(\theta_{max}\) は \(10^{-8}\) 未満である可能性が高い正の値であると計算できます。同様の議論により、\(\theta_{min}\) はおおよそ \(-\theta_{max}\) となるため、すべての \(j\) について \(|\theta_j| \le 10^{-8}\) であると期待されます。したがって、\(\theta_j^2\) より高次の \(\theta_j\) の冪を省略しても、A.1 で示したとおり影響は無視できるほど小さいため、安全に省略できます。

A.3. Proof of Claim 2

A.3. 主張2の証明

It is shown in A.2 that \(\theta_{max} \cong 2^{\frac{n-H_2}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}\), which implies that the corresponding value \(p_{max} = \max_j\{p_j\}\) is approximately \(2^{-n}\left(1 + 2^{\frac{n-H_2}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}\right)\). If the min-entropy of the input to the conditioning function is \(H\), then \(H_2 \ge H\), so

A.2 で \(\theta_{max} \cong 2^{\frac{n-H_2}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}\) であることが示されており、これは、対応する値 \(p_{max} = \max_j\{p_j\}\) がおおよそ \(2^{-n}\left(1 + 2^{\frac{n-H_2}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}\right)\) であることを意味します。コンディショニング関数への入力の最小エントロピーが \(H\) であれば \(H_2 \ge H\) なので、

\[ p_{max} \le 2^{-n}\left(1 + 2^{\frac{n-H}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}\right). \]
\[ p_{max} \le 2^{-n}\left(1 + 2^{\frac{n-H}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}\right). \]

The min-entropy corresponding to this value of \(p_{max}\) is:

この \(p_{max}\) の値に対応する最小エントロピーは次のとおりです。

\[ \begin{aligned} -\log_2 p_{max} &\ge n - \log_2\left(1 + 2^{\frac{n-H}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}\right) \\ &= n - \frac{\ln\left(1 + 2^{\frac{n-H}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}\right)}{\ln 2} \end{aligned} \]
\[ \begin{aligned} -\log_2 p_{max} &\ge n - \log_2\left(1 + 2^{\frac{n-H}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}\right) \\ &= n - \frac{\ln\left(1 + 2^{\frac{n-H}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}\right)}{\ln 2} \end{aligned} \]

Since \(H \ge n + 64\), \(2^{\frac{n-H}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}\) is a very small positive number, so \(\ln\left(1 + 2^{\frac{n-H}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}\right) \cong 2^{\frac{n-H}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}\), giving

\(H \ge n + 64\) なので、\(2^{\frac{n-H}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}\) は非常に小さい正の数であり、したがって \(\ln\left(1 + 2^{\frac{n-H}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}\right) \cong 2^{\frac{n-H}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}\) となるため、次が得られます。

\[ -\log_2 p_{max} \ge n - \frac{2^{\frac{n-H}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}}{\ln 2} \]
\[ -\log_2 p_{max} \ge n - \frac{2^{\frac{n-H}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}}{\ln 2} \]

Dividing this value by \(n\) gives an average per-bit min-entropy of at least

この値を \(n\) で割ると、1ビットあたりの平均最小エントロピーは少なくとも次のとおりです。

\[ 1 - \frac{2^{\frac{n-H}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}}{n\ln 2} \]
\[ 1 - \frac{2^{\frac{n-H}{2}}\sqrt{2n\ln 2 - \ln(2\pi)}}{n\ln 2} \]

When \(H \ge n + 64\), a per-bit min-entropy of at least \(1 - 2^{-32}c\) is obtained, where \(0 < c < 1\) for all the values of \(n\) of interest. Therefore, when \(H \ge n + 64\), the average per-bit min-entropy of the \(n\)-bit conditioning function output is at least \(1 - 2^{-32}\). Q.E.D.

\(H \ge n + 64\) のとき、関心のあるすべての \(n\) の値について、1ビットあたりの最小エントロピーは少なくとも \(1 - 2^{-32}c\)(\(0 < c < 1\))となります。したがって、\(H \ge n + 64\) のとき、\(n\) ビットのコンディショニング関数出力の1ビットあたりの平均最小エントロピーは少なくとも \(1 - 2^{-32}\) です。証明終。

Appendix B. List of Symbols, Abbreviations, and Acronyms

付録B 記号・略語・頭字語の一覧

DRBG
Deterministic Random Bit Generator

DRBG
決定論的乱数ビット生成器(Deterministic Random Bit Generator)

NIST
National Institute of Standards and Technology

NIST
米国国立標準技術研究所(National Institute of Standards and Technology)

RBG
Random Bit Generator

RBG
乱数ビット生成器(Random Bit Generator)

SP
(NIST) Special Publication

SP
(NIST)Special Publication

\(\varepsilon\)
A positive constant that is assumed to be no greater than \(2^{-32}\)

\(\varepsilon\)
\(2^{-32}\) 以下であると仮定する正の定数

E(\(X\))
The expected value of the random variable \(X\)

E(\(X\))
確率変数 \(X\) の期待値

log2(x)
Base-2 logarithm of x

log2(x)
x の2を底とする対数

ln(x)
Natural logarithm of x

ln(x)
x の自然対数

Var(x)
Variance of random variable x

Var(x)
確率変数 x の分散

Appendix C. Glossary

付録C 用語集

adversary
A malicious entity whose goal is to determine, to guess, or to influence the output of an RBG.

adversary
RBG の出力を判定、推測、または操作することを目的とする悪意のある主体。

bitstring
An ordered sequence (string) of 0s and 1s. The leftmost bit is the most significant bit.

bitstring
0と1の順序付けられた並び(列)。最も左のビットが最上位ビットです。

conditioning function
A deterministic function used to reduce bias and/or improve the entropy per bit.

conditioning function
偏りを減らす、または1ビットあたりのエントロピーを向上させるために用いる決定論的関数。

cryptographic boundary
An explicitly defined physical or conceptual perimeter that establishes the physical and/or logical bounds of a cryptographic module and contains all of the hardware, software, and/or firmware components of a cryptographic module.

cryptographic boundary
暗号モジュールの物理的または論理的な境界を定め、暗号モジュールのすべてのハードウェア、ソフトウェア、ファームウェアの構成要素を含む、明示的に定義された物理的または概念的な範囲。

entropy
A measure of the randomness or uncertainty of a random variable.

entropy
確率変数のランダムさまたは不確実性の尺度。

entropy source
The combination of a noise source, health tests, and optional conditioning component that produce bitstrings containing entropy.

entropy source
エントロピーを含むビット列を生成する、ノイズ源、ヘルス試験、および任意のコンディショニング構成要素の組み合わせ。

full-entropy bitstring
A bitstring with ideal randomness (i.e., the amount of entropy per bit is equal to 1). This publication proves that a bitstring satisfying a certain definition of full entropy has an entropy rate of at least \(1 - \varepsilon\), where \(\varepsilon\) is at most \(2^{-32}\).

full-entropy bitstring
理想的なランダムさを持つビット列(すなわち、1ビットあたりのエントロピーの量が1に等しいもの)。本刊行物は、完全エントロピーのある定義を満たすビット列が、少なくとも \(1 - \varepsilon\)(\(\varepsilon\) は高々 \(2^{-32}\))のエントロピー率を持つことを証明します。

ideal randomness source
The source of an ideal random sequence of bits. Each bit of an ideal random sequence is unpredictable and unbiased, with a value that is independent of the values of the other bits in the sequence. Prior to an observation of the sequence, the value of each bit is equally likely to be 0 or 1, and the probability that a particular bit will have a particular value is unaffected by knowledge of the values of any or all of the other bits. An ideal random sequence of \(n\) bits contains \(n\) bits of entropy.

ideal randomness source
理想的な乱数ビット列の源。理想的な乱数ビット列の各ビットは予測不可能かつ偏りがなく、その値は列中の他のビットの値から独立しています。列を観測する前の各ビットの値は、0である確率と1である確率が等しく、特定のビットが特定の値を取る確率は、他のビットの一部または全部の値を知っても変わりません。\(n\) ビットの理想的な乱数列は、\(n\) ビットのエントロピーを含みます。

likelihood ratio test
A statistical test aimed at distinguishing between two competing models that could have produced an observed event based on a comparison of the likelihoods of the observed event, given the two models.

likelihood ratio test
観測された事象を生じさせた可能性のある二つの競合するモデルのうち、どちらであるかを識別することを目的とする統計的検定。二つのモデルのもとでの観測事象の尤度の比較に基づきます。

min-entropy
A lower bound on the entropy of a random variable. The precise formulation for min-entropy is \((-\log_2 \max p_i)\) for a discrete distribution having probabilities \(p_1, \ldots, p_k\). Min-entropy is often used as a measure of the unpredictability of a random variable.

min-entropy
確率変数のエントロピーの下界。最小エントロピーの正確な定式化は、確率 \(p_1, \ldots, p_k\) を持つ離散分布について \((-\log_2 \max p_i)\) です。最小エントロピーは、確率変数の予測不可能性の尺度としてよく用いられます。