Shamir's (n, k) threshold secret sharing is an important component of several cryptographic protocols, such as those for secure multiparty-computation. 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 every participant. In this paper, we consider the problem of secret sharing when the dealer does not have direct communication links to all participants, and instead, they form a general network. We present an algorithm for secret sharing over networks that satisfy what we call the k-propagating-dealer condition. The algorithm is communication-efficient, distributed and deterministic. Interestingly, the solution constitutes an instance of a network coding problem admitting a distributed and deterministic solution, and furthermore, handles the case of nodal-eavesdropping, about which very little appears to be known in the literature. In the second part of the paper, 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 Θ(n), and furthermore, is always within a constant factor of the lower bound. We also show that, in contrast, existing solutions in the literature entail a communication-complexity that is superlinear for a wide class of networks, and is Θ(n2) in the worst case. Our algorithm thus allows for efficient generalization of several cryptographic protocols to a large class of networks.
Shamir's (n, k) threshold secret sharing is an important component of several cryptographic protocols, such as those for secure multiparty-computation. 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 every participant. In this paper, we consider the problem of secret sharing when the dealer does not have direct communication links to all participants, and instead, they form a general network. We present an algorithm for secret sharing over networks that satisfy what we call the k-propagating-dealer condition. The algorithm is communication-efficient, distributed and deterministic. Interestingly, the solution constitutes an instance of a network coding problem admitting a distributed and deterministic solution, and furthermore, handles the case of nodal-eavesdropping, about which very little appears to be known in the literature. In the second part of the paper, 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 Θ(n), and furthermore, is always within a constant factor of the lower bound. We also show that, in contrast, existing solutions in the literature entail a communication-complexity that is superlinear for a wide class of networks, and is Θ(n2) in the worst case. Our algorithm thus allows for efficient generalization of several cryptographic protocols to a large class of networks.
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.
Secret sharing is an important component of several cryptographic protocols. These include protocols for secure multiparty function computation, key management, and secure archival storage. Most protocols assume that the dealer has direct communication links with every participant, in which case, the dealer can directly communicate the respective shares to all participants. In this paper, we consider the problem of disseminating shares of a secret when the dealer and the participants form a general network. We provide an algorithm for secret share dissemination that is communication-efficient, distributed and deterministic. Interestingly, the solution constitutes an instance of a network coding problem admitting a distributed and deterministic solution, and furthermore, handles the case of nodal-eavesdropping, about which very little appears to be known in the literature.
A secret sharing scheme typically requires secure communications in each of two distribution phases: (1) a dealer distributes shares to participants (share distribution phase); and later (2) the participants in some authorised subset send their share information to a combiner (secret reconstruction phase). While problems on storage required for participants, for example, the size of shares, have been well studied, problems regarding the communication complexity of the two distribution phases seem to have been mostly neglected in the literature so far. In this correspondence, we deal with several communication related problems in the secret reconstruction phase. Firstly, we show that there is a tradeoff between the communication costs and the number of participants involved in the secret reconstruction. We introduce the communication rate as the ratio of the secret size and the total number of communication bits transmitted from the participants to the combiner in the secret reconstruction phase. We derive a lower bound on the communication rate and give constructions that meet the bound. Secondly, we show that the point-to-point secure communication channels for participants to send share information to the combiner can be replaced with partial broadcast channels. We formulate partial broadcast channels as set systems and show that they are equivalent to the well-known combinatorial objects of cover-free family. Surprisingly, we find that the number of partial broadcast channels can be significantly reduced from the number of point-to-point secure channels. Precisely, in its optimal form, the number of channels can be reduced from n to O(log n), where is the number of participants in a secret sharing scheme. We also study the communication rates of partial broadcast channels for the secret reconstruction.
We propose cryptographic rational secret sharing protocols over general networks. In a general network, the dealer may not have direct connections to each player, and players may not have direct connections to each of the other players. We present conditions on the network topology for which our proposed protocols are computational strict Nash equilibria and (k−1)-resilient, along with analysis on their round and communication complexity. We also present new notions of equilibria such as Φ-resilient computational Nash equilibria, whereby a protocol is resilient to coalitions that satisfy conditions in Φ, regardless of the coalition’s size. We also propose (n−1)-key leakage-tolerant equilibria applicable to cryptographic protocols involving secret keys, whereby the equilibrium holds even if some players acquire (n−1) tuples of secret keys.
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.
A dealer aims to share a secret with participants so that only predefined subsets can reconstruct it, while others learn nothing. The dealer and participants access correlated randomness and communicate over a one-way, public, rate-limited channel. For this problem, we propose the first explicit coding scheme able to handle arbitrary access structures and achieve the best known achievable rates, previously obtained non-constructively. Our construction relies on lossy source coding coupled with distribution approximation to handle the reliability constraints, followed by universal hashing to handle the security constraints. We stress that our coding scheme does not require symmetry or degradation assumptions on the correlated random variables, and does not need a pre-shared secret among the participants and dealer. As a by-product, our construction also yields explicit coding schemes for secret-key generation under one-way, rate-limited public communication that, unlike prior work, achieves the capacity for arbitrary source correlations and do not require a pre-shared secret to ensure strong secrecy.