暗号の第一義的な意味は、誰もが盗聴することができる公開通信路上における守秘通信を実現することにある。しかしながら、盗聴者自身がシステムの正規のユーザである場合など、状況によっては、受動的な盗聴に対してだけでなく、能動的なより強力な攻撃を想定しなければならない。このようなより一般的な状況を議論する現代暗号にとって要求される安全性が、攻撃者が選択暗号文攻撃に対する安全性である、という認識が確立するまでに20年以上の歳月が必要であった。さらに、このような安全性を持つ暗号の構成法については、最近まで知られていなかった。

本論文では、より一般的なシナリオとして、多重暗号を議論する。多重暗号とは、簡単に言えば、いくつかの暗号を一つのメッセージを暗号化する方法であり、それぞれの暗号は全体に対する部品として考えることができる。部品が一つの場合、即ちたった一つの暗号による多重暗号を考える場合は、従来の伝統的な暗号であると考えることができるため、その意味において、多重暗号は従来の暗号を含んでいる。

多重暗号の安全性については、限定された場合については、すでに研究が行われており、そこでは多重暗号により安全性が強められるか、もしくは、少なくとも部品中の特定の暗号と同じ程度安全である、というある意味で直感的な結論が示されている。しかし本論文では、この結論が必ずしも正しくなく、鍵漏洩と選択平文攻撃を考えた場合には、多重暗号の結果、それを構成しているどの暗号の安全性よりも低下することがあることを指摘する。

多重暗号は、いくつかの標準化委員会において、安全性を高めるための方法として推奨されているだけでなく、ミックスネットなどのプロトコル実現のためのきわめて有効な構成要素として利用されてきた事情があり、われわれの結果の持つ意味は極めて大きい。これにより、安全な多重暗号が存在するのか、さらに、もし存在するとすれば、どのようにそれを実現できるのか、という問題が極めて現実的な意味を持つことになるからである。

本論文では、上記の二つの問題に対する肯定的な解答が与えられる。即ち、安全な多重暗号が存在すること、および、安全な多重暗号のいくつかの具体的な構成方法が示される。特に、多重暗号のモデルを定式化し、多重暗号のための安全性の概念を理論的に整備した。

モデルの定式化については、まずは、ランダムオラクルを仮定した定式化を行い、その後ランダムオラクルの存在を仮定しないスタンダードモデルにおいても可能なことを示した。

安全性の概念の理論的整備については、我々は、さまざまな安全性概念の間の関係について分析すると同時に、安全性証明に必要な概念を簡単な工学的操作により扱うことができる方法を指摘する。

また、単一鍵による多重暗号についても研究を行った。これは、復号サーバが、構成暗号すべてについてたった一つの鍵を知っている状況である。この研究には、（IDに基づく）暗号の安全性を解くことが難しいとされる他の数学的問題へタイトに帰着する際に必要な、重要なテクニックを与えるという応用がある。また、匿名の鍵更新方式の安全性を証明する際にも同様のテクニックを用いることができる。

さらに、我々はAll-or-Nothing と呼ばれるある種の秘密分散方式を用いた暗号システムの安全性について解析を与えた。この解析は、パラレルな多重暗号、あるいはそれと類似の方式と密接な関係があるが、従来研究では、このような暗号システムの安全性については不明瞭であり、我々の研究はその意味においても大きな貢献であると自負している。

本論文は「On The Security Of Multiple Encryptions（多重暗号化の安全性に関する研究）」と題し，高い安全性を持ち効率的な暗号プロトコルの構成に不可欠な多重暗号化の安全性に関する，評価・解析を行ったものである．特に

（1）一般的な構成手法に固有の安全性問題

（2）安全性の定義（厳密なモデルと安全性評価手法）

（3）選択暗号文攻撃に対し安全な方式の構成手法

の三つの観点から詳細な考察を行っている．

多重暗号化は従来の暗号化方式の拡張であり，暗号の国際標準においても従来の暗号に長期的な安全性を付与する方式として推奨されている．また，暗号プロトコルの汎用的な構成手法の一つとして，理論・実用上の両面において極めて重要な基礎技術であることが知られている．しかし，必要な安全性を厳密に定義できるモデルや，選択暗号文攻撃に対し安全な多重暗号化方式の構成手法などは，これまで未解決であり，多重暗号理論の整備が急務の課題とされていた．本論文は，これらの課題に対し厳密な考察を行い，有効な解決策を示したものである．本論文は「Introduction」を含めて7つの章から構成されている．

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

第2章「Model and Security Definitions（モデルと安全性定義）」では，多重暗号化のモデルを厳密に定義している．具体的には，（1）鍵を漏洩するオラクルを導入し，（2）強秘匿性（Indistinguishability）と頑強性（Non-Malleability），および弱選択暗号文攻撃（weak Chosen Ciphertext Attack）と弱頑強性（generalized Non-Malleability）に基づく定義を行っている．

第3章「Relations among Security Notions（安全性定義の関係）」では，多重暗号のモデルを定式化し，多重暗号のための安全性の概念を理論的に整備した．安全性の概念の理論的整備については，さまざまな安全性概念の間の関係を明らかにすると共に，安全性証明に必要な概念を簡単な操作で扱う手法を示す．

第4章「Secure Constructions（安全な構成手法）」では，前章で定義した安全性を満たす多重暗号が存在するかどうか，また，存在するとすれば，どのようにそれを実現できるか，という実際的に二つの問題に対し，肯定的な解答を与えている．ここでは，ランダムオラクルを仮定した定式化を行うだけでなく，ランダムオラクルを仮定しないスタンダードモデルにおいてもその定式化が可能なことについて詳細に説明している．

第5章「Multiple Encryption with Fewer Keys（より少ない鍵を使った多重暗号）」では，構成要素となっている各暗号方式の数より秘密鍵が少ない場合の多重暗号方式のモデルを示し，さらに三つの汎用的な構成手法を提案している．また，この手法の応用として，IDベース暗号を考察し，そこで未解決問題であった帰着効率についても，双線形DH判定問題に基づく手法を用いて解決した．

第6章「Applications（応用）」では，多重暗号化技術を使った，さまざまな応用例を挙げている．具体的に，鍵隔離暗号，閾値暗号，証明書に基づく暗号（証明書不要暗号），放送暗号，耐解読暗号，キーワードサーチ可能な公開鍵暗号，代理暗号，ミックスネット，オニオンルーチングなどについて，汎用的な構成法を提案した．特に，鍵隔離暗号については，選択暗号文攻撃に対し安全な汎用的構成法を初めて提案している．また，あわせて閾値暗号についても考察を行い，従来手法より効率のいい方式の導出に成功している．

第7章は「Conclusion（結言）」で，本研究の総括を行い将来の展望について述べ，本論文をまとめている．

最後に，付録では並列多重暗号と密接な関係があるAll-or-Nothing と呼ばれるある種の秘密分散方式を用いた暗号システムの安全性について解析を行っている．

以上これを要するに，本論文は，多重暗号化の安全性に関する基礎検討，厳密なモデルとそれに基づく安全性の定義，およびその理論的整備を行い，その応用として汎用的かつ安全な暗号プロトコルの構成手法を示したものであり，電子情報学，特に情報セキュリティ工学上貢献するところが少なくない．

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