Shamir's celebrated secret sharing scheme provides an efficient method for encoding a secret of arbitrary length @math among any @math players such that for a threshold parameter @math , (i) the knowledge of any @math shares does not reveal any information about the secret and, (ii) any choice of @math shares fully reveals the secret. It is known that any such threshold secret sharing scheme necessarily requires shares of length @math , and in this sense Shamir's scheme is optimal. The more general notion of ramp schemes requires the reconstruction of secret from any @math shares, for a positive integer gap parameter @math . Ramp secret sharing scheme necessarily requires shares of length @math . Other than the bound related to secret length @math , the share lengths of ramp schemes can not go below a quantity that depends only on the gap ratio @math . In this work, we study secret sharing in the extremal case of bit-long shares and arbitrarily small gap ratio @math , where standard ramp secret sharing becomes impossible. We show, however, that a slightly relaxed but equally effective notion of semantic security for the secret, and negligible reconstruction error probability, eliminate the impossibility. Moreover, we provide explicit constructions of such schemes. One of the consequences of our relaxation is that, unlike standard ramp schemes with perfect secrecy, adaptive and non-adaptive adversaries need different analysis and construction. For non-adaptive adversaries, we explicitly construct secret sharing schemes that provide secrecy against any @math fraction of observed shares, and reconstruction from any @math fraction of shares, for any choices of @math . Our construction achieves secret length @math , which we show to be optimal. For adaptive adversaries, we construct explicit schemes attaining a secret length @math .
In @cite_23 @cite_17 , the secret is one bit. In @cite_20 , secrets of length equal to a fraction of @math (number of players) is considered. This time binary secret sharing with adaptive and non-adaptive adversaries similar to the model we consider in this work is defined. However the paper considers only a privacy threshold @math , and reconstruction is from the full share set ( @math always). Their goal is to achieve large secrets @math over binary shares with large privacy parameter @math , which is also similar to ours. They have an additional goal of keeping the computational complexity of the reconstruction algorithm within AC @math , which we do not consider in this work. Their large privacy parameter @math is with a @math much smaller than @math , which means that the relative threshold gap @math can not be arbitrarily small.
@cite_20 @cite_23 @cite_17
602475741 1990304797
A secret sharing scheme is a method to store information securely and reliably. Particularly, in a threshold secret sharing scheme , a secret is encoded into @math shares, such that any set of at least @math shares suffice to decode the secret, and any set of at most @math d @math t_ 1 d n$ . The scheme is based on a generalization of Shamirs secret sharing scheme and preserves its simplicity and efficiency. In addition, we consider the setting of secure distributed storage where the proposed communication efficient secret sharing schemes not only improve decoding bandwidth but further improve disk access complexity during decoding. Consider two parties holding samples from correlated distributions @math and @math , respectively, where these samples are within distance @math of each other in some metric space. The parties wish to agree on a close-to-uniformly distributed secret key @math by sending a single message over an insecure channel controlled by an all-powerful adversary who may read and modify anything sent over the channel. We consider both the keyless case, where the parties share no additional secret information, and the keyed case, where the parties share a long-term secret @math that they can use to generate a sequence of session keys @math using multiple pairs @math . The former has applications to, e.g., biometric authentication, while the latter arises in, e.g., the bounded-storage model with errors. We show solutions that improve upon previous work in several respects. The best prior solution for the keyless case with no errors (i.e., @math ) requires the min-entropy of @math to exceed @math , where @math is the bit length of @math . Our solution applies whenever the min-entropy of @math exceeds the minimal threshold @math , and yields a longer key. Private information retrieval (PIR) is the problem of retrieving as efficiently as possible, one out of @math messages from @math non-communicating replicated databases (each holds all @math messages) while keeping the identity of the desired message index a secret from each individual database. The information theoretic capacity of PIR (equivalently, the reciprocal of minimum download cost) is the maximum number of bits of desired information that can be privately retrieved per bit of downloaded information. @math -private PIR is a generalization of PIR to include the requirement that even if any @math of the @math databases collude, the identity of the retrieved message remains completely unknown to them. Robust PIR is another generalization that refers to the scenario where we have @math databases, out of which any @math may fail to respond. For @math messages and @math databases out of which at least some @math must respond, we show that the capacity of @math -private and Robust PIR is @math . The result includes as special cases the capacity of PIR without robustness ( @math ) or @math -privacy constraints ( @math ).