Lossy Chains and Fractional Secret Sharing.

Motivated by the goal of controlling the amount of work required to access a shared resource or to solve a cryptographic puzzle, we introduce and study the related notions of lossy chains and fractional secret sharing. Fractional secret sharing generalizes traditional secret sharing by allowing a fine-grained control over the amount of uncertainty about the secret. More concretely, a fractional secret sharing scheme realizes a fractional access structure f : 2^{[n]} -> {0,...,m-1} by guaranteeing that from the point of view of each set T \subseteq [n] of parties, the secret is uniformly distributed over a set of f(T) + 1 potential secrets. We show that every (monotone) fractional access structure can be realized. For symmetric structures, in which f(T) depends only on the size of T, we give an efficient construction with share size poly(n,log m). Our construction of fractional secret sharing schemes is based on the new notion of lossy chains which may be of independent interest. A lossy chain is a Markov chain (X_0,...,X_n) which starts with a random secret X_0 and gradually loses information about it at a rate which is specified by a loss function g. Concretely, in every step t, the distribution of X_0 conditioned on the value of X_t should always be uniformly distributed over a set of size g(t). We show how to construct such lossy chains efficiently for any possible loss function g, and prove that our construction achieves an optimal asymptotic information rate.Motivated by the goal of controlling the amount of work required to access a shared resource or to solve a cryptographic puzzle, we introduce and study the related notions of lossy chains and fractional secret sharing. Fractional secret sharing generalizes traditional secret sharing by allowing a fine-grained control over the amount of uncertainty about the secret. More concretely, a fractional secret sharing scheme realizes a fractional access structure f : 2^{[n]} -> {0,...,m-1} by guaranteeing that from the point of view of each set T \subseteq [n] of parties, the secret is uniformly distributed over a set of f(T) + 1 potential secrets. We show that every (monotone) fractional access structure can be realized. For symmetric structures, in which f(T) depends only on the size of T, we give an efficient construction with share size poly(n,log m). Our construction of fractional secret sharing schemes is based on the new notion of lossy chains which may be of independent interest. A lossy chain is a Markov chain (X_0,...,X_n) which starts with a random secret X_0 and gradually loses information about it at a rate which is specified by a loss function g. Concretely, in every step t, the distribution of X_0 conditioned on the value of X_t should always be uniformly distributed over a set of size g(t). We show how to construct such lossy chains efficiently for any possible loss function g, and prove that our construction achieves an optimal asymptotic information rate.

Leibniz international proceedings in informaticsJan 1, 20137 citations

Quadratic Secret Sharing and Conditional Disclosure of Secrets

Amos Beimel, Hussien Othman, Naty Peter

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.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.

IEEE Transactions on Information TheoryJul 18, 20233 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.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.7423KybernetikaMay 28, 20230 citations

Cutting-Edge Cryptography Through the Lens of Secret Sharing

Ilan Komargodski, Mark Zhandry

Secret sharing is a mechanism by which a trusted dealer holding a secret “splits ” the secret into many “shares ” and distributes the shares to a collection of parties. Associated with the sharing is a monotone access structure, that specifies which parties are “qualified ” and which are not: any qualified subset of parties can (efficiently) reconstruct the secret, but no unqualified subset can learn anything about the secret. In the most general form of secret sharing, the access structure can be any monotone NP language. In this work, we consider two very natural extensions of secret sharing. In the first, which we call distributed secret sharing, there is no trusted dealer at all, and instead the role of the dealer is distributed amongst the parties themselves. Distributed secret sharing can be thought of as combining the features of multiparty non-interactive key exchange and standard secret sharing, and may be useful in settings where the secret is so sensitive that no one individual dealer can be trusted with the secret. Our second notion is called functional secret sharing, which incorporates some of the features of functional encryption into secret sharing by providing more fine-grained access to the secret. Qualified subsets of parties do not learn the secret, but insteadSecret sharing is a mechanism by which a trusted dealer holding a secret “splits ” the secret into many “shares ” and distributes the shares to a collection of parties. Associated with the sharing is a monotone access structure, that specifies which parties are “qualified ” and which are not: any qualified subset of parties can (efficiently) reconstruct the secret, but no unqualified subset can learn anything about the secret. In the most general form of secret sharing, the access structure can be any monotone NP language. In this work, we consider two very natural extensions of secret sharing. In the first, which we call distributed secret sharing, there is no trusted dealer at all, and instead the role of the dealer is distributed amongst the parties themselves. Distributed secret sharing can be thought of as combining the features of multiparty non-interactive key exchange and standard secret sharing, and may be useful in settings where the secret is so sensitive that no one individual dealer can be trusted with the secret. Our second notion is called functional secret sharing, which incorporates some of the features of functional encryption into secret sharing by providing more fine-grained access to the secret. Qualified subsets of parties do not learn the secret, but instead

Feb 16, 20160 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.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 informaticsJan 1, 20230 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.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, 20260 citations

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.