[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Secret-Sharing Schemes: A Survey

  • Conference paper
Coding and Cryptology (IWCC 2011)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 6639))

Included in the following conference series:

  • 4237 Accesses

Abstract

A secret-sharing scheme is a method by which a dealer distributes shares to parties such that only authorized subsets of parties can reconstruct the secret. Secret-sharing schemes are an important tool in cryptography and they are used as a building box in many secure protocols, e.g., general protocol for multiparty computation, Byzantine agreement, threshold cryptography, access control, attribute-based encryption, and generalized oblivious transfer.

In this survey, we describe the most important constructions of secret-sharing schemes; in particular, we explain the connections between secret-sharing schemes and monotone formulae and monotone span programs. We then discuss the main problem with known secret-sharing schemes – the large share size, which is exponential in the number of parties. We conjecture that this is unavoidable. We present the known lower bounds on the share size. These lower bounds are fairly weak and there is a big gap between the lower and upper bounds. For linear secret-sharing schemes, which is a class of schemes based on linear algebra that contains most known schemes, super-polynomial lower bounds on the share size are known. We describe the proofs of these lower bounds. We also present two results connecting secret-sharing schemes for a Hamiltonian access structure to the NP vs. coNP problem and to a major open problem in cryptography – constructing oblivious-transfer protocols from one-way functions.

Research supported by ISF grant 938/09 and by the Frankel Center for Computer Science.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 35.99
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
GBP 44.99
Price includes VAT (United Kingdom)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Alon, N., Goldreich, O., Håstad, J., Peralta, R.: Simple constructions of almost k-wise independent random variables. Random Structures & Algorithms 3, 289–304 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  2. Babai, L., Gál, A., Wigderson, A.: Superpolynomial lower bounds for monotone span programs. Combinatorica 19(3), 301–319 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  3. Beimel, A.: Secure Schemes for Secret Sharing and Key Distribution. PhD thesis, Technion (1996), http://www.cs.bgu.ac.il/~beimel/pub.html

  4. Beimel, A., Chor, B.: Universally ideal secret sharing schemes. IEEE Trans. on Information Theory 40(3), 786–794 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  5. Beimel, A., Gál, A., Paterson, M.: Lower bounds for monotone span programs. Computational Complexity 6(1), 29–45 (1997); Conference version: FOCS 1995

    Article  MathSciNet  MATH  Google Scholar 

  6. Beimel, A., Ishai, Y.: On the power of nonlinear secret-sharing. SIAM J. on Discrete Mathematics 19(1), 258–280 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  7. Beimel, A., Livne, N., Padró, C.: Matroids can be far from ideal secret sharing. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 194–212. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  8. Beimel, A., Orlov, I.: Secret sharing and non-shannon information inequalities. IEEE Trans. on Information Theory (2011); Preliminary version Reingold, O. (ed.): TCC 2009. LNCS, vol. 5444, pp. 539–557. Springer, Heidelberg (2009)

    Book  Google Scholar 

  9. Beimel, A., Paskin, A.: On linear secret sharing for connectivity in directed graphs. In: Ostrovsky, R., De Prisco, R., Visconti, I. (eds.) SCN 2008. LNCS, vol. 5229, pp. 172–184. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  10. Beimel, A., Weinreb, E.: Separating the power of monotone span programs over different fields. SIAM J. on Computing 34(5), 1196–1215 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  11. Beimel, A., Weinreb, E.: Monotone circuits for monotone weighted threshold functions. Inform. Process. Lett. 97(1), 12–18 (2006); Conference version: Proc. of 20th Annu. IEEE Conf. on Computational Complexity, pp. 67–75 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  12. Bellare, M., Rogaway, P.: Robust computational secret sharing and a unified account of classical secret-sharing goals. In: Proc. of the 14th ACM Conference on Computer and Communications Security, pp. 172–184 (2007)

    Google Scholar 

  13. Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for noncryptographic fault-tolerant distributed computations. In: Proc. of the 20th ACM Symp. on the Theory of Computing, pp. 1–10 (1988)

    Google Scholar 

  14. Benaloh, J.C., Leichter, J.: Generalized secret sharing and monotone functions. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 27–35. Springer, Heidelberg (1990)

    Chapter  Google Scholar 

  15. Benaloh, J.C., Rudich, S.: Private communication (1989)

    Google Scholar 

  16. Bertilsson, M., Ingemarsson, I.: A construction of practical secret sharing schemes using linear block codes. In: Zheng, Y., Seberry, J. (eds.) AUSCRYPT 1992. LNCS, vol. 718, pp. 67–79. Springer, Heidelberg (1993)

    Chapter  Google Scholar 

  17. Blakley, G.R.: Safeguarding cryptographic keys. In: Merwin, R.E., Zanca, J.T., Smith, M. (eds.) Proc. of the 1979 AFIPS National Computer Conference. AFIPS Conference Proceedings, vol. 48, pp. 313–317. AFIPS Press (1979)

    Google Scholar 

  18. Blundo, C., De Santis, A., De Simone, R., Vaccaro, U.: Tight bounds on the information rate of secret sharing schemes. Designs, Codes and Cryptography 11(2), 107–122 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  19. Blundo, C., De Santis, A., Gargano, L., Vaccaro, U.: On the information rate of secret sharing schemes. Theoretical Computer Science 154(2), 283–306 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  20. Blundo, C., De Santis, A., Vaccaro, U.: On secret sharing schemes. Inform. Process. Lett. 65(1), 25–32 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  21. Brickell, E.F.: Some ideal secret sharing schemes. Journal of Combin. Math. and Combin. Comput. 6, 105–113 (1989)

    MathSciNet  MATH  Google Scholar 

  22. Brickell, E.F., Davenport, D.M.: On the classification of ideal secret sharing schemes. J. of Cryptology 4(73), 123–134 (1991)

    MATH  Google Scholar 

  23. Capocelli, R.M., De Santis, A., Gargano, L., Vaccaro, U.: On the size of shares for secret sharing schemes. J. of Cryptology 6(3), 157–168 (1993)

    Article  MATH  Google Scholar 

  24. Chaum, D., Crépeau, C., Damgård, I.: Multiparty unconditionally secure protocols. In: Proc. of the 20th ACM Symp. on the Theory of Computing, pp. 11–19 (1988)

    Google Scholar 

  25. Chor, B., Goldwasser, S., Micali, S., Awerbuch, B.: Verifiable secret sharing and achieving simultaneity in the presence of faults (extended abstract). In: Proc. of the 26th IEEE Symp. on Foundations of Computer Science, pp. 383–395 (1985)

    Google Scholar 

  26. Chor, B., Kushilevitz, E.: Secret sharing over infinite domains. J. of Cryptology 6(2), 87–96 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  27. Cover, T.M., Thomas, J.A.: Elements of Information Theory. John Wiley & Sons, Chichester (1991)

    Book  MATH  Google Scholar 

  28. Cramer, R., Damgård, I.B., Maurer, U.M.: General secure multi-party computation from any linear secret-sharing scheme. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 316–334. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  29. Csirmaz, L.: The size of a share must be large. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 223–231. Springer, Heidelberg (1995); Journal version in: J. of Cryptology 10(4), 223–231 (1997)

    Google Scholar 

  30. Csirmaz, L.: The dealer’s random bits in perfect secret sharing schemes. Studia Sci. Math. Hungar. 32(3-4), 429–437 (1996)

    MathSciNet  MATH  Google Scholar 

  31. Desmedt, Y.G., Frankel, Y.: Shared generation of authenticators and signatures. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 457–469. Springer, Heidelberg (1992)

    Google Scholar 

  32. van Dijk, M.: A linear construction of perfect secret sharing schemes. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 23–34. Springer, Heidelberg (1995)

    Chapter  Google Scholar 

  33. van Dijk, M.: On the information rate of perfect secret sharing schemes. Designs, Codes and Cryptography 6, 143–169 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  34. van Dijk, M., Kevenaar, T., Schrijen, G.-J., Tuyls, P.: Improved constructions of secret sharing schemes by applying (λ],ω)-decompositions. Inform. Process. Lett. 99(4), 154–157 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  35. Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. CACM 28(6), 637–647 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  36. Gál, A.: A characterization of span program size and improved lower bounds for monotone span programs. Computational Complexity 10(4), 277–296 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  37. Gál, A., Pudlák, P.: Monotone complexity and the rank of matrices. Inform. Process. Lett. 87, 321–326 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  38. Gennaro, R., Rabin, M.O., Rabin, T.: Simplified vss and fact-track multiparty computations with applications to threshold cryptography. In: Proc. of the 17th ACM Symp. on Principles of Distributed Computing, pp. 101–111 (1998)

    Google Scholar 

  39. Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: Proc. of the 19th ACM Symp. on the Theory of Computing, pp. 218–229 (1987)

    Google Scholar 

  40. Goyal, V., Pandey, O., Sahai, A., Waters, B.: Attribute-based encryption for fine-grained access control of encrypted data. In: Proc. of the 13th ACM Conference on Computer and Communications Security, pp. 89–98 (2006)

    Google Scholar 

  41. Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: Construction of a pseudo-random generator from any one-way function. SIAM J. on Computing 28(4), 1364–1396 (1999)

    Article  MATH  Google Scholar 

  42. Hirt, M., Maurer, U.: Player simulation and general adversary structures in perfect multiparty computation. J. of Cryptology 13(1), 31–60 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  43. Impagliazzo, R.: A personal view of average-case complexity. In: Proc. of the 10th IEEE Structure in Complexity Theory, pp. 134–147 (1995)

    Google Scholar 

  44. Impagliazzo, R., Rudich, S.: Limits on the provable consequences of one-way permutations. In: Proc. of the 21st ACM Symp. on the Theory of Computing, pp. 44–61 (1989)

    Google Scholar 

  45. Ito, M., Saito, A., Nishizeki, T.: Secret sharing schemes realizing general access structure. In: Proc. of the IEEE Global Telecommunication Conf., Globecom 1987, pp. 99–102 (1987); Journal version: Multiple assignment scheme for sharing secret. J. of Cryptology, 6(1), 15–20 (1993)

    Google Scholar 

  46. Karchmer, M., Wigderson, A.: On span programs. In: Proc. of the 8th IEEE Structure in Complexity Theory, pp. 102–111 (1993)

    Google Scholar 

  47. Karnin, E.D., Greene, J.W., Hellman, M.E.: On secret sharing systems. IEEE Trans. on Information Theory 29(1), 35–41 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  48. Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)

    Book  MATH  Google Scholar 

  49. Martí-Farré, J., Padró, C.: On secret sharing schemes, matroids and polymatroids. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 273–290. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  50. Matúš, F.: Infinitely many information inequalities. In: IEEE International Symposium on Information Theory 2007, pp. 41–44 (2007)

    Google Scholar 

  51. Metcalf-Burton, J.R.: Improved upper bounds for the information rates of the secret sharing schemes induced by the Vamos matroid. Technical Report abs/0809.3010, CoRR (2008)

    Google Scholar 

  52. Naor, M., Wool, A.: Access control and signatures via quorum secret sharing. IEEE Transactions on Parallel and Distributed Systems 9(1), 909–922 (1998)

    Article  Google Scholar 

  53. Rabin, M.O.: How to exchange secrets by oblivious transfer. Technical Report TR-81, Harvard Aiken Computation Laboratory (1981), Available online in the Cryptology ePrint Archive, Report 2005/187, http://eprint.iacr.org/2005/187

  54. Rabin, M.O.: Randomized Byzantine generals. In: Proc. of the 24th IEEE Symp. on Foundations of Computer Science, pp. 403–409 (1983)

    Google Scholar 

  55. Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: Proc. of the 22nd ACM Symp. on the Theory of Computing, pp. 387–394 (1990)

    Google Scholar 

  56. Rudich, S.: Private communication, via M. Naor (1989)

    Google Scholar 

  57. Sahai, A., Waters, B.: Fuzzy identity-based encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457–473. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  58. Shamir, A.: How to share a secret. Communications of the ACM 22, 612–613 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  59. Shankar, B., Srinathan, K., Rangan, C.P.: Alternative protocols for generalized oblivious transfer. In: Rao, S., Chatterjee, M., Jayanti, P., Murthy, C.S.R., Saha, S.K. (eds.) ICDCN 2008. LNCS, vol. 4904, pp. 304–309. Springer, Heidelberg (2008)

    Chapter  Google Scholar 

  60. Simmons, G.J.: How to (really) share a secret. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 390–448. Springer, Heidelberg (1990)

    Chapter  Google Scholar 

  61. Simmons, G.J., Jackson, W., Martin, K.M.: The geometry of shared secret schemes. Bulletin of the ICA 1, 71–88 (1991)

    MathSciNet  MATH  Google Scholar 

  62. Simonis, J., Ashikhmin, A.: Almost affine codes. Designs, Codes and Cryptography 14(2), 179–197 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  63. Stinson, D.R.: Decomposition construction for secret sharing schemes. IEEE Trans. on Information Theory 40(1), 118–125 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  64. Tassa, T.: Hierarchical threshold secret sharing. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 473–490. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  65. Tassa, T.: Generalized oblivious transfer by secret sharing. Designs, Codes and Cryptography 58 (2011)

    Google Scholar 

  66. Tassa, T., Dyn, N.: Multipartite secret sharing by bivariate interpolation. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 288–299. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  67. Vinod, V., Narayanan, A., Srinathan, K., Pandu Rangan, C., Kim, K.: On the power of computational secret sharing. In: Johansson, T., Maitra, S. (eds.) INDOCRYPT 2003. LNCS, vol. 2904, pp. 162–176. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  68. Waters, B.: Ciphertext-policy attribute-based encryption: An expressive, efficient, and provably secure realization. Technical Report 2008/290, Cryptology ePrint Archive (2008), http://eprint.iacr.org/

  69. Yao, A.C.: Unpublished manuscript. Presented at Oberwolfach and DIMACS Workshops (1989)

    Google Scholar 

  70. Yeung, R.W.: Information Theory and Network Coding. Springer, Heidelberg (2008)

    MATH  Google Scholar 

  71. Zhang, Z., Yeung, R.W.: On characterization of entropy function via information inequalities. IEEE Trans. on Information Theory 44(4), 1440–1452 (1998)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel

    Amos Beimel

Authors
  1. Amos Beimel
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Physical and Mathematical Sciences, Division of Mathematical Sciences, Nanyang Technological University, 637371, Singapore

    Yeow Meng Chee , San Ling , Huaxiong Wang  & Chaoping Xing , ,  & 

  2. College of Information Engineering, Qingdao University, 266071, Shandong, P.R. China

    Zhenbo Guo

  3. Qingdao University, 266071, Shandong, P.R. China

    Fengjing Shao

  4. School of Mathematical Sciences, Yangzhou University, 225002, Jiangsu, P.R. China

    Yuansheng Tang

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Beimel, A. (2011). Secret-Sharing Schemes: A Survey. In: Chee, Y.M., et al. Coding and Cryptology. IWCC 2011. Lecture Notes in Computer Science, vol 6639. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-20901-7_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-20901-7_2

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-20900-0

  • Online ISBN: 978-3-642-20901-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation