arXiv:2304.14934 · IEEE International Symposium on Information Theory (ISIT)

Randomness Requirements for Three-Secret Sharing

Hari Krishnan P. Anilkumar, Aayush Rajesh, Varun Narayanan, Manoj Prabhakaran, Vinod M. Prabhakaran

Published Jun 25, 2023• 3 citations

Abstract

We study a secret sharing problem with three secrets where the secrets are allowed to be related to each other, i.e., only certain combinations of the three secrets are permitted. The dealer produces three shares such that every pair of shares reveals a unique secret and reveals nothing about the other two secrets, other than what can be inferred from the revealed secret. For the case of binary secrets, we exactly determine the minimum amount of randomness required by the dealer, for each possible set of permitted combinations. Our characterization is based on new lower and upper bounds.

DOI: 10.1109/isit54713.2023.10206455

Related papers

The Price of Privacy: Randomness Complexity of Graph-Based Multi-Secret Sharing

Piotr Marszalik

We study the randomness required to share possibly correlated secret bits among parties connected by a graph. A dealer places shares on the edges so that each party can recover its own secret from its incident shares and learn nothing about the others beyond what its own secret reveals. Anilkumar et al. completely determined the minimum randomness required for three binary secrets. We extend this study to four secrets and obtain results for arbitrary numbers of secrets on general graphs. For four parties on a complete graph, we determine the minimum number of random states for every set of permitted secret combinations: the possible values are one, two, three and four. We also characterize when one random bit suffices on an arbitrary graph.

arXiv:2610.10002Oct 7, 20260 citations

ON THE DEALER'S RANDOMNESS REQUIRED IN PERFECT SECRET SHARING SCHEMES WITH ACCESS STRUCTURES OF CONSTANT RANK

Hung–Min Sun

A secret sharing scheme is a method which allows a dealer to share a secret among a set of participants in such a way that only qualified subsets of participants can recover the secret. The collection of subsets of participants that can reconstruct the secret in this way is called access structure. The rank of an access structure is the maximum cardinality of a minimal qualified subset. A secret sharing scheme is perfect if unqualified subsets of participants obtain no information regarding the secret. The dealer's randomness is the number of random bits required by the dealer to setup a secret sharing scheme. The efficiency of the dealer's randomness is the ratio between the amount of the dealer's randomness and the length of the secret. Because random bits are a natural computational resource, it is important to reduce the amount of randomness used by the dealer to setup a secret sharing scheme. In this paper, we propose some decomposition constructions for perfect secret sharing schemes with access structures of constant rank. Compared with the best previous results, our constructions have some improved upper bounds on the dealer's randomness and on the efficiency of the dealer's randomness.

International Journal of Foundations of Computer ScienceJun 1, 20000 citations

Lower Bounds for Leakage-Resilient Secret Sharing.

Jesper Buus Nielsen, Mark Simkin

Threshold secret sharing allows a dealer to split a secret into n shares such that any authorized subset of cardinality at least t of those shares efficiently reveals the secret, while at the same time any unauthorized subset of cardinality less than t contains no information about the secret. Leakage-resilience additionally requires that the secret remains hidden even if one is given a bounded amount of additional leakage from every share.

Jan 1, 20192 citations

Randomness in Multi-Secret Sharing Schemes.

Carlo Blundo, Barbara Masucci

: A multi--secret sharing scheme is a protocol to share a number of (arbitrarily related) secrets among a set of participants in such a way that only qualified sets of participants can recover the secrets, whereas non-qualified sets of participants might have partial information about them. In this paper we analyze the amount of randomness needed by multi--secret sharing schemes. Given an m-tuple of access structures, we give a lower bound on the number of random bits needed by multi--secret sharing schemes; the lower bound is expressed in terms of a combinatorial parameter that depends only upon the access structures and not on the particular multi--secret sharing scheme used. Key Words: Data Security, Cryptography, Randomness, Secret Sharing Schemes. Category: E.3 1 Introduction There are many situations in cryptography in which it is important to be able to generate random numbers, random bit strings, etc. For example, cryptographic keys are to be generated at random from a speci...

JUCS - Journal of Universal Computer ScienceJan 1, 19998 citations

Secret key agreement by public discussion from common information

Ueli M. Maurer

The problem of generating a shared secret key S by two parties knowing dependent random variables X and Y, respectively, but not sharing a secret key initially, is considered. An enemy who knows the random variable Z, jointly distributed with X and Y according to some probability distribution P/sub XYZ/, can also receive all messages exchanged by the two parties over a public channel. The goal of a protocol is that the enemy obtains at most a negligible amount of information about S. Upper bounds on H(S) as a function of P/sub XYZ/ are presented. Lower bounds on the rate H(S)/N (as N to infinity ) are derived for the case in which X=(X/sub 1/, . . ., X/sub N/), Y=(Y/sub 1/, . . ., Y/sub N/) and Z=(Z/sub 1/, . . ., Z/sub N/) result from N independent executions of a random experiment generating X/sub i/, Y/sub i/ and Z/sub i/ for i=1, . . ., N. It is shown that such a secret key agreement is possible for a scenario in which all three parties receive the output of a binary symmetric source over independent binary symmetric channels, even when the enemy's channel is superior to the other two channels.>

IEEE Transactions on Information TheoryMay 1, 19932,005 citations

Efficient and Distributed Secret Sharing in General Networks

Nihar B. Shah, K. V. Rashmi, Kannan Ramchandran

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.

arXiv:1207.0120Jun 30, 20122 citations