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

arXiv:1909.13663 · Journal of Mathematical Cryptology

Secret sharing and duality

László Csirmaz

Published Nov 25, 2020• 20 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1515/jmc-2019-0045

Related papers

Secret sharing schemes and polymatroids

Yang An

Secret sharing, which refers to methods of distributing a secret value among a group of participants, is a very important primitive in cryptology. This thesis contains some contribution to this topic. The results that are presented herein deal with two of the main open problems in secret sharing: the characterization of the ideal access structures and the optimization of the length of the shares. For both open problems, polymatroids are a powerful tool. On one hand, ideal\n\n\n\nmultipartite secret sharing schemes are strongly connected to polymatroids. On the other hand, the entropies of shares of a scheme determine a polymatroid, and because of that, they are fundamental in the search of lower bounds of the length of the shares. For the first open problem, some new and useful families of ideal multipartite access structures are found by using integer polymatroids. As a result the proofs for the existence of ideal secret sharing schemes for them are simplified in great measure. Regarding the second open problem, we present positive and negative results about the only known technique to find lower bounds: linear programming. The positive result are obtained by strengthening this method. The negative ones show the limitation of this method trying to improve the asymptotic lower bounds.

•Jan 1, 2014•0 citations

On ideal and weakly-ideal access structures

Reza Kaboli, Shahram Khazaei, Maghsoud Parviz

For more than two decades, proving or refuting the following statement has remained a challenging open problem in the theory of secret sharing schemes (SSSs): every ideal access structure admits an ideal perfect multi-linear SSS. The class of group-characterizable (GC) SSSs include the multi-linear ones. Hence, if the above statement is true, then so is the following weaker statement: every ideal access structure admits an ideal perfect GC SSS. One contribution of this paper is to show that ideal SSSs are not necessarily GC. Our second contribution is to study the above two statements with respect to several variations of weakly-ideal access structures. Recently, Mejia and Montoya studied ideal access structures that admit ideal multi-linear schemes and provided a classification-like theorem for them. We additionally present some tools that are useful to extend their result.

Advances in Mathematics of Communications•Jun 11, 2021•2 citations

Upper and lower bounds for secret sharing schemes with general access structures

Sofia Barbetta

Secret sharing schemes are a fundamental cryptographic tool for securely distributing sensitive information among multiple parties according to a specified access structure. For a given access policy, several schemes with different levels of efficiency may exist. One of the main parameters in this analysis is the share size and a central goal is to minimize it. This thesis studies the complexity of secret sharing schemes by focusing on lower and upper bounds on the share size for arbitrary and explicit access structures. The main objective is to collect the most relevant results in the literature, ranging from early lower bounds due to Karnin et al. and Csirmaz and upper-bound of Liu and Vaikuntanathan to recent advances that have significantly improved known bounds. Despite this progress, a significant gap between lower and upper bounds remains, leaving the determination of the optimal share size an open problem.

•Jan 27, 2026•0 citations

Partial Secret Sharing Schemes

Amir Jafari, Shahram Khazaei

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.

IEEE Transactions on Information Theory•Apr 6, 2023•10 citations

On the Size of a Share for Non-perfect Secret Sharing Schemes

Maki Yoshida

In a secret sharing scheme, a secret s is divided into multiple shares and distributed among n participants. As more shares are collected, the mutual information between the secret and the shares increases monotonically. In the perfect case, the best known explicit lower bound on the share size is given by $\frac{{{2^k} - 1}}{k} \cdot H(s)$, where H(s) is the entropy of the secret and k is the largest integer such that n ≥ 2k+k−2. This paper considers the non-perfect case, in which each share reveals at most a $\frac{1}{L}$ fraction of the secret's entropy, for an integer L > 1. A prior result in this setting provides a lower bound of $\frac{{{2^k} - 1}}{{kL}} \cdot H(s)$, under the condition n ≥ 2k+k+L−3. We provide a new lower bound that approaches the perfect-case bound, namely $\frac{{{2^k} - 2 + 1/L}}{k} \cdot H(s)$, which holds under the condition n ≥ 2k+k+2L−4. The proof generalizes perfect-case techniques by increasing the number of participants by 2(L−1). These results refine our understanding of the trade-off between share size and information leakage in non-perfect secret sharing. In particular, we construct non-perfect access structures that nearly attain the perfect lower bound with fewer participants than previous non-perfect bounds, thus complementing and extending prior work.

IEEE Information Theory Workshop (ITW)•Sep 29, 2025•0 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
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, which refers to methods of distributing a secret value among a group of participants, is a very important primitive in cryptology. This thesis contains some contribution to this topic. The results that are presented herein deal with two of the main open problems in secret sharing: the characterization of the ideal access structures and the optimization of the length of the shares. For both open problems, polymatroids are a powerful tool. On one hand, ideal\n\n\n\nmultipartite secret sharing schemes are strongly connected to polymatroids. On the other hand, the entropies of shares of a scheme determine a polymatroid, and because of that, they are fundamental in the search of lower bounds of the length of the shares. For the first open problem, some new and useful families of ideal multipartite access structures are found by using integer polymatroids. As a result the proofs for the existence of ideal secret sharing schemes for them are simplified in great measure. Regarding the second open problem, we present positive and negative results about the only known technique to find lower bounds: linear programming. The positive result are obtained by strengthening this method. The negative ones show the limitation of this method trying to improve the asymptotic lower bounds.
For more than two decades, proving or refuting the following statement has remained a challenging open problem in the theory of secret sharing schemes (SSSs): every ideal access structure admits an ideal perfect multi-linear SSS. The class of group-characterizable (GC) SSSs include the multi-linear ones. Hence, if the above statement is true, then so is the following weaker statement: every ideal access structure admits an ideal perfect GC SSS. One contribution of this paper is to show that ideal SSSs are not necessarily GC. Our second contribution is to study the above two statements with respect to several variations of weakly-ideal access structures. Recently, Mejia and Montoya studied ideal access structures that admit ideal multi-linear schemes and provided a classification-like theorem for them. We additionally present some tools that are useful to extend their result.
Secret sharing schemes are a fundamental cryptographic tool for securely distributing sensitive information among multiple parties according to a specified access structure. For a given access policy, several schemes with different levels of efficiency may exist. One of the main parameters in this analysis is the share size and a central goal is to minimize it. This thesis studies the complexity of secret sharing schemes by focusing on lower and upper bounds on the share size for arbitrary and explicit access structures. The main objective is to collect the most relevant results in the literature, ranging from early lower bounds due to Karnin et al. and Csirmaz and upper-bound of Liu and Vaikuntanathan to recent advances that have significantly improved known bounds. Despite this progress, a significant gap between lower and upper bounds remains, leaving the determination of the optimal share size an open problem.
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.
In a secret sharing scheme, a secret s is divided into multiple shares and distributed among n participants. As more shares are collected, the mutual information between the secret and the shares increases monotonically. In the perfect case, the best known explicit lower bound on the share size is given by 2k−1k⋅H(s)\frac{{{2^k} - 1}}{k} \cdot H(s)k2k−1​⋅H(s), where H(s) is the entropy of the secret and k is the largest integer such that n ≥ 2k+k−2. This paper considers the non-perfect case, in which each share reveals at most a 1L\frac{1}{L}L1​ fraction of the secret's entropy, for an integer L > 1. A prior result in this setting provides a lower bound of 2k−1kL⋅H(s)\frac{{{2^k} - 1}}{{kL}} \cdot H(s)kL2k−1​⋅H(s), under the condition n ≥ 2k+k+L−3. We provide a new lower bound that approaches the perfect-case bound, namely 2k−2+1/Lk⋅H(s)\frac{{{2^k} - 2 + 1/L}}{k} \cdot H(s)k2k−2+1/L​⋅H(s), which holds under the condition n ≥ 2k+k+2L−4. The proof generalizes perfect-case techniques by increasing the number of participants by 2(L−1). These results refine our understanding of the trade-off between share size and information leakage in non-perfect secret sharing. In particular, we construct non-perfect access structures that nearly attain the perfect lower bound with fewer participants than previous non-perfect bounds, thus complementing and extending prior work.
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.