Public key encryption (PKE) is a fundamental cryptographic primitive with which we can communicate securely over possibly insecure network without shared secret information in advance. For PKE schemes, security against chosen ciphertext attacks (CCA security) is nowadays considered as a standard security notion needed in most practical applications/situations where PKE schemes are used. Roughly, CCA security captures security against "active" adversaries that can access to an imaginary machine called decryption oracle which on input a ciphertext returns a decryption result of it, and has been shown to imply important strong security notions such as non-malleability and universal composability. Therefore, studies on constructing and understanding CCA secure PKE schemes are important research topics in the area of cryptography. In this thesis, we focus on "generic constructions" of CCA secure PKE schemes from other cryptographic primitives, and make several contributions both from practical and theoretical points of view.

Firstly, aiming at generic constructions that lead to CCA secure PKE schemes with practical efficiency, we focus on the so-called "IBE-to-PKE" transformation paradigm, where IBE stands for identity-based encryption and is a kind of PKE scheme where any string can be used as a public key. This is a methodology that transforms an IBE scheme which only satisfies security against chosen plaintext attacks (CPA security), the least requirement as an encryption scheme, into a CCA secure PKE scheme, and is the only known generic methodology with which we can construct CCA secure PKE schemes with practical efficiency. The biggest problem of this methodology is that the constructed PKE scheme has large ciphertext size, even if we use a practical IBE scheme as a building block. We propose two approaches to overcome this problem. The first approach is to require non-malleability, slightly stronger security than CPA security, for the underlying IBE scheme, and develop a new very simple IBE-to-PKE transformation where we only use one-way function, the weakest primitive used in the area of cryptography, as an additional building block. The second approach is to develop a new efficient encapsulation scheme, which is a special kind of commitment scheme and is a primitive used in one of the previous IBE-to-PKE transformations, from a special kind of pseudorandom generator. Both approaches do not need strong cryptographic primitives as additional building blocks, and lead to CCA secure PKE schemes with smaller ciphertext size than the previous IBE-to-PKE transformations.

Secondly, we focus on the problem of whether it is possible to construct a CCA secure PKE scheme only from a CPA secure one. This is an important fundamental open problem that leads to clarifying a necessary and sufficient condition to realize a CCA secure PKE scheme. Regarding this problem, the best known positive results are the constructions of so-called bounded CCA secure schemes from any CPA secure PKE scheme, where bounded CCA security is security against adversaries that make at most the predetermined number of decryption queries, and thus is weaker than ordinary CCA security. Since we can achieve the best possible security in the bounded CCA security notions, in order to further tackle the fundamental problem, we need new security notions that capture intermediate security notions that lie between CPA and CCA security in a different sense from bounded CCA security. Motivated by this situation, in order to provide a theoretical foundation for further tackling the above problem, we focus on parallel decryption queries for the extension of bounded CCA security, and introduce a new security notion which we call "mixed CCA" security. It captures security against adversaries that make single and parallel decryption queries in a predetermined order, where each parallel query can contain unboundedly many ciphertexts. Moreover, how the decryption oracle is available before and after the challenge is also taken into account in this new security definition, which enables us to capture existing major security notions that lie between CPA and CCA security, including a complex notion like non-malleability against bounded CCA, in a unified security notion. We investigate the relations among mixed CCA security notions, and show a necessary and sufficient condition regarding implications/separations between any two notions in mixed CCA security. We then show two black-box constructions of PKE schemes from CPA secure ones, one of which satisfies a strictly stronger security notion than the security notions achieved by the existing constructions of PKE schemes constructed only from a CPA secure one. We also discuss the consequences of our results regarding security with parallel decryption queries and give several observations.

本論文は、「 SecurityNotions and Generic Constructions of Chosen Ciphertext SecurePubIic Key Encryption Schemes(選択暗号文攻撃に対して安全な公開鍵暗号の安全性定義と一般的構成法)」と題し、汎用的に用いられる場合は必須とされる選択暗号文攻撃に対する安全性(CCA安全性)を持つ公開鍵暗号方式の一般的構成法として、実用的な効率を持つ具体的方式につながる構成法を提案し、さらに、CCA安全な公開鍵暗号が存在するための必要十分条件に関して深く詳細に論じる新たな理論体系を示している。論文の構成は、「Introduction」と「Basic Definitions」を含め5章からなる。

第1章は「Introduction(序論)」で、本研究の背景と動機を述べ、成果の概要をまとめている。特に、CCA安全性の重要性と、CCA安全性を持つ公開鍵暗号方式を他の要素技術の組み合わせで構成する一般的構成法に関する重要な2つの未解決問題について、述べている。1つは実用的な具体的方式につながる一般的構成法は可能かという問題であり、もう1つは、公開鍵暗号として最低限の安全性である選択平文攻撃に対する安全性(CPA安全性)しか持たない方式のみを用いてCCA安全な公開鍵暗号方式を構成できるかという問題である。本章では、暗号理論におけるこれらの未解決問題の重要性から、本研究を行う意義を明らかにしている。

第2章は「Basic Definitions(基本的な定義)」と題し、暗号技術一般の証明可能安全性について、次章以降で用いられる各要素技術の機能的要件と安全性要件を厳密に記述している。

第3章は「Practical Constructions:IBE-to-PKE Transformations(実用的な構成法:IBE-to-PKE変換)」と題し、CCA安全性と実用的な効率を持つ具体的な公開鍵暗号方式をもたらサー般的構成法を目指し、IBE-to-PKE変換と呼ばれるタイプの一般的な構成法を二種提案している。IDベース暗号(IBE)とは、公開鍵暗号のうちで任意の文字列を公開鍵とできる特殊なクラスであり、IBE-to-PKE変換とは、CPA安全性しか持たないIBEをCCA安全な公開鍵暗号へ変換する手法である。第一の提案では、CPA安全性よりもやや強い安全性である頑強性をIBEに要求することで、IBE以外の要素技術として、最も基礎的な要素技術である一方向関数のみしか使用しない非常に簡素な変換を実現している。第二の提案では、Encapsulationと呼ぱれる特殊なコミットメント方式の効率的な構成法を示し、それを用いて従来のIBE-to-PKE変換を効率化できることを示している。両提案手法では、IBEとして実用的な効率を持つ方式を用いれば変換後の公開鍵暗号も実用的な効率を持つという点で、従来のIBE-to-PKE変換が抱えていた非効率性の課題を克服している。

第4章は「Towards CCA Security from CPA Security(CPA安全性からCCA安全性へ向けて)」と題し、CPA安全な公開鍵暗号のみを用いてCCA安全な公開鍵暗号を構成できるかという、暗号理論における極めて重要な未解決問題に取り組んでいる。本章では最初に、既存研究よりも深く詳細に構成可能性及び構成不可能性を議論するためにはCPA安全性とCCA安全性の間に位置する安全性を定義するのが有効であることを指摘し、「Mixed CCA安全性」を新たに定義している。この安全性は、単一型と並行型の復号クエリを事前に決められた順序で行う攻撃者に対する安全性であって、攻撃者に許される行為を詳細かつ厳密に捉えるという暗号理論の真髄を高いレベルで追究した成果であり、理論体系の基盤となる。実際、本章では、Mixed CCA安全性において表現できる安全性定義間の包含や隔離の関係を完全に解明する定理の導出に成功している。さらに、従来の構成法が達成した安全性よりも真に強い安全性、及び、従来の構成では達成されていない種類の安全性を持つ公開鍵暗号の、CPA安全な公開鍵暗号のみを用いた構成法を示している。本章の最後では、さらなる理論的発展をもたらすための示唆として、MixedCCA安全性に関する未解決問題についても議論している。

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

以上これを要するに、本論文は、CCA安全性を持つ公開鍵暗号の一般的構成法に関して、実用的な具体的方式につながる構成法や、CPA安全な方式のみから構成することの可能性及び不可能性を論じるための理論基盤を、厳密な証明可能安全性の枠組みで体系的に示した論文であり、電子情報学、特に情報セキュリティ工学上貢献するところが大きい。

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