Pseudorandom error-correcting code

A Pseudorandom Error-correcting Code (PRC) is a type of SKE that requires ciphertext decoding to be robust to some modifications, introduced by CG24. There is additionally a zero-bit PRC which does not allow for a message. Both variations are useful for constructing cryptographic watermarking of generative AI.

Syntax

An $L$-bit PRC is a tuple of efficient algorithms $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$, with respect to key space $\mathcal{K}$, message space $\{0,1{\}}^L$, and ciphertext space $\{0,1{\}}^n$ such that

• $\mathsf{Gen}(1^{\lambda })\to k$, is a randomized algorithm that takes a security parameter, and outputs a key $k\in \mathcal{K}$,
• ${\mathsf{Enc}}_k(m)\to c$, is a randomized algorithm that takes a key $k\in \mathcal{K}$ and message $m\in \{0,1{\}}^L$, and outputs a ciphertext $c\in \{0,1{\}}^n$,
• ${\mathsf{Dec}}_k(c)\to \{m,\perp \}$, is a deterministic algorithm that takes a key $k\in \mathcal{K}$ and candidate ciphertext $c\in \{0,1{\}}^n$, and outputs either a message $m\in \{0,1{\}}^L$ or $\perp$

A zero-bit PRC has the same requirements as an $L$-bit PRC, except that the message space is just the singleton set $\{1\}$, which means that $\mathsf{Enc}$ takes no input and just outputs codewords. Then, $\mathsf{Dec}$ simply detects whether or not the candidate ciphertext is close to a codeword.

Properties

Pseudorandomness

We define the advantage of a distinguisher $D$ as ${\mathbf{Adv}}_D^{\mathrm{prc}}(\lambda ):=\left|\mathrm{Pr}[D^{{\mathsf{Enc}}_k}(1^{\lambda })=1]-\mathrm{Pr}[D^R(1^{\lambda })=1]\right|,$where $k\leftarrow \mathsf{Gen}(1^{\lambda })$ and $R$ is a random response oracle, which on each query gives a uniformly random $n$-bit string (even on the same input, unlike a random oracle).

A PRC is pseudorandom if for all efficient $D$, there exists a negligible function $\nu$, such that: ${\mathbf{Adv}}_D^{\mathrm{prc}}(\lambda )\le \nu (\lambda )$.

Completeness/Robustness

A PRC is $\epsilon$-robust if there is a negligible function $\nu$, such that for every message $m$, $\mathrm{Pr}[{\mathsf{Dec}}_k(\mathcal{E}({\mathsf{Enc}}_k(m)))\ne m]\le \nu (\lambda ),$where $k\leftarrow \mathsf{Gen}(1^{\lambda })$ and $\mathcal{E}$ is any $\epsilon$-bounded channel. Meaning that $\mathcal{E}$ is a length preserving function with the property that for every $n$-bit string $c$, $\mathcal{E}(c)$ and $c$ have Hamming distance at most $\epsilon \cdot n$.

Soundness

A PRC is sound if there is a negligible function $\nu$, such that for all $\hat{c}$, ${\mathrm{Pr}}_{k\leftarrow \mathsf{Gen}(1^{\lambda })}[{\mathsf{Dec}}_k(\hat{c})\ne \perp ]\le \nu (\lambda )$ — CG24.

Variations

Adaptive robustness

A PRC with adaptive robustness strengthens the robustness property to allow the channel $\mathcal{E}$ to be chosen after seeing the codeword $c={\mathsf{Enc}}_k(m)$, rather than being fixed in advance. Formally, the adversarial channel $\mathcal{E}$ may depend on $c$ (but not on $k$ or $m$ directly). This models a stronger adversary who can tailor the corruption pattern to the specific codeword.

Ideal PRC

An ideal PRC is one for which, with $k\leftarrow \mathsf{Gen}(1^{\lambda })$, oracle access to $({\mathsf{Enc}}_k,{\mathsf{Dec}}_k)$ is computationally indistinguishable from oracle access to an ideal functionality. Its encoder returns a fresh uniformly random $n$-bit string on every query. Its decoder returns $m$ on any string within Hamming distance $\epsilon n$ of a string the encoder returned on input $m$, and $\perp$ on every other string. The adversary never receives $k$. Ideal security implies pseudorandomness, soundness and adaptive robustness against efficient channels — AACDG25.

Zero-bit PRC

A zero-bit PRC has a singleton message space $\{1\}$: the encoder takes no message input and simply outputs a codeword, while the decoder detects whether a candidate string is close to a codeword. Zero-bit PRCs are useful for watermarking generative AI outputs: embed a pseudorandom codeword into generated text/images such that possession of the secret key allows detection, while outputs look uniformly random to anyone without the key — CG24.

Other results

• PRCs were introduced in CG24 motivated by undetectable watermarking of AI-generated content
• Zero-bit PRC ⇒ Watermarking
• Subexponential LPN ⇒ PRC, including zero-bit PRCs — CG24

Participates in

Builds on Pseudorandom error-correcting code

• Adaptive robustness ⇒ PRC (via Adaptive robustness)
• PRC ⇒ SKE
• Zero-bit PRC ⇒ Trapdoor pseudorandom generators (via Zero-bit PRC)
• Zero-bit PRC ⇒ Watermarking (via Zero-bit PRC)

Produces Pseudorandom error-correcting code

• Adaptive robustness ⇒ PRC
• Subexponential LPN ⇒ Zero-bit PRC (via Zero-bit PRC)
• Subexponential LPN ⇒ PRC