Document Open Access Logo

Probabilistic Secret Sharing

Authors Paolo D'Arco , Roberto De Prisco , Alfredo De Santis , Angel Pérez del Pozo , Ugo Vaccaro

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.64.pdf
  • Filesize: 0.49 MB
  • 16 pages

Document Identifiers

Author Details

Paolo D'Arco
  • Dipartimento di Informatica, Università of Salerno, Italy
Roberto De Prisco
  • Dipartimento di Informatica, Università of Salerno, Italy
Alfredo De Santis
  • Dipartimento di Informatica, Università of Salerno, Italy
Angel Pérez del Pozo
  • Departamento de Matemática Aplicada, Ciencia e Ingeniería de los Materiales y Tecnología Electrónica, Universidad Rey Juan Carlos, Madrid, Spain
Ugo Vaccaro
  • Dipartimento di Informatica, Università of Salerno, Italy

Cite AsGet BibTex

Paolo D'Arco, Roberto De Prisco, Alfredo De Santis, Angel Pérez del Pozo, and Ugo Vaccaro. Probabilistic Secret Sharing. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.MFCS.2018.64

Abstract

In classical secret sharing schemes a dealer shares a secret among a set of participants in such a way that qualified subsets can reconstruct the secret, while forbidden ones do not get any kind of information about it. The basic parameter to optimize is the size of the shares, that is, the amount of secret information that the dealer has to give to participants. In this paper we formalize a notion of probabilistic secret sharing schemes, in which qualified subsets can reconstruct the secret but only with a certain controlled probability. We show that, by allowing a bounded error in the reconstruction of the secret, it is possible to drastically reduce the size of the shares the participants get (with respect to classical secret sharing schemes). We provide efficient constructions both for threshold access structures on a finite set of participants and for evolving threshold access structures, where the set of participants is potentially infinite. Some of our constructions yield shares of constant size (i.e., not depending on the number of participants) and an error probability of successfully reconstructing the secret which can be made as close to 1 as desired.

Subject Classification

ACM Subject Classification
  • Security and privacy → Mathematical foundations of cryptography
Keywords
  • Secret sharing
  • probabilistic secret sharing
  • evolving secret sharing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. G. Ateniese, C. Blundo, A. De Santis, and D. R. Stinson. Visual cryptography for general access structures. Inf. Comput., 129(2):86-106, 1996. URL: http://dx.doi.org/10.1006/inco.1996.0076.
  2. A. Beimel. Secret-sharing schemes: A survey. In Proceedings of the Third International Conference on Coding and Cryptology, LNCS 6639, pages 11-46, Berlin, Heidelberg, 2011. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=2017916.2017918.
  3. M. Bellare and P. Rogaway. Robust computational secret sharing and a unified account of classical secret-sharing goals. In Proceedings of the 14th ACM Conference on Computer and Communications Security, CCS '07, pages 172-184, New York, NY, USA, 2007. ACM. URL: http://dx.doi.org/10.1145/1315245.1315268.
  4. J. Benaloh and J. Leichter. Generalized secret sharing and monotone functions. In Proceedings on Advances in Cryptology, LNCS 403, pages 27-35, Berlin, Heidelberg, 1990. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=88314.88328.
  5. J. Benaloh and J. Leichter. Generalized secret sharing and monotone functions. In Proceedings on Advances in Cryptology (CRYPTO '88), LNCS 403, pages 27-35, Berlin, Heidelberg, 1990. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=88314.88328.
  6. G. R. Blakley. Safeguarding cryptographic keys. In Proceedings of the 1979 AFIPS National Computer Conference, pages 313-317. AFIPS Press, 1979. Google Scholar
  7. G. R. Blakley and C. Meadows. Security of ramp schemes. In Proceedings of CRYPTO 84 on Advances in Cryptology, pages 242-268, New York, NY, USA, 1985. Springer-Verlag New York, Inc. URL: http://dl.acm.org/citation.cfm?id=19478.19498.
  8. C. Blundo, A. De Santis, R. De Simone, and U. Vaccaro. Tight bounds on the information rate of secret sharing schemes. Designs, Codes and Cryptography, 11(2):107-110, May 1997. URL: http://dx.doi.org/10.1023/A:1008216403325.
  9. A. Bogdanov, S. Guo, and I. Komargodski. Threshold secret sharing requires a linear size alphabet. In Proceedings, Part II, of the 14th International Conference on Theory of Cryptography, LNCS 9986, pages 471-484, Berlin, Heidelberg, 2016. Springer-Verlag. URL: http://dx.doi.org/10.1007/978-3-662-53644-5_18.
  10. R. M. Capocelli, A. De Santis, L. Gargano, and U. Vaccaro. On the size of shares for secret sharing schemes. J. Cryptol., 6(3):157-167, 1993. URL: http://dx.doi.org/10.1007/BF00198463.
  11. I. Cascudo, R. Cramer, and C. Xing. Bounds on the threshold gap in secret sharing and its applications. Information Theory, IEEE Transactions on, 59:5600-5612, 09 2013. Google Scholar
  12. S.-K. Chen and S.-J. Lin. Optimal (2,n) and (2,∞) visual secret sharing by generalized random grids. J. Vis. Commun. Image R., 23:677-684, 2012. Google Scholar
  13. S. Cimato, R. De Prisco, and A. De Santis. Probabilistic visual cryptography schemes. Comput. J., 49(1):97-107, 2006. URL: http://dx.doi.org/10.1093/comjnl/bxh152.
  14. R. Cramer, I. Damgard, and J. B. Nielsen. Secure Multiparty Computation and Secret Sharing. Cambridge University Press, New York, NY, USA, 1st edition, 2015. Google Scholar
  15. L. Csirmaz. The size of a share must be large. Journal of Cryptology, 10(4):223-231, Sep 1997. URL: http://dx.doi.org/10.1007/s001459900029.
  16. László Csirmaz. Probabilistic infinite secret sharing. IACR Cryptology ePrint Archive, 2012:412, 2012. Google Scholar
  17. P. D'Arco and R. De Prisco. Visual cryptography - models, issues, applications and new directions. In Innovative Security Solutions for Information Technology and Communications - 9th International Conference, SECITC 2016, Bucharest, Romania, June 9-10, 2016, Revised Selected Papers, LNCS 10006, pages 20-39, 2016. URL: http://dx.doi.org/10.1007/978-3-319-47238-6_2.
  18. P. D'Arco, R. De Prisco, and Y. Desmedt. Private visual share-homomorphic computation and randomness reduction in visual cryptography. In Information Theoretic Security - 9th International Conference, ICITS 2016, Tacoma, WA, USA, August 9-12, 2016, Revised Selected Papers, LNCS 10015, pages 95-113, 2016. URL: http://dx.doi.org/10.1007/978-3-319-49175-2_5.
  19. R. De Prisco and A. De Santis. On the relation of random grid and deterministic visual cryptography. IEEE Trans. Information Forensics and Security, 9(4):653-665, 2014. URL: http://dx.doi.org/10.1109/TIFS.2014.2305574.
  20. A. Dibert and L. Csirmaz. Infinite secret sharing - examples. J. Mathematical Cryptology, 8(2):141-168, 2014. Google Scholar
  21. Y. Ishai, H. K. Maji, A. Sahai, and J. Wullschleger. Single-use ot combiners with near-optimal resilience. In 2014 IEEE International Symposium on Information Theory, pages 1544-1548, June 2014. URL: http://dx.doi.org/10.1109/ISIT.2014.6875092.
  22. M. Ito, A. Saio, and T. Nishizeki. Secret sharing schemes realizing general access structure. In Proc. of the IEEE Global Telecommunication Conf., Globecom '87, pages 99-102. IEEE, 1987. Google Scholar
  23. M. Ito, A. Saio, and T. Nishizeki. Multiple assignment scheme for sharing secret. J. Cryptology, 6(1):15-20, 1993. URL: http://dx.doi.org/10.1007/BF02620229.
  24. O. Kafri and E. Keren. Encryption of pictures and shapes by random grids. Optics letters, 12:377-379, 1987. Google Scholar
  25. M. Karchmer and A. Wigderson. On span programs. In Proc. of the 8th IEEE Structure in Complexity Theory, pages 102-111, 1993. URL: http://dx.doi.org/10.1109/SCT.1993.336536.
  26. I. Komargodski, M. Naor, and E. Yogev. How to share a secret, infinitely. In Procc. of TCC 2016, LNCS 9986, pages 485-514. Springer, 2016. Google Scholar
  27. I. Komargodski, M. Naor, and E. Yogev. How to share a secret, infinitely. IEEE Transactions on Information Theory, 64(6):4179-4190, June 2018. URL: http://dx.doi.org/10.1109/TIT.2017.2779121.
  28. I. Komargodski and A. Paskin-Cherniavsky. Evolving secret sharing: Dynamic thresholds and robustness. In Theory of Cryptography - 15th International Conference, TCC 2017, Baltimore, MD, USA, November 12-15, 2017, Proceedings, Part II, LNCS 10678, pages 379-393, 2017. URL: http://dx.doi.org/10.1007/978-3-319-70503-3_12.
  29. H. Krawczyk. Secret sharing made short. In Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology (CRYPTO '93), LNCS 773, pages 136-146, Berlin, Heidelberg, 1994. Springer-Verlag. URL: http://dl.acm.org/citation.cfm?id=646758.705700.
  30. T. Liu and V. Vaikuntanathan. Breaking the circuit-size barrier in secret sharing. Cryptology ePrint Archive, Report 2018/333, 2018. URL: https://eprint.iacr.org/2018/333.
  31. M. Naor and A. Shamir. Visual cryptography. In Advances in Cryptology - EUROCRYPT '94, Workshop on the Theory and Application of Cryptographic Techniques, Perugia, Italy, May 9-12, 1994, Proceedings, LNCS 950, pages 1-12, 1994. URL: http://dx.doi.org/10.1007/BFb0053419.
  32. A. Paskin-Cherniavsky. How to infinitely share a secret more efficiently. IACR Cryptology ePrint Archive, 2016:1088, 2016. Google Scholar
  33. R. Robere, T. Pitassi, Rossman B., and S. A. Cook. Exponential lower bounds for monotone span programs. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 406-415, Oct 2016. URL: http://dx.doi.org/10.1109/FOCS.2016.51.
  34. A. Shamir. How to share a secret. Commun. ACM, 22(11):612-613, 1979. Google Scholar
  35. J. G. Simmons, W. Jackson, and K. Martin. The geometry of shared secret schemes. Bulletin of the Institute of Combinatorics and its Applications, 1, 01 1991. Google Scholar
  36. C.-N. Yang. New visual secret sharing schemes using probabilistic method. Pattern Recogn. Lett., 25(4):481-494, mar 2004. URL: http://dx.doi.org/10.1016/j.patrec.2003.12.011.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact