本論文では,NIST乱数検定のLZ検定の問題点に対処するにあたって直面したT-codeとT-complexityの解析と応用に関する問題に取り組み,次の項目を明らかにした.(1) 本論文で提案するアルゴリズム(forward T-decomposition)によって逐次的なT-decompositionが実現できること.(2) 本論文で提案する微分方程式の手法を使って理論的にT-complexityのプロファイルが導出できること.(3) 乱数系列に対するT-complexityの分布が特徴づけられること及びT-complexity最大系列の特性が明らかにできること.(4) T-codeに基づいて効率的なユニバーサルデータ圧縮が構成できること及びその性能がUNIXの'compress'よりも良いこと.以上の特性により,T-complexityが系列のランダム性の良い指標になる.これらの特性を踏まえて,最後にT-complexityに基づく乱数検定(T-complexity検定)を提案し,それによってLZ検定の問題点の解決とNIST乱数検定の強化ができることを示した.

本論文の第1章で述べた研究背景の概要は次のとおりである.暗号の安全性評価には,擬似乱数生成器からの出力系列のランダム性の計測が含まれる.その方法には,(1) 統計的手法による計測 (2) 情報理論の立場に基づく系列の圧縮性による計測がある.後者の方法の究極は,コルモゴロフ複雑度である.系列sのコルモゴロフ複雑度K(s)は,sを生成する最も短いプログラムサイズである.K(s)がsのサイズより小さければ,sはランダムではないと考える.このように,系列の複雑度と圧縮は密接に関連するが,一般にK(s)は計算不可能である.LZ-complexityはユニバーサルデータ圧縮LZ78に基づく複雑度であり,コルモゴロフ複雑度の推定に広く用いられる.NIST乱数検定は,米国商務省標準技術局NISTの文書SP 800-22が規定する乱数検定セットであり,暗号の統計的評価のために標準的に使われてきた.NIST乱数検定にはLZ-complexityに基づく乱数検定(LZ検定)が含まれていたが,LZ検定には問題があり,2008年に公式に除外された.情報セキュリティの分野では複雑度に基づく評価が極めて重要であるため,LZ検定の問題の解決が望まれるが,LZ-complexityを使う限り解決は困難である.一方,T-codeに基づく複雑度(T-complexity)は,LZ-complexityと類似性がある上に,LZ-complexityよりも系列の再帰的構造を良く検出できることが期待できる.そこで,T-complexity検定を構成してLZ検定の問題を解決することを考えた.しかし,その前に,T-codeとT-complexityには次の問題がある.(1) LZ-complexityを求めるためのLZ78増分分解法は逐次処理できるが,T-complexityを求めるためのT-decompositionは,アルゴリズム開始時に系列全体が必要なので逐次処理できない.(2) LZ78系の効率的なユニバーサルデータ圧縮が存在するが,T-codeに基づく効率的なデータ圧縮は存在しない.(3) T-complexityの最大値は乱数系列で達成されず,乱数系列より大きなT-complexityを持つ系列が存在する.

以上の問題を踏まえて,冒頭に述べた項目を第2章以降で順番に示した.以下,T-codeの基本事項を説明した後,本論文を構成する章の内容を述べる.

T-codeの符号語は,符号木を再帰的に成長させることにより,レベル1,レベル2,レベル3…の順に生成する.レベルiの符号語の集合をSiとおく.S0はアルファベットAとする.SiからSi+1を生成する方法は次のようになる.Siから1つの符号語を選び,それをT-prefix pi+1とし,正整数を1つ選び,それをT-expansion parameter ki+1とする.Siを表す符号木を考えると, Si+1の符号木は,Siの符号木のpi+1に対応する葉にSiの符号木全体をki+1回コピーして得られる.A={0,1}のときの生成例を図1に示す.与えられた系列sを分解して,系列sが最長符号語に対応するT-codeのパラメタを決定することをT-decompositionという.T-complexityは,T-decompositionが決定したT-expansion parameterの値をもとに計算できる.T-decompositionは系列を分解して,T-prefixを順番に連結した形にする.各T-prefixは,それまでのT-prefixを再帰的に連結し,最後に1シンボルを付けた形になる.LZ78増分分解法では,各ワードが,それまでのワードの中で自身に最も長く一致するワードの後ろに1シンボルを付けた形になる.このように,LZ78増分分解法とT-decompositionには類似性がある.

第2章では,系列を先頭から逐次処理するT-decompositionアルゴリズムを提案した.2.2節では,T-expansion parameterを1に固定する場合,2.3節では,一般の場合のアルゴリズムを提案した.本アルゴリズムは,図2に例示したようにトライ木を成長させながら実行する.トライ木tiはi番目までのT-prefixを記憶し,i番目のT-prefixは根から番号iを持つ節点までの経路として表現される.系列を読み込みながら,トライ木を根から葉に向かって辿ってT-prefixの構成要素を1つずつ決定することを繰り返すことにより逐次的なT-decompositionが実現できる.本アルゴリズムの計算量のオーダーと計算時間の計測結果も記した.計算時間は実用的な系列長で十分に短い.また,従来のT-decompositionと異なり逐次処理するため,オンラインアプリケーションにも向いている.

第3章は,T-complexity及びLZ-complexityのプロファイルの理論的導出に関する研究である. Titchenerは,T-complexity最大系列のプロファイルが対数積分関数(li関数)で表現できることを実験で予想した.その後,Titchenerらは,li関数をトップダウン的に使って,この予想を理論的に証明した(cf. 3.2節).3.3節では,T-codeの符号木の平均符号語長に関する微分方程式に基づいてT-complexity最大系列のプロファイルを導出する方法を提案した.この導出法は,プロファイルがli関数を使って必然的に表現されることをボトムアップ的に示すことができる点で,先行研究の証明法より優れている.同様の導出法を使って,3.3節の後半では,乱数系列のT-complexityのプロファイルを,3.4節では,LZ-complexity最大系列のプロファイル及び乱数系列のLZ-complexityのプロファイルを求めた.これらの導出結果が,先行研究等の結果と合致することも確認した.このように,本章で提案した導出法には一般性がある.

第4章では,T-complexity最大系列の特性をNIST乱数検定,離散フーリエ変換によるスペクトラム,自己相関関数を使って解析した.4.2節では,T-complexity最大系列とLZ-complexity最大系列の生成アルゴリズムを示した.4.3節では,T-complexity最大系列とLZ-complexity最大系列の解析結果を示した.この解析結果により,T-complexity最大系列は LZ-complexity最大系列よりも非ランダムであることを確認した.また,T-complexity最大系列の非ランダム性の原因を定性的,定量的に考察した.

第5章では,T-codに基づく辞書式データ圧縮法を提案した.5.2節では,LZ78系圧縮を概説し,5.3節では,T-codeに基づくデータ圧縮の唯一の先行研究をまとめ,その問題点を整理した.5.4節では,本提案法の詳細を記した.本提案法は,辞書に追加されるフレーズにT-codeの再帰的構造がある.また, 3方式(A, B, C)のフレーズ作成規則を検討した.5.5節では,従来法,UNIXの'compress'及び本提案法の性能を比較した(表1).本提案法は,従来法及びUNIXの'compress'より圧縮率が良い.なお,C方式のユニバーサル性も考察した.

第6章では,6.1節で暗号分野における乱数検定の研究背景を述べた後,6.2節でT-complexity検定の構成法を示した.本検定で乱数系列を検定したときに異常がないこと(LZ検定の問題点を解決すること)を確認した.6.3節では,2種類の非ランダム系列に対して,T-complexity検定は,NIST乱数検定に含まれる全ての検定,LZ検定,2006年に提案された修正LZ検定よりも検出力が著しく良いことを示した.

第7章で本論文の成果を総括し,今後の課題を次のように述べた.(1) T-complexity検定を普及させること.(2) forward T-decompositionのアルゴリズムを改良して計算量を削減すること.(3) T-complexityの漸近分布の数学的証明を与えること.

図 1 レベル0~4のT-codeの符号木.左方向の枝に0,右方向の枝に1が対応する.

図 2 トライ木の成長過程

表 1 Calgaryコーパスに対する圧縮率の比較

本論文は「Analysis and Applications of the T-complexity (T-complexityの解析と応用)」と題し、7章から構成されている。多くの情報セキュリティシステムでは、その安全性が暗号鍵などの2値系列のランダム性に基づいているため、系列に何らかの偏りがないかを調べる乱数検定が、情報セキュリティシステムの安全性に非常に重要となる。その乱数検定においては、系列のランダム性を測るための指標としての複雑度(Complexity)が重要な役割を果たしている。本論文では、そのような複雑度としてT-complexityを取り上げ、理論およびシミュテーションによりその特性を解析すると共に、データ圧縮や乱数検定への実用的な応用法を提案している。

第1章「Introduction」では、乱数検定や複雑度に対する研究の背景, 目的および従来研究に対する本研究の位置付けを述べている。さらに、T-complexityの基になっているT-codeや関連するLZ-complexity, 統計的乱数検定法などの基本概念をまとめている。

第2章「Forward T-decomposition」では、T-complexityを求めるための系列の新しい分解アルゴリズムを提案している。従来の分解アルゴリズムは、全系列が揃って初めて開始できるオフラインアルゴリズムであったのに対し、本章で提案された分解アルゴリズムは逐次的に処理できる特徴がある。さらに、数値実験により従来のものより、高速にT-complexityが求められることを実証している。

第3章「Differential Equation Method for Derivation of the Formulas of the T-complexity and the LZ-complexity」では、微分方程式を用いてT-complexityのプロファイルを導出する新しい方法論を提案している。従来、T-complexity最大系列のプロファイルが対数積分関数 (li関数)で表現できることが実験的に予想され理論的に証明されていたが、li関数が現れる本質的な理由が分かっていなかった。しかし、本章の解析により、T-complexity最大系列のプロファイルが必然的にli関数で表されることが明らかにされている。また、同様の手法により、一般系列のT-complexityや、LZ-complexityのプロファイルも導出できることも示されている。

第4章「Properties of the Maximum T-complexity Sequences」では、T-complexity最大系列がどのような特性を持つかを,乱数検定などを適用することにより解析している。その結果、T-complexity最大系列はLZ-complexity最大系列よりもランダム性が少ないことを明らかにすると共に、T-complexity最大系列の非ランダム性の原因を定性的、定量的に考察している。

第5章「Application of the forward T-decomposition to Data Compression」では、 3章で提案した系列分解法(forward T-decomposition)のデータ圧縮への応用を取り扱っている。系列の分解法とデータ圧縮符号は密接に関係しており、LZ-complexityの分解法を利用したUnixのcompressは比較的性能のよいデータ圧縮符号として知られている。しかし、T-complexityに対応した性能のよいデータ圧縮法は今まで知られていなかった。本章では、辞書式データ圧縮法において、辞書に登録されるフレーズをforward T-decompositionを利用して登録するデータ圧縮法を提案している。さらに、それらが従来知られていたT-decompositionを利用したデータ圧縮法やcompressなどより性能がよいことを、実際のファイル圧縮性能を比較することにより実証している。この成果は、T-complexityが系列のランダム性を検出するよい能力を持っていることの傍証となっている。

第6章「Application of the T-complexity to Randomness Testing for Cryptography」では、T-complexityを用いた新しい乱数検定法(T-complexity検定)を提案している。T-complexity検定の具体的な構成法を示すと共に、その検定が性能のよい検定法となっていることを実証している。乱数検定としては,NIST(米国国立標準技術研究所)の乱数検定ツールが世界的によく用いられている。しかし、それに含まれていたLZ-complexityに基づくLZ検定に問題があり、排除された状況になっている。これに対して、本章で提案されたT-complexity検定では、そのような問題がないことを明らかにすると共に、従来のLZ検定やそれを改良した修正LZ検定よりも検定能力が高いことを示している。さらに、NIST乱数検定ツールではほとんど検出できないが、T-complexity検定で検出可能な非乱数系列が存在し、T-complexity検定はNIST乱数検定の弱点を補完できる検定法であることが示されている。

第7章「Conclusions」では、本論文の成果をまとめると共に、今後の研究課題を示している。

なお,本論文の成果は、山本博資との共同研究であるが、論文提出者が主体となって新しいアルゴリズムの提案、解析、シミュレーションを行なったものであり、論文提出者の寄与が十分であると判断する。

したがって、博士(科学)の学位を授与できると認める。