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

IEEE Transactions on Information Theory

Partial Secret Sharing Schemes

Amir Jafari, Shahram Khazaei

Published Apr 6, 2023• 9 citations
Publisher

Abstract

The following standard relaxations of perfect security for secret sharing schemes (SSSs) exist in the literature:quasi-perfect,almost-perfect, andstatistical. Understanding the power of these relaxations on the efficiency of SSSs, measured via a parameter calledinformation ratio, is a long-standing open problem. In this article, we introduce and study an extremely relaxed security notion, calledpartial security, for which it is only required that any qualified set gains strictly more information about the secret than any unqualified one. To get a meaningful efficiency measure, we normalize the (standard) information ratio of such schemes by an appropriate parameter and refer to the new measure aspartial information ratio. We present three main results in this paper.First, we prove that partial and perfect information ratios coincide for the class of linear SSSs.Second, we prove that for the general (i.e., non-linear) class of SSSs, partial and statistical information ratios are equal.Third, we show that partial and almost-perfect information ratios do not coincide for the class of mixed-linear schemes (i.e., schemes constructed by combining linear schemes with different underlying finite fields). We also use the notion of partial secret sharing to strengthen and unify the previousdecompositiontheorems for constructing SSSs.

DOI
10.1109/tit.2023.3265093

Related papers

Secret sharing schemes based on min-entropies

Mitsugu Iwamoto, Junji Shikata

Fundamental results on secret sharing schemes (SSSs) are discussed in the setting where security and share size are measured by (conditional) min-entropies. We first formalize a unified framework of SSSs based on (conditional) Rέnyi entropies, which includes SSSs based on Shannon and min entropies etc. as special cases. By deriving the lower bound of share sizes in terms of Rέnyi entropies based on the technique introduced by Iwamoto-Shikata, we obtain the lower bounds of share sizes measured by min entropies as well as by Shannon entropies in a unified manner. As the main contributions of this paper, we show two existential results of non-perfect SSSs based on min-entropies under several important settings. We first show that there exists a nonperfect SSS for arbitrary binary secret information and arbitrary monotone access structure. In addition, for every integers k and n (k ≤ n), we prove that the ideal non-perfect (k, n)-threshold scheme exists even if the distribution of the secret is not uniformly distributed.

arXiv:1401.5896•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•8 citations

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

Secret sharing and duality

László Csirmaz

Secret sharing is an important building block in cryptography. All explicit secret sharing schemes which are known to have optimal complexity are multi-linear, thus are closely related to linear codes. The dual of such a linear scheme, in the sense of duality of linear codes, gives another scheme for the dual access structure. These schemes have the same complexity, namely the largest share size relative to the secret size is the same. It is a long-standing open problem whether this fact is true in general: the complexity of any access structure is the same as the complexity of its dual. We give a partial answer to this question. An almost perfect scheme allows negligible errors, both in the recovery and in the independence. There exists an almost perfect ideal scheme on 174 participants whose complexity is strictly smaller than that of its dual.

•Nov 1, 2020•12 citations

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

Secret sharing and duality

László Csirmaz

Abstract Secret sharing is an important building block in cryptography. All explicit secret sharing schemes which are known to have optimal complexity are multi-linear, thus are closely related to linear codes. The dual of such a linear scheme, in the sense of duality of linear codes, gives another scheme for the dual access structure. These schemes have the same complexity, namely the largest share size relative to the secret size is the same. It is a long-standing open problem whether this fact is true in general: the complexity of any access structure is the same as the complexity of its dual. We give a partial answer to this question. An almost perfect scheme allows negligible errors, both in the recovery and in the independence. There exists an almost perfect ideal scheme on 174 participants whose complexity is strictly smaller than that of its dual.

arXiv:1909.13663•Journal of Mathematical Cryptology•Nov 25, 2020•1 citation

A Linear Algebraic Approach to Strongly Secure Ramp Secret Sharing for General Access Structures

Reo Eriguchi, Noboru Kunihiro, Koji Nuida

Secret sharing is a cryptographic technique to share a secret among participants in such a way that only authorized subsets are able to recover the secret. Ramp secret sharing schemes can achieve better information ratio than perfect schemes while some partial information on a secret which is composed of several sub-secrets leaks out. The notion of strong security has been introduced to control the amount of information on every subset of the sub-secrets unauthorized sets can obtain. In this paper, we reduce the construction of strongly secure ramp secret sharing for general access structures to a linear algebraic problem. As a result, we show that previous results on strongly secure network coding imply two constructions of a linear transformation which makes a given linear ramp scheme strongly secure. They are explicit or provide a deterministic algorithm while the previous method which works for any linear ramp scheme is probabilistic.

International Symposium on Information Theory and its Applications•Oct 24, 2020•0 citations
The following standard relaxations of perfect security for secret sharing schemes (SSSs) exist in the literature:quasi-perfect,almost-perfect, andstatistical. Understanding the power of these relaxations on the efficiency of SSSs, measured via a parameter calledinformation ratio, is a long-standing open problem. In this article, we introduce and study an extremely relaxed security notion, calledpartial security, for which it is only required that any qualified set gains strictly more information about the secret than any unqualified one. To get a meaningful efficiency measure, we normalize the (standard) information ratio of such schemes by an appropriate parameter and refer to the new measure aspartial information ratio. We present three main results in this paper.First, we prove that partial and perfect information ratios coincide for the class of linear SSSs.Second, we prove that for the general (i.e., non-linear) class of SSSs, partial and statistical information ratios are equal.Third, we show that partial and almost-perfect information ratios do not coincide for the class of mixed-linear schemes (i.e., schemes constructed by combining linear schemes with different underlying finite fields). We also use the notion of partial secret sharing to strengthen and unify the previousdecompositiontheorems for constructing SSSs.
Fundamental results on secret sharing schemes (SSSs) are discussed in the setting where security and share size are measured by (conditional) min-entropies. We first formalize a unified framework of SSSs based on (conditional) Rέnyi entropies, which includes SSSs based on Shannon and min entropies etc. as special cases. By deriving the lower bound of share sizes in terms of Rέnyi entropies based on the technique introduced by Iwamoto-Shikata, we obtain the lower bounds of share sizes measured by min entropies as well as by Shannon entropies in a unified manner. As the main contributions of this paper, we show two existential results of non-perfect SSSs based on min-entropies under several important settings. We first show that there exists a nonperfect SSS for arbitrary binary secret information and arbitrary monotone access structure. In addition, for every integers k and n (k ≤ n), we prove that the ideal non-perfect (k, n)-threshold scheme exists even if the distribution of the secret is not uniformly distributed.
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.
Secret sharing is an important building block in cryptography. All explicit secret sharing schemes which are known to have optimal complexity are multi-linear, thus are closely related to linear codes. The dual of such a linear scheme, in the sense of duality of linear codes, gives another scheme for the dual access structure. These schemes have the same complexity, namely the largest share size relative to the secret size is the same. It is a long-standing open problem whether this fact is true in general: the complexity of any access structure is the same as the complexity of its dual. We give a partial answer to this question. An almost perfect scheme allows negligible errors, both in the recovery and in the independence. There exists an almost perfect ideal scheme on 174 participants whose complexity is strictly smaller than that of its dual.
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 Secret sharing is an important building block in cryptography. All explicit secret sharing schemes which are known to have optimal complexity are multi-linear, thus are closely related to linear codes. The dual of such a linear scheme, in the sense of duality of linear codes, gives another scheme for the dual access structure. These schemes have the same complexity, namely the largest share size relative to the secret size is the same. It is a long-standing open problem whether this fact is true in general: the complexity of any access structure is the same as the complexity of its dual. We give a partial answer to this question. An almost perfect scheme allows negligible errors, both in the recovery and in the independence. There exists an almost perfect ideal scheme on 174 participants whose complexity is strictly smaller than that of its dual.
Secret sharing is a cryptographic technique to share a secret among participants in such a way that only authorized subsets are able to recover the secret. Ramp secret sharing schemes can achieve better information ratio than perfect schemes while some partial information on a secret which is composed of several sub-secrets leaks out. The notion of strong security has been introduced to control the amount of information on every subset of the sub-secrets unauthorized sets can obtain. In this paper, we reduce the construction of strongly secure ramp secret sharing for general access structures to a linear algebraic problem. As a result, we show that previous results on strongly secure network coding imply two constructions of a linear transformation which makes a given linear ramp scheme strongly secure. They are explicit or provide a deterministic algorithm while the previous method which works for any linear ramp scheme is probabilistic.