A Public-Key-Dependent Adversarial-Deletion Ceiling for Fixed-Alphabet Multi-Bit Pseudorandom Codes

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/sqrt m), these thresholds approach 1/2. Our bounds are specific to public-key-dependent adversarial channels and do not apply to oblivious edit channels.