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

ACM Symposium on Theory of Computing (STOC)

Breaking the circuit-size barrier in secret sharing

Tianren Liu, Vinod Vaikuntanathan

Published Jun 20, 2018• 54 citations
Publisher

Abstract

We study secret sharing schemes for general (non-threshold) access structures. A general secret sharing scheme for n parties is associated to a monotone function F:{0,1}n→{0,1}. In such a scheme, a dealer distributes shares of a secret s among n parties. Any subset of parties T ⊆ [n] should be able to put together their shares and reconstruct the secret s if F(T)=1, and should have no information about s if F(T)=0. One of the major long-standing questions in information-theoretic cryptography is to minimize the (total) size of the shares in a secret-sharing scheme for arbitrary monotone functions F.

DOI
10.1145/3188745.3188936

Related papers

Universally ideal secret-sharing schemes

Amos Beimel, Benny Chor

Given a set of parties {1, /spl middot//spl middot//spl middot/, n}, an access structure is a monotone collection of subsets of the parties. For a certain domain of secrets, a secret-sharing scheme for an access structure is a method for a dealer to distribute shares to the parties. These shares enable subsets in the access structure to reconstruct the secret, while subsets not in the access structure get no information about the secret. A secret-sharing scheme is ideal if the domains of the shares are the same as the domain of the secrets. An access structure is universally ideal if there exists an ideal secret-sharing scheme for it over every finite domain of secrets. An obvious necessary condition for an access structure to be universally ideal is to be ideal over the binary and ternary domains of secrets. The authors prove that this condition is also sufficient. They also show that being ideal over just one of the two domains does not suffice for universally ideal access structures. Finally, they give an exact characterization for each of these two conditions.>

IEEE Transactions on Information Theory•May 1, 1994•113 citations

Computational Quantum Secret Sharing

Alper Çakan, Vipul Goyal, Chen-Da Liu-Zhang +1 more

Quantum secret sharing (QSS) allows a dealer to distribute a secret quantum state among a set of parties so that certain subsets can reconstruct the secret, while unauthorized subsets obtain no information. While QSS was introduced over twenty years ago, previous works focused only on existence of perfectly secure schemes, and the share size of the known schemes is exponential even for access structures computed by polynomial size monotone circuits. This stands in contrast to the classical case, where efficient computationally-secure schemes have been long known for all access structures in $\mathsf{monotone~P}$, and one can even obtain shares which are much shorter than the secret which is impossible with perfect security. In this work, we initiate the study of computationally-secure QSS and show that computational assumptions help significantly in building QSS schemes. We present a simple compiler and use it to obtain a large variety results: We construct polynomial-time QSS schemes under standard assumptions for a rich class of access structures. This includes many access structures for which previous results in QSS required exponential share size. We also construct QSS schemes for which the size of the shares is significantly smaller than the size of the secret. As in the classical case, this is impossible with perfect security. We also use our compiler to obtain results beyond computational QSS. In the information-theoretic setting, we improve the share size of perfect QSS schemes for a large class of access structures to $1.5^{n+o(n)}$, improving upon best known schemes and matching the best known result for general access structures in the classical case. Finally, we show construct efficient schemes for all access structures in $\mathsf{P}$ and $\mathsf{NP}$ when the quantum secret sharing scheme is given multiple of copies of the secret.

arXiv:2305.00356•Leibniz international proceedings in informatics•Jan 1, 2023•6 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

Secret sharing with public reconstruction

Amos Beimel, Benny Chor

All known constructions of information theoretic t-out-of-n secret-sharing schemes require secure, private communication channels among the parties for the reconstruction of the secret. We investigate the cost of performing the reconstruction over public communication channels. A naive implementation of this task distributes 2n-2 one times pads to each party. This results in shares whose size is 2n-1 times the secret size. We present three implementations of such schemes that are substantially more efficient. A scheme enabling multiple reconstructions of the secret by different subsets of parties, with factor O(n/t) increase in the shares' size. A one-time scheme, enabling a single reconstruction of the secret, with O(log(n/t)) increase in the shares' size. A one-time scheme, enabling a single reconstruction by a set of size exactly t, with factor O(1) increase in the shares' size. We prove that the first implementation is optimal (up to constant factors) by showing a tight /spl Omega/(n/t) lower bound for the increase in the shares' size.

IEEE Transactions on Information Theory•Jan 1, 1998•44 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

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

Hung–Min Sun

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.

International Journal of Foundations of Computer Science•Jun 1, 2000•0 citations
We study secret sharing schemes for general (non-threshold) access structures. A general secret sharing scheme for n parties is associated to a monotone function F:{0,1}n→{0,1}. In such a scheme, a dealer distributes shares of a secret s among n parties. Any subset of parties T ⊆ [n] should be able to put together their shares and reconstruct the secret s if F(T)=1, and should have no information about s if F(T)=0. One of the major long-standing questions in information-theoretic cryptography is to minimize the (total) size of the shares in a secret-sharing scheme for arbitrary monotone functions F.
Given a set of parties {1, /spl middot//spl middot//spl middot/, n}, an access structure is a monotone collection of subsets of the parties. For a certain domain of secrets, a secret-sharing scheme for an access structure is a method for a dealer to distribute shares to the parties. These shares enable subsets in the access structure to reconstruct the secret, while subsets not in the access structure get no information about the secret. A secret-sharing scheme is ideal if the domains of the shares are the same as the domain of the secrets. An access structure is universally ideal if there exists an ideal secret-sharing scheme for it over every finite domain of secrets. An obvious necessary condition for an access structure to be universally ideal is to be ideal over the binary and ternary domains of secrets. The authors prove that this condition is also sufficient. They also show that being ideal over just one of the two domains does not suffice for universally ideal access structures. Finally, they give an exact characterization for each of these two conditions.>
Quantum secret sharing (QSS) allows a dealer to distribute a secret quantum state among a set of parties so that certain subsets can reconstruct the secret, while unauthorized subsets obtain no information. While QSS was introduced over twenty years ago, previous works focused only on existence of perfectly secure schemes, and the share size of the known schemes is exponential even for access structures computed by polynomial size monotone circuits. This stands in contrast to the classical case, where efficient computationally-secure schemes have been long known for all access structures in monotone P\mathsf{monotone~P}monotone P, and one can even obtain shares which are much shorter than the secret which is impossible with perfect security. In this work, we initiate the study of computationally-secure QSS and show that computational assumptions help significantly in building QSS schemes. We present a simple compiler and use it to obtain a large variety results: We construct polynomial-time QSS schemes under standard assumptions for a rich class of access structures. This includes many access structures for which previous results in QSS required exponential share size. We also construct QSS schemes for which the size of the shares is significantly smaller than the size of the secret. As in the classical case, this is impossible with perfect security. We also use our compiler to obtain results beyond computational QSS. In the information-theoretic setting, we improve the share size of perfect QSS schemes for a large class of access structures to 1.5n+o(n)1.5^{n+o(n)}1.5n+o(n), improving upon best known schemes and matching the best known result for general access structures in the classical case. Finally, we show construct efficient schemes for all access structures in P\mathsf{P}P and NP\mathsf{NP}NP when the quantum secret sharing scheme is given multiple of copies of the secret.
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.
All known constructions of information theoretic t-out-of-n secret-sharing schemes require secure, private communication channels among the parties for the reconstruction of the secret. We investigate the cost of performing the reconstruction over public communication channels. A naive implementation of this task distributes 2n-2 one times pads to each party. This results in shares whose size is 2n-1 times the secret size. We present three implementations of such schemes that are substantially more efficient. A scheme enabling multiple reconstructions of the secret by different subsets of parties, with factor O(n/t) increase in the shares' size. A one-time scheme, enabling a single reconstruction of the secret, with O(log(n/t)) increase in the shares' size. A one-time scheme, enabling a single reconstruction by a set of size exactly t, with factor O(1) increase in the shares' size. We prove that the first implementation is optimal (up to constant factors) by showing a tight /spl Omega/(n/t) lower bound for the increase in the shares' size.
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 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.