text: 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 .
  @cite_20: We present a novel method for constructing linear secret sharing schemes (LSSS) from linear error correcting codes and linear universal hash functions in a blackbox way. The main advantage of this new construction is that the privacy property of the resulting secret sharing scheme essentially becomes independent of the code we use, only depending on its rate. This allows us to fully harness the algorithmic properties of recent code constructions such as efficient encoding and decoding or efficient list-decoding. Choosing the error correcting codes and universal hash functions involved carefully, we obtain solutions to the following open problems:
  @cite_23: 
  @cite_17: Shamir's scheme for sharing secrets is closely related to Reed-Solomon coding schemes. Decoding algorithms for Reed-Solomon codes provide extensions and generalizations of Shamir's method.
summary: 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.