(本文) In this thesis, we study encryption schemes with various "high functionalities" including one specific focus on broadcast encryption. As for the main contributions, we propose a framework for constructing practical broadcast encryption schemes and a unified framework for public-key encryption with various functionalities.

The first focus of the thesis is on a special but important kind of encryption schemes, namely broadcast encryption. Such a scheme has many useful applications; the most important one to be mentioned is the digital right management. More precisely, broadcast encryption enables the protection of digital contents such as copyrighted DVD. Such a technology is "inevitable" nowadays as modern advancements in communication infrastructure and digital storage technologies have, on one hand, enabled pervasive digital media distribution, but on the other hand, also allowed the spread of "pirate" contents to be done easier than ever before.

There are some broadcast encryption schemes available in the literature; however, as the number of all users in the system tends to be increased, these existing solutions tend to be quite inefficient, and eventually cannot be used in the real-world application. Our focus is then to construct practical broadcast encryption schemes, which can be "scalable", in the sense that the efficiency of scheme will not be affected by the increasing number of users. As a result of the research, we achieve this goal by constructing the first schemes whose the main two parameters, namely the ciphertext size and the private key size, are independent of the number of all users, while the computational cost is semi-scalable (namely, the cost is increasing but slowly as logarithmically). Behind this scheme, we proposed a theoretical framework that can be used to construct efficient schemes in a systematical way.

The second topic shifts the research focus from the practical point of views to more theoretical ones and looked beyond to more general encryption schemes with "high functionalities". The motivation came from the fact that in recent years, there have been many cryptographic primitives which extend the normal public-key encryption to achieve useful functionalities such as ID-based encryption, Key-insulated encryption, Forward-secure encryption, Certificate-less encryption, and many more. Each functionality is proved to be useful in different scenarios and applications thereof. Although being seemingly related primitives, there was no unified framework for defining or constructing them.

In this work, we proposed a unified framework called Directed Acyclic Graph Encryption (DAGE) that unifies these highly-functional encryption primitives into a unified syntax, a unified security notion, and unified generic/specific constructions. More precisely, we reduce a specification of such a primitive to its necessary and sufficient information, which is turned out to be its underlying graph: by specifying a graph, the definition and constructions will be automatically induced by the framework. We also give a primitive implication theorem which gives a simple criterion whether a primitive implies another.

In the theoretical point of view, the merits of the proposed framework are direct. It helps understanding the theoretical essences of the encryption schemes with high-functionalities from our unified characterization. This result simplifies the previous complicated researches into one piece. The result on the primitive implication theorem gives an automated verification of relations among primitives. This reduces the proof of relations which has to be performed based on complexity-theoretic approaches in the previous individual researches, which is quite complicated and can be verified only by human, to the logical-based approach, which is much simpler and can be verified automatedly by computer.

The proposed generic construction implies the possibility result for arbitrary graphs. This has merits not only in the theoretical point of view but also in the practical point of view where the protocol designer can just specify a "tailor-made" graph for the on-purposed application and the implementation of the scheme will be prompted to use. Furthermore, any esoteric scheme featured with many combined functionalities can be directly implemented; for example, a forward-secure certificate-less public-key encryption with keyword-searchability. This is also something that previous works cannot achieve, particularly since there was no unified framework to cope with.

For the third main topic, we focus on the combination of the above-mentioned two previous results: public-key broadcast encryption schemes that are simultaneously practical and feature high functionalities. To be able to attain such practical broadcast schemes, it is unavoidable to focus on more specific functionalities (not generic as in the second topic above). We focused on some most useful functionalities, namely forward-security and keyword-searchability. Forward-security enables the private-key updating and guarantees the security of the previously-encrypted ciphertexts even when the present-time private key is exposed. We presents the most practical and scalable forward-secure broadcast encryption so far in the literature. Keyword-searchability enables the search over encrypted data. It has a killer application of encrypted file sharing systems over public database. We presented the first such scheme in the literature.

　本論文は「Unified Frameworks for Practical Broadcast Encryption and Public Key Encryption with High Functionalities(放送型暗号と高機能公開鍵暗号方式のための統合的枠組みに関する研究)」と題し、デジタルコンテンツの著作権管理や高度な機能を伴った秘密情報保護に用いられる暗号技術について、それらを統一的に取り扱う世界で初めての理論的枠組みを提案するとともに、もっとも効率的な放送型暗号方式やもっとも高度なキーワード検索機能付き暗号方式など、多様かつ完成度の高い暗号方式の具体的構成を示している。論文の構成は「Introduction」と「Preliminaries」を含め6章からなる。

　第1章は「Introduction(序論)」で、本研究の背景を述べ、研究の位置づけを明らかにしている。さらに本章では、放送型暗号と高機能公開鍵暗号の関連研究について整理して記述している。

　第2章は「Preliminaries(準備)」で、本論文の第3章以降に使われる記号や暗号要素技術などを体系的に記述している。

　第3章は「Practical Symmetric-Key Broadcast Encryption(実用的な放送型対称暗号)」と題し、効率的な放送型対称暗号方式とその枠組みを提案している。放送型暗号とは、秘密情報を複数の機器に配信する技術である。不正なユーザにコンテンツを再生できないようにさせる無効化が可能なため、映画や音楽などのデジタルコンテンツを配信する際の著作権保護等の有望な産業応用がある。本章では、対称鍵タイプの放送型暗号に関して従来方式を整理し、擬似乱数生成器、落とし戸なしRSA暗号、落とし戸付きRSA暗号、それぞれに基づく三つの枠組みを提案した。これらの枠組みの利点は、根本的な組み合わせ論的構造を決めればそれぞれの枠組みに当てはめることで証明可能安全性を持つ放送型暗号の具体的構成が自動的に得られることである。本章で新たに導いた具体的な構成の中でももっとも重要な結果は、「Subset-Incremental-Chain」という構造に基づく。この構造は、ユーザ鍵サイズと暗号文の長さがシステムの全体ユーザ数に依存せず、かつ計算量を抑えた初めての放送型暗号方式を与える。本方式は、今後デジタルメディアの主流となるであろうBlu-ray DiscとHD-DVDの両方の規格への採用が報じられている既存の放送型暗号方式(Subset-Difference Method)よりもはるかにスケーラビリティの優れた効率的な方式である。

　第4章は「Unifying Public Key Encryption with "High Functionalities"(高機能公開鍵暗号の統一的枠組み)」と題し、多様な高機能公開鍵暗号(Public-key Encryption: PKE)を統一して取り扱うことが可能な枠組みを初めて提案している。ここで高機能公開鍵暗号とは、高度な機能を付加した公開鍵暗号方式、あるいは公開鍵暗号の変形のことをいう。具体例としては、「Forward-secure PKE(フォーワードセキュア公開鍵暗号)」、「Identity-based Encryption(ID情報に基づく暗号)」、「Certificate-based PKE(証明書に基づく公開鍵暗号)」、「Certificate-less PKE(証明書不要な公開鍵暗号)」、「Key-insulated PKE」とそれぞれを階層化した方式などが挙げられる。第3章の放送型暗号の公開鍵版もその一例である。本章の一つ目の成果は、これらの暗号プリミティブを統一し、「Directed Acyclic Graph Encryption」という枠組みでまとめたことである。この枠組みでは、それぞれのプリミティブのグラフ表現を、プリミティブを規定するために必要十分な情報と見なすことが出来る。そのプリミティブの「アルゴリズムの定義」と「安全性概念の定義」と「証明可能安全性をもつ具体的構成法」は、グラフによって自動的に得られる。さらに、新しい機能を持つ公開鍵暗号や、多様な機能の組み合わせを持つ公開鍵暗号などを設計することが出来る。本章の二つ目の成果は、任意の二つのプリミティブがお互いに帰着出来るかどうかの判断の条件(Graph Syntactic Consequence)を提案し、その健全性(Soundness)の定理を示したことである。この条件の利点は、従来の一般的帰着判断に利用されている条件と違い、計算量理論に基づかず完全にフォーマルロジックに基づいているため、自動的な証明検証(Automated Verification)が可能なことである。

　第5章は「Practical Forward-Secure and Searchable Broadcast Encryption(効率的なフォーワードセキュア放送型公開鍵暗号とキーワード検索機能付き放送型公開鍵暗号)」と題し、放送型公開鍵暗号について、効率的な高機能暗号方式を提案している。本章では、第4章の統一的構成法よりも効率を向上させるために、対象となる機能を絞り、Forward Security(フォワードセキュリティ)とKeyword Searchability(キーワード検索機能)に着目した。結果として、ユーザ鍵サイズと暗号文の長さがユーザ数に依存しない初めてのスケーラブルなフォーワードセキュア放送型公開鍵暗号の提案と、Poly-logarithmicサイズの効率を持つキーワード検索機能付き放送型公開鍵暗号の提案を行っている。

　第6章は「Conclusions(結論)」で、本研究の総括を行い、併せて将来展望などについて述べている。

　以上これを要するに、本論文は、世界でもっとも効率的な放送型暗号方式を提案するだけでなく、多様な高機能公開鍵暗号方式を統一して取り扱うことが可能な枠組みを初めて提案して幾多の完成度の高い具体的構成を示し、この分野の集大成として体系的にまとめた論文であり、電子情報学、特に情報セキュリティ工学上貢献するところが少なくない。

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