High-Rate Public-Key Pseudorandom Codes for Edit Errors Shengtang Huang∗
Xin Li†
Songtao Mao‡
Zhaienhe Zhou§
arXiv:2605.19402v1 [cs.CR] 19 May 2026
Abstract Pseudorandom codes (PRCs), introduced by Christ and Gunn (CRYPTO ’2024), are errorcorrecting 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γ for any constant γ > 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 poly(λ), where λ 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.
∗ [email protected], School of the Gifted Young, University of Science and Technology of China. Work done in part while visiting Johns Hopkins University. † [email protected], Department of Computer Science, Johns Hopkins University. ‡ [email protected], Department of Computer Science, Johns Hopkins University. § [email protected], School of the Gifted Young, University of Science and Technology of China. Work done in part while visiting Johns Hopkins University.
Contents 1 Introduction 1.1 Main Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Technical Overviews . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Open Problems and Discussions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Paper Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 2 4 9 9
2 Preliminaries 2.1 Metric and Channel Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Pseudorandom Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Cryptographic Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Pseudorandom Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9 10 10 11 12
3 Zero-Bit Public-Key Edit PRCs 3.1 CGK Embedding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Detailed Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Analysis of Algorithm 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13 13 16 17
4 Generic Reduction to Zero-Bit 4.1 Building Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Detailed Construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Analysis of the Algorithm 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
21 21 22 24
5 Constant-Alphabet PRCs with Rate Close to 1 5.1 Synchronization Strings and Self-Matching . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Construction of the Seeded Payload Code . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Analysis of Algorithm 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Instantiating the Generic Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . .
28 29 30 32 33
6 Binary PRCs with Rate Close to 1/2 6.1 Seeded High-Rate Binary Insdel Code . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Amplification of Robustness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3 Binary Payload Code and Put Together . . . . . . . . . . . . . . . . . . . . . . . . .
35 35 36 43
1
Introduction
The rapid spread of AI-generated content has made reliable provenance identification increasingly important. A natural approach is watermarking: embedding a hidden signal into generated content so that its origin can later be verified. For such a watermark to be useful, it should satisfy two basic requirements. First, it should provide undetectability: even an efficient adversary making many adaptive queries cannot distinguish the watermarked model from the original one. In particular, watermarking should cause no computationally detectable degradation in output quality. Second, it should provide robustness: given the secret key, the hidden signal should remain efficiently detectable even after the generated content has been modified. Reconciling these two requirements is the central challenge of watermarking. Starting with [Aar22, KGW+ 23], a growing line of work has explored watermarking schemes for generative models, including approaches based on modifying the randomness used during generation [CGZ24, ZALW24, KGW+ 24, KTHL24, FGJ+ 25]. These works pursue different notions of watermarking and different trade-offs between quality and robustness, and together they highlight the difficulty of achieving both strong undetectability and strong robustness simultaneously. A recent cryptographic approach to this problem is based on pseudorandom codes (PRCs), introduced by Christ and Gunn [CG24]. Informally, a PRC is a keyed error-correcting code whose codewords are computationally indistinguishable from uniformly random strings to any efficient observer without the decoding key, while still being decodable by someone holding the key even after the codeword has been corrupted. In addition to robustness and pseudorandomness, PRCs satisfy a soundness property: strings unrelated to genuine codewords should decode to ⊥ except with negligible probability. These properties make PRCs a natural primitive for building watermarks that are both robust and undetectable. Since their introduction, pseudorandom codes have been studied from several complementary directions. On the positive side, prior works have given constructions under a range of assumptions, clarified their connections to watermarking and related cryptographic primitives, strengthened robustness guarantees in the substitution-error setting, and developed stronger security notions such as adaptive robustness, ideal security, and CCA-style security [GM24, GG25, AAC+ 25, CGG+ 25]. They have also led to concrete watermarking applications for images, video, and other generative models [ZGC+ 25, GZS25, CHS25]. On the negative side, recent works have established strong black-box barriers, showing that PRCs tolerating a constant error rate cannot, in general, be based solely on generic cryptographic primitives [GGW25, DMR25]. Together, these results suggest that PRCs form a rich and subtle primitive at the intersection of coding theory, cryptography, and watermarking. For edit errors (insertions, deletions, and substitutions), however, the picture is substantially more challenging. Insertions and deletions destroy synchronization, so one must cope not only with corrupted symbols but also with the loss of alignment. Despite recent progress, the theory of pseudorandom codes under edit errors remains far from satisfactory. The original work of [CG24] handled only a constant fraction of random substitutions and deletions. Golowich and Moitra [GM24] obtained a public-key PRC robust to a constant fraction of edit errors, but over a polynomial-sized alphabet, which translates to a substantially stronger entropy requirement in watermarking applications. More recently, Christ, Golowich, Gunn, Moitra and Wichs [CGG+ 25] gave the first binary-alphabet PRC robust to a constant fraction of edit errors, but only in the secret-key setting and under the less standard permuted codes conjecture. Moreover, both [GM24] and [CGG+ 25] construct only zero-bit PRCs in the edit-error setting. In summary, to the best of our knowledge, prior to this work there was no public-key PRC for adversarial edit channels over any constant-sized alphabet, or any compelling high-rate public-key PRC for edit channels. 1
From the application side, edit errors naturally model transformations that arise in modern AI pipelines, including paraphrasing, rewriting, cropping, and other operations that disrupt synchronization [KSK+ 23, SKB+ 23, QZT+ 25, KKR+ 24, SZL+ 24, ASG+ 19]. This is especially relevant because such transformations are often exactly the kinds of post-processing steps an adversary, editor, or downstream system may apply to generated content. Moreover, in watermarking applications, the relevant efficiency parameter is not only a quantitative concern but also affects applicability. In PRC-based watermarking, the codeword is used to drive the sampling randomness of the generative process, and detection requires recovering a noisy version of this codeword from the generated content. Thus, highly redundant or low-rate constructions may require longer or higher-entropy outputs before enough of the embedded structure can be recovered and decoded, which can significantly restrict applicability in low-entropy regimes [KTHL24, FGJ+ 25]. Thus, constructing edit-robust PRCs with high rate is a central goal both theoretically and in practice. In this work, we develop a general framework for high-rate public-key pseudorandom codes for edit channels over constant-sized alphabets. In particular, we give the first construction of a public-key binary zero-bit PRC with suitable edit robustness, and then use it as a building block to obtain high-rate public-key PRCs over small alphabets.
1.1
Main Results
We first introduce the channel notions and assumptions used in our results. Definition 1.1. Let p ∈ (0, 1). A channel E : Σ∗ → Σ∗ is called a p-bounded substitution (edit) channel if, for every string x ∈ Σn , E(x) differs from x in at most pn substitutions (respectively, is within edit distance at most pn from x). The related p-bounded insertion-deletion channel only allows at most pn insertions and deletions. A channel E : Σ∗ → Σ∗ is called a sublinear polynomial substitution (edit) channel if there exists a constant 0 < c < 1 such that, for every string x ∈ Σn , E(x) differs from x in at most n1−c substitutions (respectively, is within edit distance at most n1−c from x). Assumption 1.2 (Informal version of Assumption 2.5, [CG24]). At least one of the following holds: √
• Subexponential LPN: LPN is hard for every 2O( n) -time adversary; • Polynomial LPN + planted XOR: Both LPN and XOR are hard for every polynomial-time adversary. We stress that this is the same assumption that yields zero-bit Hamming-robust PRCs, and in fact, for our constructions we can use any such assumption. We begin by showing how to obtain zero-bit PRCs that are robust to edit errors from zerobit PRCs over the binary alphabet that are robust to substitution errors. This yields a generic reduction from Hamming robustness to edit robustness, at the cost of a subpolynomial loss in the tolerable error rate. Theorem 1.3 (Reduction from Hamming to edit PRCs, informal version of Theorem 3.1). Let PRCh be a binary zero-bit public-key (resp., secret-key) PRC that is robust against every p-bounded substitution channel for some constant p > 14 . Then there exists a zero-bit public-key (resp., secretkey) PRC over the binary alphabet that is robust against every sublinear polynomial edit channel. Combining Theorem 1.3 with the zero-bit Hamming PRC construction of [CG24] under Assumption 1.2, we obtain the following corollary.
2
Corollary 1.4 (Binary zero-bit edit PRC, informal version of Theorem 3.2). Under Assumption 1.2, there exists a binary zero-bit public-key (secret-key) PRC that is robust against every sublinear polynomial edit channel. We note that this gives the first edit-robust public-key zero-bit PRC over the binary alphabet. Starting from the zero-bit construction above, we then develop a general framework for boosting the rate. Our next result shows that, over a larger alphabet, one can obtain pseudorandom codes with rate arbitrarily close to 1 while still tolerating either a constant fraction of edit errors or a sublinear polynomial number of edit errors, depending on the underlying zero-bit PRC. Theorem 1.5 (Multi-bit to zero-bit reduction, informal version of Corollary 5.8). For every sufficiently small ε > 0 and every alphabet Σ with |Σ| ≥ poly(1/ε), the following holds. If there exists a zero-bit public-key (resp., secret-key) PRC over Σ that is robust against every pbounded edit channel (resp., sublinear polynomial edit channel), then there exists a public-key (resp., secret-key) PRC over the same alphabet Σ with rate 1 − ε that is robust against every p′ -bounded edit channel (resp., sublinear polynomial edit channel) for some p′ = Ω(min{p, ε}). We then plug in different zero-bit PRC constructions to obtain: Corollary 1.6 (PRC with rate close to 1, informal version of Corollaries 5.9 and 5.10). For every sufficiently small constant ε > 0 and any security parameter λ ∈ N, there exist public-key PRCs with rate 1 − ε such that: • Over alphabets of size poly(λ, 1/η), for any constant 0 < η < 1, that are robust against every (ε − η)-bounded edit channel, under the same cryptographic assumptions as [GM24] (local weak PRFs). • Over alphabets of size poly(1/ε) that are robust against every sublinear polynomial edit channel, under Assumption 1.2. In particular, we formulate the first item for Insdel channels because in that setting the achieved tradeoff is essentially optimal: it matches the Singleton bound. Finally, by instantiating our framework with binary zero-bit PRCs, we obtain a binary construction with positive constant rate. In particular, we achieve rate arbitrarily close to 1/2 while retaining robustness against a sublinear polynomial number of edit errors. Theorem 1.7 (Binary PRC with rate close to 1/2, informal version of Theorem 6.13). For every security parameter λ > 0 and every sufficiently small ε > 0, the following holds. If there exists a zero-bit public-key (resp., secret-key) binary PRC that is robust against every p-bounded edit channel (resp., sublinear polynomial edit channel), then there exists a public-key ′ -bounded edit channel (resp., secret-key) binary PRC with rate 1/2 − ε that is robust po against n every 3 ε (resp., sublinear polynomial edit channel), for some p′ = Ω min p, log(1/ε) . Corollary 1.8 (Informal version of Corollary 6.14). Under Assumption 1.2, we have binary publickey PRCs with rate 1/2 − ε that are robust against every sublinear polynomial edit channel. For comparison, we summarize prior PRC constructions together with our results in Table 1.
3
Work
Rate
Alphabet
Error type
Error bound
PK/SK
Assumptions
[CG24]
constant
binary
substitution / random deletion
O(n)
PK / SK
LPN or LPN+XOR
[GM24]
zero-bit
poly(λ)
edit
O(n)
PK
Local weak PRFs
[GG25]
zero-bit
binary
substitution
O(n)
PK
Planted hyperloop,
[GG25]
zero-bit
binary
substitution
O(n)
PK
Weak planted XOR
[GG25]
zero-bit
binary
substitution
O(n)
SK
Unconditional (against polytime, space-bounded adversaries)
[AAC+ 25]
constant
binary
substitution
O(n)
PK / SK
LPN or LPN+XOR; random oracle for CCA-security
[CGG+ 25]
constant
binary
edit
O(n)
SK
Permuted codes conjecture
Corollary 1.4
zero-bit
binary
edit
O(n1−c )
PK / SK
LPN or LPN+XOR
Corollary 1.6
1−ε
poly(λ)
edit
O(n)
PK / SK
LPN or LPN+XOR
Corollary 1.6
1−ε
poly(1/ε)
edit
O(n1−c )
PK / SK
LPN or LPN+XOR
Corollary 1.8
1 2 −ε
binary
edit
O(n1−c )
PK / SK
LPN or LPN+XOR
Table 1: Comparison of prior PRC constructions and our new edit-robust PRCs. n is the codeword length of PRCs, and λ is the security parameter. Let c ∈ (0, 1) be any constant. For the precise LPN and LPN+XOR assumptions, see Assumption 2.5.
1.2
Technical Overviews
In our later proofs, we work with insertion-deletion (Insdel) errors only, without allowing substitutions. This is without loss up to a factor of 2, since each substitution can be simulated by one deletion and one insertion. A key difficulty in constructing PRCs for edit errors is that one can no longer directly apply sparse parity checks, which are naturally resistant to Hamming errors and therefore have been used extensively in Hamming-robust (public-key) PRC constructions. Sparse parity checks are also closely related to linear codes and make it easy to derive the pseudorandom property from wellestablished hardness assumptions such as LPN and planted XOR. However, sparse parity checks break down completely in the edit-error setting, since even a single edit operation can cause shifts in the entire codeword, and thus the operation does not need to affect the exact index involved in the parity check in order to corrupt it. One natural approach would then be to transform a Hamming-robust PRC into an edit-robust PRC, for example by attempting to attach a synchronization string [HS21] to a Hamming-robust PRC. This approach has been very successful in transforming standard codes for Hamming errors to codes for edit errors. However, in the setting of PRCs, it is unclear how to choose the syn4
chronization string. On the one hand, if we use a fixed synchronization string, then part of the codeword remains identical across different queries, which violates the pseudorandom property. On the other hand, random strings are also good synchronization strings, so one can try to use random strings here. However, then the encoder would need to share with the decoder the randomness used to generate the synchronization string, which requires an edit-robust PRC in the first place. Indeed, to overcome this, the work of [GM24] needs to use a polynomial-sized alphabet to record the index, together with some extra effort to make it pseudorandom. Constructing public-key edit-robust PRCs poses additional challenges. The construction in [CGG+ 25] appears difficult to adapt to the public-key setting, because it relies on randomly permuting the indices and alphabet during code generation to make it edit-robust. These permutations must be used during encoding, and therefore in the public-key setting would need to be included in the public key. However, once they are revealed to the adversary, the Permuted Code assumption used in the pseudorandomness proof no longer seems applicable. In this paper, we present a novel approach that indeed transforms a Hamming-robust PRC into an edit-robust PRC. In addition, our transformation preserves the alphabet size and the public-key security of the Hamming-robust PRC. We describe the details below. Zero-bit public-key edit PRCs over binary alphabet. The crucial tool we use here is an embedding from edit distance to Hamming distance. Specifically, the CGK embedding [CGK16] is a randomized mapping Emb that transforms edit distance into Hammingdistance with quadratic distortion: for strings x, y with edit distance k, ∆H Emb(x, r), Emb(y, r) = O(k 2 ) with constant probability over the randomness of r. Furthermore, this function is reversible. Given an embedding string e and the random seed r, we can recover x = Emb−1 (e, r). To construct a zero-bit edit-robust PRC, we start from a Hamming-robust PRCh (e.g., from [CG24, GG25]) that tolerates a (1/4 + ε) fraction of substitution errors. The high level idea is that we want to use the CGK embedding to map our edit-robust PRC codewords to codewords in the Hamming-robust PRC. This suggests the following encoding and decoding procedure for a single-block construction: • We first generate the public/secret key pair (pkh , skh ) via the key generator of PRCh , and also sample a random seed r in the public key for the CGK embedding. • For encoding, first compute a Hamming codeword a ← Ench (1λ , pkh , 1), and then output an edit-robust PRC codeword y = Emb−1 (a, r). • For decoding, the decoder takes the received string y ′ and computes â = Emb(y ′ , r). If Dech (skh , â) = 1, it outputs 1, otherwise ⊥. However, one issue with the above is that in the second step, not every binary string is a valid embedding under seed r, hence we may not be able to find such a y = Emb−1 (a, r). To address this, we “project” a to a valid embedding b under seed r and output y = Emb−1 (b, r) instead. Note that the CGK embedding is generated by a random walk on the input indices, and copying the bits of the input string to bits of the output string at corresponding indices. At each step of the random walk, with probability 1/2 it stays at the same index and with probability 1/2 it moves to the next index. Whenever the walk stays at the same index, the corresponding output bits must be consistent, because they come from the same input bit. If a violates this, then a is not a valid embedding, but we can repair it by flipping the conflicting bits. We show that doing this will add at most 1/4 fraction of Hamming errors, which is still fine because the Hamming-robust PRC can tolerate any (1/4 + ε) fraction of substitution errors. 5
For pseudorandomness, the key observation here is that for any fixed r, if we first “project” a to a valid embedding b under r and then set y = Emb−1 (b, r), this process actually induces an injective mapping from the indices of y to those of a, that is, each coordinate of y is determined by a distinct coordinate of a. Hence, when a is a uniformly random string, y is also distributed uniformly. Consequently, by the pseudorandomness of PRCh , the Hamming code a is computationally indistinguishable from uniform, and thus the resulting edit codeword y is also computationally indistinguishable from uniform. Note that the above reasoning holds for any fixed r, so r can be made public and treated as part of the public key. The above single-block construction works whenever the CGK embedding succeeds, but the embedding succeeds only with constant probability. To amplify, we take ℓ = poly(n) independent copies, where n is the length of each block. Each copy uses independent keys and seeds, and the final codeword is the concatenation y = y1 ◦ · · · ◦ yℓ . Edit errors may shift block boundaries, but because this is a zero-bit PRC, which has only one possible message, for decoding we only need to hit a single good block. The decoder enumerates all substrings of the received string via a sliding window, treating each substring as a candidate block. By Markov’s inequality at least a constant fraction of the blocks suffer few edit errors. For such a good block the distortion bound guarantees that â = Emb(y ′ , r) lies within the Hamming correction radius with constant probability. Since the blocks are independent, the probability that no good block succeeds is at most Θ(1)Θ(ℓ) = negl(λ). Finally, note that for sublinear polynomial edit channels, choosing the final codeword length appropriately allows us to tolerate any polynomially bounded sublinear number of edits. Combining these ingredients yields a zero-bit public-key PRC that is robust to any sublinear polynomial edit channel, under exactly the same cryptographic assumptions required for the underlying Hamming PRC. Building high-rate PRCs via randomly interleaving seed markers. The main challenge in turning a zero-bit PRC into a high-rate PRC is that the decoder must recover not only whether a codeword is present (which is enough for a zero-bit PRC), but also enough of the encoder’s randomness to decode the actual payload. In particular, in LPN-based constructions, merely knowing the parity-check matrix is no longer sufficient. This forces us to introduce an additional payload code, together with extra random or pseudorandom masking to hide its structure. To avoid sacrificing the rate too much, however, we can afford to use only a short truly random seed. Our solution is to protect this short seed using the zero-bit PRC, and then expand it via a pseudorandom generator so that the resulting pseudorandom bits mask the payload code and make the overall codeword look pseudorandom. In [CG24], this issue is addressed by using a codeword of the form PRCλ (s) ◦ PRG(s) ⊕ c , where c is the payload codeword carrying the message information, s ∈ {0, 1}λ is a short random seed, and PRCλ (s) is an encoding of s built from a zero-bit PRC. Concretely, each bit of s is represented by either a genuine zero-bit PRC codeword, indicating that the bit is 1, or by an independent uniform string, indicating that the bit is 0. In this way, the decoder can first recover s from PRCλ (s), and then use PRG(s) to unmask the payload part PRG(s) ⊕ c. However, this basic structure is fragile under adversarial errors: the protected seed part PRCλ (s) is much shorter than the payload part; consequently, an adversary may concentrate many of the allowed errors on PRCλ (s) without violating the overall error budget, causing the recovery of s to fail and thus breaking the entire decoding procedure. To address this issue, [CG24] introduced two additional layers of randomization: a random permutation π over the coordinates and an additive mask z. Together, these ensure that both the 6
locations of the blocks in PRCλ (s) and the symbols themselves are uniformly distributed. As a result, for any fixed error channel, the corruption is spread nearly evenly across the different parts of the codeword, so that with probability 1 − negl(λ), every individual part incurs only a small fraction of the total errors. For edit errors, however, this approach no longer applies directly, because insertions and deletions destroy synchronization. While a random permutation can easily hide the positions of the protected blocks, it becomes much harder to recover those positions once insertions and deletions have shifted the coordinates. Similarly, a global mask is difficult to remove without first recovering the correct alignment, since one must know which received symbol corresponds to which original position. To solve these two issues, we use the following two methods: • To locate and recover the zero-bit PRC codewords, we insert each entire zero-bit codeword into the payload string as a contiguous block, rather than partitioning it into smaller pieces. The insertion locations of the different zero-bit codewords are sampled uniformly at random, subject to the constraint that the corresponding intervals are pairwise disjoint. The decoder first searches over all candidate intervals in the received word and attempts to recover each zero-bit PRC block separately. However, this interleaving alone does not guarantee that every block can be decoded with high probability. For example, if the edit channel concentrates a constant fraction of its deletions on one interval, then any zero-bit PRC block inserted there may be heavily corrupted, causing the corresponding seed bit to be decoded incorrectly. In general, we can only expect that a constant fraction of the zero-bit PRC blocks are recovered correctly. To overcome this, we add an additional layer of binary Hamming coding: instead of embedding the seed s directly, we first encode it with a binary error-correcting code and then protect the resulting bits using the zero-bit PRC blocks. This ensures that the encoder’s random seed s can still be recovered even if some of the zero-bit PRC blocks fail to decode. In addition, we append a suffix of 1’s to the seed encoding, which serves as a validation string and prevents confusion between genuine encodings of zero-bits and null codewords, that is, random strings not generated using the public key pk. • To prevent the adversarial channel E from exploiting statistical information about the codeword in order to target specific parts of the encoding, we also need the final codeword distribution to be uniform and independent of the encoding procedure. To achieve this, we require that the zero-bit PRC codewords are independently and uniformly distributed over the randomness of the public key pk and the encoder. For the payload part, instead of applying a single global mask, we mask the output of PRG(s) directly. Thus, once the seed s is recovered, the corresponding mask can also be removed. These two components are independent, and consequently the channel cannot gain any statistical advantage from the encoding procedure when deciding how to corrupt the codeword. After recovering s, the inserted PRCλ blocks can be viewed simply as additional insertions, whose total contribution is only an o(1) fraction of the overall codeword length. Therefore, if the underlying channel introduces a p fraction of edit errors and the payload code can tolerate a p + ε fraction of edit errors for some constant ε > 0, then the original message can still be recovered correctly. High-rate code via synchronization strings. Given the reduction above, it remains to instantiate the payload code with a randomly encoded code that is robust to insertion-deletion errors
7
(insdel errors for short). For this purpose, we use a standard synchronization-string-based construction of insdel codes [HS21]. A key fact, noted in [HS21], is that for every sufficiently small constant ε > 0, a uniformly random string is ε-self-matching with probability 1 − exp(−Ω(n)). This is exactly the level of reliability we need, since in our application the decoding guarantee must hold with probability 1 − negl(n). To make the construction both uniform and pseudorandom, we split the seed s into two parts, say s = (s1 , s2 ). The first part is used to generate the synchronization string through PRGsyn (s1 ), while the second part is used to generate the masking string through PRGmsg (s2 ), which hides the payload codeword and makes the overall encoding pseudorandom. In addition, we apply public shift vectors to both components. Thus, conditioned on the public shifts, each component is uniformly distributed, while the decoder can still recover them once the seed is reconstructed. The role of the synchronization string is to convert insdel errors into ordinary symbol corruptions after alignment. Concretely, suppose σ ′ is the synchronization string embedded in the codeword, and σ̃ ′ is its corrupted version after at most k insdel errors. If σ ′ is ε-self-matching, then the synchronization algorithm of [HS21] produces an approximate matching between positions of σ ′ and positions of σ̃ ′ . After placing the matched symbols into their intended coordinates and treating √ unmatched positions as erasures, the misalignment introduces at most k +3 εn corrupted or erased positions in total. In other words, once synchronization succeeds, the insdel channel is reduced to √ a Hamming-type error pattern with only an additional 3 εn loss beyond the original k edits. Finally, we use a standard algebraic-geometry code as the base code in the synchronizationstring construction. We choose it to have sufficiently high rate and a sufficiently large alphabet so that appending the synchronization string incurs only a negligible loss in the overall rate. High-rate binary code via concatenation with random linear inner code. The approach with synchronization string discussed above no longer works well in the binary setting, since the synchronization needs a sufficiently large (albeit constant-sized) alphabet. More generally, in the theory of binary insdel codes, one typically relies on concatenation in order to obtain efficiently decodable constructions. To address the synchronization problem, many prior works insert long runs of 0’s between adjacent inner codewords, using these buffers as additional markers for the decoder, such as the Schulman-Zuckerman code [SZ02] and its subsequent improvements [GL16, GW17]. Another approach is to append additional redundancy derived from a document exchange protocol, as in [CJLW18]. However, such additional markers are not only easy for the decoder to identify, but also easy for an adversarial distinguisher to detect, and therefore they destroy pseudorandomness. In our construction, we use the insdel binary code in [CJL+ 23], which does not rely on any additional markers. Instead, the construction uses different inner codes for different blocks. For our purposes, these inner codes do not need to be fixed in advance to satisfy any particular structural property; instead, independently sampled random linear codes already suffice. Moreover, since the randomness specifying the inner codes is generated as PRG(s) ⊕ z, where z is the public shifting vector, the resulting codeword is naturally uniformly distributed over the randomness of z. The only issue with this construction is that, in order to maintain both high rate and efficient decoding, the inner codeword length is only Θ(log n), since the decoding guarantee for each inner code is obtained by brute force over logarithmic-length blocks. As a result, randomly chosen inner codes are good with probability only 1 − 1/poly(n), rather than with probability 1 − negl(n). To overcome this, we introduce an additional layer of concatenation, using nβ such seeded codewords as building blocks for some 0 < β < 1. This amplifies the probability that the overall construction is good from 1 − 1/poly(n) to 1 − negl(n). The decoder still proceeds hierarchically, from the inner
8
level to the outer level, and by choosing the parameters appropriately, we ensure that the final decoding succeeds with required probability.
1.3
Open Problems and Discussions
Our reduction based on the CGK embedding has the advantage that it does not require any additional cryptographic assumptions beyond those already needed for the underlying Hammingrobust PRC. However, it only yields robustness against a sublinear polynomial fraction of edit errors, because the CGK embedding maps k edit errors to roughly k 2 Hamming errors. This quadratic loss is inherent to the CGK approach and cannot, in general, be improved, even in average-case settings. It is therefore an important open problem to find a different reduction from edit robustness to Hamming robustness with substantially smaller distortion. Such a reduction could plausibly lead to public-key PRCs of constant rate against constant-fraction edit channels. Another important direction is to identify compelling computational assumptions under which one can construct public-key pseudorandom codes that are directly robust to edit errors. At present, known constructions of edit-robust PRCs either proceed by reducing edit robustness to Hamming robustness, as in our work and [GM24], or else obtain edit robustness only in the secretkey setting under less standard assumptions, such as in [CGG+ 25]. It is therefore a natural open problem to formulate and justify assumptions that directly support public-key edit-robust PRCs. Such assumptions could lead to conceptually simpler constructions and potentially to stronger guarantees, such as constant rate over small alphabets against a constant fraction of edit errors.
1.4
Paper Organization
In Section 2, we review the necessary preliminaries. In Section 3, we apply the CGK embedding to construct a binary zero-bit public-key PRC that is robust against every sublinear polynomial edit channel, thereby proving Theorem 1.3. In Section 4, we develop a general black-box framework for transforming a zero-bit PRC into a higher-rate PRC. In Section 5, we instantiate this framework using a synchronization-string-based payload code to prove Theorem 1.5. Finally, in Section 6, we combine the framework with our binary concatenation-based payload code to prove Theorem 1.7.
2
Preliminaries
For an integer n ∈ N, we write [n] := {1, 2, . . . , n}. For a string x ∈ Σ∗ over an alphabet Σ, let |x| denote its length. For i ∈ [|x|], let xi be the i-th symbol. For an interval I = [i, j] (1 ≤ i ≤ j ≤ |x|), let xI or x[i:j] denote the substring xi xi+1 · · · xj . For strings x, y, we write x ◦ y for concatenation. We write Un (Σ) for the uniform distribution over Σn . When the alphabet Σ is clear in the context, we may abbreviate it as Un . Unless otherwise stated, all algorithms are probabilistic polynomial time (PPT). We write y ← A(x) for running a randomized algorithm A on input x and outputting y. We write x ← Ω or x ← D for sampling x uniformly from a finite set Ω or from a distribution D, respectively. A function negl : N → R≥0 is negligible if for every constant c > 0 there exists N such that negl(n) ≤ n−c for all n ≥ N . Lemma 2.1 (Hoeffding’s inequality). Let X1 , . . . , Xn be independent random variables such that Xi ∈ [ai , bi ]. Let X = X1 + · · · + Xn and µ = E[X]. Then for any t > 0, we have 2t2 Pr[|X − µ| ≥ t] ≤ 2 exp − Pn . 2 i=1 (bi − ai ) 9
2.1
Metric and Channel Models
We measure errors using either Hamming distance or edit distance. • For two strings x, y ∈ Σn of equal length, the Hamming distance ∆H (x, y) is the number of positions at which they differ. • For two strings x ∈ Σn and y ∈ Σ∗ of possibly different lengths, the edit distance ∆E (x, y) = |x|+|y|−2·LCS(x, y) is the minimum number of insertions and deletions required to transform x into y, where LCS(x, y) is the length of the longest common subsequence between x and y. This definition differs slightly from the classical edit distance: substitutions are not allowed, or equivalently, each substitution is counted as two operations. This formulation is chosen for technical convenience in our analysis and proofs. Definition 2.2 (p(·)-bounded channels). Let p : N → [0, 1] be a function. • A channel E : Σ∗ → Σ∗ is called a p(·)-bounded Hamming channel if for every input x ∈ Σ∗ , the output x′ = E(x) satisfies |x′ | = |x| and ∆H (x, x′ ) ≤ p(|x|) · |x|. • A channel E : Σ∗ → Σ∗ is called a p(·)-bounded edit channel if for every input x ∈ Σ∗ , the output x′ = E(x) satisfies ∆E (x, x′ ) ≤ p(|x|) · |x|. In particular, when p : N → [0, 1] is a constant function, we may abbreviate it as the p-bounded Hamming/edit channel. And when p(x) = c/xγ for some constant c > 0 and 0 < γ < 1, we also call such channel as a sublinear polynomial Hamming/edit channel. In this paper, all channels are assumed to be oblivious, namely, their error patterns are chosen independently of the sampled keys and codewords.
2.2
Pseudorandom Code
Definition 2.3 (Secret-key PRC). Let Σ be a fixed alphabet and let E : Σ∗ → Σ∗ be a channel. A secret-key pseudorandom error-correcting code (secret-key PRC) with robustness to E is a triple of randomized polynomial-time algorithms (KeyGen, Enc, Dec), together with functions ℓ, n, k : N → N, such that for every λ ∈ N, KeyGen(1λ ) ∈ {0, 1}ℓ(λ) , Enc : {1λ } × {0, 1}ℓ(λ) × Σk(λ) → Σn(λ) , Dec : {1λ } × {0, 1}ℓ(λ) × Σ∗ → Σk(λ) ∪ {⊥}, and the following conditions hold: • Robustness. For every λ ∈ N and every m ∈ Σk(λ) , h i Pr Dec(1λ , sk, E(x)) = m : x ← Enc(1λ , sk, m) ≥ 1 − negl(λ). sk←KeyGen(1λ )
• Soundness. For every fixed c ∈ Σ∗ , Pr Dec(1λ , sk, c) = ⊥ ≥ 1 − negl(λ). sk←KeyGen(1λ )
10
• Pseudorandomness. For any probabilistic polynomial-time adversary A, Pr
sk←KeyGen(1λ )
Enc(1λ ,sk,·) λ A (1 ) = 1 − Pr AU (1λ ) = 1 ≤ negl(λ), U
where U is an oracle that answers each query with an independent uniform sample from Σn(λ) . Definition 2.4 (Public-key PRC). Let Σ be a fixed alphabet and let E : Σ∗ → Σ∗ be a channel. A public-key pseudorandom error-correcting code (public-key PRC) with robustness to E is a triple of randomized polynomial-time algorithms (KeyGen, Enc, Dec), together with functions ℓpk , ℓsk , n, k : N → N, such that for every λ ∈ N, (pk, sk) ← KeyGen(1λ ) ∈ {0, 1}ℓpk (λ) × {0, 1}ℓsk (λ) , Enc : {1λ } × {0, 1}ℓpk (λ) × Σk(λ) → Σn(λ) ,
Dec : {1λ } × {0, 1}ℓsk (λ) × Σ∗ → Σk(λ) ∪ {⊥},
and the following conditions hold: • Robustness. For every λ ∈ N and every m ∈ Σk(λ) , h i Dec(1λ , sk, E(x)) = m : x ← Enc(1λ , pk, m) ≥ 1 − negl(λ). Pr (pk,sk)←KeyGen(1λ )
• Soundness. For every fixed c ∈ Σ∗ , Pr
(pk,sk)←KeyGen(1λ )
Dec(1λ , sk, c) = ⊥ ≥ 1 − negl(λ).
• Pseudorandomness. For any probabilistic polynomial-time adversary A, Pr
(pk,sk)←KeyGen(1λ )
λ AEnc(1 ,pk,·) (1λ , pk) = 1 −
Pr
(pk,sk)←KeyGen(1λ ) U
U λ A (1 , pk) = 1 ≤ negl(λ),
where U is an oracle that answers each query with an independent uniform sample from Σn(λ) . The codeword length of a (secret-key or public-key) PRC is n(λ) and the message length is k(λ). The rate is the function R(λ) := k(λ)/n(λ). We often drop the dependence on λ when it is clear from context. For both secret-key and public-key PRCs, if there is only one possible message (i.e. k(λ) = 0), we denote this unique message by 1 and say that the scheme is a zero-bit PRC.
2.3
Cryptographic Assumptions
We state the cryptographic assumptions used in [CG24] to construct PRCs robust to a constant fraction of substitution errors. Our edit PRC construction treats such Hamming PRCs as a black box. Thus, any construction of a Hamming-robust PRC, whether based on the assumptions below or on alternative assumptions (e.g., those in [GG25]), can be seamlessly integrated. No additional assumptions are required beyond those needed for the underlying Hamming PRC. Problem 1 (Learning Parity with Noise LPNg,η ). Let η ∈ (0, 1/2) be a constant and let g : N → N n×g(n) be a function. Distinguish between the following two distributions over pairs in F2 × Fn2 : 11
n×g(n)
g(n)
1. Noisy parity distribution: D0 (n, g(n), η), obtained by sampling A ← F2 , s ← F2 , e ← Ber(n, η), and outputting (A, As ⊕ e), where Ber(n, η) denotes the product Bernoulli distribution on Fn2 with parameter η. n×g(n)
2. Uniform distribution: D1 (n, g(n)), obtained by sampling A ← F2 outputting (A, u).
, u ← Fn2 , and
Problem 2 (Planted XOR XORm,t ). Let m, t : N → N be functions with m(n) = nΩ(1) and n×m(n) t(n) = Θ(log n). Distinguish between the following two distributions over matrices in F2 : n×m(n)
1. Null distribution: D0 (n, m(n)), the uniform distribution over F2
;
2. Planted distribution: D1 (n, m(n), t(n)), obtained by first sampling a random t(n)-sparse n×m(n) vector s ∈ St(n),n and then sampling a random matrix G ∈ F2 subject to s⊤ G = 0, n where St(n),n ⊆ F2 denotes the set of all vectors of Hamming weight exactly t(n). Assumption 2.5. At least one of the following holds: 1. Subexponential hardness of LPNg,η . There exist a constant η ∈ (0, 1/2) and a function √ g : N → N with g(n) = Ω(log2 n) such that no probabilistic adversary running in time 2O( n) can solve Problem 1 with non-negligible advantage. 2. Polynomial hardness of LPNg,η together with hardness of XORm,t . There exist constants η ∈ (0, 1/2) and ε ∈ (0, 1) such that: • No probabilistic polynomial-time adversary can solve Problem 1 for g(n) = nε with nonnegligible advantage. • No probabilistic polynomial-time adversary can solve Problem 2 for m(n) = 2nε and t(n) = Θ(log n) with advantage 1 − negl(n). Theorem 2.6 ([CG24, Theorem 1]). Let p ∈ (0, 1/2) be any constant. Under Assumption 2.5, there exists a zero-bit public-key (secret-key) pseudorandom code PRC = (KeyGen, Enc, Dec) against any p-bounded Hamming channel.
2.4
Pseudorandom Generators
Lemma 2.7 (Cryptographic pseudorandom generator). Suppose that one-way functions exist. Then for any polynomial ℓ(λ) > λ, there exists a deterministic algorithm PRG : {0, 1}∗ → {0, 1}∗ such that: • |PRG(s)| = ℓ(|s|) for any input s ∈ {0, 1}∗ . • For any λ ∈ N and every PPT distinguisher A, we have Pr
s←{0,1}λ
A(1λ , PRG(s)) = 1 −
Pr
A(1λ , r) = 1 ≤ negl(λ).
r←{0,1}ℓ(λ)
Throughout this paper, we fix such a pseudorandom generator PRG and use it directly whenever needed, without mentioning it explicitly each time.
12
3
Zero-Bit Public-Key Edit PRCs
In [GM24], the authors give an edit-robust PRC construction over a large alphabet, reducing edit PRC to a Hamming PRC via indexing. More recently, in [CGG+ 25], the authors give binary, constant-rate secret-key pseudorandom codes that tolerate a constant fraction of worst-case edits, based on permuted codes conjecture. In this section, we present a binary-alphabet zero-bit publickey PRC resistant to any sublinear polynomial edit errors, and do not require extra assumptions other than those required by a Hamming PRC. More precisely, we give a reduction from zero-bit edit PRC to zero-bit Hamming PRC: Theorem 3.1. Let PRCh = (KeyGenh , Ench , Dech ) be a zero-bit public-key (secret-key) PRC against any 14 + c1 -bounded Hamming channel, where c1 < 1/4 is a fixed constant. Then for any constant 0 < γ < 1/2, Algorithm 3 constructs a zero-bit public-key (secret-key) PRC against any p(·)-bounded edit channel for small enough constant c2 and p : x 7→ c2 /xγ . Combining Theorem 2.6, i.e. the constructions of Hamming PRCs in [CG24] under Assumption 2.5, we obtain that: Theorem 3.2. Under Assumption 2.5, for any 0 < γ < 1/2, there exists a zero-bit public-key (secret-key) PRC against any p(·)-bounded edit channel for small enough constant c and p : x 7→ c/xγ . The crucial tool we use here is the CGK embedding [CGK16]. We will give the description and properties of the CGK embedding and decoding functions in Section 3.1. And then show the detailed constructions of zero-bit public-key edit PRCs in Section 3.2. Finally, we prove Theorem 3.1 in Section 3.3.
3.1
CGK Embedding
The CGK embedding, originally introduced by Chakraborty, Goldenberg and Koucký [CGK16], provides a mapping from strings under edit distance to strings under Hamming distance. At a high level, the embedding performs a random walk on the index axis of the input string, which induces a partial synchronization between two input strings that are close in edit distance. This synchronization ensures that corresponding symbols in the two strings tend to be aligned in the embedding, despite insertions and deletions. As a result, the embedding maps edit distance to Hamming distance with only a quadratic distortion: two strings with edit distance k are mapped to embedded strings whose Hamming distance is O(k 2 ) with constant probability. CGK embedding. We briefly recall the idea of the CGK embedding. The embedding maps a binary string x ∈ {0, 1}L to a longer binary string by performing a randomized walk over the indices of x. At each step t, the current symbol xi is written to the output, and the index i is advanced according to a random function ht (xi ) ∈ {0, 1} derived from the shared randomness r. As a result, each input bit may be repeated multiple times in the output sequence, while the relative order of symbols is preserved. This randomized walk ensures that nearby symbols in the original string tend to remain close in the embedding. Algorithm 1 CGK Embedding Function Emb Require: L, x ∈ {0, 1}L , and r ∈ {0, 1}3L . 1: function Emb(x, r) 13
Interpret r as a description of h1 , . . . , h1.5L : {0, 1} → {0, 1} 3: Initialize i = 1 and a1∼1.5L = ⊥1.5L ▷ a1∼1.5L is the resulting string 4: for t = 1, 2, . . . , 1.5L do 5: if i ≤ L then 6: at = xi 7: i = i + ht (xi ) ▷ Update the counter i according to r 8: else 9: at = 0 ▷ Pad a with 0 if the counter i overflows 10: end if 11: end for 12: return a 13: end function 2:
The CGK embedding function has a nice property: it can guarantee a quadratic distortion with constant probability over the randomness of r: Lemma 3.3 (Modified from [CGK16, Theorem 4]). Let Emb : {0, 1}L × {0, 1}3L → {0, 1}1.5L be the embedding mapping computed by Algorithm 1. Then for every positive constant c and every √ x, y ∈ {0, 1}L , ∆H (Emb(x, r), Emb(y, r)) ≤ c · (∆E (x, y))2 with probability at least 1 − 6/ c over the randomness of r. Remark 3.4. (1) The original proof in [CGK16] is for the case that allows substitutions, and the √ bound is 1 − 12/ c. Since not allowing substitutions will at most double the edit distance, it leads √ to the bound 1 − 6/ c. (2) In the original construction of [CGK16], the embedding function outputs a string of length 3L. In our setting, we truncate the process, resulting in an output length of 1.5L. The distortion guarantee in Lemma 3.3 is in fact independent of the output length. Inspecting the proof in [CGK16], one can see that the bound ∆H (Emb(x, r), Emb(y, r)) ≤ c · (∆E (x, y))2 √ with probability at least 1 − 6/ c continues to hold for this shortened version without any loss in parameters. While this lemma theoretically holds even if the number of random walk steps (i.e., the output length) is arbitrarily reduced, our overall PRC construction strictly requires the output length to be √ Θ(L). Since the channel introduces O( n) edit errors on each block, the CGK embedding amplifies them quadratically into O(n) Hamming errors. To successfully correct these errors, the underlying Hamming PRC must have a codeword length of at least Θ(n). CGK decoding. We now describe how to interpret an arbitrary binary string under the CGK embedding with a fixed seed r. Not every binary string is a valid output of the CGK embedding. Nevertheless, for any a ∈ {0, 1}1.5L , one can deterministically “project” a to a valid embedding string b by enforcing the local constraints induced by r. This projection simulates a legal CGK walk and ensures consistency between repeated visits to the same input index. Algorithm 2 CGK Decoding Function Emb−1 Require: L, a ∈ {0, 1}1.5L , and r ∈ {0, 1}3L . 1: function Emb−1 (a, r) 2: Interpret r as a description of h1 , . . . , h1.5L : {0, 1} → {0, 1} 3: Initialize i = 1, x1∼L = ⊥L and b1∼1.5L = ⊥1.5L 4: ▷ x1∼L is the resulting string, and b1∼1.5L is a valid embedding projected from a1∼1.5L 14
for t = 1, 2, . . . , 1.5L do 6: if i ≤ L then 7: if xi ̸= ⊥ and xi ̸= at then ▷ r indicates a “stay” step 8: bt = 1 − at ▷ Flip the current bit if it differs from the previous one 9: else 10: bt = at 11: end if 12: xi = bt 13: i = i + ht (xi ) ▷ Update the counter i according to r 14: else 15: bt = 0 ▷ Pad b with 0 if the counter i overflows 16: end if 17: end for 18: Fill the remaining positions xk where xk = ⊥ with i.i.d. bits 19: return x 20: end function 5:
Lemma 3.5. Let Emb−1 : {0, 1}1.5L × {0, 1}3L → {0, 1}L be the decoding function computed by Algorithm 2, and for any a ∈ {0, 1}1.5L , let b1∼1.5L be the string defined and computed in the execution of Emb−1 (a, r). Then the following statements hold: 1. Letting x = Emb−1 (a, r), we have Emb(x, r) = b. Moreover, for any constant c > 0, 3 ∆H (a, b) ≤ +c L 8 with probability at least 1 − negl(L) over the uniform randomness of r. 2. For any fixed r, if the input a is sampled uniformly from {0, 1}1.5L , then Emb−1 (a, r) ≡ UL . Proof. (1) It is immediate from the construction of Algorithm 2 that if x = Emb−1 (a, r), then the algorithm reconstructs the valid embedding string b = Emb(x, r). The Hamming distance ∆H (a, b) may arise from two types of positions. Type I (stay collisions). When i ≤ L and xi has already been assigned, if at ̸= xi , then the decoder sets bt = 1 − at in Line 8. This event happens only if ht (0) = ht (1) = 0, which occurs with probability 1/4. Hence, #{t : bt = 1 − at , i ≤ L} is bounded by the sum of 1.5L independent Bernoulli(1/4) random variables, with expectation 3L/8. By Hoeffding’s inequality, for any constant c > 0, 3L Pr #{t : bt = 1 − at , i ≤ L} > + cL ≤ 2 exp(−2c2 L) = negl(L). 8 Type II (padding after overflow). When i > L, the decoder sets bt = 0 in Line 15. Since the embedding length is 1.5L, and the counter i increases with probability 1/2 at each step while i ≤ L, we have that the value ifinal of the counter i after the main loop satisfies E[ifinal ] = 1 +
1.5L = 1 + 0.75L < L. 2 15
By Hoeffding’s inequality, with probability at least 1 − negl(L), the counter i never exceeds L throughout the 1.5L steps, and therefore no Type II error occurs. Combining the two cases, we conclude that 3 Pr ∆H (a, b) ≤ + c L ≥ 1 − negl(L). 8 (2) Fix any r ∈ {0, 1}3L . During the execution of Algorithm 2, let K ⊆ [L] be the set of indices j such that xj is assigned a value during the main loop. For each j ∈ K, xj is assigned for the first time at some unique time step tj ∈ [1.5L] just after the counter i increases from j − 1 to j. Since xj = ⊥ at this exact moment, the algorithm directly sets xj = atj . Thus, the decoding process induces an injective mapping π : K → [1.5L], where π(j) = tj for all j ∈ K, such that each xj for j ∈ K is exactly determined by aπ(j) . If a is sampled from U1.5L , then the bits {aπ(j) }j∈K are mutually independent and uniformly random. It follows that the assigned bits {xj }j∈K are i.i.d. bits. For the remaining coordinates j ∈ [L] \ K, xj remains ⊥ during the loop and is filled with fresh i.i.d. bits in the final step of the algorithm. Therefore, the entire string x consists of mutually independent, uniformly random bits, which means Emb−1 (U1.5L , r) ≡ UL .
3.2
Detailed Construction
We present the zero-bit (public-key) edit PRC construction as follows. • Key Generation: Sample ℓ = poly(n) independent pairs of keys (pkt , skt )ℓt=1 of the underlying Hamming PRC PRCh . Independently sample ℓ random seeds r1 , . . . , rℓ for the CGK embedding, and ℓ independent uniform masks e1 , . . . , eℓ for one-time padding. The final public key is pk = (pkt , rt , et )ℓt=1 , and the final secret key is sk = (skt , rt , et )ℓt=1 . Multiple independent seeds are used to amplify the constant success probability guaranteed by the CGK embedding to high probability in decoding. • Encoding: Since this is a zero-bit PRC, the only message is 1. For each t ∈ [ℓ], first generate a Hamming PRC codeword at ← Ench (1λ , pkt , 1), and mask it with the one-time pad to get a′t = at ⊕ et . Then project a′t to a valid CGK embedding bt under seed rt , and output yt = Emb−1 (bt , rt ) = Emb−1 (a′t , rt ). The final codeword is y = y1 ◦ · · · ◦ yℓ . • Decoding: Given a received string y ′ ∈ {0, 1}∗ , the decoder enumerates all substrings z = ′ . Each substring is deterministically truncated or padded with trailing zeros to length n. y[i:j] For each such candidate z and each (skt , rt , et ) in the secret key, the decoder computes the embedding Emb(z, rt ), unmasks it by computing ât = Emb(z, rt ) ⊕ et , and applies the Hamming PRC decoder with secret key skt . The decoder outputs 1 as soon as any trial of Dech accepts; if none of the trials accept, it outputs ⊥. This procedure exploits the one-sided success guarantee of the CGK embedding: it suffices that one good block and one good seed succeed.
16
Algorithm 3 CGK-Based Zero-Bit Public-Key Edit PRC 1
−1
Require: Security parameter λ, 0 < γ < 1/2, n = n(λ), ℓ = n 2γ Zero-bit public-key PRC PRCh = (KeyGenh , Ench , Dech ) with codeword length 1.5n CGK embedding function Emb : {0, 1}n × {0, 1}3n → {0, 1}1.5n CGK decoding function Emb−1 : {0, 1}1.5n × {0, 1}3n → {0, 1}n 1: function KeyGen(1λ ) 2: Use KeyGenh (1λ ) to sample ℓ independent pairs of keys (pkt , skt )ℓt=1 3: Sample ℓ independent random seeds r1 , . . . , rℓ ← {0, 1}3n 4: Sample ℓ independent random masks e1 , . . . , eℓ ← {0, 1}1.5n 5: return (pk, sk) = (pkt , rt , et )ℓt=1 , (skt , rt , et )ℓt=1 6: end function 7: function Enc(1λ , pk, 1)
▷ The only message is 1 since this is a zero-bit PRC
for t = 1, 2, . . . , ℓ do Define at ← Ench (1λ , pkt , 1) 10: Define a′t = at ⊕ et 11: Define yt ← Emb−1 (a′t , rt ) 12: end for 13: return y = y1 ◦ · · · ◦ yℓ 14: end function 8: 9:
▷ Apply one-time pad in Hamming space
15: function Dec(1λ , sk, y ′ )
▷ Return ⊥ when y ′ is far from all valid codewords 16: ▷ Use a sliding window to hit a good block ′ 17: Let z = y[i:j] ▷ Try all consecutive substrings of y ′ 18: Deterministically truncate z to its first n bits if |z| > n 19: Or pad z with trailing zeros to length n otherwise 20: for t = 1, 2, . . . , ℓ do 21: if Dech (1λ , skt , Emb(z, rt ) ⊕ et ) ̸= ⊥ then ▷ Recover and decode z in PRCh 22: return 1 ▷ Return 1 if any instance succeeds 23: end if 24: end for 25: end for 26: return ⊥ ▷ Return ⊥ if no instance succeeds 27: end function for all intervals [i : j] of y ′ do
3.3
Analysis of Algorithm 3
Now we are ready to prove the main theorem. We restate Theorem 3.1 here. We only prove for the public-key case. The secret-key case is similar. Theorem 3.1. Let PRCh = (KeyGenh , Ench , Dech ) be a zero-bit public-key (secret-key) PRC against any 14 + c1 -bounded Hamming channel, where c1 < 1/4 is a fixed constant. Then for any constant 0 < γ < 1/2, Algorithm 3 constructs a zero-bit public-key (secret-key) PRC against any p(·)-bounded edit channel for small enough constant c2 and p : x 7→ c2 /xγ . Let PRC = (KeyGen, Enc, Dec) be the scheme constructed in Algorithm 3, and N = N (λ) = 1 n(λ) · ℓ = n 2γ be the codeword length of PRC. Recall that the decoder enumerates all substrings 17
′ , deterministically truncates/pads each z to length n, and tries all (sk , r , e )ℓ . The z = y[i:j] t t t t=1 decoder accepts if any call to Dech (1λ , skt , Emb(z, rt ) ⊕ et ) accepts.
Robustness. Since it is a zero-bit PRC, the only message is 1. For each t ∈ [ℓ], let at ← Ench (1λ , pkt , 1) be the Hamming PRC codeword sampled in the encoding procedure, a′t = at ⊕ et be the masked block, and let yt ← Emb−1 (a′t , rt ) be the corresponding block. Let y = y1 ◦ · · · ◦ yℓ denote the final codeword computed by Enc(1λ , pk, 1), and let y ′ = E(y) be the corrupted codeword through a p(·)-bounded edit channel E with p : x 7→ c2 /xγ . We partition y into ℓ consecutive blocks y1 , . . . , yℓ , and assign each edit operation in the edit transcript of (y, y ′ ) to exactly one block as follows: edits strictly inside yt are assigned to block t, and edits crossing the boundary between yt and yt+1 are assigned to block t. This induces a corresponding partition y ′ = y1′ ◦ · · · ◦ yℓ′ , where yt′ is the substring of y ′ aligned with yt under the edit transcript. Since the total edit distance is at most p(N ) · |y|, by Markov’s inequality, the number of blocks t for which ∆E (yt , yt′ ) > 2p(N ) · |yt | is at most ℓ/2. Hence, at least ℓ/2 blocks are good, meaning ∆E (yt , yt′ ) ≤ 2p(N ) · |yt | = 2n ·
√ n. = 2c 2 (n1/(2γ) )γ c2
Recall that the decoder enumerates all substrings of y ′ . Therefore for each good block t, there exists some iteration in which the candidate substring z equals yt′ . Then z will be deterministically truncated/padded to length n, which may at most double the edit distance, ensuring ∆E (yt , z) ≤ √ 4c2 n. Crucially, we establish the statistical independence between (yt , z) and the embedding seed rt . Fix the underlying key (pkt , skt ) and the internal randomness of Ench , so that at is a fixed string. Since et ∼ U1.5n is sampled independently, the masked codeword a′t = at ⊕ et is uniformly distributed over {0, 1}1.5n and strictly independent of rt . By the second property of Lemma 3.5, the output yt = Emb−1 (a′t , rt ) is uniformly distributed over {0, 1}n , and its distribution is independent of rt . Furthermore, since the edit channel E is oblivious (its error operations are fixed beforehand and do not depend on the codewords or the keys), the edited string y ′ and the substring z depend exclusively on y and the predetermined channel E. Therefore, the random variables (yt , z) are entirely independent of rt . Fix a good block t. By the first property of Lemma 3.5, with probability at least 1 − negl(λ) over the randomness of rt , for any constant c3 > 0, 3 ′ ∆H Emb(yt , rt ), at ≤ + c3 n. 8 Since (yt , z) is independent of rt , we can apply Lemma 3.3 by conditioning on any fixed values √ yt = v and z = w such that ∆E (v, w) ≤ 4c2 n. Over the randomness of rt , for any constant c4 > 0, √ Pr ∆H Emb(v, rt ), Emb(w, rt ) ≤ c4 · (∆E (v, w))2 ≥ 1 − 6/ c4 . rt
√ Taking the expectation over all such valid pairs (v, w), we have with probability at least 1−6/ c4 over rt : ∆H Emb(yt , rt ), Emb(z, rt ) ≤ c4 · (∆E (yt , z))2 ≤ 16c4 c22 · n.
18
√ Choose c4 such that 1 − 6/ c4 ≥ 1/2, and choose c2 , c3 sufficiently small so that 3 3 + 16c4 c22 + c3 ≤ + 1.5c1 . 8 8 Then we can bound the distance to the original codeword at : ∆H (ât , at ) = ∆H Emb(z, rt ) ⊕ et , at = ∆H Emb(z, rt ), at ⊕ et = ∆H Emb(z, rt ), a′t ≤ ∆H Emb(z, rt ), Emb(yt , rt ) + ∆H Emb(yt , rt ), a′t 1 3 2 ≤ 16c4 c2 · n + + c3 n ≤ + c1 · 1.5n. 8 4 Since PRCh is robust to any ( 14 + c1 )-bounded Hamming channel and has codeword length 1.5n, it follows that, with probability at least 1/2 − negl(λ), Dech 1λ , skt , Emb(z, rt ) ⊕ et = 1. Finally, note that at least ℓ/2 blocks are good and each good block succeeds with constant probability over rt , and the decoder tries all t ∈ [ℓ]. Additionally, since (skt , rt , et )ℓt=1 are independent, these good blocks also succeed independently. Hence the probability that none of the trials ℓ/2 succeeds is at most 21 + negl(λ) = negl(λ). Thus, Pr
[Dec(1λ , sk, y ′ ) = 1] ≥ 1 − negl(λ).
(pk,sk)←KeyGen(1λ )
Soundness. such that
Suppose for contradiction that PRC is not sound. Then there exists a fixed string y Pr
(pk,sk)←KeyGen(1λ )
Dec(1λ , sk, y) ̸= ⊥ ≥
1 . poly(λ)
By a standard averaging argument, there exist fixed choices of seeds (r1∗ , . . . , rℓ∗ ) and masks (e∗1 , . . . , e∗ℓ ) such that 1 Dec(1λ , sk, y) ̸= ⊥ ≥ Pr , ℓ poly(λ) (pkt ,skt )t=1 where the secret key sk now incorporates these fixed seeds and masks. By the definition of the decoder, this implies that with non-negligible probability over (pkt , skt )ℓt=1 , there exist indices i, j and t such that Dech 1λ , skt , Emb(z, rt∗ ) ⊕ e∗t = 1, where z is obtained from y[i:j] by a fixed deterministic truncation/padding rule to length n. By a union bound over all Θ(n2 ) choices of (i, j) and ℓ blocks, there exist fixed indices (i∗ , j ∗ , t∗ ) such that 1/poly(λ) 1 Pr Dech 1λ , skt∗ , Emb(z ∗ , rt∗∗ ) ⊕ e∗t∗ = 1 ≥ = , 2 λ Θ(n ) · ℓ poly(λ) (pkt∗ ,skt∗ )←KeyGenh (1 ) where z ∗ is the deterministically truncated/padded version of y[i∗ :j ∗ ] . Let y ∗ = Emb(z ∗ , rt∗∗ ) ⊕ e∗t∗ . Then we have 1 Pr Dech (1λ , skt∗ , y ∗ ) ̸= ⊥ ≥ , λ poly(λ) (pkt∗ ,skt∗ )←KeyGenh (1 ) which contradicts the soundness of PRCh . Therefore, PRC is sound. 19
Pseudorandomness. Since the only message is 1, we prove that the outputs of Enc(1λ , pk, 1) are computationally indistinguishable from Unℓ given the public key pk via hybrid arguments. We define a sequence of ℓ + 1 hybrid experiments H0 , H1 , . . . , Hℓ . In hybrid Hk , the challenger constructs the public key pk exactly as in the real scheme, but answers each encoding oracle query for 1 by generating the ℓ blocks y1 , . . . , yℓ as follows: • For t ≤ k, the block is generated honestly: at ← Ench (1λ , pkt , 1) and yt ← Emb−1 (at ⊕ et , rt ). • For t > k, the block is generated randomly: at ← U1.5n and yt ← Emb−1 (at ⊕ et , rt ). Observe the endpoints of these hybrids: • In Hℓ , all ℓ blocks are generated honestly, which perfectly corresponds to the real encoding oracle Enc(1λ , pk, ·). • In H0 , all ℓ blocks are generated from fresh uniform strings at ∼ U1.5n . For any t, et is given in the public key, and so at ⊕ et is strictly distributed as U1.5n . By the second property of Lemma 3.5, for the fixed rt in the public key, the output yt = Emb−1 (at ⊕ et , rt ) is uniform. Since a1 , . . . , aℓ are independent, y = y1 ◦ · · · ◦ yℓ in H0 is perfectly uniformly distributed over {0, 1}nℓ . Thus, H0 perfectly corresponds to the uniform oracle Unℓ . We claim that for any k ∈ [ℓ], the adjacent hybrids Hk−1 and Hk are computationally indistinguishable. Suppose there exists a PPT distinguisher A that distinguishes Hk−1 and Hk . We can construct a PPT distinguisher B to break the public-key pseudorandomness of PRCh . B receives a single target public key pk∗ and has access to an oracle O∗ , which is either the real encoder Ench (1λ , pk∗ , ·) or a uniform oracle returning strings in U1.5n . B simulates the environment for A by embedding pk∗ into the k-th position: • For t ̸= k, B runs KeyGenh (1λ ) to independently generate (pkt , skt ). • For t = k, B sets pkk = pk∗ . B then independently samples r1 , . . . , rℓ from {0, 1}3n and e1 , . . . , eℓ from {0, 1}1.5n . It constructs the full public key pk = (pkt , rt , et )ℓt=1 and runs A(1λ , pk). Whenever A makes an encoding oracle query for 1, B constructs the intermediate strings a1 , . . . , aℓ as follows: • For t < k, B computes at ← Ench (1λ , pkt , 1) using the keys it generated. • For t = k, B queries its oracle to obtain ak ← O∗ (1). • For t > k, B directly samples at ← U1.5n . For each t ∈ [ℓ], B computes yt ← Emb−1 (at ⊕ et , rt ), and returns the concatenated string y = y1 ◦ · · · ◦ yℓ to A. When A outputs a bit, B outputs the exact same bit. If the oracle O∗ is the real encoder Ench (1λ , pk∗ , ·), then ak is a valid codeword, matching the distribution of Hk ; if O∗ provides uniformly random strings, then ak ∼ U1.5n , matching the distribution of Hk−1 . Obviously, B is a valid PPT distinguisher. By the public-key pseudorandomness of PRCh , the distinguishing advantage between O∗ = Ench and O∗ = U1.5n must be negligible, which implies a contradiction. Consequently, the advantage of A in distinguishing Hk−1 and Hk is at most negl(λ). Finally, the total distinguishing advantage between H0 and Hℓ is at most ℓ · negl(λ) = negl(λ). Therefore, the output distribution of PRC is computationally indistinguishable from uniform given the public key pk. 20
Remark 3.6. (1) The uniform mask et is crucial for decoupling the codeword from the embedding seed rt . Lemma 3.3 relies on a random walk argument that strictly requires the input strings to be statistically independent of rt . Without et , the block yt (and thus the edited substring z) would be heavily correlated with rt , invalidating the probability bound. In contrast, the first property of Lemma 3.5 does not require the input a to be independent of rt . Its distance bound is unconditionally dominated by the event ht (0) = ht (1) = 0, which depends solely on rt , allowing a direct application of Hoeffding’s inequality regardless of a. (2) The reduction in Theorem 3.1 is not limited to the binary alphabet. The CGK embedding applies to strings over any constant-size alphabet, and hence the reduction holds verbatim for PRCs over any constant alphabet Σ.
4
Generic Reduction to Zero-Bit
In this section, we present a general black-box framework for using a zero-bit PRC to construct a constant-rate PRC over a general alphabet, and hence also over the binary alphabet. The construction works as follows. We use a short master seed s both to generate the payload-side randomness and to protect itself through many sparse marker blocks inserted at random locations. The decoder first recovers s from these marker blocks, and then uses s to decode the payload. Our construction can be seen as an extension of [CG24] for Hamming errors, but we make several modifications to adapt it to edit errors. We first describe the building blocks for our reduction framework, and abstract an object named seeded payload code in Section 4.1. Then we give detailed descriptions of our reduction in Section 4.2. Finally, we state our main result Theorem 4.3 for this section and prove it in Section 4.3.
4.1
Building Blocks
To construct a constant-rate PRC against any p(·)-bounded edit channel for a function p : N → [0, 1], we use the following building blocks. • Zero-Bit PRC. Let λ be the security parameter. Let PRC0 = (KeyGen0 , Enc0 , Dec0 ) be a zero-bit public-key PRC over alphabet Σ with codeword length ℓ, which is robust to any p0 (·)-bounded edit channel for a function p0 : N → [0, 1]. Moreover, PRC0 should satisfy the uniformity property defined in the following. Particularly, the zero-bit public-key PRC given by Algorithm 3 in Section 3.2 satisfies this uniformity property. Definition 4.1 (Uniformity). We say a PRC with codeword length ℓ over alphabet Σ has the uniformity property, if for any fixed message, over the randomness of the key-generation and encoding procedures, the resulting codeword is uniformly distributed over Σℓ . • Seeded Payload Code. We next introduce the notion of a seeded payload code, which will serve as the payload code in our construction. Informally, such a code uses a short random seed and a (public) masking string to encode the message, while satisfying robustness, uniformity, and pseudorandomness. Definition 4.2 (Seeded payload code). We use M to denote the size of the message space. Let ECCload : [M ] × {0, 1}d × {0, 1}r → Σn 21
log
M
, which should be determinbe the encoding map for the payload code with rate R = |Σ| n istic polynomial-time computable. We say ECCload is a seeded payload code robust to any δ fraction of edit errors, if it satisfies the following properties: – Robustness. There exists a deterministic polynomial-time computable decoding map ∗ d r ECC−1 load : Σ × {0, 1} × {0, 1} → [M ] ∪ {⊥}
such that for every m ∈ [M ], with probability at least 1 − negl(λ) over the choice of s ∈ {0, 1}d and shiftpk ∈ {0, 1}r , every received word y ′ satisfying ∆E y ′ , ECCload (m, s, shiftpk ) ≤ δn also satisfies ′ ECC−1 load (y , s, shiftpk ) = m.
– Uniformity. If shiftpk is sampled uniformly from {0, 1}r , then for every fixed m ∈ [M ] and s ∈ {0, 1}d , the output ECCload (m, s, shiftpk ) is uniformly distributed over Σn . – Pseudorandomness. For every PPT adversary A, Pr
shiftpk ←Ur
ECC (·,U ,shift ) λ pk (1 , shiftpk ) = 1 − A load d
Pr
shiftpk ←Ur U
U λ A (1 , shiftpk ) = 1 ≤ negl(λ),
where ECCload (·, Ud , shiftpk ) denotes the oracle that first samples s ← Ud and then returns ECCload (·, s, shiftpk ), and U denotes an oracle that returns a fresh uniform sample from Σn on each query. Note that the distinguisher knows shiftpk since we will put it in the public key. • Hamming ECC. Let
′
ECCseed : {0, 1}d → {0, 1}d
be a seed code of constant rate that can be efficiently decoded from a pseed fraction of Hamming errors, where 0 < pseed < 1/4 is a constant. Such codes exist for all sufficiently large d. For example, one may use a concatenated code. We take d = Θ(nγ ) for some constant 0 < γ < 1/4. Since ECCseed has constant rate, it follows that d′ = O(d).
4.2
Detailed Construction
Now we describe the construction of our PRC. • Key Generation: For each j ∈ [2d′ ], sample an independent key pair (pkj , skj ) ← KeyGen0 (1λ ). Also sample a uniformly random string shiftpk ← Ur . Set pk := (pk1 , . . . , pk2d′ , shiftpk ),
22
sk := (sk1 , . . . , sk2d′ , shiftpk ).
• Encoding: Given a message m ∈ [M ], the encoder first samples a short seed s ← {0, 1}d . It then encodes the seed using the seed code and appends a padding of d′ ones: ′
′
s′ := ECCseed (s) ◦ 1d ∈ {0, 1}2d . For each i ∈ [2d′ ], the encoder uses the public key pki to encode the bit s′i , obtaining a marker block ( Enc0 (1λ , pki , 1), if s′i = 1, ui ← Uℓ , if s′i = 0. Next, the encoder computes the payload codeword c := ECCload (m, s, shiftpk ) ∈ Σn . Finally, the encoder samples insertion locations loc1 , . . . , loc2d′ and interleaves the marker blocks u1 , . . . , u2d′ into the payload codeword c. More precisely, we view the final codeword as occupying coordinates in [n + 2d′ ℓ]. The encoder samples 2d′ pairwise disjoint intervals I1 = [loc1 , loc1 + ℓ − 1], . . . , I2d′ = [loc2d′ , loc2d′ + ℓ − 1] ⊆ n + 2d′ ℓ , each of length ℓ, uniformly at random subject to the condition that they are pairwise disjoint. Equivalently, one may sample candidate intervals independently and resample until all chosen intervals are pairwise disjoint. For each i ∈ [2d′ ], the marker block ui is placed on the interval Ii , while the symbols of the payload codeword c are placed in the remaining coordinates in their natural order. The resulting word is denoted by y. • Decoding: Given a received word y ′ , the decoder first searches for candidate marker blocks. More precisely, for each index i ∈ [2d′ ], it applies the zero-bit decoder Dec0 (1λ , ski , ·) to candidate substrings of y ′ , and uses the resulting outputs to reconstruct a corrupted version s̃ of the protected seed string s′ . It then checks whether the padding portion of s̃ is consistent, and decodes the seed-encoding portion using the decoder of ECCseed to recover the seed s. If either step fails, the decoder outputs ⊥. Once we successfully recover s, we can run the decoder ECC−1 load for the payload code using s and shiftpk , and output the recovered message. Algorithm 4 Generic Construction from a Zero-Bit Public-Key Edit PRC Require: Security parameter λ, n = n(λ), d = d(λ), ℓ = ℓ(λ), message space [M ] Zero-bit public-key PRC PRC0 = (KeyGen0 , Enc0 , Dec0 ) over alphabet Σ Seeded payload code ECCload : [M ] × {0, 1}d × {0, 1}r → Σn ′ Seed code ECCseed : {0, 1}d → {0, 1}d , d′ = O(d) 1: function KeyGen(1λ ) 2: for j = 1 to 2d′ do 3: (pkj , skj ) ← KeyGen0 (1λ ) 4: end for 5: Sample a uniformly random shifting vector shiftpk ← Ur 6: pk = (pk1 , . . . , pk2d′ , shiftpk ) 7: sk = (sk1 , . . . , sk2d′ , shiftpk ) 23
return (pk, sk) 9: end function 8:
10: function Enc(1λ , pk, m)
Sample s ← {0, 1}d ′ 12: Compute s′ ← ECCseed (s) ◦ 1d 13: for i = 1 to 2d′ do 14: if s′i = 1 then 15: ui ← Enc0 (1λ , pki , 1) ▷ For s′i = 1, the marker block is a PRC codeword 16: else 17: ui ← Uℓ ▷ For s′i = 0, the marker block is a random string 18: end if 19: end for 20: Compute the payload codeword c = ECCload (m, s, shiftpk ) 21: Interleave the marker blocks u1 , . . . , u2d′ into the payload codeword c as described 22: return the resulting word y 23: end function 11:
24: function Dec(1λ , sk, y ′ ) ′
Initialize s̃ = ⊥2d ▷ Step 1: Recover the seed s 26: for i = 1 to 2d′ do 27: for all intervals [l : r] of y ′ do ′ ) 28: Run Dec0 (1λ , ski , y[l:r] ▷ Try all substrings of y ′ 29: end for 30: Set s̃i = 1 if the decoder succeeds in any trial; otherwise set s̃i = 0 31: end for ′ 32: if s̃[d′ +1,2d′ ] = 0d then ▷ Check consistency of the padding portion 33: return ⊥ 34: end if 35: Decode s̃[1:d′ ] using the seed decoder ECC−1 seed to recover s 36: if seed decoding fails then 37: return ⊥ 38: end if ′ ▷ Step 2: Use the payload decoder to recover the message 39: return ECC−1 load (y , s, shiftpk ) 40: end function 25:
4.3
Analysis of the Algorithm 4
Theorem 4.3. Let λ be a security parameter, and: • PRC0 = (KeyGen0 , Enc0 , Dec0 ) is a zero-bit public-key (secret-key) PRC with codeword length ℓ that is robust to any p0 (·)-bounded edit channel for the function p0 : N → [0, 1]. Moreover, PRC0 satisfies the uniformity property (see Definition 4.1). • ECCload : [M ] × {0, 1}d × {0, 1}r → Σn is a seeded payload code (see Definition 4.2) with rate R = log|Σ| M/n that is robust to any δ fraction of edit errors. ′
• ECCseed : {0, 1}d → {0, 1}d is an error-correcting code against any pseed fraction of Hamming errors, where 0 < pseed < 1/4 is a constant. 24
Let N = n + 2d′ ℓ be the total codeword length. Suppose the parameters satisfy d′ = ℓ = Θ(nγ ) for some constant 0 < γ < 1/4. Moreover, let p : N → [0, 1] be a function such that p(N ) ≤ (1 − ε) · min{δ, p0 (ℓ) · pseed } for some constant ε > 0. Then the scheme PRC = (KeyGen, Enc, Dec) constructed in Algorithm 4 is a public-key (secret-key) PRC that is robust against any p(·)-bounded edit channels E, with rate log|Σ| M = R − o(1). n + 2d′ ℓ Robustness. We now establish the robustness of the edit PRC. Observe that the zero-bit PRC component and the payload codeword are independent, and each is uniformly distributed over the randomness of key generation and encoding. Combining with the uniformity property of the payload code ECCload , the final codeword is also uniformly distributed. Let y denote the transmitted word, and let y ′ = E(y) be the received word. By the uniformity property, the edit pattern imposed by the channel is independent of the random placement of the blocks ui . Therefore, for the purpose of analysis, we may equivalently imagine that the channel first fixes its edit pattern, and only afterwards the encoder samples the random locations of the blocks ui . We charge each edit operation in the edit transcript of (y, y ′ ) to exactly one position as follows: for any j ∈ [N ], edit operations between two positions yj and yj+1 are charged to position j. For each position j ∈ [N ], let wj denote the number of edit operations charged to that position. If the marker block ui is placed on the interval Ii = [loci , loci + ℓ −P 1] ⊆ [N ], then the total number of edit operations charged to the interval occupied by ui is ci := j∈Ii wj . Claim 4.4. Call an interval Ii bad if ci > p0 (ℓ) · ℓ. Then, with probability at least 1 − negl(λ) over the random choice of the insertion locations, the numbers of bad intervals with i ∈ [1, d′ ] and i ∈ [d′ + 1, 2d′ ] are both at most pseed · d′ . Proof. We first analyze an idealized model in which the interval locations are sampled independently. We will remove this assumption at the end. Recall that the total number of edit operations is at most p(N ) · N . Fix a block ui . The interval Ii has length ℓ, and its starting location is sampled uniformly from at least N − ℓ + 1 possible positions. Since each charged error can affect at most ℓ candidate intervals, for any i ∈ [2d′ ], we have p(N ) · N ℓ E[ci ] ≤ ≤ (1 + o(1)) · p(N ) · ℓ N −ℓ+1 Then by Markov’s inequality, for any i ∈ [2d′ ], Pr[ci > p0 (ℓ) · ℓ] ≤
E[ci ] ≤ (1 − ε + o(1)) · pseed . p0 (ℓ) · ℓ
Let X1 and X2 denote the numbers of bad intervals with i ∈ [1, d′ ] and i ∈ [d′ + 1, 2d′ ], respectively. Under the independence assumption, the indicators of the events “ci > p0 (ℓ) · ℓ” are independent, and hence by Hoeffding’s inequality, both Pr X1 > pseed · d′ and Pr X2 > pseed · d′ ≤ 2 exp − (2 − o(1)) · ε2 p2seed d′ = negl(λ). Hence, under the independence assumption, with probability at least 1 − negl(λ), the numbers of bad intervals with i ∈ [1, d′ ] and i ∈ [d′ + 1, 2d′ ] are both at most pseed · d′ .
25
Finally, we account for the non-overlapping constraint. One sampling trial fails if two sampled intervals intersect. The probability of this event is ′ 2d′ ′2 ℓd ℓd . q =1− 1−O =O N N The encoder therefore repeats the sampling procedure independently up to λ times, stopping once it finds a collection of pairwise disjoint intervals. The probability that all λ trials fail is at most q λ = negl(λ). We next show that every non-bad block ui can be recovered correctly with probability at least 1 − negl(λ). Consequently, by a union bound over all non-bad blocks, with probability at least 1 − negl(λ), every non-bad block is recovered correctly. ′ • Case s′i = 1. In this case, the decoder enumerates all substrings y[l:r] in Line 28. Since Ii is not bad, the total number of edit operations charged to Ii is at most p0 (ℓ) · ℓ. Therefore, among the candidate substrings examined by the decoder, there exists one that contains the corrupted image of ui and differs from the original block by at most p0 (ℓ) · ℓ edits. By the robustness of PRC0 , the decoder successfully recovers this block, and hence outputs s̃i = 1 with probability at least 1 − negl(λ).
• Case s′i = 0. In this case, the encoder places an independent uniform string ui ← Uℓ on the interval Ii . For every candidate substring considered by the decoder, this string remains independent of the key pair (pki , ski ). Therefore, by the soundness of PRC0 , the probability that any such candidate substring is incorrectly accepted is at most negl(λ). Taking a union bound over all candidate substrings examined for the i-th position, we conclude that s̃i = 0 with probability at least 1 − negl(λ). Conditioned on the event in Claim 4.4 and on the event that all non-bad blocks are recovered correctly, we know that in both the seed-encoding portion and the padding portion, at most pseed ·d′ bits are decoded incorrectly. Hence, the padding check in Line 32 does not output ⊥. And by the decoding guarantee of ECCseed , the seed s is correctly recovered in Line 35. In all, we conclude that the decoder recovers the correct seed s with probability at least 1 − negl(λ). Finally, conditioned on recovering the correct seed s, we view the inserted PRC0 blocks as additional insertion errors relative to the payload codeword. The underlying channel contributes at most p(N ) fraction of edit errors, while the total length of all inserted PRC0 blocks is 2d′ ℓ = Θ(N 2γ ). Hence the payload codeword experiences at most p(N )N + Θ(N 2γ ) ≤ δN edit errors in total since p(N ) ≤ (1−ε)δ. The robustness of the payload code implies that, for every message m, the decoder outputs the correct message with probability at least 1 − negl(λ). Soundness. We now establish the soundness of the resulting PRC. Fix any received word y ′ ∈ Σ∗ . We analyze the seed-recovery stage of the decoder. For each index i ∈ [2d′ ] and each candidate interval I, the decoder applies Dec0 (1λ , ski , ·) to the corresponding substring of y ′ . By the soundness of PRC0 , for every fixed pair (i, I), Pr Dec0 (1λ , ski , yI′ ) ̸= ⊥ ≤ negl(λ). (pki ,ski )←KeyGen0 (1λ )
Thus, except with negligible probability, the decoder rejects on that candidate interval. Since there are 2d′ choices of i and at most polynomially many candidate intervals I, by a union bound, Pr Some invocation of Dec0 accepts ≤ 2d′ · poly(n) · negl(λ) = negl(λ). (pk,sk)←KeyGen(1λ )
26
Hence, with probability at least 1 − negl(λ), every invocation of Dec0 rejects, which implies that the recovered string s̃ is the all-zero string. Therefore the padding check in the decoding algorithm fails, and the decoder outputs ⊥. Pseudorandomness. We show that the pseudorandomness of the final construction follows from the pseudorandomness of the underlying zero-bit PRC together with the pseudorandomness of the payload code. Informally, the proof proceeds in two steps. First, we replace the marker blocks produced by the zero-bit PRC with independent uniform blocks; this changes the distribution only negligibly by the security of PRC0 . Second, conditioned on the marker blocks already being uniform, the payload part is pseudorandom by assumption, and hence the entire interleaved codeword is pseudorandom. Formally, we define the following sequence of hybrid experiments: • Hybrid H0 (Real World). The challenger generates (pk, sk) ← KeyGen(1λ ) honestly. When A makes an encoding query for message m, the challenger computes c ← Enc(1λ , pk, m) using the real encoding algorithm and returns c. • Hybrid H1 (Uniform Marker Blocks). Same as H0 , except that for each encoding query, the marker blocks u1 , . . . , u2d′ are sampled as independent uniform strings from Σℓ instead of being generated via Enc0 . Specifically, we replace ui ← Enc0 (1λ , pki , 1) when s′i = 1 with ui ← Uℓ for all i ∈ [2d′ ]. • Hybrid H2 (Uniform Payload). Same as H1 , except that the payload codeword c = ECCload (m, s, shiftpk ) is replaced with a uniformly random string c ← Un . • Hybrid H3 (Ideal World). Same as H2 , except that the entire output is a uniformly random string from ΣN . This corresponds to the oracle UN in the theorem statement. We now bound the distinguishing advantage between adjacent hybrids. Claim 4.5. H0 and H1 are computational indistinguishable even with pk. Proof. We use a hybrid argument over the 2d′ marker blocks. Let H0,j be an experiment where the first j marker blocks are uniform, and the remaining 2d′ − j blocks are generated honestly. Note that H0,0 = H0 and H0,2d′ = H1 . For any j ∈ [2d′ ], suppose A distinguishes H0,j−1 and H0,j with non-negligible advantage. We construct an adversary B against PRC0 : 1. B receives a target public key pk∗ and an oracle O∗ which is either Enc0 (1λ , pk∗ , 1) or Uℓ . 2. B samples (pki , ski ) ← KeyGen0 (1λ ) for i ̸= j and shiftpk ← Ur . 3. Run A 1λ , pk = (pk1 , . . . , pk∗ , . . . , pk2d′ , shiftpk ) . When A queries m: ′
• B samples s ← {0, 1}d and computes s′ = ECCseed (s) ◦ 1d . • For i < j, B sets ui ← Uℓ . • For i = j: If s′j = 1, B sets uj ← O∗ ; otherwise, uj ← Uℓ . • For i > j: If s′i = 1, B sets ui ← Enc0 (1λ , pki , 1); otherwise, ui ← Uℓ . • B computes c = ECCload (m, s, shiftpk ) and returns the interleaved result to A.
27
If O∗ is the real encoder, B perfectly simulates H0,j−1 . If O∗ is the uniform oracle, B simulates H0,j . The two hybrids differ only in the distribution of the j-th marker block when s′j = 1: in H0,j−1 it is generated as Enc0 (1λ , pk∗ , 1), whereas in H0,j it is sampled uniformly from Uℓ . By the pseudorandomness of PRC0 , these two cases are computationally indistinguishable given pk∗ , and therefore the distinguishing advantage of A between H0,j−1 and H0,j is at most negl(λ). Summing over 2d′ hybrid steps, the total distinguishing advantage between H0 and H1 is still negl(λ). Claim 4.6. H1 and H2 are computational indistinguishable even with pk. Proof. In H1 , the marker blocks ui are all independent uniform strings. This means they are statistically independent of the seed s. Therefore, the adversary’s view of s through the marker blocks is null. We can reduce this directly to the pseudorandomness of ECCload : 1. B receives shiftpk and an oracle O which is either ECCload (·, Ud , shiftpk ) or Un . 2. B samples all (pki , ski ) ← KeyGen0 (1λ ) honestly and runs A 1λ , pk = (pk1 , . . . , pk2d′ , shiftpk ) . 3. For each query m made by A, B sets all ui ← Uℓ , obtains c ← O(m), and returns the interleaved result to A. If O is the real payload oracle, this is exactly H1 . If it is uniform, this is H2 . By the pseudorandomness of the payload code ECCload , the advantage is negl(λ). Finally, note that in H2 , the payload and all marker blocks are independent uniform strings. Their interleaving is identically distributed to a uniform string of length N . Thus the advantage between H2 and H3 is 0. In all, the advantage between H0 and H3 is negl(λ), which completes the proof for pseudorandomness. At the end of this section, we state a direct corollary of our reduction. We may choose a binary code of constant rate with efficient decoding radius 41 − ε as ECCseed . This gives: Corollary 4.7. Let λ be the security parameter, and let PRC0 and ECCload be as in Theorem 4.3. Suppose the resulting code over Σ has codeword length N . Let p : N → [0, 1] be such that 1 p(N ) ≤ (1 − ε) · min δ, p0 (ℓ) 4 for some constant ε > 0. Then the scheme PRC = (KeyGen, Enc, Dec) constructed in Algorithm 4 is a public-key (respectively, secret-key) PRC robust against every p(·)-bounded edit channel E, and it has rate R − o(1).
5
Constant-Alphabet PRCs with Rate Close to 1
In this section, we first present a construction of a seeded payload code (see Definition 4.2) over a constant-size alphabet and with a constant decoding radius. We observe that synchronization strings [HS21] are well suited to our application: they handle edit errors while ensuring the codeword appears random, as required by the definition of a seeded payload code. We use synchronization strings via the standard method [HS21]: attaching a constant-alphabet random string (with certain synchronizing properties) to the message, extending its alphabet by a constant factor. To make the codeword uniform over the randomness of (sk, pk), we apply the public shifting vector shiftpk to the codeword at the end of generation. However, as shiftpk is fixed in the public 28
key, to ensure the codeword remains pseudorandom even when queried multiple times, we must apply additional masking generated by PRGs. This is easily handled as the framework in Section 4 allows the encoder and decoder to share common randomness through the shared random seed. For ease of exposition, throughout this section we assume that the alphabets (e.g. Σ, Σmsg ) we use are finite fields. This allows us to use addition and subtraction to apply and remove the shifts and masks. Theorem 5.1 (Seeded payload code via synchronization string). Let ECCmsg : [M ] → Σnmsg be an ECC robust to any pmsg fraction of half-errors. Then Algorithm 5 yields a seeded payload code ECCload : [M ] × {0, 1}d × {0, 1}r → Σn that is robust to any pload fraction of edit errors, provided that the block length n = Ω(λ), pload ≤ pmsg − δ for some constant δ > 0, and the alphabet size |Σ| ≥ |Σmsg | · Ω(δ −4 ). We use the standard half-error metric: each erasure counts as 1, each substitution as 2, so the total half-error count is 2e + s. We will first describe some background on synchronizing strings in Section 5.1, then present the detailed construction, and prove Theorem 5.1 in Section 5.3. Finally in Section 5.4, we combine our construction of the seeded payload code with appropriate error-correcting codes to get a multi-bit to zero-bit reduction in Corollary 5.8, following Theorem 4.3. We further plug in different zero-bit PRC constructions to obtain a multi-bit edit PRC with a constant rate, these results are stated in Corollary 5.9 and Corollary 5.10.
5.1
Synchronization Strings and Self-Matching
Synchronization strings, introduced by Haeupler and Shahrasbi [HS21], provide a way to recover approximate alignment under insertions and deletions. In our proof, we only use a relaxed property of synchronization strings, namely the self-matching property, together with the corresponding decoding guarantee from [HS21, Section 6.3]. We recall below the notions that are needed later. Definition 5.2 (Monotone matching [HS21, Definition 6.1]). Let S, S ′ ∈ Σ∗ . A monotone matching between S and S ′ is a set of pairs M = {(a1 , b1 ), · · · , (am , bm )} such that a1 < · · · < am ,
b1 < · · · < bm ,
Sai = Sb′ i
for all i ∈ [m].
Equivalently, a monotone matching is a common subsequence together with the indices realizing it. Definition 5.3 (ε-self-matching). A string S ∈ Σn is said to be ε-self-matching if for every monotone matching M = {(a1 , b1 ), · · · , (am , bm )} between S and itself, the number of pairs with ai ̸= bi is at most εn. Intuitively, the ε-self-matching property says that one cannot find a large monotone matching between two copies of the same string that mismatches many positions. This is exactly the global non-self-similarity condition needed by the alignment algorithm [HS21, Algorithm 3]. For our application, we do not explicitly construct synchronization strings. Instead, after recovering the seed s, the decoder reconstructs σ = PRGsyn (s1 ) + shiftsyn ∈ Σnsyn , and we use the fact that σ is uniformly random over Σnsyn because shiftsyn is uniform. Hence, it suffices to know that a random string is ε-self-matching with high probability. 29
Theorem 5.4 (Random strings are self-matching [HS21, Theorem 6.9]). Let S be a uniformly random string in Σn . Then for every ε ∈ (0, 1), 2 nε e Pr[S is ε-self-matching] ≥ 1 − . 2 ε |Σ| We will also use the decoding guarantee from [HS21]. Informally, if a received string differs from an ε-self-matching string by at most t insertions and deletions, then the synchronization algorithm √ outputs an indexing with at most t + O( ε)n misdecodings. Lemma 5.5 (Alignment via self-matching strings (implicit in [HS21])). Let σ ∈ Σnsyn be an ε-self|σ̃|
matching string, and let σ̃ be any string with ∆E (σ, σ̃) ≤ t. Let x̃ ∈ Σmsg be produced by applying the same edit operations to a string x ∈ Σnmsg . There is a polynomial-time procedure that outputs x̂ ∈ (Σmsg ∪ {⊥})n such that, letting e and s be the numbers of incorrect symbols and erasures in x̂ relative to the original x, we have √ 2e + s ≤ t + 6n ε. Proof sketch. The repositioning algorithm of [HS21, Algorithm 3] produces a mapping P : [|σ̃|] → [n]∪{⊥} from received positions to source positions. Inverting this mapping and applying standard conflict resolution (as in the rearrangement procedure of [HS21, Algorithm 2]): keeping only the unique claimant for each source and marking the rest as erasures, gives a candidate received position rj for each source position j ∈ [n]. We set x̂j = x̃rj when rj ̸= ⊥, and x̂j = ⊥ otherwise. √ By [HS21, Theorem 6.13], at most 3n ε successfully transmitted positions are misdecoded, each contributing at most 2 half-errors in the worst case. Deletions create at most dr (number of deletions) ≤ t erasures (each 1 half-error). Summing, √ √ 2e + s ≤ dr + 2 · 3n ε ≤ t + 6n ε.
5.2
Construction of the Seeded Payload Code
We list the components required in our construction: • Hamming ECCs. In our construction, we employ a Hamming error-correcting code ECCmsg : n [M ] → Σmsg that is robust against any pmsg fraction of half-errors, i.e., it admits efficient unique decoding from any combination of a fraction e of substitution errors and a fraction s of erasures as long as 2e + s ≤ pmsg . We denote its encoding and decoding functions by ECCmsg (·) and ECC−1 msg (·), respectively. An explicit family of such codes with rate arbitrarily close to 1 − pmsg and alphabet size poly(1/ε) is given by the AG code; we restate the required guarantee in Lemma 5.6. The role of ECCmsg is to correct the remaining Hamming-type corruptions that remain after the edit errors have been converted into substitution errors and erasures via the synchronization string. • Pseudorandom Generator. We require a cryptographic pseudorandom generator PRG such that no PPT adversary can distinguish its output from a uniform string with nonnegligible advantage. In our scheme, we instantiate the PRG twice to produce masking strings over different alphabets: 30
– PRGmsg : {0, 1}d2 → Σnmsg is used to mask the encoded payload message, ensuring its pseudorandomness. – PRGsyn : {0, 1}d1 → Σnsyn is used to mask the synchronization string, making it computationally indistinguishable from uniform. These two generators ensure that each component of the assembled codeword satisfies the pseudorandomness requirement. Notation convention. In this section, we follow a consistent naming convention to distinguish between the different stages of the codeword. We use a tilde to denote corrupted sequences (e.g., ỹ and σ̃). We also use ñ to denote the length of the corrupted message. For sequences reconstructed during the decoding process, we use a hat (e.g., x̂ as the estimate of x and m̂ as the recovered message). Encoding ECCload (m, s, shiftpk ): Applying Synchronization String and Masking. Parse shiftpk into (shiftmsg , shiftsyn ) such that (shiftpk )i = ((shiftmsg )i , (shiftsyn )i ) ∈ Σmsg × Σsyn . And split s into (s1 , s2 ). We then generate the synchronization strings by applying the public shift shiftsyn to a pseudorandom string PRGsyn (s1 ), i.e., σ = PRGsyn (s1 ) + shiftsyn ∈ Σnsyn . For the message part, we compute ECCmsg (m) ∈ Σnmsg , mask it with PRGmsg (s2 ), and apply shiftmsg : x = ECCmsg (m) + PRGmsg (s2 ) + shiftmsg ∈ Σnmsg . We then assemble the edit PRC by combining x and σ; specifically, we define the assembled sequence y where each entry yi := (xi , σi ) ∈ Σmsg ×Σsyn (combining σ and x symbol-by-symbol lets the decoder recover alignment under insertions and deletions by matching σ̃ against σ (see Lemma 5.5)). Decoding ECC−1 load (ỹ, s, shiftpk ): Recover the Synchronizing String. We split s into s1 and s2 , and regenerate the synchronization string σ = PRGsyn (s1 ) + shiftsyn . Synchronize. We denote the synchronization string part of ỹ as σ̃, and the message part as x̃. We then apply the algorithm in Lemma 5.5 to find an alignment of x̃ based on σ and σ̃. We then write the “synchronized” version of x to x̂. Note that there may be both substitution errors and erasures in x̂. If σ happens to be ε-self-matching, then by Lemma 5.5 the number of half-errors in x̂ is at √ most t + 6n ε, which the AG code in Lemma 5.6 corrects via mixed erasure-error decoding. Finally, we remove the mask PRGmsg (s2 ) and shiftmsg and run the ECCmsg decoder: m̂ = ECC−1 msg (x̂ − PRGmsg (s2 ) − shiftmsg ), and output ⊥ if decoding fails. Note that the subtraction are only done for the non-erased positions, so that the erasures are preserved and handled by the ECC−1 msg . Formally, the parameter setting and pseudo-code are shown below. 31
Algorithm 5 Seeded Payload Code via Synchronization Strings Require: Security parameter λ, Message m ∈ [M ], seed s = (s1 , s2 ) ∈ {0, 1}d Parameters n = Ω(λ), Public shifting vector shiftpk ∈ (Σmsg × Σsyn )n where (shiftpk )i = ((shiftmsg )i , (shiftsyn )i ), Building blocks: Hamming ECC ECCmsg and PRGs (PRGmsg , PRGsyn ), Alphabet Σ = Σmsg × Σsyn where |Σsyn | satisfies Theorem 5.1. 1: function ECCload (m, s, shiftpk )
Parse shiftpk into (shiftmsg , shiftsyn ) s.t. (shiftpk )i = ((shiftmsg )i , (shiftsyn )i ). Parse s ← (s1 , s2 ). 4: σ ← PRGsyn (s1 ) + shiftsyn ∈ Σnsyn 5: x ← ECCmsg (m) + PRGmsg (s2 ) + shiftmsg ∈ Σnmsg . 6: Assemble y ← (y1 , . . . , yn ) where yi = (xi , σi ) ∈ Σmsg × Σsyn . 7: return y 8: end function 2:
3:
−1
9: function ECCload (ỹ ∈ Σñ , s, shiftpk )
▷ Step 1: Recover the Synchronizing String 10: Parse shiftpk into (shiftmsg , shiftsyn ) s.t. (shiftpk )i = ((shiftmsg )i , (shiftsyn )i ). 11: Parse s ← (s1 , s2 ). 12: σ ← PRGsyn (s1 ) + shiftsyn . ▷ Step 2: Synchronization ñ , x̃ ∈ Σñ , such that ỹ = (x̃ , σ̃ ) 13: Decompose ỹ into σ̃ ∈ Σsyn i i i msg 14: x̂ ∈ (Σmsg ∪ {⊥})n ← Algorithm of Lemma 5.5 applied to (σ, σ̃, x̃). ▷ Step 3: Message Reconstruction 15: return m̂ = ECC−1 (x̂ − PRG (s ) − shift ). if fails return ⊥. msg 2 msg msg 16: end function
5.3
Analysis of Algorithm 5
Now we are ready to prove the main theorem. Theorem 5.1 (Seeded payload code via synchronization string). Let ECCmsg : [M ] → Σnmsg be an ECC robust to any pmsg fraction of half-errors. Then Algorithm 5 yields a seeded payload code ECCload : [M ] × {0, 1}d × {0, 1}r → Σn that is robust to any pload fraction of edit errors, provided that the block length n = Ω(λ), pload ≤ pmsg − δ for some constant δ > 0, and the alphabet size |Σ| ≥ |Σmsg | · Ω(δ −4 ). Proof. The uniformity of our construction will be used in later proofs. Uniformity. This property is straightforward since for fixed m and s, shiftmsg uniform makes x uniform over Σnmsg , and shiftsyn uniform makes σ uniform over Σnsyn ; these are independent, hence y is uniform over Σn . Robustness. Given that the seed s is successfully recovered, we now show that the message m can also be correctly decoded. Because σ = PRGsyn (s1 ) + shiftsyn and shiftsyn is uniformly random, σ is uniformly random over Σnsyn . 32
Let ε > 0 be a constant to be decided later. According to Theorem 5.4, a random string over an e2 alphabet of size |Σsyn | is ε-self-matching (see Definition 5.3) with probability 1 − ( ε2 |Σ )nε . We syn | can therefore choose |Σsyn | = e3 ε−2 to make the failing probability ≤ e−nε which is negl(λ) given that n = Ω(λ) and ε = Ω(1). Assuming that σ is ε-self-matching, then by Lemma 5.5, running [HS21, Algorithm 2,3] successfully align them, turning the edit errors into almost same number of half-errors while introducing at √ most 6 εn additional half-errors. Therefore, after the synchronization, the number of half-errors in x̂ will be at most: √ √ pload · n + 6 εn = (pload + 6 ε)n (1) | {z } | {z } # Original Errors
Additional Errors of Lemma 5.5 2
δ Therefore, for any pload ≤ pmsg − δ, we can set ε := 36 , |Σsyn | := e3 ε−2 = Ω( δ14 ) which is still a constant. In this case, (1) will be bounded by pmsg · n and the underlying ECCmsg can correct all the remaining half-errors.
Pseudorandomness. Fix any public shifting vector shiftpk = (shiftmsg , shiftsyn ) and message m. We show that the output of ECCload (m, s, shiftpk ) is computationally indistinguishable from a uniform string over Σn . Since s = (s1 , s2 ) consists of two independent parts, we define a sequence of hybrid experiments H2 , H1 , H0 as follows: • Hybrid H2 (Real World): The codeword y is generated according to the real encoding procedure: x = ECCmsg (m) + PRGmsg (s2 ) + shiftmsg and σ = PRGsyn (s1 ) + shiftsyn . • Hybrid H1 (Uniform PRGsyn ): Same as H2 , except that the pseudo-random string PRGsyn (s1 ) is replaced by a truly uniform string Usyn ∈ Σnsyn . • Hybrid H0 (Ideal World): Same as H1 , except that the pseudo-random string PRGmsg (s2 ) is replaced by a truly uniform string Umsg ∈ Σnmsg . The indistinguishability between H2 and H1 follows from the security of PRGsyn . Formally, if there exists a PPT distinguisher A that distinguishes H2 and H1 with non-negligible advantage (even given m and shiftpk ), we can construct a PPT adversary B to break the PRG. B receives a challenge string z (which is either PRGsyn (s1 ) or a uniform string), samples an independent seed s2 to compute x = ECCmsg (m) + PRGmsg (s2 ) + shiftmsg , and sets σ = z + shiftsyn . Since B can perfectly simulate the distribution of H2 (if z is pseudo-random) or H1 (if z is uniform), it inherits the advantage of A. The transition from H1 to H0 follows by an identical reduction to the security of PRGmsg , noting that s2 is independent of s1 . In H0 , both x = ECCmsg (m) + Umsg + shiftmsg and σ = Usyn + shiftsyn are perfectly uniform and independent strings over their respective alphabets. Thus, the assembled sequence y in H0 is distributed according to Un . Consequently, for any fixed shiftpk , the oracle ECCload (·, Ud , shiftpk ) is computationally indistinguishable from an oracle that returns independent uniform samples from Σn .
5.4
Instantiating the Generic Reduction
We apply the AG code, which supports decoding from a combination of erasures and substitution errors: 33
Lemma 5.6 (AG codes). For every sufficiently small constant ε > 0, there exists a square prime power q = poly(1/ε) and an explicit family of algebraic-geometry codes CAG ⊆ FN q such that, for all sufficiently large N , the code has rate R and relative distance δ satisfying R + δ ≥ 1 − ε. Moreover, CAG admits polynomial-time encoding and polynomial-time unique decoding from any combination of e substitution errors and s erasures provided 2e + s < d [SLJH98], where d = δN denotes the minimum distance. Combining Lemma 5.6 and Theorem 5.1, we obtain: Corollary 5.7. For every constant ε > 0 and every sufficiently small constant η ∈ (0, ε), there exists a seeded payload code ECCload : [M ] × {0, 1}d × {0, 1}r → Σn with information rate at least 1 − ε and alphabet size |Σ| = poly(1/η), that is robust to any ε − η fraction of edit errors. Proof. Apply Lemma 5.6 with parameter η/4 (i.e., taking ε = η/4 in the lemma). Let ECCmsg be the resulting AG code over Σmsg = Fq , with half-error tolerance pmsg = ε − η/2 and rate Rmsg ≥ 1 − ε + η/4. The alphabet size is q = |Σmsg | = poly(1/η). Next, we instantiate the synchronization string reduction (see Theorem 5.1) with ECCmsg as the outer code. Choose the synchronization alphabet Σsyn of size poly(1/η) such that the induced seeded payload code corrects every pload -bounded edit channel whenever pload ≤ pmsg − η/2. Define the final alphabet by Σ := Σmsg × Σsyn . Then |Σ| = q · |Σsyn | = poly(1/η). Moreover, the information rate of the resulting seeded payload code is Rload = Rmsg ·
log q . log q + log |Σsyn |
Since |Σsyn | = poly(1/η), we have log |Σsyn | = O(log(1/η)). Setting q = (1/η)C for a sufficiently large constant C then yields Rload ≥ 1 − ε. Finally, the outer AG code is chosen to tolerate a pmsg = ε−η/2 fraction of half-errors. Hence, by the synchronization reduction, the resulting seeded payload code corrects every pload = pmsg −η/2 = ε − η fraction of edit errors. Therefore the resulting seeded payload code has information rate at least 1 − ε, alphabet size |Σ| = poly(1/η), and is robust against every (ε − η)-bounded edit channel. Combining Corollary 5.7 and Theorem 4.3, we get the following: Corollary 5.8 (Multi-bit to zero-bit reduction). For every sufficiently small constant ε > 0 and every alphabet Σ with |Σ| ≥ poly(1/ε), the following holds. If there exists a zero-bit public-key (resp., secret-key) PRC0 over Σ that is robust against every p0 -bounded edit channel (resp., sublinear polynomial edit channel), then there exists a public-key (resp., secret-key) PRC over the same alphabet Σ with rate 1 − ε that is robust against every pload ≤ (1 − δ) min( p40 , ε)-bounded edit channel (resp., sublinear polynomial edit channel) for any constant δ > 0. Plugging in the zero-bit PRC constructed in Theorem 3.2, we get the following multi-bit PRC under Assumption 2.5. Corollary 5.9. Under Assumption 2.5, for every security parameter λ > 0 and every sufficiently small ε > 0, there exists a public-key PRC over alphabet of size poly(1/ε) with rate 1 − ε that is robust against every sublinear polynomial edit channel.
34
Moreover, we can instantiate our generic reduction using the public-key zero-bit PRC construction of Golowich and Moitra [GM24]. Their construction achieves robustness against a constant fraction of edit errors over a poly(λ)-sized alphabet by employing an “indexing” approach, where each symbol is interpreted as an index into a binary Hamming-robust PRC. By plugging in this zero-bit PRC construction, we obtain a public-key PRC that handles constant-fraction edit errors, while maintaining a rate arbitrarily close to 1. Corollary 5.10. Under the same cryptographic assumptions as [GM24] (local weak PRFs), for every security parameter λ > 0 and every sufficiently small ε > 0 and η ∈ (0, ε), there exists a public-key PRC over alphabet of size poly(λ, 1/η) with rate 1 − ε that is robust against every (ε − η)-bounded edit channel.
6
Binary PRCs with Rate Close to 1/2
In this section, we focus on the binary setting and show how to obtain pseudorandom codes with rate arbitrarily close to 1/2. Our construction proceeds in two steps. We first build a high-rate binary insertion-deletion code with random encoding, where the encoding randomness determines a family of binary inner codes and simultaneously guarantees pseudorandomness. We then combine this seeded binary payload code with the generic reduction from the previous section to obtain the final binary PRC.
6.1
Seeded High-Rate Binary Insdel Code
We now describe the main building block for the binary reduction. Given a message m and a seed r, the encoder outputs a binary codeword C(m; r). Following the general construction of [CJL+ 23], let q = Θ(log n) be a prime power and let Σ = Fq , and we take Cout : ΣK → Σn to be an [n, K, d]q Reed–Solomon code, and d = δn, where δ = γ/2. We also construct n distinct binary inner codes 1 , . . . , C n , each of codeword length n and message length k = 1 (1 − γ ′ )n . The resulting binary Cin 1 1 1 in 2 code therefore has codeword length N := nn1 . For each seed r ∈ {0, 1}t , let Cr = (Cr,1 , Cr,2 , . . . , Cr,n ) denote the collection of binary inner encoders specified by r, where each Cr,i ⊆ {0, 1}n1 is the inner code associated with position i. Given a message m ∈ ΣK , write Cout (m) = (a1 , a2 , . . . , an ) ∈ Σn for the corresponding outer codeword. We then define the binary encoding of m with seed r by C(m; r) := Cr,1 (a1 ) ◦ Cr,2 (a2 ) ◦ · · · ◦ Cr,n (an ) ∈ {0, 1}N . The decoding guarantee of [CJL+ 23] relies on the following combinatorial property of the family of inner codes. Property 6.1 (with parameters s, t, d′ ). Let Cr = (Cr,1 , . . . , Cr,n ) be a family of binary inner codes associated with a seed r, where each Cr,i ⊆ {0, 1}n1 . For every i ∈ [n − t], j ∈ [n − t − 1], every w = wi ◦ wi+1 ◦ · · · ◦ wi+t−1 ∈ ⃝ℓ∈[t] Cr, i−1+ℓ , and every u = uj ◦ uj+1 ◦ · · · ◦ uj+t ∈ ⃝ℓ∈[t+1] Cr, j−1+ℓ , it holds that for every substring w′ of u, we have ∆E (w, w′ ) ≥ d′ , provided that the number of unique blocks in w or u is at least s. A block wi′ of w is called unique if wi′ ̸= 0n1 and, among all blocks of u coming from the same inner code Cr,i′ , none is equal to wi′ . The definition of a unique block of u is symmetric. The following two lemmas from [CJL+ 23] provide the key ingredients: for a random seed r, the induced family of inner codes Cr satisfies Property 6.1 with high probability, and any family satisfying this property yields a high-rate binary insertion-deletion code with efficient decoding.
35
Lemma 6.2 ([CJL+ 23, Lemma 9]). Fix any constants γ ′ , δ ∈ (0, 1/2), and let n1 be the codeword length of each inner code. Suppose that for each i ∈ [n], the inner code Cr,i ⊆ {0, 1}n1 is an independent random binary linear code of message rate 1/2 − γ ′ . Then, with probability at least 1 − 1/poly(n) over the choice of r, the family Cr = (Cr,1 , . . . , Cr,n ) satisfies Property 6.1 with ′) ′ γ′ parameters (s, t, d′ ), where nd1 = 10 , t = 10 log(1/γ , and s = δt γ′δ 4. Lemma 6.3 ([CJL+ 23, Lemma 14]). Let Cout be an [n, K, d]q Reed–Solomon code of relative distance δ, and let Cr = (Cr,1 , . . . , Cr,n ) be a family of binary inner codes, each of codeword length n1 and rate 1/2−γ ′ . Suppose that Cr satisfies Property 6.1 with parameters (s, t, d′ ). Then the resulting concatenated binary code C(·; r) has rate at least 1/2−γ, relative distance Ω γ 3 / log(1/γ) , and ad mits a polynomial-time decoder that corrects an η-fraction of edit errors, where η = Ω γ 3 / log(1/γ) . In particular, when r is chosen uniformly at random, the resulting code is decodable with probability at least 1 − 1/poly(n) over the choice of the inner codes. This is already sufficient for existential arguments and derandomization-based constructions. However, it is not strong enough for our later pseudorandom coding application, where we need the decoding guarantee to hold with overwhelmingly high probability over the encoding randomness. To overcome this issue, we introduce an additional layer of concatenation. The next subsection explains how this extra layer amplifies the robustness guarantee while preserving the desired rate.
6.2
Amplification of Robustness
We now explain how to amplify the success probability of the seeded decoding guarantee from 1 − 1/poly(n) (or even from an arbitrary fixed constant bounded away from 1) to 1 − negl(n). The main idea is to introduce one additional layer of concatenation. For clarity and greater generality, we present this amplification step over an arbitrary alphabet Σ of size q. Our eventual application is to the binary setting, which is then obtained as a direct specialization. Before stating the main amplification theorem, we first prove a lemma that captures the key rejection property needed in the analysis. Lemma 6.4. Let Σ be an alphabet of size q ≥ 2, and let C ⊆ Σn be a code with minimum edit distance larger than 2δn. Fix constants b, r1 ∈ (0, 1), and suppose that 2r1 ≤ 1 − 2b
(2)
2H2 (r1 δ) + r1 δ log2 q < bδ log2 q.
(3)
and Let Dec be the threshold decoder that outputs a codeword c ∈ C iff ∆E (y, c) ≤ r1 δn, and otherwise outputs ⊥. Fix an arbitrary word x ∈ Σn , fix a set S ⊆ [n] of size |S| = m := ⌊bδn⌋, and let Y ∈ Σn be obtained from x by replacing the symbols in S independently and uniformly from Σ. Then, with probability at least 1 − 2−Ω(n) , the following stronger statement holds: for every word ′ Y satisfying ∆E (Y, Y ′ ) ≤ r1 δn, we have Dec(Y ′ ) = ⊥. That is, h i Pr ∃Y ′ with ∆E (Y, Y ′ ) ≤ r1 δn and Dec(Y ′ ) ̸= ⊥ ≤ 2−Ω(n) .
36
Proof. Let B := {y ∈ Σn : yi = xi for all i ∈ / S}. Then Y is uniform over B, and |B| = q m . Define BallE (c, r) := {y ∈ Σn : ∆E (c, y) ≤ rn}. Let C1 := {c ∈ C : B ∩ BallE (c, r1 δ) ̸= ∅}. Claim 6.5.
r
BallE (c, r) ≤ poly(n) · 2n(2H2 (r/2)+ 2 log2 q)
Proof. For a fixed j, the number of strings obtained from c by deleting j positions is at most nj , and each resulting string has length n − j. From any fixed string z ∈ Σn−j , the number of length-n strings obtained by inserting j symbols is at most nj q j . Summing over all 0 ≤ j ≤ ⌊rn/2⌋ yields ⌊rn/2⌋
BallE (c, r) ≤
n j
X j=0
2
qj r
≤ poly(n) · 2n(2H2 (r/2)+ 2 log2 q) .
Claim 6.6. Fix a codeword c ∈ C. Suppose there exists a word c′ ∈ B such that ∆E (c, c′ ) ≤ r1 δn. Then ⌊bδn⌋ X m B ∩ BallE (c, δ) ≥ (q − 1)i ≥ 2bδn log2 q−O(1) . i i=0
Proof. By Equation (2), every word in B obtained from c′ by changing at most ⌊bδn⌋ free coordinates lies in BallE (c, δ). Therefore
|BallE (c, 2r1 δ)| ≤ poly(n) · 2n(2H2 (r1 δ)+r1 δ log2 q−bδ log2 q)+O(1) . B ∩ BallE (c, δ)
By Equation (3), the right-hand side is at most 2−Ω(n) . Now, if c1 ̸= c2 are distinct codewords, then B ∩ BallE (c1 , δ) ∩ B ∩ BallE (c2 , δ) = ∅, Therefore |B| ≥
X
B ∩ BallE (c, δ) ,
c∈C1
and thus
P Pr ∃c ∈ C : ∆E (Y, c) ≤ 2r1 δn ≤
c∈C1 |B ∩ BallE (c, 2r1 δ)|
|B| |Ball E (c, 2r1 δ)| c∈C1
P ≤P
c∈C1 B ∩ BallE (c, δ)
≤ 2−Ω(n) .
Fix such a Y , and let Y ′ be any word with ∆E (Y, Y ′ ) ≤ r1 δn. Then for every c ∈ C, by the triangle inequality, ∆E (Y ′ , c) ≥ ∆E (Y, c) − ∆E (Y, Y ′ ) > 2r1 δn − r1 δn = r1 δn. Thus Y ′ is outside the decoding radius of every codeword, and therefore Dec(Y ′ ) = ⊥. This proves that, with probability at least 1 − 2−Ω(n) over Y , every further edit corruption of size at most r1 δn is still rejected by the decoder. 37
We are now ready to state the main amplification theorem. It shows that any seeded insertiondeletion code satisfying the properties above can be boosted, via one additional layer of concatenation, so that the decoding guarantee holds with overwhelming probability over the seed. Theorem 6.7. Let Σ be an alphabet of size q ≥ 2. Suppose we have an encoding map C : ΣK ×Σt → ΣN , such that the following hold. 1. For every message m ∈ ΣK , C(m; Ut ) = UN . 2. For every seed r ∈ Σt , the code {C(m; r) : m ∈ ΣK } ⊆ ΣN has minimum edit distance larger than 2δN . 3. There exists a polynomial-time decoder Decin and a constant r1 ∈ (0, 1) such that, with probability at least 1 − ρ over r ∼ Ut , the following holds simultaneously for every message m ∈ ΣK and every word z ∈ ΣN : Decin (r, z) = m ⇐⇒ ∆E z, C(m; r) ≤ r1 δN. 4. There exists b ∈ (0, 1) such that 2r1 ≤ 1 − 2b,
(4)
2H2 (r1 δ) + r1 δ log2 q < bδ log2 q,
(5)
3 1 3b + r1 < . 2 2
(6)
and
′
′
Let Eout : (ΣK )M → (ΣK )N be an outer code of relative Hamming distance ∆out > 0, equipped with a polynomial-time error-erasure decoder. Let τ > 0 satisfy ρ + 6τ r1 < ∆out . Assume also that ′ N = ω(log N ). Then there is a concatenated encoding map ′
′
′
C ′ : (ΣK )M × (Σt )N → ΣN N such that: ′
1. For every message m′ ∈ (ΣK )M , C ′ (m′ ; UN ′ t ) = UN ′ N . ′
2. There exists a polynomial-time decoder Decout such that, for every message m′ ∈ (ΣK )M , ′ with probability at least 1 − 2−Ω(N ) over r′ ∼ UN ′ t , the following holds: for every received word y, ∆E y, C ′ (m′ ; r′ ) ≤ τ δN ′ N =⇒ Decout (r′ , y) = m′ . We now describe the sequential decoding procedure. For convenience, define L := bδ + r12δ N . The decoder maintains a current word Y (i) , where initially Y (1) := y. For i = 1, 2, · · · , N ′ , given the current word Y (i) , the decoder proceeds as follows. 1. Slide a window of length N from left to right over Y (i) . Equivalently, for each contiguous interval J ⊆ Y (i) of length exactly N , run the inner decoder Decin (ri , J). 38
2. If there exists such an interval J ⊆ Y (i) with Decin (ri , J) ̸= ⊥, let Ji be the leftmost such interval, and set u bi := Decin (ri , Ji ). We then declare block i to be successfully decoded with value u bi . 3. After a successful decoding, update the current word by keeping only the first L symbols and the last L symbols of Ji , deleting the middle part of Ji , and retaining all symbols outside Ji . The resulting word is denoted by Y (i+1) . 4. If no interval J ⊆ Y (i) of length N satisfies Decin (ri , J) ̸= ⊥, then set u bi := ⊥ and Y (i+1) := (i) Y . At the end, this produces
′
(b u1 , · · · , u bN ′ ) ∈ (ΣK ∪ {⊥})N , which we feed to the outer decoder. Proof. We state the condition with the stronger margin ρ + 6τ r1 < ∆out to absorb the concentration slack and the union-bound losses appearing in the proof. Let (u1 , · · · , uN ′ ) = Eout (m′ ), xi := C(ui ; ri ) ∈ ΣN , and x := x1 ◦ · · · ◦ xN ′ = C ′ (m′ ; r′ ). Assume ∆E (y, x) ≤ τ δN ′ N. Fix an edit sequence from x to y. Charge each edit to one of the N ′ blocks, charging an insertion between two consecutive blocks to the earlier block. Let ei be the total number of edits charged to block i. Then N′ X ei ≤ τ δN ′ N. i=1
Call block i locally good if ei ≤
r1 δN . 2 ′
N 2τ ′ Then the number of blocks that are not locally good is at most (rτ1δN δN )/2 = r1 N . Hence at least ′ 1 − 2τ r1 N blocks are locally good. Call a seed ri good if it satisfies item (3). Since the ri ’s are independent and each is good with probability at least 1 − ρ, Hoeffding’s inequality implies that, ′ with probability at least 1 − 2−Ω(N ) , at most (ρ + ε)N ′ seeds are bad, where ε > 0 is an arbitrarily small fixed constant. Fix such a realization of r′ .
Claim 6.8 (Good blocks admit a correct window). Suppose block i is locally good, and suppose the portion of the received word corresponding to block i is still present in Y (i) . If ri is good, then there exists a contiguous interval J ⊆ Y (i) of length exactly N such that Decin (ri , J) = ui . In particular, the i-th step of the sequential decoder has at least one successful window. Proof. Since block i is locally good, we have ei ≤ r12δN . Hence there exists a contiguous interval J ⊆ Y (i) of length exactly N such that ∆E (J, xi ) ≤ 2ei ≤ r1 δN . Because ri is good, the exact threshold property of the inner decoder implies Decin (ri , J) = ui . Thus J is a successful window for block i.
39
Claim 6.9 (Wrong successful decoding consumes many edits). Suppose ri is good. If, during the decoding of block i, some length-N interval J ⊆ Y (i) is decoded to an incorrect message, then the middle portion removed in Step 3 contains at least r12δN charged edits. Proof. Suppose otherwise that fewer than r12δN charged edits occur in the removed middle interval. Since the removed middle interval has length N − 2L = N − (2bδ + r1 δ)N , it follows that at least r1 δN 3r1 N − 2L − δN = N − 2b + 2 2 symbols in this interval come from the transmitted codeword. We bound separately the number of such symbols coming from the true i-th block and from other blocks. First, at most 1 − 2δ N of these symbols can come from the true i-th block. Indeed, if more than 1 − 2δ N symbols came from the i-th block, then the interval would have edit distance strictly less than δN from xi . Since ri is good and the code for seed ri has minimum edit distance greater than 2δN , an interval within distance < δN of xi cannot decode to a wrong message. Since the seeds r1 , . . . , rN ′ are independent, conditioning on all previous decoding outcomes and on the current seed ri does not change the fact that any symbols of J originating from blocks other than i are independent of ri ; moreover, by the exact-uniformity property of the inner code, those symbols are distributed as uniform random symbols relative to the code determined by ri . Second, except with probability 2−Ω(N ) , at most bδN symbols in the interval can come from other blocks. Indeed, if more than bδN symbols came from other blocks, then the interval would contain at least bδN symbols that are independent random symbols relative to the key ri . By Lemma 6.4, such an interval is decoded to ⊥ except with probability 2−Ω(N ) . Therefore, except with probability 2−Ω(N ) , the total number of transmitted symbols in the δ removed interval is at most 1 − 2 N + bδN . Comparing this with the lower bound above yields 3r1 δ N − 2b + δN ≤ 1 − N + bδN. 2 2 Equivalently, 3 1 3b + r1 ≥ , 2 2 contradicting (6). This proves the claim. Claim 6.10 (Successful steps preserve future locally good blocks). Suppose that, during the decoding of block i, the decoder finds a successful length-N interval Ji , i.e., Decin (ri , Ji ) ̸= ⊥. Then, except with probability 2−Ω(N ) , Step 3 deletes no symbol belonging to any later locally good block. Proof. Write Ji = x1 ◦ x2 ◦ x3 , where x2 is the portion of Ji coming from the true i-th block, while x1 and x3 come from neighboring blocks (possibly empty). We claim that, except with probability 2−Ω(N ) , |x1 | ≤ L and |x3 | ≤ L. Indeed, suppose |x1 | > L. Then, after discarding at most r1 δN/2 inserted symbols, there are still at least L − r12δN = bδN symbols in x1 coming from outside the i-th block. These symbols are independent random symbols relative to the key ri . By Lemma 6.4, any length-N interval containing such a set of symbols is decoded to ⊥ except with probability 2−Ω(N ) , contradicting the assumption that Ji is successful. Thus |x1 | ≤ L except with probability 2−Ω(N ) . The same argument applies to x3 . 40
Now consider the case where x2 does not come from the true i-th block. Then the same randomrejection argument applies directly to x2 : if x2 came from a locally good block different from i, then Ji would contain at least bδN symbols that are independent random symbols relative to ri , and hence Ji would decode to ⊥ except with probability 2−Ω(N ) . Therefore, except with negligible probability, such an x2 cannot come from a locally good block. By the previous claim, any successful but incorrect decoding step already consumes at least r12δN charged edits in the removed interval, so this case cannot destroy more than the budget already accounted for. Therefore, except with probability 2−Ω(N ) , the middle part removed in Step 3 lies entirely inside the current block, and no symbol belonging to any later locally good block is deleted. By Claim 6.9, each wrong successful decoding step consumes at least r12δN charged edits. Since the total charged edit budget is at most τ δN ′ N , the number of such steps is at most τ δN ′ N 2τ ′ N. = (r1 δN )/2 r1 The only exceptional events arise from applications of Lemma 6.4. Therefore, except with proba′ ′ bility 2−Ω(N ) , the number of wrong successful decoding steps is at most 2τ r1 N . Indeed, there are at most N ′ stages, and since N = ω(log N ′ ), a union bound over the failure probabilities 2−Ω(N ) ′ ′ contributes at most 2−Ω(N ) . Therefore, except with probability 2−Ω(N ) , at least 4τ 1−ρ−ε− N′ r1 outer positions are decoded correctly. This is because a position can fail to contribute a correct outer symbol for one of the following reasons: ′ • the block is not locally good, which happens for at most 2τ r1 N positions;
• the seed ri is bad, which happens for at most (ρ + ε)N ′ positions except with probability ′ 2−Ω(N ) ; ′ • the block is destroyed by an earlier wrong successful step, which happens for at most 2τ r1 N positions.
By Claim 6.8, every remaining position has a correct successful window, and by Claim 6.10, correct ′ successful steps do not destroy later locally good blocks except with probability 2−Ω(N ) . Therefore at least 4τ 1−ρ−ε− N′ r1 positions are decoded correctly. ′ Therefore, except with probability 2−Ω(N ) , the number of incorrect or erased outer positions is 4τ ′ at most (ρ + ε + 4τ r1 )N . Choosing ε > 0 small enough so that ρ + ε + r1 < ∆out , the outer decoder recovers (u1 , · · · , uN ′ ) = Eout (m′ ), and hence recovers m′ . Finally, for every fixed m′ , the blocks C(u1 ; Ut ), · · · , C(uN ′ ; Ut ) are independent uniform strings ′ in ΣN . Therefore their concatenation is uniform in ΣN N , that is, C ′ (m′ ; UN ′ t ) = UN ′ N . This completes the proof. Corollary 6.11. For every sufficiently large N , there exists an encoding map C : [M ] × {0, 1}r → {0, 1}N with r = O(N log N ) and rate 1/2 − γ such that: 41
1. for every message m ∈ [M ], C(m; Ur ) = UN ; 2. there exists a polynomial-time decoder Dec such that, with probability at least 1 − negl(N ) over γ3 s ∼ Ur , the map m 7→ C(m; s) has relative edit distance Ω log(1/γ) , and moreover, for every message m ∈ [M ] and every received word y, ∆E y, C(m; s) ≤ Ω
γ3 ·N log(1/γ)
=⇒
Dec(s, y) = m.
Proof. We instantiate Theorem 6.7 using the seeded binary code from Section 6.1 as the inner code. Let Cin : [K] × {0, 1}r0 → {0, 1}N0 be the inner binary encoding map, with codeword length N0 , message space [K], seed length r0 , γ3 1 and decoding radius η = Ω log(1/γ) . By Lemma 6.2, the bad-seed probability is ρ = poly(N . 0) We set inner-code distance parameter with δ := η. Choose an outer Reed–Solomon code of rate 1 − ε, where ε > 0 is a sufficiently small constant, so that its relative Hamming distance satisfies ∆out = ε + o(1). Next choose a constant τ > 0 such that ρ + 6τ r1 < ∆out . For example, for all ′ 1ε sufficiently large N , which is the length of Reed–Solomon code, it suffices to take τ = r12 . We now apply Theorem 6.7, which yields an amplified encoding map ′
′
′
C : ([K])M × ({0, 1}r0 )N → {0, 1}N N0 ′
with seed failure probability 2−Ω(N ) , exact uniformity under a uniform seed, and decoding radius τ ηN ′ N0 = Ω
γ3 · N ′ N0 . log(1/γ) ′
We now rename parameters by setting M := K M , r := N ′ r0 , and N := N ′ N0 . With this notation, the amplified code takes the form C : [M ] × {0, 1}r → {0, 1}N , ′
2K with rate logN2 M = MNlog . Since the outer Reed–Solomon code has rate 1−ε and the inner binary ′N 0 code has rate at least 1/2 − γ, we obtain 1 log2 M ≥ (1 − ε) −γ . N 2
By choosing ε > 0 sufficiently small and absorbing constant-factor losses into γ, we may write the final rate as at least 1/2 − γ. Similarly, the theorem gives relative edit distance and decoding radius γ3 Ω(τ η) = Ω(η) = Ω , log(1/γ)
so the amplified code has the claimed asymptotic distance and correctable noise rate, up to constant factors. It remains to verify the seed length bound and the uniformity statement. Since the seed of the amplified code consists of N ′ independent inner seeds, each of length r0 = O(N0 log N0 ), we have r = N ′ r0 . Therefore r = O(N ′ N0 log N0 ) = O(N log N ). 42
Finally, exact uniformity under a uniform seed follows directly from the uniformity and independence of the inner code, and thus for every fixed message m ∈ [M ], C(m; Ur ) = UN .
6.3
Binary Payload Code and Put Together
We now package the binary construction above into the payload code (see Definition 4.2) required by the generic reduction in Section 4. Recall that the amplified binary seeded code provides an encoding map C : [M ] × {0, 1}r → {0, 1}n , such that a uniformly random seed yields a uniformly random codeword, while decoding succeeds with overwhelming probability over the choice of the seed. To fit the framework of Section 4, we derive the seed of this code from two parts. A short seed s ∈ {0, 1}d is first expanded by a pseudorandom generator PRG : {0, 1}d → {0, 1}r , and then combined with a public shifting vector shiftpk ∈ {0, 1}r . We take d = nβ for some constant β > 0, which is sufficient for generating pseudorandom strings of length r = O(n log n). We therefore define the payload encoder by ECCload : [M ] × {0, 1}d × {0, 1}r → {0, 1}n , ECCload (m, s, shiftpk ) := C m, PRG(s) ⊕ shiftpk . The corresponding decoder is ∗ d r ECC−1 load : {0, 1} ×{0, 1} ×{0, 1} → [M ]∪{⊥},
ECC−1 load (y, s, shiftpk ) := Dec PRG(s)⊕shiftpk , y ,
where Dec is the decoder of the amplified binary seeded code. The key point is that, when shiftpk is uniform, the effective seed PRG(s)⊕shiftpk is itself uniform for every fixed s. Hence the resulting payload codeword is exactly uniform. At the same time, once the short seed s is recovered by the outer reduction, the decoder can reconstruct the effective seed and use it to decode the payload. We now fix the parameters for the binary payload code. Given any target ε > 0, we choose the underlying binary insertion-deletion code so that its rate is at least 1/2 − ε. By the construction ε3 above, the corresponding decoding radius remains Ω log(1/ε) . Indeed, this follows by taking the parameter γ in Corollary 6.11 to be a sufficiently small constant multiple of ε, and absorbing constant-factor losses into the Ω(·) notation. The resulting encoding and decoding procedures are given in Algorithm 6. Lemma 6.12. Suppose ECCload : [M ] × {0, 1}d × {0, 1}r → {0, 1}n is the payload encoding map defined above, where the underlying binary seeded code has rate at least 1/2 − ε and decoding radius ε3 δ=Ω . log(1/ε) Then ECCload is a seeded payload code with rate 1/2 − ε that is robust to any δ fraction of edit errors.
43
Proof. The robustness and uniformity statements follow directly from Corollary 6.11. For pseudorandomness, observe that for every fixed public shifting vector shiftpk , the effective seed PRG(s) ⊕ shiftpk is computationally indistinguishable from uniform by the pseudorandomness of PRG. Since the map (s, shiftpk ) 7→ ECCload (m, s, shiftpk ) = C m, PRG(s) ⊕ shiftpk is efficiently computable, computational indistinguishability is preserved under this encoding procedure. Thus the output distribution of ECCload (·, Ud , shiftpk ) is computationally indistinguishable from uniform. A standard hybrid argument, analogous to that used in the proof of Theorem 4.3, completes the proof. Algorithm 6 Binary Payload Code with Rate Close to 1/2 Require: Security parameter λ, Message m ∈ [M ], seed s ∈ {0, 1}d , public shifting vector shiftpk ∈ {0, 1}r Pseudorandom generator PRG : {0, 1}d → {0, 1}r ′ ′ Outer Reed–Solomon code Eout : ({0, 1}K )M → ({0, 1}K )N with decoder DecRS Base binary seeded code Cbase : {0, 1}K × {0, 1}t0 → {0, 1}N0 with decoder Decbase Constant L 1: function ECCload (m, s, shiftpk )
Compute the effective seed r ← PRG(s) ⊕ shiftpk ′ Parse m = (m1 , . . . , mM ′ ) ∈ ({0, 1}K )M ′ 4: Parse r = (r1 , . . . , rN ′ ) ∈ ({0, 1}t0 )N ′ 5: Compute the outer codeword (u1 , . . . , uN ′ ) ← Eout (m) ∈ ({0, 1}K )N 6: for i = 1 to N ′ do 7: xi ← Cbase (ui ; ri ) ∈ {0, 1}N0 8: end for ′ 9: return x1 ◦ x2 ◦ · · · ◦ xN ′ ∈ {0, 1}N N0 10: end function 2: 3:
−1
11: function ECCload (y, s, shiftpk ) 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27:
Compute the effective seed r ← PRG(s) ⊕ shiftpk ′ Parse r = (r1 , . . . , rN ′ ) ∈ ({0, 1}t0 )N Initialize Y (1) ← y for i = 1 to N ′ do u bi ← ⊥ for every contiguous interval J ⊆ Y (i) of length exactly N0 do if Decbase (ri , J) ̸= ⊥ then Let Ji be the leftmost such interval ▷ Choose the first successful window u bi ← Decbase (ri , Ji ) break end if end for if u bi ̸= ⊥ then Write Ji = Jileft ◦ Jimid ◦ Jiright where |Jileft | = |Jiright | = L Delete the middle block Jimid from Y (i) Denote the resulting word by Y (i+1) 44
else 29: Y (i+1) ← Y (i) ▷ No successful window found for this block 30: end if 31: end for ′ 32: Run the outer decoder on (b u1 , . . . , u bN ′ ) ∈ ({0, 1}K ∪ {⊥})N 33: return DecRS (b u1 , . . . , u bN ′ ) 34: end function 28:
Instantiation from the binary payload code. We now combine the binary payload code constructed above with the generic reduction in Algorithm 4. Using the guarantees provided by Corollary 4.7, we obtain the following binary pseudorandom code. Theorem 6.13 (Binary PRC with rate close to 1/2). For every sufficiently small constant ε > 0, the following hold. 1. Let p ∈ (0, 1) be any constant. If there exists a zero-bit public-key (resp., secret-key) binary PRC that is robust against every p-bounded edit channel, then there exists a public-key (resp., secret-key) binary PRC with rate 1/2 − ε that is robust against every p′ -bounded edit channel, where ε3 ′ p = Ω min p, . log(1/ε) 2. If there exists a zero-bit public-key (resp., secret-key) binary PRC that is robust against every sublinear polynomial edit channel, then there exists a public-key (resp., secret-key) binary PRC with rate 1/2 − ε that is robust against every sublinear polynomial edit channel. Using Theorem 3.2, we get the following binary PRC under Assumption 2.5. Corollary 6.14. Under Assumption 2.5, for every security parameter λ > 0 and every sufficiently small ε > 0, there exists a binary public-key PRC with rate 1/2 − ε that is robust against every sublinear polynomial edit channel.
References [AAC+ 25] Omar Alrabiah, Prabhanjan Ananth, Miranda Christ, Yevgeniy Dodis, and Sam Gunn. Ideal pseudorandom codes. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 1638–1647. ACM, 2025. 1, 4 [Aar22]
Scott Aaronson. My AI Safety Lecture for UT Effective Altruism. scottaaronson.blog/?p=6823, November 2022. 1
https://
[ASG+ 19] Abhijeet Awasthi, Sunita Sarawagi, Rasna Goyal, Sabyasachi Ghosh, and Vihari Piratla. Parallel iterative edit models for local sequence transduction. In Proceedings of the 2019 conference on empirical methods in natural language processing and the 9th international joint conference on natural language processing (EMNLP-IJCNLP), pages 4260–4270, 2019. 2 [CG24]
Miranda Christ and Sam Gunn. Pseudorandom error-correcting codes. In Annual International Cryptology Conference, pages 325–347, 2024. 1, 2, 4, 5, 6, 11, 12, 13, 21 45
[CGG+ 25] Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, and Daniel Wichs. Improved pseudorandom codes from permuted puzzles. arXiv preprint arXiv:2512.08918, 2025. 1, 4, 5, 9, 13 [CGK16]
Diptarka Chakraborty, Elazar Goldenberg, and Michal Koucký. Streaming algorithms for embedding and computing edit distance in the low distance regime. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, page 712–725, New York, NY, USA, 2016. Association for Computing Machinery. 5, 13, 14
[CGZ24]
Miranda Christ, Sam Gunn, and Or Zamir. Undetectable watermarks for language models. In Shipra Agrawal and Aaron Roth, editors, The Thirty Seventh Annual Conference on Learning Theory, June 30 - July 3, 2023, Edmonton, Canada, volume 247 of Proceedings of Machine Learning Research, pages 1125–1139. PMLR, 2024. 1
[CHS25]
Aloni Cohen, Alexander Hoover, and Gabe Schoenbach. Watermarking language models for many adaptive users. In 2025 IEEE Symposium on Security and Privacy (SP), pages 2583–2601. IEEE, 2025. 1
[CJL+ 23]
Kuan Cheng, Zhengzhong Jin, Xin Li, Zhide Wei, and Yu Zheng. Linear insertion deletion codes in the high-noise and high-rate regimes. arXiv preprint arXiv:2303.17370, 2023. 8, 35, 36
[CJLW18] Kuan Cheng, Zhengzhong Jin, Xin Li, and Ke Wu. Deterministic document exchange protocols, and almost optimal binary codes for edit errors. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 200–211. IEEE, 2018. 8 [DMR25]
Nico Döttling, Anne Müller, and Mahesh Sreekumar Rajasree. Separating pseudorandom codes from local oracles. In Theory of Cryptography Conference, pages 225–257. Springer, 2025. 1
[FGJ+ 25]
Jaiden Fairoze, Sanjam Garg, Somesh Jha, Saeed Mahloujifar, Mohammad Mahmoody, and Mingyuan Wang. Publicly-detectable watermarking for language models. IACR Communications in Cryptology, 1(4), 2025. 1, 2
[GG25]
Surendra Ghentiyala and Venkatesan Guruswami. New Constructions of Pseudorandom Codes. In Alina Ene and Eshan Chattopadhyay, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025), volume 353 of Leibniz International Proceedings in Informatics (LIPIcs), pages 54:1–54:22, Dagstuhl, Germany, 2025. Schloss Dagstuhl – LeibnizZentrum für Informatik. 1, 4, 5, 11
[GGW25]
Sanjam Garg, Sam Gunn, and Mingyuan Wang. Black-box crypto is useless for pseudorandom codes. In Theory of Cryptography Conference, pages 205–224. Springer, 2025. 1
[GL16]
Venkatesan Guruswami and Ray Li. Efficiently decodable insertion/deletion codes for high-noise and high-rate regimes. In 2016 IEEE International Symposium on Information Theory (ISIT), pages 620–624. IEEE, 2016. 8
[GM24]
Noah Golowich and Ankur Moitra. Edit distance robust watermarks via indexing pseudorandom codes. Advances in Neural Information Processing Systems, 37:20645– 20693, 2024. 1, 3, 4, 5, 9, 13, 35 46
[GW17]
Venkatesan Guruswami and Carol Wang. Deletion codes in the high-noise and high-rate regimes. IEEE Transactions on Information Theory, 63(4):1961–1970, 2017. 8
[GZS25]
Sam Gunn, Xuandong Zhao, and Dawn Song. An undetectable watermark for generative image models. In The Thirteenth International Conference on Learning Representations, 2025. 1
[HS21]
Bernhard Haeupler and Amirbehshad Shahrasbi. Synchronization Strings: Codes for Insertions and Deletions Approaching the Singleton Bound. Journal of the ACM, 68(5):1–39, October 2021. 4, 8, 28, 29, 30, 33
[KGW+ 23] John Kirchenbauer, Jonas Geiping, Yuxin Wen, Jonathan Katz, Ian Miers, and Tom Goldstein. A watermark for large language models. In International conference on machine learning, pages 17061–17084. PMLR, 2023. 1 [KGW+ 24] John Kirchenbauer, Jonas Geiping, Yuxin Wen, Manli Shu, Khalid Saifullah, Kezhi Kong, Kasun Fernando, Aniruddha Saha, Micah Goldblum, and Tom Goldstein. On the reliability of watermarks for large language models. In The Twelfth International Conference on Learning Representations, 2024. 1 [KKR+ 24] Korbinian Kuhn, Verena Kersken, Benedikt Reuter, Niklas Egger, and Gottfried Zimmermann. Measuring the accuracy of automatic speech recognition solutions. ACM Transactions on Accessible Computing, 16(4):1–23, 2024. 2 [KSK+ 23] Kalpesh Krishna, Yixiao Song, Marzena Karpinska, John Wieting, and Mohit Iyyer. Paraphrasing evades detectors of ai-generated text, but retrieval is an effective defense. Advances in neural information processing systems, 36:27469–27500, 2023. 2 [KTHL24] Rohith Kuditipudi, John Thickstun, Tatsunori Hashimoto, and Percy Liang. Robust distortion-free watermarks for language models. Transactions on Machine Learning Research, 2024. 1, 2 [QZT+ 25] Wenjie Qu, Wengrui Zheng, Tianyang Tao, Dong Yin, Yanze Jiang, Zhihua Tian, Wei Zou, Jinyuan Jia, and Jiaheng Zhang. Provably robust multi-bit watermarking for {AIgenerated} text. In 34th USENIX Security Symposium (USENIX Security 25), pages 201–220, 2025. 2 [SKB+ 23]
Vinu Sankar Sadasivan, Aounon Kumar, Sriram Balasubramanian, Wenxiao Wang, and Soheil Feizi. Can ai-generated text be reliably detected? arXiv preprint arXiv:2303.11156, 2023. 2
[SLJH98]
S. Sakata, D.A. Leonard, H.E. Jensen, and T. Hoholdt. Fast erasure-and-error decoding of algebraic geometry codes up to the Feng-Rao bound. IEEE Transactions on Information Theory, 44(4):1558–1564, July 1998. 34
[SZ02]
Leonard J Schulman and David Zuckerman. Asymptotically good codes correcting insertions, deletions, and transpositions. IEEE transactions on information theory, 45(7):2552–2557, 2002. 8
[SZL+ 24]
Yan Shu, Weichao Zeng, Zhenhang Li, Fangmin Zhao, and Yu Zhou. Visual text meets low-level vision: A comprehensive survey on visual text processing. arXiv preprint arXiv:2402.03082, 2024. 2 47
[ZALW24] Xuandong Zhao, Prabhanjan Vijendra Ananth, Lei Li, and Yu-Xiang Wang. Provable robust watermarking for AI-generated text. In The Twelfth International Conference on Learning Representations, 2024. 1 [ZGC+ 25] Xuandong Zhao, Sam Gunn, Miranda Christ, Jaiden Fairoze, Andres Fabrega, Nicholas Carlini, Sanjam Garg, Sanghyun Hong, Milad Nasr, Florian Tramer, et al. Sok: Watermarking for ai-generated content. In 2025 IEEE Symposium on Security and Privacy (SP), pages 2621–2639. IEEE, 2025. 1
48