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).
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].
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].
A computational secret-sharing scheme is a method that enables a dealer, that has a secret, to distribute this secret among a set of parties such that a qualified subset of parties can efficiently reconstruct the secret while any unqualified subset of parties cannot efficiently learn anything about the secret. The collection of qualified subsets is defined by a Boolean function. It has been a major open problem to understand which (monotone) functions can be realized by a computational secret-sharing schemes. Yao suggested a method for secret-sharing for any function that has a polynomial-size monotone circuit (a class which is strictly smaller than the class of monotone functions in P). Around 1990 Rudich raised the possibility of obtaining secret-sharing for all monotone functions in NP: In order to reconstruct the secret a set of parties must be qualified and provide a witness attesting to this fact. Recently, Garg et al. (STOC 2013) put forward the concept of witness encryption, where the goal is to encrypt a message relative to a statement in for a language L in NP such that anyone holding a witness to the statement can decrypt the message, however, if x is not in L, then it is computationally hard to decrypt. Garg et al. showed how to construct several cryptographic primitives from witness encryption and gave a candidate construction. One can show that computational secret-sharing implies witness encryption for the same language. Our main result is the converse: we give a construction of a computational secret-sharing scheme for any monotone function in NP assuming witness encryption for NP and one-way functions. As a consequence we get a completeness theorem for secret-sharing: computational secret-sharing scheme for any single monotone NP-complete function implies a computational secret-sharing scheme for every monotone function in NP.
Secret-sharing schemes are a tool used in many cryptographic protocols. In these schemes, a dealer holding a secret string distributes shares to the parties such that only authorized subsets of participants can reconstruct the secret from their shares. The collection of authorized sets is called an access structure. An access structure is ideal if there is a secret-sharing scheme realizing it such that the shares are taken from the same domain as the secrets. Brickell and Davenport (Journal of Cryptology, 1991) have shown that ideal access structures are closely related to matroids. They give a necessary condition for an access structure to be ideal-the access structure must be induced by a matroid. Seymour (Journal of Combinatorial Theory B, 1992) has proved that the necessary condition is not sufficient: There exists an access structure induced by a matroid that does not have an ideal scheme. The research on access structures induced by matroids is continued in this work. The main result in this paper is strengthening the result of Seymour. It is shown that in any secret-sharing scheme realizing the access structure induced by the Vamos matroid with domain of the secrets of size k, the size of the domain of the shares is at least k + Omega(radic(k)). The second result considers nonideal secret-sharing schemes realizing access structures induced by matroids. It is proved that the fact that an access structure is induced by a matroid implies lower and upper bounds on the size of the domain of shares of subsets of participants even in nonideal schemes (as long as the shares are still relatively short). This generalized results of Brickell and Davenport for ideal schemes. Finally, an example of a nonideal access structure that is nearly ideal is presented.