IEEE Information Theory Workshop (ITW)

Coding theorems on the threshold scheme for a general source

H. Koga

Published Dec 10, 2005• 0 citations

Abstract

This paper is concerned with basic properties of the (t, m)-threshold scheme, where m denotes the number of shares and t a threshold. We are interested in the case where a secret information is generated from a source with no assumption on its probabilistic structure. We first give conditions that the (t, m)-threshold scheme must satisfy. Then, we give a theorem which is related to lower bounds on the sizes of shares and the length of random bits needed to a dealer. In addition, we show that the (t, m)-threshold scheme is realized under a certain mild assumption on the source

DOI: 10.1109/itwtpi.2005.1543959

Related papers

Coding Theorems on the Threshold Scheme for a General Source

Hiroki Koga

In this paper, coding theorems on the (t, m) -threshold scheme for a general source are discussed, where m means the number of the shares and t means a threshold. The (t,m) -threshold scheme treated in this paper encrypts n source outputs Xnto m shares at once and is required to satisfy the two conditions that 1) Xnis reproduced from arbitrary t shares, and 2) almost no information of Xnis revealed from any t - 1 shares. It is shown that the (t,m) -threshold scheme must satisfy certain inequalities including the limit inferiors in probability. One of the inequalities is closely related to the minimum length of the fair random bits needed to a dealer for realizing the (t, m) -threshold scheme. In addition, it is shown that a certain variation of Shamir's threshold scheme meets the two conditions. The same approach can be taken to the problems of Shannon's cipher system with the perfect secrecy and fixed-length source coding with vanishing decoding error probability. It is shown that the same kind of inequalities, which indicate the converse coding theorems, hold in both two cases.

IEEE Transactions on Information TheoryMay 29, 20089 citations

Multiple Threshold Schemes Under The Weak Secure Condition

Jiahong Wu, Nan Liu, Kang, Wei

In this paper, we consider the case that sharing many secrets among a set of participants using the threshold schemes. All secrets are assumed to be statistically independent and the weak secure condition is focused on. Under such circumstances we investigate the infimum of the (average) information ratio and the (average) randomness ratio for any structure pair which consists of the number of the participants and the threshold values of all secrets. For two structure pairs such that the two numbers of the participants are the same and the two arrays of threshold values have the subset relationship, two leading corollaries are proved following two directions. More specifically, the bound related to the lengths of shares, secrets and randomness for the complex structure pair can be truncated for the simple one; and the linear schemes for the simple structure pair can be combined independently to be a multiple threshold scheme for the complex one. The former corollary is useful for the converse part and the latter one is helpful for the achievability part. Three new bounds special for the case that the number of secrets corresponding to the same threshold value $ t $ is lager than $ t $ and two novel linear schemes modified from the Vandermonde matrix for two similar cases are presented. Then come the optimal results for the average information ratio, the average randomness ratio and the randomness ratio. We introduce a tiny example to show that there exists another type of bound that may be crucial for the information ratio, to which we only give optimal results in three cases.

arXiv:2312.05737Dec 10, 20230 citations

Secret sharing schemes based on min-entropies

Mitsugu Iwamoto, Junji Shikata

Fundamental results on secret sharing schemes (SSSs) are discussed in the setting where security and share size are measured by (conditional) min-entropies. We first formalize a unified framework of SSSs based on (conditional) Rέnyi entropies, which includes SSSs based on Shannon and min entropies etc. as special cases. By deriving the lower bound of share sizes in terms of Rέnyi entropies based on the technique introduced by Iwamoto-Shikata, we obtain the lower bounds of share sizes measured by min entropies as well as by Shannon entropies in a unified manner. As the main contributions of this paper, we show two existential results of non-perfect SSSs based on min-entropies under several important settings. We first show that there exists a nonperfect SSS for arbitrary binary secret information and arbitrary monotone access structure. In addition, for every integers k and n (k ≤ n), we prove that the ideal non-perfect (k, n)-threshold scheme exists even if the distribution of the secret is not uniformly distributed.

arXiv:1401.5896IEEE International Symposium on Information Theory (ISIT)Jun 1, 20148 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 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

Updating the Parameters of a Threshold Scheme by Minimal Broadcast.

Susan G. Barwick, Wen‐Ai Jackson, Keith M. Martin

Threshold schemes allow secret data to be protected amongst a set of participants in such a way that only a pre-specified threshold of participants can reconstruct the secret from private information (shares) distributed to them on system setup using secure channels. We consider the general problem of designing unconditionally secure threshold schemes whose defining parameters (the threshold and the number of participants) can later be changed by using only public channel broadcast messages. In this paper we are interested in the e#ciency of such threshold schemes, and seek to minimise storage costs (size of shares) as well as optimise performance in low bandwidth environments by minimising the size of necessary broadcast messages. We prove a number of lower bounds on the smallest size of broadcast message necessary to make general changes to the parameters of a threshold scheme in which each participant already holds shares of minimal size.

Jan 1, 20041 citation