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

World Congress on Software Engineering (WCSE)

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

Xiaomin Zha, Yongxuan Sang, Jiwen Zen, Jun Xu

Published Jan 1, 2009• 0 citations
Publisher

Abstract

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.

DOI
10.1109/wcse.2009.294

Related papers

Randomness in Multi-Secret Sharing Schemes.

Carlo Blundo, Barbara Masucci

: A multi--secret sharing scheme is a protocol to share a number of (arbitrarily related) secrets among a set of participants in such a way that only qualified sets of participants can recover the secrets, whereas non-qualified sets of participants might have partial information about them. In this paper we analyze the amount of randomness needed by multi--secret sharing schemes. Given an m-tuple of access structures, we give a lower bound on the number of random bits needed by multi--secret sharing schemes; the lower bound is expressed in terms of a combinatorial parameter that depends only upon the access structures and not on the particular multi--secret sharing scheme used. Key Words: Data Security, Cryptography, Randomness, Secret Sharing Schemes. Category: E.3 1 Introduction There are many situations in cryptography in which it is important to be able to generate random numbers, random bit strings, etc. For example, cryptographic keys are to be generated at random from a speci...

JUCS - Journal of Universal Computer Science•Jan 1, 1999•7 citations

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

Linear Secret-Sharing Schemes for Forbidden Graph Access Structures

Amos Beimel, Oriol Farràs, Yuval Mintz +1 more

A secret-sharing scheme realizes the forbidden graph access structure determined by a graph$G=(V,E)$if the parties are the vertices of the graph and the subsets that can reconstruct the secret are the pairs of vertices in$E$(i.e., the edges) and the subsets of at least three vertices. Secret-sharing schemes for forbidden graph access structures defined by bipartite graphs are equivalent to conditional disclosure of secrets (CDS) protocols. We study the complexity of realizing a forbidden graph access structure by linear secret-sharing schemes, which are schemes in which the secret can be reconstructed from the shares by a linear mapping. We provide efficient constructions and lower bounds on the share size of linear secret-sharing schemes for sparse and very dense graphs, closing the gap between upper and lower bounds. Given a sparse (resp. very dense) graph with$n$vertices and at most$n^{1+\beta }$edges (resp. at least$\binom {n}{2} - n^{1+\beta }$edges), for some$0 \leq \beta < 1$, we construct a linear secret-sharing scheme realizing its forbidden graph access structure with total share size$\tilde {O} (n^{1+\beta /2})$. Furthermore, we construct linear secret-sharing schemes realizing these access structures in which the size of each share is$\tilde {O} (n^{1/4+\beta /4})$. We also provide constructions achieving different trade-offs between the size of each share and the total share size. We prove that almost all forbidden graph access structures require linear secret-sharing schemes with total share size$\Omega (n^{3/2})$; this shows that the construction of Gay, Kerenidis, and Wee [CRYPTO 2015] is optimal. Furthermore, we show that for every$0 \leq \beta < 1$there exist a graph with at most$n^{1+\beta }$edges and a graph with at least$\binom {n}{2}-n^{1+\beta }$edges such that the total share size in any linear secret-sharing scheme realizing the associated forbidden graph access structures is$\Omega (n^{1+\beta /2})$. Finally, we show that for every$0 \leq \beta < 1$there exist a graph with at most$n^{1+\beta }$edges and a graph with at least$\binom {n}{2}-n^{1+\beta }$edges such that the size of the share of at least one party in any linear secret-sharing scheme realizing these forbidden graph access structures is$\Omega (n^{1/4+\beta /4})$. This shows that our constructions are optimal (up to poly-logarithmic factors).

IEEE Transactions on Information Theory•Dec 6, 2021•7 citations

Access structure in graphs in high dimension and application to secret sharing

Anne Marin, Damian Markham, Simon Perdrix

We give graphical characterisation of the access structure to both classical and quantum information encoded onto a multigraph defined for prime dimension $q$, as well as explicit decoding operations for quantum secret sharing based on graph state protocols. We give a lower bound on $k$ for the existence of a $((k,n))_q$ scheme and prove, using probabilistic methods, that there exists $α$ such that a random multigraph has an accessing parameter $k\leq αn$ with high probability.

arXiv:1304.7105•Apr 26, 2013•8 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•4 citations

Ideal and perfect multi-secret sharing schemes whose access structure are Q 3

Lv yingli, Xiaojun Xu, Zhang Xiao-feng +1 more

The characterization of access structure is one of the main open problems in secret sharing schemes. We are particularly interested in determining which Q 3 access structures can be realized and the requirement should be achieved even in the presence of an adversary who is able to corrupt some players in an ideal secret sharing scheme. The problems are studied in our paper. Above all, we present a concrete scheme that can meet all above requirements. In our scheme, it is not only a dynamic multi-secret and multi-use sharing protocol, but participants from access structure can recover the secret using their shares, while the same number of participants from adversary structure can't recover the secret using their shares, which is different from general access structure schemes. Moreover, in the whole dynamic process, the coefficients of polynomial and private secret shares always stay the same. Therefore, it enjoys high practical value.

•Aug 1, 2012•0 citations
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.
: A multi--secret sharing scheme is a protocol to share a number of (arbitrarily related) secrets among a set of participants in such a way that only qualified sets of participants can recover the secrets, whereas non-qualified sets of participants might have partial information about them. In this paper we analyze the amount of randomness needed by multi--secret sharing schemes. Given an m-tuple of access structures, we give a lower bound on the number of random bits needed by multi--secret sharing schemes; the lower bound is expressed in terms of a combinatorial parameter that depends only upon the access structures and not on the particular multi--secret sharing scheme used. Key Words: Data Security, Cryptography, Randomness, Secret Sharing Schemes. Category: E.3 1 Introduction There are many situations in cryptography in which it is important to be able to generate random numbers, random bit strings, etc. For example, cryptographic keys are to be generated at random from a speci...
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 secret-sharing scheme realizes the forbidden graph access structure determined by a graphG=(V,E)G=(V,E)G=(V,E)if the parties are the vertices of the graph and the subsets that can reconstruct the secret are the pairs of vertices inEEE(i.e., the edges) and the subsets of at least three vertices. Secret-sharing schemes for forbidden graph access structures defined by bipartite graphs are equivalent to conditional disclosure of secrets (CDS) protocols. We study the complexity of realizing a forbidden graph access structure by linear secret-sharing schemes, which are schemes in which the secret can be reconstructed from the shares by a linear mapping. We provide efficient constructions and lower bounds on the share size of linear secret-sharing schemes for sparse and very dense graphs, closing the gap between upper and lower bounds. Given a sparse (resp. very dense) graph withnnnvertices and at mostn1+βn^{1+\beta }n1+βedges (resp. at least(n2)−n1+β\binom {n}{2} - n^{1+\beta }(2n​)−n1+βedges), for some0≤β<10 \leq \beta < 10≤β<1, we construct a linear secret-sharing scheme realizing its forbidden graph access structure with total share sizeO~(n1+β/2)\tilde {O} (n^{1+\beta /2})O~(n1+β/2). Furthermore, we construct linear secret-sharing schemes realizing these access structures in which the size of each share isO~(n1/4+β/4)\tilde {O} (n^{1/4+\beta /4})O~(n1/4+β/4). We also provide constructions achieving different trade-offs between the size of each share and the total share size. We prove that almost all forbidden graph access structures require linear secret-sharing schemes with total share sizeΩ(n3/2)\Omega (n^{3/2})Ω(n3/2); this shows that the construction of Gay, Kerenidis, and Wee [CRYPTO 2015] is optimal. Furthermore, we show that for every0≤β<10 \leq \beta < 10≤β<1there exist a graph with at mostn1+βn^{1+\beta }n1+βedges and a graph with at least(n2)−n1+β\binom {n}{2}-n^{1+\beta }(2n​)−n1+βedges such that the total share size in any linear secret-sharing scheme realizing the associated forbidden graph access structures isΩ(n1+β/2)\Omega (n^{1+\beta /2})Ω(n1+β/2). Finally, we show that for every0≤β<10 \leq \beta < 10≤β<1there exist a graph with at mostn1+βn^{1+\beta }n1+βedges and a graph with at least(n2)−n1+β\binom {n}{2}-n^{1+\beta }(2n​)−n1+βedges such that the size of the share of at least one party in any linear secret-sharing scheme realizing these forbidden graph access structures isΩ(n1/4+β/4)\Omega (n^{1/4+\beta /4})Ω(n1/4+β/4). This shows that our constructions are optimal (up to poly-logarithmic factors).
We give graphical characterisation of the access structure to both classical and quantum information encoded onto a multigraph defined for prime dimension qqq, as well as explicit decoding operations for quantum secret sharing based on graph state protocols. We give a lower bound on kkk for the existence of a ((k,n))q((k,n))_q((k,n))q​ scheme and prove, using probabilistic methods, that there exists ααα such that a random multigraph has an accessing parameter k≤αnk\leq αnk≤αn with high probability.
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.
The characterization of access structure is one of the main open problems in secret sharing schemes. We are particularly interested in determining which Q 3 access structures can be realized and the requirement should be achieved even in the presence of an adversary who is able to corrupt some players in an ideal secret sharing scheme. The problems are studied in our paper. Above all, we present a concrete scheme that can meet all above requirements. In our scheme, it is not only a dynamic multi-secret and multi-use sharing protocol, but participants from access structure can recover the secret using their shares, while the same number of participants from adversary structure can't recover the secret using their shares, which is different from general access structure schemes. Moreover, in the whole dynamic process, the coefficients of polynomial and private secret shares always stay the same. Therefore, it enjoys high practical value.