Paper 2026/2179

Capacity-Approaching Pseudorandom Code for Stochastic Edit Channels

Abstract

Pseudorandom codes (PRCs) are error-correcting codes whose codewords are computationally indistinguishable from uniformly random strings to any efficient adversary. Most prior PRC work focuses on Hamming error channels; nevertheless, the few proposed constructions on edit channels are not optimized for a stochastic channel with both Hamming and synchronization errors. We study PRC over a stochastic memoryless Binary Substitution-Insertion-Deletion (BSID) channel and its generalized $q$-ary version. At each current input symbol, the channel inserts a uniformly random symbol without advancing with probability $P_i$, deletes and advances with probability $P_d$, or transmits and advances otherwise; a transmitted symbol is then replaced uniformly by another alphabet symbol with probability $P_s$. We first prove that the majority based PRC construction of Christ and Gunn remains robust over the BSID channel whenever $1-P_i-P_d>0$ and $P_s<1/2$, by proving its majority decoding after the BSID channel recovers more than half of the original coordinates by a constant margin with overwhelming probability. Then we propose a unique-decodable public-key multi-bit PRC on a constant alphabet constructed by letting the Christ--Gunn majority component protect control information and the Haeupler--Shahrasbi synchronization/list-recovery construction encodes the high-rate payload. For every sufficiently large admissible constant alphabet q depending on the channel parameters, the PRC is robust against a q-ary SID channel bounded by $P_i+P_d<1$, $P_s<$1, and its rate approaches the genie-aided capacity upper bound of the channel when q approaches infinity.