Abstract
A secret sharing scheme permits a secret to be shared among participants in such a way that only qualified subsets of participants can recover the secret, but any nonqualified subset has absolutely no information on the secret. The set of all qualified subsets defines the access structure to the secret. Sharing schemes are useful in the management of cryptographic keys and in multiparty secure protocols.
We analyze the relationships among the entropies of the sample spaces from which the shares and the secret are chosen. We show that there are access structures with four participants for which any secret sharing scheme must give to a participant a share at least 50% greater than the secret size. This is the first proof that there exist access structures for which the best achievable information rate (i.e., the ratio between the size of the secret and that of the largest share) is bounded away from 1. The bound is the best possible, as we construct a secret sharing scheme for the above access structures that meets the bound with equality.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J. C. Benaloh and J. Leichter, Generalized Secret Sharing and Monotone Functions, Proceedings of Crypto '88—Advances in Cryptology, Lecture Notes in Computer Science, vol. 403, S. Goldwasser, ed., Springer-Verlag, Berlin, 1990, pp. 27–35.
G. R. Blakley, Safeguarding Cryptographic Keys, Proceedings of AFIPS 1979 National Computer Conference, vol. 48, New York, June 1979, pp. 313–317.
G. R. Blakley and C. Meadows, Security of Ramp Schemes, Proceedings 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, D. R. Stinson, and U. Vaccaro, Graph Decomposition and Secret Sharing Schemes, Proceedings of Eurocrypt '92—Advances in Cryptology, Lecture Notes in Computer Science, Springer-Verlag, Berlin, to appear.
E. F. Brickell and D. M. Davenport, On the Classification of Ideal Secret Sharing Schemes, Journal of Cryptology, vol. 4, no. 2, 1991, pp. 123–134.
E. F. Brickell and D. R. Stinson, Some Improved Bounds on the Information Rate of Perfect Secret Sharing Schemes, Proceedings of Crypto '90—Advances in Cryptology, Lecture Notes in Computer Science, vol. 576, S. A. Vanstone, ed., Springer-Verlag, Berlin, 1992, pp. 242–252.
R. M. Capocelli, A. De Santis, L. Gargano, and U. Vaccaro, A Note on Secret Sharing Schemes, in: Sequences II: Methods in Communications, Security and Computer Science, R. M. Capocelli, A. De Santis, and U. Vaccaro, eds., Springer-Verlag, Berlin, 1993, pp. 335–344.
I. Csiszár and J. Körner, Information Theory. Coding Theorems for Discrete Memoryless Systems, Academic Press, New York, 1981.
D. Denning, Cryptography and Data Security, Addison-Wesley, Reading, MA, 1983.
R. G. Gallager, Information Theory and Reliable Communications, Wiley, New York, 1968.
O. Goldreich, S. Micali, and A. Wigderson, How to Play Any Mental Game, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, New York, 1987, pp. 218–229.
M. Ito, A. Saito, and T. Nishizeki, Secret Sharing Scheme Realizing General Access Structure, Proceedings of IEEE Global Telecommunications Conference—Globecom 87, Tokyo, 1987, pp. 99–102.
E. D. Karnin, J. W. Greene, and M. E. Hellman, On Secret Sharing Systems, IEEE Transactions on Information Theory, vol. 29, no. 1, 1983, pp. 35–41.
S. C. Kothari, Generalized Linear Threshold Schemes, Proceedings 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. 231–241.
A Shamir, How To Share a Secret, Communications of the ACM, vol. 22, no. 11, 1979, pp. 612–613.
C. E. Shannon, The Mathematical Theory of Communication, Bell. Systems Journal, vol. 27, July/Oct. 1948, pp. 379–423, 623–656.
G. J. Simmons, Robust Shared Secret Schemes or “How To Be Sure You Have the Right Answer Even Though You Don't Know the Question,” Congressus Numerantium, vol. 8, 1989, pp. 215–248.
Author information
Authors and Affiliations
Additional information
Communicated by Ernest F. Brickell
This work was partially supported by “Algoritmi, Modelli di Calcolo e Sistemi Informativi” of M.U.R.S.T. and by “Progetto Finalizzato Sistemi Informatici e Calcolo Parallelo” of C.N.R. under Grant Number 91.00939.PF69.
Rights and permissions
About this article
Cite this article
Capocelli, R.M., De Santis, A., Gargano, L. et al. On the size of shares for secret sharing schemes. J. Cryptology 6, 157–167 (1993). https://doi.org/10.1007/BF00198463
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00198463