Kybernetika 59 no. 2, 179-197, 2023

Infinite probabilistic secret sharing

Laszlo CsirmazDOI: 10.14736/kyb-2023-2-0179

Abstract:

A probabilistic secret sharing scheme is a joint probability distribution of the shares and the secret together with a collection of secret recovery functions. The study of schemes using arbitrary probability spaces and unbounded number of participants allows us to investigate their abstract properties, to connect the topic to other branches of mathematics, and to discover new design paradigms. A scheme is perfect if unqualified subsets have no information on the secret, that is, their total share is independent of the secret. By relaxing this security requirement, three other scheme types are defined. Our first result is that every (infinite) access structure can be realized by a perfect scheme where the recovery functions are non-measurable. The construction is based on a paradoxical pair of independent random variables which determine each other. Restricting the recovery functions to be measurable ones, we give a complete characterization of access structures realizable by each type of the schemes. In addition, either a vector-space or a Hilbert-space based scheme is constructed realizing the access structure. While the former one uses the traditional uniform distributions, the latter one uses Gaussian distributions, leading to a new design paradigm.

Keywords:

secret sharing, abstract probability space, Sierpiński topology, product measure, span program, Hilbert space program

Classification:

60B05, 94A62, 46C99, 54D10

References:

  1. J. Azema, M. Yor, F. Meyer and R. de la Rue: Espaces de Lebesgue. In: Séminaire de Probabilités XXVII, volume 1557 of Lecture Notes in Mathematics, pages Springer Berlin - Heidelberg 1993, pp. 15-21.   DOI:10.1007/BFb0087958
  2. A. Beimel: Secret-sharing schemes: A survey. In: IWCC (Y.-M. Chee, Z. Guo, S. Ling, F. Shao, Y. Tang, H. Wang, and Ch. Xing, eds.), volume 6639 of Lecture Notes in Computer Science, Springer 2011, pp 11-46.   CrossRef
  3. G. R. Blakley and L. Swanson: Infinite structures in information theory. In: CRYPTO 1982, pp. 39-50.   DOI:10.1080/15244118208548018
  4. J. T. Chang and D. D. Pollard: Conditioning as disintegration. Statistica Neerlandica 51 (1997), 3, 287-317.   DOI:10.1111/1467-9574.00056
  5. B. Chor and E. Kushilevitz: Secret sharing over infinite domain. J. Cryptology 6 (1993), 2, 97-86.   DOI:10.1007/BF02620137
  6. A. Dibert: Generalized Secret Sharing. Master's Thesis, Central European University, Budapest 2011.   CrossRef
  7. A. Dibert and I. Csirmaz: Infinite secret sharing - Exmples. J. Math. Cryptology 8 (2014), 2, 141-168.   DOI:10.1515/jmc-2013-0005
  8. H. G. Eggleston: Two measure properties of cartesian product sets. Quater. J. Math. Oxford 5 (1954), 108-115.   DOI:10.1093/qmath/5.1.108
  9. D. H. Fremlin: Measure Theory, Volume 2. Torres Fremlin, Colchester 2003.   CrossRef
  10. J. Haezendonck: Abstract Lebesgue-Rokhlin spaces. Bull. Soc. Math. Belgique 25 (1973), 243-258.   CrossRef
  11. S. Janson: Gaussian Hilbert Spaces. Cambridge Tracts in Mathematics. Cambridge University Press, 1997.   CrossRef
  12. O. Kallenberg: Foundations of Modern Probability. Probability and Its Applications Series. Springer, 2010.   CrossRef
  13. M. Karchmer and A. Wigderson: On span programs. In: Structure in Complexity Theory Conference 1993, pp. 102-111.   CrossRef
  14. B. H. Makar: Transfinite cryptography. Cryptologia 4 (1980), 4, 230-237.   DOI:10.1080/0161-118091855176
  15. J. Patarin: Transfinite cryptography. IJUC 8 (2012), 11-72.   CrossRef
  16. R. Phan and S. Vaudenay: On the impossibility of strong encryption over $\aleph_0$. In: Coding and Cryptology (Y. Chee, Ch. Li, S. Ling, H. Wang, and Ch. Xing, eds.), volume 5557 of Lecture Notes in Computer Science, Springer, Berlin-Heidelberg 2009, pp. 202-218.   DOI:10.1007/978-3-642-01877-0\_17
  17. V. A. Rokhlin: On the fundamental ideas of measure theory. Trans. Amer. Math. Soc. 10 (1962), 1-54.   CrossRef
  18. T. Tao: An introduction to measure theory. Amer. Math. Soc., Graduate Studies Math. 126 (2011), 206 pp.   DOI:10.1090/gsm/126
  19. S. Watson: Power of the Sierpiński space. Topology Appl. 35 (1990), 2-3, 299-302.   DOI:10.1016/0166-8641(90)90114-H