Abstract
We consider the problem of threshold secret sharing in groups with hierarchical structure. In such settings, the secret is shared among a group of participants that is partitioned into levels. The access structure is then determined by a sequence of threshold requirements: a subset of participants is authorized if it has at least k 0 members from the highest level, as well as at least k 1 > k 0 members from the two highest levels and so forth. Such problems may occur in settings where the participants differ in their authority or level of confidence and the presence of higher level participants is imperative to allow the recovery of the common secret. Even though secret sharing in hierarchical groups has been studied extensively in the past, none of the existing solutions addresses the simple setting where, say, a bank transfer should be signed by three employees, at least one of whom must be a department manager. We present a perfect secret sharing scheme for this problem that, unlike most secret sharing schemes that are suitable for hierarchical structures, is ideal. As in Shamir’s scheme, the secret is represented as the free coefficient of some polynomial. The novelty of our scheme is the usage of polynomial derivatives in order to generate lesser shares for participants of lower levels. Consequently, our scheme uses Birkhoff interpolation, i.e., the construction of a polynomial according to an unstructured set of point and derivative values. A substantial part of our discussion is dedicated to the question of how to assign identities to the participants from the underlying finite field so that the resulting Birkhoff interpolation problem will be well posed. In the course of this discussion, we borrow some results from the theory of Birkhoff interpolation over ℝ and import them to the context of finite fields.
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
Atkinson, K., Sharma, A.: A partial characterization of poised Hermite-Birkhoff interpolation problems. Siam Journal on Numerical Analysis 6, 230–235 (1969)
Benaloh, J., Leichter, J.: Generalized secret sharing and monotone functions. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 27–35. Springer, Heidelberg (1990)
Beutelspacjer, A., Vedder, K.: Geometric structures as threshold schemes. In: Cryptography and Coding, pp. 255–268. Clarendon Press (1989)
Blakley, G.R.: Safeguarding cryptographic keys. In: Proceedings of the National Computer Conference, AFIPS, vol. 48, pp. 313–317 (1979)
Brickell, E.F.: Some ideal secret sharing schemes. Journal of Combinatorial Mathematics and Combinatorial Computing 9, 105–113 (1989)
Charnes, C., Martin, K., Pieprzyk, J., Safavi-Naini, R.: Sharing secret information in hierarchical groups. In: Han, Y., Quing, S. (eds.) ICICS 1997. LNCS, vol. 1334, pp. 81–86. Springer, Heidelberg (1997)
Dawson, E., Donovan, D.: The breadth of Shamir’s secret sharing scheme. Computers and Security 13, 69–78 (1994)
Faddeev, D.K., Sominskii, I.S.: Problems in Higher Algebra. W.H. Freeman, San Francisco (1965)
Friedman, J.: Constructing O(n log n) size monotone formulae for the k-th elementary symmetric polynomial of n Boolean variables. IEEE Symposium on Foundations of Computer Science, 506–515 (1984)
Gál, A.: Combinatorial Methods in Boolean Function Complexity. Ph.D. thesis, University of Chicago (1995)
Karchmer, M., Wigderson, A.: On span programs. In: 8th Annual Conference on Structure in Complexity Theory (SCTC 1993), pp. 102–111. IEEE Computer Society Press, Los Alamitos (1993)
Lorentz, G.G., Jetter, K., Riemenschneider, S.D.: Birkhoff Interpolation. In: Encyclopedia of Mathematics and its Applications, vol. 19, Addison-Wesley, Reading (1983)
Padró, C., Sáez, G.: Secret sharing schemes with bipartite access structure. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 500–511. Springer, Heidelberg (1998)
Schoenberg, I.J.: On Hermite-Birkhoff interpolation. Journal of Mathematical Analysis and Applications 16, 538–543 (1966)
Shamir, A.: How to share a secret. Communications of the ACM 22, 612–613 (1979)
Simmons, G.J.: How to (really) share a secret. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 390–448. Springer, Heidelberg (1990)
Simmons, G.J.: An introduction to shared secret and/or shared control schemes and their applications. In: Contemporary Cryptology, The Science of Information Integrity, pp. 441–497. IEEE Press, Los Alamitos (1991)
Wool, A.: Private communication
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Tassa, T. (2004). Hierarchical Threshold Secret Sharing. In: Naor, M. (eds) Theory of Cryptography. TCC 2004. Lecture Notes in Computer Science, vol 2951. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24638-1_26
Download citation
DOI: https://doi.org/10.1007/978-3-540-24638-1_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21000-9
Online ISBN: 978-3-540-24638-1
eBook Packages: Springer Book Archive