High-Rate Public-Key Pseudorandom Codes for Edit Errors

Computer Science > Cryptography and Security [Submitted on 19 May 2026] High-Rate Public-Key Pseudorandom Codes for Edit Errors Shengtang Huang, Xin Li, Songtao Mao, Zhaienhe Zhou Pseudorandom codes (PRCs), introduced by Christ and Gunn (CRYPTO '2024), are error-correcting codes whose codewords are computationally indistinguishable from uniformly random strings, while still being decodable by someone holding the key. They provide a natural primitive for robust and undetectable watermarking, particularly in applications to AI-generated content. Although recent works have obtained strong results for substitution errors, the edit-error setting remains much less understood, especially in the high-rate regime and over small alphabets. We study public-key pseudorandom codes against edit errors. First, we give a new reduction showing that binary zero-bit PRCs robust against a constant fraction of substitution errors can be transformed into binary zero-bit PRCs robust against edit errors. Consequently, under any assumption that yields zero-bit Hamming-robust PRCs, one also obtains zero-bit PRCs for edit channels, albeit only for the weaker class of sublinear polynomial edit channels, namely channels with edit error rate 1/n^{\gamma} for any constant \gamma>0. In the high-rate regime, we construct public-key PRCs with rate arbitrarily close to 1 over sufficiently large constant alphabets, and with rate arbitrarily close to 1/2 over the binary alphabet. Moreover, if we allow the alphabet size to be \mathrm{poly}(\lambda), where \lambda is the security parameter, then our public-key PRCs can attain the Singleton bound for insertion-deletion channels. Taken together, these results yield the first high-rate public-key binary PRC constructions for edit channels, under the same assumption that yields zero-bit Hamming-robust PRCs. Subjects: Cryptography and Security (cs.CR) Cite as: arXiv:2605.19402 [cs.CR]   (or arXiv:2605.19402v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2605.19402 Focus to learn more Submission history From: Shengtang Huang [view email] [v1] Tue, 19 May 2026 05:57:25 UTC (55 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-05 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)