Group Siganture Schemes and Payment Systems Based on the Discrete Log Problem Jan Camenisch -------------------------------------------------------------------------------- Contents 1 Introduction 1 2 Foundations and Basic Protocols 5 2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1.1 Complexity Theory . . . . . . . . . . . . . . . . . . . 5 2.1.2 Interactive Protocols . . . . . . . . . . . . . . . . . 7 2.1.3 Miscellaneous Notations . . . . . . . . . . . . . . . 8 2.2 Algebra and Number Theory . . . . . . . . . . . . . . . . 9 2.2.1 Groups . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.2 The Groups Zm and Zm* . . . . . . . . . . . . . . . . 10 2.2.3 Efficiency of Group Operations in Zm . . . . . . . 11 2.3 Number-Theoretic Problems . . . . . . . . . . . . . . . . . 12 2.3.1 The Discrete Logarithm Problem . . . . . . . . . . 12 2.3.2 The Representation Problem . . . . . . . . . . . . 15 2.3.3 The Diffie-Hellman Problem . . . . . . . . . . . . 15 2.3.4 Factoring Large Integers . . . . . . . . . . . . . . . 16 2.3.5 Computing Square-Roots and e-th Roots . . . . . . . 17 2.4 Public Key Cryptography . . . . . . . . . . . . . . . . . . 19 2.5 Public Key Encryption . . . . . . . . . . . . . . . . . . . . 20 2.5.1 Diffie-Hellman Key Exchange . . . . . . . . . . . . 20 2.5.2 The RSA Encryption Scheme . . . . . . . . . . . . 21 2.5.3 The ElGamal Encryption Scheme . . . . . . . . . . 22 2.6 Identification Protocols . . . . . . . . . . . . . . . . . . . 23 2.6.1 The Schnorr Identification Protocol . . . . . . . . . 23 2.7 Digital Signature Schemes . . . . . . . . . . . . . . . . . . 24 2.7.1 The RSA Signature Scheme . . . . . . . . . . . . . 26 2.7.2 The ElGamal Signature Scheme . . . . . . . . . . . 27 2.7.3 The Schnorr Signature Scheme . . . . . . . . . . . 28 2.8 Blind Digital Signature Schemes . . . . . . . . . . . . . . 29 2.8.1 The Blind RSA Signature Scheme . . . . . . . . . . 30 2.8.2 The Blind Schnorr Signature Scheme . . . . . . . . 31 2.9 Zero-Knowledge Proofs of Knowledge . . . . . . . . . . . 33 2.9.1 Interactive Proofs of Knowledge . . . . . . . . . . 34 2.9.2 Zero Knowledge Protocols . . . . . . . . . . . . . 35 2.9.3 Witness Hiding Protocols . . . . . . . . . . . . . . 37 2.9.4 An example: Schnorr's Identification Scheme . . 39 2.10 Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . 42 2.11 Secret Sharing . . . . . . . . . . . . . . . . . . . . . . . . . 44 3 Proofs of Knowledge About Discrete Logarithms 47 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.2 Proving Knowledge of Secret Keys . . . . . . . . . . . . . 49 3.2.1 Algebraic Setting . . . . . . . . . . . . . . . . . . . 49 3.2.2 First Building Blocks and Notation . . . . . . . . . 49 3.3 Statements About Knowledge . . . . . . . . . . . . . . . . 52 3.4 Proving the Equality of Secret Keys . . . . . . . . . . . . . 57 3.5 Proving Polynomial Relations Among Secret Keys . . . . 59 3.5.1 Linear Relations . . . . . . . . . . . . . . . . . . . . 59 3.5.2 Polynomial Relations . . . . . . . . . . . . . . . . . 61 3.5.3 Related Work . . . . . . . . . . . . . . . . . . . . . 69 4 Efficient and Generalized Group Signature Schemes 71 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.1.1 Related Work . . . . . . . . . . . . . . . . . . . . . 72 4.1.2 The Schemes Presented in This Chapter . . . . . . 73 4.2 Our Model of Group Signature Schemes . . . . . . . . . . 74 4.3 Constructions of the Schemes . . . . . . . . . . . . . . . . 76 4.3.1 An Efficient Simple Group Signature Scheme . . . 76 4.3.2 A Generalized Group Signature Scheme . . . . . . 79 4.3.3 An Example: A Threshold Group Signature Scheme 82 4.3.4 Security Properties . . . . . . . . . . . . . . . . . . 83 4.3.5 Efficiency Considerations . . . . . . . . . . . . . . 84 4.4 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.4.1 Sharing the Functionalities of the Group Manager 85 4.4.2 Reducing the Size of the Group's Public Key . . . 86 5 Group Signature Schemes for Large Groups 87 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 87 5.2 The Basic Idea . . . . . . . . . . . . . . . . . . . . . . . . . 88 5.3 Building Blocks . . . . . . . . . . . . . . . . . . . . . . . 90 5.3.1 Double Discrete Logarithms and Roots of Loga- rithms . . . . . . . . . . . . . . . . . . . . . . . . 91 5.3.2 Proofs of Knowledge of Discrete Logarithms and Representations . . . . . . . . . . . . . . . . . . . . 91 5.3.3 Proofs of Knowledge of Double Discrete Loga- rithms . . . . . . . . . . . . . . . . . . . . . . . . 92 5.3.4 Proofs of Knowledge of Roots of Discrete Loga- rithms . . . . . . . . . . . . . . . . . . . . . . . . 96 5.4 The Basic Group Signature Scheme . . . . . . . . . . . . . 99 5.4.1 System Setup . . . . . . . . . . . . . . . . . . . . 100 5.4.2 Generating Membership Keys and Certificates . . 101 5.4.3 Signing Messages . . . . . . . . . . . . . . . . . . . 102 5.4.4 Opening Signatures . . . . . . . . . . . . . . . . . 103 5.4.5 Security Properties . . . . . . . . . . . . . . . . . 104 5.4.6 Efficiency Considerations . . . . . . . . . . . . . . 104 5.5 An Advanced Scheme . . . . . . . . . . . . . . . . . . . . 105 5.5.1 System Setup . . . . . . . . . . . . . . . . . . . . 105 5.5.2 Generating Membership Keys and Certificates . . 106 5.5.3 Signing Messages . . . . . . . . . . . . . . . . . . . 107 5.5.4 Opening Signatures . . . . . . . . . . . . . . . . . 108 5.5.5 Security Properties . . . . . . . . . . . . . . . . . 108 5.5.6 Efficiency Considerations . . . . . . . . . . . . . . 109 5.6 A More Efficient Variant . . . . . . . . . . . . . . . . . . . 109 5.6.1 System Setup . . . . . . . . . . . . . . . . . . . . 111 5.6.2 Generating Membership Keys and Certificates . . 112 5.6.3 Signing Messages . . . . . . . . . . . . . . . . . . . 112 5.6.4 Opening Signatures . . . . . . . . . . . . . . . . . 114 5.6.5 Security Properties . . . . . . . . . . . . . . . . . 114 5.6.6 Efficiency Considerations . . . . . . . . . . . . . . 115 5.7 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.7.1 Sharing the Functionality of the Group Manager . 115 5.7.2 Generalized Group Signature Schemes . . . . . . 116 5.8 Comparison of the Different Group Signature Schemes . 117 5.9 Open Problems . . . . . . . . . . . . . . . . . . . . . . . . 118 6 Payment Systems with Passive Trustees 119 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 120 6.2 Digital Payment Systems . . . . . . . . . . . . . . . . . . . 121 6.3 Anonymity Revocation by a Trustee . . . . . . . . . . . . 122 6.4 Payment System with a Passive Trustee . . . . . . . . . . 124 6.4.1 System Setup . . . . . . . . . . . . . . . . . . . . 124 6.4.2 A Subprotocol: A Modified Blind Schnorr Signa- ture Scheme . . . . . . . . . . . . . . . . . . . . . 125 6.4.3 The Withdrawal Protocol . . . . . . . . . . . . . . 127 6.4.4 The On-line Payment Protocol . . . . . . . . . . . 128 6.4.5 Anonymity Revocation . . . . . . . . . . . . . . . 129 6.4.6 Security Properties . . . . . . . . . . . . . . . . . 130 6.4.7 Efficiency Considerations . . . . . . . . . . . . . . 132 6.5 Extensions to On-line Payments . . . . . . . . . . . . . . . 132 6.5.1 Enabling the Bank to Identify Cheaters . . . . . . 132 6.5.2 Observers Can Prevent Double-spending . . . . . 134 6.5.3 Security properties . . . . . . . . . . . . . . . . . 140 6.6 Sharing the Revocation Capability Among Several Trustees 141 6.7 Comparison with Other Schemes with Passive Trustees . 141 7 Sharing and Diverting the Capability of Anonymity Revoca- tion 143 7.1 Provable Encryption . . . . . . . . . . . . . . . . . . . . . 144 7.2 Sharing the Capability of Anonymity Revocation . . . . . 145 7.2.1 Threshold Access Structures . . . . . . . . . . . . . 146 7.2.2 Using Publicly Verifiable Secret Sharing . . . . . . 146 7.3 Diverting the Capability of Anonymity Revocation . . . . 147 8 Concluding Remarks 149 Bibliography 151 Index 171