(本文)Public-key encryption is playing a crucial role in modern cryptography and information security, for the confidentiality of the secrecy and privacy. This dissertation considers the efficient design and provable security of public-key encryptions. We present new algorithms and motivating applications, with rigorous proofs based on well-known cryptographic assumptions. All schemes we presented are efficient and practical.

　In particular, our approach is focusing on the following areas.

1). Generic conversions for public-key encryptions: The confidentiality of public-key encryptions is required to satisfy the strongest security, however, most of current public-key encryptions are only fulfilling with relatively weak security. Although there were some generic conversions had been proposed for enhancing the security of the original public-key encryptions including some distinguished schemes, unfortunately, there does not exist such a scheme that could generically transform many public-key encryption schemes to the strongest security, with the theoretically minimal overhead. Optimal Asymmetric Encryption Padding (OAEP), as its name, was considered to be able to transform a specific public-key encryption to the strongest security with optimal message overhead, but finally found to have a flaw if without additional overhead. Thus, it loses the optimal result. We present here a generic conversion which is the first one to achieve the optimal message overhead while keeping the strongest security. It bases on a well-known cryptographic assumption, and its proof has a tight reduction cost compared to the previous schemes, which usually implies a better performance under the same security level.

On the other hand, a number of public-key encryptions currently used are subject to quantum algorithms if quantum computer could be built. Concerning that long-term security, it is essential to take account of post-quantum public-key encryptions as soon as possible. Among many candidates, a kind of promising public-key encryptions has recently been broken by a decryption error based attack. We present here a generic and efficient solution to thwart the underlying attack, so that the public-key encryption with decryption errors may still immune to the quantum algorithm based attack.

2). Efficient hybrid encryption: Since we have achieved the optimal result when solely public-key encryption scheme is used, we also intend to construct efficient schemes in other cases. One of the most important applications of public-key encryptions, is to transfer session key for the symmetric encryption to encrypt the lengthy data in a fast way. A combination of public-key encryptions and symmetric-key encryptions works in tandem, which is called hybrid encryption. We show that in hybrid encryption scenario, the efficiency could be further enhanced while keeping the security as the same. We present two schemes in hybrid public-key encryption setting, which are based on a recently presented advantageous framework in a number of aspects. One of the schemes is quite simple and nearly optimal since only one cryptographic hash function and one key derivation function are needed in addition to the original public-key encryption. Astonishingly, a distinguished scheme proposed more than 10 years ago could be actually taken as a special case of our very efficient scheme. Therefore, our result can be considered as a generalization solution, and several significant public-key encryptions are possibly adapted to our new scheme in order to guarantee the strongest security. The scheme is secure as long as a well-known mathematical assumption holds, and the security proof is built in the so-called "random oracle" model.

Although the random oracle model is a powerful tool widely use in the design and analysis of cryptography, sometimes it is not desired to assume such an ideal cryptographic hash function in practice. The other scheme we presented here, has achieved the best security in the standard model (i.e. without requiring the random oracles). We take advantage of identity-based encryption to construct a hybrid public-key encryption in the strongest sense. The resulting scheme is a lot more efficient than the previous one both in computation and communication cost.

More interestingly, the second scheme is naturally functional in the threshold cryptography, which has numerous applications in E-commerce and E-voting. Basing on our new scheme, we also present a threshold hybrid encryption and an identity-based threshold hybrid encryption in the standard model, with pretty good efficiency. The technique we used may have an independent meaning in cryptography.

3). Lightweight public-key encryptions: Public-key encryptions have plenty of applications in theory and in practice. We are motivated by the security requirement in wireless environment, where the problem is hard to tackle because of the restricted computation and communication sources. Although it is difficult to achieve a full-fledged public-key encryption in the best security level, we point out that some lightweight solutions are still available. We present two secure authentication protocols by using a partial public-key encryption, and prove the protocols are effective and efficient. Summarizing another work where we find successful attacks against a distinguished lightweight authentication based on a similar assumption, we conclude that our protocols are very promising for protecting wireless security in practice.

Finally, this dissertation summarizes the methodology of design and analysis of public-key encryptions. We wish that it will contribute to the research of cryptography and information security, for protecting the information technology as well as personal secrecy and privacy.

本論文は、「Efficient Constructions and Provable Security of Public-Key Encryptions(公開鍵暗号の効率的構成法および証明可能安全性に関する研究)」と題し、情報通信の強秘匿性や個人情報の保護などを達成するために用いられる暗号技術について、安全性の不十分な公開鍵暗号を十分に高い安全性を備えた方式へ効率的に変換する方式の提案と、公開鍵暗号と共通鍵暗号を組み合わせてより強力な暗号を構成するハイブリッド暗号の提案、及びNP問題に基づく暗号方式の解読と実験、改良を行っている。論文の構成は「Introduction(序論)」を含め6章からなる。

第1章は「Introduction(序論)」で、本研究の背景を明らかにした上で、現代暗号と情報セキュリティにおける公開鍵暗号の重大な意義を述べ、研究の位置づけについて整理している。

第2章は「Security Definitions(安全性定義)」と題し、本論文に必要である暗号学的安全性の諸概念を導入して明確な定義を示し、提案方式に用いられるプリミティブなど準備知識を説明している。特に、安全性が不十分である一方向性や、最強の安全性と言われる強秘匿性に関して、受動攻撃や能動攻撃のもとでのそれぞれの安全性を詳しく分析している。

第3章は「Efficient and Generic Conversions for Public-Key Encryptions(公開鍵暗号用の効率的かつ汎用的な変換方式)」と題し、受動攻撃にしか耐性を持たない公開鍵暗号方式から、能動攻撃に対しても強秘匿性を持ついわば「最も安全な」方式への変換法の具体的構成法を二つ提案している。公開鍵暗号において最強の安全性を満たすためには、元の暗号にランダムなパディング方式を組み合わせるのが有効な手法である。しかし実際には、理想的なランダムネスを利用するのは困難である。例えば、NISTにより標準化されるなど高く評価されている最も有名なOAEP(最適化非対称暗号パディング)方式ですら、標準化当時に「最適」と強調したことが誤りである。すなわち、強力な攻撃を受けると、多数の冗長ビットが加えられない限り、安全性が損なわれる。また、冗長ビットの助けを受けたその安全性も、RSA暗号を用いた時には保証されるが、それ以外の場合はほとんど保証されない。本章の新たな提案1においては、これらの問題を解決すると共に、ランダムネスの最適な汎用パディング方式を初めて提示している。さらに、この方式が理論的な限界を達成したことを証明し、結果として、最適な通信オーバーヘッドで暗号化することが一般的に可能であることを示している。また、提案方式2の変換方式では、量子アルゴリズムによる攻撃に耐える上で有望な公開鍵暗号にランダムなパディングの手法を用いて、特殊な復号攻撃に対する耐性を与えることに成功している。この結果は、将来のポスト量子公開鍵暗号として重大な意味を持つ。

第4章は「Efficient Hybrid Encryption(効率的なハイブリッド暗号)」と題し、公開鍵暗号と共通鍵暗号を組み合わせて効率を向上させる技法について、既存のフレームワークを分析し、新たなハイブリッド暗号方式を提案している。本章では、最近提案されたハイブリッド暗号のひとつの概念であるTag-KEMフレームワークに基づいて、最も効率のよいTag-KEMを提案したものである。広く知られているBellare-Rogaway方式が今回の提案の特殊な場合となっていることも示している。また、より弱い仮定の下で、IDベース暗号を用いて、効率的なハイブリッド暗号とそのしきい値暗号の拡張を行っている。弱い仮定に基づく安全性証明も示されており、暗号理論の分野において大きなインパクトを持っている。

第5章は「Use of Public-Key Encryptions in Lightweight Cryptography(公開鍵暗号の軽量暗号への応用)」と題し、リソースが制限され軽量化が求められる環境において効率的に公開鍵暗号を応用する技術について、プロトコルの安全性分析と現実的で実行可能な改良方式の提案を行っている。具体的には、広く知られているHopper-Blum暗号プロトコルを解読する最も強力なアルゴリズムを提案し、包括的な解読攻撃実験を行い、その解読確率を見積もっている。また、リソースの制限された環境において、公開鍵暗号の手法を用いて実用的なプロトコルを提案し、しかも厳密な安全性証明を与えている。

最後に第6章は「Conclusion(結言)」で、本研究の総括を行い、併せて当該分野の将来展望について述べている。

以上これを要するに、本論文は、安全な公開鍵暗号の設計に必要な暗号強度評価のための安全性概念定義と変換方式などに関する証明を整備し、既存の暗号にはない実用上有意義な特徴をもつ安全かつ効率的な暗号の設計と、具体的な応用方式の構成を体系的に行ったものであり、電子情報学、特に情報セキュリティ工学上貢献するところが少なくない。

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