Abstract
A multicast communication source often needs to securely verify which multicast group members have received a message, but verification of individually signed acknowledgments from each member would impose a significant computation and communication cost. As pointed out by Nicolosi and Mazieres [NM04], such cost is minimized if the intermediate nodes along the multicast distribution tree aggregate the individual signatures generated by the multicast receivers into a single multisignature.
While the solution of [NM04], based on a multisignature scheme of Boldyreva [Bol03], relied on so-called “Gap Diffie-Hellman” groups, we propose a solution using a multisignature scheme which is secure under just the discrete logarithm assumption. However, unlike the previously known discrete-log based multisignature scheme of Micali et al. [MOR01a], our multisignature scheme is robust, which allows for an efficient multisignature generation even in the presence of (possibly malicious) node and communication failures.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiable encrypted signatures from bilinear maps. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, Springer, Heidelberg (2003)
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)
Boldyreva, A.: Efficient threshold signatures, multisignatures and blind signatures based on the gap-diffie-hellman-group signature scheme. In: Public Key Cryptography 2003 (2003)
Gagne, M.: Applications of bilinear maps in cryptography. Master’s thesis, University of Waterloo (2002)
Itakura, K., Nakamura, K.: A public-key cryptosystem suitable for digital multisignatures. NEC Research and Development (71), 1-8 October (1983)
Joux, A.: The weil and tate pairings as building blocks for public key cryptosystems. In: Proceedings of the 5th International Symposium on Algorithmic Number Theory (2002)
Merkle, R.C.: A certified digital signature. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 218–238. Springer, Heidelberg (1990)
Micali, S., Ohta, K., Reyzin, L.: Accountable-subgroup multisignatures. In: ACM Conference on Computer and Communications Security (October 2001)
Micali, S., Ohta, K., Reyzin, L.: Accountable-subgroup multisignatures (2001), available from, www.cs.bu.edu/~reyzin/research.html
Nicolosi, A., Mazieres, D.: Secure acknowledgement of multicast messages in open peer-to-peer networks. In: Voelker, G.M., Shenker, S. (eds.) IPTPS 2004. LNCS, vol. 3279, pp. 259–268. Springer, Heidelberg (2005)
Pointcheval, D., Stern, J.: Security proofs for signature schemes. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 387–398. Springer, Heidelberg (1996)
Schnorr, C.: Efficient identification and signatures for smart cards. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 688–689. Springer, Heidelberg (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Castelluccia, C., Jarecki, S., Kim, J., Tsudik, G. (2005). A Robust Multisignature Scheme with Applications to Acknowledgement Aggregation. In: Blundo, C., Cimato, S. (eds) Security in Communication Networks. SCN 2004. Lecture Notes in Computer Science, vol 3352. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30598-9_14
Download citation
DOI: https://doi.org/10.1007/978-3-540-30598-9_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24301-4
Online ISBN: 978-3-540-30598-9
eBook Packages: Computer ScienceComputer Science (R0)