Cutting-Edge Cryptography Through the Lens of Secret Sharing

Ilan Komargodski, Mark Zhandry

Published Feb 16, 2016• 0 citations

Abstract

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 instead

Related papers

Secret-Sharing for NP from Indistinguishability Obfuscation

Ilan Komargodski, Moni Naor, Eylon Yogev

A computational secret-sharing scheme is a method that enables a dealer, that has a secret, to distribute this secret among a set of parties such that a qualified subset of parties can efficiently reconstruct the secret while any unqualified subset of parties cannot efficiently learn anything about the secret. The collection of qualified subsets is defined by a Boolean function. It has been a major open problem to understand which (monotone) functions can be realized by a computational secret-sharing schemes. Yao suggested a method for secret-sharing for any function that has a polynomial-size monotone circuit (a class which is strictly smaller than the class of monotone functions in P). Around 1990 Rudich raised the possibility of obtaining secret-sharing for all monotone functions in NP: In order to reconstruct the secret a set of parties must be qualified and provide a witness attesting to this fact. Recently, Garg et al. (STOC 2013) put forward the concept of witness encryption, where the goal is to encrypt a message relative to a statement in for a language L in NP such that anyone holding a witness to the statement can decrypt the message, however, if x is not in L, then it is computationally hard to decrypt. Garg et al. showed how to construct several cryptographic primitives from witness encryption and gave a candidate construction. One can show that computational secret-sharing implies witness encryption for the same language. Our main result is the converse: we give a construction of a computational secret-sharing scheme for any monotone function in NP assuming witness encryption for NP and one-way functions. As a consequence we get a completeness theorem for secret-sharing: computational secret-sharing scheme for any single monotone NP-complete function implies a computational secret-sharing scheme for every monotone function in NP.

arXiv:1403.5698Jan 1, 20144 citations

Breaking the circuit-size barrier in secret sharing

Tianren Liu, Vinod Vaikuntanathan

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.

ACM Symposium on Theory of Computing (STOC)Jun 20, 201846 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, 20012 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 informaticsJan 1, 20230 citations

Lossy Chains and Fractional Secret Sharing

Yuval Ishai, Eyal Kushilevitz Z, Omer Strulovich

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

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 TheoryMay 1, 1994111 citations