# Pseudorandom Error-Correcting Codes

Miranda Christ
Columbia University  Equal contribution. Email addresses:
<EMAIL_ADDRESS><EMAIL_ADDRESS>Sam Gunn∗
UC Berkeley Supported by a Google PhD Fellowship.

###### Abstract

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.

###### Contents

  1. 1 Introduction
    1. 1.1 An approach to watermarking
    2. 1.2 Our contributions
    3. 1.3 Related work: short summary
    4. 1.4 Organization
  2. 2 Technical overview
    1. 2.1 Pseudorandom code basics
    2. 2.2 Pseudorandom LDPC codes
    3. 2.3 Pseudorandom codes for the deletion channel
    4. 2.4 Constant-rate pseudorandom codes
    5. 2.5 Watermarks for language models
    6. 2.6 Watermarks with public attribution
    7. 2.7 Robust steganography
  3. 3 Preliminaries
    1. 3.1 Cryptography preliminaries
    2. 3.2 Coding theory preliminaries
  4. 4 Pseudorandom code basics
    1. 4.1 Definitions
    2. 4.2 Heuristic construction from permuted codes
  5. 5 Constructing pseudorandom codes from cryptographic assumptions
    1. 5.1 The zero-bit construction
    2. 5.2 Codeword detection (zero-bit decoding)
    3. 5.3 Pseudorandomness from the planted XOR assumption and LPN
    4. 5.4 Pseudorandomness from subexponential LPN
  6. 6 Boosting the rate and robustness of any pseudorandom code
    1. 6.1 Multi-bit pseudorandom codes
    2. 6.2 Constant-rate pseudorandom codes
    3. 6.3 Pseudorandom codes for the deletion channel
  7. 7 Application: watermarking for language models
    1. 7.1 Watermarking preliminaries
    2. 7.2 Robust watermarking from PRCs
    3. 7.3 Language model steganography
    4. 7.4 Watermarks with public attribution
  8. 8 Application: universal steganography
    1. 8.1 Steganography preliminaries
    2. 8.2 Robust stateless steganography
    3. 8.3 Stateless steganography from weaker modeling assumptions
  9. A Related work

##  1 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.

###  1.1 An approach to watermarking

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.111By 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.

#### Watermarks 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.

However, this strategy results in redundancy of responses because the
$i^{\text{th}}$ token of every response is biased towards the $i^{\text{th}}$
bit of $x$. This is problematic as it limits the variability of text that the
language model generates. For instance, it should not be the case that certain
words are preferred as the first word of every response. One can mitigate this
issue by storing a family of seeds $x_{1},\dots,x_{\ell}\in\\{0,1\\}^{n}$ and
randomly choosing one such seed for each response. Increasing $\ell$ improves
the variability, but comes at the cost of a corresponding increase in both
watermark key length _and_ detector runtime. Now, the detector must compute
the edit distance for each seed, resulting in a runtime of $O(n^{2}\ell)$. In
particular, for any polynomial-time watermarking scheme using this approach,
there exists a polynomial-time adversary that can distinguish watermarked
content from un-watermarked content without needing the watermark detection
key.

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.

###  1.2 Our contributions

#### Pseudorandom codes (Sections 4, 5 and 6).

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).

######  Definition (Definitions 1 and 2).

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.

######  Assumption (1).

Either

  * •

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_.

######  Theorem (Theorems 2 and 1).

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.

######  Theorem (Theorem 3).

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.

######  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$.

######  Theorem (Theorem 4).

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.

######  Corollary.

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.

######  Theorem (Theorem 5).

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.

######  Theorem (Theorem 6).

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.

######  Theorem (Theorem 8).

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.222Since 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.”

######  Theorem (Theorem 7).

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.

######  Theorem (Theorem 9).

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.

######  Theorem (Theorem 10).

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.

###  1.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.

###  1.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.

#### Acknowledgements.

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.

##  2 Technical overview

###  2.1 Pseudorandom code basics

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.

######  Definition (Definition 1).

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}$,

$\Pr_{\sk}[\mathsf{Decode}_{\sk}(\operatorname{\mathcal{E}}(x))={\sf
m}:x\leftarrow\mathsf{Encode}_{\sk}({\sf m})]\geq 1-\negl,$

and for any fixed $c\in\Sigma^{*}$,

$\Pr_{\sk}[\mathsf{Decode}_{\sk}(c)=\bot]\geq 1-\negl.$

  * •

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

$\abs{\Pr_{\sk}[\adv^{\mathsf{Encode}_{\sk}}(\secparam)=1]-\Pr_{\begin{subarray}{c}\sk\\\
\operatorname{\mathcal{U}}\end{subarray}}[\adv^{\operatorname{\mathcal{U}}}(\secparam)=1]}\leq\negl,$

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}$.

For a sufficiently weak channel $\operatorname{\mathcal{E}}$, it is not hard
to construct a secret-key PRC with robustness to $\operatorname{\mathcal{E}}$
where pseudorandomness rests on very mild assumptions. For instance, if
$F_{\sk}:\\{0,1\\}^{\ell}\to\\{0,1\\}$ is a pseudorandom function, we can
build a secret-key PRC with the following encoding algorithm. This
construction can only encode the singular message ‘1,’ so we call it a _zero-
bit_ PRC:

  1. $\mathsf{Encode}_{\sk}(1)$:

  2. 1.

Randomly sample $x_{1},\dots,x_{\ell}\leftarrow\\{0,1\\}$.

  3. 2.

For $i=\ell+1,\dots,n$, let $x_{i}=F_{\sk}(x_{i-\ell},\dots,x_{i-1})$.

  4. 3.

Output $x_{1},\dots,x_{n}$.

The decoding algorithm $\mathsf{Decode}_{\sk}$ simply checks whether much more
than a $1/2$ fraction of conditions $x_{i}=F_{\sk}(x_{i-\ell},\dots,x_{i-1})$
are satisfied. Pseudorandomness follows by taking $\ell$ to be the security
parameter. It is immediate that this PRC is robust to any length-preserving
channel that introduces at most a $p$ fraction of errors, for $p<<1/\ell$. We
call any such channel $p$-_bounded_.

This secret-key PRC construction can be seen as implicit in prior hash-based
watermarking schemes [Aar22, KGW+23a, CGZ23], where essentially the same level
of robustness to a $1/\ell$ error rate is obtained. Unfortunately, it has an
inherent trade-off between pseudorandomness and robustness: After roughly
$2^{\ell/2}$ samples from $\mathsf{Encode}_{\sk}(1)$, there will be repeated
prefixes and therefore correlations between the samples. In particular, if we
want this PRC to be robust to a constant rate of errors, we have to set
$\ell=O(1)$, in which case even a constant number of queries are enough to
observe correlations. We therefore turn to alternative constructions.

###  2.2 Pseudorandom LDPC codes

Fortunately, one of the most prominent assumptions in theoretical cryptography
is a statement about codes: Learning Parity with Noise (LPN). The LPN
assumption states that noisy samples from the codespace of a random linear
code are pseudorandom, even to an adversary who knows a generator matrix for
the code. In more detail, let $n,g$ be integers and
$G\leftarrow\mathbb{F}_{2}^{n\times g}$ be a random matrix. The LPN assumption
(with noise rate $\eta$ and secrets of size $g$) states that $(G,Gs\oplus
e)\approx(G,u)$,333Throughout this work we use $\approx$ to refer to
computational indistinguishability. where $s\leftarrow\mathbb{F}_{2}^{g}$,
$e\leftarrow\operatorname{\mathrm{Ber}}(n,\eta)$, and
$u\leftarrow\mathbb{F}_{2}^{n}$.

The LPN assumption suggests using noisy codewords from a random linear code as
a PRC. That is, let $G\leftarrow\mathbb{F}_{2}^{n\times g}$ be the secret key
and $\mathsf{Encode}_{G}$ be the following zero-bit secret-key PRC encoder:

  * •

$\mathsf{Encode}_{G}(1)$: Sample $s\leftarrow\mathbb{F}_{2}^{g}$ and
$e\leftarrow\operatorname{\mathrm{Ber}}(n,\eta)$. Output $Gs\oplus e$.

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.

It turns out that low-weight parity checks can serve as such a trapdoor. That
is, instead of sampling $G$ uniformly at random, we first sample a “parity-
check matrix” $P\in\mathbb{F}_{2}^{r\times n}$ with sparse rows (i.e., “low
density”), and then sample $G\in\mathbb{F}_{2}^{n\times g}$ subject to $PG=0$.
For appropriate choice of $n,g,t,r$, we will show that the resulting marginal
distribution on $G$ is random or pseudorandom. The low-density parity-check
matrix $P$ will allow for efficient detection of near-codewords.

Codes defined by Low-Density Parity-Check matrices are called LDPC codes. For
$n,g,t,r\in\mathbb{N}$, we define an $(n,g,t,r)$ random LDPC code by the
following distribution over parity-check and generator matrices:

  1. $\mathsf{LDPC}[n,g,t,r]$:

  2. 1.

Sample a random matrix $P\in\mathbb{F}_{2}^{r\times n}$ subject to every row
of $P$ being $t$-sparse.

  3. 2.

Sample a random matrix $G\in\mathbb{F}_{2}^{n\times g}$ subject to $PG=0$.

  4. 3.

Output $(P,G)$.

Zero-bit decoding works by counting the number of satisfied parity checks. For
any fixed $x\in\mathbb{F}_{2}^{n}$, with high probability over
$P\in\mathbb{F}_{2}^{r\times n}$ we expect that the number of unsatisfied
parity checks, $\operatorname{\mathrm{wt}}(Px)$, is roughly $r/2$. But if $x$
is close to $\operatorname{Im}G\subseteq\ker P$ in Hamming distance, then as
long as the error and the sparsity $t$ of the parity checks are not too high,
we expect $\operatorname{\mathrm{wt}}(Px)$ to be significantly smaller than
$r/2$.

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

  * •

$\mathsf{Decode}_{P}(x)$: If
$\operatorname{\mathrm{wt}}(Px)<(1/2-n^{-1/4})\cdot r$, output 1; otherwise
output $\bot$.444Throughout this work, $\operatorname{\mathrm{wt}}$ will refer
to Hamming weight.

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)$.

On the other hand, if we set $t=O(1)$ then $\mathsf{Encode}_{G}(1)$ cannot be
pseudorandom. This is because it is possible to brute-force search over all
$\binom{n}{t}$ possible parity checks of weight $t$, and one can test whether
$\mathsf{Encode}_{G}$ is consistent with a given parity check
$s\in\mathbb{F}_{2}^{n}$ by simply computing $s\cdot x$ for many samples
$x\leftarrow\mathsf{Encode}_{G}(1)$.

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.

######  Remark.

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.

#### Pseudorandom generator matrix (Lemma 8).

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

  * $\operatorname{\mathcal{D}}_{0}^{m}$:

a random $m$-dimensional linear subspace $V\subseteq\mathbb{F}_{2}^{n}$, and

  * $\operatorname{\mathcal{D}}_{1}^{m}$:

a random $m$-dimensional linear subspace $V_{s}\subseteq\mathbb{F}_{2}^{n}$
satisfying a random planted $t$-XOR relation $s$ (i.e., $s$ is a random
$t$-sparse vector and $s\cdot v=0$ for all $v\in V_{s}$).

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}$:

  * $\operatorname{\mathcal{D}}_{r}^{m}$:

a random $m$-dimensional linear subspace
$V_{s_{1},\dots,s_{r}}\subseteq\mathbb{F}_{2}^{n}$ satisfying $r$ random
planted $t$-XOR relations $s_{1},\dots,s_{r}$ (i.e., $s_{1},\dots,s_{r}$ are
random $t$-sparse vectors and $s_{1}\cdot v=\cdots=s_{r}\cdot v=0$ for all
$v\in V_{s_{1},\dots,s_{r}}$).

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.

  1. $\mathsf{Red}_{i}(W)$:

  2. 1.

Sample $i$ random $t$-sparse vectors $s_{1},\dots,s_{i}\in\mathbb{F}_{2}^{n}$
and let $S=\\{v\in\mathbb{F}_{2}^{n}:v\cdot s_{j}=0\ \forall j\in[i]\\}$.

  3. 2.

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$.

  4. 3.

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.

  * •

$\mathsf{Red}_{i}(\operatorname{\mathcal{D}}_{0}^{m+r})\equiv\operatorname{\mathcal{D}}_{i}^{m}$.
Fix $s_{1},\dots,s_{i}$ sampled in $\mathsf{Red}_{i}$ and let
$S=\\{v\in\mathbb{F}_{2}^{n}:v\cdot s_{j}=0\ \forall j\in[i]\\}$. Since $W$ is
a random subspace of $\mathbb{F}_{2}^{n}$, conditioned on any $d=\dim(W\cap
S)$, $U=W\cap S$ is a random $d$-dimensional subspace of $S$. Therefore the
output of $\mathsf{Red}_{i}(\operatorname{\mathcal{D}}_{0}^{m+r})$ is a random
$m$-dimensional subspace of $S$.

  * •

$\mathsf{Red}_{i}(\operatorname{\mathcal{D}}_{1}^{m+r})\equiv\operatorname{\mathcal{D}}_{i+1}^{m}$.
Fix $s_{1},\dots,s_{i}$ sampled in $\mathsf{Red}_{i}$ and let
$S=\\{v\in\mathbb{F}_{2}^{n}:v\cdot s_{j}=0\ \forall j\in[i]\\}$, as above.
Suppose that $W\leftarrow\operatorname{\mathcal{D}}_{1}^{m+r}$ is sampled with
the planted relation $s$. Fix $s$ and let $S^{\prime}=\\{v\in S:v\cdot
s=0\\}$. Again, conditioned on any $d=\dim(W\cap S)$, $U=W\cap S=W\cap
S^{\prime}$ is a random $d$-dimensional subspace of $S^{\prime}$. Therefore
the output of $\mathsf{Red}_{i}(\operatorname{\mathcal{D}}_{1}^{m+r})$ is a
random $m$-dimensional subspace of $S^{\prime}$.

#### 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:

  1. 1.

Sample a uniformly random $G_{0}\leftarrow\mathbb{F}_{2}^{0.01n\times g}$.

  2. 2.

For $i\in[0.99n]$:

    1. (a)

Sample a random $(t-1)$-sparse $s_{i}\in\mathbb{F}_{2}^{0.01n}$.

    2. (b)

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

$G_{i}=\begin{bmatrix}G_{i-1}\\\ s_{i}^{T}G_{0}\end{bmatrix}.$

    3. (c)

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

  3. 3.

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]$.

The leftover hash lemma immediately implies that $G$ is statistically random.
Recall that the leftover hash lemma states that if
$A\leftarrow\mathbb{F}_{2}^{g\times\ell}$ is a uniformly random matrix and
$s\in\mathbb{F}_{2}^{\ell}$ has min-entropy $\mu$, then $(A,As)$ is
$2^{-(\mu-g)/2}$-close to uniform in statistical distance. In our case, we use
$A=G_{0}^{T}$ and $s=s_{i}$ to see that $s_{i}^{T}G_{0}$ is
$2^{-(\log\binom{0.01n}{t}-g)/2}$-close to uniform in statistical distance for
each $i\in[n-g]$. If $t=\Omega(\log n)$, then there is a choice of
$g=\Omega(\log^{2}n)$ such that
$2^{-(\log\binom{0.01n}{t}-g)/2}=2^{-\Omega(\log^{2}n)}=\negl[n]$, completing
the proof.

####  $\mathsf{LDPC\text{-}PRC}_{0}$ is robust to any $p$-bounded channel
(Lemma 4).

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:

  1. 1.

any fixed $x\in\mathbb{F}_{2}^{n}$ decodes to $\bot$ with high probability,
and

  2. 2.

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

Unfortunately, (1) does not quite hold for the scheme presented above. The
issue is that, while _most_ fixed strings will decode to $\bot$, a small
fraction of strings will decode to 1 regardless of $P$. For instance, 0 will
always decode to 1 because $\operatorname{\mathrm{wt}}(P\cdot 0)=0$ for any
$P$. Therefore we modify our scheme slightly by using a one-time pad
$z\in\mathbb{F}_{2}^{n}$, included in the public key. The modified
$\mathsf{Encode}_{G}(1)$ outputs $Gs\oplus e\oplus z$, and
$\mathsf{Decode}_{P}(x)$ computes $\operatorname{\mathrm{wt}}(Px\oplus Pz)$
instead of $\operatorname{\mathrm{wt}}(Px)$; this is the actual scheme we
describe in Section 5.

Now, for any fixed $x\in\mathbb{F}_{2}^{n}$,
$\operatorname{\mathrm{wt}}(Px\oplus Pz)$ is distributed identically to
$\operatorname{\mathrm{wt}}(Pz)$ because $z$ is uniform. In Section 5.4 we
will see that $P$ is full rank with high probability, so $Pz$ is uniformly
random. By a Chernoff bound,
$\operatorname{\mathrm{wt}}(Pz)\geq(1/2-n^{-1/4})\cdot r$ with high
probability and therefore $\mathsf{Decode}_{P}(x)$ outputs $\bot$. This
concludes the proof of (1), so we turn to (2).

Suppose that we sample $Gs\oplus e\oplus z\leftarrow\mathsf{Encode}_{G}(1)$
and apply some $p$-bounded channel $\operatorname{\mathcal{E}}$. The one-time
pad effectively converts $\operatorname{\mathcal{E}}$ to a fixed error
channel, independent of $P,G,s,e$: Suppose that
$\operatorname{\mathcal{E}}(x)=x\oplus e(x)$, where $e(x)$ is a random
variable depending on $x$. Since $\operatorname{\mathcal{E}}$ is $p$-bounded,
$\operatorname{\mathrm{wt}}(e(x))\leq p\cdot n$. Letting $y=Gs\oplus e\oplus
z$, we have

$\displaystyle\operatorname{\mathcal{E}}(Gs\oplus e\oplus z)\oplus z$
$\displaystyle=(Gs\oplus e\oplus z)\oplus e(Gs\oplus e\oplus z)\oplus z$
$\displaystyle=Gs\oplus e\oplus e(y)$

where $y$ is uniformly random in $\mathbb{F}_{2}^{n}$, independent of
$P,G,s,e$ because of $z$. Now it only remains to see that
$\operatorname{\mathrm{wt}}(P(Gs\oplus e\oplus
e(y)))=\operatorname{\mathrm{wt}}(P(e\oplus e(y)))<(1/2-n^{-1/4})\cdot r$ with
high probability. Since $e$ and $e(y)$ are independent errors, each of weight
$(1/2-\Omega(1))\cdot n$, the combined error $e\oplus e(y)$ also has weight
$(1/2-\Omega(1))\cdot n$. Therefore, if the row sparsity $t$ of $P$ is $c\log
n$ for sufficiently small constant $c$, then we will have
$\operatorname{\mathrm{wt}}(P(e\oplus e(y)))<(1/2-n^{-1/4})\cdot r$ with high
probability, completing the proof of (2).

###  2.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:

$\mathsf{MajDec}_{k}(z)$:

  1. 1.

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

  2. 2.

Output
$(\operatorname{\mathrm{Maj}}(z_{1})||\cdots||\operatorname{\mathrm{Maj}}(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.555That 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_.

$\mathsf{MajEnc}_{T}({\sf m})$:

  1. 1.

For $i\in[k]$, let $z_{i}$ be a random sample from $\\{0,1\\}^{T}$ conditioned
on $\operatorname{\mathrm{Maj}}(z_{i})={\sf m}_{i}$.

  2. 2.

Output $(z_{1}||\cdots||z_{k})$.

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.666As
$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}$.

###  2.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}$ as777In 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.

$\mathsf{PRC}.\mathsf{Encode}(r),\mathsf{Enc}({\sf m})\oplus\mathsf{PRG}(r),$

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}$.

###  2.5 Watermarks for language models

In this work, a generative language model is formally described by an
algorithm $\mathsf{Model}$ that takes as input a prompt prompt and a sequence
of tokens output thus far ${\sf t}_{1},\ldots,{\sf t}_{i-1}$, and produces a
distribution over the next token. A full response is generated by iteratively
sampling from these distributions, at each step providing $\mathsf{Model}$
with the partial response, and terminating once a special “done” token is
sampled. For simplicity, we assume here that tokens are binary, which allows
us to specify the distribution ${\sf p}_{i}$ over the next token as a
Bernoulli distribution $\operatorname{\mathrm{Ber}}(\hat{{\sf p}}_{i})$ where
$\hat{{\sf p}}_{i}:=\mathop{{}\mathbb{E}}[{\sf p}_{i}]\in[0,1]$. We also
assume for the purposes of this technical overview that the model always
generates a response of length $n$. In Section 7 we explain why neither of
these assumptions is important for our results.

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.

#### Defining $\mathsf{Generate}$ for language models.

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

  1. (1)

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

  2. (2)

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:

  * •

If $\hat{{\sf p}}_{i}\leq 1/2$, sample ${\sf
t}_{i}\leftarrow\operatorname{\mathrm{Ber}}(2x_{i}\hat{{\sf p}}_{i})$.

  * •

If $\hat{{\sf p}}_{i}>1/2$, sample ${\sf
t}_{i}\leftarrow\operatorname{\mathrm{Ber}}(1-2(1-x_{i})(1-\hat{{\sf
p}}_{i}))$.

For any $\hat{{\sf p}}_{i}\in[0,1]$, one can easily see that ${\sf t}_{i}$ is
distributed as $\operatorname{\mathrm{Ber}}(\hat{{\sf p}}_{i})$ since $x_{i}$
is a uniformly random bit. This means that $\mathsf{Generate}$ satisfies
Condition (1) above.

For Condition (2), the bias toward the seed is stronger the closer $\hat{{\sf
p}}_{i}$ is to $1/2$. It is strongest when $\hat{{\sf p}}_{i}=1/2$ exactly, in
which case ${\sf t}_{i}$ is sampled from $\operatorname{\mathrm{Ber}}(x_{i})$
and is therefore equal to $x_{i}$. At the other extreme, if $\hat{{\sf
p}}_{i}=0$ or $1$, there is no bias. In general the response is a noisy
version of the seed, where the amount of noise on the $i^{\text{th}}$ token
decays as the binary entropy of $\operatorname{\mathrm{Ber}}(\hat{{\sf
p}}_{i})$ grows.

#### 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

  * $\mathsf{Wat}(\textsc{prompt})$:

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

  * $\mathsf{Detect}({\sf t})$:

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.

######  Remark.

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.888For 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.

In order to show this, we require a stronger assumption on the response: That
$\operatorname{\mathcal{E}}_{\mathsf{Emb}}$ behaves as the binary symmetric
channel $\text{BSC}_{q}$ for some $q\in(0,1/2)$. The binary symmetric channel
$\text{BSC}_{q}$ is the channel that flips each bit of its input independently
with probability $q$, so
$\text{BSC}_{q}(x)=x\oplus\operatorname{\mathrm{Ber}}(q)$ for $x\in\\{0,1\\}$.
Essentially, this is equivalent to the assumption that the response has high
entropy _and does not repeat words too often_.

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)$.

###  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.999Note 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}$.

###  2.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_ ,101010In 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$:

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

  2. 1.

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

  3. 2.

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

  4. 3.

Output $d=d_{1}||\ldots||d_{n}$

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.

However, this scheme is very brittle. If the stegotext is corrupted with any
errors at all — even ones resulting from any small bias in the hash function
$f$ — the message cannot be recovered. A natural attempt at achieving
robustness is for the sender to apply an error-correcting code
$(\mathsf{Enc},\mathsf{Dec})$ to the ciphertext before embedding it. But this
loses pseudorandomness and therefore steganographic secrecy! Consequently, the
robust steganography schemes of prior work rely on stronger assumptions like
the ability of the sender and receiver to share state. A shared state allows
the sender to generate a fresh one-time pad $r$ for each message it sends,
making the task much easier: The sender embeds $x=\mathsf{Enc}({\sf m})\oplus
r$ by choosing $d$ such that $f(d_{i})=x_{i}$, and the receiver computes
$\mathsf{Dec}(\tilde{x}\oplus r)$, where $(\mathsf{Enc},\mathsf{Dec})$ is any
error-correcting code. However, if the sender and receiver become
unsynchronized (as is likely in practice), the receiver can no longer decode
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.

##  3 Preliminaries

Let $\mathbb{N}:=\\{1,2,\dots\\}$ denote the set of positive integers. We will
write $[q]:=\\{1,\dots,q\\}$. For a set $X$, we define
$X^{*}:=\\{(x_{1},\dots,x_{k})\mid x_{1},\dots,x_{k}\in X\wedge
k\in\mathbb{Z}_{\geq 0}\\}$ to be the set of all strings with alphabet $X$.
For a binary string $s\in X^{*}$, we let $s_{i}$ denote the $i^{\text{th}}$
symbol of $s$ and $\operatorname{\mathrm{len}}s$ denote the length of $s$. For
a string $s\in X^{*}$ and positive integers $a\leq
b\leq\operatorname{\mathrm{len}}s$, let $s[a:b]$ denote the substring
$(s_{a},\ldots,s_{b})$.

For a finite set $X$, we will use the notation $x\leftarrow X$ to denote a
uniformly random sample $x$ from $X$. If $X$ is a set of $n$-dimensional
column vectors, we will write $X^{m}$ to refer to the set of $n\times m$
matrices whose columns take values in $X$. Unless otherwise specified, vectors
are assumed to be column vectors. For matrices $M\in\mathbb{F}_{2}^{m\times
n}$, let $\ker M$ and $\operatorname{Im}M$ denote the kernel and image of $M$
over $\mathbb{F}_{2}$, respectively.

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

Let $\operatorname{\mathrm{Ber}}(p)$ be the Bernoulli distribution on
$\\{0,1\\}$ with expectation $p$. Let $\operatorname{\mathrm{Ber}}(n,p)$ be
the distribution on $n$-bit strings where each bit is an i.i.d sample from
$\operatorname{\mathrm{Ber}}(p)$.

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.

######  Lemma 1 (Azuma’s inequality).

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$,

$\Pr[\abs{Z_{n}-Z_{0}}>t]\leq\exp{\left(\frac{-t^{2}}{2nC^{2}}\right)}+\varepsilon.$

######  Lemma 2 (Chernoff bounds).

Let $X_{1},\ldots,X_{n}\in[0,1]$ be independent random variables. Let
$\mu=\mathop{{}\mathbb{E}}\left[\sum_{i=1}^{n}X_{i}\right]$. Then for any
$\delta\in(0,1)$:

$\displaystyle\Pr\left[\sum_{i=1}^{n}X_{i}\geq(1+\delta)\mu\right]$
$\displaystyle\leq\exp\left(-\frac{\mu\delta^{2}}{3}\right)\text{ and}$
$\displaystyle\Pr\left[\sum_{i=1}^{n}X_{i}\leq(1-\delta)\mu\right]$
$\displaystyle\leq\exp\left(-\frac{\mu\delta^{2}}{2}\right).$

Let $\operatorname{\mathrm{Hyp}}(N,K,n)$ denote the hypergeometric
distribution with a population of size $N$, with $K$ success elements, and $n$
draws. That is, a random variable $X\sim\operatorname{\mathrm{Hyp}}(N,K,n)$ is
the number of success elements contained in $n$ uniform draws from the
population without replacement.

######  Lemma 3 (Hypergeometric tail bounds [Hoe94]).

Let $X\sim\operatorname{\mathrm{Hyp}}(N,K,n)$ and $p=K/N$. Then for any
$0<t<K/N$,

$\displaystyle\Pr\left[X\leq(p-t)n\right]$ $\displaystyle\leq
e^{-2t^{2}n},\text{ and}$ $\displaystyle\Pr\left[X\geq(p+t)n\right]$
$\displaystyle\leq e^{-2t^{2}n}.$

###  3.1 Cryptography preliminaries

#### Pseudorandom function (PRF).

Let
$\mathcal{F}=\\{F_{\sk}:\\{0,1\\}^{\ell_{1}(\secpar)}\to\\{0,1\\}^{\ell_{2}(\secpar)}\
|\ \sk\in\\{0,1\\}^{\secpar}\\}$ be a family of functions. $\mathcal{F}$ is a
PRF if $F_{\sk}$ is efficiently computable and for all polynomial-time
distinguishers $D$,

$\left|\Pr_{\sk\leftarrow\\{0,1\\}^{\secpar}}\left[D^{F_{\sk}(\cdot)}(1^{\secpar})=1\right]-\Pr_{f}\left[D^{f(\cdot)}(1^{\secpar})=1\right]\right|\leq\negl.$

where $f$ denotes a random function from $\\{0,1\\}^{\ell_{1}(\secpar)}$ to
$\\{0,1\\}^{\ell_{2}(\secpar)}$.

#### 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:

  * $\mathsf{Gen}:$

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

  * $\mathsf{Sign}:$

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})$.

  * $\mathsf{Vrfy}:$

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}}$.

$\mathsf{SigForge}_{\adv,\Pi}(\secpar)$
$(\pk,\sk)\leftarrow\mathsf{Gen}(1^{\secpar})$ $({\sf
m},\sigma)\leftarrow\adv^{\mathsf{Sign}_{\sk}(\cdot)}(\pk)$ Let
$\operatorname{\mathcal{Q}}$ denote the set of queries made by $\adv$ to
$\mathsf{Sign}_{\sk}(\cdot)$.
return $\mathsf{Vrfy}_{\pk}({\sf m},\sigma)\land{\sf
m}\notin\operatorname{\mathcal{Q}}$

Figure 1: The signature forgery experiment
$\mathsf{SigForge}_{\adv,\Pi}(\secpar)$

######  Definition (Security of a digital signature scheme.).

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$,

$\Pr[\mathsf{SigForge}_{\adv,\Pi}(\secpar)=1]\leq\negl$

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

###  3.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{BSC}_{p}:\\{0,1\\}^{*}\to\\{0,1\\}^{*}$ is the binary symmetric channel
with error rate $p\in(0,1)$. That is, $\text{BSC}_{p}(x)=x\oplus e$ where
$e\leftarrow\operatorname{\mathrm{Ber}}(\operatorname{\mathrm{len}}x,p)$.

  * •

$\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$.

##  4 Pseudorandom code basics

###  4.1 Definitions

In this section we define pseudorandom codes (PRCs) and related terminology. A
PRC can be viewed as a family111111We 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.

######  Definition 1 (Secret-key PRC).

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

  * •

(Syntax) There exist functions $\ell,n,k:\mathbb{N}\to\mathbb{N}$ such that
for all $\secpar\in\mathbb{N}$,
$\mathsf{KeyGen}(\secparam)\in\\{0,1\\}^{\ell(\secpar)}$,
$\mathsf{Encode}:\\{\secparam\\}\times\\{0,1\\}^{\ell(\secpar)}\times\Sigma^{k(\secpar)}\to\Sigma^{n(\secpar)}$,
and
$\mathsf{Decode}:\\{\secparam\\}\times\\{0,1\\}^{\ell(\secpar)}\times\Sigma^{*}\to\Sigma^{k(\secpar)}\cup\\{\bot\\}$.

  * •

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

$\Pr_{\sk\leftarrow\mathsf{KeyGen}(\secparam)}[\mathsf{Decode}(\secparam,\sk,\operatorname{\mathcal{E}}(x))={\sf
m}:x\leftarrow\mathsf{Encode}(\secparam,\sk,{\sf m})]\geq 1-\negl,$

and for any fixed $c\in\Sigma^{*}$,

$\Pr_{\sk\leftarrow\mathsf{KeyGen}(\secparam)}[\mathsf{Decode}(\secparam,\sk,c)=\bot]\geq
1-\negl.$

  * •

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

$\abs{\Pr_{\sk\leftarrow\mathsf{KeyGen}(\secparam)}[\adv^{\mathsf{Encode}(\secparam,\sk,\cdot)}(\secparam)=1]-\Pr_{\operatorname{\mathcal{U}}}[\adv^{\operatorname{\mathcal{U}}}(\secparam)=1]}\leq\negl,$

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)}$.

######  Definition 2 (Public-key PRC).

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

  * •

(Syntax) There exist functions
$\ell_{\dec},\ell_{\enc},n,k:\mathbb{N}\to\mathbb{N}$ such that for all
$\secpar\in\mathbb{N}$,
$\mathsf{KeyGen}(\secparam)\in\\{0,1\\}^{\ell_{\dec}(\secpar)}\times\\{0,1\\}^{\ell_{\enc}(\secpar)}$,
$\mathsf{Encode}:\\{\secparam\\}\times\\{0,1\\}^{\ell_{\enc}(\secpar)}\times\Sigma^{k(\secpar)}\to\Sigma^{n(\secpar)}$,
and
$\mathsf{Decode}:\\{\secparam\\}\times\\{0,1\\}^{\ell_{\dec}(\secpar)}\times\Sigma^{*}\to\Sigma^{k(\secpar)}\cup\\{\bot\\}$.

  * •

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

$\displaystyle\Pr_{(\sk,\pk)\leftarrow\mathsf{KeyGen}(\secparam)}[\mathsf{Decode}(\secparam,\sk,\operatorname{\mathcal{E}}(x))={\sf
m}:x\leftarrow\mathsf{Encode}(\secparam,\pk,{\sf m})]\geq 1-\negl,$

and for any fixed $c\in\Sigma^{*}$,

$\Pr_{(\sk,\pk)\leftarrow\mathsf{KeyGen}(\secparam)}[\mathsf{Decode}(\secparam,\sk,c)=\bot]\geq
1-\negl.$

  * •

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

$\abs{\Pr_{(\sk,\pk)\leftarrow\mathsf{KeyGen}(\secparam)}[\adv^{\mathsf{Encode}(\secparam,\pk,\cdot)}(\secparam,\pk)=1]-\Pr_{\begin{subarray}{c}(\sk,\pk)\leftarrow\mathsf{KeyGen}(\secparam)\\\
\operatorname{\mathcal{U}}\end{subarray}}[\adv^{\operatorname{\mathcal{U}}}(\secparam,\pk)=1]}\leq\negl,$

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.

######  Remark.

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.

###  4.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.

######  Construction 1 ($\mathsf{Permuted\text{-}PRC}_{\eta}[\enc,\dec]$).

  *   * •

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}$:

    1. 1.

Sample a random string $r\leftarrow\Sigma^{\secpar}$ and a noise vector
$e\leftarrow\operatorname{\mathrm{Ber}}(n,\eta)$.

    2. 2.

Compute $c=\enc(r||{\sf m})\oplus e$.

    3. 3.

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

  * •

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

    1. 1.

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

    2. 2.

Compute ${\sf m}^{\prime}=\dec(c)$.

    3. 3.

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.

##  5 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.

###  5.1 The zero-bit construction

Let

$\operatorname{\mathcal{S}}_{t,n}=\\{s\in\mathbb{F}_{2}^{n}:\operatorname{\mathrm{wt}}(s)=t\\}$

be the set of all $t$-sparse vectors in $\mathbb{F}_{2}^{n}$, and

$\operatorname{\mathcal{S}}_{t,r,n}=\\{P\in\mathbb{F}_{2}^{r\times
n}:\operatorname{\mathrm{wt}}(P_{i,:})=t\ \forall i\in[r]\\}$

be the set of all $t$-row-sparse matrices in $\mathbb{F}_{2}^{r\times n}$.

Our zero-bit pseudorandom LDPC codes are parameterized by a public generator
matrix $G\in\mathbb{F}_{2}^{n\times g}$ and a secret parity-check matrix
$P\in\mathbb{F}_{2}^{r\times n}$. The sampling process for these matrices is
described in Definition 3.

######  Definition 3 (Random LDPC code, $\mathsf{LDPC}[n,g,t,r]$).

For $n,g,t,r\in\mathbb{N}$, define the distribution $\mathsf{LDPC}[n,g,t,r]$
over $\mathbb{F}_{2}^{r\times n}\times\mathbb{F}_{2}^{n\times g}$ as follows:

  1. $\mathsf{LDPC}[n,g,t,r]$:

  2. 1.

Sample $P\leftarrow\operatorname{\mathcal{S}}_{t,r,n}$, i.e.
$P\in\mathbb{F}_{2}^{r\times n}$ is chosen to have i.i.d random $t$-sparse
rows.

  3. 2.

Sample $G\leftarrow(\ker P)^{g}$, i.e. $G\in\mathbb{F}_{2}^{n\times g}$ is a
random matrix subject to $PG=0$.

  4. 3.

Output $(P,G)$.

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.

######  Construction 2 (Zero-bit public-key pseudorandom LDPC code,
$\mathsf{LDPC\text{-}PRC}_{0}[n,g,t,r,\eta,\zeta]$).

Let $n,g,t,r:\mathbb{N}\to\mathbb{N}$ and $\eta,\zeta:\mathbb{N}\to[0,1/2)$ be
efficiently-computable functions of the security parameter. We define
$\mathsf{LDPC\text{-}PRC}_{0}[n,g,t,r,\eta,\zeta]$ by the following
algorithms, where we leave the dependence of $n,g,t,r,\eta,\zeta$ on $\secpar$
implicit:

  * •

$\mathsf{KeyGen}(\secparam)$: Sample $(P,G)\leftarrow\mathsf{LDPC}[n,g,t,r]$
and $z\leftarrow\mathbb{F}_{2}^{n}$. Output $(\sk=(P,z),\pk=(G,z))$.

  * •

$\mathsf{Encode}(\secparam,(G,z))$: Sample $u\leftarrow\mathbb{F}_{2}^{g}$,
$e\leftarrow\operatorname{\mathrm{Ber}}(n,\eta)$. Output $Gu\oplus z\oplus e$.

  * •

$\mathsf{Decode}(\secparam,(P,z),x)$: If $\operatorname{\mathrm{wt}}(Px\oplus
Pz)<\left(\frac{1}{2}-\zeta\right)\cdot r$, output 1; otherwise output $\bot$.

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$.

###  5.2 Codeword detection (zero-bit decoding)

We say that a length-preserving binary channel
$\operatorname{\mathcal{E}}:\\{0,1\\}^{*}\to\\{0,1\\}^{*}$ is _$p$ -bounded_
if there exists a negligible function $\negl[\cdot]$ such that for all
$n\in\mathbb{N}$,
$\Pr_{x\leftarrow\\{0,1\\}^{n}}[\operatorname{\mathrm{wt}}(\operatorname{\mathcal{E}}(x)\oplus
x)>pn]\leq\negl[n]$.

######  Lemma 4.

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.

###### Proof.

Lemma 6 shows that any fixed string $c\in\mathbb{F}_{2}^{n}$ decodes to $\bot$
with probability $1-\negl[n]$. It remains to show that codewords subject to
any $p$-bounded channel decode to $1$.

Let $\operatorname{\mathcal{E}}$ be any $p$-bounded channel. We need to show
that $\operatorname{\mathrm{wt}}(Px\oplus
Pz)<\left(\frac{1}{2}-n^{-1/4}\right)r$ with probability $1-\negl[n]$ over
$(P,G)\leftarrow\mathsf{LDPC}[n,g,t,r],u\leftarrow\mathbb{F}_{2}^{g},z\leftarrow\mathbb{F}_{2}^{n},e\leftarrow\operatorname{\mathrm{Ber}}(n,\eta),x\leftarrow\operatorname{\mathcal{E}}(Gu\oplus
z\oplus e)$.

We will show that there exists a constant $\alpha\in(0,1/2)$ such that
$\operatorname{\mathrm{wt}}(Gu\oplus z\oplus
x)\leq\left(\frac{1}{2}-\alpha\right)n$ with probability $1-\negl[n]$. Then we
can apply Lemma 5 with $y=Gu\oplus z\oplus x$ to see that
$\operatorname{\mathrm{wt}}(Py)=\operatorname{\mathrm{wt}}(Px\oplus
Pz)<\left(\frac{1}{2}-n^{-1/4}\right)r$ with probability $1-\negl[n]$ for
appropriate choices of $t,r$.

Let $c=Gu\oplus z\oplus e$. Then

$\displaystyle y$ $\displaystyle=Gu\oplus z\oplus x$ $\displaystyle=Gu\oplus
z\oplus\operatorname{\mathcal{E}}(Gu\oplus z\oplus e)$ $\displaystyle=e\oplus
c\oplus\operatorname{\mathcal{E}}(c),$

where $c$ is uniformly distributed because of $z$. Let
$e^{\prime}=c\oplus\operatorname{\mathcal{E}}(c)$, so that $y=e\oplus
e^{\prime}$. Then since $e\leftarrow\operatorname{\mathrm{Ber}}(n,\eta)$ is
independent from $e^{\prime}$, we have

$\displaystyle\mathop{{}\mathbb{E}}[\operatorname{\mathrm{wt}}(y)]$
$\displaystyle=\mathop{{}\mathbb{E}}[\operatorname{\mathrm{wt}}(e\oplus
e^{\prime})]$
$\displaystyle=(1-\eta)\mathop{{}\mathbb{E}}[\operatorname{\mathrm{wt}}(e^{\prime})]+\eta\mathop{{}\mathbb{E}}[n-\operatorname{\mathrm{wt}}(e^{\prime})]$
$\displaystyle\leq(1-\eta)pn+\eta(1-p)n+\negl[n]$

where the inequality holds because $\operatorname{\mathcal{E}}$ is
$p$-bounded, so $\operatorname{\mathrm{wt}}(e^{\prime})\leq pn$ with
probability $1-\negl[n]$. Conditioned on
$\operatorname{\mathrm{wt}}(e^{\prime})\leq pn$, a Chernoff bound over the
random choice of $e$ implies that

$\operatorname{\mathrm{wt}}(e\oplus
e^{\prime})\leq\left[\frac{(1-\eta)p+\eta(1-p)}{2}+\frac{1}{4}\right]\cdot n$

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]$. ∎

######  Lemma 5.

Let $\alpha\in(0,1/2)$ be some constant and suppose that $r=\Omega(n)$ and
$t\leq\frac{1}{5}\log_{1/2\alpha}n$. If $y\in\mathbb{F}_{2}^{n}$ satisfies
$\operatorname{\mathrm{wt}}(y)\leq\left(\frac{1}{2}-\alpha\right)n$, then

$\Pr_{P\leftarrow\operatorname{\mathcal{S}}_{t,r,n}}\left[\operatorname{\mathrm{wt}}(Py)<\left(\frac{1}{2}-n^{-1/4}\right)r\right]\geq
1-\negl[n].$

###### Proof.

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

$\Pr_{P_{i}\leftarrow\operatorname{\mathcal{S}}_{t,1,n}}[P_{i}y=0]\geq\frac{1}{2}+\frac{2}{n^{1/4}},$
(1)

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

Let $j_{1},\dots,j_{t}\in[n]$, $Y_{1},\dots,Y_{t}\in\\{-1,1\\}$ be random
variables, defined as follows, for $\ell=1,\dots,t$:

  1. 1.

Sample $j_{\ell}\leftarrow[n]\setminus\\{j_{1},\dots,j_{\ell-1}\\}$.

  2. 2.

Let $Y_{\ell}=(-1)^{x_{j_{\ell}}}$.

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

$\displaystyle\Pr_{P_{i}\leftarrow\operatorname{\mathcal{S}}_{t,1,n}}[P_{i}y=0]$
$\displaystyle=\Pr[Y_{1}\cdots Y_{t}=1]$
$\displaystyle=\frac{1}{2}+\frac{1}{2}\mathop{{}\mathbb{E}}[Y_{1}\cdots
Y_{t}].$

The remainder of the proof is devoted to showing that

$\mathop{{}\mathbb{E}}[Y_{1}\cdots Y_{t}]\geq(2\alpha)^{t}-2t^{2}/n.$ (2)

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

Let $\alpha^{\prime}=1/2-\operatorname{\mathrm{wt}}(y)/n$, and note that
$\alpha^{\prime}\geq\alpha$. To prove Equation 2 we first show that for all
$m\in[t]$,

$\abs{\mathop{{}\mathbb{E}}[Y_{1}\cdots
Y_{m}]-2\alpha^{\prime}\mathop{{}\mathbb{E}}[Y_{1}\cdots Y_{m-1}]}\leq 2t/n.$
(3)

By the tower property and linearity of expectation,

$\abs{\mathop{{}\mathbb{E}}[Y_{1}\cdots
Y_{m}]-2\alpha^{\prime}\mathop{{}\mathbb{E}}[Y_{1}\cdots
Y_{m-1}]}=\abs{\mathop{{}\mathbb{E}}\left[Y_{1}\cdots
Y_{m-1}\cdot\big{(}\mathop{{}\mathbb{E}}[Y_{m}\mid
Y_{<m}]-2\alpha^{\prime}\big{)}\right]}.$ (4)

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

$\displaystyle\mathop{{}\mathbb{E}}[Y_{m}\mid Y_{<m}]$
$\displaystyle=\Pr_{j_{m}}[x_{j_{m}}=0\mid
Y_{<m}]-(1-\Pr_{j_{m}}[x_{j_{m}}=0\mid Y_{<m}])$
$\displaystyle=2\Pr_{j_{m}}[x_{j_{m}}=0\mid Y_{<m}]-1$

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$.

We now have that $\abs{\mathop{{}\mathbb{E}}[Y_{m}\mid
Y_{<m}]-2\alpha^{\prime}}\leq 2t/n$, and $\abs{Y_{1}\cdots Y_{m-1}}=1$.
Plugging these two facts into Equation 4 gives us Equation 3.

We complete the proof by showing by induction that
$\mathop{{}\mathbb{E}}[Y_{1}\cdots Y_{m}]\geq(2\alpha^{\prime})^{m}-2mt/n$.
Observe first that
$\mathop{{}\mathbb{E}}[Y_{1}]=(\frac{1}{2}+\alpha^{\prime})-(\frac{1}{2}-\alpha^{\prime})>2\alpha^{\prime}-2t/n$.
Assume that the inequality holds for some $m<t$; we’ll show that it holds for
$m+1$. We have $\mathop{{}\mathbb{E}}[Y_{1}\cdots Y_{m+1}]\geq
2\alpha^{\prime}\mathop{{}\mathbb{E}}[Y_{1}\cdots Y_{m}]-2t/n$. Therefore,
since $2\alpha^{\prime}\leq 1$,

$\displaystyle\mathop{{}\mathbb{E}}[Y_{1}\cdots Y_{m+1}]$ $\displaystyle\geq
2\alpha^{\prime}\left((2\alpha^{\prime})^{m}-\frac{2mt}{n}\right)-\frac{2t}{n}$
$\displaystyle=(2\alpha^{\prime})^{m+1}-\frac{2(m+1)t}{n}$

as desired.

∎

######  Lemma 6.

If $\Omega(n)\leq r\leq 0.99n$, then for any fixed $c\in\mathbb{F}_{2}^{n}$,

$\Pr_{\begin{subarray}{c}P\leftarrow\operatorname{\mathcal{S}}_{t,r,n}\\\
z\leftarrow\mathbb{F}_{2}^{n}\end{subarray}}\left[\operatorname{\mathrm{wt}}(Pc\oplus
Pz)\geq\left(\frac{1}{2}-n^{-1/4}\right)r\right]\geq 1-\negl[n].$

###### Proof.

With probability $1-\negl[n]$, $P\leftarrow\operatorname{\mathcal{S}}_{t,r,n}$
is full rank by Lemma 12 (invoking the lemma with $g=0$). For any such $P$,
over the random choice of $z\leftarrow\mathbb{F}_{2}^{n}$, the vector
$P(c\oplus z)\in\mathbb{F}_{2}^{r}$ is uniformly random. The lemma follows
from a Chernoff bound. ∎

###  5.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.

#### Cryptographic assumptions.

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

######  Assumption 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.

We now define the $\mathsf{LPN}_{g,\eta}$ and $\mathsf{XOR}_{m,t}$
assumptions. Let us first recall the LPN assumption. We only state the
decisional, constant-noise version, since all of our results pertain to that
variant. For $\eta\in(0,1/2)$ and $g:\mathbb{N}\to\mathbb{N}$, the
$\mathsf{LPN}_{g,\eta}$ problem is to distinguish between $(A,As\oplus e)$ and
$(A,r)$, where $A\leftarrow\mathbb{F}_{2}^{n\times g(n)}$,
$s\leftarrow\mathbb{F}_{2}^{g(n)},e\leftarrow\operatorname{\mathrm{Ber}}(n,\eta)$,
and $r\leftarrow\mathbb{F}_{2}^{n}$.

######  Assumption 2 (LPN assumption).

For $\eta\in(0,1/2)$ and $g:\mathbb{N}\to\mathbb{N}$, the
$\mathsf{LPN}_{g,\eta}$ assumption states that for every $n\in\mathbb{N}$ and
every polynomial-time adversary $\adv$,

$\abs{\Pr_{\begin{subarray}{c}A\leftarrow\mathbb{F}_{2}^{n\times g(n)}\\\
s\leftarrow\mathbb{F}_{2}^{g(n)}\\\
e\leftarrow\operatorname{\mathrm{Ber}}(n,\eta)\end{subarray}}[\adv(A,As\oplus
e)=1]-\Pr_{\begin{subarray}{c}A\leftarrow\mathbb{F}_{2}^{n\times g(n)}\\\
r\leftarrow\mathbb{F}_{2}^{n}\end{subarray}}[\adv(A,r)=1]}\leq\negl[n].$

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.

The planted XOR assumption is lesser-known than LPN, but there is still
precedent [SSV23]. This assumption states that a random linear subspace over
$\mathbb{F}_{2}$ is indistinguishable from one containing a planted sparse
vector. Formally, it says that the distributions
$\operatorname{\mathcal{D}}_{0}(n,m)$ and
$\operatorname{\mathcal{D}}_{1}(n,m,t)$ are computationally indistinguishable,
where the “null” distribution $\operatorname{\mathcal{D}}_{0}$ is the uniform
distribution over $\mathbb{F}_{2}^{n\times m}$, and the “planted” distribution
$\operatorname{\mathcal{D}}_{1}$ is defined as follows.

$\operatorname{\mathcal{D}}_{1}(n,m,t)$:

  1. 1.

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

  2. 2.

Sample a random matrix $G\in\mathbb{F}_{2}^{n\times m}$ subject to $s^{T}G=0$.

  3. 3.

Output $G$.

######  Assumption 3 (Planted XOR assumption).

For $m,t:\mathbb{N}\to\mathbb{N}$, the $\mathsf{XOR}_{m,t}$ assumption states
that for every $n\in\mathbb{N}$ and every polynomial-time adversary $\adv$,

$\abs{\Pr_{G\leftarrow\operatorname{\mathcal{D}}_{0}(n,m(n))}[\adv(G)=1]-\Pr_{G\leftarrow\operatorname{\mathcal{D}}_{1}(n,m(n),t(n))}[\adv(G)=1]}\leq\negl[n].$

Note that when $m=n-O(\log n)$, the $\mathsf{XOR}_{m,t}$ assumption is false
because there will be only $n^{O(1)}$ vectors $v\in\mathbb{F}_{2}^{n}$ such
that $v^{T}G=0$, and one can therefore brute force search for the planted
relation $s$. On the other hand, Claim 7 shows that when (for instance)
$t\sim\log n$ and $m\sim\log^{2}n$ the $\mathsf{XOR}_{m,t}$ assumption holds
against even _unbounded_ adversaries. This claim follows from Theorem 4.2 of
[SSV23].

######  Claim 7.

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

$SD(\operatorname{\mathcal{D}}_{0}(n,m),\operatorname{\mathcal{D}}_{1}(n,m,t))=n^{-\Omega(t)}.$

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.

######  Lemma 8.

Let $m,t,r:\mathbb{N}\to\mathbb{N}$ be such that $m(n)+r(n)\leq n-\omega(\log
n)$. The $\mathsf{XOR}_{m+r,t}$ assumption (3) implies that the marginal
distribution on $G$ for $(P,G)\leftarrow\mathsf{LDPC}[n,m,t,r]$ is
pseudorandom.

###### Proof.

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.

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

  2. 1.

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

  3. 2.

Sample a random matrix $G\in\mathbb{F}_{2}^{n\times m^{\prime}}$ subject to
$s_{j}^{T}G=0$ for all $j\in[i]$.

  4. 3.

Output $G$.

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:

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

  2. 1.

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

  3. 2.

Sample a random _full-rank_ matrix $G\in\mathbb{F}_{2}^{n\times m^{\prime}}$
subject to $s_{j}^{T}G=0$ for all $j\in[i]$.

  4. 3.

Output $G$.

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.

  1. $\mathsf{Red}_{i}(W)$:

  2. 1.

Sample $i$ random $t$-sparse vectors $s_{1},\dots,s_{i}\in\mathbb{F}_{2}^{n}$
and let $S=\\{v\in\mathbb{F}_{2}^{n}:v\cdot s_{j}=0\ \forall j\in[i]\\}$.

  3. 2.

Let $U=\operatorname{Im}(W)\cap S$. Since $i<r$ and
$\dim\operatorname{Im}W=m+r$, we have $\dim U>m$.

  4. 3.

Sample a random full-rank matrix $G\in\mathbb{F}_{2}^{n\times m}$ such that
$\operatorname{Im}(G)\subseteq U$.

  5. 4.

Output $G$.

It remains to see why
$\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)$.
In fact both of these statements are true even for _fixed_ planted relations.

#### Proof that
$\mathsf{Red}_{i}(\hat{\operatorname{\mathcal{D}}}_{0}(n,m+r,t))\equiv\hat{\operatorname{\mathcal{D}}}_{i}(n,m,t)$.

Suppose that $W\leftarrow\hat{\operatorname{\mathcal{D}}}_{0}(n,m+r,t)$. Fix
$s_{1},\dots,s_{i}$ sampled in $\mathsf{Red}_{i}(W)$ and let
$S=\\{v\in\mathbb{F}_{2}^{n}:v\cdot s_{j}=0\ \forall j\in[i]\\}$. For any
$d\in\\{m+1,\dots,m+r\\}$, consider the distribution of the subspace
$U=\operatorname{Im}(W)\cap S$ conditioned on the event that $\dim U=d$.
Before the conditioning $\operatorname{Im}W$ was a random subspace of
$\mathbb{F}_{2}^{n}$, so after the conditioning $U$ is a random
$d$-dimensional subspace of $S$. The output of $\mathsf{Red}_{i}(W)$ is a
random full-rank matrix $G\in\mathbb{F}_{2}^{n\times m}$ such that
$\operatorname{Im}(G)\subseteq U\subseteq S$. But we have just seen that $U$
is a uniformly random $d>m$ dimensional subspace of $S$, so it follows that
$G$ is a random matrix subject to $\operatorname{Im}G\subseteq S$ — i.e.,
$s_{j}^{T}G=0$ for all $j\in[i]$.

#### Proof that
$\mathsf{Red}_{i}(\hat{\operatorname{\mathcal{D}}}_{1}(n,m+r,t))\equiv\hat{\operatorname{\mathcal{D}}}_{i+1}(n,m,t)$.

Suppose that $W\leftarrow\hat{\operatorname{\mathcal{D}}}_{1}(n,m+r,t)$ is
sampled with the planted relation $s$. Fix $s$ and $s_{1},\dots,s_{i}$ sampled
in $\mathsf{Red}_{i}$. Let $S=\\{v\in\mathbb{F}_{2}^{n}:v\cdot s_{j}=0\
\forall j\in[i]\\}$ and $S^{\prime}=\\{v\in\mathbb{F}_{2}^{n}:v\cdot s=0\\}$.
Again, for each $d\in\\{m+1,\dots,m+r\\}$, consider the distribution of
$U=\operatorname{Im}(W)\cap S$ conditioned on the event that $\dim U=d$.
Before the conditioning $\operatorname{Im}W$ was a random subspace of
$S^{\prime}$, so after the conditioning $U$ is a random $d$-dimensional
subspace of $S\cap S^{\prime}$. The output of $\mathsf{Red}_{i}(W)$ is a
random full-rank matrix $G\in\mathbb{F}_{2}^{n\times m}$ such that
$\operatorname{Im}(G)\subseteq U\subseteq S\cap S^{\prime}$. But we have just
seen that $U$ is a uniformly random $d>m$ dimensional subspace of $S\cap
S^{\prime}$, so it follows that $G$ is a random matrix subject to
$\operatorname{Im}G\subseteq S\cap S^{\prime}$ — i.e., $s^{T}G=0$ and
$s_{j}^{T}G=0$ for all $j\in[i]$. ∎

Claim 7 and Lemma 8 together imply that the generator matrix from
$\mathsf{LDPC}[n,\log^{2}n,4\log n,\log^{2}n]$ is statistically uniform. In
Lemma 9 we improve this to show that the generator matrix from
$\mathsf{LDPC}[n,g,4\log n,r]$ is statistically uniform for any $r\leq 0.99n$
(and some $g=\Omega(\log^{2}n)$).

######  Theorem 1.

For any constants $p,\eta,\varepsilon\in(0,1/2)$, there exists a function
$t=\Theta(\log n)$ such that $\mathsf{LDPC\text{-}PRC}_{0}[n,\varepsilon
n,t,\varepsilon n,\eta,n^{-1/4}]$ is a zero-bit public-key PRC that is robust
to every $p$-bounded channel, where pseudorandomness rests on the
$\mathsf{LPN}_{\varepsilon n,\eta}$ assumption (2) and the
$\mathsf{XOR}_{2\varepsilon n,t}$ assumption (3).

###### Proof.

By Lemma 4, there exists $t=\Theta(\log n)$ such that
$\mathsf{LDPC\text{-}PRC}_{0}[n,\varepsilon n,t,\varepsilon n,\eta,n^{-1/4}]$
is robust to every $p$-bounded channel.

By Lemma 8, the $\mathsf{XOR}_{2\varepsilon n,t}$ assumption implies that for
$(P,G)\leftarrow\mathsf{LDPC}[n,\varepsilon n,t,\varepsilon n]$, the marginal
distribution on $G$ is pseudorandom. By the $\mathsf{LPN}_{\varepsilon
n,\eta}$ assumption, it follows that
$\mathsf{LDPC\text{-}PRC}_{0}[n,\varepsilon n,t,\varepsilon n,\eta,n^{-1/4}]$
is a public-key PRC. ∎

###  5.4 Pseudorandomness from subexponential LPN

In Section 5.3, we showed that the generator matrix
$G\in\mathbb{F}_{2}^{n\times g}$ of $\mathsf{LDPC\text{-}PRC}_{0}$ was
pseudorandom under the planted XOR assumption. In Lemma 9 of this section, we
will show that $G$ is _statistically_ random if we set $g$ to be sufficiently
small. Therefore, the planted XOR assumption is no longer necessary; however,
the number of columns will be only $g=O(\log^{2}n)$, so we must rely on a
stronger, sub-exponential variant of LPN than in Section 5.3.

######  Remark.

Before we see Lemma 9, note that we use a different proof strategy here than
the technical overview. The reason we use this more involved proof here is
that the proof outlined in the technical overview results in a different
ensemble of parity-check matrices $P$ with a triangular restriction and non-
independent rows. By proving Lemma 9, we are able to use the same ensemble as
in Section 5.3 — that is, the rows of $P$ are still independent and uniform
$t$-sparse vectors.

######  Lemma 9.

If $r\leq 0.99n$ and $\omega(\sqrt{\log n})\leq t\leq O(\log n)$, then there
is a $g=\Omega(t^{2})$ such that the marginal distribution on $G$ for
$(P,G)\leftarrow\mathsf{LDPC}[n,g,t,r]$ is $\negl[n]$-close to uniform in
statistical distance.

###### Proof.

Recall the definitions of $\operatorname{\mathcal{S}}_{t,n}$ and
$\operatorname{\mathcal{S}}_{t,r,n}$ from Section 5.1. Let
$\operatorname{\mathcal{D}}$ be the marginal distribution on
$G\in\mathbb{F}_{2}^{n\times g}$ for $(P,G)\leftarrow\mathsf{LDPC}[n,g,t,r]$.

We will show that $\operatorname{\mathcal{D}}$ is $\negl[n]$-close to the
uniform distribution in statistical distance. For any
$G^{*}\in\mathbb{F}_{2}^{n\times g}$,

$\displaystyle\Pr_{G\leftarrow\operatorname{\mathcal{D}}}[G=G^{*}]$
$\displaystyle=\sum_{\begin{subarray}{c}P^{*}\in\operatorname{\mathcal{S}}_{t,r,n}:\\\
P^{*}G^{*}=0\end{subarray}}\Pr_{P\leftarrow\operatorname{\mathcal{S}}_{t,r,n}}[P=P^{*}]\cdot\Pr_{G\leftarrow(\ker
P^{*})^{g}}[G=G^{*}]$
$\displaystyle=\frac{1}{\binom{n}{t}^{r}}\sum_{\begin{subarray}{c}P^{*}\in\operatorname{\mathcal{S}}_{t,r,n}:\\\
P^{*}G^{*}=0\end{subarray}}\frac{1}{\abs{\ker P^{*}}^{g}}$
$\displaystyle\leq\frac{1}{\binom{n}{t}^{r}}\sum_{\begin{subarray}{c}P^{*}\in\operatorname{\mathcal{S}}_{t,r,n}:\\\
P^{*}G^{*}=0\end{subarray}}\frac{1}{2^{(n-r)m}}$
$\displaystyle=\frac{\eta(G^{*})^{r}}{\binom{n}{t}^{r}\cdot 2^{(n-r)m}}$

where $\eta(G^{*})$ is the number of collections of $t$ rows of $G^{*}$ that
sum to 0. Since valid rows of $P^{*}$ correspond to collections of $t$ rows of
$G^{*}$ that sum to 0, $|\\{P^{*}\in\mathbb{F}_{2}^{r\times n}:\
P^{*}G^{*}=0\\}|=\eta(G^{*})^{r}$, which gives us the last equality above.

Let $\operatorname{\mathcal{F}}\subset\mathbb{F}_{2}^{r\times n}$ be the set
of $t$-row-sparse matrices of full rank,

$\operatorname{\mathcal{F}}:=\\{P\in\operatorname{\mathcal{S}}_{t,r,n}\mid\operatorname{\mathrm{rank}}(P)=r\\}=\\{P\in\operatorname{\mathcal{S}}_{t,r,n}\mid\dim\ker(P)=n-r\\}.$

Then we also have

$\displaystyle\Pr_{G\leftarrow\operatorname{\mathcal{D}}}[G=G^{*}]$
$\displaystyle=\frac{1}{\binom{n}{t}^{r}}\sum_{\begin{subarray}{c}P^{*}\in\operatorname{\mathcal{S}}_{t,r,n}:\\\
P^{*}G^{*}=0\end{subarray}}\frac{1}{\abs{\ker P^{*}}^{g}}$
$\displaystyle\geq\frac{1}{\binom{n}{t}^{r}}\sum_{\begin{subarray}{c}P^{*}\in\operatorname{\mathcal{F}}:\\\
P^{*}G^{*}=0\end{subarray}}\frac{1}{2^{(n-r)g}}$
$\displaystyle=\frac{\eta(G^{*})^{r}}{\binom{n}{t}^{r}\cdot
2^{(n-r)g}}\cdot\Pr_{P^{*}\leftarrow\mathbb{F}_{2}^{r\times n}}[P^{*}\text{
has full rank}\mid P^{*}G^{*}=0].$

Let
$\operatorname{\mathcal{P}}(G^{*})=\\{P^{*}\in\operatorname{\mathcal{S}}_{t,r,n}\mid
P^{*}G^{*}=0\\}$. The above two inequalities give us a point-wise
approximation to the density of $\operatorname{\mathcal{D}}$,

$\Pr_{P^{*}\leftarrow\operatorname{\mathcal{P}}(G^{*})}[P^{*}\text{ has full
rank}]\cdot\frac{\eta(G^{*})^{r}}{\binom{n}{t}^{r}\cdot
2^{(n-r)g}}\leq\Pr_{G\leftarrow\operatorname{\mathcal{D}}}[G=G^{*}]\leq\frac{\eta(G^{*})^{r}}{\binom{n}{t}^{r}\cdot
2^{(n-r)g}}.$ (5)

We complete the proof with the following three facts:

  * •

Lemma 10 is a general statistical fact, which implies that if

$\Pr_{G^{*}\leftarrow\mathbb{F}_{2}^{n\times
g}}\left[\abs{\Pr_{G\leftarrow\operatorname{\mathcal{D}}}[G=G^{*}]-\frac{1}{2^{ng}}}\leq\frac{\negl[n]}{2^{ng}}\right]\geq
1-\negl[n],$

then $\operatorname{\mathcal{D}}$ is $\negl[n]$-close to uniform in
statistical distance. Crucially, Lemma 10 and Equation 5 reduce the problem to
reasoning about _the uniform distribution_ over $G^{*}$, rather than
$\operatorname{\mathcal{D}}$.

  * •

Lemma 11 implies that

$\Pr_{G^{*}\leftarrow\mathbb{F}_{2}^{n\times
g}}\left[\abs{\frac{\eta(G^{*})^{r}}{\binom{n}{t}^{r}\cdot
2^{(n-r)g}}-\frac{1}{2^{ng}}}\leq\frac{\negl[n]}{2^{ng}}\right]\geq
1-\negl[n].$

The proof is a simple invocation of Chebyshev’s inequality.

  * •

Lemma 12 implies that

$\Pr_{G^{*}\leftarrow\mathbb{F}_{2}^{n\times
g}}\left[\Pr_{P^{*}\leftarrow\operatorname{\mathcal{P}}(G^{*})}[P^{*}\text{
has full rank}]\geq 1-\negl[n]\right]\geq 1-\negl[n].$

Using Lemmas 11 and 12 with Equation 5, the condition of Lemma 10 is
satisfied. This completes the proof of the theorem. ∎

######  Lemma 10.

Let $p$ be a probability distribution on a finite set
$\operatorname{\mathcal{X}}$. If

$\Pr_{x\leftarrow\operatorname{\mathcal{X}}}\left[\abs{p(x)-\frac{1}{\abs{\operatorname{\mathcal{X}}}}}>\frac{\alpha}{\abs{\operatorname{\mathcal{X}}}}\right]\leq\beta,$

then the statistical distance between $p$ and the uniform distribution is at
most $\alpha+\beta$.

###### Proof.

We just compute

$\displaystyle\sum_{\begin{subarray}{c}x\in\operatorname{\mathcal{X}}:\\\
p(x)<\frac{1}{\abs{X}}\end{subarray}}\left(\frac{1}{\abs{X}}-p(x)\right)$
$\displaystyle=\sum_{\begin{subarray}{c}x\in\operatorname{\mathcal{X}}:\\\
\frac{1-\alpha}{\abs{X}}\leq
p(x)<\frac{1}{\abs{X}}\end{subarray}}\left(\frac{1}{\abs{X}}-p(x)\right)+\sum_{\begin{subarray}{c}p(x)<\frac{1-\alpha}{\abs{X}}\end{subarray}}\left(\frac{1}{\abs{X}}-p(x)\right)$
$\displaystyle\leq\alpha+\sum_{\begin{subarray}{c}p(x)<\frac{1-\alpha}{\abs{X}}\end{subarray}}\frac{1}{\abs{X}}$
$\displaystyle\leq\alpha+\beta.$

∎

######  Lemma 11.

For any $\varepsilon>0$,

$\Pr_{G^{*}\leftarrow\mathbb{F}_{2}^{n\times
g}}\left[\abs{\eta(G^{*})-\binom{n}{t}\cdot
2^{-g}}>\varepsilon\cdot\binom{n}{t}\cdot
2^{-g}\right]\leq\frac{2^{g}}{\binom{n}{t}\cdot\varepsilon^{2}}.$

###### Proof.

By linearity of expectation,

$\mathop{{}\mathbb{E}}_{G^{*}\leftarrow\mathbb{F}_{2}^{n\times
g}}\eta(G^{*})=\sum_{w\in\operatorname{\mathcal{S}}_{t,n}}\Pr_{G^{*}\leftarrow\mathbb{F}_{2}^{n\times
g}}[w^{T}G^{*}=0]=\binom{n}{t}\cdot 2^{-g}.$

Furthermore,
$\\{\mathbbm{1}[w^{T}G^{*}=0]\\}_{w\in\operatorname{\mathcal{S}}_{t,n}}$ are
pairwise independent random variables over
$G^{*}\leftarrow\mathbb{F}_{2}^{n\times g}$, so the lemma follows from
Chebyshev’s inequality. ∎

######  Lemma 12.

If $r\leq 0.99n$ and $\omega(\sqrt{\log n})\leq t\leq O(\log n)$, then there
is a $\tilde{g}=\Omega(t^{2})$ such that for all $g\leq\tilde{g}$,

$\Pr_{G^{*}\leftarrow\mathbb{F}_{2}^{n\times
g}}\left[\Pr_{P^{*}\leftarrow\operatorname{\mathcal{P}}(G^{*})}[P^{*}\text{\emph{
has full rank}}]\geq 1-\negl[n]\right]\geq 1-\negl[n].$

###### Proof.

We say that a subset of rows $S\subseteq[r]$ of $P^{*}$ forms a “simple
dependency” if those rows sum to $0$, and no subset of them sums to $0$. For a
$1-\negl[n]$ fraction of $G^{*}\leftarrow\mathbb{F}_{2}^{n\times g}$, we will
show that over $P^{*}\leftarrow\operatorname{\mathcal{P}}(G^{*})$ the expected
number of simple dependencies in $P^{*}$ is $\negl[n]$.

Letting $W_{i}$ denote the $i$th row of the matrix $W$, we define

$\mathsf{SD}_{\ell}=\left\\{W\in\operatorname{\mathcal{S}}_{t,\ell,n}\
\middle|\ \bigoplus_{i\in[\ell]}W_{i}=0\text{ and }\forall
T\subsetneq[\ell],\bigoplus_{i\in T}W_{i}\neq 0\right\\}$

and

$\mathsf{SD}_{\ell}(G^{*})=\\{W\in\mathsf{SD}_{\ell}\mid WG^{*}=0\\}.$

For any $G^{*}$, over $P^{*}\leftarrow\operatorname{\mathcal{P}}(G^{*})$ the
expected number of simple dependencies in $P^{*}$ is

$\displaystyle\mathop{{}\mathbb{E}}_{P^{*}\leftarrow\operatorname{\mathcal{P}}(G^{*})}\sum_{\ell=1}^{r}\sum_{S\in\binom{[r]}{\ell}}\mathbbm{1}[P^{*}_{S}\in\mathsf{SD}_{\ell}]$
$\displaystyle=\sum_{\ell=1}^{r}\sum_{S\in\binom{[r]}{\ell}}\Pr_{P^{*}\leftarrow\operatorname{\mathcal{P}}(G^{*})}[P^{*}_{S}\in\mathsf{SD}_{\ell}]$
$\displaystyle=\sum_{\ell=1}^{r}\binom{r}{\ell}\frac{\abs{\mathsf{SD}_{\ell}(G^{*})}}{\eta(G^{*})^{\ell}}.$
(6)

Now since any $\ell-1$ of the rows of any simple dependency are linearly
independent, we have

$\Pr_{G^{*}\leftarrow\mathbb{F}_{2}^{n\times
g}}[WG^{*}=0]=\frac{1}{2^{(\ell-1)g}}$

for any $W\in\mathsf{SD}_{\ell}$. Therefore,

$\displaystyle\mathop{{}\mathbb{E}}_{G^{*}\leftarrow\mathbb{F}_{2}^{n\times
g}}\abs{\mathsf{SD}_{\ell}(G^{*})}$
$\displaystyle=\sum_{W\in\mathsf{SD}_{\ell}}\Pr_{G^{*}\leftarrow\mathbb{F}_{2}^{n\times
g}}[WG^{*}=0]$ $\displaystyle=\frac{\abs{\mathsf{SD}_{\ell}}}{2^{(\ell-1)g}}.$

By Markov’s inequality it follows that for any $q>0$, with probability $1-1/q$
over $G^{*}\leftarrow\mathbb{F}_{2}^{n\times g}$,

$\abs{\mathsf{SD}_{\ell}(G^{*})}\leq\frac{\abs{\mathsf{SD}_{\ell}}}{2^{(\ell-1)g}}\cdot
q.$

Together with Lemma 11, we have that for any $q,\varepsilon>0$ the expected
number of simple dependencies computed in Equation 6 is at most

$\displaystyle\sum_{\ell=1}^{r}\binom{r}{\ell}\frac{\abs{\mathsf{SD}_{\ell}(G^{*})}}{\eta(G^{*})^{\ell}}$
$\displaystyle\leq
q\sum_{\ell=1}^{r}\binom{r}{\ell}\frac{\abs{\mathsf{SD}_{\ell}}}{\eta(G^{*})^{\ell}\cdot
2^{(\ell-1)g}}$
$\displaystyle\leq\frac{q}{(1-\varepsilon)^{n}}\sum_{\ell=1}^{r}\binom{r}{\ell}\frac{2^{g\ell}\abs{\mathsf{SD}_{\ell}}}{\binom{n}{t}^{\ell}2^{(\ell-1)g}}$
$\displaystyle=\frac{q\cdot
2^{g}}{(1-\varepsilon)^{n}}\sum_{\ell=1}^{r}\binom{r}{\ell}\frac{\abs{\mathsf{SD}_{\ell}}}{\binom{n}{t}^{\ell}}$

with probability
$1-\frac{1}{q}-\frac{2^{g}}{\binom{n}{t}\cdot\varepsilon^{2}}$ over $G^{*}$.
Since

$\frac{\abs{\mathsf{SD}_{\ell}}}{\binom{n}{t}^{\ell}}\leq\Pr_{w_{1},\dots,w_{\ell}\leftarrow\operatorname{\mathcal{S}}_{t,n}}[w_{1}\oplus\cdots\oplus
w_{\ell}=0],$

the remainder of the proof is devoted to showing that

$\sum_{\ell=1}^{r}\binom{r}{\ell}\Pr_{w_{1},\dots,w_{\ell}\leftarrow\operatorname{\mathcal{S}}_{t,n}}[w_{1}\oplus\cdots\oplus
w_{\ell}=0]\leq 2^{-ct^{2}}.$ (7)

for some constant $c>0$. Setting $\tilde{g}=ct^{2}/4$, $q=2^{ct^{2}/4}$, and
$\varepsilon=2^{-t\log(n/t)/8}$ will then complete the proof of Lemma 12.

Let $A$ be the transition matrix for the random walk on $\mathbb{F}_{2}^{n}$
where, at each step, we sample a random
$w\leftarrow\operatorname{\mathcal{S}}_{t,n}$ and move $x\mapsto x\oplus w$.
Observe that
$\Pr_{w_{1},\dots,w_{\ell}\leftarrow\operatorname{\mathcal{S}}_{t,n}}[w_{1}\oplus\cdots\oplus
w_{\ell}=0]$ is equal to the probability that $\ell$ steps of this walk form a
(not necessarily simple) cycle, i.e.,

$\Pr_{w_{1},\dots,w_{\ell}\leftarrow\operatorname{\mathcal{S}}_{t,n}}[w_{1}\oplus\cdots\oplus
w_{\ell}=0]=\frac{1}{2^{n}}\operatorname{Tr}(A^{\ell}).$

Let $H$ be the transition matrix for the random walk on the hypercube graph on
$\mathbb{F}_{2}^{n}$. In Claim 13, we bound the probability that $\ell$ steps
of $A$ form a cycle in terms of the probability that $\ell t$ steps of $H$
form a cycle.

######  Claim 13.

If $\ell=O(n)$ and $t=o(n^{1/3})$, then $\operatorname{Tr}(A^{\ell})\leq
O\left(e^{t^{2}\ell/n}\cdot\operatorname{Tr}(H^{\ell t})\right)$.

###### Proof.

Let $\operatorname{\mathcal{E}}_{H}$ denote the event that $\ell t$ steps of
$H$ form a cycle, and let $\operatorname{\mathcal{E}}_{A}$ denote the event
that $\ell$ steps of $A$ form a cycle. Observe that

$\frac{1}{2^{n}}\operatorname{Tr}(A^{\ell})=\Pr[\operatorname{\mathcal{E}}_{A}]=\Pr\left[\operatorname{\mathcal{E}}_{H}\
|\ \text{every }t\text{-block is distinct}\right]$

where we consider the walk in $H$ as consisting of $\ell$ consecutive blocks
of $t$ steps each, and we say a block is “distinct” if a different index is
changed in each step.

Furthermore,

$\frac{1}{2^{n}}\operatorname{Tr}(H^{\ell
t})=\Pr[\operatorname{\mathcal{E}}_{H}]\geq\Pr\left[\operatorname{\mathcal{E}}_{H}\big{|}\
\text{every }t\text{-block is distinct}\right]\cdot\Pr[\text{every
}t\text{-block is distinct}]$

So
$\Pr[\operatorname{\mathcal{E}}_{A}]\leq\frac{\Pr[\operatorname{\mathcal{E}}_{H}]}{\Pr[\text{every
}t\text{-block is distinct}]}$. Thus, it suffices to see that

$\displaystyle\Pr[\text{every }t\text{-block is distinct}]$
$\displaystyle=\Pr[\text{a given }t\text{-block is distinct}]^{\ell}$
$\displaystyle\geq(1-t/n)^{t\ell}$
$\displaystyle\geq\left(e^{-t}\left(1-\frac{t^{2}}{n}\right)\right)^{t\ell/n}$
$\displaystyle\geq e^{-t^{2}\ell/n}\cdot(1-t^{3}\ell/n^{2})$
$\displaystyle\geq\Omega(e^{-t^{2}\ell/n}).$

∎

Applying Claim 13, we have reduced the problem of proving Equation 7 to
showing that

$\sum_{\ell=1}^{r}\binom{r}{\ell}\cdot\frac{e^{t^{2}\ell/n}}{2^{n}}\operatorname{Tr}(H^{\ell
t})\leq 2^{-\Omega(t^{2})}.$ (8)

Fortunately, the eigenvalues of $H$ are simple to compute:

$\frac{1}{2^{n}}\operatorname{Tr}(H^{\ell
t})=\mathop{{}\mathbb{E}}_{x\leftarrow\mathbb{F}_{2}^{n}}\left[\left(1-\frac{2\operatorname{\mathrm{wt}}(x)}{n}\right)^{\ell
t}\right]$ (9)

where $\operatorname{\mathrm{wt}}(x)$ denotes the Hamming weight of
$x\in\mathbb{F}_{2}^{n}$. We analyze this expression separately depending on
how large $\ell$ is.

#### Small $\ell$ ($\ell\leq(e-\Omega(1))\cdot n/t)$.

We can rewrite Equation 9 as a moment of a simple random walk:

$\mathop{{}\mathbb{E}}_{x\leftarrow\mathbb{F}_{2}^{n}}\left[\left(1-\frac{2\operatorname{\mathrm{wt}}(x)}{n}\right)^{\ell
t}\right]=n^{-\ell
t}\mathop{{}\mathbb{E}}_{X_{1},\dots,X_{n}\leftarrow\\{1,-1\\}}\left[\left(\sum_{i=1}^{n}X_{i}\right)^{\ell
t}\right].$

Let $X=\sum_{i=1}^{n}X_{i}$ where $X_{1},\dots,X_{n}\leftarrow\\{1,-1\\}$. For
small $\ell$, the Gaussian approximation to these moments is good enough. For
even $p$,

$\displaystyle\mathop{{}\mathbb{E}}\left[X^{p}\right]$
$\displaystyle=\sum_{i_{1},\dots,i_{p}\in[n]}\mathop{{}\mathbb{E}}[X_{i_{1}}\cdots
X_{i_{p}}]$ $\displaystyle=\abs{\\{(i_{1},\dots,i_{p})\in[n]^{p}\mid\text{
each $i_{j}$ appears an even number of times}\\}}$ $\displaystyle\leq
n^{p/2}\cdot(p-1)!!$

For odd $p$, $\mathop{{}\mathbb{E}}[X^{p}]=0$. Therefore, for $\ell=O(n/t)$ we
have

$\displaystyle\binom{r}{\ell}\cdot\frac{e^{t^{2}\ell/n}}{2^{n}}\operatorname{Tr}(H^{\ell
t})$ $\displaystyle\leq e^{O(t)}\binom{n}{\ell}\cdot\frac{(\ell
t-1)!!}{n^{\ell t/2}}$ $\displaystyle\leq
e^{O(t)}\left(\frac{en}{\ell}\right)^{\ell}\cdot\left(\frac{\ell
t}{en}\right)^{\ell t/2}\cdot O(\sqrt{\ell t})$
$\displaystyle=e^{O(t)}\left(\frac{\ell}{en}\right)^{\ell(t/2-1)}\cdot t^{\ell
t/2}\cdot O(\sqrt{\ell t})$ If $\ell\leq t$, then this yields
$\displaystyle\binom{r}{\ell}\cdot\frac{e^{t^{2}\ell/n}}{2^{n}}\operatorname{Tr}(H^{\ell
t})$ $\displaystyle\leq
e^{O(t)}\left(\frac{t^{t-1}}{(en)^{t/2-1}}\right)^{\ell}=n^{-\Omega(t)}$ and
if $t<\ell\leq(e-\Omega(1))\cdot n/t$,
$\displaystyle\binom{r}{\ell}\cdot\frac{e^{t^{2}\ell/n}}{2^{n}}\operatorname{Tr}(H^{\ell
t})$ $\displaystyle\leq
e^{O(t)}\left(\frac{e-\Omega(1)}{et}\right)^{\ell(t/2-1)}\cdot t^{\ell
t/2}\cdot O(\sqrt{\ell t})=2^{-\Omega(t^{2})}.$

In either case we have a bound of $2^{-\Omega(t^{2})}$.

#### Large $\ell$ ($\ell\geq(e-o(1))\cdot n/t$).

Using the binomial theorem,

$\displaystyle\frac{1}{2^{n}}\operatorname{Tr}(H^{\ell t})$