Modular Design of Secure yet Practical Cryptographic Protocols

Modular Design of Secure yet Practical Cryptographic Protocols ......Page 1
Acknowledgements ......Page 3
ToC ......Page 5
1.1 History ......Page 8
1.2 Research Goals ......Page 16
1.3 Overview ......Page 21
2.1 Model and Definitions ......Page 26
2.2.2 Special Soundness and Collision Intractability ......Page 29
2.2.3 Zero-Knowledge ......Page 31
2.2.4 Witness Hiding and Witness Indistinguishability ......Page 32
2.2.5 Proofs of Knowledge ......Page 33
2.2.6 Interactive Proofs ......Page 34
2.2.7 Signature Protocols ......Page 35
2.3.2 Based on Discrete Logarithms ......Page 36
2.3.3 Based on RSA ......Page 38
2.4 Basic Theory of Sigma-protocols ......Page 40
2.4.1 Collision Intractability ......Page 41
2.4.2 Approximating Special Soundness ......Page 44
2.4.3 Simulation Properties ......Page 47
2.4.4 Manipulating the Challenge Length ......Page 48
2.4.5 Trade-offs ......Page 50
2.5 Existence ......Page 53
2.5.1 One-way Group Homomorphisms ......Page 54
2.5.2 Special One-way Group Isomorphisms ......Page 55
2.5.3 Claw-Free Pairs of Trapdoor Permutations ......Page 60
2.5.4 Special Claw-Free Pairs of Trapdoor Permutations ......Page 63
3.1 Introduction ......Page 66
3.2.1 Introduction ......Page 69
3.2.2 Monotone Functions ......Page 70
3.2.3 Secret Sharing ......Page 71
3.2.4 Main Results ......Page 76
3.3.1 Introduction ......Page 84
3.3.2 Bitcommitments and Linear Proofs of Contents ......Page 88
3.3.3 General Approach ......Page 90
3.3.4 Zero Knowledge Interactive Proofs for NP ......Page 94
3.3.5 Interactive Arguments for NP ......Page 95
3.3.6 Existence of Bitcommitment Schemes ......Page 96
3.4.1 Introduction ......Page 102
3.4.2 Notation and Definitions ......Page 104
3.4.3 Overview ......Page 105
3.4.4 The Closure Property for L ......Page 107
3.4.5 The Closure Property for L' ......Page 110
3.5.1 Introduction ......Page 112
3.5.2 Overview of the Approach ......Page 113
3.5.3 Related Work ......Page 114
3.5.4 Cryptographic Primitives ......Page 115
3.5.5 Secret Ballot Election Scheme ......Page 117
3.6.1 Introduction ......Page 121
3.6.3 Main Result ......Page 125
3.6.5 Security Analysis ......Page 126
3.6.7 Applications ......Page 128
4.1 Introduction ......Page 130
4.2 Our Contributions ......Page 133
4.3 Definitions ......Page 135
4.4 Shorter GMR-Signatures ......Page 136
4.4.2 The Goldwasser-Micali-Rivest scheme ......Page 137
4.4.3 The Modification ......Page 139
4.4.4 Preliminaries ......Page 140
4.4.5 Description of the Signature Scheme ......Page 141
4.4.6 Proof of Security ......Page 143
4.4.7 Alternative Descriptions ......Page 146
4.5.1 Introduction ......Page 147
4.5.2 Notation ......Page 148
4.5.3 Overview of Our Method ......Page 149
4.5.4 Linear Signature Protocols ......Page 150
4.5.5 Existence of Linear Signature Protocols ......Page 151
4.5.7 Main Result ......Page 152
4.5.8 Proof of Security ......Page 154
4.5.9 Example ......Page 156
4.6 Security Amplifications for Signatures ......Page 158
4.6.1 The Transformation ......Page 159
4.7 Secure and Practical RSA-based Signatures ......Page 161
4.7.1 Basic Ideas ......Page 162
4.7.2 Description of the Scheme ......Page 163
4.7.4 Performance of the Scheme ......Page 166
4.7.5 Proof of Security ......Page 167
4.7.6 Optimizations ......Page 170
Nederlandse Samenvatting ......Page 172
Curriculum Vitae ......Page 180
Bibliography ......Page 182
Index ......Page 192