Paper 2026/1184

Public-Key Pseudorandom Codes from Distorted McEliece Assumptions

Danilo Francati, Sapienza University of Rome

Daniele Venturi, Sapienza University of Rome

Abstract

Pseudorandom codes (PRCs), introduced at Crypto 2024 by Christ and Gunn, are encryption schemes with pseudorandom ciphertexts and error-correction guarantees. PRCs are useful as a tool to obtain watermarking for generative models, in particular ensuring that a watermark is hard to remove against an attacker that can modify up to a given fraction of the watermarked output (a.k.a. the robustness property). A PRC is public-key if the encoding procedure is public (whereas detection requires the corresponding secret key). In this paper, we provide the first construction of public-key PRCs for the binary alphabet satisfying robustness in the presence of a constant fraction of substitutions ($1/6 - \varepsilon$, for arbitrary $\varepsilon > 0$) and at the same time achieving pseudorandomness against sub-exponential-time distinguishers. The pseudorandomness property relies on a new family of distorted McEliece assumptions that we introduce, instantiated with a class of expanded subcodes of Reed-Solomon codes, called Raw Reed-Solomon codes, for which we provide heuristic evidence of (plausible) sub-exponential hardness. Our construction is obtained by revisiting the original blueprint by Christ and Gunn to obtain public-key PRCs based on McEliece assumptions. Along the way, we also uncover that their blueprint does not work directly with Raw Reed-Solomon codes. In particular, we show that a generating matrix of a permuted Raw Reed-Solomon code is distinguishable in polynomial time from a uniformly random generating matrix. To circumvent that difficulty, we propose to distort the public key by multiplication with a sparse invertible matrix of constant row Hamming weight.

Note: Adding multi-bit construction

@misc{cryptoeprint:2026/1184,
      author = {Victor Dyseryn and Danilo Francati and Daniele Venturi},
      title = {Public-Key Pseudorandom Codes from Distorted {McEliece} Assumptions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1184},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1184}
}