Abstract
Self-healing key distribution schemes enables a large and dynamic group of users to establish a group key over an unreliable network. A group manager broadcasts in every session some packet of information in order to provide a common key to members in the session group. The goal of self-healing key distribution schemes is that even if in a certain session the broadcast is lost, the group member can recover the key from the broadcast packet received before and after the session. This approach to key distribution is quite suitable for wireless networks, mobile wireless ad-hoc networks and in several Internet-related settings, where high security requirements need to be satisfied.
In this work we provide a generalization of previous definitions in two aspects. The first one is to consider general monotone decreasing structures for the family of subsets of users that can be revoked instead of a threshold one. The objective of this generalization is to reach more flexible performances of the scheme. In the second one, the distance between the broadcasts used to supply the lost one is limited in order to shorten the length of the broadcast information by the group manager. After giving the formal definition of threshold self-healing key distribution schemes, we find some lower bounds on the amount of information used for the system. We also give a general construction that gives us a family of threshold self-healing key distribution schemes by means of a linear secret sharing scheme. We prove the security of the schemes constructed in this way and we analyze the efficiency.
This work was done while the author was in the Dipartimento di Informatica ed Applicazioni at the Università di Salerno, Italy. The author would like to thank people in the Crypto Research Group for their kind hospitality and useful comments. Research supported in part by Spanish Ministerio de Ciencia y Tecnología under project CICYT TIC 2003–00866.
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
Blundo, C., D’Arco, P., De Santis, A., Listo, M.: Design of Self-Healing Key Distribution Schemes. Designs, Codes and Cryptography 32, 15–44 (2004)
Blundo, C., D’Arco, P., De Santis, A., Listo, M.: Definitions and Bounds for Self-Healing Key Distribution. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 234–245. Springer, Heidelberg (2004)
Brickell, E.F.: Some ideal secret sharing schemes. Journal of Combinatorial Mathematics and Combinatorial Computing 9, 105–113 (1989)
Cover, T.M., Thomas, J.A.: Elements of Information Theory. John Wiley & Sons, Chichester (1991)
Daza, V., Herranz, J., Sáez, G.: Constructing General Dynamic Group Key Distribution Schemes with Decentralized User Join. In: Safavi-Naini, R., Seberry, J. (eds.) ACISP 2003. LNCS, vol. 2727, pp. 464–475. Springer, Heidelberg (2003)
Liu, D., Ning, P., Sun, K.: Efficient Self-Healing Key Distribution with Revocation Capability. In: 10th ACM Conference on Computer and Communications Security (2003)
Padró, C., Sáez, G.: Secret sharing schemes with bipartite access structure. IEEE Transactions on Information Theory 46(7), 2596–2604 (2000)
Shamir, A.: How to share a secret. Communications of the ACM 22, 612–613 (1979)
Simmons, G.J., Jackson, W., Martin, K.: The geometry of secret sharing schemes. Bulletin of the ICA 1, 71–88 (1991)
Staddon, J., Miner, S., Franklin, M., Balfanz, D., Malkin, M., Dean, D.: Self-Healing Key Distribution with Revocation. IEEE Symposium on Security and Privacy (2002)
Stinson, D.R.: An explication of secret sharing schemes. Designs, Codes and Cryptography 2, 357–390 (1992)
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
Sáez, G. (2005). On Threshold Self-healing Key Distribution Schemes. In: Smart, N.P. (eds) Cryptography and Coding. Cryptography and Coding 2005. Lecture Notes in Computer Science, vol 3796. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11586821_23
Download citation
DOI: https://doi.org/10.1007/11586821_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30276-6
Online ISBN: 978-3-540-32418-8
eBook Packages: Computer ScienceComputer Science (R0)