We construct pseudorandom error-correcting codes (or simply pseudorandom
codes), which are error-correcting codes with the property that any polynomial
number of codewords are pseudorandom to any computationally-bounded adversary.
Efficient decoding of corrupted codewords is possible with the help of a
decoding key.
We build pseudorandom codes that are robust to substitution and deletion
errors, where pseudorandomness rests on standard cryptographic assumptions.
Specifically, pseudorandomness is based on either $2^{O(\sqrt{n})}$-hardness of
LPN, or polynomial hardness of LPN and the planted XOR problem at low density.
As our primary application of pseudorandom codes, we present an undetectable
watermarking scheme for outputs of language models that is robust to cropping
and a constant rate of random substitutions and deletions. The watermark is
undetectable in the sense that any number of samples of watermarked text are
computationally indistinguishable from text output by the original model. This
is the first undetectable watermarking scheme that can tolerate a constant rate
of errors.
Our second application is to steganography, where a secret message is hidden
in innocent-looking content. We present a constant-rate stateless steganography
scheme with robustness to a constant rate of substitutions. Ours is the first
stateless steganography scheme with provable steganographic security and any
robustness to errors.

构建假随机纠错码、鲁棒的数字水印方案和可证明的隐写术方案。

伪随机纠错码

Pseudorandom Error-Correcting Codes

We introduce a cryptographic method to hide an arbitrary secret payload in
the response of a Large Language Model (LLM). A secret key is required to
extract the payload from the model's response, and without the key it is
provably impossible to distinguish between the responses of the original LLM
and the LLM that hides a payload. In particular, the quality of generated text
is not affected by the payload. Our approach extends a recent result of Christ,
Gunn and Zamir (2023) who introduced an undetectable watermarking scheme for
LLMs.

使用加密方法在大型语言模型的回应中隐藏任意秘密负载，需要秘密密钥提取模型回应中的负载，负载不会影响生成文本的质量，扩展了 Christ、Gunn 和 Zamir（2023 年）引入的大型语言模型不可检测的水印方案。