Optimal Break-Resilient Codes

Abstract

Break-resilient codes enable reliable communication in the presence of an omniscient adversary that may split a transmitted message at arbitrary boundaries between consecutive symbols, while the receiver observes only an unordered multiset of the resulting fragments. For binary codewords of length~$n$ subject to at most~$t$ breaks, the best known explicit construction has redundancy~$O(t{\log }_{2}n{\log }_2{\log }_2{\log }_{2}n)$, whereas the information-theoretic lower bound is~$\Omega (t{\log }_2(n/t))$. In this paper, we extend the binary break model to any fixed finite field~$\bbF_q$ and establish a redundancy lower bound of~$\Omega (t{\log }_q(n/t))$. We then give an explicit construction of~$q$-ary break-resilient codes with redundancy~$O(t{\log }_{q}n)$ when~$t\le n^{1-\epsilon }$ for a fixed constant~$\epsilon \in (0,1)$, matching the information-theoretic lower bound up to a constant factor. The key idea is to compute a short algebraic fingerprint of the message, which enables the decoder to reject incorrect assemblies of the received fragments.