暗号は、今やインターネットや携帯電話をはじめ、社会生活のインフラストラクチャーに必要不可欠な技術となっている。共通鍵ブロック暗号（以下、ブロック暗号）はその中でも高速な暗号化・復号処理が特徴で、秘匿の機能のみならず、擬似乱数生成やメッセージ認証コードのビルディングブロックとして利用されるなど、重要な役割を担っている。

多くの公開鍵暗号が、素因数分解問題や離散対数問題といった計算量的に困難な問題に基づいて設計され、その安全性について理論的に帰着関係が示されているのに対し、公開鍵暗号の1000倍、10000倍もの速度が要求されるブロック暗号については、このような安全性が証明できる設計法は知られていない。よって、ブロック暗号を設計するには、想定されるあらゆる解読法に対する安全性を評価する必要がある。ブロック暗号の設計と解析（強度評価）は車の両輪のような関係で、安全なブロック暗号の設計には、既知の解読法に関する知識と強度評価技術が不可欠となっている。

本論文では、まず、ブロック暗号に対する強度評価において最も重要な解読法、すなわち差分解読法、線形解読法、高階差分攻撃法、補間攻撃法に対する強度評価手法の改良について述べる。

差分解読法及び線形解読法については、これらの解読法に対する強度評価指標をより効率的に計算することが可能になり、現実的な時間で強度評価が行なえるようになった。例えば、これまで数ヶ月必要であった評価計算を3日未満で実行可能となった。

高階差分攻撃法及び補間攻撃法については、これらの解読法に対する強度評価指標をより正確に計算することが可能になり、より厳密に安全性を評価できるようになった。例えば、従来の評価法では、解読には鍵の全数探索よりも多い計算量が必要であるため安全であると予想されていた暗号が、本改良により、実際はそれよりも少ない計算量で解読可能であることが示された。

本論文では、また、このような強度評価技術をもとに設計した128ビットブロック暗号 Camellia について述べる。特に安全性と性能を両立させるための設計指針と強度評価結果について述べている。

本論文の主な成果は以下の通りである。

最良線形特性及び最良差分特性探索の改良：線形解読法及び差分解読法を用いてブロック暗号を解読するのに必要な計算量の下限を見積もるために、最良線形特性及び最良差分特性を導出する必要がある。本論文では、最良線形特性や最良差分特性を探索するアルゴリズムを改良する方法を示した。本改良では、各段でとりうる線形確率及び差分確率の値の組を探索パターンとして導入し、前処理により不必要な探索候補を効果的に枝刈りすることで探索計算量の削減が可能となった。従来、松井によって示されていた探索アルゴリズムではFEAL暗号の8段最良線形特性を求めるのに3ヶ月近く必要であることが試算されていたが、改良アルゴリズムでは3日以内で求めることができるようになった。さらに、この探索により計算されたFEALの最大線形特性確率は、従来 Biham らにより示されていた予測値より大きいこと、FEALの仕様となっている32段では線形解読法に必要な計算量は鍵の全数探索よりも少なく、線形解読法に対し十分な安全性をもつことが示された。

高階差分攻撃法の解読計算量削減：ブロック暗号に対する代数的攻撃法の一つとして高階差分攻撃が知られているが、本論文では従来よりも解読計算量を削減させる新しい高階差分攻撃法を提案する。Jakobsen と Knudsen によって示された高階差分攻撃では、攻撃対象である最終段の鍵を求めるのに、全ての鍵候補に対して全数探索を行っていた。しかし、高階差分攻撃が可能となる条件下では、最終段の鍵に関する代数方程式を立て、これを一次方程式に変換して現実的な計算量で解くことができることに注目した。これにより大幅に解読計算量が削減できる。この攻撃法をカナダ政府標準暗号として有名なCAST暗号ファミリーの一つに適用したところ、217組の選択平文とそれに対応する暗号文を用いて225回以下のラウンド関数の計算に要する計算量で解読できることが分かった。

補間攻撃法の解読計算量削減：補間攻撃法は、ラグランジェ補間公式を利用して暗号アルゴリズムを復元する代数的攻撃法の一つである。本論文では補間攻撃法に必要な平文-暗号文数及び計算量の上限をより厳密に与える強度評価方法を提案する。補間攻撃法では、平文と暗号文の間に成り立つ多項式表現や有理式表現等の代数関係式の項数が強度評価指標となることが知られている。しかし、従来の評価方法ではこの多項式表現や有理式表現の次数をもとにして項数を評価していたため、補間攻撃に必要な計算量を過大評価してしまう傾向にあった。本論文では、数式処理システムを用いることによりこの問題を解決した。すなわち、実際の多項式表現や有理式表現に含まれる項数を厳密に評価し、かつ攻撃に有利な少ない項数をもつ多項式表現を選択することが可能となった。

128ビットブロック暗号 Camellia の設計：Camellia は高い安全性と性能を兼ね備えることを目標に設計された128ビットブロック暗号である。安全性に関しては、これまでに知られているあらゆる攻撃法に対する十分な安全性と、将来の解読法の進歩に耐えるよう十分なマージンをもつよう設計を行った。性能に関しては、ソフトウェア実装・ハードウェア実装の両方に適し、低コストのICカードから高速ネットワークのサーバーまで対応できる柔軟性を自指した。現在のところ、ソフトウェアでの最適化実装では Pentium III(1.13GHz)上で471Mbpsの暗号化速度、ハードウェア小型化実装では0.18μm CMOS ASICライブラリを用いて6.26Kゲートという世界最小クラスを実現している。Camellia は2000年にNTTと三菱電機で共同開発されて以来、現在までに、日本電子政府推奨暗号リスト案に採用されているほか、ISO/IEC、EU NESSIEプロジェクト、IETF、W3C、TV-Anytime Forum等の国際標準機関において規格化が検討されている。

本論文は「Design and Analysis of Block Ciphers (ブロック暗号の設計と解析に関する研究)」と題し、(1)安全な共通鍵ブロック暗号を設計する上で不可欠な解析・強度評価技術の改良と、(2)高い安全性と性能を兼ね備えた共通鍵ブロック暗号の設計法について検討している。安全な共通鍵ブロック暗号を設計するために、既知の暗号解読法に対する定量的な強度（安全性）を厳密かつ効率的に評価することが不可欠となっている。本論文では、代表的な暗号解読法に対する強度評価手法を改良するのに有効ないくつかの手法を示すとともに、これらの解析手法をもとに設計した新しい共通鍵ブロック暗号を提案している。本論文は「Introduction」を含め7章からなり、第2章から第4章までが Part I 「ブロック暗号の解析」、第5章が Part II 「ブロック暗号の設計」という構成となっている。

第1章は「Introduction（序論）」で、本研究の動機となる共通鍵ブロック暗号の動向について整理し、本研究の対象である共通鍵ブロック暗号とその代表的な解読法について述べている。

第2章は「Improving the Search Algorithm for the Best Linear Expression（最良線形特性探索アルゴリズムの改良）」と題し、ブロック暗号に対する最も汎用的かつ強力な攻撃法である、線形解読法及び差分解読法に対する強度指標を計算するアルゴリズムの改良手法を示している。このアルゴリズムは最大線形（差分）特性確率をもつ候補を探索する最適化問題であるが、事前処理により探索不要な候補を効果的に枝刈りできる手法を示した。これにより探索計算量は大幅に削減され、実際にFEAL暗号の強度評価に適用した事例では、従来アルゴリズムでは3ヶ月近く必要であった計算を3日未満で計算可能としている。

第3章は「Improved Higher Order Differential Attack（高階差分攻撃の改良）」と題し、ブロック暗号に対する代数的攻撃法の一つである高階差分攻撃の解読計算量を削減させる手法を提案している。従来法では全ての鍵候補に対して全数探索を行っていた部分を、鍵に関するブール多項式の連立方程式を立て、これを連立一次方程式に変換して現実的な計算量で解くことができることに注目した。これにより高階差分攻撃に必要な解読計算量は大幅に削減され、強度指標を見直す必要が示された。一例として、カナダ政府標準暗号であるＣＡＳＴ暗号ファミリーの一つが現実的な計算量で解読できることが示された。

第4章は「Efficient Interpolation Attack（効率的な補間攻撃法）」と題し、ラグランジュ補間に基づく代数的攻撃である、補間攻撃法に対する強度指標の厳密な評価法を示している。補間攻撃法では、平文と暗号文の間に成り立つ代数関係式に含まれる項数が強度評価指標となることが知られている。しかし、従来の評価方法ではこの代数関係式の次数をもとにして項数を評価していたため、解読計算量を過大評価してしまう場合があるという問題点があった。本論文では、数式処理システムを用いて実際の多項式表現や有理式表現に含まれる項数を厳密に評価することにより、この問題を解決している。

第5章は「Design of Camellia: the 128-bit Block Cipher（128ビットブロック暗号Camellia）」と題し、高い安全性と性能を兼ね備えた128ビットブロック暗号Camellia(カメリア)を提案している。安全性に関しては、これまでに知られている暗号解読法に対する十分な安全性と、将来の解読法の進歩に耐える十分なマージンをもつよう設計されている。性能に関しては、ソフトウェア実装・ハードウェア実装の両方に適し、低コストのＩＣカードから高速ネットワークのサーバまで対応できる柔軟性を目指している。Camelliaは現在までに、CRYPTREC(暗号技術評価委員会)による評価に基づき、電子政府推奨暗号として認定されたほか、EUの暗号評価プロジェクトNESSIEでも、米国政府標準暗号AESと並ぶ推奨暗号として高い評価を受けている。

最後に第7章は「Conclusion（結論）」で、本研究で得られた成果をまとめている。

以上これを要するに、本論文は、共通鍵ブロック暗号の解析と設計に関する体系的な研究をなしており、共通鍵ブロック暗号の強度評価技術に関して世界的にも高いレベルの成果を含み、かつ安全な共通鍵ブロック暗号の設計技術の進歩に貢献したという点で、電子情報工学、特に情報セキュリティ工学上貢献するところが少なくない。

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