💻 computer science

A Survey on Complexity Measures of Pseudo-Random Sequences

この論文は、1960 年代に導入されたコルモゴロフ複雑性以降の 40 年間にわたる擬似乱数列の線形・二次・最大次数複雑性、およびそれらとレペル・ジブ複雑性や 2 進数複雑性などの関連する複雑性尺度との関係を網羅的にレビューした調査報告である。

原著者： Chunlei Li

公開日 2026-04-15

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Chunlei Li

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

この論文は、**「サイバーセキュリティの鍵となる『偽のランダム性』を、どうやって測り、どうやって見抜くか」**というテーマについて書かれた調査報告書です。

専門用語が多くて難しそうですが、実は**「魔法の箱（フィードバックシフトレジスタ）」と「パズル」**の話だと考えると、とてもイメージしやすくなります。

以下に、この論文の核心を、日常の言葉と面白い例えを使って解説します。

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

インターネット上の暗号化やセキュリティでは、**「誰にも予測できないランダムな数字の羅列」**が鍵として使われています。

理想のランダム性： 神様がサイコロを振って出したような、完全に予測不能な数字。
現実のランダム性（擬似乱数）： コンピュータという機械が、ある「種（初期値）」から計算して作り出した数字。

問題点： コンピュータは「計算」をするので、原理的には**「ある規則（アルゴリズム）」**に従って数字を作っています。もし、この「規則」が簡単に見つかってしまうと、ハッカーがその数字の並びを全部予測できてしまい、セキュリティが崩壊してしまいます。

そこで重要なのが**「複雑さ（コンプレキシティ）」**という概念です。「この数字の並びを作るのに、どれくらい複雑な機械（ルール）が必要か？」を測るのです。

複雑さが高い＝ 規則が複雑で、ハッカーには見破れない（安全）。
複雑さが低い＝ 規則が単純で、すぐに解かれてしまう（危険）。

2. この論文が扱っている「複雑さ」の種類の紹介

著者の Chunlei Li さんは、過去 40 年間の研究をまとめ、いくつかの「複雑さを測るものさし」について解説しています。

① 線形複雑さ（Linear Complexity）

例え： 「直線的な足し算パズル」
説明： 「前の数字を足し合わせたり、引いたりするだけの単純なルール」で、この数字の並びが作れるか？を測ります。
特徴： 最も古くから研究されており、計算も簡単です。NIST（アメリカの規格機関）のテストでも使われています。
論文の発見： ランダムな数字なら、この「線形複雑さ」は半分の長さくらいになるのが普通ですが、周期を持つ数字（ループする数字）だと、少し違う動きをすることがわかっています。

② 2 次複雑さ（Quadratic Complexity）

例え： 「掛け算パズル」
説明： 「前の数字同士を掛け合わせる」ルールも加えた場合、どれくらい複雑になるか？
特徴： 線形より少し難しいですが、まだ計算可能です。
論文の発見： ランダムな数字の「2 次複雑さ」がどうなるかという理論的な答えはまだ完全にはわかっていません。しかし、もしこの値が小さすぎると、ハッカーが「掛け算のルール」を簡単に推測できてしまうため、暗号には不向きです。

③ 最大次数複雑さ（Maximum-Order Complexity）

例え： 「過去の履歴を全部覚えるパズル」
説明： 「前の数字を足す・掛ける」だけでなく、「過去のあらゆる組み合わせ」をルールに含めても、この並びを作れるか？を測ります。
特徴： これが最も厳しき（強力な）テストです。
論文の発見：
- ランダムな数字の場合、この複雑さは「数字の長さの対数（log）」くらいになるのが普通です。
- 面白い矛盾： 「最も複雑さが高い（＝安全そうに見える）」数字の並び（例：000...001）は、実は**「規則が単純すぎる」**ため、ランダム性としては最悪の部類に入ります。これは「複雑さが高い＝安全」とは限らないことを示しています。

3. 他の「ものさし」との関係

この論文では、上記の「FSR（フィードバックシフトレジスタ）」ベースの複雑さだけでなく、他の有名な測り方との関係も整理しています。

Lempel-Ziv 複雑さ： 「この数字の並びを、どのくらい圧縮できるか？」を測ります。圧縮できたら規則がある証拠なので、圧縮率が高い＝複雑さが低い（危険）です。
2-adic 複雑さ： 「桁上がり（キャリー）がある計算」を使う場合の複雑さです。
相関（Correlation）： 「数字の並びに、隠れたパターン（偏り）がないか」を測ります。

重要な関係性：
これらの「ものさし」は独立しているわけではなく、**「A が小さければ、B も小さくなる傾向がある」**といった関係が成り立っています。つまり、一つのテストで弱点が見つかったら、他のテストでも弱点が見つかる可能性が高いということです。

4. 結論：何がわかって、何がわからない？

この調査報告書（サーベイ）の結論は以下の通りです。

よくわかっていること：
- 「線形複雑さ」については、計算方法も統計的な性質もよく理解されています。
- 「最大次数複雑さ」についても、最近の進歩で計算アルゴリズムが改良され、理解が深まってきました。
まだ謎が多いこと：
- 「2 次複雑さ」や「拡張複雑さ」など、他の複雑さの指標については、理論的な裏付けがまだ不足しています。
- 「最も複雑な数字の並び」が、実は「ランダム性としては最悪」であるというパラドックスは、セキュリティ設計において非常に注意すべき点です。
今後の課題：
- これらの複雑さの指標を、より深く結びつける新しい数学的な道具や理論が必要とされています。

まとめ

この論文は、**「暗号に使われる数字が本当に安全かどうかを判断するための『物差し』を、いくつかの角度から整理し、どれが優れていて、どれがまだ未開拓なのか」**をまとめたものです。

ハッカーが「パズル」を解くのを防ぐために、私たちは「パズルの難易度（複雑さ）」を正しく測る必要があります。この論文は、そのための「測る技術」の現状を詳しく解説しているのです。

論文「A Survey on Complexity Measures for Pseudo-Random Sequences」の技術的サマリー

著者: Chunlei Li (ノルウェー・ベルゲン大学)
概要: 本論文は、疑似ランダム系列のランダム性を評価するための「複雑性尺度（Complexity Measures）」に関する過去 40 年間の主要な研究をレビューした調査論文である。特に、フィードバックシフトレジスタ（FSR）に基づく線形複雑性、二次複雑性、最大次数複雑性（非線形複雑性）に焦点を当て、それらの計算アルゴリズム、統計的挙動、理論的構成、および他の複雑性尺度（Lempel-Ziv 複雑性、2 進数複雑性、相関尺度など）との関係性を体系的に整理している。

1. 問題設定 (Problem)

暗号学やセキュリティ応用（鍵生成、初期化ベクトル、ノンスなど）において、理想的なランダムソースからの区別がつかないビット列の生成は極めて重要である。しかし、現実の乱数生成器（RBG）は破綻し、システム全体のセキュリティが崩壊する事例が後を絶たない。
特に、決定論的アルゴリズムを用いて高エントロピーな初期値からビット列を生成する「疑似ランダムビット生成器（PRBG）」の安全性を評価する際、その出力系列が「いかにランダムか」を定量的に評価する指標が必要となる。
従来のランダム性テスト（頻度、連続性など）に加え、**「系列を生成するために必要な最小の計算リソース（または FSR の長さ）」**を測る複雑性尺度が、予測不可能性の評価において重要視されている。本論文は、線形複雑性だけでなく、より強力な非線形モデル（二次、最大次数）を含む複雑性尺度の現状を包括的に調査し、未解決課題を明らかにすることを目的としている。

2. 手法とアプローチ (Methodology)

本論文は、以下の主要な複雑性尺度について、定義、計算アルゴリズム、統計的挙動、および相互関係を網羅的にレビューする手法を採用している。

線形複雑性 (Linear Complexity, $L_n(s)$ ):
- 系列を生成する最短の線形フィードバックシフトレジスタ（LFSR）の長さ。
- Berlekamp-Massey 法による効率的な計算 ( $O(n^2)$ )。
- 確率論的アプローチ（Niederreiter による連分数との関連付け）を用いたランダム系列の期待値と分散の導出。
- 周期系列に対する離散フーリエ変換（DFT）および Gunther-Blahut 定理を用いた代数的手法。
二次複雑性 (Quadratic Complexity, $Q_n(s)$ ):
- 二次フィードバック関数を持つ FSR による生成に必要な最小長さ。
- 線形方程式系 $M(n, m)F(m) = E(n, m)$ の解の存在条件（ランク条件）に基づく再帰的アルゴリズムの提案（Rizomiliotis ら）。
- 行列 $M(n, m)$ のネスト構造を利用した計算効率化。
最大次数複雑性 (Maximum-order Complexity, $M_n(s)$ ):
- 任意の非線形フィードバック関数を持つ FSR による生成に必要な最小長さ（非線形複雑性とも呼ばれる）。
- DAWG (Direct Acyclic Word Graph) 構築による計算（Jansen）。
- 系列の「固有語（Eigenwords）」の概念と、再帰的な更新アルゴリズム（Berlekamp-Massey 法に類似）の提案。
- 統計的挙動の近似分布モデルの構築（Erdman-Murphy 法）。
他の尺度との関係性の分析:
- Lempel-Ziv 複雑性、2 進数複雑性（2-adic complexity）、展開複雑性（Expansion complexity）、相関尺度との不等式関係や相互変換のレビュー。

3. 主要な貢献と結果 (Key Contributions & Results)

3.1 線形複雑性の理論的基盤の再確認

ランダムな有限長系列の線形複雑性の期待値が $n/2$ に収束すること、およびその分散が一定値に収束することが再確認された。
周期系列については、 $L(s) = n - \deg(\gcd(x^n-1, s_n(x)))$ という代数式が提示され、最大長系列（m-sequence）や Legendre 系列などの代数構造を持つ系列の複雑性が分析された。
「 $d$ -perfect 系列」（線形複雑性プロファイルが $n/2$ に非常に近い系列）の構成問題が提起され、連分数を用いたshift系列の解析手法が紹介された。

3.2 二次複雑性の計算アルゴリズムと未解決課題

二次フィードバック関数の決定には、変数数 $1 + m(m+1)/2$ の線形方程式系を解く必要があることが示された。
行列のランク条件に基づき、項ごとの再帰的アルゴリズムが提案されたが、計算コストは依然として高い。
重要な知見: 二次複雑性が小さい系列は、短くても $O(m^2)$ 程度の連続するビットからフィードバック関数が一意に決定されてしまうため、暗号用途には不適切である。
未解決: ランダム系列における二次複雑性の統計的挙動（期待値など）に関する厳密な理論結果は未だ存在せず、数値実験に基づく $E[Q_n] \approx \sqrt{2n}$ という予想が提示されているのみである。

3.3 最大次数複雑性の完全な特徴付け

最大次数複雑性 $M(s)$ と DAWG の深さ $d(s)$ の関係 ( $M(s) = d(s)+1$ ) が明確にされた。
定理 10 (Sun et al.): $n$ $n$ 周期系列が最大次数 $n-1$ $n - 1$ を持つための必要十分条件が完全特徴付けされた。
- 条件: 系列が $(\alpha, \dots, \alpha, \beta)$ の形（ $\alpha \neq \beta$ ）であるか、あるいはユークリッド互除法に基づく強い再帰構造を持つこと。
- 結論: 最大次数複雑性を持つ系列は、構造的に「ランダムではない（バランス性や安定性が悪い）」ため、暗号用には避けるべきであるという重要な示唆が得られた。
有限長系列および周期系列における最大次数複雑性の分布関数や、 $n/2$ 以上の高複雑性系列の生成アルゴリズムが提案された。

3.4 複雑性尺度間の関係性

不等式関係: $M_n(s) \leq Q_n(s) \leq L_n(s) \leq n$ が成立する。
2 進数複雑性: 最大次数複雑性は 2 進数複雑性によって上から抑えられることが示された。
Lempel-Ziv 複雑性: 最大次数複雑性プロファイルと Lempel-Ziv 複雑性の間には、系列の「固有語」の分布を通じて関連性があるが、一方から他方を完全に推定することはできない。
相関尺度: 線形複雑性や最大次数複雑性が低い場合、高次の相関尺度が必ず大きくなるという下限関係が示された。

4. 意義と結論 (Significance & Conclusion)

本調査論文は、疑似ランダム系列の安全性評価における複雑性尺度の現状を以下のように総括している。

線形複雑性の成熟: 線形複雑性は計算機科学および暗号学において十分に理解されており、NIST のランダム性テストスイートなど実用化されている。
非線形複雑性の課題: 二次複雑性や最大次数複雑性は、より強力な攻撃モデル（非線形フィードバックの推定）に対応する必要があるが、その統計的挙動の理論的解析や効率的な計算手法は線形の場合に比べて未発展である。
高複雑性系列のパラドックス: 数学的に「最大次数複雑性」を持つ系列は、構造的に単純（再帰的）であり、ランダム性としては劣っている。したがって、単に複雑性が高いからといって暗号的に安全とは限らない。
今後の研究方向:
- 二次複雑性や $k$ -エラー最大次数複雑性に関する統計的理論の確立。
- 異なる複雑性尺度間のより深い関係性の解明。
- 高複雑性かつランダム性の高い系列の効率的な構成法の開発。

本論文は、暗号設計者および研究者に対し、単一の複雑性尺度に依存せず、多角的な視点（線形、非線形、相関、圧縮性など）から系列のランダム性を評価する必要性を強く訴え、今後の研究の指針を示す重要な文献となっている。