Lists that are smaller than their parts: A coding approach to tunable secrecy
This work addresses the need for tunable secrecy in non-asymptotic settings, offering a foundational framework that could impact cryptography and coding theory, though it appears incremental by extending existing concepts.
The paper tackles the problem of information-theoretic secrecy by introducing list-source codes and a new metric called ε-symbol secrecy, which bridges cryptographic and asymptotic approaches, and shows that these bounds can be achieved using MDS codes for uniformly distributed sources.
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.