Paper 2026/2179

Capacity-Approaching Pseudorandom Code for Stochastic Edit Channels

Leshui Wang, Tokyo Institute of Technology
Kenji Yasunaga, Tokyo Institute of Technology
Abstract

Pseudorandom codes (PRCs) are error-correcting codes whose codewords are computationally indistinguishable from uniformly random strings to any efficient adversary. We study public-key multi-bit PRCs over the stochastic memoryless binary substitution-insertion-deletion channel and its $q$-ary generalization. Here $P_i,P_d$ are the insertion and deletion probabilities, and $P_s$ is the substitution probability conditional on transmission. We first show that the majority-based construction of Christ and Gunn yields a binary PRC with vanishing rate that recovers the transmitted message with overwhelming probability whenever $P_i+P_d<1$ and $P_s<1/2$. We then use this binary PRC to protect control information in a high-rate, uniquely decodable PRC over an unbounded family of constant-size alphabets. For fixed channel parameters satisfying $P_i+P_d<1$ and $P_s<1$, its decoder recovers the transmitted message with overwhelming probability. The alphabet size may depend on the channel parameters and desired rate gap, but not on the security parameter. As the gap tends to zero and the alphabet grows through the supported sizes, the rate approaches the capacity upper bound obtained by revealing insertion and deletion locations to the receiver. The constructions use the assumptions underlying the Christ--Gunn public-key PRC and secure pseudorandom generators.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Pseudorandom codesstochastic edit channelssynchronization errors
Contact author(s)
wang l e512 @ m isct ac jp
yasunaga @ comp isct ac jp
History
2026-10-28: revised
2026-09-23: received
See all versions
Short URL
https://ia.cr/2026/2179
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2179,
      author = {Leshui Wang and Kenji Yasunaga},
      title = {Capacity-Approaching Pseudorandom Code for Stochastic Edit Channels},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2179},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2179}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.