Accountable-subgroup multisignatures: extended abstract

ABSTRACT

Formal models and security proofs are especially important for multisignatures: in contrast to threshold signatures, no precise definitions were ever provided for such schemes, and some proposals were subsequently broken.In this paper, we formalize and implement a variant of multi-signature schemes, Accountable-Subgroup Multisignatures (ASM). In essence, ASM schemes enable any subgroup, S, of a given group, G, of potential signers, to sign efficiently a message M so that the signature provably reveals the identities of the signers in S to any verifier.Specifically, we provide:

1. The first formal model of security for multisignature schemes that explicitly includes key generation (without relying on trusted third parties);
2. A protocol, based on Schnorr's signature scheme [33], that is both provable and efficient:
   • Only three rounds of communication are required per signature.
   • The signing time per signer is the same as for the single-signer Schnorr scheme, regardless of the number of signers.
   • The verification time is only slightly greater than that for the single-signer Schnorr scheme.
   • The signature length is the same as for the single signer Schnorr scheme, regardless of the number of signers.

Our proof of security relies on random oracles and the hardness of the Discrete Log Problem.

REFERENCES

• 1: Proceedin s of the Twentieth Annual ACM Symposium on Theory of Computing ,Chicago,Illinois,2 -4 May 1988.
• 2: Eric Bach, How to generate factored random numbers, SIAM Journal on Computing, v.17 n.2, p.179-193, April 1988 [doi>10.1137/0217012]
• 3: Mihir Bellare , Phillip Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the 1st ACM conference on Computer and communications security, p.62-73, November 03-05, 1993, Fairfax, Virginia, United States [doi>10.1145/168588.168596]
• 4: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 5: Proceedings on Advances in cryptology, July 1989
• 6: Jan Camenisch , Markus Stadler, Efficient Group Signature Schemes for Large Groups (Extended Abstract), Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.410-424, August 17-21, 1997
• 7: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• 8: D.Chaum and E.van Heyst.Group signatures.In
• 9: D.W.Davies,editor.Advances in Cryptology -EUROCRYPT 91 ,volume 547 of Lecture Notes in Computer Science .Springer-Verlag, 8 -11 Apr.1991.
• 10: Yvo G. Desmedt , Yair Frankel, Threshold cryptosystems, Proceedings on Advances in cryptology, p.307-315, July 1989, Santa Barbara, California, United States
• 11: U. Feige , A. Fiat , A. Shamir, Zero-knowledge proofs of identity, Journal of Cryptology, v.1 n.2, p.77-94, Aug. 1988 [doi>10.1007/BF02351717]
• 12: Amos Fiat , Adi Shamir, How to prove yourself: practical solutions to identification and signature problems, Proceedings on Advances in cryptology---CRYPTO '86, p.186-194, January 1987, Santa Barbara, California, United States
• 13: Rosario Gennaro , Stanislaw Jarecki , Hugo Krawczyk , Tal Rabin, Robust and Efficient Sharing of RSA Functions, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.157-172, August 18-22, 1996
• 14: R.Gennaro,S.Jarecki,H.Krawczyk,and T.Rabin. Robust threshold DSS signatures.In {23 },pp.354 -371.
• 15: R.Gennaro,S.Jarecki,H.Krawczyk,and T.Rabin. Secure distributed key generation for discrete-log based cryptosystems.In J.Stern,editor,Advances in Cryptology -EUROCRYPT '99 ,volume 1592 of Lecture Notes in Computer Science ,pages 295 -310. Springer-Verlag,2 -6 May 1999.
• 16: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 17: L.Harn.Group-oriented (t,n )threshold digital signature scheme and digital multisignature.IEE Proc.-Comput.Digit.Tech.,141(5),Sept.1994.
• 18: P.Horster,M.Michels,and H.Petersen. Meta-multisignatures schemes based on the discrete logarithm problem.In Information Security:The Next Decade.Proceedin s of the IFIP TC11 Eleventh International Conference on Information Security, IFIP/Sec '95 ,pages 128 -141.Chapman &Hall,1995.
• 19: K.Itakura and K.Nakamura.Apublic-key cryptosystem suitable for digital multisignatures.NEC Research &Development ,(71):1 -8,Oct.1983.
• 20: Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, August 1996
• 21: Susan K. Langford, Weakness in Some Threshold Cryptosystems, Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, p.74-82, August 18-22, 1996
• 22: C.-M.Li,T.Hwang,and N.-Y.Lee. Threshold-multisignature schemes where suspected forgery mplies traceability of adversarial shareholders. In A.De Santis,editor,Advances in Cryptology -EUROCRYPT 94 ,volume 950 of Lecture Notes in Computer Science ,pages 194 -204. Springer-Verlag,1995,9 -12 May 1994.
• 23: U.Maurer,editor.Advances in Cryptology -EUROCRYPT 96 ,volume 1070 of Lecture Notes in Computer Science .Springer-Verlag, 12 -16 May 1996.
• 24: Ralph C. Merkle, A certified digital signature, Proceedings on Advances in cryptology, p.218-238, July 1989, Santa Barbara, California, United States
• 25: Silvio Micali, Computationally Sound Proofs, SIAM Journal on Computing, v.30 n.4, p.1253-1298, 2000 [doi>10.1137/S0097539795284959]
• 26: Markus Michels , Patrick Horster, On the Risk of Disruption in Several Multiparty Signature Schemes, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.334-345, November 03-07, 1996
• 27: Kazuo Ohta , Tatsuaki Okamoto, A Digital Multisignature Scheme Based on the Fiat-Shamir Scheme, Proceedings of the International Conference on the Theory and Applications of Cryptology: Advances in Cryptology, p.139-148, November 11-14, 1991
• 28: Kazuo Ohta , Tatsuaki Okamoto, On Concrete Security Treatment of Signatures Derived from Identification, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.354-369, August 23-27, 1998
• 29: K.Ohta and T.Okamoto.Multi-signature schemes secure against active nsider attacks.IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences , E82-A(1):21 -31,Jan.1999.
• 30: Tatsuaki Okamoto, A digital multisignature scheme using bijective public-key cryptosystems, ACM Transactions on Computer Systems (TOCS), v.6 n.4, p.432-441, Nov. 1988 [doi>10.1145/48012.48246]
• 31: T.P.Pedersen.Athreshold cryptosystem without a trusted party (extended abstract).In Davies {9 },pages 522 -526.
• 32: D.Pointcheval and J.Stern.Security proofs for signature schemes.In Maurer {23 },pages 387 -398.
• 33: C.-P.Schnorr.E .cient signature generation by smart cards.Journal of Cryptology ,4(3):161-174,1991.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Authentication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce

General Terms:
Algorithms, Design, Security, Theory

Keywords:
digital signature, multisignature