We present a new information-theoretic definition and associated results, based on list decoding in a source coding setting. We begin by presenting list-source codes, which naturally map a key length (entropy) to list size. We then show that such codes can be analyzed in the context of a novel information-theoretic metric, -symbol secrecy, that encompasses both the one-time pad and traditional rate-based asymptotic metrics, but, like most cryptographic constructs, can be applied in non-asymptotic settings. We derive fundamental bounds for -symbol secrecy and demonstrate how these bounds can be achieved with MDS codes when the source is uniformly distributed. We discuss applications and implementation issues of our codes.
@cite_6: We consider distributed storage over two untrusted networks, whereby coding is used as a means to achieve a prescribed level of confidentiality. The key idea is to exploit the algebraic structure of the Vandermonde matrix to mix the input blocks, before they are stored in different locations. The proposed scheme ensures that eavesdroppers with access to only one of the networks are unable to decode any symbol even if they are capable of guessing some of the missing blocks. Information-theoretic techniques allow us to quantify the achievable level of confidentiality. Moreover, the proposed approach is shown to offer low complexity and optimal rate.
The setting considered in this paper is related to the wiretap channel II in that a fraction of the source symbols is hidden from a possible adversary. Oliveira al investigated in @cite_6 a related setting in the context of data storage over untrusted networks that do not collude, introducing a solution based on Vandermonde matrices. The MDS coding scheme introduced in this paper is similar to @cite_6 , albeit the framework developed here is more general.