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

arXiv:1310.7423 · Kybernetika

Infinite probabilistic secret sharing

László Csirmaz

Published May 28, 2023• 0 citations
arXivHTMLPDF

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.

DOI
10.14736/kyb-2023-2-0179

Related papers

Probabilistic Infinite Secret Sharing

László Csirmaz

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.

•Oct 1, 2013•3 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, 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•6 citations

On quantum evolving schemes

Shion Samadder Chaudhury

A quantum secret sharing scheme is a method to share a quantum secret among participants in such a way that only certain specified subsets of the set of participants can combine to recover the secret. A quantum evolving secret sharing scheme is a recently introduced variant of secret sharing schemes where the sets of participants is not fixed and an unbounded and unspecified number of participants arrive one by one with time. The number of participants can be potentially infinite and and a quantum secret is shared and protected among the participants. The existing construction has some major drawbacks such as 1) the exponential quantum memory requirement and 2) the very high dimensions of the shares which makes the scheme difficult to implement. In this paper we overcome these drawbacks by constructing a scheme which uses quantum memory linear in the number of participants and significantly improves on the dimensions of the shares of the participants. This construction uses quantum secret redistribution and trap codes. The construction is flexible and can be modified to different types of access structures(subsets of participants which can recover the secret). Certain ramp properties can also be incorporated in the scheme.

Quantum Information and Computation•Apr 1, 2022•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

Lossy Chains and Fractional Secret Sharing.

Yuval Ishai, Eyal Kushilevitz, Omer Strulovich

Motivated by the goal of controlling the amount of work required to access a shared resource or to solve a cryptographic puzzle, we introduce and study the related notions of lossy chains and fractional secret sharing. Fractional secret sharing generalizes traditional secret sharing by allowing a finegrained control over the amount of uncertainty about the secret. More concretely, a fractional secret sharing scheme realizes a fractional access structure f: 2 [n] → [m] by guaranteeing that from the point of view of each set T ⊆ [n] of parties, the secret is uniformly distributed over a set of f(T) potential secrets. We show that every (monotone) fractional access structure can be realized. For symmetric structures, in which f(T) depends only on the size of T, we give an efficient construction with share size poly(n, log m). Our construction of fractional secret sharing schemes is based on the new notion of lossy chains which may be of independent interest. A lossy chain is a Markov chain (X0,..., Xn) which starts with a random secret X0 and gradually loses information about it at a rate which is specified by a loss function g. Concretely, in every step t, the distribution of X0 conditioned on the value of Xt should always be uniformly distributed over a set of size g(t). We show how to construct such lossy chains efficiently for any possible loss function g, and prove that our construction achieves an optimal asymptotic information rate. 1

•Jan 1, 2013•0 citations
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.
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.
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).
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].
A quantum secret sharing scheme is a method to share a quantum secret among participants in such a way that only certain specified subsets of the set of participants can combine to recover the secret. A quantum evolving secret sharing scheme is a recently introduced variant of secret sharing schemes where the sets of participants is not fixed and an unbounded and unspecified number of participants arrive one by one with time. The number of participants can be potentially infinite and and a quantum secret is shared and protected among the participants. The existing construction has some major drawbacks such as 1) the exponential quantum memory requirement and 2) the very high dimensions of the shares which makes the scheme difficult to implement. In this paper we overcome these drawbacks by constructing a scheme which uses quantum memory linear in the number of participants and significantly improves on the dimensions of the shares of the participants. This construction uses quantum secret redistribution and trap codes. The construction is flexible and can be modified to different types of access structures(subsets of participants which can recover the secret). Certain ramp properties can also be incorporated in the scheme.
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.
Motivated by the goal of controlling the amount of work required to access a shared resource or to solve a cryptographic puzzle, we introduce and study the related notions of lossy chains and fractional secret sharing. Fractional secret sharing generalizes traditional secret sharing by allowing a finegrained control over the amount of uncertainty about the secret. More concretely, a fractional secret sharing scheme realizes a fractional access structure f: 2 [n] → [m] by guaranteeing that from the point of view of each set T ⊆ [n] of parties, the secret is uniformly distributed over a set of f(T) potential secrets. We show that every (monotone) fractional access structure can be realized. For symmetric structures, in which f(T) depends only on the size of T, we give an efficient construction with share size poly(n, log m). Our construction of fractional secret sharing schemes is based on the new notion of lossy chains which may be of independent interest. A lossy chain is a Markov chain (X0,..., Xn) which starts with a random secret X0 and gradually loses information about it at a rate which is specified by a loss function g. Concretely, in every step t, the distribution of X0 conditioned on the value of Xt should always be uniformly distributed over a set of size g(t). We show how to construct such lossy chains efficiently for any possible loss function g, and prove that our construction achieves an optimal asymptotic information rate. 1