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 .
The notion of secrecy in wiretap codes has evolved over years. More recently the notion of semantic security for wiretap model has been introduced @cite_6 , which allows arbitrary message distribution and is shown to be equivalent to negligible leakage with respect to statistical distance. There remains one last distinction between semantically secure wiretap model and secret sharing with fixed share size. That is the nature of the main and wiretapper channels are typically stochastic (e.g., the erasure channel with random i.i.d. erasures), whereas for secret sharing a worst-case guarantee for the erasure patterns is required. Namely, in secret sharing, reconstruction with overwhelming probability is required for every choice of @math or more shares, and privacy of the secret is required for every (adaptive or non-adaptive) choice of the @math shares observed by the adversary.
@cite_6
182801106
In the paradigm of network coding, the nodes in a network are allowed to encode the information received from the input links. With network coding, the full capacity of the network can be utilized. In this paper, we propose a model, call the wiretap network, that incorporates information security with network coding. In this model, a collection of subsets of the channels in the network is given, and a wiretapper is allowed to access any one (but not more than one) of these subsets without being able to obtain any information about the message transmitted. Our model includes secret sharing in classical cryptography as a special case. We present a construction of secure linear network codes that can be used provided a certain graph-theoretic condition is satisfied. We also prove the necessity of this condition for the special case that the wiretapper may choose to access any subset of channels of a fixed size. The optimality of our code construction is established for this special case. Finally, we extend our results to the scenario when the wiretapper is allowed to obtain a controlled amount of information about the message. Achieving information-theoretic security using explicit coding scheme in which unlimited computational power for eavesdropper is assumed, is one of the main topics is security consideration. It is shown that polar codes are capacity achieving codes and have a low complexity in encoding and decoding. It has been proven that polar codes reach to secrecy capacity in the binary-input wiretap channels in symmetric settings for which the wiretapper's channel is degraded with respect to the main channel. The first task of this paper is to propose a coding scheme to achieve secrecy capacity in asymmetric nonbinary-input channels while keeping reliability and security conditions satisfied. Our assumption is that the wiretap channel is stochastically degraded with respect to the main channel and message distribution is unspecified. The main idea is to send information set over good channels for Bob and bad channels for Eve and send random symbols for channels that are good for both. In this scheme the frozen vector is defined over all possible choices using polar codes ensemble concept. We proved that there exists a frozen vector for which the coding scheme satisfies reliability and security conditions. It is further shown that uniform distribution of the message is the necessary condition for achieving secrecy capacity. With the advent of quantum key distribution (QKD) systems, perfect (i.e., information-theoretic) security can now be achieved for distribution of a cryptographic key. QKD systems and similar protocols use classical error-correcting codes for both error correction (for the honest parties to correct errors) and privacy amplification (to make an eavesdropper fully ignorant). From a coding perspective, a good model that corresponds to such a setting is the wire tap channel introduced by Wyner in 1975. In this correspondence, we study fundamental limits and coding methods for wire tap channels. We provide an alternative view of the proof for secrecy capacity of wire tap channels and show how capacity achieving codes can be used to achieve the secrecy capacity for any wiretap channel. We also consider binary erasure channel and binary symmetric channel special cases for the wiretap channel and propose specific practical codes. In some cases our designs achieve the secrecy capacity and in others the codes provide security at rates below secrecy capacity. For the special case of a noiseless main channel and binary erasure channel, we consider encoder and decoder design for codes achieving secrecy on the wiretap channel; we show that it is possible to construct linear-time decodable secrecy codes based on low-density parity-check (LDPC) codes that achieve secrecy. We consider a group of m trusted nodes that aim to create a shared secret key K over a wireless channel in the presence an eavesdropper Eve. We assume an erasure broadcast channel from one of the honest nodes to the rest of them including Eve. All of the trusted nodes can also discuss over a cost-free public channel which is observed by Eve. For this setup we characterize the secret key generation capacity and propose an achievability scheme that is computationally efficient and employs techniques from network coding. Surprisingly, whether we have m = 2 nodes, or an arbitrary number m of nodes, we can establish a shared secret key among them at the same rate, independently of m.1