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

Quadratic Secret Sharing and Conditional Disclosure of Secrets

Amos Beimel, Hussien Othman, Naty Peter

Published Jul 18, 2023• 3 citations
Publisher

Abstract

There is a huge gap between the upper and lower bounds on the share size of secret-sharing schemes for$n$-party access structures; consistent with our current knowledge the optimal share size can be anywhere between polynomial and exponential in$n$. For linear secret-sharing schemes, the share size for almost all$n$-party access structures is exponential in$n$. We would like to study larger classes of secret-sharing schemes with two goals: 1) prove lower bounds for larger classes of secret-sharing schemes; and 2) construct efficient secret-sharing schemes. Given this motivation, Paskin-Cherniavsky and Radune (ITC’20) introduced a new class of secret-sharing schemes in which the shares are generated by applying degree-$d$polynomials to the secret and some random field elements. We define and study two additional classes of polynomial secret-sharing schemes: 1) schemes in which the reconstruction of the secret is done using polynomials; and 2) schemes in which both sharing and reconstruction are done by polynomials. Our main result is a construction of secret-sharing schemes and conditional disclosure of secrets protocols with quadratic sharing and reconstruction that are more efficient than linear secret-sharing schemes. To complement our results, we prove lower bounds on the share size for schemes with polynomial reconstruction. Finally, we give an evidence that schemes with polynomial sharing are probably stronger than schemes with polynomial reconstruction.

DOI
10.1109/tit.2023.3296588

Related papers

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

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•6 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 in such a way that certain authorized subsets can reconstruct the secret, while unauthorized subsets obtain no information about it. Previous works on QSS for general access structures focused solely on the existence of perfectly secure schemes, and the share size of the known schemes is necessarily exponential even in cases where the access structure is computed by polynomial size monotone circuits. This stands in stark contrast to the classical setting, where polynomial-time computationally-secure secret sharing schemes have been long known for all access structures computed by polynomial-size monotone circuits under standard hardness assumptions, and one can even obtain shares which are much shorter than the secret (which is impossible with perfect security). While QSS was introduced over twenty years ago, previous works only considered information-theoretic privacy. In this work, we initiate the study of computationally-secure QSS and show that computational assumptions help significantly in building QSS schemes, just as in the classical case. We present a simple compiler and use it to obtain a large variety results: We construct polynomial-time computationally-secure QSS schemes under standard hardness assumptions for a rich class of access structures. This includes many access structures for which previous results in QSS necessarily required exponential share size. In fact, we can go even further: We construct QSS schemes for which the size of the quantum shares is significantly smaller than the size of the secret. As in the classical setting, this is impossible with perfect security. We also apply 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 n-party 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 setting. Finally, among other things, we study the class of access structures which can be efficiently implemented when the quantum secret sharing scheme has access to a given number of copies of the secret, including all such functions in 𝖯 and NP.

Leibniz international proceedings in informatics•Jan 1, 2023•0 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•Apr 29, 2023•1 citation

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

On the Power of Nonlinear Secret-Sharing.

Amos Beimel, Yuval Ishai

A secret-sharing scheme enables a dealer to distribute a secret among n parties such that only some predefined authorized sets of parties will be able to reconstruct the secret from their shares. The (monotone) collection of authorized sets is called an access structure, and is freely identified with its characteristic monotone function f : 1}. A family of secret-sharing schemes is called efficient if the total length of the n shares is polynomial in n. Most previously known secret-sharing schemes belonged to a class of linear schemes, whose complexity coincides with the monotone span program size of their access structure. Prior to this work there was no evidence that nonlinear schemes can be significantly more efficient than linear schemes, and in particular there were no candidates for schemes efficiently realizing access structures which do not lie in NC.

•Jan 1, 2001•2 citations
There is a huge gap between the upper and lower bounds on the share size of secret-sharing schemes fornnn-party access structures; consistent with our current knowledge the optimal share size can be anywhere between polynomial and exponential innnn. For linear secret-sharing schemes, the share size for almost allnnn-party access structures is exponential innnn. We would like to study larger classes of secret-sharing schemes with two goals: 1) prove lower bounds for larger classes of secret-sharing schemes; and 2) construct efficient secret-sharing schemes. Given this motivation, Paskin-Cherniavsky and Radune (ITC’20) introduced a new class of secret-sharing schemes in which the shares are generated by applying degree-dddpolynomials to the secret and some random field elements. We define and study two additional classes of polynomial secret-sharing schemes: 1) schemes in which the reconstruction of the secret is done using polynomials; and 2) schemes in which both sharing and reconstruction are done by polynomials. Our main result is a construction of secret-sharing schemes and conditional disclosure of secrets protocols with quadratic sharing and reconstruction that are more efficient than linear secret-sharing schemes. To complement our results, we prove lower bounds on the share size for schemes with polynomial reconstruction. Finally, we give an evidence that schemes with polynomial sharing are probably stronger than schemes with polynomial reconstruction.
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.
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).
Quantum secret sharing (QSS) allows a dealer to distribute a secret quantum state among a set of parties in such a way that certain authorized subsets can reconstruct the secret, while unauthorized subsets obtain no information about it. Previous works on QSS for general access structures focused solely on the existence of perfectly secure schemes, and the share size of the known schemes is necessarily exponential even in cases where the access structure is computed by polynomial size monotone circuits. This stands in stark contrast to the classical setting, where polynomial-time computationally-secure secret sharing schemes have been long known for all access structures computed by polynomial-size monotone circuits under standard hardness assumptions, and one can even obtain shares which are much shorter than the secret (which is impossible with perfect security). While QSS was introduced over twenty years ago, previous works only considered information-theoretic privacy. In this work, we initiate the study of computationally-secure QSS and show that computational assumptions help significantly in building QSS schemes, just as in the classical case. We present a simple compiler and use it to obtain a large variety results: We construct polynomial-time computationally-secure QSS schemes under standard hardness assumptions for a rich class of access structures. This includes many access structures for which previous results in QSS necessarily required exponential share size. In fact, we can go even further: We construct QSS schemes for which the size of the quantum shares is significantly smaller than the size of the secret. As in the classical setting, this is impossible with perfect security. We also apply 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 n-party 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 setting. Finally, among other things, we study the class of access structures which can be efficiently implemented when the quantum secret sharing scheme has access to a given number of copies of the secret, including all such functions in 𝖯 and NP.
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.
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.
A secret-sharing scheme enables a dealer to distribute a secret among n parties such that only some predefined authorized sets of parties will be able to reconstruct the secret from their shares. The (monotone) collection of authorized sets is called an access structure, and is freely identified with its characteristic monotone function f : 1}. A family of secret-sharing schemes is called efficient if the total length of the n shares is polynomial in n. Most previously known secret-sharing schemes belonged to a class of linear schemes, whose complexity coincides with the monotone span program size of their access structure. Prior to this work there was no evidence that nonlinear schemes can be significantly more efficient than linear schemes, and in particular there were no candidates for schemes efficiently realizing access structures which do not lie in NC.