Improved Pseudorandom Codes from Permuted Puzzles

• URL: http://arxiv.org/abs/2512.08918v1
• Date: Tue, 09 Dec 2025 18:53:42 GMT
• Title: Improved Pseudorandom Codes from Permuted Puzzles
• Authors: Miranda Christ, Noah Golowich, Sam Gunn, Ankur Moitra, Daniel Wichs,
• Abstract summary: 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.
• Score: 28.363531214070196
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Watermarks are an essential tool for identifying AI-generated content. Recently, Christ and Gunn (CRYPTO '24) introduced pseudorandom error-correcting codes (PRCs), which are equivalent to watermarks with strong robustness and quality guarantees. A PRC is a pseudorandom encryption scheme whose decryption algorithm tolerates a high rate of errors. Pseudorandomness ensures quality preservation of the watermark, and error tolerance of decryption translates to the watermark's ability to withstand modification of the content. In the short time since the introduction of PRCs, several works (NeurIPS '24, RANDOM '25, STOC '25) have proposed new constructions. Curiously, all of these constructions are vulnerable to quasipolynomial-time distinguishing attacks. Furthermore, all lack robustness to edits over a constant-sized alphabet, which is necessary for a meaningfully robust LLM watermark. Lastly, they lack robustness to adversaries who know the watermarking detection key. Until now, it was not clear whether any of these properties was achievable individually, let alone together. We construct pseudorandom codes that achieve all of the above: plausible subexponential pseudorandomness security, robustness to worst-case edits over a binary alphabet, and robustness against even computationally unbounded adversaries that have the detection key. Pseudorandomness rests on a new assumption that we formalize, the permuted codes conjecture, which states that a distribution of permuted noisy codewords is pseudorandom. We show that this conjecture is implied by the permuted puzzles conjecture used previously to construct doubly efficient private information retrieval. To give further evidence, we show that the conjecture holds against a broad class of simple distinguishers, including read-once branching programs.

Related papers

• Post-Quantum Sanitizable Signatures from McEliece-Based Chameleon Hashing [1.7062009989943252]
  We introduce a novel post-quantum sanitizable signature scheme constructed upon a hash function derived from the McEliece cryptosystem.<n>In this design, the designated sanitizer possesses the inherent trapdoor of a Goppa code, which facilitates controlled collision-finding.<n>We provide formal security definitions and rigorous proofs of existential unforgeability and immutability.
  arXiv  Detail & Related papers  (2026-02-24T08:01:20Z)
• An Ensemble Framework for Unbiased Language Model Watermarking [60.99969104552168]
  We propose ENS, a novel ensemble framework that enhances the detectability and robustness of unbiased watermarks.<n>ENS sequentially composes multiple independent watermark instances, each governed by a distinct key, to amplify the watermark signal.<n> Empirical evaluations show that ENS substantially reduces the number of tokens needed for reliable detection and increases resistance to smoothing and paraphrasing attacks.
  arXiv  Detail & Related papers  (2025-09-28T19:37:44Z)
• Ideal Pseudorandom Codes [8.382679821011134]
  Pseudorandom codes are error-correcting codes with the property that no efficient adversary can distinguish encodings from uniformly random strings. Several constructions of pseudorandom codes have since been proposed, but none of them are robust to error channels that depend on previously seen codewords. We show that any adaptively robust pseudorandom code for single-bit messages can be used to build a CCA-secure pseudorandom code.
  arXiv  Detail & Related papers  (2024-11-08T20:22:14Z)
• 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)
• Edit Distance Robust Watermarks via Indexing Pseudorandom Codes [29.69428894587431]
  Motivated by the problem of detecting AI-generated text, we consider the problem of watermarking the output of language models with provable guarantees.<n>We aim for watermarks which satisfy: (a) undetectability, a cryptographic notion introduced by Christ, Gunn & Zamir (2024) and (b) robustness to channels which introduce a constant fraction of adversarial insertions, substitutions, and deletions.
  arXiv  Detail & Related papers  (2024-06-04T04:03:17Z)
• Correcting Subverted Random Oracles [55.4766447972367]
  We prove that a simple construction can transform a "subverted" random oracle which disagrees with the original one at a small fraction of inputs into an object that is indifferentiable from a random function. Our results permit future designers of cryptographic primitives in typical kleptographic settings to use random oracles as a trusted black box.
  arXiv  Detail & Related papers  (2024-04-15T04:01:50Z)
• Provably Secure Disambiguating Neural Linguistic Steganography [66.30965740387047]
  The segmentation ambiguity problem, which arises when using language models based on subwords, leads to occasional decoding failures.<n>We propose a novel secure disambiguation method named SyncPool, which effectively addresses the segmentation ambiguity problem.<n> SyncPool does not change the size of the candidate pool or the distribution of tokens and thus is applicable to provably secure language steganography methods.
  arXiv  Detail & Related papers  (2024-03-26T09:25:57Z)
• Pseudorandom Error-Correcting Codes [0.716879432974126]
  We build pseudorandom codes that are robust to cryptographic substitution and deletion errors. We present an undetectable watermarking scheme for outputs of random substitutions and deletions. Our second application is to steganography, where a secret message is hidden in innocent-looking content.
  arXiv  Detail & Related papers  (2024-02-14T18:17:45Z)
• SemStamp: A Semantic Watermark with Paraphrastic Robustness for Text Generation [72.10931780019297]
  Existing watermarking algorithms are vulnerable to paraphrase attacks because of their token-level design. We propose SemStamp, a robust sentence-level semantic watermarking algorithm based on locality-sensitive hashing (LSH) Experimental results show that our novel semantic watermark algorithm is not only more robust than the previous state-of-the-art method on both common and bigram paraphrase attacks, but also is better at preserving the quality of generation.
  arXiv  Detail & Related papers  (2023-10-06T03:33:42Z)
• Who Wrote this Code? Watermarking for Code Generation [53.24895162874416]
  We propose Selective WatErmarking via Entropy Thresholding (SWEET) to detect machine-generated text. Our experiments show that SWEET significantly improves code quality preservation while outperforming all baselines.
  arXiv  Detail & Related papers  (2023-05-24T11:49:52Z)
• Revocable Cryptography from Learning with Errors [61.470151825577034]
  We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
  arXiv  Detail & Related papers  (2023-02-28T18:58:11Z)

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.