In a k-threshold secret sharing scheme, a dealer who holds a secret s distributes parts of this secret (the shares) to n players; If k or more of these players pool their shares, they are able to determine s, but if less than k of them pool their shares, they cannot infer any information on s. In 1979, Shamir introduced such a scheme, based on polynomial interpolation in a finite field. This scheme is widely used in other cryptographic protocols, because it is simple, elegant and above all information-theoretically secure. There are a few proofs of the scheme's security, but to our knowledge, none of them is entirely based on the information-theoretical entropy function introduced by Shannon in 1948. We propose such a demonstration.
In a k-threshold secret sharing scheme, a dealer who holds a secret s distributes parts of this secret (the shares) to n players; If k or more of these players pool their shares, they are able to determine s, but if less than k of them pool their shares, they cannot infer any information on s. In 1979, Shamir introduced such a scheme, based on polynomial interpolation in a finite field. This scheme is widely used in other cryptographic protocols, because it is simple, elegant and above all information-theoretically secure. There are a few proofs of the scheme's security, but to our knowledge, none of them is entirely based on the information-theoretical entropy function introduced by Shannon in 1948. We propose such a demonstration.
Secret sharing is an instrumental tool for sharing secret keys in distributed systems. In a classical threshold setting, this involves a dealer who has a secret/key, a set of parties/users to which shares of the secret are sent, and a threshold on the number of users whose presence is needed in order to recover the secret. In secret sharing, secure links with no leakage are often assumed between the involved parties. However, when the users are nodes in a communication network and all the links are physical links, e.g., wireless, such assumptions are not valid anymore. In order to study this critical problem, we propose a statistical leakage model of secret sharing, where some noisy versions of all the secret shares might be independently leaked to an adversary. We then study the resilience of the seminal Shamir's secret sharing scheme with statistical leakage, and bound certain measures of security (i.e., semantic security, mutual information security), given other parameters of the system including the amount of leakage from each secret share. We show that for an extreme scenario of Shamir's scheme, in particular when the underlying field characteristic is 2, the security of each bit of the secret against leakage improves exponentially with the number of users. To the best of our knowledge, this is the first attempt towards understanding secret sharing under general statistical noisy leakage.
Shamir's (n, k) threshold secret sharing is an important component of several cryptographic protocols, such as those for secure multiparty-computation, key management, and Byzantine agreement. These protocols typically assume the presence of direct communication links from the dealer to all participants, in which case, the dealer can directly pass the shares of the secret to each participant. In this paper, we consider the problem of secret sharing when the dealer does not have direct links to all the participants, and instead, the dealer and the participants form a general network. We present an efficient and distributed algorithm for secret sharing over general networks that satisfy what we call the k-propagating-dealer condition.
We derive information-theoretic lower bounds on the communication complexity of secret sharing over any network, which may also be of independent interest. We show that for networks satisfying the k-propagating-dealer condition, the communication complexity of our algorithm is {\Theta}(n), and furthermore, is a constant factor away from the lower bounds. We also show that, in contrast, the existing solution entails a communication-complexity that is super-linear for a wide class of networks, and is {\Theta}(n^2) in the worst case. Moreover, the amount of randomness required under our algorithm is a constant, while that required under the existing solution increases with n for a large class of networks, and in particular, is {\Theta}(n) whenever the degree of the dealer is bounded. Finally, while the existing solution requires considerable coordination in the network and knowledge of the global topology, our algorithm is completely distributed and requires each node to know only the identities of its neighbours. Our algorithm thus allows for efficient generalization of several cryptographic protocols to a large class of general networks.
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.
Function secret sharing (FSS) is a cryptographic primitive that is introduced by Boyle et al. (Eurocrypt 2015), motivated by application scenarios involving private access to large distributed data while minimising the overhead of communication, for example, private information retrieval. Informally, an n-party FSS scheme splits a function f into n functions f1,...,fnsuch that f = f1+...+ fnand every strict subset of the function shares hide f . Most of the known FSS constructions only have computational hiding, namely, the hiding property holds only against a computationally bounded adversary. We consider information-theoretic hiding in this work while allowing f to be recovered from t function shares and correspondingly, any (t - 1) function shares unconditionally hide f . Call it (t, n)-threshold function secret sharing ((t, n)-TFSS for short). Using information-theoretic tools and through a series of optimizations, we show that our (t, n)-TFSS have better performance than FSS in terms of communication complexity, a criterion that measures the efficiency of such protocols. Specifically, a (t, n)-TFSS scheme with communication complexity O(l) is designed in this paper and it is better than the existing FSS schemes with lowest communication complexity O(λl), where λ is the length of pseudo-random generator's seeds. In addition, the (t, n)-TFSS have an extra robustness property in the sense that even if up to (n - t) function shares are not available, the protocol still computes the function value at a given point correctly.
We consider the problem of increasing the threshold parameter of a secret-sharing scheme after the setup (share distri- bution) phase, without further communication between the dealer and the shareholders. Previous solutions to this problem require one to start off with a nonstandard scheme designed specifically for this purpose, or to have communication between shareholders. In contrast, we show how to increase the threshold parameter of the standard Shamir secret-sharing scheme without communica- tion between the shareholders. Our technique can thus be applied to existing Shamir schemes even if they were set up without con- sideration to future threshold increases. Our method is a new positive cryptographic application for lat- tice reduction algorithms, inspired by recent work on lattice-based list decoding of Reed-Solomon codes with noise bounded in the Lee norm. We use fundamental results from the theory of lattices (geometry of numbers) to prove quantitative statements about the information-theoretic security of our construction. These lattice- based security proof techniques may be of independent interest.