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

International Journal of Foundations of Computer Science

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

Hung–Min Sun

Published Jun 1, 2000• 0 citations
Publisher

Abstract

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.

DOI
10.1142/s0129054100000168

Related papers

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

A New Bound on the Average Information Ratio of Perfect Secret-Sharing Schemes for Access Structures Based on Bipartite Graphs of Larger Girth

Hui-Chuan Lu

In a perfect secret-sharing scheme, a dealer distributes 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 the participants in any unqualified subset is statistically independent of the secret. The access structure of the scheme refers to the collection of all qualified subsets. In a graph-based access structures, 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 a given access structure is the ratio of the average length of the shares given to the participants to the length of the secret. The infimum of the average information ratio of all possible perfect secret-sharing schemes realizing an access structure is called the optimal average information ratio of that access structure. We study the optimal average information ratio of the access structures based on bipartite graphs. Based on some previous results, we give a bound on the optimal average information ratio for all bipartite graphs of girth at least six. This bound is the best possible for some classes of bipartite graphs using our approach.

•Jul 5, 2014•0 citations

Not all perfect extrinsic secret sharing schemes are ideal.

W. D. Wallis

Abstract. We construct a perfect extrinsic secret sharing scheme for any case in which a set of participants can gain access to the secret if and only if the set contains a pair of members from some given list of pairs. A secret sharing scheme is a way by which a dealer rnay distribute secret information to individuals (call participants). There is associated '-<U.lh'.lcH"""F- of subsets of a set of can if they constitute a member of the access structure. usual to demand that the access structure be monotone: If A contains a subset which to the structure, then A itself must also belong to the structure. A secret scheme is called perfect if a set of pa.rticipants can no information by their shares unless the set is member of the access structure. An structure is called extrinsic if each participant '8 share contains the same amount of information. Simmons [4] has pointed out the desirability of a scheme which is and the access structure of which extrinsic. Observe

Australas. J Comb.•Jan 1, 1990•0 citations

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•8 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 From Correlated Random Variables and Rate-Limited Public Communication

Rumia Sultana, Rémi A. Chou

A dealer aims to share a secret with participants so that only predefined subsets can reconstruct it, while others learn nothing. The dealer and participants access correlated randomness and communicate over a one-way, public, rate-limited channel. For this problem, we propose the first explicit coding scheme able to handle arbitrary access structures and achieve the best known achievable rates, previously obtained non-constructively. Our construction relies on lossy source coding coupled with distribution approximation to handle the reliability constraints, followed by universal hashing to handle the security constraints. We stress that our coding scheme does not require symmetry or degradation assumptions on the correlated random variables, and does not need a pre-shared secret among the participants and dealer. As a by-product, our construction also yields explicit coding schemes for secret-key generation under one-way, rate-limited public communication that, unlike prior work, achieves the capacity for arbitrary source correlations and do not require a pre-shared secret to ensure strong secrecy.

arXiv:2505.04076•IEEE Transactions on Information Forensics and Security•Jan 1, 2026•2 citations
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.
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.
In a perfect secret-sharing scheme, a dealer distributes 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 the participants in any unqualified subset is statistically independent of the secret. The access structure of the scheme refers to the collection of all qualified subsets. In a graph-based access structures, 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 a given access structure is the ratio of the average length of the shares given to the participants to the length of the secret. The infimum of the average information ratio of all possible perfect secret-sharing schemes realizing an access structure is called the optimal average information ratio of that access structure. We study the optimal average information ratio of the access structures based on bipartite graphs. Based on some previous results, we give a bound on the optimal average information ratio for all bipartite graphs of girth at least six. This bound is the best possible for some classes of bipartite graphs using our approach.
Abstract. We construct a perfect extrinsic secret sharing scheme for any case in which a set of participants can gain access to the secret if and only if the set contains a pair of members from some given list of pairs. A secret sharing scheme is a way by which a dealer rnay distribute secret information to individuals (call participants). There is associated '-<U.lh'.lcH"""F- of subsets of a set of can if they constitute a member of the access structure. usual to demand that the access structure be monotone: If A contains a subset which to the structure, then A itself must also belong to the structure. A secret scheme is called perfect if a set of pa.rticipants can no information by their shares unless the set is member of the access structure. An structure is called extrinsic if each participant '8 share contains the same amount of information. Simmons [4] has pointed out the desirability of a scheme which is and the access structure of which extrinsic. Observe
: 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...
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.
A dealer aims to share a secret with participants so that only predefined subsets can reconstruct it, while others learn nothing. The dealer and participants access correlated randomness and communicate over a one-way, public, rate-limited channel. For this problem, we propose the first explicit coding scheme able to handle arbitrary access structures and achieve the best known achievable rates, previously obtained non-constructively. Our construction relies on lossy source coding coupled with distribution approximation to handle the reliability constraints, followed by universal hashing to handle the security constraints. We stress that our coding scheme does not require symmetry or degradation assumptions on the correlated random variables, and does not need a pre-shared secret among the participants and dealer. As a by-product, our construction also yields explicit coding schemes for secret-key generation under one-way, rate-limited public communication that, unlike prior work, achieves the capacity for arbitrary source correlations and do not require a pre-shared secret to ensure strong secrecy.