🔢 mathematics

Correlation Bounds and Markov Analysis for Ring-Oscillator TRNGs: A Joint Validation Framework

この論文は、リング発振器型真乱数発生器の品質評価において、マウラーの Z スコアと 2 次相関測度 $C_2$ 、および高次マルコフ連鎖遷移確率を理論的・計算的に結びつけた初の共同検証フレームワークを提案し、これらを組み合わせた統一的な評価指標の実現可能性を示しています。

原著者： Miguel Alcocer, Ana Isabel Gómez, Domingo Gomez-Perez

公開日 2026-03-17

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Miguel Alcocer, Ana Isabel Gómez, Domingo Gomez-Perez

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

1. 背景：なぜ「本当のランダム」が必要なのか？

現代のセキュリティ（パスワードや暗号）は、**「予測できない数字の羅列（乱数）」**に支えられています。

悪い例： 人間が計算して作った数字は、パターンが見えてしまい、ハッカーに狙われやすくなります。
良い例： 自然界の「熱の揺らぎ」や「ノイズ」から数字を作る「真の乱数発生器（TRNG）」なら、誰にも予測できません。

この論文では、リングオシレーターという、電気の信号がループして振動する仕組みを使って、その「熱の揺らぎ」を乱数に変換する装置の研究をしています。

2. 問題点：「本当にランダムか？」をどうチェックする？

装置を作っても、それが本当にランダムな数字を出しているかどうかがわからないと困ります。これまで、チェックする方法がいくつかありましたが、**「バラバラにチェックしていた」**のが問題でした。

方法 A（マウアーのテスト）： 数字の並びが「圧縮」できるかチェックする。「ランダムなら圧縮できないはず」という考え方です。
方法 B（相関測定）： 前の数字と後の数字に「隠れた関係（パターン）」がないかチェックします。

これらは別々に使われていましたが、**「この 2 つのチェック結果は、実は深くつながっているのではないか？」**というのが、この論文の大きな発見です。

3. 論文の核心：3 つの「魔法の鏡」をつなぐ

著者たちは、以下の 3 つの概念を数学的に結びつけ、新しい「統一されたチェック方法」を提案しました。

マウアーのテスト（Z スコア）： 乱数の「圧縮しにくさ」を測る鏡。
相関測定（C2）： 数字同士の「隠れた仲良し関係（パターン）」を測る鏡。
マルコフ連鎖： 次に来る数字が、前の数字にどう依存するかを計算する「確率の地図」。

【例え話：お茶碗の積み木】

ランダムな積み木： 積み木を適当に積み上げると、どの積み木も独立していて、全体として「ランダム」に見えます。
偏った積み木： もし「赤い積み木は必ず青い積み木の上に載る」というルール（パターン）があると、それはランダムではありません。

この論文は、「赤と青の組み合わせ（相関）」を測れば、「積み木の全体のランダムさ（マウアーのテスト）」も同時にわかることを発見しました。つまり、**「2 つの鏡を同時に覗くだけで、装置の品質が一目でわかる」**ようになったのです。

4. 実験結果：「カウンター方式」が勝った

著者たちは、OpenTRNG というオープンソースのツールを使って、さまざまな設定で実験を行いました。

失敗した方法： 単純に振動の「瞬間」を切り取るだけだと、パターンが残りやすく、ランダム性が低かった（相関が高い）。
成功した方法： **「振動の周期（回数）を数える」**という方法（カウンター方式）を使いました。
- これにより、外部のノイズの影響を相殺（キャンセル）でき、**「 Schmidt の限界」**と呼ばれる理論的な最高水準に近い、非常にきれいなランダムな数字が得られました。

【結果のまとめ】

強い相関： 「相関測定（C2）」の数値が低い（パターンがない）装置は、必ず「マウアーのテスト（Z スコア）」も良い結果を出しました。
新しい基準： これまでバラバラだったチェック項目が、**「C2 が 0.01 未満かつ Z スコアが 2 未満」**という 2 つの条件を満たせば、ほぼ間違いなく高品質な乱数であることがわかりました。

5. 結論：デザイナーへのプレゼント

この研究は、新しい乱数発生器を作るエンジニアにとって、**「簡易診断キット」**のようなものです。

以前： 複雑なテストを何十回も行って、「たぶん大丈夫かな？」と不安になる。
今：「相関測定」と「マウアーのテスト」の 2 つを計算すれば、**「この設計は完璧だ！」**と自信を持って言えるようになった。

つまり、「数学的な理論」と「実際の実験」をつなぐ橋渡しが完成し、より安全で信頼性の高い暗号システムを作るための道筋が整ったのです。

一言で言うと：
「乱数生成器の品質チェックを、バラバラだった 2 つの指標を『数学的に結びつける』ことで、より簡単かつ正確に行えるようにした画期的な研究」です。

論文要約：リング発振器 TRNG に対する相関境界とマルコフ分析の共同検証フレームワーク

論文タイトル: Correlation Bounds and Markov Analysis for Ring-Oscillator TRNGs: A Joint Validation Framework
著者: Miguel Alcocer, Ana Isabel Gómez, Domingo Gómez-Pérez (スペイン)

1. 背景と問題提起

真乱数発生器（TRNG）は、暗号鍵やノンスなどの生成に不可欠であり、その出力は統計的に高品質で予測不能でなければならない。リング発振器（RO）に基づく TRNG は、その性能と簡便さから広く採用されているが、熱雑音（ジッター）をエントロピー源とする設計において、出力ビット列の統計的性質を厳密に検証する必要がある。

既存の研究では、以下の指標が個別に扱われてきたが、それらの間の相関関係や統合的な検証手法は確立されていなかった。

Mauduit-Sárközy 相関測度 ( $C_k$ ): 擬似ランダム性に対する理論的な境界を提供する。特に 2 次相関 $C_2$ は重要視される。
Maurer のユニバーサル統計テスト: 実用的なエントロピー評価を行うためのテストであり、Z スコア（ $Z$ ）が用いられる。
高次マルコフ連鎖: 出力の遷移確率をモデル化し、エントロピーの境界を導出するために用いられる。

本研究の目的は、これら 3 つの指標（Maurer の Z スコア、2 次相関 $C_2$ 、高次マルコフ遷移確率）を理論的・実験的に結びつけ、リング発振器 TRNG の品質評価を統合するフレームワークを提案することである。

2. 手法と理論的枠組み

2.1 理論的導出

著者は以下の 2 つの主要な定理を導出した。

相関測度とマルコフ遷移確率の関係:
長さ $N$ のビット列 $S$ において、 $k$ 次マルコフ連鎖の経験的遷移行列 $T(X)$ と $k$ 次相関測度 $C_k(S)$ の間に以下の関係が成り立つことを証明した。
$\left| P(\text{遷移}) - \frac{1}{2} \right| \leq \frac{2^{k-2} C_k(S)}{1 - 2^{k-2} C_k(S)}$
この結果は、 $C_k(S)$ が小さい（ランダムに近い）場合、遷移確率が $1/2$ に近づき、高エントロピーが保証されることを示している。
Maurer テストと相関測度の関係:
Maurer テストの関数値 $f_{TU}$ に対して、相関測度 $C_k(S)$ を用いた上下界を導出した。これにより、Maurer テストの Z スコアと相関測度が数学的に密接に関連していることが示された。

2.2 実装とシミュレーション

プラットフォーム: OpenTRNG（オープンソースのリング発振器 TRNG 設計・評価フレームワーク）を使用。
設計アプローチ: Allini らが提唱した「差分カウンタベース」のアプローチを採用。2 つのリング発振器の周期を参照クロックで計数し、その LSB を XOR 合成することで、共通モードのジッターを除去し、独立した熱雑音のみを抽出する。
実験設定:
- 発振器周波数 ( $f_1, f_2$ ) と参照周波数 ( $f_{ref}$ ) を変化させた 58 種類の構成（ERO と COSO の 2 種類）。
- XOR 累積深度 ( $n = 1, 2, 4, 8, 16$ ) を変化させた。
- 各構成で $N=10^5$ ビットのデータを生成し、 $C_2$ と Maurer の Z スコアを計算。

3. 主要な結果

3.1 相関関係の発見

実験結果から、以下の重要な知見が得られた。

強い正の相関: Maurer の Z スコアとオフピーク 2 次相関 $C_2$ の間に、ピアソン相関係数 $r = 0.95$ の強い正の相関が確認された。
品質基準の明確化:
- $|Z| < 0.1$ の構成は、一貫して $C_2 < 0.01$ を達成していた。
- 高い $C_2$ 値（> 0.8）は $Z > 1$ と相関し、ランダム性からの逸脱を示していた。
XOR 累積の効果: XOR 累積深度 $n$ を増やす（ $n \geq 4$ ）ことで、性能が理想的な領域（ $|Z| \approx 0, C_2 < 0.01$ ）に近づくことが確認された。

3.2 サンプリング方式との比較

直接ビットサンプリング: 従来のビット直接サンプリング方式では、 $C_2 = 0.34$ 、 $Z = -2.1$ （テスト失敗）となり、乱数性が低かった。
カウンタベース方式: 本研究で採用したカウンタ方式では、 $C_2 = 0.009$ 、 $|Z| < 1$ （テスト合格）となり、 $C_2$ 値が約 40 倍改善された。

3.3 理論的限界との比較

Schmidt が改善した相関境界（ $C_k(S) \leq \sqrt{2k \ln N / N}$ ）に基づき、 $N=10^5, k=2$ の場合の目標値は $C_2 \lesssim 0.021$ である。実験結果では、最適な構成においてこの理論限界をさらに下回る $C_2$ 値（2〜3 倍の余裕）を達成しており、実装の有効性が裏付けられた。

4. 貢献と意義

本研究の主な貢献は以下の 3 点である。

初の統合的検証フレームワークの提案:
従来の個別評価ではなく、Maurer の Z スコアと $C_2$ 相関を結びつけた初の経験的・理論的フレームワークを提供した。これにより、TRNG の品質評価が「Maurer テストの合格」と「 $C_2$ の低さ」という 2 つの指標の組み合わせで簡略化・統合化された。
理論的関係性の確立:
相関測度 $C_k$ とマルコフ遷移確率、および Maurer テストの間の数学的関係を導出した。これにより、組み合わせ論的な評価（相関）と確率論的な評価（マルコフ・エントロピー）の架け橋が作られた。
実用的な設計指針の提示:
OpenTRNG を用いたシミュレーションにより、カウンタベースの差分抽出が理論限界を十分に下回る性能を持つことを実証した。設計者に対して、「 $C_2 < 0.01$ かつ $|Z| < 2$ 」を満たす構成を選定すれば、NIST や AIS31 などの包括的なテストスイートを通過する可能性が高いという実用的な検証プロトコルを提案した。

5. 結論

本論文は、リング発振器 TRNG において、Mauduit-Sárközy 相関測度と Maurer テストが密接に関連していることを初めて実証し、これらを統合した効率的な品質評価手法を確立した。このアプローチは、新しい TRNG 設計の研究を簡素化し、設計欠陥の早期検出を可能にするものとして、暗号ハードウェア分野において重要な意義を持つ。今後の課題として、アーキテクチャ固有のより厳密な相関境界の導出や、より高次の相関への拡張が挙げられている。