Abstract
A secret sharing scheme permits a secret to be shared among participants of an n-element group in such a way that only qualified subsets of participants can recover the secret. If any non-qualified subset has absolutely no information on the secret, then the scheme is called perfect. The share in a scheme is the information what a participant must remember. We prove that for each n there exists an access structure on n participants so that any perfect sharing scheme must give some participant a share which is at least about n/log n times the secret size. We also show that the best possible result achievable by the information theoretic method used here is n times the secret size.
This research was supported by OTKA grant no. 1911
Chapter PDF
References
G. R. Blakley and C. Meadows, Security of Ramp Schemes, Proceeding of Crypto'84 — Advances in Cryptology, Lecture Notes in Computer Science, Vol 196, G. R. Blakley and D. Chaum, eds. Springer-Verlag, Berlin, 1985, pp. 411–431.
C. Blundo, A. De Santis, L. Gargano, U. Vaccaro, On the Information Rate of Secret Sharing Schemes, in Advances in Cryptology — CRYPTO '92, Lecture Notes in Computer Science, Vol 740, E. Brickell ed, Springer-Verlag, Berlin, 1993, pp. 149–169.
C. Blundo, A. De Santis, A. G. Gaggia, U. Vaccaro, New Bounds on the Information Rate of Secret Sharing Schemes, Preprint, 1993
R. M. Capocelli, A. De Santis, U. Vaccaro, On the Size of Shares for Secret Sharing Schemes, Journal of Cryptology, Vol 6(1993) pp. 157–167.
M. Carpentieri, A. De Santis, U. Vaccaro, Size of Shares and Probability of Cheating in Threshold Schemes, Proceeding of Eurocrypt'93.
I. Csiszár and J. Körner, Information Theory. Coding Theorems for Discrete Memoryless Systems, Academic Press, New York, 1981.
I. Csiszár, personal communication.
M. van Dijk, On the Information Rate of Perfect Secret Sharing Schemes, Proprint, 1994
S. Fujishige, Polymatroid dependence structure of a set of random variables, Information and Control 39(1978) pp. 55–72.
M. Ito, A. Saito, T. Nishizeki, Multiple Assignment Scheme for Sharing Secret Journal of Cryptology, Vol 6(1993) pp. 15–20.
K. Kurosawa, K. Okada, K. Sakano, W. Ogata, S. Tsujii, Nonperfect Secret Sharing Schemes and Matroids, Proceedings of Eurocrypt'93.
G. J. Simmons, An Introduction to Shared Secret and/or Shared Control Schemes and Their Application, Contemporary Cryptology, IEEE Press pp. 441–497, 1991.
E. Sperner, Ein Stas über Untermengen einer endlichen Menge, Math. Z. 27(1928), pp. 544–548.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Csirmaz, L. (1995). The size of a share must be large. In: De Santis, A. (eds) Advances in Cryptology — EUROCRYPT'94. EUROCRYPT 1994. Lecture Notes in Computer Science, vol 950. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0053420
Download citation
DOI: https://doi.org/10.1007/BFb0053420
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60176-0
Online ISBN: 978-3-540-44717-7
eBook Packages: Springer Book Archive