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.
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.
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.
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 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
Verifiable Secret-Sharing(VSS) is a fundamental primitive in secure distributed computing that allows a designated dealer to share a secret amongnparties in the presence of an adversary controlling at mosttof them. We study VSS in the presence ofcomputationally-boundedadversaries. Known VSS protocols tolerate up totstaperfectsecurity (Appan et al. IEEE IT 2023) where the threshold conditions arenotknown to be optimal or withstatistical security(Appan et al. TCC 2023) where the threshold conditions are optimal, but the parties need to performexponentialamount of computation and communication. Using our VSS protocol, we design a secureMulti-Party Computation(MPC) protocol in theplain Public Key Infrastructure (PKI) model, i.e., without assuming an expensive trusted setup. Although our proposed MPC protocol incurs higher communication complexity than state-of-the-art network-agnostic MPC protocols, it motivates alternative directions for designingcomputationally inexpensiveMPC protocols based on a plain PKI setup, which has not been explored in the domain of computationally secure networkagnostic MPC and offers valuable insights into designing it.