Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Probabilistic Infinite Secret Sharing

László Csirmaz

Published Oct 1, 2013• 3 citations
OpenAlex

Abstract

The study of probabilistic secret sharing schemes using arbitrary probability spaces and possibly infinite number of participants lets us investigate abstract properties of such schemes. It highlights important properties, explains why certain definitions work better than others, connects this topic to other branches of mathematics, and might yield new design paradigms. A probabilistic secret sharing scheme is a joint probability distribution of the shares and the secret together with a collection of secret recovery functions for qualified subsets. The scheme is measurable if the recovery functions are measurable. Depending on how much information an unqualified subset might have, we define four scheme types: perfect, almost perfect, ramp, and almost ramp. Our main results characterize the access structures which can be realized by schemes of these types. We show that every access structure can be realized by a non-measurable perfect probabilistic scheme. The construction is based on a paradoxical pair of independent random variables which determine each other. For measurable schemes we have the following complete characterization. An access structure can be realized by a (measurable) perfect, or almost perfect scheme if and only if the access structure, as a subset of the Sierpiński space {0, 1} P, is open, if and only if it can be realized by a span program. The access structure can be realized by a (measurable) ramp or almost ramp scheme if and only if the access structure is a Gδ set (intersection of countably many open sets) in the Sierpiński topology, if and only if it can be realized by a Hilbert-space program.

Related papers

Infinite probabilistic secret sharing

László Csirmaz

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.

arXiv:1310.7423•Kybernetika•May 28, 2023•0 citations

Infinite secret sharing – Examples

Alexander Dibert, László Csirmaz

Abstract. The motivation for extending secret sharing schemes to cases when either the set of players is infinite or the domain from which the secret and/or the shares are drawn is infinite or both, is similar to the case when switching to abstract probability spaces from classical combinatorial probability. It might shed new light on old problems, could connect seemingly unrelated problems, and unify diverse phenomena. Definitions equivalent in the finitary case could be very much different when switching to infinity, signifying their difference. The standard requirement that qualified subsets should be able to determine the secret has different interpretations in spite of the fact that, by assumption, all participants have infinite computing power. The requirement that unqualified subsets should have no or limited information on the secret suggests that we also need some probability distribution. In the infinite case events with zero probability are not necessarily impossible, and we should decide whether bad events with zero probability are allowed or not. In this paper, rather than giving precise definitions, we enlist an abundance of hopefully interesting infinite secret sharing schemes. These schemes touch quite diverse areas of mathematics such as projective geometry, stochastic processes and Hilbert spaces. Nevertheless our main tools are from probability theory. The examples discussed here serve as foundation and illustration to the more theory oriented companion paper [arXiv:1310.7423].

arXiv:1310.7418•Journal of Mathematical Cryptology•Mar 5, 2014•0 citations

Generalized secret sharing

Alexander Dibert

In this thesis we discussed secret haring for infinite secret domains. The first part of the thesis is devoted to the result by Chor and Kushilevitz. We proved an impossibility of secret haring over countable set of secrets and shares. Our result is slightly more general the the one by Chor and Kushilevitz. Also we gave several counterexamples which show an importance of assumptions in our theorem. Later we discussed possible definition of secret sharing over continuum set of secrets. Particularly, using the idea by Gabor Tardos, we constructed a scheme that shows that the definition by Chor and Kushilevitz is ”intuitively incorrect”. Namely, it is possible that an unqualified set of players can reconstruct the secret. We suggested a modified definition and showed that the positive result by Chor and Kushilevitz holds for the new definition. Finally we gave an introduction to Lebesgue-Rokhlin probability spaces and showed that a secret from such spaces can be shared. We suggest a further research in this direction. It seems that the converse is true. Namely, if a secret sharing scheme exists for a secret picked up from a probability space, then this space is Lebesgue-Rokhlin. As a short digression we presented a nice scheme for the situation when a secret is a branch of a binary tree(possible infinite). This scheme seems to be useful as it allows to compute several primitives on a secret without any communication between participants. In the last part of the thesis we presented our concept of perfect uniform non-probabilistic secret sharing, in which we avoid the idea of probability and concentrate on cardinalities. We showed that there exists a perfect uniform non-probabilistic secret sharing scheme for any secret domain and any access structure(possibly infinite).

•Jan 1, 2011•3 citations

Infinite Secret Sharing – Examples ∗

Alexander Dibert, Csirmaz László

The motivation for extending secret sharing schemes to cases when either the set of players is infinite or the domain from which the secret and/or the shares are drawn is infinite or both, is similar to the case when switching to abstract probability spaces from classical combinatorial probability. It might shed new light on old problems, could connect seemingly unrelated problems, and unify diverse phenomena. Definitions equivalent in the finitary case could be very much different when switching to infinity, signifying their difference. The standard requirement that qualified subsets should be able to determine the secret has different interpretations in spite of the fact that, by assumption, all participants have infinite computing power. The requirement that unqualified subsets should have no or limited information on the secret suggests that we also need some probability distribution. In the infinite case events with zero probability are not necessarily impossible, and we should decide whether bad events with zero probability are allowed or not. In this paper, rather than giving precise definitions, we enlist an abundance of hopefully interesting infinite secret sharing schemes. These schemes touch quite diverse areas of mathematics such as projective geometry, stochastic processes and Hilbert spaces. Nevertheless our main tools are from probability theory. The examples discussed here serve as foundation and illustration to the more theory oriented companion paper [arXiv:1310.7423].

•Jan 22, 2013•6 citations

A Study On The Average Information Ratio Of Perfect Secret-Sharing Schemes For Access Structures Based On Bipartite Graphs

Hui-Chuan Lu

A perfect secret-sharing scheme is a method to distribute a secret among a set of participants in such a way that only qualified subsets of participants can recover the secret and the joint share of participants in any unqualified subset is statistically independent of the secret. The collection of all qualified subsets is called the access structure of the perfect secret-sharing scheme. In a graph-based access structure, each vertex of a graph G represents a participant and each edge of G represents a minimal qualified subset. The average information ratio of a perfect secret-sharing scheme realizing the access structure based on G is defined as AR = (Pv2V (G) H(v))/(|V (G)|H(s)), where s is the secret and v is the share of v, both are random variables from and H is the Shannon entropy. The infimum of the average information ratio of all possible perfect secret-sharing schemes realizing a given access structure is called the optimal average information ratio of that access structure. Most known results about the optimal average information ratio give upper bounds or lower bounds on it. In this present structures based on bipartite graphs and determine the exact values of the optimal average information ratio of some infinite classes of them.

•Sep 29, 2012•1 citation

ON THE DEALER'S RANDOMNESS REQUIRED IN PERFECT SECRET SHARING SCHEMES WITH ACCESS STRUCTURES OF CONSTANT RANK

Hung–Min Sun

A secret sharing scheme is a method which allows a dealer to share a secret among a set of participants in such a way that only qualified subsets of participants can recover the secret. The collection of subsets of participants that can reconstruct the secret in this way is called access structure. The rank of an access structure is the maximum cardinality of a minimal qualified subset. A secret sharing scheme is perfect if unqualified subsets of participants obtain no information regarding the secret. The dealer's randomness is the number of random bits required by the dealer to setup a secret sharing scheme. The efficiency of the dealer's randomness is the ratio between the amount of the dealer's randomness and the length of the secret. Because random bits are a natural computational resource, it is important to reduce the amount of randomness used by the dealer to setup a secret sharing scheme. In this paper, we propose some decomposition constructions for perfect secret sharing schemes with access structures of constant rank. Compared with the best previous results, our constructions have some improved upper bounds on the dealer's randomness and on the efficiency of the dealer's randomness.

International Journal of Foundations of Computer Science•Jun 1, 2000•0 citations
The study of probabilistic secret sharing schemes using arbitrary probability spaces and possibly infinite number of participants lets us investigate abstract properties of such schemes. It highlights important properties, explains why certain definitions work better than others, connects this topic to other branches of mathematics, and might yield new design paradigms. A probabilistic secret sharing scheme is a joint probability distribution of the shares and the secret together with a collection of secret recovery functions for qualified subsets. The scheme is measurable if the recovery functions are measurable. Depending on how much information an unqualified subset might have, we define four scheme types: perfect, almost perfect, ramp, and almost ramp. Our main results characterize the access structures which can be realized by schemes of these types. We show that every access structure can be realized by a non-measurable perfect probabilistic scheme. The construction is based on a paradoxical pair of independent random variables which determine each other. For measurable schemes we have the following complete characterization. An access structure can be realized by a (measurable) perfect, or almost perfect scheme if and only if the access structure, as a subset of the Sierpiński space {0, 1} P, is open, if and only if it can be realized by a span program. The access structure can be realized by a (measurable) ramp or almost ramp scheme if and only if the access structure is a Gδ set (intersection of countably many open sets) in the Sierpiński topology, if and only if it can be realized by a Hilbert-space program.
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.
Abstract. The motivation for extending secret sharing schemes to cases when either the set of players is infinite or the domain from which the secret and/or the shares are drawn is infinite or both, is similar to the case when switching to abstract probability spaces from classical combinatorial probability. It might shed new light on old problems, could connect seemingly unrelated problems, and unify diverse phenomena. Definitions equivalent in the finitary case could be very much different when switching to infinity, signifying their difference. The standard requirement that qualified subsets should be able to determine the secret has different interpretations in spite of the fact that, by assumption, all participants have infinite computing power. The requirement that unqualified subsets should have no or limited information on the secret suggests that we also need some probability distribution. In the infinite case events with zero probability are not necessarily impossible, and we should decide whether bad events with zero probability are allowed or not. In this paper, rather than giving precise definitions, we enlist an abundance of hopefully interesting infinite secret sharing schemes. These schemes touch quite diverse areas of mathematics such as projective geometry, stochastic processes and Hilbert spaces. Nevertheless our main tools are from probability theory. The examples discussed here serve as foundation and illustration to the more theory oriented companion paper [arXiv:1310.7423].
In this thesis we discussed secret haring for infinite secret domains. The first part of the thesis is devoted to the result by Chor and Kushilevitz. We proved an impossibility of secret haring over countable set of secrets and shares. Our result is slightly more general the the one by Chor and Kushilevitz. Also we gave several counterexamples which show an importance of assumptions in our theorem. Later we discussed possible definition of secret sharing over continuum set of secrets. Particularly, using the idea by Gabor Tardos, we constructed a scheme that shows that the definition by Chor and Kushilevitz is ”intuitively incorrect”. Namely, it is possible that an unqualified set of players can reconstruct the secret. We suggested a modified definition and showed that the positive result by Chor and Kushilevitz holds for the new definition. Finally we gave an introduction to Lebesgue-Rokhlin probability spaces and showed that a secret from such spaces can be shared. We suggest a further research in this direction. It seems that the converse is true. Namely, if a secret sharing scheme exists for a secret picked up from a probability space, then this space is Lebesgue-Rokhlin. As a short digression we presented a nice scheme for the situation when a secret is a branch of a binary tree(possible infinite). This scheme seems to be useful as it allows to compute several primitives on a secret without any communication between participants. In the last part of the thesis we presented our concept of perfect uniform non-probabilistic secret sharing, in which we avoid the idea of probability and concentrate on cardinalities. We showed that there exists a perfect uniform non-probabilistic secret sharing scheme for any secret domain and any access structure(possibly infinite).
The motivation for extending secret sharing schemes to cases when either the set of players is infinite or the domain from which the secret and/or the shares are drawn is infinite or both, is similar to the case when switching to abstract probability spaces from classical combinatorial probability. It might shed new light on old problems, could connect seemingly unrelated problems, and unify diverse phenomena. Definitions equivalent in the finitary case could be very much different when switching to infinity, signifying their difference. The standard requirement that qualified subsets should be able to determine the secret has different interpretations in spite of the fact that, by assumption, all participants have infinite computing power. The requirement that unqualified subsets should have no or limited information on the secret suggests that we also need some probability distribution. In the infinite case events with zero probability are not necessarily impossible, and we should decide whether bad events with zero probability are allowed or not. In this paper, rather than giving precise definitions, we enlist an abundance of hopefully interesting infinite secret sharing schemes. These schemes touch quite diverse areas of mathematics such as projective geometry, stochastic processes and Hilbert spaces. Nevertheless our main tools are from probability theory. The examples discussed here serve as foundation and illustration to the more theory oriented companion paper [arXiv:1310.7423].
A perfect secret-sharing scheme is a method to distribute a secret among a set of participants in such a way that only qualified subsets of participants can recover the secret and the joint share of participants in any unqualified subset is statistically independent of the secret. The collection of all qualified subsets is called the access structure of the perfect secret-sharing scheme. In a graph-based access structure, each vertex of a graph G represents a participant and each edge of G represents a minimal qualified subset. The average information ratio of a perfect secret-sharing scheme realizing the access structure based on G is defined as AR = (Pv2V (G) H(v))/(|V (G)|H(s)), where s is the secret and v is the share of v, both are random variables from and H is the Shannon entropy. The infimum of the average information ratio of all possible perfect secret-sharing schemes realizing a given access structure is called the optimal average information ratio of that access structure. Most known results about the optimal average information ratio give upper bounds or lower bounds on it. In this present structures based on bipartite graphs and determine the exact values of the optimal average information ratio of some infinite classes of them.
A secret sharing scheme is a method which allows a dealer to share a secret among a set of participants in such a way that only qualified subsets of participants can recover the secret. The collection of subsets of participants that can reconstruct the secret in this way is called access structure. The rank of an access structure is the maximum cardinality of a minimal qualified subset. A secret sharing scheme is perfect if unqualified subsets of participants obtain no information regarding the secret. The dealer's randomness is the number of random bits required by the dealer to setup a secret sharing scheme. The efficiency of the dealer's randomness is the ratio between the amount of the dealer's randomness and the length of the secret. Because random bits are a natural computational resource, it is important to reduce the amount of randomness used by the dealer to setup a secret sharing scheme. In this paper, we propose some decomposition constructions for perfect secret sharing schemes with access structures of constant rank. Compared with the best previous results, our constructions have some improved upper bounds on the dealer's randomness and on the efficiency of the dealer's randomness.