In the research field of cryptography, in order to claim the security of the proposed scheme, security proofs are essentially important. However, owing to complications on evolutions of new protocols security proofs of these protocols have been difficult. So, the aim of this dissertation is to give rigorous security proofs in several public key cryptographic schemes and to propose new security methodology by using reduction technique and meta-reduction technique. In order to establish the framework in which correct security proofs are given against powerful adversaries, we make research two different stages.

Aiming at rigorous security analysis for complex cryptographic scheme, we give several security analyses for anonymous authentication and extended encryption. Specifically, we focus on secret handshake scheme and proxy re-encryption scheme.

First, we show the flaw of "secret handshake scheme with multiple groups (SHSMG)". Secret handshake scheme allows members of the same group to authenticate each other secretly, that is, two members who belong to the same group can learn their counterparts in the same group, while non-member of the group cannot determine whether the counterpart is a member of the group or not. Yamashita and Tanaka extended a single group setting to a multiple groups setting where two members output accept iff both member's affiliations of the multiple groups are identical. First, we show the attack to their scheme in the meaning of detector resistance. Second, we introduce a new concept of secret handshake scheme "monotone condition secret handshake with multiple groups" in order to extend the condition of accept.

Second, we discuss the anonymity for secret handshake schemes. When a more strict anonymity is required even for a group authority (GA), previous anonymity is unfavorable in some situations. Since the above previous anonymities are extreme, the previous secret handshake schemes are not applicable to several systems. So, we propose several new anonymity requirements. Additionally, we propose a secret handshake scheme which satisfies our proposed anonymity requirements using group signature with message recovery technique.

Next, we present the first generic construction of chosen-ciphertext (CCA) secure uni-directional proxy re-encryption (PRE) scheme. PRE is an interesting extension to traditional public key encryption (PKE). In addition to the normal operations of a PKE, with a dedicated re-encryption key (generated by a receiver A), a proxy can turn a class of ciphertexts to user A into those to another user B. A remarkable property of PRE is that the proxy, who can do the transform, is totally ignorant of the plaintext. In particular, full CCA security of our proposed scheme is proven even against powerful adversaries which are given a more advantageous attack environment than in all previous works, and furthermore, it does not require random oracles. For achieving such strong security, we establish a totally novel methodology for designing PRE which is based on a specific class of threshold encryption. Via our generic construction, we present first construction which is CCA secure in the standard model.

Aiming at easy security proof methodology, we present new technique that we can check whether a security proof of a scheme (in this thesis, a public key encryption and a digital signature) is possible or not. Specifically, we proposed new impossibility proof technique (so-called meta-reduction technique) and analysis for public key encryption and digital signature schemes.

First, we introduce new meta-reduction technique in order to show several impossibility results. We use the proposed concepts to rigorously classify the impossibility range for general cases. Finally, we show the application to security analysis using new meta-reduction technique for a specific digital signature scheme. We introduce Variant Rabin signature scheme and classify its security into secure/insecure/no-information ranges using newly developed techniques.

Second, we discuss the strong attack model security for PKE and digital signature. The main motivation of this chapter is to find an essential mechanism of secure schemes under strong attack model. So, we prove several impossibility results by using the meta-reduction. We classify two types of PKE: First model is (Gen, Enc, Dec) which we call the setup-free model, Second model is (Setup, Gen, Enc, Dec) which we call the setup model. We prove that it is impossible to reduce indistinguishability under strong chosen ciphertext attack (IND-SCCA) security to any other weaker security notion under black-box analysis in the standard model. Second, when a PKE is a setup model, we show that it is impossible that the security of SCCA is proven if the reduction is setup-preserving black-box reductions. Finally, we discuss the essential mechanism to construct IND-SCCA secure public key encryption scheme in the standard model.

Finally, we discuss security of public-key cryptographic primitives in the case that the public key is fixed. In the standard argument, security of cryptographic primitives is evaluated by estimating the average probability of being successfully attacked where keys are treated as random variables. In contrast to this, in practice, a user is mostly interested in the security under his specific public key which has been already fixed. However, it is obvious that such security cannot be mathematically guaranteed due to the fact that for any given public key, there always potentially exists an adversary which breaks its security. Therefore, the best what we can do is just to use a public key such that its effective adversary is not likely to be constructed in the real life, and thus, it is desired to provide a method for evaluating this possibility. The motivation of this work is to investigate (in)feasibility of predicting whether for a given fixed public key, its successful adversary will actually appear in the real life or not. As our main result, we prove that for any digital signature scheme or public key encryption scheme, it is impossible to reduce any fixed key adversary in any weaker security notion than the de facto ones to fixed key adversaries in the de facto security notion in a black-box manner.

本博士論文は大きく3部9章からなり,第一部は研究の位置づけについて,第二部は様々な拡張された公開鍵暗号技術の安全性の定式化,およびその安全性を達成する具体的方式の設計,第三部は公開鍵暗号とデジタル署名方式における証明不可能性について述べられている. 本研究の目的は様々な公開鍵暗号技術における安全性証明をより厳密なものにすることにある.1976年にDiffieらによって公開鍵暗号の概念が提唱されて以来,公開鍵暗号やデジタル署名をはじめとする公開鍵暗号技術が提案されており,新しい暗号技術の提案には,その安全性を数学的に証明することが必要不可欠である.暗号方式の安全性証明には帰着技法が広く使われている.これは,暗号方式Sに対する攻撃者Aが存在したと仮定すると,計算量的に困難とされているある特定の問題P が計算可能となってしまうことを示す証明手法である.この場合,問題Pが計算困難であることから攻撃者A の存在は否定され,方式Sの安全性が証明される.帰着技法で証明された方式の安全性レベルは,(a) 攻撃者A の攻撃の種類と程度,(b) 問題Pの困難さ,(c) 証明を行った際のモデル,の3点から考察される.(a) はより強い攻撃者に対し安全性が証明できたほうが望ましく,(b) については,より解読が難しいとされている問題を安全性の根拠に置くほうが望ましい.また(c)は,安全性証明を行う際に現実の環境に近い状況を想定したほうが望ましい.しかし,提案されている方式のほとんどは,証明を容易にする目的や,設計者が証明を構成できないなどの理由から,この条件を満たしているとは言えない.また,証明する安全性が高くなればなるほど,また対象とする方式が高機能化すればするほど証明は複雑になっていく.また高機能な方式は安全性の定義自体に改良の余地がある場合も多い.本論文は上記の問題に対し二方面から研究を行った.第二部においては,様々な拡張された公開鍵暗号技術の安全性の定式化は非常に重要な研究であると考え,安全性定義の定式化とその実現方式を示した.具体的には匿名認証方式の一つであるSecret Handshake(三,四章)と公開鍵暗号の拡張である代理再暗号化(五章)に対して研究を行った.Secret Handshakeとは,グループに所属しているユーザ同士が認証を行い,互いに自らのグループを明かすことなく相手と同じグループに所属しているかを認証する方式である.これに対して,(1)ユーザが複数のグループに所属しているケースを対象とした既存研究の安全性証明の誤りを指摘し,その修正を行った.(2)通常のSecret Handshakeはグループに対する匿名性のみを扱うのに対し,ユーザIDの匿名性を考慮した新たな匿名性を定式化し,それを満たす方式を提案した.代理再暗号化とは,暗号文受信者が復号鍵を渡すことなく他のユーザに暗号文の復号する権利を譲渡することが可能な方式である.これに対して,強い攻撃方法である選択暗号文攻撃に対して安全な方式をどのように設計すればよいかを分析し,閾値暗号の特性を利用できることを発見した.そして既存研究よりも高い安全性を証明可能な方式を設計した.第三部においては,既存の証明不可能性技法を拡張しいくつかの結果を得た.安全性の定式化や安全性の根拠となる数論仮定によっては安全性証明が不可能である事がある.もし証明不可能であることを示すことができたならば,証明可能な方式設計に有益な情報となる.そこで,メタ帰着技法という証明不可能性技法に着目しその拡張と様々な方式への適用を行った.具体的には,(1)素因数分解問題に基づく方式において,合成数のみを公開鍵とするケースではあるレベル以上の安全性が証明できないこと,離散対数問題に基づく方式において,離散対数問題のみならずDiffie-Hellman型の数論仮定を用いて安全性証明を行う場合,ある証明方針では証明不可能であること(六章),(2)全てのユーザが全く異なる公開鍵を所持する公開鍵暗号方式は,非常に強い選択暗号文攻撃に対して安全性は証明できないこと,また安全な方式を設計するためには,一部同じパラメータを全てのユーザに共有させる必要があること(七章)を示した.

本論文第三章は,丹野 翔太郎,近藤 崇裕,米山一樹,太田和夫,國廣昇との共同研究,第四章は米山一樹,太田和夫,國廣昇との共同研究,第五章は,花岡悟一郎, 國廣昇, 松田隆宏,翁健, 張鋭, 趙運磊との共同研究,第六章は太田和夫との共同研究,第七章は,坂井祐介,太田和夫,國廣昇との共同研究,第八章は花岡悟一郎,太田和夫,國廣昇との共同研究であるが,論文提出者が主体となり貢献を行っており,論文提出者の寄与が十分であると判断する.

したがって,博士(科学)の学位を授与できると認める.