様々な暗号アルゴリズムに対する安全性評価手法を提案する。従来、暗号の安全性評価は限られた専門家以外には実行不可能であったが、本提案手法により専門家以外でも容易に安全性評価を行うことを可能にした。更に非専門家が新たに安全な暗号を設計するための設計手法も与えた。また提案手法の有効性を示すため、従来広く知られているアルゴリズムの安全性評価を行い、その有効性を実証した。

対称鍵暗号やハッシュ関数には大きく分けて、次の2つのクラスの解読法が知られている。1つは差分解読法、線形解読法、トランケイテッド差分解読法、不能差分解読法に代表される統計的手法に基づく解読法であり、もう1つはXL、XSL、グレブナー解読法に代表される代数的解読法である。ここで差分解読法は1991年にBiham, Shamirにより提案された解読法であり、線形解読法は三菱電機の松井氏により1994年に提案された解読法である。差分解読法については選択平文攻撃（解読者に都合のよい平文を自由に選んだ後に暗号に入力し、得られた暗号文と元の平文のペアを複数利用して鍵を推定する解読法）で、線形解読法については既知平文攻撃（既知の平文を暗号に入力し、得られた暗号文と平文のペアを複数利用して鍵を推定する解読法）であり、共にDES（従来の米国標準暗号）の解読に成功し、暗号解読における歴史的な成果とされている。またグレブナー基底アルゴリズムは1979年にBuchbergerによって提案された連立方程式の一般的な計算アルゴリズムであり、XL、XSLアルゴリズムはその改良アルゴリズムとしてそれぞれ2000年と2002年にフランスのCourtoisらにより提案された解読法である。XSLにより現在世界標準暗号となりつつあるAES（Advanced Encryption Standard） が解読可能である、という主張が2002年になされ、暗号研究者以外にも世界的な注目を集めていた。

本論文ではこれらの解読法を現在世界で用いられている様々な暗号に適用し、その有効性を検証した。特に世界的に広く知られているブロック暗号Camellia, E2, AESの差分解読法、トランケイテッド差分解読法、不能差分解読による暗号解析の手法を提案し、それら解読法に対して安全な暗号を設計するための設計手法も提案した。またXL, XSLとグレブナー基底アルゴリズムの関係について明らかにし、XSLが実はグレブナー基底アルゴリズムの一部であり、全てがグレブナー基底計算帰着しているため、この方法によりAESを解読するのは困難であることを明らかにした。最後に統計的手法と代数的手法を組み合わせることにより、近年解読法が発表され社会化しているSHA-1の差分解読法による解析も行い、衝突計算の詳細を世界で初めて明らかにした。

Chapter 2ではブロック暗号Camelliaのトランケイテッド差分解読法、不能差分解読法に対する安全性評価を行った。ブロック暗号CamelliaはNTTと三菱電機により提案されたブロック暗号で、全ての暗号解読法に対して安全性を保証可能な暗号として提案された。Camelliaは128ビットブロックサイズを入力とし、鍵長については128ビットと256ビットの可変でありAESと同様の仕様となっている。また全ての演算がワード単位の演算によって構成されている。Camelliaの主要な構造は、Feistel構造と呼ばれる従来の世界標準であったDES等で用いられた段構造を踏襲し、各段中のラウンド関数と呼ばれる関数として、バイト単位の表置換（Substitution）とバイト単位の線形変換（Permutation）を合成したSPの2層構造を採用している。Camelliaは現在ISO/IEC JTC 1/SC27で世界標準として採用されており、他にもNESSIE （New European Schemes for Signature, Integrity and Encryption）, CRYPTREC （CRYPTography Research & Evaluation Committee of Japan）, ISO, IETF, SSL等で標準として採用されている。ブロック暗号CamelliaはAES公募にNTTによって応募され不採用となったE2の改良版であり、大きな変更点はラウンド関数が従来SPS（Substitution, Permutation, Substitution）の3層構造であったものをSP（Substitution, Permutation）構造に変更した点にあり、更に6段ごとに挿入されているFL関数により安全性が高められている。

このブロック暗号Camelliaに対してMatrix-methodというトランケイテッド差分確率の計算方法を新たに提案し、この手法とCamelliaについて固有の性質とを融合して、FL関数なしの場合に9段Camelliaでのトランケイテッド差分と呼ばれる統計的偏りがあることを示した。さらに7段で不能差分と呼ばれる別種の統計的偏りを発見した。従来トランケイテッド差分解読法においては6段、不能差分解読法においては5段までしか統計的偏りが発見されておらず、以後現在に至るまでにこれを上回る段数の統計的偏りは発見されていない。また実際のCamelliaにおいてはFL関数があるため解読が不可能であることも示し、ブロック暗号Camelliaの安全性を示す根拠として世界中の標準化で本成果が参照されている。

Chapter 3ではXLアルゴリズムと従来から知られていたグレブナー基底アルゴリズムとの関係を明らかにした。ブロック暗号AESは線形解読法、差分解読法の進展に伴うDESの安全性低下に伴い、米国NIST（National Institute of Standards and Technology）により新規に公募され、以後数年間に渡り世界中の研究者が参加した公開審査の後に制定されたブロック暗号である。AESは表置換（Substitution）とバイト単位の（GF（28）上の）線形変換（Permutation）が交互に重なったSPN（Substitusion and Permutation Network）と呼ばれる構造から成り立っており、各段が代数的に簡略な構造から成り立っているという特徴がある。Chapter 3では、XLが扱っていた連立方程式のクラスに対し、連立方程式を解くことが既約グレブナー基底を計算することと一致することを証明した。さらにXLアルゴリズムが実はグレブナー基底アルゴリズムであり、既知の高速グレブナー基底計算アルゴリズムであるF4を冗長にしたものに過ぎないことも証明した。

従来XLアルゴリズムは完全なグレブナー基底アルゴリズムを計算する必要がないために高速であるという主張がなされていた。しかしChapter 3の結果は、XLアルゴリズムが与えられた連立方程式に対応する既約グレブナー基底をF4アルゴリズムよりも冗長なアルゴリズムで計算しているに過ぎないことから、予想されていたよりも非効率的であることを示している。

さらにこれら理論的な検討に加え、世界最速のグレブナー基底計算プログラムであるMagmaを超える世界最高速実装に、暗号学的に重要であるGF（2）上で成功した。さらにこのプログラムをグリッドコンピュータ上にも実装してToyocryptというストリーム暗号の世界初の解読に成功した。ここでToyocryptとは2000年に公募された電子政府推奨暗号に応募された暗号の一つで、結局不採用となったものの、その後世界的な学会で代数的解読法を用いた理論的な解読法が発表され世界的に有名になったストリーム暗号である。

Chapter4では、近年中国のWangによって解読法が発表され、暗号学会のみならずPKIなどの認証の世界でも大問題となっているハッシュ関数SHA-1の解読法の技術的詳細について解析した。

ハッシュ関数SHA-1は最長264のメッセージから160ビットのハッシュ値を出力する関数でPKI認証などあらゆる場面で最も広く用いられているハッシュ関数である。SHA-1は米国NISTにより1995年にFederal Information Processing Standard （FIPS）という政府調達基準として標準化されている。

SHA-1はMerkle/Dangardと呼ばれるメッセージ列に対して連鎖的にハッシュ値を計算する構造を有し、データ構造としてはchaining valueと呼ばれる160ビットのレジスタビットと512ビットのmessage blockから構成され、chaining valueの初期値IVは固定されている。

具体的な処理としては、16×32ビットのメッセージから80×32ビットの拡大メッセージを線形変換により生成し、80個の拡大メッセージを順々にchaining valueに作用させていき、最後に得られたchaining conditionが出力ハッシュ値となる。

従来Wangの衝突発見法の概略については明らかにされているものの、解析に用いる差分パスの発見方法、Message Modification Techniqueと呼ばれる衝突発見確率を劇的に向上させる技術の詳細等、大部分の詳細が明らかにされていなかった。Chapter4では2つの有効な差分パスを組み合わせることによってさらに有効な差分パスを構成する手法について提案し、この方法によりWangの差分パスを含むクラスの有効な差分パスが発見可能であることを示した。またMessage Modification Techniqueが実質的にグレブナー基底計算に帰着することを示した。さらに基底計算に必要なelimination orderと呼ばれる変数の順序を導入することで、代数的手法に基づくMessage Modificationに成功し、その技術的詳細を世界で初めて明らかにした。さらにWangによるSufficient ConditionにMessage Modificationのための条件を追加したAdvanced Sufficient Conditionとうい条件を新規に導入し、衝突発見手法の視覚化に成功した。本手法をWangにより衝突パターンが実際に発表されている58段の簡略版のSHA-1について実際にコンピュータ実装し、全てのMessage Conditionと1-22段のChaining Value Condition全てを満たすようにMessage Modificationすることに実際に成功し、その有効性を実証した。

本論文は「Security Evaluation of Cryptographic Algorithms by Statistical and Algebraic Methods（統計的及び代数的手法に基づく暗号アルゴリズムの安全性評価）」と題し，安全な暗号アルゴリズムを構成する上で不可欠な安全性評価手法に関し，理論的評価手法として代表的な統計的手法と代数的手法の二つについて論じたものである．安全な暗号アルゴリズムを構成する上で理論的評価手法は必須であるが，実際に暗号アルゴリズムを設計する場合には，さらに，この安全性評価手法に対して安全に構成するための設計指針を立てることが重要となる．本論文は，これらの問題に対し，有効な解決策を示したものであり，「Introduction」を含め5章からなる．

第1章は「Introduction（序論）」で，本研究の背景を明らかにした上で，研究の動機と目的について言及し，研究の位置付けについて整理している．

第2章は「Security analysis of block ciphers（ブロック暗号の安全性）」と題して，ブロック暗号Camelliaの打切り差分解読法，不能差分解読法に対する安全性評価を行った．このブロック暗号Camelliaに対してMatrix-methodという打切り差分確率の計算方法を新たに提案し，この手法とCamelliaについての固有の性質とを融合して，FL関数と呼ばれる部分を削除し簡略化した9段Camelliaについて打切り差分と呼ばれる計測値に統計的偏りがあることを示した．さらに7段で不能差分についても統計的偏りを発見した．

第3章は「Security analysis of polynomial based cryptographic algorithms by algebraic attack - Relation between the XL algorithm and Grobner Basis Algorithms（多変数多項式暗号アルゴリズムの代数的攻撃による安全性解析 - XL法とグレブナー基底法の関係」と題し，最近Courtoisらが提案し話題となったXL法と従来から知られていたグレブナー基底法との関係を明らかにしている．まず，XL法が扱う連立方程式のクラスに対し，これを解くことが既約グレブナー基底を計算することと等価であることを示し，XL法が実は既知の高速グレブナー基底計算法F4を冗長にしたものに過ぎないことを証明した．さらに，暗号学的に重要なGF（2）上のグレブナー基底計算プログラムの世界最高速実装を実現した．また，このプログラムをグリッドコンピュータ上にも実装してToyocryptというストリーム暗号の世界初の解読に成功した．

第4章は「Security analysis of hash function - Finding new differential patterns of SHA-1 and improvement of Wang's message modification technique （ハッシュ関数の安全性解析 - SHA-1の新しい差分パターンの発見とWangのメッセージ修正手法の改良」と題し，最近中国のWangによって攻撃が発表され，暗号学会のみならず情報セキュリティの世界で大問題となっているハッシュ関数SHA-1の解読法の技術的詳細について解析した．従来Wangの衝突発見法の概略については明らかにされているものの，解析に用いる差分パスの発見方法，メッセージ修正手法と呼ばれる衝突発見確率を劇的に向上させる技術の詳細は明らかにされていなかった．ここでは2つの有効な差分パスを組み合わせることによってさらに有効な差分パスを構成する手法について提案し，この方法によりWangの差分パスを含む有効な差分パスが発見可能であることを示した．またメッセージ修正手法が実質的にグレブナー基底計算に帰着することを示した．さらに基底計算における項の消去順序に工夫を加えることで，代数的手法に基づくメッセージ修正に成功し，その技術的詳細を世界で初めて明らかにした．

最後に第5章は「Conclusion（結言）」で，本研究の総括を行い，併せて将来展望について述べている．

以上これを要するに，本論文は，Camellia, 多変数多項式暗号, SHA-1など暗号アルゴリズムに対する理論的安全性評価手法を提案するとともに，安全な暗号アルゴリズムの設計指針を明示したものであり，電子情報学，特に情報セキュリティ工学上貢献するところが少なくない．

よって本論文は博士（情報理工学）の学位請求論文として合格と認められる．