High-Rate Public-Key Pseudorandom Codes for Edit Errors

• URL: http://arxiv.org/abs/2605.19402v1
• Date: Tue, 19 May 2026 05:57:25 GMT
• Title: High-Rate Public-Key Pseudorandom Codes for Edit Errors
• Abstract summary: Pseudorandom codes (PRCs) are error-correcting codes whose codewords are computationally indistinguishable from uniformly random strings.<n>We show that binary zero-bit PRCs robust against a constant fraction of substitution errors can be transformed into binary zero-bit PRCs against edit errors.<n>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.
• Score: 4.314680428399915
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Pseudorandom codes (PRCs), introduced by Christ and Gunn (CRYPTO '2024), are error-correcting codes whose codewords are computationally indistinguishable from uniformly random strings, while still being decodable by someone holding the key. They provide a natural primitive for robust and undetectable watermarking, particularly in applications to AI-generated content. Although recent works have obtained strong results for substitution errors, the edit-error setting remains much less understood, especially in the high-rate regime and over small alphabets. We study public-key pseudorandom codes against edit errors. First, we give a new reduction showing that binary zero-bit PRCs robust against a constant fraction of substitution errors can be transformed into binary zero-bit PRCs robust against edit errors. Consequently, under any assumption that yields zero-bit Hamming-robust PRCs, one also obtains zero-bit PRCs for edit channels, albeit only for the weaker class of sublinear polynomial edit channels, namely channels with edit error rate $1/n^γ$ 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 $\mathrm{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.

Related papers

• A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
  We study tradeoff between solution quality and stability when elements arrive over time.<n>Our algorithm has a future implementation for rational oracle$ with $O(varepsilon-1)$ recourse and separate the existence of universal-price certificates from their efficient algorithms.
  arXiv  Detail & Related papers  (2026-09-09T10:13:43Z)
• A Public-Key-Dependent Adversarial-Deletion Ceiling for Fixed-Alphabet Multi-Bit Pseudorandom Codes [2.1485350418225244]
  A pseudorandom code (PRC) is a keyed error-correcting code whose codewords are computationally indistinguishable from uniform strings.<n>We study publickey PRCs over fixed alphabets against adversarial deletions.
  arXiv  Detail & Related papers  (2026-08-31T21:31:03Z)
• Towards Worst-case Hardness for Low-Noise LPN [6.6603865098703805]
  Existing worst-case-to-average-case reductions for [BLVW19, YZ21] rely on statistical smoothing of linear codes.<n>We show that any efficient solver can be transformed into a pair of efficient algorithms.
  arXiv  Detail & Related papers  (2026-06-04T08:11:23Z)
• Public Key Encryption from High-Corruption Constraint Satisfaction Problems [6.201763450086127]
  We give a public key encryption scheme with plausible quasi-exponential security based on the conjectured intractability of two constraint satisfaction problems (CSPs)<n>Our public key encryption scheme is the first to leverage high corruption CSPs while simultaneously achieving a plausible security level far above quasi-polynomial.
  arXiv  Detail & Related papers  (2026-04-12T06:19:54Z)
• Improved Pseudorandom Codes from Permuted Puzzles [28.363531214070196]
  We construct pseudorandom codes that achieve subexponential pseudorandomness security, robustness to worst-case edits over a binary alphabet, and robustness against even computationally unbounded adversaries.<n>We show that this conjecture is implied by the permuted puzzles conjecture used previously to construct doubly efficient private information retrieval.
  arXiv  Detail & Related papers  (2025-12-09T18:53:42Z)
• The Coding Limits of Robust Watermarking for Generative Models [8.828526790179673]
  We prove a sharp threshold for the robustness of cryptographic watermarking for generative models.<n>We show that a simple crop and resize operation reliably flipped about half of the latent signs and consistently prevented belief-propagation decoding.
  arXiv  Detail & Related papers  (2025-09-11T18:08:32Z)
• Threshold Selection for Iterative Decoding of $(v,w)$-regular Binary Codes [84.0257274213152]
  Iterative bit flipping decoders are an efficient choice for sparse $(v,w)$-regular codes.<n>We propose concrete criteria for threshold determination, backed by a closed form model.
  arXiv  Detail & Related papers  (2025-01-23T17:38:22Z)
• New constructions of pseudorandom codes [23.22566380210149]
  Pseudorandom error-correcting codes (PRCs) are a new cryptographic primitive with applications in watermarking generative AI models.<n>In this work, we examine the assumptions under which PRCs with robustness to a constant error rate exist.<n>We show how to construct secret-key PRCs of length $O(n)$ which are $textitunconditionally$ indistinguishable from random by $textpoly(n)$ time, $O(n1.5-varepsilon) space.
  arXiv  Detail & Related papers  (2024-09-11T19:14:39Z)
• $\mathbb{USCD}$: Improving Code Generation of LLMs by Uncertainty-Aware Selective Contrastive Decoding [64.00025564372095]
  Large language models (LLMs) have shown remarkable capabilities in code generation. The effects of hallucinations (e.g., output noise) make it challenging for LLMs to generate high-quality code in one pass. We propose a simple and effective textbfuncertainty-aware textbfselective textbfcontrastive textbfdecoding.
  arXiv  Detail & Related papers  (2024-09-09T02:07:41Z)
• Crooked indifferentiability of the Feistel Construction [53.572703605492904]
  The Feistel construction is a fundamental technique for building pseudorandom permutations and block ciphers. This paper shows that a simple adaptation of the construction is resistant, even to algorithm substitution attacks.
  arXiv  Detail & Related papers  (2024-04-15T04:29:24Z)
• Deterministic identification over channels with finite output: a dimensional perspective on superlinear rates [49.126395046088014]
  We consider the problem in its generality for memoryless channels with finite output, but arbitrary input alphabets.<n>Our main findings are that the maximum length of messages thus identifiable scales superlinearly as $R,nlog n$ with the block length $n$.<n>We show that it is sufficient to ensure pairwise reliable distinguishability of the output distributions to construct a DI code.
  arXiv  Detail & Related papers  (2024-02-14T11:59:30Z)
• Linear-time Minimum Bayes Risk Decoding with Reference Aggregation [52.1701152610258]
  Minimum Bayes Risk (MBR) decoding is a text generation technique that has been shown to improve the quality of machine translations. It requires the pairwise calculation of a utility metric, which has quadratic complexity. We propose to approximate pairwise metric scores with scores calculated against aggregated reference representations.
  arXiv  Detail & Related papers  (2024-02-06T18:59:30Z)
• Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [84.0257274213152]
  We propose a new technique to provide accurate estimates of the DFR of a two-iterations (parallel) bit flipping decoder.<n>We validate our results, providing comparisons of the modeled and simulated weight of the syndrome, incorrectly-guessed error bit distribution at the end of the first iteration, and two-itcrypteration Decoding Failure Rates (DFR)
  arXiv  Detail & Related papers  (2024-01-30T11:40:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.