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

Online secret sharing

László Csirmaz, Gábor Tardos

Published Jul 25, 2010• 0 citations
OpenAlex

Abstract

First secret sharing with infinitely many participants is looked at, showing that even the threshold cases are non trivial to achieve. We present some interesting infinite ramp shemes supporting the conjecture that all access structure can be realized by some ramp scheme. Secondly we introduce online secret sharing, where the shares should be distributed knowing only the trace of the access structure on the participants seen so far. We show that for graph based access structures the online complexity can be bounded by the graph degree, even in the infinite case.

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

SECRET SHARING ON INFINITE GRAPHS

László Csirmaz

We extend the notion of perfect secret sharing scheme for access structures with infinitely many participants. In particular we investigate cases when the participants are the vertices of an (infinite) graph, and the minimal qualified sets are the edges. The (worst case) information ratio of an access structure is the largest lower bound on the amount of information some participantmustrememberforeachbitinthesecret -- justtheinverseoftheinformationrate. Wedeterminethisvalueforseveralin honeycomb lattices; and give upper and finite graphs: lower bounds in on finite path, two-dimensional square and It is also shown that the information ratio is not necessarily the ratio local, for the i.e. triangular all nite spanned lattice. subgraphs have strictly smaller ratio than the whole graph. several open problems.

•Jan 1, 2008•3 citations

The Existence of Multi-secret Sharing Schemes Based on Random Walks on Graphs

Xiaomin Zha, Yongxuan Sang, Jiwen Zen +1 more

A multi-secret sharing scheme is the extension of a secret sharing scheme to the case in which there are many secrets need to be shared, and each secret may with different qualified subsets of participants. We study multi-secret sharing schemes based on random walks on graphs. Since many problems of secret sharing can be seen as having structure of the graphs. Different access structures corresponding to different walks for a graph with n vertices can be defined. So considering multi-secret sharing scheme based on random walks on graphs is meaningful. We prove that there exists multi-secret sharing schemes based on random walks on graphs by studying monotone span programs computing monotone Boolean function and secret sharing schemes realizing these classes of access structure.

World Congress on Software Engineering (WCSE)•Jan 1, 2009•0 citations

Finding Lower Bounds on the Complexity of Secret Sharing Schemes by Linear Programming.

Carles Padró, Leonor Vázquez, Yang An

Optimizing the maximum, or average, length of the shares in relation to the length of the secret for every given access structure is a difficult and long-standing open problem in cryptology. Most of the known lower bounds on these parameters have been obtained by implicitly or explicitly using that every secret sharing scheme defines a polymatroid related to the access structure. The best bounds that can be obtained by this combinatorial method can be determined by using linear programming, and this can be effectively done for access structures on a small number of participants. By applying this linear programming approach, we improve some of the known lower bounds for the access structures on five participants and the graph access structures on six participants for which these parameters were still undetermined. Nevertheless, the lower bounds that are obtained by this combinatorial method are not tight in general. For some access structures, they can be improved by adding to the linear program non-Shannon information inequalities as new constraints. We obtain in this way new separation results for some graph access structures on eight participants and for some ports of non-representable matroids. Finally, we prove that, for two access structures on five participants, the combinatorial lower bound cannot be attained by any linear secret sharing scheme.

•Jan 1, 2012•0 citations

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

Secret sharing schemes with bipartite access structure

G. Sáez, Carles Padró

We study the information rate of secret sharing schemes whose access structure is bipartite. In a bipartite access structure there are two classes of participants and all participants in the same class play an equivalent role in the structure. We characterize completely the bipartite access structures that can be realized by an ideal secret sharing scheme. Both upper and lower bounds on the optimal information rate of bipartite access structures are given. These results are applied to the particular case of weighted threshold access structure with two weights.

IEEE Transactions on Information Theory•Jan 1, 2000•118 citations
First secret sharing with infinitely many participants is looked at, showing that even the threshold cases are non trivial to achieve. We present some interesting infinite ramp shemes supporting the conjecture that all access structure can be realized by some ramp scheme.
Secondly we introduce online secret sharing, where the shares should be distributed knowing only the trace of the access structure on the participants seen so far. We show that for graph based access structures the online complexity can be bounded by the graph degree, even in the infinite case.
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.
We extend the notion of perfect secret sharing scheme for access structures with infinitely many participants. In particular we investigate cases when the participants are the vertices of an (infinite) graph, and the minimal qualified sets are the edges. The (worst case) information ratio of an access structure is the largest lower bound on the amount of information some participantmustrememberforeachbitinthesecret -- justtheinverseoftheinformationrate. Wedeterminethisvalueforseveralin honeycomb lattices; and give upper and finite graphs: lower bounds in on finite path, two-dimensional square and It is also shown that the information ratio is not necessarily the ratio local, for the i.e. triangular all nite spanned lattice. subgraphs have strictly smaller ratio than the whole graph. several open problems.
A multi-secret sharing scheme is the extension of a secret sharing scheme to the case in which there are many secrets need to be shared, and each secret may with different qualified subsets of participants. We study multi-secret sharing schemes based on random walks on graphs. Since many problems of secret sharing can be seen as having structure of the graphs. Different access structures corresponding to different walks for a graph with n vertices can be defined. So considering multi-secret sharing scheme based on random walks on graphs is meaningful. We prove that there exists multi-secret sharing schemes based on random walks on graphs by studying monotone span programs computing monotone Boolean function and secret sharing schemes realizing these classes of access structure.
Optimizing the maximum, or average, length of the shares in relation to the length of the secret for every given access structure is a difficult and long-standing open problem in cryptology. Most of the known lower bounds on these parameters have been obtained by implicitly or explicitly using that every secret sharing scheme defines a polymatroid related to the access structure. The best bounds that can be obtained by this combinatorial method can be determined by using linear programming, and this can be effectively done for access structures on a small number of participants. By applying this linear programming approach, we improve some of the known lower bounds for the access structures on five participants and the graph access structures on six participants for which these parameters were still undetermined. Nevertheless, the lower bounds that are obtained by this combinatorial method are not tight in general. For some access structures, they can be improved by adding to the linear program non-Shannon information inequalities as new constraints. We obtain in this way new separation results for some graph access structures on eight participants and for some ports of non-representable matroids. Finally, we prove that, for two access structures on five participants, the combinatorial lower bound cannot be attained by any linear secret sharing scheme.
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.
We study the information rate of secret sharing schemes whose access structure is bipartite. In a bipartite access structure there are two classes of participants and all participants in the same class play an equivalent role in the structure. We characterize completely the bipartite access structures that can be realized by an ideal secret sharing scheme. Both upper and lower bounds on the optimal information rate of bipartite access structures are given. These results are applied to the particular case of weighted threshold access structure with two weights.