Abstract
A well-known fact in the theory of secret sharing schemes is that shares must be of length at least as the secret itself. However, the proof of this lower bound uses the notion of information theoretic secrecy. A natural (and very practical) question is whether one can do better for secret sharing if the notion of secrecy is computational, namely, against resource bounded adversaries. In this note we observe that, indeed, one can do much better in the computational model (which is the one used in most applications).
We present an m-threshold scheme, where m shares recover the secret but m − 1 shares give no (computational) information on the secret, in which shares corresponding to a secret S are of size |S|/m plus a short piece of information whose length does not depend on the secret size but just in the security parameter. (The bound of |S|/m is clearly optimal if the secret is to be recovered from m shares). Therefore, for moderately large secrets (a confidential file, a long message, a large data base) the savings in space and communication over traditional schemes is remarkable. The scheme is very simple and combines in a natural way traditional (perfect) secret sharing schemes, encryption, and information dispersal. It is provable secure given a secure (e.g., private key) encryption function.
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
Benaloh, J. and Leichter J., “Generalized secret sharing and monotone functions”, Proc. Crypto’ 88, pp. 27–35.
Blakley, G.R., “Safeguarding Cryptographic Keys”, Proc. AFIPS 1979 National Computer Conference, New York, Vol. 48, 1979, pp. 313–317.
Blakley, G.R., and Meadows C. “Security of Ramp Schemes”, in Lecture Notes in Computer Science 196; Advances in Cryptology: Proc. Crypto’ 84, Springer-Verlag, 1985, pp.242–268.
Brickel, E.F., and Stinson, D.R., “The Detection of Cheaters in Threshold Schemes”, in Lecture Notes in Computer Science 403; Advances in Cryptology: Proc. Crypto’ 88, Springer-Verlag, 1990, pp.564–577.
Chor, B., S. Goldwasser, S. Micali, and B. Awerbuch, “Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults”, Proc. 26th FOCS, 1985, pp. 383–395.
Dolev, D., Dwork, C., Waarts, O., and Yung, M., “Perfectly Secure Message Transmission”, Proc. 31st IEEE Symp. on Foundations of Computer Science, 1990, pp. 36–45.
Goldreich, O., “A Uniform-Complexity Treatment of Encryption and Zero-Knowlege”, Jour. of Cryptology, Vol. 6, No. 1, 1993, pp.21–53.
Goldwasser, S., and S. Micali, “Probabilistic Encryption”, JCSS, Vol. 28, No. 2, 1984, pp. 270–299.
Krawczyk, H., “Distributed Fingerprints and Secure Information Dispersal”, Proc. of 12th. PODC, pp. 207–218, 1993.
McElice R.J., and Sarwate, D.V., “On Sharing Secrets and Reed-Solomon Codes”, Comm. ACM, Vol. 24, No. 9, 1978, pp. 583–584.
Micali, S., “Fair Public-Key Cryptosystems”, Crypto’ 92.
Naor, M., and Roth, R.M., “Optimal File Sharing in Distributed Networks”, Proc. 32nd IEEE Symp. on Foundations of Computer Science, 1991, pp. 515–525.
Preparata, F.P., “Holographic Dispersal and Recovery of Information”, IEEE Trans. on Information Theory, IT-35, No. 5, 1989, pp. 1123–1124.
Rabin, M.O., “Randomized Byzantine Agreement”, 24th FOCS, pp. 403–409, 1983.
Rabin, M.O., “Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance”, Jour. of ACM, Vol. 36, No. 2, 1989, pp. 335–348.
Shamir, A., “How to Share a Secret”, Comm. ACM, Vol. 22, No. 11, 1979, pp. 612–613.
Tompa, M. and H. Woll, “How to share a secret with cheaters”, Journal of Cryptology, Vol 1, 1988, pp 133–138.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Krawczyk, H. (1994). Secret Sharing Made Short. In: Stinson, D.R. (eds) Advances in Cryptology — CRYPTO’ 93. CRYPTO 1993. Lecture Notes in Computer Science, vol 773. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48329-2_12
Download citation
DOI: https://doi.org/10.1007/3-540-48329-2_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57766-9
Online ISBN: 978-3-540-48329-8
eBook Packages: Springer Book Archive