A Public-Key-Dependent Adversarial-Deletion Ceiling for Fixed-Alphabet Multi-Bit Pseudorandom Codes
Abstract
A pseudorandom code (PRC) is a keyed error-correcting code whose codewords are computationally indistinguishable from uniform strings. We study public-key PRCs over fixed alphabets against adversarial deletions, where the deletion channel may both depend on the public encoding key and the transmitted codeword. Let γqLCS denote the asymptotic normalised longest-common-subsequence length of two independent uniform q-ary strings. We prove that for every fixed q≥2 no multi-message public-key PRC with a single-output decoder is robust against all such δ-deletion channels for any δ>1−γqLCS. For q=2, the current rigorous bound γ2≥0.792665992 rules out every constant δ>0.207334008. The proof uses pseudorandomness only to transfer an LCS event from uniform strings to independently sampled codewords and therefore also the resulting collision argument is information-theoretic and requires no secret key. We also extend the argument to list decoding: for every fixed constant L, provided the message space contains at least L+1 messages, no such PRC with output lists of size at most L is robust for δ>1−γ2(L+1). Since γ2(m)=1/2+Θ(1/√m), these thresholds approach 1/2. Our bounds are specific to public-key-dependent adversarial channels and do not apply to oblivious edit channels.
Related
- Alphabet-Dependent Bounds for Pure Quantum (r,ρ)-Locally Recoverable Codes
- The Expected Number of Distinct Substrings in an Alphabet String
- Maximizing Measures for Subadditive and Almost-Additive Potentials on Countable-Alphabet Subshifts
- Long induced cycles in pseudorandom graphs
- Optimally pseudorandom K4-free graphs
BibTeX
@misc{dehmel2026publickeydependent,
title = {{A Public-Key-Dependent Adversarial-Deletion Ceiling for Fixed-Alphabet Multi-Bit Pseudorandom Codes}},
author = {Frederick Dehmel and Shilun Li},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.02943},
eprint = {2609.02943},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.02943},
note = {CC0},
}
RIS
TY - UNPB
TI - A Public-Key-Dependent Adversarial-Deletion Ceiling for Fixed-Alphabet Multi-Bit Pseudorandom Codes
AU - Frederick Dehmel
AU - Shilun Li
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.02943
UR - https://arxiv.org/abs/2609.02943
AB - A pseudorandom code (PRC) is a keyed error-correcting code whose codewords are computationally indistinguishable from uniform strings. We study public-key PRCs over fixed alphabets against adversarial deletions, where the deletion channel may both depend on the public encoding key and the transmitted codeword. Let γ_q^LCS denote the asymptotic normalised longest-common-subsequence length of two independent uniform q-ary strings. We prove that for every fixed q≥2 no multi-message public-key PRC with a single-output decoder is robust against all such δ-deletion channels for any δ>1−γ_q^LCS. For q=2, the current rigorous bound γ_2≥0.792665992 rules out every constant δ>0.207334008. The proof uses pseudorandomness only to transfer an LCS event from uniform strings to independently sampled codewords and therefore also the resulting collision argument is information-theoretic and requires no secret key. We also extend the argument to list decoding: for every fixed constant L, provided the message space contains at least L+1 messages, no such PRC with output lists of size at most L is robust for δ>1−γ_2^(L+1). Since γ_2^(m)=1/2+Θ(1/√m), these thresholds approach 1/2. Our bounds are specific to public-key-dependent adversarial channels and do not apply to oblivious edit channels.
ER -