Pseudorandom Error-Correcting Codes

Introduction

The proliferation of AI-generated content is one of the biggest issues facing the internet today. Recent breakthroughs in large language models have made it increasingly difficult to distinguish this influx of AI-generated content from human-generated content.

A promising solution for detecting AI-generated content is watermarking, where a hidden signal is embedded in the content. Several major companies, including OpenAI and Google, have pledged to embed watermarks in content output by their models [BH23]. Despite this explosion of interest in watermarking, there are very few techniques for building watermarking schemes that do not noticeably alter the generated content. Existing schemes incur trade-offs between the quality of generated content, the robustness of the watermark, and the computational complexity of detection.

In this work, we take a new cryptographic approach to this problem that allows us to avoid some of these trade-offs. Our approach is based on a new cryptographic primitive that we call a pseudorandom error-correcting code, or simply a pseudorandom code (PRC). A PRC is an error-correcting code that is parameterized by a decoding key. The pseudorandomness property states that, without this decoding key, any polynomial number of codewords are pseudorandom.

We find that the problem of building robust, quality-preserving watermarks reduces to the problem of building PRCs. Essentially, the watermarking strategy is to replace some of the randomness used by the generative algorithm with outputs from a PRC.

Building PRCs is challenging: Error-correcting codes are typically highly structured, while pseudorandomness implies a lack of discernible structure. Indeed, a priori it is not clear that such objects should exist. Nonetheless, we construct PRCs from standard (subexponential) cryptographic assumptions. Our constructions are related to low-density parity-check codes, and we base pseudorandomness on the Learning Parity with Noise assumption. We construct PRCs with strong robustness properties, including robustness to any constant rate of substitution and deletion errors.

Applying these PRCs to watermarking for language models, we obtain the first quality-preserving language model watermarking schemes that are robust to cropping and any constant rate of substitution and deletion errors. That is, the watermark detector will work as long as it is provided any sufficiently-long sequence of text, even if that text is subjected to any constant (less than $1/2$) rate of random substitutions and any constant (less than $1$) rate of random deletions.

In this subsection we present a simple, general template for watermarking AI-generated content. The template described here can in principle be used to watermark arbitrary media, but we only present concrete instantiations in certain contexts (Sections 7 and 8).

In all generative AI settings there is a generative algorithm, $\mathsf{Generate}$, that defines the behavior of the AI. A user provides a prompt, and $\mathsf{Generate}$ outputs some randomly-generated content. A watermarking scheme modifies $\mathsf{Generate}$ so that the generated content contains a hidden pattern, called a watermark. There are two essential requirements that any watermarking scheme should satisfy:

Quality: embedding the watermark should not reduce the quality of generative algorithm; and

Robustness: the watermark should be detectable in generated content, even if this content is corrupted.

Achieving both of these properties simultaneously is the central challenge of watermarking. Quality means that the watermark should not significantly alter the generated content, while robustness seems to require the watermark to change the content a great deal.

In this work, we propose a new strategy for watermarking: replacing the randomness used by $\mathsf{Generate}$ with codewords from a pseudorandom error-correcting code. A pseudorandom error-correcting code, or simply pseudorandom code (PRC), is a new cryptographic primitive that we introduce in this work. A PRC is defined by algorithms $\mathsf{Encode},\mathsf{Decode}$ satisfying two properties:

Pseudorandomness: Any efficient adversary, without knowledge of the decoding key, cannot distinguish between oracle access to $\mathsf{Encode}$ and an oracle that always outputs a fresh random string; and

Error correction or robustness: For any message ${\sf m}$, if $x\leftarrow\mathsf{Encode}({\sf m})$ and $x^{\prime}$ is a “corrupted” version of $x$ where the amount of corruption is bounded, then $\mathsf{Decode}(x^{\prime})={\sf m}$.

For watermarking the message can be simply ${\sf m}=1$, indicating the presence of a watermark.By instead encoding a longer message in the PRC, this technique extends to steganography — where messages are secretly communicated in innocent-looking content — as well.

In order to make detection possible, we specify $\mathsf{Generate}$ in such a way that the detector can approximate the randomness used to produce any given content. To test for the presence of a watermark, the detector computes this approximation and then applies $\mathsf{Decode}$ to the result. If the content is watermarked and the approximation is close enough to the true randomness, then robustness of the PRC ensures that $\mathsf{Decode}$ returns 1. This indicates to the detector that the watermark is present. Stronger robustness of the PRC translates to stronger robustness of the watermark.

Pseudorandomness of the PRC guarantees that, without the decoding key, watermarked content is indistinguishable from content produced by the original generative algorithm — even if one is allowed to see many outputs. In particular, the quality of the generative algorithm is not deteriorated by the watermark. In [CGZ23], such a watermark is referred to as undetectable.

Therefore, the problem of building robust, quality-preserving watermarks reduces to building PRCs (and appropriately specifying $\mathsf{Generate}$). Below, we describe the application of this template to watermarking for language models.

A generative language model is a randomized algorithm that takes as input a prompt, and samples text constituting a response. This text consists of tokens. For simplicity, we assume here that tokens are binary and that the full response is of a fixed length $n$. Neither of these assumptions is important for our results, as discussed in Section 7.

Given any generative language model, it is not difficult to define an algorithm $\mathsf{Generate}$ that takes a prompt and a random seed $x\in\{0,1\}^{n}$, and samples a response ${\sf t}\in\{0,1\}^{n}$ such that

if $x$ is uniformly random, then ${\sf t}$ is distributed identically to the original model, and

each bit of ${\sf t}$ is correlated with the corresponding bit of $x$.

See Section 2.5 for an example of such an algorithm. Now it is easy to recover an approximation of the randomness $x$ that was used to produce a given text: just use the text ${\sf t}$ itself.

One natural watermarking strategy is to use the same random seed $x\in\{0,1\}^{n}$ for every call to $\mathsf{Generate}$, storing $x$ itself as the watermarking key. This is essentially the strategy used by [KTHL23], and it yields a highly robust watermark because the detector can compute the edit distance between the given text and $x$. The resulting quality guarantee is that a single response from the watermarked model is distributed identically to a single response from the original model.

A PRC is exactly the object needed to avoid this tradeoff between response variability and efficiency. Our watermark detection key will be the decoding key for a PRC, and we will embed the watermark by sampling a fresh pseudorandom seed $x\leftarrow\mathsf{Encode}(1)$ for each query to $\mathsf{Generate}$. This results in no observable correlations between responses, regardless of the number of queries — i.e., the watermark is undetectable. Since the same hidden structure is present in every sample from $\mathsf{Encode}(1)$, our detector can simply apply $\mathsf{Decode}$ to check for this structure. Now, the detector’s runtime has no dependence on the response variability. Using PRCs that we construct in Sections 5 and 6, we also find that our watermarking scheme can be made robust to a constant fraction of random substitution and deletion errors.

A note on undetectability.

Undetectability is a strong quality guarantee for watermarking. Outputs of the watermarked model must be computationally indistinguishable from outputs of the original model, even to a user who is allowed to make many queries. While this is imperative for steganography, its necessity in watermarking is less clear, as some noticeable changes to the model may be permissible as long as the outputs remain “high-quality.”

However, measuring the quality of watermarked content is often challenging or impossible — especially when the content is used in a wide range of applications. Computational indistinguishability is a strong quality guarantee that applies uniformly to every application: it implies that the watermark causes no observable loss in any efficiently-computable quality metric. Without such a guarantee, it is impossible to verify that a watermark is quality-preserving across all applications. We therefore focus on undetectability in this work.

2 Our contributions

Our first contribution is to identify PRCs as an interesting cryptographic primitive, with applications to robustly hiding messages in AI-generated content. Very roughly, the definition is as follows — for more details, see either the technical overview (Section 2.1) or the formal definitions (Section 4.1).

A pseudorandom code (PRC) is an error-correcting code where codewords are pseudorandom to any computationally-bounded adversary who doesn’t hold the decoding key.

We consider both public- and secret-key variants of PRCs. For a public-key PRC, the encoding algorithm can be made public without sacrificing pseudorandomness. When the message space consists of only a single message, we call it a zero-bit PRC. Zero-bit PRCs can also be viewed as robust backdoored (or trapdoor) pseudorandom generators [VV83, DGG+15], and they are sufficient for our applications to watermarking.

We show how to build zero-bit public-key PRCs related to low-density parity-check (LDPC) codes, where pseudorandomness rests on standard (subexponential) cryptographic assumptions. All of the PRCs we construct are over a binary alphabet. Depending on the parameter choices, the pseudorandomness of these LDPC-related codes is based on either of two assumptions, which we state together as 1.

LPN is hard for any $2^{O(\sqrt{n})}$-time adversary, or

LPN and planted XOR are both hard for any polynomial-time adversary.

For descriptions of the LPN and planted XOR assumptions, see either Section 2.2 or Section 5. Under 1, we prove that there exist PRCs with robustness to channels that introduce a bounded number of substitution errors. We say that any channel that introduces at most a $p$ fraction of substitution errors (and no other types of errors) is $p$-bounded.

Let $p\in(0,1/2)$ be any constant. Under 1, there exists a zero-bit public-key PRC that is robust to every $p$-bounded channel.

For some applications it will be useful to have multi-bit PRCs. Any such construction should ideally have a high rate, which is the ratio of the number of message bits to the number of codeword bits. We prove that any zero-bit PRC can be combined with any error correcting code to give a multi-bit PRC.

Suppose that there exists a zero-bit (public-key) PRC and a rate-$R$ error-correcting code, that are both robust to every $p$-bounded channel. Then there exists a (public-key) PRC of rate $R-o(1)$ that is robust to every $(p-\varepsilon)$-bounded channel, for every constant $\varepsilon>0$.

Applying this theorem with our zero-bit LDPC-based PRCs and the binary error-correcting codes of [ABN+92, NN93, Ta-17], we have the following corollary.

Let $p\in(0,1/2)$ be any constant. Under 1, there exists a constant-rate PRC that is robust to every $p$-bounded channel.

None of the PRCs mentioned so far can handle deletions. Deletions are a particularly important type of edit for text watermarks, because an adversary may try to remove the watermark by simply deleting some of the words.

Deletions are notoriously difficult to handle in error correction, and standard techniques involve significant structure — thus violating pseudorandomness. Nonetheless, we show that if a PRC has sufficiently strong robustness to substitutions, then it can be converted to a PRC with robustness to deletions (at the cost of a decreased rate).

Let $\text{BSC}_{p}$ be the binary symmetric channel with error rate $p$, and $\text{BDC}_{q}$ be the binary deletion channel with deletion rate $q$. That is, $\text{BSC}_{p}$ randomly flips each bit with probability $p$ and $\text{BDC}_{q}$ randomly deletes each bit with probability $q$.

For any constants $p\in(0,1/2)$ and $q\in(0,1)$, there exists $p^{\prime}\in(0,1/2)$ such that the following holds. If there exists a zero-bit (public-key) PRC with robustness to every $p^{\prime}$-bounded channel, then there exists a zero-bit (public-key) PRC that is robust to the channel $\text{BSC}_{p}\circ\text{BDC}_{q}$.

Together with our LDPC-based PRCs, we obtain the following result.

Let $p\in(0,1/2)$ and $q\in(0,1)$ be any constants. Under 1, there exists a zero-bit public-key PRC that is robust to the channel $\text{BSC}_{p}\circ\text{BDC}_{q}$.

Watermarking and steganography for language models (Section 7).

We apply our zero-bit PRCs to build the first undetectable watermarking scheme for language models with robustness to a constant rate of random substitutions and deletions. In this section, we assume that text output by the language model is represented as a bitstring. Arbitrary text can be mapped to a bitstring by either randomly assigning a single bit to each token, or by expanding the tokens into a binary representation.

Let $p\in(0,1/2)$ be any constant. Under 1, there exists an undetectable watermarking scheme $\operatorname{\mathcal{W}}$ such that the watermark appears in any sufficiently high-entropy text, even if the text is subjected to the channel $\text{BSC}_{p}$.

Under an extra assumption about the generated text, which roughly corresponds to the text having few repeated words, we can strengthen this to handle deletions as well.

Let $p\in(0,1/2)$ and $q\in(0,1)$ be any constants. Under 1, there exists an undetectable watermarking scheme $\operatorname{\mathcal{W}}$ such that the watermark appears in any sufficiently high-entropy and “variable” text, even if the text is subjected to the channel $\text{BSC}_{p}\circ\text{BDC}_{q}$.

In all of our theorems the text can be cropped, as long as the remaining text is sufficiently high-entropy.

We also construct undetectable watermarking schemes with unforgeable public attribution and the same robustness as $\operatorname{\mathcal{W}}$. Public attribution means that there is a public algorithm to identify which portion of a given text was output by the model. Unforgeability means that no efficient user can produce text that the attribution algorithm identifies as model-generated, but that was not output by the model. Interestingly, our schemes retain the standard robust secret-key detector in addition to this public attribution algorithm.

Under 1, there exists a watermarking scheme $\operatorname{\mathcal{W}}_{\sf att}$ that retains all properties of $\operatorname{\mathcal{W}}$ from Theorem 5 or Theorem 6, and additionally satisfies unforgeable public attribution.

Finally, using PRCs with constant rate (Theorem 3), we also obtain the first robust language model steganography scheme.Since this scheme doesn’t rely on the decoder having access to the prompt, it can also be seen as an undetectable “multi-bit watermarking scheme.”

Let $p\in(0,1/2)$ be any constant. Under 1, there exists a language model steganography scheme with constant information rate, such that the message can be recovered from any sufficiently high-entropy text, even if the text is subjected to the channel $\text{BSC}_{p}$.

Universal steganography (Section 8).

In Section 8 we show that PRCs can be used to solve a long-standing open question in steganography: A simple application of PRCs yields the first robust, stateless universal steganography scheme. Universal steganography can be used for language model steganography, but it is more general [vAH04]. We take the rate of the steganography scheme to be the ratio of the number of stegotext symbols to the number of bits in the message being encoded.

Suppose there is a hash function that is unbiased over the covertext channel. If $\mathsf{PRC}$ is any PRC, then there exists a stateless, public-key universal steganography scheme with the same rate and robustness as $\mathsf{PRC}$.

Finally, we show that this result can be extended to the setting where an unbiased hash function on the covertext channel is not known, with some loss in robustness.

Suppose there is a hash function that has constant min-entropy over the covertext channel. Then under 1, for any $p\in(0,1/2)$, there exists a constant-rate public-key stateless steganography scheme that is robust to a $p$ rate of random substitutions.

3 Related work: short summary

We briefly outline some of the related work here. See Appendix A for a more complete discussion.

Code-based cryptography: Our work bears some similarity to the field of code-based cryptography. However, code-based cryptography is generally focused on building existing primitives from new assumptions — whereas PRCs are a new primitive that we base on existing assumptions.

Trapdoor pseudorandom generators: Our zero-bit PRCs can be equivalently viewed as robust trapdoor (or equivalently, backdoored) pseudorandom generators [VV83, DGG+15]. That is, we require the additional property that the trapdoor (or secret key) can be used to detect even corrupted pseudorandom strings.

Watermarking for language models: We build watermarking schemes for language models satisfying the strongest quality guarantee, undetectability. Undetectability was defined by [CGZ23], where undetectable watermarks for language models were also constructed. In that work and in [Aar22, KGW+23a], it is essential for watermark detection that many sufficiently-long contiguous substrings of the response remain unchanged. Therefore, these watermarks are easily removable by simple attacks (see the “robustness of our watermark” paragraph of Section 2.5). The watermarks of [KTHL23] are more robust — their robustness is more comparable to ours — but they sacrifice undetectability. Instead, their watermarks satisfy the weaker property of distortion-freeness, which is the single-query version of undetectability. [ZALW23] obtain even stronger robustness, at the cost of even further reduced quality.

Impossibility of strong watermarks: [ZEF+23] explore the possibility of watermarking for language models in the presence of motivated adversaries. They argue that sampling a random response is easier when one is provided any response. Since a random response cannot be watermarked (or else there would be a high false-positive rate), they use this to argue that any watermarked language model necessarily provides some assistance in generating un-watermarked text.

Steganography: Steganography is the study of concealing secret messages in innocent-looking content. Whereas encryption is about hiding the message, steganography is about hiding the existence of the message. Ever since steganography was formalized by [HLVA02], robust steganography schemes (that don’t require a shared state) have remained elusive. We resolve this problem using PRCs.

4 Organization

In Section 2, we give a technical overview of the paper, which is self-contained and sufficient to understand the high-level ideas and results of each section. In Section 3, we state relevant preliminaries and notation. In Section 4, we formally define PRCs and provide a heuristic construction. In Section 5, we build PRCs from LDPC codes and prove their pseudorandomness from standard cryptographic assumptions. We then show in Section 6 how to improve the rate and robustness of any PRC, resulting in our constant-rate multi-bit PRCs and PRCs for deletion channels. In Section 7, we present our language model watermarking schemes from PRCs, including both our standard watermarks and our watermarks with unforgeable public attribution. Finally, in Section 8, we show how PRCs can be used to construct robust universal steganography schemes.

Appendix A gives a more comprehensive overview of related work.

We thank Yael Kalai, Vinod Vaikuntanathan, Venkat Guruswami, Rainer Böhme, Or Zamir, Shyamal Patel, and Shivam Nadimpalli for helpful research conversations. We thank Mihalis Yannakakis and Fermi Ma for helpful suggestions about the write-up. We thank Omar Alrabiah for help in proving Lemma 9, as well as general assistance with coding theory.

Technical overview

Pseudorandom codes (PRCs) can be viewed as a combination of two related primitives:

Pseudorandom encryption, where ciphertexts are indistinguishable from random under a chosen plaintext attack [RBB03]. Secret-key pseudorandom encryption is easy to build using a pseudorandom function $F_{\sk}$ — just encrypt ${\sf m}$ by sampling a random $r$ and outputting $(r,{\sf m}\oplus F_{\sk}(r))$. Public-key pseudorandom encryption is also known from standard assumptions [vAH04]. However, none of these constructions have any nontrivial robustness.

Robust encryption, where encryptions of messages are robust to errors. Robust encryption is easy to build by applying an error-correcting code to ciphertexts from any standard encryption scheme. Even if that encryption scheme is pseudorandom, the use of the error-correcting code will in general render the robust encryption scheme not pseudorandom.

A PRC is required to simultaneously satisfy both pseudorandomness and robustness — properties that are in direct tension with each other. Using the secret key, one should be able to discern the redundancy and structure that give ciphertexts their robustness. Without the secret key, ciphertexts must appear completely unstructured.

We define secret-key PRCs below. For public-key PRCs (Definition 2), we further require that the encoding algorithm can be made public without sacrificing pseudorandomness.

Let $\Sigma$ be an alphabet and $\operatorname{\mathcal{E}}:\Sigma^{*}\to\Sigma^{*}$ be a channel. A secret-key PRC with robustness to $\operatorname{\mathcal{E}}$ is described by algorithms $\mathsf{Encode}_{\sk}:\Sigma^{k}\to\Sigma^{n}$ and $\mathsf{Decode}_{\sk}:\Sigma^{*}\to\Sigma^{k}\cup\{\bot\}$, parameterized by a secret key $\sk$, satisfying the following criteria for every security parameter $\secpar$:

(Error correction, or robustness) For any message ${\sf m}\in\Sigma^{k}$,

(Pseudorandomness) For any polynomial-time adversary $\adv$,

where $\adv^{\operatorname{\mathcal{U}}}$ means that the adversary has access to an oracle that, on any (even previously queried) input, responds with a freshly drawn uniform value in $\Sigma^{n}$.

2 Pseudorandom LDPC codes

The LPN assumption immediately implies that an arbitrary polynomial number of samples from $\mathsf{Encode}_{G}(1)$ are pseudorandom. However, recall that the LPN assumption states that these samples are pseudorandom even given $G$ — which means precisely that there does not exist an efficient zero-bit decoder $\mathsf{Decode}_{G}(x)$!

While this random linear code construction does not work, it naturally suggests a strategy that does. If we find a sampling procedure that produces a random (or even pseudorandom) generator matrix $G$ together with a trapdoor for efficient decoding, then we have a public-key PRC where the generator matrix is the public encoding key and the trapdoor is the secret decoding key. By the LPN assumption, $\mathsf{Encode}_{G}(1)$ produces pseudorandom vectors even to an adversary who knows $G$, so the construction will satisfy pseudorandomness.

Therefore our zero-bit pseudorandom LDPC code uses the following zero-bit decoding algorithm:

Encoding is exactly the same $\mathsf{Encode}_{G}$ algorithm as above — but now that $G$ is sampled together with the trapdoor $P$, we have an efficient decoding algorithm. Observe that this is a zero-bit scheme, because the decoder only determines whether the input is related to the keys or not. Using belief propagation, it is possible to push this construction beyond a zero-bit PRC, although this results in lower robustness. We ultimately construct a constant-rate multi-bit PRC by other means, which we discuss in Section 6.2.

Let $\mathsf{LDPC\text{-}PRC}_{0}$ be the zero-bit public-key PRC defined by $(\mathsf{Encode}_{G},\mathsf{Decode}_{P})$ for $(P,G)\leftarrow\mathsf{LDPC}[n,g,t,r]$. In a moment we will outline our proofs that $\mathsf{LDPC\text{-}PRC}_{0}$ is a public-key PRC with very strong robustness. First, let us see some restrictions on the sparsity parameter $t$ that provide important context for these proofs.

If random noise of rate $1/2-\varepsilon$ is applied to $x\in\operatorname{Im}G$, then the probability of each parity check being satisfied for the noisy codeword is $1/2-\varepsilon^{t}$. So in order for $\mathsf{Decode}_{P}(x)$ to output 1 with high probability, we need $\varepsilon^{t}>n^{-1/4}$, i.e., $t<\log n/4\log(1/\varepsilon)=O(\log n)$.

Therefore, we will choose $t=\Theta(\log n)$ in order to rely on the weakest possible cryptographic assumption for pseudorandomness, without sacrificing robustness to a constant noise rate.

The LDPC codes considered in this work differ from the traditional Gallager’s LDPC ensemble in two important ways. First, our LDPC codes will have $t=\Theta(\log n)$ sparsity as opposed to constant sparsity. Unfortunately, the usual belief propagation decoder does not work for noise rates beyond $O(\log t/t)$; this is the reason why we only perform the simple zero-bit decoding. The second difference is that we use independent parity checks, which results in an irregular Tanner graph.

For appropriate choices of parameters, it turns out that the generator matrix of $\mathsf{LDPC}[n,g,t,r]$ is pseudorandom under the planted $t$-XOR assumption. The planted $t$-XOR problem (and its generalization, the planted $t$-SUM problem) is a natural and well-studied problem — see e.g. [SSV23] for a more detailed discussion. Formally, the $(n,m,t)$ planted XOR problem states that it is computationally hard to distinguish between

Throughout this overview, we consider linear subspaces to be described by a random basis. Recalling the definition of $(P,G)\leftarrow\mathsf{LDPC}[n,g,t,r]$, if $r=1$ the $(n,g,t)$ planted XOR assumption immediately implies that $G$ is pseudorandom (by identifying $V$ with $\operatorname{Im}G$). But for the more interesting case that $r>1$, we require a stronger version of the planted XOR assumption with many planted relations. That is, we need to assume that the following distribution is indistinguishable from $\operatorname{\mathcal{D}}_{0}^{m}$:

We are not aware of any prior work on this assumption that $\operatorname{\mathcal{D}}^{m}_{0}\approx\operatorname{\mathcal{D}}^{m}_{r}$, so it is not immediately clear how reliable it is. Fortunately, it is implied by the $(n,m+r,t)$ planted XOR assumption.

We prove this with a hybrid argument. Suppose that an efficient adversary $\adv$ distinguishes between $\operatorname{\mathcal{D}}_{0}^{m}$ and $\operatorname{\mathcal{D}}_{r}^{m}$ with advantage $\varepsilon>0$. By a telescoping argument, $\adv$ must distinguish between $\operatorname{\mathcal{D}}_{i}^{m}$ and $\operatorname{\mathcal{D}}_{i+1}^{m}$ with advantage $\varepsilon/r$, for some $i\in\{0,\dots,r-1\}$. For each $i$, the following efficient reduction $\mathsf{Red}_{i}$ satisfies $\mathsf{Red}_{i}(\operatorname{\mathcal{D}}_{0}^{m+r})\equiv\operatorname{\mathcal{D}}_{i}^{m}$ and $\mathsf{Red}_{i}(\operatorname{\mathcal{D}}_{1}^{m+r})\equiv\operatorname{\mathcal{D}}_{i+1}^{m}$, which implies that $\varepsilon/r$ (and therefore $\varepsilon$) is negligible under the $(n,m+r,t)$ planted XOR assumption.

Let $U=W\cap S$. Notice that $\dim U\geq\dim W-i$. Since $\dim W=m+r$ and $i<r$, this is at least $m$.

Output a random $m$-dimensional subspace of $U$.

It remains to see why $\mathsf{Red}_{i}(\operatorname{\mathcal{D}}_{0}^{m+r})\equiv\operatorname{\mathcal{D}}_{i}^{m}$ and $\mathsf{Red}_{i}(\operatorname{\mathcal{D}}_{1}^{m+r})\equiv\operatorname{\mathcal{D}}_{i+1}^{m}$. In fact both of these statements are true even for fixed planted relations.

Narrow, statistically random generator matrix (Lemma 9).

Since the planted XOR assumption is not a standard cryptographic assumption, we show in Lemma 9 that the generator matrix of $\mathsf{LDPC}[n,c\log^{2}n,\log n,0.99n]$ is statistically random for some $c>0$. This removes the need for the planted XOR assumption, but it comes at the cost of requiring a stronger version of the LPN assumption: When we invoke LPN to see that samples $(G,Gs\oplus e)$ are pseudorandom, the secrets $s$ are now only of size $c\log^{2}n$. Therefore, for this PRC we will rely on a subexponential version of the LPN assumption which states that LPN is $2^{O(\sqrt{n})}$-hard.

For the purposes of this technical overview, we will show that the generator matrix of a closely related code is random. The proof for this version is significantly simpler, but the distribution is less natural and has worse error-correcting properties. The modified distribution on $(P,G)$ is defined as follows:

Let $G_{i}$ be the matrix $G_{i-1}$ with the extra row $s_{i}^{T}G_{0}$ appended to the bottom,

Let $s_{i}^{\prime}=[s_{i}^{T},0^{i-1},1,0^{0.99n-i}]$.

Let $P$ be the matrix whose rows are $s_{1}^{\prime},\dots,s_{0.99n}^{\prime}$ and $G=G_{0.99n}$. Output $(P,G)$.

First observe that $PG=0$, because $s_{i}^{\prime}G=[s_{i}^{T},0^{i-1},1,0^{0.99n-i}]G=s_{i}^{T}G_{0}\oplus(s_{i}^{T}G_{0})=0$ for every $i\in[0.99n]$.

Recall that we say that any length-preserving channel that introduces at most a $p$ fraction of bit-flip errors is $p$-bounded. To prove robustness, we need to show two things:

for any $p$-bounded channel $\operatorname{\mathcal{E}}$, samples from $\operatorname{\mathcal{E}}(\mathsf{Encode}_{G}(1))$ decode to 1 with high probability.

3 Pseudorandom codes for the deletion channel

So far, we have only considered PRCs for substitution channels. For our applications to watermarking and steganography, it will be useful to have PRCs for the noisy deletion channel as well. The noisy deletion channel randomly introduces both deletions and substitutions.

Unfortunately, existing error-correcting codes for the deletion channel introduce a large amount of structure into codewords that precludes pseudorandomness. For instance, the popular techniques of synchronization symbols or concatenation with constant-sized inner codes are immediately seen to be incompatible with pseudorandomness. Even further limiting the techniques available to us, we want our PRCs for the noisy deletion channel to have a binary alphabet in order to be useful for watermarking.

We therefore turn to alternative techniques. Surprisingly, we find that the repetition code — perhaps the simplest and most-structured error-correcting code — is a useful starting point.

For odd integer $T$, the rate-$(1/T)$ repetition code works by repeating each bit of the message $T$ times. That is, for any message ${\sf m}=({\sf m}_{1}||\cdots||{\sf m}_{k})\in\{0,1\}^{k}$, the encoder $\mathsf{RepEnc}_{T}$ is defined by $\mathsf{RepEnc}_{T}({\sf m})=({\sf m}_{1})^{T}||\cdots||({\sf m}_{k})^{T}$, where $({\sf m}_{i})^{T}$ denotes bit ${\sf m}_{i}$ repeated $T$ times. For example, the rate-$(1/3)$ repetition code encodes $010$ as $\mathsf{RepEnc}_{T}(010)=000111000$.

Now suppose that the encoding $({\sf m}_{1})^{T}||\cdots||({\sf m}_{k})^{T}$ is subjected to the noisy deletion channel, resulting in a string $z$. A natural algorithm for decoding $z$ is to partition $z$ into $k$ equal-length blocks $z_{1},\dots,z_{k}$, and compute the majority of each block:

Partition $z$ into $k$ equal-length blocks $z=(z_{1}||\cdots||z_{k})$.

As long as the deletions are sufficiently balanced across the different blocks, the $z_{i}$ will align well with the original blocks $({\sf m}_{i})^{T}$. Provided further that there are not too many substitutions in any block, we should have $\mathsf{MajDec}_{k}(z)={\sf m}$. The issue is that $\mathsf{RepEnc}_{T}({\sf m})$ is not pseudorandom even for random ${\sf m}$, because a random string is (extremely) unlikely to consist of $T$ repeated bits.

On the other hand, a random string typically does have $\Theta(\sqrt{T})$ bias towards 0 or 1.That is, a random string has $\Theta(\sqrt{T})$ more 0’s than 1’s, or 1’s than 0’s. This can be seen as a consequence of the fact that a one-dimensional simple random walk of length $T$ will usually terminate $\Theta(\sqrt{T})$ away from the origin. So if we change or delete a small $O(\sqrt{T})$ number of bits of a random string, we expect the majority to stay the same. This observation brings us to the following encoder $\mathsf{MajEnc}_{T}$, which encodes each bit in the majority of a random string. We refer to the code defined by $(\mathsf{MajEnc}_{T},\mathsf{MajDec}_{k})$ as the majority code.

Now if ${\sf m}$ is random, then $z=\mathsf{MajEnc}_{T}({\sf m})$ is random as well. Furthermore, if we subject $z$ to the noisy deletion channel to obtain $z^{\prime}$, then the bits of ${\sf m}^{\prime}=\mathsf{MajDec}_{k}(z^{\prime})$ are positively correlated with the bits of ${\sf m}$. This is because the deletions are at random locations, and are therefore (roughly) evenly-distributed across the different blocks $z_{i}$ — meaning that $\mathsf{MajDec}_{k}$ will mostly use the correct locations to decode each bit. Since the bit-flip errors are random, they merely dilute the $\Theta(\sqrt{T})$ biases. If $T>>k$ and the rates of deletions and bit-flip errors are constants below 1 and $1/2$ respectively, then we show in Lemma 15 that $\Pr[{\sf m}_{i}={\sf m}_{i}^{\prime}]$ is a constant greater than $1/2$. Therefore, the majority code has the effect of converting the constant-rate noisy deletion channel into some $p$-bounded channel.

Of course, the majority code is not itself a PRC. The first problem is that codewords for the majority code are only random if the message is random, whereas a PRC needs to allow encoding of any particular message. The second problem is that, even if the message is random, the majority code recovers a string that is only correlated with it.

But these are exactly the problems solved by PRCs for bounded-weight error channels! That is, if $\mathsf{PRC}$ is any PRC with robustness to every $p$-bounded channel (e.g. the PRCs from Section 2.2), then the combined code $\mathsf{PRC}_{\sf del}=(\mathsf{MajEnc}\circ\mathsf{PRC}.\mathsf{Encode},\mathsf{PRC}.\mathsf{Decode}\circ\mathsf{MajDec})$ is a PRC with robustness to some constant-rate noisy deletion channel.As $p$ approaches $1/2$, the combined PRC tolerates a noisy deletion channel with rates of deletions and bit-flip errors approaching 1 and $1/2$. Pseudorandomness follows from the pseudorandomness of $\mathsf{PRC}.\mathsf{Encode}$: Since $\mathsf{PRC}.\mathsf{Encode}({\sf m})$ is pseudorandom for any message ${\sf m}$, $\mathsf{MajEnc}(\mathsf{PRC}.\mathsf{Encode}({\sf m}))$ is as well. Robustness follows from the fact that the majority code has the effect of converting the constant-rate noisy deletion channel into some $p$-bounded channel, which is handled by $\mathsf{PRC}.\mathsf{Decode}$.

4 Constant-rate pseudorandom codes

So far we have only considered zero-bit PRCs, but for many applications it will be useful to have PRCs that can encode longer messages. There is a simple construction of a multi-bit PRC directly from any zero-bit PRC: Encode each bit of the message with either a zero-bit PRC codeword, or a uniformly random string. That is, if $\mathsf{PRC}$ is a zero-bit PRC, we encode a message ${\sf m}\in\{0,1\}^{k}$ as $(x_{1}||\cdots||x_{k})$ where for each $i\in[k]$, $x_{i}\leftarrow\{0,1\}^{n}$ if ${\sf m}_{i}=0$ and $x_{i}\leftarrow\mathsf{PRC}.\mathsf{Encode}(1)$ if ${\sf m}_{i}=1$.

Unfortunately this scheme has a very low rate. If the zero-bit PRC has block length $n$, then the resulting multi-bit PRC has rate $1/n$. However, we show in Section 6.2 that one can use any such low-rate PRC to make any error-correcting code pseudorandom, with no asymptotic loss in rate.

The idea is to encode a seed for a one-time pad in the simple low-rate PRC just described, and then use the one-time pad to hide an error-correcting encoding of the message. More formally, let $(\mathsf{Enc},\mathsf{Dec})$ be any (standard) error-correcting code and $\mathsf{PRC}$ be a low-rate PRC. We do not require $(\mathsf{Enc},\mathsf{Dec})$ to have any cryptographic properties. We encode a message ${\sf m}$ asIn order to obtain stronger robustness guarantee, we actually randomly permute the symbols of this encoding. For the purposes of this technical overview we omit this detail.

where $\mathsf{PRG}$ is any pseudorandom generator and $r\leftarrow\{0,1\}^{k}$ is a fresh uniformly random string.

By pseudorandomness of $\mathsf{PRC}$, $\mathsf{PRC}.\mathsf{Encode}(r)$ is indistinguishable from a uniformly random string — even for a fixed choice of $r$. By security of $\mathsf{PRG}$, the encoding is therefore indistinguishable from a totally random string.

Decoding works as long as $\mathsf{PRC}.\mathsf{Encode}(r)$ is not too corrupted for $\mathsf{PRC}$ to recover $r$, and $\mathsf{Enc}({\sf m})\oplus\mathsf{PRG}(r)$ is not too corrupted for $\mathsf{Dec}$ to recover ${\sf m}$.

5 Watermarks for language models

As defined in [CGZ23], a watermarking scheme for a language model consists of algorithms $\mathsf{Wat}$ and $\mathsf{Detect}$, where $\mathsf{Wat}$ is the watermarked model and $\mathsf{Detect}$ is an algorithm used to detect the presence of the watermark. In this work we are interested in watermarks that are undetectable, sound, and robust, loosely defined as follows.

Undetectability: Any polynomial number of responses from the watermarked model are computationally indistinguishable from those of the original model.

Soundness: Text generated independently of the watermarked model is not falsely detected.

Robustness: Sufficiently high-entropy text output by the model is detected as watermarked, even if it is altered.

We show that the watermarking strategy from Section 1, which replaces some of the model’s randomness with PRC codewords, yields a scheme that satisfies all of the above properties.

Recall that the approach from Section 1 requires an algorithm $\mathsf{Generate}$ that takes as input a prompt and a random seed $x\in\{0,1\}^{n}$, and samples a response ${\sf t}\in\{0,1\}^{n}$ such that

if $x$ is uniformly random, then ${\sf t}$ is distributed identically to a response from $\mathsf{Model}$, and

each bit of ${\sf t}$ is correlated with the corresponding bit of $x$.

We define $\mathsf{Generate}(\textsc{prompt},x)$ to sample the $i^{\text{th}}$ bit ${\sf t}_{i}$ of the response as follows. It first computes ${\sf p}_{i}$ by querying $\mathsf{Model}$ with prompt and the response output thus far, then:

Replacing seeds with PRC codewords.

We use PRC samples $x\leftarrow\mathsf{PRC}.\mathsf{Encode}(1)$, instead of random samples $x\leftarrow\{0,1\}^{n}$, as the seeds in $\mathsf{Generate}$. That is, if $\mathsf{PRC}$ is a zero-bit PRC, we let our watermarking scheme $\operatorname{\mathcal{W}}[\mathsf{PRC}]$ be defined by

Sample $x\leftarrow\mathsf{PRC}.\mathsf{Encode}(1)$ and output a sample from $\mathsf{Generate}(\textsc{prompt},x)$.

Compute $\mathsf{PRC}.\mathsf{Decode}({\sf t})$ and output the result.

By Condition (1) and the pseudorandomness property of $\mathsf{PRC}$, the responses from $\mathsf{Wat}$ are computationally indistinguishable from those of the original model. By Condition (2) and the robustness property of $\mathsf{PRC}$, the watermark will be detectable as long as the PRC is sufficiently powerful.

Depending on the kind of robustness of the PRC, substituting the entire seed with a single PRC sample results in a watermark that may or may not be detectable from just a subsequence. This is easily fixed by using $x=(x_{1}||\cdots||x_{m})$, where $x_{i}\leftarrow\mathsf{PRC}.\mathsf{Encode}(1)$ are independent PRC samples that are much shorter than the generated content. As long as the text contains at least one subsequence corresponding to a PRC sample $x_{i}$, the watermark will be detected.

PRC error correction and watermark robustness.

To understand how error correction of $\mathsf{PRC}$ translates to robustness of $\operatorname{\mathcal{W}}[\mathsf{PRC}]$, it is helpful to think of $\mathsf{Generate}$’s sampling process as a noisy embedding channel applied to the seed. That is, for a seed $x\in\{0,1\}^{n}$, let $\operatorname{\mathcal{E}}_{\mathsf{Emb}}(x)=\mathsf{Generate}(\textsc{prompt},x)$ be the “embedding channel” describing the noise in $x\mapsto{\sf t}$. For detection, it is sufficient for $\mathsf{PRC}$ to correct against the channel $\operatorname{\mathcal{E}}_{\mathsf{Emb}}$, since watermarked responses are exactly samples from $\operatorname{\mathcal{E}}_{\mathsf{Emb}}(x)$ for $x\leftarrow\mathsf{PRC}.\mathsf{Encode}(1)$.

Robustness of $\operatorname{\mathcal{W}}[\mathsf{PRC}]$ is determined by $\mathsf{PRC}$’s ability to correct from additional errors on top of $\operatorname{\mathcal{E}}_{\mathsf{Emb}}$. Let $\operatorname{\mathcal{E}}_{\sf adv}$ be a channel modeling the changes an adversary introduces to a watermarked response, so the overall error applied to ${\sf t}$ follows $\operatorname{\mathcal{E}}_{\sf adv}\circ\operatorname{\mathcal{E}}_{\mathsf{Emb}}$. If $\mathsf{PRC}$ is robust to $\operatorname{\mathcal{E}}_{\sf adv}\circ\operatorname{\mathcal{E}}_{\mathsf{Emb}}$, the watermark is robust to this adversary’s modifications.

In Section 7.2, we show that as long as the text has non-zero entropy, $\operatorname{\mathcal{E}}_{\mathsf{Emb}}$ introduces errors at a rate of less than $1/2$. Therefore, using any PRC with robustness to every $p$-bounded channel, we immediately obtain watermarks that are robust to a constant rate of random substitutions.

Robustness of our watermark.

Hashing-based watermarking schemes — including all existing undetectable schemes — are removable by the simple “emoji attack” [Aar22, KGW+23a]. In this attack, an adversary asks the model to respond to its prompt and insert an emoji between every word of its response. The adversary then deletes the emojis from the response. This attack removes any watermark that relies on the detector seeing contiguous sequences of watermarked text.

It turns out that hashing-based schemes [Aar22, KGW+23a, CGZ23] can easily be made robust to this particular attack.For instance, we could choose to only hash tokens whose index has the same parity as the token being sampled. However, if the adversary instead instructs the model to insert the emojis randomly, then we do not know how to make any hashing-based scheme robust. By constructing PRCs with robustness to random deletion channels, we give the first undetectable watermarking scheme that can resist this kind of attack.

Under this assumption, if $\operatorname{\mathcal{E}}_{\sf adv}=\text{BDC}_{p}$ is the binary deletion channel for some $p\in(0,1)$, then we just need a PRC with robustness to $\operatorname{\mathcal{E}}_{\sf adv}\circ\operatorname{\mathcal{E}}_{\mathsf{Emb}}=\text{BDC}_{p}\circ\text{BSC}_{q}$. The binary deletion channel $\text{BDC}_{p}$ is the channel that deletes each bit of its input independently with probability $p$. Indeed, we saw in Section 2.3 that there exist PRCs with robustness to $\text{BDC}_{p}\circ\text{BSC}_{q}$ for any $p\in(0,1),q\in(0,1/2)$.

6 Watermarks with public attribution

For the “standard” notions of watermarks considered so far, the goal is to determine whether a given text is a possibly-corrupted version of an output generated by a model. Standard watermarks are well-suited for applications such as detecting plagiarism, where one wishes to know if a model was used at all to produce a text, even if that text has been altered by the user.

A different use of watermarks is in attributing content to an LLM that generated it. For example, if harmful content generated by an LLM is found on social media, it would be useful to trace this content back to the model using the watermark. Ideally, anyone holding a public detection key should be able to trace the content. On the other hand, it should only be possible to embed the watermark by using a secret embedding key, in order to avoid falsely attributing text to any model.Note that the roles of the public and secret keys are reversed here. For PRCs, a secret key is necessary for decoding, but anyone can encode with knowledge of a public key. Public-key PRCs are useful for public-key steganography. In other words, to an attacker who does not know the secret key, the watermark should be unforgeable.

In addition to unforgeability, watermarks with public attribution have subtly different detection properties than standard watermarks. Robustness of standard watermarks means that an LLM-generated text will be detected even if small modifications are made. If robust watermarks were used for attribution, an attacker could use a model to generate a benign watermark text, then change a few words to make it offensive. By robustness, the watermark would still be present in this now-offensive content. So whereas robustness is a useful feature for standard watermarking, in the context of attribution it is actually an issue.

We therefore define a watermark with public attribution to have a separate detection algorithm called $\mathsf{AttrText}$, which is intentionally designed to not be robust. $\mathsf{AttrText}$, given a text $x$ and a public detection key, indicates whether the model output verbatim a significant part of that text, and outputs that portion of the text if so.

In order to preserve the benefits of robust watermarking for applications like detecting plagiarism, our publicly attributable watermarks also retain a $\mathsf{Detect}$ algorithm (in addition to the $\mathsf{AttrText}$ algorithm) with the robustness of our standard watermarking schemes. One can choose at detection time whether one wants to use $\mathsf{Detect}$ for standard detection, or $\mathsf{AttrText}$ for attribution.

Our watermarking scheme with public attribution, $\operatorname{\mathcal{W}}_{\sf att}[\mathsf{PRC}]$, is a natural extension of our regular watermarking scheme $\operatorname{\mathcal{W}}[\mathsf{PRC}]$. Recall that $\operatorname{\mathcal{W}}[\mathsf{PRC}]$ embeds a codeword of a zero-bit PRC into the model’s response; the detector checks whether the given text is close to a codeword. Of course, if we use a PRC that encodes an arbitrary message (rather than only ‘1’ as in a zero-bit PRC), then $\operatorname{\mathcal{W}}[\mathsf{PRC}]$ will embed arbitrary messages in the text. $\operatorname{\mathcal{W}}_{\sf att}[\mathsf{PRC}]$ does exactly this, where the message that it encodes is a signature on the response output thus far. $\mathsf{AttrText}$ decodes the given text to obtain this signature, and checks using the public detection key that it is a valid signature of a portion of the response. If so, this signed portion must have been generated by the model.

Concurrent work [FGJ+23] also constructs a watermark with public detection, although this scheme is designed to have mild robustness (comparable to that of [CGZ23]) and therefore is not appropriate for attribution as-is. Their scheme can easily be modified to satisfy our definition of unforgeable public attribution, but it would then lose all robustness guarantees for standard watermarking. Our scheme simultaneously functions as a highly robust standard watermark via $\mathsf{Detect}$, while also satisfying unforgeable public attribution via $\mathsf{AttrText}$.

7 Robust steganography

In steganography, the goal is to send a hidden message such that an observer cannot tell that a message is being sent at all. In the classic presentation, a prisoner wishes to secretly communicate with an outside party even though the warden is filtering their letters. If the warden detects any unusual language then the communication channel will be shut down, so the prisoner cannot simply encrypt the message: The warden should not only be unable to learn anything about the message, but should be unable to even detect that secret communication is occurring at all.

Steganography was formalized in [HLVA02]. In this presentation, there is some underlying steganographic channel,In the steganography literature this is usually just called a “channel”; we call it a “steganographic channel” to differentiate it from the coding-theoretic channels we use in the context of robustness. a distribution with which the sender wishes to conceal a message. The sender is given sample access to this steganographic channel and sends a stegotext to the receiver. Steganographic secrecy requires that the distribution of stegotexts is indistinguishable from the steganographic channel, except to the receiver who can recover the message with a secret key.

[HLVA02] proves the security of a steganography scheme of [AP98] that can be constructed using any encryption scheme $(\mathsf{Encode},\mathsf{Decode})$ with pseudorandom ciphertexts. The key idea behind this scheme is to embed each bit $x_{i}$ of a pseudorandom encryption of the message by drawing a sample $d_{i}$ from the steganographic channel such that $f(d_{i})=x_{i}$ for some hash function $f$:

$\mathsf{Steg}.\mathsf{Encode}(\sk,{\sf m})$ [AP98, HLVA02]:

Let $x=x_{1}||\ldots||x_{n}\leftarrow\mathsf{Encode}(\sk,{\sf m})$

For $i\in[n]$, sample a random $d_{i}$ from the channel conditioned on $f(d_{i})=x_{i}$

The decoder $\mathsf{Steg}.\mathsf{Decode}$ simply outputs $\mathsf{Decode}(\sk,f(d_{1})||\ldots||f(d_{n}))=\mathsf{Decode}(\sk,x)={\sf m}$.

If $x_{i}$ is uniform over $\{0,1\}$, and $f$ is perfectly unbiased for the channel, then $d_{i}$ is sampled exactly from the channel distribution. Therefore, by pseudorandomness of the ciphertext, an observer cannot distinguish stegotexts from samples from the steganographic channel. The receiver, which knows the decoding key for the encryption scheme, can evaluate $f$ on each block of the stegotext to obtain the ciphertext, then decrypt to recover the message.

We observe that PRCs are exactly the primitive needed for robust stateless steganography: Using a PRC as the pseudorandom encryption scheme in the above $(\mathsf{Steg}.\mathsf{Encode},\mathsf{Steg}.\mathsf{Decode})$ construction immediately gives us a steganography scheme with the same robustness as the PRC. If we use a public-key PRC, the resulting steganography scheme is also public-key. Furthermore, the robustness of the PRC allows us to relax the assumption that $f$ is perfectly unbiased on the steganographic channel.

Our main result of Section 8 is the first stateless steganography scheme with nontrivial robustness to errors. In particular, using our LDPC-based PRCs, we construct stateless steganography schemes that are robust to $p$-bounded channels for any constant $p$, or any constant-rate random deletion channel.

Preliminaries

We use $\log(x)$ to denote the logarithm base 2 of $x$, and $\ln(x)$ to denote the natural logarithm of $x$.

We let $\circ$ denote the composition of functions, algorithms, or channels; that is, $f\circ g$ denotes (the function/algorithm/channel) obtained by applying $g$, then $f$.

Let $\secpar$ denote the security parameter. A function $f$ of $\secpar$ is negligible if $f(\secpar)=O(\frac{1}{\poly})$ for every polynomial $\poly[\cdot]$. We write $f(\secpar)\leq\negl$ to mean that $f$ is negligible. We let $\approx$ denote computational indistinguishability and $\equiv$ denote statistical indistinguishability.

Let $Z_{0},\dots,Z_{n}$ be a martingale with respect to $X_{0},\dots,X_{n}$. If the differences $\abs{Z_{i}-Z_{i-1}}$ are all bounded by $C$ with probability $1-\varepsilon$, then for all $t>0$,

Digital signature scheme.

We use the definition of a digital signature from [KL07], with small modifications. A digital signature scheme is defined over a message space $\operatorname{\mathcal{M}}$ and consists of polynomial-time algorithms $(\mathsf{Gen},\mathsf{Sign},\mathsf{Vrfy})$ such that:

takes as input a security parameter $1^{\secpar}$ and outputs a public-private key pair $(\pk,\sk)$.

takes as input a private key $\sk$ and a message ${\sf m}\in\operatorname{\mathcal{M}}$. It outputs a signature $\sigma$, which we write as $\sigma\leftarrow\mathsf{Sign}_{\sk}({\sf m})$.

takes as input a public key $\pk$, a message ${\sf m}$, and a signature $\sigma$. It outputs 1 if the signature is valid and 0 otherwise. We write $b:=\mathsf{Vrfy}_{\pk}({\sf m},\sigma)$.

It is required that except with negligible over $(\pk,\sk)$ output by $\mathsf{Gen}(1^{\secpar})$, it holds that $\mathsf{Vrfy}_{\pk}({\sf m},\mathsf{Sign}_{\sk}({\sf m}))=1$ for every ${\sf m}\in\operatorname{\mathcal{M}}$.

A digital signature scheme $\Pi=(\mathsf{Gen},\mathsf{Sign},\mathsf{Vrfy})$ is existentially unforgeable under an adaptive chosen-message attack, or just secure, if for all polynomial-time adversaries $\adv$,

where the experiment $\mathsf{SigForge}_{\adv,\Pi}(\secpar)$ is defined in Figure 1.

2 Coding theory preliminaries

A channel is a randomized map $\operatorname{\mathcal{E}}:\Sigma^{*}\to\Sigma^{*}$. That is, for $x\in\Sigma^{*}$, $\operatorname{\mathcal{E}}(x)$ is a random sample from $\Sigma^{*}$. We use channels to model errors introduced by the environment, or by an adversary attempting to e.g. remove a watermark. Two of the most important channels we consider are the binary symmetric channel BSC and the binary deletion channel BDC:

$\text{BDC}_{q}:\{0,1\}^{*}\to\{0,1\}^{*}$ is the binary deletion channel with deletion rate $q\in(0,1)$. That is, $\text{BDC}_{p}(x)$ randomly deletes each bit $x_{i}$ independently with probability $q$.

For the purposes of this work, an error-correcting code with robustness to the channel $\operatorname{\mathcal{E}}$ is a pair of algorithms $(\enc,\dec)$ where $\enc,\dec:\Sigma^{*}\to\Sigma^{*}$. Error-correction (or robustness) for the channel $\operatorname{\mathcal{E}}$ says that if $x\leftarrow\enc({\sf m})$, then $\dec(\operatorname{\mathcal{E}}(x))={\sf m}$. The block length of an error correcting code is the number of symbols in a codeword required to encode a message of a particular length. We therefore write the block length $n=n(k)$ as a function of the message length $k$. The rate of a code is the function $k\mapsto k/n(k)$, which may or may not depend on the message length $k$.

Pseudorandom code basics

In this section we define pseudorandom codes (PRCs) and related terminology. A PRC can be viewed as a familyWe remark that if a PRC were a fixed code rather than a family of codes, pseudorandomness against non-uniform adversaries would be impossible since the adversary could have the decoding key hard-coded. of error-correcting codes indexed by encoding and decoding keys. For secret-key PRCs, the encoding and decoding keys are identical; for public-key PRCs, the encoding key is public and the decoding key is secret.

Formally, a PRC is specified by three algorithms. A key generation function samples the keys. An encoding function takes as input the encoding key and a message, and it outputs a codeword. A decoding function takes as input the decoding key and a perturbed codeword, and it outputs the message or $\bot$.

Our error correction guarantee is defined in terms of a channel. A PRC is robust to a channel $\operatorname{\mathcal{E}}$ if $\mathsf{Decode}$ can recover ${\sf m}$ from $\operatorname{\mathcal{E}}(\mathsf{Encode}({\sf m}))$ with overwhelming probability. In addition to requiring that we can recover messages from noisy codewords, we also require that $\mathsf{Decode}$ outputs $\bot$ given a string that is unrelated to the code. That is, for any string $c$, $\mathsf{Decode}(c)$ outputs $\bot$ with overwhelming probability over the choice of the decoding key. This property is important for applications such as watermarking, where we want the ability to distinguish codewords from uniformly random strings.

Pseudorandomness of the PRC ensures that an adversary without knowledge of the secret key cannot distinguish between an oracle for the $\mathsf{Encode}$ algorithm of the scheme, or an oracle that outputs independently drawn uniform strings. If a PRC is viewed as an encryption scheme, pseudorandomness is equivalent to indistinguishability from random bits against a chosen plaintext attack (IND-$CPA security) [RBB03]. For public-key PRCs, pseudorandomness holds even against adversaries holding the encryption key.

Let $\Sigma$ be a fixed alphabet. A secret-key pseudorandom error-correcting code (abbreviated as secret-key PRC) with robustness to a channel $\operatorname{\mathcal{E}}:\Sigma^{*}\to\Sigma^{*}$ is a triple of polynomial-time randomized algorithms $(\mathsf{KeyGen},\mathsf{Encode},\mathsf{Decode})$ satisfying

(Pseudorandomness) For any polynomial-time adversary $\adv$,

where $\adv^{\operatorname{\mathcal{U}}}$ means that the adversary has access to an oracle that, on any (even previously queried) input, responds with a freshly drawn uniform value in $\Sigma^{n(\secpar)}$.

Let $\Sigma$ be a fixed alphabet. A public-key pseudorandom error-correcting code (abbreviated as public-key PRC) with robustness to a channel $\operatorname{\mathcal{E}}:\Sigma^{*}\to\Sigma^{*}$ is a triple of polynomial-time randomized algorithms $(\mathsf{KeyGen},\mathsf{Encode},\mathsf{Decode})$ satisfying

(Pseudorandomness) For any polynomial-time adversary $\adv$,

where $\adv^{\operatorname{\mathcal{U}}}$ means that the adversary has access to an oracle that, on any (even previously queried) input, responds with a freshly drawn uniform value in $\Sigma^{n(\secpar)}$.

The block length of a (public-key or secret-key) PRC is $n(\secpar)$ and the message length is $k(\secpar)$. The rate is the function $\secpar\mapsto k(\secpar)/n(\secpar)$. We often drop the dependence on $\secpar$ when it is clear from context.

We present our constructions of PRCs for messages of fixed lengths. That is, for a given set of keys, the construction will only work for messages of a fixed length. However, we note that this can be easily remedied using a pseudorandom function (PRF) to select new keys for every message length. We do not include the PRF in our constructions in order to simplify presentation.

2 Heuristic construction from permuted codes

In this section we describe a natural heuristic transformation for building a candidate secret-key PRC from any error-correcting code. In Section 5 we will give provably secure constructions of PRCs from standard (subexponential) cryptographic assumptions.

Our heuristic construction can be applied to any binary error-correcting code, such as the polar code [Ari09]. The secret key will be a random permutation of the indices of the codewords. To encode a message, we encode it using the error-correcting code, then apply the secret permutation, and finally add a small amount of random Bernoulli noise.

There are two drawbacks of this generic permuted code construction relative to our pseudorandom LDPC codes:

In general the pseudorandomness of a permuted code is based on non-standard, ad-hoc conjectures. For certain codes, such as Gallager’s LDPC ensemble [Gal62], the permuted code construction is not pseudorandom.

Permuted codes are inherently secret-key PRCs, whereas our pseudorandom LDPC codes are public-key.

For any error-correcting code $(\enc,\dec)$ and parameter $\eta>0$, we formally define the corresponding permuted code $\mathsf{Permuted\text{-}PRC}_{\eta}[\enc,\dec]$ as follows. Let $n=n(\cdot)$ be the block length for $(\enc,\dec)$, as a function of the message length. (Recall that the block length is the number of codeword symbols needed to encode a given message.) $\mathsf{Permuted\text{-}PRC}_{\eta}[\enc,\dec]$ will encode messages of length $k$ into codewords of length $n=n(k+\secpar)$, where $\secpar$ is a security parameter.

Let $\secpar$ be a security parameter, let $k$ be the length of messages we wish to encode, and let $n=n(k+\secpar)$.

$\mathsf{KeyGen}(1^{\secpar})$: Sample a random permutation $\pi:[n]\to[n]$ and output $\sk=\pi$.

$\mathsf{Encode}(\sk,{\sf m})$ for ${\sf m}\in\Sigma^{k}$:

Output $(c_{\pi(1)}||\cdots||c_{\pi(n)})$.

$\mathsf{Decode}(\sk,x)$ for $x\in\Sigma^{n}$:

Compute $c=(x_{\pi^{-1}(1)}||\cdots||x_{\pi^{-1}(n)})$.

Output the last $k$ symbols of ${\sf m}^{\prime}$.

A permuted code has the same robustness to substitutions, and nearly the same rate, as $(\enc,\dec)$.

A natural choice of error-correcting codes to use in this permuted code construction is polar codes [Ari09]. Since polar codes have linear rate and tolerate a constant rate of adversarial errors, permuted polar codes are a candidate linear-rate secret-key PRC with robustness to a constant rate of adversarial errors. We do not know whether such codes satisfy pseudorandomness.

Constructing pseudorandom codes from cryptographic assumptions

In this section, we introduce a public-key PRC based on LDPC codes. We present the zero-bit version of our scheme, $\mathsf{LDPC\text{-}PRC}_{0}$, in Section 5.1; we will see in Section 6 that this immediately implies a many-bit scheme with essentially the same robustness. In Section 5.2 we show that $\mathsf{LDPC\text{-}PRC}_{0}$ is robust to every error channel of bounded weight, as long as the parity checks have sufficiently low weight. Finally, we prove pseudorandomness of $\mathsf{LDPC\text{-}PRC}_{0}$ in two different parameter regimes under different cryptographic assumptions: In Section 5.3, we prove pseudorandomness under LPN and a certain planted XOR assumption; in Section 5.4, we prove pseudorandomness under a subexponential-query variant of LPN.

An $(n,g,t,r)$ random LDPC code is a pair of matrices $(P,G)\leftarrow\mathsf{LDPC}[n,g,t,r]$.

The focus of this section will be on the following zero-bit PRC. Recall that a zero-bit PRC is one whose message space is just $\{1\}$. We will see in Section 6.2 that a constant-rate PRC can be generically constructed from any zero-bit PRC.

For the remainder of this section, we will identify the security parameter $\secpar$ with the dimension of the code $n$. We will therefore write $g,t,r,\eta,\zeta$ as functions of $n$, with the understanding that $n(\secpar)=\secpar$.

2 Codeword detection (zero-bit decoding)

For any $p,\eta\in[0,1/2)$, there exits $\delta>0$ such that the following holds. For any $t\leq\delta\log n$, $g>0$, and $\Omega(n)\leq r\leq 0.99n$, $\mathsf{LDPC\text{-}PRC}_{0}[n,g,t,r,\eta,n^{-1/4}]$ is robust to every $p$-bounded channel.

with probability $1-\negl[n]$. Therefore we apply Lemma 5 with $\alpha=\left[\frac{(1-\eta)p+\eta(1-p)}{2}+\frac{1}{4}\right]$. ∎

Let $P_{i}$ denote the $i^{\text{th}}$ row of $P$. We will show that

and the independence of the rows of $P$ will imply the lemma by a Chernoff bound.

Then the bit $P_{i}y$ is distributed as $(1-Y_{1}\cdots Y_{t})/2$, so

The remainder of the proof is devoted to showing that

For large enough $n$, this will imply Equation 1 by the assumption that $t\leq\frac{1}{5}\log_{1/2\alpha}n$.

By the tower property and linearity of expectation,

For all possible assignments of $Y_{<m}$,

Recall that $j_{m}$ is chosen to be a uniformly random index from $[n]\setminus\{j_{<m}\}$. Since $m\leq t$, $[n]\setminus\{j_{<m}\}$ contains at least $(\frac{1}{2}+\alpha^{\prime})n-t$ and at most $(\frac{1}{2}+\alpha^{\prime})n$ indices for which the corresponding bit of $y$ is 0. Therefore, $\frac{1}{2}+\alpha^{\prime}-t/n\leq\Pr_{j_{m}}[x_{j_{m}}=0\mid Y_{<m}]\leq\frac{1}{2}+\alpha^{\prime}+t/n$.

3 Pseudorandomness from the planted XOR assumption and LPN

In this subsection we prove that the generator matrix (public key) of $\mathsf{LDPC\text{-}PRC}_{0}$ is pseudorandom under the planted XOR assumption. This is Lemma 8. The number of columns of the generator matrix and the number of rows of the parity check matrix will depend on the particular planted XOR assumption one is willing to make. Then, since the generator matrix is pseudorandom, pseudorandomness of $\mathsf{LDPC\text{-}PRC}_{0}$ (Theorem 1) follows directly from the standard LPN assumption.

The existence of our LDPC-based PRCs relies on either of two assumptions. We state the two assumptions together as 1.

At least one of the following two statements is true:

There exists a constant $\eta\in(0,1/2)$ such that, for any function $g(n)=\Omega(\log^{2}n)$, the $\mathsf{LPN}_{g,\eta}$ assumption (2) holds.

There exist constants $\eta,\varepsilon\in(0,1/2)$ such that, for any function $t(n)=\Theta(\log n)$, both the $\mathsf{LPN}_{\varepsilon n,\eta}$ assumption (2) and the $\mathsf{XOR}_{2\varepsilon n,t}$ assumption (3) hold.

By a standard hybrid argument, the $\mathsf{LPN}_{g,\eta}$ assumption implies that any polynomial number of samples of the form $(A,As\oplus e)$ are indistinguishable from uniformly random samples.

Sample $s\leftarrow\operatorname{\mathcal{S}}_{t,n}$.

If $t=O(\log n)$ and $m\leq(1-\Omega(1))t\log n$, then

For larger values of $m$, $\operatorname{\mathcal{D}}_{0}(n,m)$ and $\operatorname{\mathcal{D}}_{1}(n,m,t)$ are no longer statistically close, but the planted XOR assumption says that they remain computationally indistinguishable.

The proof closely mirrors that in the technical overview (Section 2.1), with the main difference being that here we deal with generator matrices instead of the linear subspaces themselves. For $i\in\{0,\dots,r-1\}$ and $m^{\prime}\in[m+r]$, let $\operatorname{\mathcal{D}}_{i}(n,m^{\prime},t)$ be defined as follows.

$\operatorname{\mathcal{D}}_{i}(n,m^{\prime},t)$:

Sample $s_{1},\dots,s_{i}\leftarrow\operatorname{\mathcal{S}}_{t,n}$.

Observe that $\operatorname{\mathcal{D}}_{0}(n,m^{\prime},t)=\operatorname{\mathcal{D}}_{0}(n,m^{\prime})$, and $\operatorname{\mathcal{D}}_{1}(n,m^{\prime},t)$ is consistent with the definition given earlier.

For each $i\in\{0,\dots,r-1\}$ and $m^{\prime}\in[m+r]$, since $m^{\prime}\leq m+r\leq n-\omega(\log n)$, the matrix $G\leftarrow\operatorname{\mathcal{D}}_{i}(n,m^{\prime},t)$ has full rank with probability $1-\negl[n]$. Therefore, $\operatorname{\mathcal{D}}_{i}(n,m^{\prime},t)$ is $\negl[n]$-close in statistical distance to the following distribution:

$\hat{\operatorname{\mathcal{D}}}_{i}(n,m^{\prime},t)$:

Sample $s_{1},\dots,s_{i}\leftarrow\operatorname{\mathcal{S}}_{t,n}$.

Since $\hat{\operatorname{\mathcal{D}}}_{0}(n,m+r,t)$ (resp. $\hat{\operatorname{\mathcal{D}}}_{1}(n,m+r,t)$) is $\negl[n]$-close to $\operatorname{\mathcal{D}}_{0}(n,m+r)$ (resp. $\operatorname{\mathcal{D}}_{1}(n,m+r,t)$) in statistical distance, the $(n,m+r,t)$ planted XOR assumption implies that $\hat{\operatorname{\mathcal{D}}}_{0}(n,m+r,t)$, and $\hat{\operatorname{\mathcal{D}}}_{1}(n,m+r,t)$ are computationally indistinguishable.

Now suppose that an efficient adversary $\adv$ distinguishes between $\hat{\operatorname{\mathcal{D}}}_{0}(n,m,t)$ and $\hat{\operatorname{\mathcal{D}}}_{r}(n,m,t)$ with advantage $\varepsilon>0$. By a telescoping argument, $\adv$ must distinguish between $\hat{\operatorname{\mathcal{D}}}_{i}(n,m,t)$ and $\hat{\operatorname{\mathcal{D}}}_{i+1}(n,m,t)$ with advantage $\varepsilon/r$, for some $i\in\{0,\dots,r-1\}$. For each $i\in\{0,\dots,r-1\}$, the following efficient reduction $\mathsf{Red}_{i}$ satisfies $\mathsf{Red}_{i}(\hat{\operatorname{\mathcal{D}}}_{0}(n,m+r,t))\equiv\hat{\operatorname{\mathcal{D}}}_{i}(n,m,t)$ and $\mathsf{Red}_{i}(\hat{\operatorname{\mathcal{D}}}_{1}(n,m+r,t))\equiv\hat{\operatorname{\mathcal{D}}}_{i+1}(n,m,t)$. Therefore, the $(n,m+r,t)$ planted XOR assumption implies that $\varepsilon/r=\negl[n]$, which will complete the proof.