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. 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
-
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}
}