Tight security for cryptographic schemes in the multi-instance settings

다국어 초록 (Multilingual Abstract)

This thesis presents tight security results in independent cryptographic
schemes public-key encryption (PKE) and identity-based signature (IBS). The
security of PKE schemes in multi-user settings is aimed at capturing real-world
scenarios in which an adversary could attack multiple users and multiple ciphertexts
of its choice. However, the fact that a real-world adversary can also
mount key-exposure attacks requires us to consider a more realistic notion of
security in multi-user settings. An IBS scheme can be generically constructed
from an ordinary signature scheme. But it was unclear that a generic construction
leads to a tightly secure IBS scheme, no matter what tightly secure
signature scheme be used as a building block.
The summary of tight security results of this thesis is presented as follows:
• This thesis defines the security notion of PKE in a multi-user setting with
corruptions, where an adversary is able to issue corruption (i.e., private key)
queries. Then, this thesis proposes the first practical and tightly secure PKE
scheme in the multi-user setting with corruptions.
• This thesis shows that the recent work by Seo, Abdalla, Lee, and Park
(Information Sciences, July 2019) has a flaw in the security analysis of
CCA conversion methods and presents revised security proofs.
• This thesis demonstrates that the generic construction of IBS can achieve
tightness if the underlying signature scheme is tightly secure in the multiuser
setting with corruption. In addition, this thesis extends the tightness
result of IBS to the multi-instance setting, where an adversary can corrupt
multiple key generation centers and obtain related master secret keys.

목차 (Table of Contents)

• 1 Introduction 1
• 1.1 Motivation 3
• 1.2 Contributions 6
• 1.3 Related Work 10
• 2 Preliminaries 14
• 2.1 Notations 14
• 2.2 Assumptions 15
• 2.2.1 DiffieHellman Assumption 15
• 2.2.2 Twin DiffieHellman Assumption 16
• 2.3 Formal Model of KEM/Signature 16
• 2.3.1 Key Encapsulation Mechanism 16
• 2.3.2 Signature 18
• 2.4 Zero Knowledge Proof System 19
• 2.4.1 Interactive Proof System 19
• 2.4.2 Protocol for Proving the Equality of Discrete Logarithms 21
• 2.4.3 Protocol for Proving the Linearity of Discrete Logarithms 22
• 2.4.4 NIZK in the Random Oracle Model 24
• 2.5 OR-Proof of Equality of Discrete Logarithms 27
• 3 Tightly Secure IND-CCA KEM 29
• 3.1 Formal Model of KEM in the MUC+ 29
• 3.2 Achieving Tight Security in the MUC+ Model 31
• 3.3 Construction 34
• 3.4 Discussion 44
• 4 Tightly Secure IND-CCA PKE 47
• 4.1 Formal Model of PKE in the MUC+ 47
• 4.2 Augmented Data Encapsulation Mechanism 50
• 4.3 Augmented Hybrid Encryption 51
• 5 NIZK-based CCA Conversion 59
• 5.1 Conversion Method for CCA-Secure KEM 60
• 5.1.1 Conversion Method 60
• 5.1.2 Flaws in Security Proof in Previous Research Literature 62
• 5.1.3 Corrected Security Proof 65
• 5.2 Conversion Method for CCA-secure IBKEM 75
• 5.2.1 IBKEM 75
• 5.2.2 Conversion Method 77
• 5.2.3 Corrected Security Proof 79
• 6 Tightly Secure (H)IBS 88
• 6.1 Formal Model of (H)IBS 88
• 6.1.1 Syntax 88
• 6.1.2 Security Model 89
• 6.2 Achieving Tight Security of IBS in the Fully Adaptive Model 92
• 6.3 Generic Construction 94
• 6.3.1 Generic Construction of IBS 94
• 6.3.2 Generic Construction of HIBS 98
• 7 Tightly Secure (H)IBS in the Multi-Instance Setting 104
• 7.1 Formal Model in the Multi-Instance Setting 104
• 7.1.1 Security Model 104
• 7.2 Generic Construction in the Multi-Instance Model 107
• 8 Instantiations 116
• 8.1 Applications of NIZK-based Conversions 116
• 8.1.1 CCA-Secure ElGamal KEM 116
• 8.1.2 CCA-Secure Linear KEM 118
• 8.1.3 CCA-Secure BonehFranklin IBKEM 120
• 8.1.4 CCA-Secure BonehBoyen IBKEM 123
• 8.2 Tightly Secure IBS Schemes 126
• 8.2.1 IBS Scheme 1: Tightly Secure IBS 126
• 8.2.2 IBS Scheme 2: Tightly Secure IBS in the MI Model 128
• 8.2.3 Comparison 130
• 9 Conclusion 134
• Bibliography 136