Multi-signatures in the plain public-Key model and a general forking lemma

ABSTRACT

A multi-signature scheme enables a group of signers to produce a compact, joint signature on a common document, and has many potential uses. However, existing schemes impose key setup or PKI requirements that make them impractical, such as requiring a dedicated, distributed key generation protocol amongst potential signers, or assuming strong, concurrent zero-knowledge proofs of knowledge of secret keys done to the CA at key registration. These requirements limit the use of the schemes. We provide a new scheme that is proven secure in the plain public-key model, meaning requires nothing more than that each signer has a (certified) public key. Furthermore, the important simplification in key management achieved is not at the cost of efficiency or assurance: our scheme matches or surpasses known ones in terms of signing time, verification time and signature size, and is proven secure in the random-oracle model under a standard (not bilinear map related) assumption. The proof is based on a simplified and general Forking Lemma that may be of independent interest.

REFERENCES

• 1: Michel Abdalla , Jee Hea An , Mihir Bellare , Chanathip Namprempre, From Identification to Signatures via the Fiat-Shamir Transform: Minimizing Assumptions for Security and Forward-Security, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.418-433, May 02, 2002
• 2: Michel Abdalla , Leonid Reyzin, A New Forward-Secure Digital Signature Scheme, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.116-129, December 03-07, 2000
• 3: C. Adams, S. Farrell, T. Kause, and T. Monen. Internet X.509 Public Key Infrastructure Certificate Management Protocol (CMP). Internet Engineering Task Force RFC 4210, 2005.
• 4: Kenneth Barr , Krste Asanović, Energy aware lossless data compression, Proceedings of the 1st international conference on Mobile systems, applications and services, p.231-244, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066123]
• 5: Mihir Bellare , Oded Goldreich, On Defining Proofs of Knowledge, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.390-420, August 16-20, 1992
• 6: M. Bellare, C. Namprempre, and G. Neven. Unrestricted aggregate signatures. Cryptology ePrint Archive, Report 2006/285, 2006.
• 7: M. Bellare and G. Neven. New multi-signatures and a general forking lemma. Full version of this paper, available from http://www.cs.ucsd.edu/users/mihir, 2006.
• 8: Mihir Bellare , Adriana Palacio, GQ and Schnorr Identification Schemes: Proofs of Security against Impersonation under Active and Concurrent Attacks, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.162-177, August 18-22, 2002
• 9: M. Bellare, T. Ristenpart, and S. Yilek. Work in progress, 2006.
• 10: 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]
• 11: Alexandra Boldyreva, Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.31-46, January 06-08, 2003
• 12: D. Boneh, C. Gentry, B. Lynn, and H. Shacham. Aggregate and verifiably encrypted signatures from bilinear maps. EUROCRYPT 2003, LNCS 2656, Springer-Verlag.
• 13: Dan Boneh , Ben Lynn , Hovav Shacham, Short Signatures from the Weil Pairing, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.514-532, December 09-13, 2001
• 14: A. De Santis and G. Persiano. Zero-knowledge proofs of knowledge without interaction. FOCS 1992, {IEEE Computer Society Press.
• 15: 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]
• 16: A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. CRYPTO 1986, LNCS 263, Springer-Verlag.
• 17: M. Fischlin. Communication-efficient non-interactive proofs of knowledge with online extractors. CRYPTO 2005, LNCS 3621, Springer-Verlag.
• 18: S. D. Galbraith, K. G. Paterson, and N. P. Smart. Pairings for cryptographers. Cryptology ePrint Archive, Report 2006/165, 2006.
• 19: Louis C. Guillou , Jean-Jacques Quisquater, A "Paradoxical" Indentity-Based Signature Scheme Resulting from Zero-Knowledge, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.216-231, August 21-25, 1988
• 20: L. Harn. Group-oriented (t,n) threshold digital signature scheme and digital multisignature. IEE Proceedings -- Computers and Digital Techniques, 141(5):307--313, 1994.
• 21: R. Hayashi, T. Okamoto, and K. Tanaka. An RSA family of trap-door permutations with a common domain and its applications. PKC 2004, LNCS 2947, Springer-Verlag.
• 22: J. Herranz and G. Sáez. Forking lemmas for ring signature schemes. INDOCRYPT 2003, LNCS 2947, Springer-Verlag.
• 23: Florian Hess, Efficient Identity Based Signature Schemes Based on Pairings, Revised Papers from the 9th Annual International Workshop on Selected Areas in Cryptography, p.310-324, August 15-16, 2002
• 24: P. Horster, M. Michels, and H. Petersen. Meta-multisignatures schemes based on the discrete logarithm problem. IFIP/SEC 1995. Chapman & Hall.
• 25: K. Itakura and K. Nakamura. A public-key cryptosystem suitable for digital multisignatures. NEC Research & Development, 71:1--8, 1983.
• 26: Jonathan Katz , Nan Wang, Efficiency improvements for signature schemes with tight security reductions, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948132]
• 27: 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
• 28: C.-M. Li, T. Hwang, and N.-Y. Lee. Threshold-multisignature schemes where suspected forgery implies traceability of adversarial shareholders. EUROCRYPT 1994, LNCS 950, Springer-Verlag.
• 29: S. Lu, R. Ostrovsky, A. Sahai, H. Shacham, and B. Waters. Sequential aggregate signatures and multisignatures without random oracles. EUROCRYPT 2006, LNCS 4004, Springer-Verlag.
• 30: A. Lysyanskaya, S. Micali, L. Reyzin, and H. Shacham. Sequential aggregate signatures from trapdoor permutations. EUROCRYPT 2004, LNCS 3027, Springer-Verlag.
• 31: Silvio Micali , Kazuo Ohta , Leonid Reyzin, Accountable-subgroup multisignatures: extended abstract, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502017]
• 32: 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
• 33: Kazuo Ohta , Tatsuaki Okamoto, A Modification of the Fiat-Shamir Scheme, Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, p.232-243, August 21-25, 1988
• 34: 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
• 35: K. Ohta and T. Okamoto. Multi-signature schemes secure against active insider attacks. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences, E82-A(1):21--31, 1999.
• 36: Tatsuaki Okamoto, Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.31-53, August 16-20, 1992
• 37: H. Ong , C. P. Schnorr, Fast signature generation with a Fiat Shamir—like scheme, Proceedings of the workshop on the theory and application of cryptographic techniques on Advances in cryptology, p.432-440, February 1991, Aarhus, Denmark
• 38: PKCS #10: Certification request syntax standard. RSA Data Security, Inc., 2000.
• 39: Ernest F. Brickell , David Pointcheval , Serge Vaudenay , Moti Yung, Design Validations for Discrete Logarithm Based Signature Schemes, Proceedings of the Third International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.276-292, January 18-20, 2000
• 40: D. Pointcheval and J. Stern. Security arguments for digital signatures and blind signatures. Journal of Cryptology, 13(3):361--396, 2000.
• 41: J. Schaad.Internet X.509 Public Key Infrastructure Certificate Request Message Format, Internet Engineering Task Force RFC 4211, 2005.
• 42: C.-P. Schnorr. Efficient signature generation by smart cards. Journal of Cryptology, 4(3):161--174, 1991.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

General Terms:
Security

Keywords:
cryptography, digital signatures, forking lemma, multi-signatures