Optimal Break-Resilient Codes

Break-resilient codes protect a word against an omniscient adversary who breaks it at arbitrary boundaries between adjacent symbols.

For binary codewords of length~$n$ subject to at most~$t$ breaks, the best known explicit construction for this model has redundancy~$O(t\log n\log\log\log n)$, whereas the information-theoretic lower bound is~$\Omega(t\log (n/t))$.

In this paper, we close this gap by presenting a break-resilient code with redundancy~$O(t\log n)$ when~$t\leq n^{1-\varepsilon}$ for a fixed $\varepsilon\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.