Abstract
A multisignature scheme allows an ad hoc set of users to sign a message so that the resulting single signature certifies that the users endorsed the message. However, all known multisignatures are either at the price of complexity and additional trust of Certificate Authority (CA), or sacrificing efficiency of computation and communication (including both bandwidth and round). This paper proposes a new multisignature scheme with efficient verification in the plain public key model. Our multisignatures enjoys the most desired features: (1) Our plain public key model-based multisignatures do not impose any impractical key setup or PKI requirements; (2) Our multisignature scheme is non-interactive, which saves computation and communication in signature generation; (3) Through pre-computation, our scheme achieves \(\mathcal{O}(1)\) verification in the plain public key model; (4) Provable tighter security under the standard CDH assumption ensures high level of security in both practice and theory. Hence, our non-interactive multisignatures are of great use in authentication of routes in networks.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Micali, S., Ohta, K., Reyzin, L.: Accountable-Subgroup Multisignatures: Extended Abstract. In: Eighth ACM Conference on Computer and Communications Security, pp. 245–254. ACM Press, New York (2001)
Bellare, M., Neven, G.: Multisignatures in the Plain Public-Key Model and a General Forking Lemma. In: 13th ACM Conference on Computer and Communications Security, pp. 390–399. ACM Press, New York (2006)
Boldyreva, A.: Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 31–46. Springer, Heidelberg (2002)
Kim, J., Tsudik, G.: Srdp: Securing Route Discovery in DSR. In: Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, pp. 247–260. IEEE Press, Los Alamitos (2005)
Bagherzandi, A., Cheon, J., Jarecki, S.: Multisignatures Secure under the Discrete Logarithm Assumption and a Generalized Forking Lemma. In: The 15th ACM Conference on Computer and Communications Security, pp. 449–458. ACM Press, New York (2008)
Bagherzandi, A., Jarecki, S.: Multisignatures Using Proofs of Secret Key Possession, as Secure as the Diffie-Hellman Problem. In: Ostrovsky, R., De Prisco, R., Visconti, I. (eds.) SCN 2008. LNCS, vol. 5229, pp. 218–235. Springer, Heidelberg (2008)
Castelluccia, C., Jarecki, S., Kim, J., Tsudik, G.: Secure Acknowledgment Aggregation and Multisignatures with Limited Robustness. Comput. Netw. 50, 1639–1652 (2006)
Lin, X., Sun, X., Ho, P.H., Shen, X.: Gsis: A Secure and Privacy Preserving Protocol for Vehicular Communications. IEEE Trans. on Vehicular Tech. 56, 3442–3456 (2007)
Lu, R., Lin, X., Zhu, H., Ho, P.H., Shen, X.: Ecpp: Efficient Conditional Privacy Preservation Protocol for Secure Vehicular Communications. In: The 27th Conference on Computer Communications IEEE INFOCOM 2008, pp. 14–18. IEEE Press, Los Alamitos (2008)
Lu, R., Lin, X., Shen, X.: Spring: A social-based Privacy-Preserving Packet Forwarding Protocol for Vehicular Delay Tolerant Networks. In: The 29th Conference on Computer Communications, IEEE INFOCOM 2010, pp. 14–19. IEEE Press, Los Alamitos (2010)
Itakura, K., Nakamura, K.: A Public Key Cryptosystem Suitable for Digital Multisignatures. NEC Research & Development 71, 1–8 (1983)
Ohta, K., Okamoto, R.: Multisignature Schemes Secure Against Active Insider Attacks. IEICE Transactions on Fundamentals E82-A, 21–31 (1999)
Lu, S., Ostrovsky, R., Sahai, A., Shacham, H., Waters, B.: Sequential Aggregate Signatures and Multisignatures Without Random Oracles. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 465–485. Springer, Heidelberg (2006)
Ristenpart, T., Yilek, S.: The Power of Proofs-of-Possession: Securing Multiparty Signatures Against Rogue-Key Attacks. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 228–245. Springer, Heidelberg (2007)
Adams, C., Farrell, S., Kause, T., Monen, T.: Internet X.509 Public Key Infrastructure Certificate Management Protocol, cmp (2005)
Schaad, J.: Internet X.509 Public Key Infrastructure Certificate Request Message Format (2005)
Ma, C., Weng, J., Li, Y., Deng, R.: Efficient Discrete Logarithm Based Multi-Signature Scheme in the Plain Public Key Model. Des. Codes Cryptography 54, 121–133 (2010)
Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and Verifiably Encrypted Signatures. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 416–432. Springer, Heidelberg (2003)
Bellare, M., Rogaway, P.: Random Oracles Are Practical: a Paradigm for Designing Efficient Protocols. In: 10th ACM Conference on Computer and Communications Security, pp. 62–73. ACM Press, New York (1993)
Bellare, M., Namprempre, C., Neven, G.: Unrestricted Aggregate Signatures. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 411–422. Springer, Heidelberg (2007)
Barr, K., Asanović, K.: Energy-Aware Lossless Data Compression. ACM Trans. Comput. Syst. 24, 250–291 (2006)
Qian, H., Xu, S.: Non-Interactive Multisignatures in the Plain Public-Key Model with Efficient Verification. Inf. Process. Lett. 111, 82–89 (2010)
Goldwasser, S., Micali, S., Rivest, R.: A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks. SIAM Journal of Computing 17, 281–308 (1988)
Boneh, D., Lynn, B., Shacham, H.: Short Signatures from the Weil Pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001)
Galbraith, S., Paterson, K., Smart, N.: Pairings for Cryptographers. Discrete Applied Mathematics 156, 3113–3121 (2008)
Lysyanskaya, A., Micali, S., Reyzin, L., Shacham, H.: Sequential Aggregate Signatures from Trapdoor Permutations. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 74–90. Springer, Heidelberg (2004)
Neven, G.: Efficient Sequential Aggregate Signed Data. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 52–69. Springer, Heidelberg (2008)
Gentry, C., Ramzan, Z.: Identity-Based Aggregate Signatures. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 257–273. Springer, Heidelberg (2006)
Ahn, J.H., Green, M., Hohenberger, S.: Synchronized Aggregate Signatures: New Definitions, Constructions and Applications. In: 17th ACM Conference on Computer and Communications Security, pp. 473–484. ACM Press, New York (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zhou, Y., Qian, H., Li, X. (2011). Non-interactive CDH-Based Multisignature Scheme in the Plain Public Key Model with Tighter Security. In: Lai, X., Zhou, J., Li, H. (eds) Information Security. ISC 2011. Lecture Notes in Computer Science, vol 7001. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24861-0_23
Download citation
DOI: https://doi.org/10.1007/978-3-642-24861-0_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-24860-3
Online ISBN: 978-3-642-24861-0
eBook Packages: Computer ScienceComputer Science (R0)