本論文では、ブロック暗号（block cipher）の新しい暗号解読手法である線形解読法（linear cryptanalysis）の提案と、線形解読法に対して安全性が保証された新しいブロック暗号の提案をおこなう。

第1章では、本論文を通して用いられる用語の説明と、暗号解読の定義づけがおこなわれる。具体的には、本論文では、固定された秘密鍵のもとで平文が連続的に暗号化されている通信路において、平文と暗号の情報から秘密鍵を、秘密鍵の総当り解読よりも少ない計算量で解読するのが、解読者の目標である。またこのような解読を許さないようなブロック暗号を、安全なブロック暗号であると定義する。これはブロック暗号の安全性に関する最も一般的な考え方である。さらに本章では、米国標準暗号DES（Data Encryption Standard）の成立の背景と、そのアルゴリズムの詳細について図示する。

第2章では、線形解読法の概念を、DESを具体例として説明する。線形解読法の原理は、暗号アルゴリズムを線形近似することにより、複雑なアルゴリズムを簡易化して、もとのアルゴリズムのかわりにこれを解読するというものである。この簡易化されたアルゴリズムは確率的なものなので、解読結果は正しい鍵を示しているとは限らない。しかし、もとのアルゴリズムと、近似されたアルゴリズムの差は、情報量、すなわち平文と暗号文のペアの数で補われ、解読者に得られた情報量が多ければ多いほど、解読結果の確からしさも向上する。本章ではこのアルゴリズム近似の方法論を、DESの最小の非線形コンポーネントであるSBOXからはじめ、アルゴリズム全体に拡大してゆく方向で述べる。ここで複数の近似式を重ねることにより得られる近似式の成立確立を簡単に計算するための方法（Piling-up Lemma）を証明する。結果として、DESは56ビットの鍵の全数探索よりも高速に解読可能であることを示す。

第3章では、第2章の結果を拡張し、計算機による初めてのDES解読実験を行うことが目標である。16段のDESのうち、中間14段を近似することにより、ひとつの式から13ビットの秘密鍵を導出することを目指す。さらにまた同じ確率で成立する式が2種類あるため、合計26ビットの導出が可能である。計算機実験にさきだち、解読効率を見積もるため、8段に縮小したDESによる解読実験をおこない、この結果から、DESは2の43乗程度の既知平文と対応する暗号文のペアがあれば、80％以上の確率で解読が成功するとの結果を得た。16段のDESの計算機による解読は12台のワークステーションコンピューター（PA-RISC 99MHz）によって行われ、50日間で正しい鍵に到達した。

第4章では、DESアルゴリズムに対して、もっとも良い近似式を探索するアルゴリズムを提案する。一般に与えられたブロック暗号アルゴリズムに対して最良な近似式を完全な形でもとめることは、現実的には計算量的に困難である。しかしDESのように小さいSBOXをもつブロック暗号の場合は、最良近似式を現実的な時間で完全に決定することができる。本章ではこの2重再帰アルゴリズムを記述する。次にこのアルゴリズムを用いて、DESの8個のSBOXの順序を変更した場合に差分解読法ならびに線形解読法に対する強度がどのように変化するかを実験した。この結果、DESのSBOXのならびは、差分解読法に対してほぼ最強のものであることが判明した。このことはDES設計者が、設計当時にすでに差分解読法を知っていたことを示している。一方線形解読法に対しては、DESのSBOXのならびは非常に弱い部類に属している。すなわちSBOXの順序を変更するだけで、DESは線形解読法に対する暗号強度を増すことができることを示す。

第5章では、差分解読法と線形解読法に対する証明可能安全性を議論する。証明可能安全とは、差分解読法や線形解読法に対する安全性の指標となる、差分確率あるいは線形確率が十分小さいことを数学的に証明することができるブロック暗号をさす。本章では差分解読法と線形解読法に対する証明可能安全性の評価式は完全にたがいに双対的な形で書き下すことができることをしめす。また証明可能安全性をみたすさまざまなブロック暗号の構成原理を提案する。そのひとつはF関数の位置を変更することにより並列処理性能の向上であり、もうひとつは再帰構造の導入である。さらに不等分分割構造を提案する。これらの構造により、暗号設計者はブロック暗号設計の大きな自由度をえることができる。すなわち、要求されるさまざまなパラメータを組み合わせて、暗号設計ができるようになることを示す。

第6章では、差分解読法と線形解読法に対する証明可能安全なブロック暗号MISTYを提案する。MISTYは第5章で示した、F関数の新しい位置、再帰構造、不等分分割の3つの新提案をすべて含んだ新しいブロック暗号であり、その再帰構造は3階層から構成される。最上位の構成の違いから、MISTY1とMISTY2という2つの具体的なアルゴリズムに分類される。MISTYはハードウエアでの小型化、高速化を狙うために算術演算を用いず、論理演算とテーブルだけでアルゴリズム全体が作られている。またテーブルはハードウエアでの小型化のため、論理ゲートの組み合わせで全体が簡単に構成できるように設計を行った。この結果MISTYは最小6キロゲートでアルゴリズム全体を構成することができる。現在MISTYの設計技術は以下の標準で採用されており、世界中で幅広く用いられている。

CRYPTREC推薦暗号（日本の電子政府のための暗号技術検討委員会）

NESSIE 推薦暗号（欧州における産学共同暗号評価プロジェクト）

ISO/IEC 18033（国際標準機構におけるブロック暗号国際標準）

第三世代携帯電話W-CDMA必須標準暗号

第二世代携帯電話GSM標準暗号

本論文は，「Linear Cryptanalysis of Block Ciphers（ブロック暗号の線形解読法）」と題し，個人のプライバシー保護や機密情報保護に用いられる暗号技術について，ブロック暗号の新しい暗号解読手法である線形解読法の提案と，米国標準暗号DESの世界初の解読実験，ならびにこの線形解読法に対して安全性が保証された，新しい実用的なブロック暗号の提案をおこなっている．論文の構成は「Preliminaries」を含め7章からなる．

第1章は「Preliminaries（序論）」で，本研究の背景を明らかにした上で，ブロック暗号ならびに暗号の安全性の定義について言及し，研究の位置づけについて整理している．さらに本章では，米国標準暗号DESの成立の背景と，そのアルゴリズムの詳細について記述している．

第2章は「Linear Cryptanalysis of the Data Encryption Standard（DESの線形解読法）」と題し，線形解読法の概念を，DESを具体例として説明している．線形解読法の原理は，複雑な暗号アルゴリズムを線形近似することにより簡易化し，もとのアルゴリズムのかわりにこの簡易化されたアルゴリズムを解読するという着想である．本章では，複数の近似式を重ねることにより得られる新しい近似式の成立確率を簡単に計算する公式（Piling-up Lemma）を証明し，結果として，DESは56ビットの鍵の全数探索よりも高速に解読可能であることを示している．

第3章は「The First Experimental Cryptanalysis of the Data Encryption Standard（DESの最初の解読実験）」と題し，計算機による世界で初めてのDES解読実験の詳細を述べている．本章では計算機実験にさきだち，簡易化したDESによる解読実験をおこない，この結果から解読効率を見積っている．完全仕様のDESの計算機による解読は12台のワークステーションコンピュータによって行われ，50日間で正しい鍵に到達したことが具体的に報告されている．

第4章は「How to Derive the Best Expression（最良表現の導出方法）」と題し，DESアルゴリズムに対して，もっとも効率の良い線形近似式を探索するアルゴリズムを提案している．一般に与えられたブロック暗号アルゴリズムに対して最良な線形近似式を完全な形で求めることは，計算量的に困難であるが，本章ではDESのように小さい乱数表をもつブロック暗号の場合に，最良近似式を現実的な時間で完全に決定するアルゴリズムを示し，さらにこのアルゴリズムを用いて，DES設計者が，設計当時にすでに差分解読法を知っていたが，線形解読法は知らなかったはずであるという強い証拠を示すことに成功している．

第5章は「Provable Security of Block Ciphers（ブロック暗号の証明可能安全性）」と題し，差分解読法と線形解読法に対して安全性が証明できるさまざまなブロック暗号の構成原理を提案している．そのひとつは内部関数の位置を変更することによる並列処理性能の向上あり，もうひとつは再帰構造の導入である．さらに不等分分割構造の発明により，暗号設計者はブロック暗号設計の大きな自由度を得ることができること，すなわち，システムで要求されるさまざまなパラメータを組み合わせて，暗号設計ができるようになることが示されている．

第6章は「Design of Block Encryption Algorithm MISTY（ブロック暗号アルゴリズムMISTYの設計）」と題し，差分解読法と線形解読法に対する証明可能安全性をもつ具体的なブロック暗号MISTYが提案されている．MISTYは第5章で示された，F関数の新しい位置，再帰構造，不等分分割の3つの新提案をすべて含んだ新しいブロック暗号である．またハードウエアでの小型化・高速化のため，算術演算を用いず，論理演算とテーブルだけでアルゴリズム全体が構成されており，実用的な性能を実現している．

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

以上これを要するに，本論文では，安全な暗号設計に必要な暗号評価手法としての暗号解読技術からはじめ，既存の暗号にはない特徴をもつ安全な暗号設計の指針と，具体的な暗号アルゴリズムを示したものであり，その技術は現在第三世代携帯電話の必須標準暗号として世界中で用いられており，電子情報学，特に情報セキュリティ工学上貢献するところが少なくない．

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