Paper deep dive
Unforgeable Watermarks for Language Models via Robust Signatures
Huijia Lin, Kameron Shahabi, Min Jae Song
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 7/21/2026, 4:04:21 AM
Summary
This paper introduces a novel watermarking scheme for language models that guarantees unforgeability and recoverability. Unforgeability prevents adversaries from creating false positive watermarks for content unrelated to the model's outputs, while recoverability allows the identification of the specific source text from which modified content was derived. The authors construct this scheme using robust digital signatures built from property-preserving hash functions, ensuring secure attribution and traceability of AI-generated content.
Entities (11)
Relation Signals (9)
Kameron Shahabi → affiliatedwith → University of Washington
confidence 95% · Kameron Shahabi Paul G. Allen School of Computer Science & Engineering, University of Washington
Huijia Lin → affiliatedwith → University of Washington
confidence 95% · Huijia Lin Paul G. Allen School of Computer Science & Engineering, University of Washington
Min Jae Song → affiliatedwith → University of Chicago
confidence 95% · Min Jae Song Data Science Institute, University of Chicago
Unforgeable Watermarking Scheme → hasproperty → Unforgeability
confidence 95% · We strengthen the notion of soundness by introducing two novel guarantees: unforgeability and recoverability.
Unforgeable Watermarking Scheme → hasproperty → Recoverability
confidence 95% · We strengthen the notion of soundness by introducing two novel guarantees: unforgeability and recoverability.
Robust Digital Signatures → constructedfrom → Property-Preserving Hash Functions
confidence 90% · We show that any standard digital signature scheme can be boosted to a robust one using property-preserving hash functions
Recoverability → enables → Source Identification
confidence 90% · Recoverability provides an additional layer of protection: whenever a watermark is detected, the detector identifies the source text from which the flagged content was derived.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Language models now routinely produce text that is difficult to distinguish from human writing, raising the need for robust tools to verify content provenance. Watermarking has emerged as a promising countermeasure, with existing work largely focused on model quality preservation and robust detection. However, current schemes provide limited protection against false attribution. We strengthen the notion of soundness by introducing two novel guarantees: unforgeability and recoverability. Unforgeability prevents adversaries from crafting false positives, texts that are far from any output from the watermarked model but are nonetheless flagged as watermarked. Recoverability provides an additional layer of protection: whenever a watermark is detected, the detector identifies the source text from which the flagged content was derived. Together, these properties strengthen content ownership by linking content exclusively to its generating model, enabling secure attribution and fine-grained traceability. We construct the first undetectable watermarking scheme that is robust, unforgeable, and recoverable with respect to substitutions (i.e., perturbations in Hamming metric). The key technical ingredient is a new cryptographic primitive called robust (or recoverable) digital signatures, which allow verification of messages that are close to signed ones, while preventing forgery of messages that are far from all previously signed messages. We show that any standard digital signature scheme can be boosted to a robust one using property-preserving hash functions (Boyle, LaVigne, and Vaikuntanathan, ITCS 2019).
Tags
Links
- Source: https://arxiv.org/abs/2602.15323v1
- Canonical: https://arxiv.org/abs/2602.15323v1
Trouble viewing inline? Open PDF directly →
Full Text
234,741 characters extracted from source content.
Expand or collapse full text
Unforgeable Watermarks for Language Models via Robust Signatures Huijia Lin Paul G. Allen School of Computer Science & Engineering, University of Washington Kameron Shahabi Paul G. Allen School of Computer Science & Engineering, University of Washington Min Jae Song Data Science Institute, University of Chicago Abstract Language models now routinely produce text that is difficult to distinguish from human writing, raising the need for robust tools to verify content provenance. Watermarking has emerged as a promising countermeasure, with existing work largely focused on model quality preservation and robust detection. However, current schemes provide limited protection against false attribution. We strengthen the notion of soundness by introducing two novel guarantees: unforgeability and recoverability. Unforgeability prevents adversaries from crafting false positives, texts that are far from any output from the watermarked model but are nonetheless flagged as watermarked. Recoverability provides an additional layer of protection: whenever a watermark is detected, the detector identifies the source text from which the flagged content was derived. Together, these properties strengthen content ownership by linking content exclusively to its generating model, enabling secure attribution and fine-grained traceability. We construct the first undetectable watermarking scheme that is robust, unforgeable, and recoverable with respect to substitutions (i.e., perturbations in Hamming metric). The key technical ingredient is a new cryptographic primitive called robust (or recoverable) digital signatures, which allow verification of messages that are close to signed ones, while preventing forgery of messages that are far from all previously signed messages. We show that any standard digital signature scheme can be boosted to a robust one using property-preserving hash functions (Boyle, LaVigne, and Vaikuntanathan, ITCS 2019). Contents 1 Introduction 1.1 Our results 1.2 Related work 2 Technical Overview 2.1 Robust and recoverable signatures from PPH 2.2 Watermarking using robust signatures and block steganography 2.3 Discussion 3 Watermarking definitions 3.1 Watermarking 4 Preliminaries 4.1 Property-preserving hash 4.2 Block steganography 5 Robust and Recoverable Digital Signatures 5.1 Difference-recovering hash family 5.2 Robust signature from PPH 5.3 Recoverable signatures from difference-recovering PPH 5.4 Instantiating Hamming signatures 6 Recoverable, Robust, and Unforgeable Watermarking 6.1 Robust and unforgeable watermarking 6.2 Generalizing verification to chains 6.3 Recoverable watermarking 6.4 Instantiating Hamming watermarks A Strong Difference Recovery and Homomorphic PPH B Sharp Sketches and Lower Bounds 1 Introduction The rapid rise of generative AI has made reliable content provenance—maintaining verifiable records of the origin and history of generated content—an urgent priority. The remarkable quality of content output by GenAI models, including large language models (LLMs) like GPT-4 [2] and diffusion models such as Stable Diffusion [35], increasingly blurs the line between authentic and synthetic content. Without reliable provenance, trust in digital ecosystems erodes, enabling large-scale misinformation, disputed ownership, and other serious risks [7]. This paper focuses on two avenues of content provenance: • Tracing content to its source: Attributing generated content to the model, model owner, or prompter responsible for generating it. • Tracking edits: Recovering the modifications or edits made to generated content by computationally bounded parties. A recent line of work [1, 29, 24] has introduced watermarking as a tool for provenance. However, existing notions of watermarking typically target a narrow objective and offer guarantees that fall short of reliable source tracing. Moreover, prior approaches do not consider the challenge of tracking edits. In this work, we address these limitations in the context of language models. Existing watermarking guarantees. A watermarking scheme for a language model is a protocol for embedding hidden, verifiable watermarks into generated content. It consists of three algorithms, (,,)( Gen, Wat, Ver). The key-generation algorithm jointly samples watermarking and verification keys (,)←(1λ)( sk, vk)← Gen(1^λ). As we will discuss shortly, we may either consider a public or secret verification key. The watermarking algorithm (,⋅) Wat( sk,·) acts as the interface to the language model, receiving prompts x∈0,1∗x∈\0,1\^* and producing watermarked responses y∈0,1∗y∈\0,1\^*. The verification algorithm (,⋅) Ver( vk,·) decides whether a candidate string ζ∈0,1∗ζ∈\0,1\^* is watermarked. Existing constructions [14, 22, 17] satisfy the following security properties: • Robustness: No efficient attacker with oracle access to Wat_ sk111In the public verification key setting, the attacker also receives the verification key vk; in the secret key setting they instead have oracle access to Ver_ vk. can produce text that is close, under a specified closeness predicate, to one of the responses y←(x)y← Wat_ sk(x) that they observe, but for which verification fails. In other words, it is hard to remove the watermark through mild modifications. • Soundness: No attacker acting independently of the watermarking and verification keys (,)( sk, vk) can generate text that is incorrectly flagged as watermarked. Preserving model quality is also a central goal. The strongest notion, undetectability [13, Definition 9], requires that without the watermarking and verification keys, no efficient observer can distinguish the oracle Wat_ sk from an oracle that produces standard (unwatermarked) outputs from the underlying model. In this work, we adopt undetectability as a core requirement for watermarking schemes. At a high level, robustness and soundness address complementary failures: robustness protects against adversaries attempting to trigger false negatives, while soundness defends against false positives. However, the threat model for soundness is weaker than that for robustness. Soundness adversaries must act without knowledge of the watermarking and verification keys. This restriction is information-theoretic, implying that the attacker has no access to watermarked content (which depends on the keys) and cannot test verification decisions on candidate text. In contrast, robustness adversaries may adaptively query watermarked outputs and are provided access to the verification procedure 222Because soundness is defined under a weaker threat model, existing watermarking schemes typically achieve soundness against computationally unbounded adversaries, whereas robustness has been achieved either against computationally bounded [14, 4] or unbounded [17] adversaries.. Despite this gap, these definitions do well in capturing the original use cases of language watermarking: distinguishing AI-generated content from honest, human-written text. Prior work has focused on two settings: public verification [17], where the verification key is released so that anyone can distinguish content, and private verification [14, 22], where a model owner keeps their verification key secret and uses it to test their own model’s content—for example, to avoid retraining their model on its own prior outputs while scraping the web for training data [36]. The robustness adversary then receives appropriate access to the verification key—full access to vk in the public key setting and oracle access to Ver_ vk in the secret key setting—as well as oracle access to Wat_ sk, reflecting the capabilities of a motivated attacker who is actively trying to remove the watermark. The soundness adversary, on the other hand, gets no access to the keys, which is justified under this traditional setup, as honest humans are unlikely to produce text correlated with randomly chosen watermarking and verification keys, and thus would rarely trigger false positives. Moreover, some applications can naturally tolerate a small number of false positives. For instance, in the example of filtering a model’s own outputs from its training data, it may be acceptable if a few human written texts are mistakenly identified as watermarked and filtered out of the training data. Tracing the source: Unforgeability. Unfortunately, existing soundness guarantees are insufficient for reliably tracing content back to its source. This is an important functionality for applications that require accountability, where it is crucial to identify parties responsible for generating harmful content, or important to assign credit to deserving parties that produced content. One might hope that verifying text under a particular verification key, together with soundness, would serve as proof that the content originated from the owner of the corresponding watermarking key. However, enabling such fine-grained attribution motivates a new class of attacks. Adversaries may observe previously generated watermarked content, detection outcomes (in the secret key setting), or the verification key itself (in the public key setting) to produce content that differs significantly from any genuine model output, yet is still flagged as watermarked. We refer to such attacks as forgeries. For example, an adversary may want to forge a model owner’s watermark onto harmful content, to frame the model owner for producing it. Soundness alone, which only protects against key-independent adversaries, provides no protection against these key-dependent forgeries. To address this, we propose a strengthened notion of soundness, (robust) unforgeability, which allows for dependence on keys: • Unforgeability: No efficient attacker with a watermarking oracle Wat_ sk can produce content that is far (under some closeness predicate) from all the responses y←(x)y← Wat_ sk(x) that they observe, yet is still flagged as watermarked. The attacker is also given access to the verification key vk (in the public key setting) or to a verification oracle Ver_ vk (in the secret key setting). Figure 1 illustrates the distinction between soundness and unforgeability. With an unforgeable watermarking scheme, content that verifies under a particular verification key vk can be reliably attributed to the owner of the corresponding watermarking key sk, since it must closely resemble content generated using that key. Figure 1: Illustration of watermarking guarantees. Correctness and soundness (blue and purple) are statistical guarantees, whereas robustness and unforgeability (green and red) can be computational. Consequently, the green and red regions may contain unwatermarked and watermarked content respectively, but no efficient adversary can find them. Our notion of unforgeability is inspired by digital signatures but differs in that it only prevents forgery of content that is significantly far from the model’s outputs, rather than content that is merely different. This design ensures that unforgeability complements robustness. A strict digital signature–style definition would conflict with robustness, since even mildly modified text that still verifies could be treated as a forgery. Prior work on watermark unforgeability [14, 17] illustrates this trade-off: these approaches leverage digital signatures but do not maintain robustness. Tracking edits: Recoverability. Prior works have yet to consider tracking edits to generated text. We introduce a formal notion, (robust) recoverability, which allows doing so. Recoverable watermarks include an additional polynomial time algorithm Rec which outputs a list, with the property: • Robust recoverability: If an efficient adversary produces text ζ that is close (under a closeness predicate) to some response y←(x)y← Wat_ sk(x), then the list (,ζ) Rec( vk,ζ) contains a substring of y whose length is nearly the length of ζ 333We allow a small loss in length between the recovered substring from y and the adversary’s output ζ.. A key benefit of recoverability is that it reduces ambiguity in defining closeness using a boolean predicate Φ:0,1∗×0,1∗→0,1 :\0,1\^*×\0,1\^*→\0,1\. In an unforgeable watermarking scheme, adversarially generated text verifies only if it is close, according to Φ , to one of the adversary’s observed model-generated responses. However, text may be close under that predicate yet still not warrant attribution to the watermarker, as it seems unlikely that any single predicate can capture diverse attribution decisions. Recoverability addresses this by enabling reconstruction of the original output, allowing the verifier to make a more informed judgement about whether to attribute content to the watermarker or to a user who modified that content. Recoverability can be viewed as a strengthening of robustness, protecting against false negatives by ensuring that we recover, rather than merely verify, when text is close to a watermarked output. It does not, however, protect against false positives in the recovered list. Nonetheless, some applications of recoverability (e.g., aiding in attribution decisions) may require the guarantee that the recovered substrings genuinely originate from the source model. We formalize this with unforgeable recoverability: if an efficient adversary produces text ζ such that the recovery algorithm outputs a non-empty list ((,ζ)≠⟂ Rec( vk,ζ)≠ ), then each recovered ξ∈(,ζ)ξ∈ Rec( vk,ζ) must be a substring of some response y←(x)y← Wat_ sk(x) that the adversary approximately copied. Applications of unforgeability and recoverability. Unforgeability enables reliably tracing content back to a specific watermarking key. This supports the following applications: • Strengthened claims of ownership and accountability. Unforgeable watermarking guarantees that content attributed to a particular watermarker (e.g., a model owner or a prompter) genuinely originates from them. This enables reliable authorship claims (e.g., for AI-generated art) and supports accountability (e.g., determining whether harmful content was actually produced by a certain watermarker). • Improved soundness for honest users. A user may interact with a watermarked model honestly—for instance, by observing and substantially modifying watermarked outputs to avoid direct copying. Soundness offers no protection against false positives in such cases, since the resulting text may still be correlated with the watermarking key. Moreover, as language models and watermarked outputs become increasingly widespread, even fully human-written text may inadvertently be correlated with watermarking keys [40], undermining the independence assumption that soundness relies on. Our threat model protects such honest users from false positives. • Tracking memorization or distillation. Consider a scenario in which a new language model, trained on content scraped from the internet, may have memorized outputs from a different, watermarked model. Unforgeability guarantees that if the new language model’s output verifies as watermarked under that watermarking key, then it is genuinely close to an output produced by the watermarked model. This provides strong evidence for claims of model distillation (as alleged in DeepSeek’s use of GPT-4). Recoverability, in turn, allows for tracking the modifications made to generated content produced by a certain watermarking key. This allows: • Finer-grained attribution. For example, in the public verification key setting, an instructor may recover AI-generated text that a student approximately copied, in order to determine whether that student used AI in a permissible manner. Unforgeable recoverability ensures that the student truly observed edit the recovered AI-generated text. • Tracing edit histories. A verifier can reconstruct content that has been modified or built upon by multiple watermarkers by following the recovery chain using their respective verification keys. 1.1 Our results Our contributions fall under two categories: conceptual and technical. Conceptually, we introduce new public and secret key notions of unforgeability and recoverability for watermarking schemes (Section 3.1). Towards attaining these properties, we define new cryptographic tools—robust and recoverable digital signatures (Section 5)—which may be of independent interest. We show these can be constructed from property-preserving hashes (PPHs) [11], a primitive that, although previously studied, has largely been treated as a standalone tool. Our work demonstrates a novel use of PPH as a building block in cryptographic constructions, uncovering an unexplored connection to AI content provenance. On the technical side, we develop a general framework for constructing robust and recoverable digital signatures, as well as recoverable, robust, and unforgeable watermarking schemes for language model. Our framework accomodates any general predicate defining closeness. We demonstrate its applicability by obtaining both public and secret key watermarking schemes for the Hamming predicate (Section 6.4). Along the way, we identify and formalize a useful property of PPHs, which we call difference recovery (Section 5.1), and show that every PPH for the Hamming predicate must satisfy this property. Defining robust, unforgeable, and recoverable watermarking. In Section 3.1, we present our new notions of security for watermarking schemes. We model adversaries as probabilistic polynomial-time (PPT) algorithms that may interact with oracles. For an adversary A with oracle access to M, the transcript of their interaction, denoted () Trans(A M), is the set of all input–output pairs observed by A. For example, if M is a watermarking oracle Wat_ sk, the transcript is the set of all the prompt-response pairs (x,y)(x,y) such that A queried (x) Wat_ sk(x) and received response y. A robust and unforgeable watermarking scheme ensures that adversarially generated text verifies if and only if it is close to one of the adversary’s observed responses. This can be decomposed into two conditions: the “if” direction corresponds to robustness, while the “only if” direction corresponds to unforgeability. The meaning of closeness is determined by a two-input predicate Φ that outputs 1 iff its inputs are deemed close. Definition 1.1 (Robust and unforgeable watermarking, informal version of Definitions 3.4 and 3.5). For any closeness predicate Φ , a watermarking scheme (,,)( Gen, Wat, Ver) for a language model is public key Φ -robust and unforgeable if for any PPT adversary A, ((,ζ)=1)⇔(∃(x,y)∈() such that Φ(ζ,y)=1), ( Ver( vk,ζ)=1 ) (∃(x,y)∈ Trans(A Wat_ sk) such that (ζ,y)=1 )\;, with probability at least 1−negl(λ)1-negl(λ) over (,)←(1λ)( sk, vk)← Gen(1^λ) and ζ←()ζ Wat_ sk( vk). Secret key robustness and unforgeability are the same, except A gets oracle access to Ver_ vk, rather than full access to vk. Note that the adversary’s output ζ∈0,1∗ζ∈\0,1\^* and watermarked outputs y∈0,1∗y∈\0,1\^* may have different lengths. With this in mind, one can think of Φ(ζ,y)=1 (ζ,y)=1 semantically as “ζ is approximately contained in y,” meaning that there exists a substring of y to which ζ is similar to. In other words, Φ(ζ,y)=1 (ζ,y)=1 indicates that the adversary approximately copied a portion of the response y. We also define recoverable watermarking. Robust recovery states that a verifier can recover an original substring from every watermarked response that an adversary approximately copies from. Definition 1.2 (Robust recovery, informal version of Definition 3.6). For any closeness predicate Φ , a recoverable watermarking scheme (,,)( Gen, Wat, Rec) for a language model is public key Φ -robust if for any PPT adversary A, ∀(x,y)∈() such that Φ(ζ,y)=1, ∀(x,y)∈ Trans(A Wat_ sk) such that (ζ,y)=1, (,ζ) contains a substring of y that is the same size as ζ, up to some loss, Rec( vk,ζ) contains a substring of y that is the same size as $ζ$, up to some loss, with probability at least 1−negl(λ)1-negl(λ) over (,)←(1λ)( sk, vk)← Gen(1^λ) and ζ←()ζ Wat_ sk( vk). We require that any recovered substring be sufficiently long relative to the adversary’s output, meaning that (,ζ) Rec( vk,ζ) contains a substring of size at least (|ζ|−loss)(|ζ|-loss) for a prescribed loss parameter. Robust recoverability does not protect against false positives in the recovered list; this restriction is enforced separately by the following unforgeability requirement, which ensures that every recovered string corresponds to a genuine model output that was approximately copied by the adversary. Definition 1.3 (Unforgeable recovery, informal version of Definition 3.7). For any closeness predicate Φ , a recoverable watermarking scheme (,,)( Gen, Wat, Rec) for a language model is public key Φ -unforgeable if for any PPT adversary A, for every recovery ξ∈(,ζ) every recovery ξ∈ Rec( vk,ζ) ∃(x,y)∈() such that ξ is a substring of y and Φ(ζ,y)=1, ∃(x,y)∈ Trans(A Wat) such that ξ is a substring of y and (ζ,y)=1, with probability at least 1−negl(λ)1-negl(λ) over (,)←(1λ)( sk, vk)← Gen(1^λ) and ζ←()ζ Wat_ sk( vk). Recoverability can thus be viewed as a witness variant of robustness: rather than merely deciding whether a given text ζ is watermarked, Rec outputs a certificate justifying that decision—namely a list of model-generated texts whose similarity to ζ can be verified. Any recoverable watermarking scheme that satisfies robustness and unforgeability immediately yields a standard robust and unforgeable watermarking scheme: one can simply verify content whenever the recovery algorithm recovers any text, (,ζ):=((,ζ)≠⊥). Ver( vk,ζ):= ( Rec( vk,ζ)≠ ). Realizing our definitions. Our main technical result is a general framework for constructing watermarking schemes that are recoverable, robust, and unforgeable. This framework relies on two building blocks. The first is robust steganography, an abstraction which we observe is implicitly achieved by existing watermarking schemes. The second is robust and recoverable digital signatures, a new notion that we introduce and construct. Robust block steganography. Robust block steganography schemes (Definition 4.11) are closely related to watermarking schemes, but additionally allow embedding messages into generated content while preserving output quality. The term block refers to their fixed-size interface: for a given security parameter, the message size k and output size n are fixed, and the scheme embeds messages m∈0,1km∈\0,1\^k into blocks y∈0,1ny∈\0,1\^n. More formally, for message and block sizes k,n:ℕ→ℕk,n:N , a block steganography scheme for a language model consists of algorithms (,,)( Gen, Embed, Dec). The key-generation algorithm samples secret and decoding keys jointly as (,)←(1λ)( sk, dk)← Gen(1^λ). The embedding algorithm (,π,m)∈0,1n(λ) Embed( sk,π,m)∈\0,1\^n(λ) takes a context π∈0,1∗π∈\0,1\^* and a message m∈0,1k(λ)m∈\0,1\^k(λ) and outputs a block y∈0,1n(λ)y∈\0,1\^n(λ). The decoding algorithm (,ζ)∈0,1k(λ)∪⟂ Dec( dk,ζ)∈\0,1\^k(λ)∪\ \ outputs either a decoded message or a failure symbol. Robustness with respect to a closeness predicate Φ requires that if a block ζ∈0,1n(λ)ζ∈\0,1\^n(λ) (chosen by an efficient adversary) is close to a valid embedding y of a message m, then ζ will decode to that message, (∃((π,m),y)∈() such that Φ(ζ,y)=1)⟹((,ζ)=m), (∃ ((π,m),y )∈ Trans(A Embed_ sk) such that (ζ,y)=1 ) ( Dec( dk,ζ)=m )\;, Block steganography should also preserve the quality of generated text. We enforce this by requiring they satisfy undetectability [13] with respect to the underlying language model444Informally, this ensures that no efficient adversary, without the watermarking and verification keys, can distinguish an oracle producing embedded outputs Embed_ sk from one producing unembedded outputs according to the underlying language model.. We emphasize that robustness and undetectability are the only properties we require. In particular, block steganography schemes need not prevent false positives nor support recovery, and therefore do not provide unforgeability or recoverability. This matches existing constructions [14, 4, 17], which achieve neither555These constructions do satisfy soundness, but our results hold even when using an unsound block steganography scheme.. Nonetheless, we show that block steganography can be generically composed with robust and recoverable digital signatures to obtain watermarking schemes that are simultaneously robust, recoverable, and unforgeable. Robust signatures. We introduce new notions of robust and recoverable signatures (Section 5). A robust signature scheme verifies on an adversarially chosen message-signature pair (ζ,σ)(ζ,σ) if and only if ζ is close to a message y that was previously signed with σ. A signature scheme is further said to be recoverable if, from any adversarially chosen message-signature pair (ζ,σ)(ζ,σ), the recovery algorithm recovers a message y if and only if (1) ζ is close to y and (2) y is a message that was previously signed with σ. Definition 1.4 (Robust/Recoverable signatures, informal version of Definitions 5.1 and 5.2). For any closeness predicate Φ , a digital signature scheme (,,)( Gen, Sign, Ver) is Φ -robust if for any PPT adversary A, ((,ζ,σ)=1)⇔(∃y such that (y,σ)∈() and Φ(ζ,y)=1). ( Ver( pk,ζ,σ)=1 ) (∃ y such that (y,σ)∈ Trans(A Sign_ sk) and (ζ,y)=1 )\;. A digital signature scheme (,,)( Gen, Sign, Rec) is further said to be Φ -recoverable if ((,ζ,σ) outputs y)⇔((y,σ)∈() and Φ(ζ,y)=1). ( Rec( pk,ζ,σ) outputs y ) ((y,σ)∈ Trans(A Sign_ sk) and (ζ,y)=1 )\;. Here, (,)←(1λ)( sk, pk)← Gen(1^λ) and (ζ,σ)←()(ζ,σ) Sign_ sk( pk), We refer to the reverse direction of the above statements—–namely, that (ζ,σ)(ζ,σ) verifies (or recovers) only if ζ is close to a message y signed with σ—–as strong unforgeability. Strongly unforgeable robust signatures generalize standard strong UF-CMA digital signatures [8], which are recovered as the special case where Φ is the equality predicate. The term strong reflects the fact that this notion guarantees not only that signatures cannot be forged on unsigned messages, but also that no new signatures can be produced even for messages that were previously signed under a different signature. Informal guarantees of our framework. Using these two tools, we design a general approach for constructing robust and unforgeable watermarking schemes. To understand its guarantees, it will be helpful to think of a string y∈0,1∗y∈\0,1\^* as being broken into consecutive, non-overlapping n-bit blocks (y1,…,y⌊|y|/n⌋)(y_1,…,y_ |y|/n ), where yty_t denotes the t-th contiguous, non-overlapping n-bit substring of y. We make this notation precise in Section 3. At a high level, for a security parameter λ, our construction produces watermarked text y←(x)y← Wat_ sk(x) by repeatedly generating blocks yty_t of size n=n(λ)n=n(λ) using a block steganography scheme. Each block embeds the robust signature σt−1 _t-1 of the preceding block yt−1y_t-1. Verification on candidate text ζ=(ζ1,…,ζ⌊|ζ|/n⌋)ζ=( _1,…, _ |ζ|/n ) proceeds by attempting to decode a signature from each block ζt _t and verifying it against the preceding block ζt−1 _t-1666Section 2.2 contains a more detailed overview.. Intuitively, this means that ζ will verify if and only if its blocks are close to a sequence of back-to-back blocks from a watermarked response y. We capture this intuition using the every-block-close lifting of a predicate Φ , [Φ,n] EBC[ ,n]. This predicate deems that “ζ is approximately contained in y” if it is blockwise Φ -close to a consecutive sequence of blocks in y, [Φ,n](ζ,y):(Parse ζ and y into n-bit blocks (ζ1,…,ζ⌊|ζ|/n⌋) and (y1,…,y⌊|y|/n⌋).Output 1 iff ∃t∈ℕ such that ∀j∈[⌊|ζ|/n⌋],Φ(ζj,yt+j−1)=1.). EBC[ ,n](ζ,y):\; ( aligned &Parse ζ and y into n-bit blocks ( _1,…, _ |ζ|/n ) and (y_1,…,y_ |y|/n ).\\ &Output 1 iff ∃ t such that ∀ j∈[ |ζ|/n ],\; ( _j,y_t+j-1)=1. aligned ). Figure 2 captures the predicate in action. Figure 2: Illustration of [Φ,n] EBC[ ,n]-closeness. Green dotted lines indicate Φ -closeness. The string ζ∗ζ^* is [Φ,n] EBC[ ,n]-close to y because its blocks are Φ -close to three consecutive blocks of y, whereas ζ′ζ may be far: although ζ′ζ is close to a substring of y of length 2n2n, this substring is not aligned with two blocks of y. By combining a Φ -robust block watermarking scheme, and a Φ -robust and recoverable digital signature scheme, we obtain a watermarking scheme that is recoverable, robust, and unforgeable with respect to the every-block-close lifting of Φ . Whether the watermark is public or secret key depends on the underlying block steganography scheme. Theorem 1.5 (General watermarking framework, informal version of Theorem 6.1). Let Q be any language model, Φ be any closeness predicate, and n:ℕ→ℕn:N be any polynomial block size. Assume there exists both • A (secret or public key) steganography scheme for Q that is robust to Φ and has block size n. • A digital signature scheme that is robust to Φ . Then there exists a watermarking scheme for Q that is (secret or public key) robust and unforgeable777Against adversaries outputting sufficiently long strings ζ. with respect to the closeness predicate [Φ,n] EBC[ ,n]. If the digital signature scheme is additionally recoverable, then there exists a recoverable watermarking scheme for the same predicate. Remark 1.6 (Subtlety between robustness and unforgeability). While the informal theorem suggests that an input ζ verifies if and only if it is [Φ,n] EBC[ ,n]-close to a watermarked response, there is a subtle distinction in the formal guarantees: • For robustness, verification succeeds if the entire string (ζ1,…,ζ⌊|ζ|/n⌋)( _1,…, _ |ζ|/n ) is [Φ,n] EBC[ ,n]-close to a watermarked response y. • For unforgeability, verification succeeds only if the substring consisting of all but the last block, (ζ1,…,ζ⌊|ζ|/n⌋−1)( _1,…, _ |ζ|/n -1), is [Φ,n] EBC[ ,n]-close to a watermarked response y. This gap is made explicit in our full Theorems (Theorems 6.1 and 6.2). Instantiating the framework. We instantiate our framework to obtain a Hamming robust and unforgeable watermarking scheme. Prior work has already constructed both secret and public key robust block steganography schemes for any language model with sufficiently high entropy, when the predicate Φ is the Hamming predicate, which indicates if its inputs are close in Hamming distance. In particular, assuming the existence of ideal pseudorandom codes that are robust to a constant fraction of Hamming errors—shown by Alrabiah et al. [4] to follow from the subexponential hardness of exact learning parity with noise [28]—the watermarking construction of Christ and Gunn [14] yields a secret key steganography scheme that is robust to a constant fraction of Hamming errors (Theorem 4.14). Separately, in the random oracle model, Fairoze et al. [17] construct a watermarking scheme for high-entropy language models, which can be viewed as a public-key steganography scheme that is robust to a subconstant fraction of Hamming errors (with a caveat, see the predicate Φδ _δ defined in Theorem 4.16). Finally, in this work we show that robust and recoverable digital signatures for a constant fraction of Hamming errors can be constructed under standard assumptions, namely the existence of collision-resistant hash functions and strong UF-CMA digital signatures (Corollary 5.11). Using these results, we obtain both secret and public key recoverable, robust, and unforgeable watermarking schemes with respect to the every-block-close lifting of the Hamming predicate (Corollaries 6.6 and 6.7). Constructing robust and recoverable signatures. In Section 5.2, we construct robust and recoverable digital signatures with respect to a constant fraction of Hamming errors. We do so by instantiating the following general framework, which leverages property-preserving hashing, introduced by Boyle et al. [11]. Property-preserving hashing For any predicate Φ and hash size k:ℕ→ℕk:N , a Φ -property preserving hash family (PPH) is a hashing scheme (,)( Sample, Eval), that allows computing the predicate value of two inputs using only their hashes of length k(λ)k(λ). That is, (h,h(y),h(y′))=Φ(y,y′) Eval(h,h(y),h(y ))= (y,y ) with probability at least 1−negl(λ)1-negl(λ) over h←(1λ)h← Sample(1^λ) and (y,y′)←(h)(y,y ) (h). Importantly, Eval is adaptively secure. We also observe that, although not explicitly stated, current PPH constructions for the Hamming predicate δ Ham_δ [19, 26] also allow recovering the bitwise difference Δ=x⊕x′ =x\, \,x from a hash h(x)h(x) and an input x′x such that Φ(x,x′)=1 (x,x )=1888In fact, these constructions satisfy a stronger property, allowing recovery of the bitwise difference from just the hashes h(x)h(x) and h(x′)h(x ). However, we show that the weaker property, where the recovery algorithm gets x′x in the clear, suffices for watermarking.. We formalize this as difference recovery and show that this is no coincidence: every PPH for the Hamming predicate must satisfy it (Proposition 5.5). Definition 1.7 (Difference recovery, informal version of Definition 5.4). A PPH (,)( Sample, Eval) for a predicate Φ is said to satisfy difference recovery if there exists a PPT recovery algorithm Rec such that (Φ(x,x′)=1)⟹((h,h(x),x′)=x′⊕x), ( (x,x )=1 ) ( Rec(h,h(x),x )=x x )\;, holds with probability at least 1−negl(λ)1-negl(λ) over h←(1λ)h← Sample(1^λ) and (x,x′)←(h)(x,x ) (h). Difference recovery is an unexplored aspect of PPHs, and our work illustrates its utility through a compelling application: recoverable watermarking. General framework for robust signatures. We show that any standard strongly unforgeable digital signature [8] can be supplemented with a Φ property preserving hash (with difference recovery) in order to build a Φ robust (recoverable) digital signature. Theorem 1.8 (General robust signature framework, informal statement of Theorem 5.8). Let Φ be any closeness predicate and let k,ℓ:ℕ→ℕk, :N be any polynomials. Assume there exists • A Φ -PPH with hash size k. • A strongly unforgeable digital signature scheme with signature size ℓ . Then there exists a Φ -robust digital signature scheme with signature size k+ℓk+ . Moreover, if the PPH is difference recovering, then the signature scheme is Φ -recoverable. Instantiating this framework with the difference-recovering Hamming PPH of Holmgren et al. [26], which relies on a special homomorphic hash function, yields a signature scheme that is robust and recoverable against a constant fraction of Hamming errors, with signature size essentially a constant fraction of the message length (Corollary 5.11). For our purposes, however, we observe that it suffices to use a standard collision resistance hash function rather than the homomorphic one, giving us a Hamming recoverable digital signature scheme from CRHFs and strong UF-CMA signatures. 1.2 Related work Watermarking schemes for generative models. Watermarking text has a history that predates the current era of large language models, with early work [39, 5, 6] focused on embedding signals into fixed objects in a way that is hard to remove, while preserving their perceived quality. More relevant to our setting, which views language models as randomized sampling algorithms, is the recent line of work [1, 29, 30, 31, 13, 43] that develops watermarking techniques from this perspective, typically by embedding correlations with a watermarking key at the token level during the sampling process. While many existing methods are distortion-free at the level of a single response [1, 31], they may introduce noticeable distortions when the watermarked model is queried repeatedly—across multiple rounds of interaction with arbitrary seed prompts. The strongest notion of model quality preservation that guards against such cumulative distortions, known as watermark undetectability, was introduced by Christ et al. [13]. Among undetectable watermarking schemes, only a select few guarantee unforgeability [17, 14]. These methods embed digital signatures into text in a computationally undetectable manner, thereby achieving both undetectability and unforgeability. However, these watermarks lack robustness. Our robust digital signatures can be integrated into either of these schemes. Recently, undetectable watermarking schemes for image models have been proposed by Gunn et al. [24], representing a notable step toward achieving undetectability in generative models beyond discrete autoregressive sampling. For a broader overview of the field, we refer the reader to the surveys [32, 44]. Steganography. Steganography, the practice of hiding messages within content drawn from some distribution (referred to as a channel), has a long history of scientific study. Early work by Cachin [12] considered a noiseless setting, where a message only needed to be hidden within unaltered content sampled from the channel. This study was motivated by Simmons’ Prisoners’ Problem [37], in which two prisoners in separate cells wish to communicate hidden messages by embedding them into letters visible to the warden. Hopper et al. [27] further studied this problem and introduced robust steganography. However, in these initial works, the decoder was often assumed to know the distribution from which the content was drawn. In contrast, hiding messages in AI-generated content presents additional challenges. The decoder, who sees content later down the line, does not know the prompt used to generate it and therefore cannot infer the distribution it came from. Nonetheless, a recent line of work has shown that (robust) steganography is still possible in this more demanding setting. Zamir [41] demonstrated that, even without knowledge of the content distribution, messages can be hidden in unaltered content. Follow-up works [14, 17] extend this result to the noisy setting, constructing schemes in which the message can be decoded even in the presence of adversarial errors. Pseudorandom error-correcting codes. Pseudorandom codes (PRC), introduced by Christ and Gunn [14], are error-correcting codes whose codewords are computationally indistinguishable from uniformly random strings to any observer lacking the decoding key. As objects that satisfy both pseudorandomness and error correctability, PRCs provide a natural foundation for constructing watermarking schemes that achieve both undetectability and robustness [14, 24, 15, 22]. PRCs with varying robustness properties have been constructed under standard cryptographic assumptions, such as the subexponential hardness of learning parity with noise (LPN) [14, 21]. In particular, Golowich and Moitra [22] construct PRCs that are robust to a constant fraction of edits, including substitutions, insertions, and deletions, at the cost of requiring a larger alphabet. This yields watermarking schemes that are robust under edit distance. However, the notion of robustness satisfied by previous PRC constructions is weak in a different sense. The decoder’s robustness guarantee holds only against corruptions that are generated independently of the PRC keys. In particular, this requirement assumes that the corruption adversary has not observed any prior codewords. This lack of adaptive robustness was highlighted by Cohen et al. [15], who ask whether PRC messages remain robustly decodable even after the perturbation adversary (or error channel) has observed multiple codewords. Ideal PRCs, introduced by Alrabiah et al. [4], address this limitation by constructing PRCs that remain robust even against computationally bounded adversaries with black-box access to both encoding and decoding oracles. In this work, we use them to instantiate secret key robust block steganography schemes. Property-preserving hash functions. We build our watermarking scheme on top of property-preserving hash functions (PPH), introduced by Boyle et al. [11]. Several PPH constructions have been proposed for the exact Hamming predicate under standard cryptographic assumptions [19, 26, 42]. Particularly relevant to our work is the elegant construction by Holmgren et al. [26], which achieves nearly optimal hash size. Their key idea of combining syndrome list-decoding of linear error-correcting codes with collision-resistant hash functions has prior roots in the study of error-correcting codes against computationally bounded noise [33, 16]. Recent work by Bogdanov et al. [10] proposed and examined a new computational assumption that implies a PPH for the Gap-ℓ2 _2 predicate over Euclidean space. This enables evaluation of whether the ℓ2 _2 distance between a pair of real vectors is small or large based solely on their compressed digests. As such, these PPHs serve as adversarially robust locality-sensitive hash functions for the Euclidean distance: compressive hash functions for which it is computationally hard to find input pairs whose true pairwise distances differ substantially from those inferred from their hashes. PPHs are also related to the cryptographic notion of secure sketches [16], which are practically relevant in biometric applications where the secret key (e.g., one’s biometric data) is inherently noisy and varies slightly with each use. Secure sketches enable recovery of a value x given a sketch g(x)g(x) and a nearby input x′x . This can be viewed as a relaxation of PPH, as it assumes access to one noisy input in the clear. 2 Technical Overview We highlight the techniques we use to construct robust signatures (Section 2.1) and robust, unforgeable, and recoverable watermarks (Section 2.2). 2.1 Robust and recoverable signatures from PPH Our construction produces a Φ -recoverable signature scheme (,,)( Gen, Sign, Rec) from a Φ -difference-recovering PPH, [,,] PPH[ Sample, Eval, Rec], and a strongly unforgeable digital signature scheme, [,,] DSS[ Gen, Sign, Ver] [8]. An analogous construction yields a robust (but not recoverable) digital signature from a standard PPH without difference recovery. To sign a message y∈0,1ny∈\0,1\^n, we compute its property-preserving hash h(y)h(y), then generate a signature of that hash τ←.(.,h(y))τ← DSS. Sign( DSS. sk,h(y)). The robust signature is defined as σ=(h(y),τ)σ=(h(y),τ). The public and secret keys are given by =(h,.) pk=(h, DSS. pk) and =. sk= DSS. sk. To verify this signature σ=(h(y),τ)σ=(h(y),τ) against a candidate message ζ∈0,1nζ∈\0,1\^n, we compute (,ζ,σ) Ver( pk,ζ,σ) =.(.,h(y),τ)∧.(h,h(y),h(ζ)). = DSS. Ver( DSS. pk,h(y),τ) PPH. Eval(h,h(y),h(ζ))\;. We formally describe our construction in Figure 4. We give the intuition behind our security proofs, which can be found in Section 5.2. Robustness. Let σ=(z,τ)σ=(z,τ) be the robust signature of some message y∈0,1ny∈\0,1\^n. If an adversarially chosen message ζ is Φ -close to y, then with overwhelming probability .(h,z,h(ζ))=1 PPH. Eval(h,z,h(ζ))=1, since z=h(y)z=h(y), from PPH correctness, and .(z,τ)=1 DSS. Ver(z,τ)=1 from DSS correctness. Unforgeability. Suppose an adversary A forges a pair (ζ,σ′)(ζ,σ ) with inverse-polynomial probability, meaning (,ζ,σ′)=1 Ver( pk,ζ,σ )=1, but ζ is Φ -far from all messages y∈0,1ny∈\0,1\^n associated with the signature σ′σ . We consider two cases and show that each leads to a contradiction. 1. The forged σ′σ is not one of the signatures observed by A through its queries to the robust signature oracle Sign_ sk. Notice that responses from Sign_ sk are precisely the message-signature pairs (z,.(.,z))(z, DSS. Sign( DSS. sk,z)) that A observes from the underlying standard strongly unforgeable digital signature DSS. If A outputs σ′=(z′,τ′)σ =(z ,τ ) that verifies despite not being one of these pairs, then (z′,σ′)(z ,σ ) breaks the strong unforgeability of DSS. 2. The forged signature σ′=(h(y),τ)σ =(h(y),τ) was observed by A, meaning it is the signature of some message y that is Φ -far from the candidate message ζ. In this case, .(h,h(y),h(ζ)) PPH. Eval(h,h(y),h(ζ)) detects, with overwhelming probability, that y and ζ are Φ -far. If it did not, the pair (y,ζ)(y,ζ) would violate the security of the PPH. Consequently, the verifier rejects, (,ζ,σ′)=0 Ver( pk,ζ,σ )=0, except with negligible probability, leading to a contradiction. Recoverability. For recoverability, we first (robustly) check (,ζ,σ′) Ver( pk,ζ,σ ) to ensure σ′σ is a signature of some y close to ζ. If the signature verifies, then output (,ζ,σ′) Rec( pk,ζ,σ ) =.(h,h(y),ζ)⊕ζ. = PPH. Rec(h,h(y),ζ) ζ\;. Otherwise, (,ζ,σ′)=⊥ Rec( pk,ζ,σ )= . Notice that when an adversarially chosen ζ is Φ -close to a previously signed message y∈0,1ny∈\0,1\^n, difference recovery of PPH ensures that .(h,h(y),ζ) PPH. Rec(h,h(y),ζ) outputs the bitwise difference y⊕ζy ζ with overwhelming probability, so (,ζ,σ′) Rec( pk,ζ,σ ) correctly outputs y. 2.2 Watermarking using robust signatures and block steganography Language models and blocks. Following prior work [24, 14, 17], we model a language model Q:0,1∗→[0,1]Q:\0,1\^*→[0,1] as a mapping that takes in a token sequence and outputs the probability that the next token is 11999Without loss of generality, we consider a binary token alphabet. This assumption is standard in the watermarking literature; see [14, Section 7.1] for a detailed discussion.. Given a prompt x∈0,1∗x∈\0,1\^*, we obtain an n-bit response u=(u[1],u[2],…,u[n])←Q¯n(x)u=(u[1],u[2],…,u[n])← Q_n(x) by autoregressive sampling initialized with x. Throughout this section, we refer to the n-bit blocks (y1,…,y⌊|y|/n⌋)(y_1,…,y_ |y|/n ) of a string y∈0,1∗y∈\0,1\^*. Informally, yty_t denotes the t-th non-overlapping, n-bit substring of y. A first attempt at unforgeable watermarking. A natural approach to constructing unforgeable watermarks is to sign text as it is generated using a standard digital signature scheme and then embed that signature into subsequently generated text via a block steganography scheme. Later, the signature can be decoded and verified along with the text. This is the approach taken by existing constructions that consider unforgeability [14, 17], but it comes at the cost of robustness. Specifically, consider a language model Q. Prior work [14, 4, 17] demonstrates that block steganography schemes can be constructed for any model with sufficiently high entropy. For the purposes of this overview, we therefore assume that Q has high entropy. We will attempt to watermark Q using the approach outlined above. Let λ be the security parameter and n=poly(λ)n=poly(λ) be a block size. Let [,,] Steg[ Gen, Embed, Dec] be a Φ -robust block steganography scheme for Q with block size n. Steg can be either public or secret key. For the purposes of this overview, we will assume it’s public key. Let [,,] DSS[ Gen, Sign, Ver] be a standard digital signature scheme with message size n. To generate verification and watermarking keys (,)( vk, sk), sample .,.)←.(1λ),(.,.)←.(1λ) DSS. pk, DSS. sk)← DSS. Gen(1^λ), ( Steg. dk, Steg. sk)← Steg. Gen(1^λ) and let = vk= (.,( DSS. pk, .) Steg. dk), =(.,.) sk=( DSS. sk, Steg. sk). We can generate 2n2n bits of watermarked text as follows. On input prompt x∈0,1∗x∈\0,1\^*, the watermarking algorithm (,x) Wat( sk,x) first samples n bits normally from the underlying language model, y1←Q¯n(x)y_1← Q_n(x). Next, it signs this block and embeds the signature into the following block101010Because robust block steganography schemes must be expanding in the message, the signature length must be smaller than the resulting block size, i.e., |σ|≪n|σ| n.: σ←.(.,y1),y2←.(.,π=(x,y1),σ),σ← DSS. Sign( DSS. sk,y_1), y_2← Steg. Embed( Steg. sk,π=(x,y_1),σ)\;, and outputs the concatenation (y1,y2)(y_1,y_2). Undetectability of Wat follows from the undetectability of Steg. To verify a candidate text ζ∈0,12nζ∈\0,1\^2n, the verification algorithm (,ζ) Ver( vk,ζ) first parses it into two blocks ζ1,ζ2∈0,1n _1, _2∈\0,1\^n. It then tries to decode a signature from the second block and check if it verifies with the first, (,ζ)=.(.,ζ1,σ′), where σ′←.(.,ζ2). Ver( vk,ζ)= DSS. Ver( DSS. pk, _1,σ ), where σ ← Steg. Dec( Steg. dk, _2)\;. Notice that this approach is unforgeable in that it only verifies ζ=(ζ1,ζ2)←()ζ=( _1, _2) Wat_ sk( vk) when the first block ζ1 _1 exactly matches one of the blocks y1y_1 for which A saw a signature for; otherwise, A could break the unforgeability of DSS with the message ζ1 _1. However, the scheme provides no robustness. Concretely, suppose an adversary ()A Wat_ sk( vk) queries its watermarking oracle and receives a response (y1,y2)(y_1,y_2). If A modifies even a single bit of y1y_1 to produce ζ1 _1, the string (ζ1,y2)( _1,y_2) can no longer verify, despite being nearly identical to an observed response. Robust signatures for both robustness and unforgeability. To overcome the limitation outlined above, we instead embed a robust signature into the generated text. Now, even if A modifies y1y_1 to produce ζ1 _1, so long as Φ(ζ1,y1)=1 ( _1,y_1)=1, the signature—and therefore the watermark—can still verify. Formally, let [,,] RDS[ Gen, Sign, Ver] be a robust signature scheme for the same predicate Φ that Steg is robust to, and generate keys (,)( vk, sk) as in the standard digital signature approach, but using .(1λ) RDS. Gen(1^λ) instead of .(1λ) DSS. Gen(1^λ). We generalize the approach above to generate rnrn bits for any r≥2r≥ 2. For the first block, t=1t=1, the algorithm (,x) Wat( sk,x) invokes y1←Q¯n(x)y_1← Q_n(x). For subsequent blocks t≥2t≥ 2, it updates the context to be the prompt and the text generated up to this point, π=(x,y1,…,yt−1)π=(x,y_1,…,y_t-1), and embeds the robust signature of the previous block: σt−1←.(.,yt−1),yt←.(.,π,σt−1), _t-1← RDS. Sign( RDS. sk,y_t-1), y_t← Steg. Embed( Steg. sk,π, _t-1)\;, The final output is the concatenation of blocks (y1,…,yr)(y_1,…,y_r). Watermark verification. We define watermark verification to operate on rnrn-bit strings for some r≥2r≥ 2. Given a candidate string ζ∗=(ζ1∗,…,ζr∗)ζ^*=( _1^*,…, _r^*) composed of r blocks of n-bits, the verification algorithm r(,ζ∗) Ver_r( vk,ζ^*) checks whether the entire chain of message-signature pairs verifies. Concretely, this means verifying that ∀i∈[r−1],.(.,ζi∗,σi′)=1, where σi′←.(.,ζi+1∗).∀ i∈[r-1],\; RDS. Ver( RDS. pk, _i^*, _i )=1, where _i ← Steg. Dec( Steg. dk, _i+1^*)\;. If RDS is additionally recoverable, we can define a corresponding recovery procedure r(,ζ∗) Rec_r( vk,ζ^*) as follows. ∀i∈[r−1],ξi←.(.,ζi∗,σi′), where σi′←.(.,ζi+1∗).∀ i∈[r-1],\; _i←\; RDS. Rec( RDS. pk, _i^*, _i ), where _i ← Steg. Dec( Steg. dk, _i+1^*)\;. The procedure outputs a single string (ξ1,…,ξr−1)( _1,…, _r-1) provided that none of the recovery attempts return ⊥ , else it outputs ⊥ . Guarantees of our construction when r=2r=2. Consider the simple case r=2r=2. To see that verification is robust, let ζ∗=(ζ1∗,ζ2∗)ζ^*=( _1^*, _2^*) be a candidate text produced by an efficient adversary ()A Wat_ sk( vk). Say that ζ∗ζ^* is approximately contained in some response y←(x)y← Wat_ sk(x) observed by A, meaning that y contains two consecutive n-bit blocks (yt,yt+1)(y_t,y_t+1) such that both Φ(ζ1∗,yt)=1 ( _1^*,y_t)=1 and Φ(ζ2∗,yt+1)=1 ( _2^*,y_t+1)=1. By the Φ -robustness of Steg, we can decode the signature σt _t of yty_t from ζ2∗ _2^*. Moreover, by the Φ -robustness of RDS, the pair (ζ1∗,σt)( _1^*, _t) will pass verification. Similarly, in this setting, the recovery algorithm outputs the first response block yty_t. Moreover, to see the watermark is unforgeable, notice that unforgeability of the digital signature says that if 2(,(ζ1∗,ζ2∗))=1 (or 2(,(ζ1∗,ζ2∗))=yt) Ver_2( vk,( _1^*, _2^*))=1 (or Rec_2( vk,( _1^*, _2^*))=y_t) then ζ1∗ _1^* must be Φ -close to one of the signed blocks yty_t observed by A. We formalize our robustness and unforgeability guarantees in Theorem 6.1, with recoverability stated in Corollary 6.4. Our construction does, however, exhibit a subtle gap. We can guarantee that verification succeeds when both blocks (ζ1∗,ζ2∗)( _1^*, _2^*) are close to back-to-back response blocks (yt,yt+1)(y_t,y_t+1), whereas we can only ensure that successful verification implies the first block ζ1∗ _1^* is close to a single response block yty_t. This asymmetry arises because we embed signatures directly into subsequent blocks: to decode the signature and ensure verification succeeds, both blocks must be close. Successful RDS verification, on the other hand, only certifies the closeness of the underlying message (the first block). We are optimistic that future strategies for embedding messages into AI-generated content could help narrow this gap. Guarantees when r>2r>2. In Theorem 6.2, we show that r Ver_r satisfies a stronger unforgeability guarantee when r>2r>2. Specifically, we show that if r(,(ζ1∗,…,ζr∗))=1, Ver_r ( vk,( _1^*,…, _r^*) )=1, then not only is each block ζi∗ _i^* for i∈[r−1]i∈[r-1] Φ -close to some response block, but moreover the blocks (ζ1∗,ζ2∗,…,ζr−1∗)( _1^*, _2^*,…, _r-1^*) are each Φ -close to the aligned blocks of a consecutive chain (yt,yt+1,…,yt+r−2)(y_t,y_t+1,…,y_t+r-2) present in a single response y. This notion of closeness is captured by the every-block-close lifting of Φ (Definition 3.2). In particular, we obtain an unforgeability guarantee of the following form: (ζ1∗,…,ζr∗)( _1^*,…, _r^*) verifies only if for there is some watermarked response y such that [Φ,n]((ζ1∗,…,ζr−1∗),y)=1 EBC[ ,n] (( _1^*,…, _r-1^*),y )=1. We obtain a matching robustness guarantee: verification succeeds whenever there exists a response y such that [Φ,n]((ζ1∗,…,ζr∗),y)=1 EBC[ ,n] (( _1^*,…, _r^*),y )=1. Generalizing verification to arbitrary-sized strings. In the discussion above, the algorithms r Ver_r and r Rec_r operate on inputs of fixed length ζ∗∈0,1rnζ^*∈\0,1\^rn. Semantically, however, it is more natural for watermark verification to operate on inputs of arbitrary length. In particular, given ζ∈0,1∗ζ∈\0,1\^*, verification should succeed if and only if some sufficiently long substring ζ∗ζ^* of ζ is approximately contained in a watermarked response. For example, if a student copies only a portion of an essay from a watermarked response, the verification algorithm should still verify the watermark when given the full essay. To capture this more semantically meaningful notion, our formal security definitions (Definitions 3.4 and 3.5) differ slightly from the informal ones given in this overview. As a concrete example, for a closeness predicate Φ and a substring-length ℓ:ℕ→ℕ :N , we define public-key (Φ,ℓ)( , )-unforgeability as follows: ((,ζ)=1)⟹(∃ζ∗⪯ζ of size ℓ(λ),∃(x,y)∈() such that Φ(ζ∗,y)=1), ( Ver( vk,ζ)=1 )\;\; \;\; ( array[]l∃ζ^* ζ of size (λ),\\ ∃(x,y)∈ Trans(A Wat_ sk) such that (ζ^*,y)=1 array )\;, where ζ∗⪯ζ^* ζ denotes that ζ∗ζ^* is a substring of ζ. Defining robustness and unforgeability in this way also has the technical advantage of addressing the gap noted in Remark 1.6, as it allows each security property to be stated over substrings of different lengths. In particular, the construction outlined above can be easily adapted to achieve ([Φ,n],rn)( EBC[ ,n],rn)-robustness and ([Φ,n],(r−1)n)( EBC[ ,n],(r-1)n)-unforgeability. This can be done by defining a verifier (,ζ) Ver( vk,ζ) that takes as input an arbitrary-length string ζ∈0,1∗ζ∈\0,1\^* and performs r-block verification r(,ζ∗) Ver_r( vk,ζ^*) on every substring ζ∗⪯ζ^* ζ of length rnrn, accepting if any such substring verifies. We formalize this algorithm in Figure 6. 2.3 Discussion We view our work as an initial step toward a broader line of investigation. Our framework treats robustness and undetectability as the traditional goals of watermarking, while focusing on introducing and achieving the new properties of unforgeability and recoverability without sacrificing the former. We demonstrate its effectiveness by instantiating language watermarking schemes for the every-block-close lifting of the Hamming predicate. The resulting notion of robust signatures is versatile. Our general construction paradigm suggests avenues for improvement and indicates that our ideas can be extended to other modalities of generative AI. We address some concerns, as well as potential applications of our framework to other settings. Why Ideal PRCs do not offer unforgeability? Ideal pseudorandom codes (PRCs) [4] do provide sharp decoding guarantees: any (adversarially chosen) ζ that is sufficiently far from all codewords decodes to ⟂ . At first glance, this suggests that ideal PRCs alone might yield secret key unforgeable watermarks. Indeed, a PRC can be seen as a secret key robust and unforgeable watermarking scheme for the uniform language model, where each bit is equally likely, as text generated by the model is indistinguishable from PRC codewords. For general language models, however, embedding PRC codewords into text introduces errors that break these guarantees. When the embedding error is large, a string ζ that is close to some watermarked response y may be far from the PRC codeword embedded in y, and a string ζ that is far from all valid responses y may still be close to a codeword. Therefore, even if ζ is far from all responses y, if the embedding errors are large it can still verify as watermarked. Typically, this error is bounded by making an assumption on the entropy of the language models: a lower bound on entropy yields an upper bound on the errors incurred when embedding PRC codewords into text. In contrast, our unforgeability guarantees are independent of the errors introduced by embedding, enabling protection against false positives without imposing entropy assumptions. Moreover, our framework is compatible with any block steganography scheme, regardless of its guarantees against false positives, which allows us to achieve a watermarking scheme that is both public key robust and public key unforgeable. Finally, our approach supports recoverability without requiring access to the underlying language model or the original generation prompt. About our Hamming guarantees. Our final guarantee is a watermarking scheme for the every-block-close lifting of the Hamming predicate. We acknowledge that Hamming distance between binary token strings may not capture a wide class of watermark removal attacks. However, our general construction paradigm means any new improvement to block steganography and PPHs, e.g. improved error rates or support for different types of errors, will translate to improved unforgeable and recoverable watermarking. For example, we believe that robust signatures for a predicate we call GapEdit, which outputs 1 when the edit distance between two strings is small, 0 when it is very large, and is undefined for intermediate distances, are within reach. We expect such signatures to be attainable by instantiating our construction with a secure sketch for edit-distance [16]. Post-hoc vs. ad-hoc steganography. We leverage ad-hoc steganography, where the message is embedded into the text during generation, to encode robust signatures directly into model outputs. In contrast, post-hoc steganography schemes, such as Google’s SynthID image watermark [23], embed the message after generation. That is, the embedder first generates y←Q¯(x)y← Q(x) normally and then post-processes it to obtain y′≈y ≈ y, where a given message is embedded into y′y . Post-hoc steganography schemes cannot guarantee undetectability, but often maintain, at least empirically, that the modified content y′y is “perceptually” similar to the original response y. Robust signatures are a natural choice for the message to be embedded using a post-hoc steganography scheme. One can generate y←Q¯(x)y← Q(x), compute its robust signature σ←(,y)σ← Sign( sk,y), and embed σ into y′≈y ≈ y using a post-hoc watermarking scheme. Later, the signature can be decoded from ζ≈y′ζ≈ y and verified via robust signature verification (,ζ,σ) Ver( pk,ζ,σ). Note, however, that some robustness may be lost due to the modifications introduced during post-hoc steganography, since σ is the robust signature of the original response y, and the message ζ is close to the post-processed output y′≈y ≈ y. In this paper, we instead focus on ad-hoc steganography due to its stronger theoretical guarantees. Robust and unforgeable image watermarking. Fairoze et al. [18] argue that constructing post-hoc watermarking schemes for image models that are both robust and unforgeable may be difficult. While our work focuses on language models, our results in fact suggest the opposite conclusion under the right abstraction. In their work, they assume the existence of an embedding function g:ℝn→ℝmg:R^n ^m with m<nm<n that compresses images and preserves visual similarity: namely, that two images y,y′∈ℝny,y ^n are visually similar if and only if g(y)g(y) and g(y′)g(y ) are close under a chosen distance metric (they consider cosine distance). They show that by combining such an embedding with standard digital signatures and a post-hoc steganography scheme for images, they can construct a robust and unforgeable post-hoc watermarking scheme for image models. At a high level, their unforgeability guarantee is as follows: if a watermark is detected in an adversarially-chosen image ζ, then the embedding g(ζ)g(ζ) must be close to the embedding of some watermarked image g(y)g(y) observed by the adversary. However, they subsequently show that the assumed embedding function g may be overly idealized. In particular, they evaluate several candidate embedding functions (e.g., the forward pass of a trained deep network) and observe that these embeddings fail to satisfy the desired property. Specifically, it is easy to efficiently find images y and y′y that are visually dissimilar, yet whose embeddings g(y)g(y) and g(y′)g(y ) are close in cosine distance. As a consequence, the unforgeability guarantee becomes vacuous: even if the underlying watermarking scheme is unforgeable, an adversary can produce an image that is visually far from all watermarked images, yet still verifies as watermarked because its embedding is close to the embedding of a previously observed image. In this work, we overcome this issue for language models by leveraging PPHs. Rather than compressing text via a heuristic, similarity-preserving embedding g, we hash it using a PPH, which enables evaluating the similarity of the original texts directly (even if the hashes themselves may not be close under any distance metric). The adaptive security of PPH rules out attacks of the form outlined above. In principle, this approach also extends to post-hoc image watermarking by using a PPH instead of the embedding function g in the construction of [18, Section 5.3]. However, Hamming PPHs are not especially compelling in this setting: one could hash the binary representations of pixels of the images, but this would effectively deem two images visually similar if and only if the Hamming distance between the binary representation of their pixels is small. PPHs for ℓ2 _2-distance do exist under the recently proposed contracting hypergrid vector assumption [10], when the input space consists of bounded integer vectors. If this bound is set to 256256, then one could hash raw (unnormalized) pixel values so that two images are deemed similar iff their pixels are close in ℓ2 _2-distance. Likewise, one could hash the latent vector used to generate an image during diffusion, which is often interpreted as capturing the image’s semantic meaning. Unfortunately, such PPH constructions may not be practical, particularly when the coordinate bound is as large as 256256, highlighting the need for further improvements. 3 Watermarking definitions Notation. For strings x,y∈0,1∗x,y∈\0,1\^*, we write x⪯yx y to denote that x is a substring of y. We write (x,y)(x,y) for their concatenation and |y||y| for the length of y. We write y[i]y[i] for the iith bit of y, and y[i:j]y[i:j] for i<ji<j to denote the substring (y[i],y[i+1],…,y[j−1])(y[i],y[i+1],…,y[j-1]) (excluding the jjth bit). For q∈ℕq , we denote [q]=1,2,…,q[q]=\1,2,…,q\. For a set X, we write x←Xx← X to denote that x is a random variable sampled uniformly from X. For a (probabilistic) algorithm A and a (possibly random) input Y, we write x←(Y)x (Y) to denote that x is a random variable distributed according to the output of A when run on input Y. Let λ∈ℕλ be a security parameter. We write n=poly(λ)n=poly(λ) if n:ℕ→ℕn:N is a polynomial function. When λ is clear from context, we simply write n for n(λ)n(λ). For a function f:ℕ→ℝf:N , we write f(λ)≤negl(λ)f(λ) (λ) to indicate that f is bounded above by some negligible function. For p∈[0,1]p∈[0,1], we write (p) Ber(p) for the Bernoulli distribution on 0,1\0,1\ with expectation p. Language models. A language model Q:0,1∗→[0,1]Q:\0,1\^*→[0,1] maps a token sequence to the probability that the next token is 11. Given a prompt x∈0,1∗x∈\0,1\^*, we obtain a response u=(u[1],u[2],…)←Q¯(x)u=(u[1],u[2],…)← Q(x) by autoregressive sampling initialized with x. Formally, each bit u[j]u[j] of the response is sampled as u[j]←(Q(x,u[1:j])). u[j]← Ber (Q(x,u[1:j]) )\;. (x,u)(x,u) is a single prompt-response pair. For ℓ∈ℕ we write Q¯ℓ(x) Q_ (x) for the distribution obtained from autoregressively sampling the next ℓ bits. Transcripts. We consider adversaries that interact with oracles M by submitting inputs x∈0,1∗x∈\0,1\^* and receiving responses y∈0,1∗y∈\0,1\^*. For oracles that accept multiple inputs, x may be viewed as a concatenation of these inputs. For a (randomized) adversary A, we denote by () Trans(A M) the transcript of this interaction, i.e., the random variable describing the set of all input-output pairs observed by A. Blocks. For a string y∈0,1∗y∈\0,1\^* and a block size n∈ℕn , we define the n-bit block parsing of y as (y)=(y1,y2,…,y⌊|y|/n⌋), Blocks(y)\;=\;(y_1,y_2,…,y_ |y|/n )\,, where each yt∈0,1ny_t∈\0,1\^n is the substring y[(t−1)n+1:tn+1]y[(t-1)n+1:tn+1]. Any trailing bits that do not form a full block are discarded. For convenience, we sometimes write “an n-sized block yty_t of y”, or just yty_t when n is clear from context. In such cases, we mean: let yty_t denote the t-th entry in the sequence given by (y) Blocks(y). Predicates. We use predicates to formalize “closeness” between strings. A predicate is a Boolean-valued function Φ:→0,1 :X→\0,1\ defined on some domain X. Throughout this paper, when we quantify over predicates, we implicitly restrict to predicates that are efficiently computable. A canonical example is the Hamming predicate, which checks whether two strings differ in at most a δ-fraction of positions. Definition 3.1 (Hamming). For any δ∈[0,1]δ∈[0,1], we define the Hamming predicate δ Ham_δ as follows. For any strings y,y′∈0,1∗y,y ∈\0,1\^*, δ(y,y′)=(|y|=|y′|∧‖y−y′‖0≤δ|y|). Ham_δ(y,y )=(|y|=|y |\; \;\|y-y \|_0≤δ|y|)\;. For a predicate Φ with input domain =0,1∗×0,1∗X=\0,1\^*×\0,1\^* and strings y,y′∈0,1∗y,y ∈\0,1\^*, we say that y is Φ -close to y′y if Φ(y,y′)=1 (y,y )=1, and Φ -far from y′y if Φ(y,y′)=0 (y,y )=0. Every block close predicate. To state the guarantees of our watermarking construction, it will be useful to have in mind a notion of every-block-closeness for a predicate Φ . Intuitively, this notion lifts Φ , which originally may only compare two equal-sized strings of size n, to a predicate on sequences of blocks: it checks whether the first input is composed of consecutive n-bit blocks that are Φ -close to a sequence of consecutive n-bit blocks contained in the second input. Definition 3.2 (Every-block close). For a predicate Φ and block size n∈ℕn , we define the predicate [Φ,n] EBC[ ,n] (every-block-close) as [Φ,n](ζ∗,y):(Check that ∃r∈ℕ such that |ζ∗|=rn. Output 0 if not.Parse (ζ1∗,…,ζr∗)=(ζ∗),(y1,…,y⌊|y|/n⌋)=(y) into n-bit blocks.Output 1 iff ∃t∈ℕ such that ∀j∈[r],Φ(ζj∗,yt+j−1)=1.) EBC[ ,n](ζ^*,y):\; ( aligned &Check that ∃ r such that |ζ^*|=rn. Output 0 if not.\\ &Parse (ζ^*_1,…, _r^*)= Blocks(ζ^*),\\ &(y_1,…,y_ |y|/n )= Blocks(y) into n-bit blocks.\\ &Output 1 iff ∃ t such that ∀ j∈[r],\; (ζ^*_j,y_t+j-1)=1. aligned ) Recall Figure 2, which illustrates [Φ,n] EBC[ ,n]. The predicate [Φ,n] EBC[ ,n] is generally asymmetric: the first input ζ∗ζ^* is treated as a sequence of r consecutive n-bit blocks, while the second input y may be longer. The predicate searches for a sequence of r consecutive blocks within y that are blockwise Φ -close to ζ∗ζ^*. When ζ∗ζ^* and y have the same length, the predicate becomes symmetric (assuming Φ is symmetric) and reduces to a simple blockwise comparison, checking that their aligned blocks are Φ -close. 3.1 Watermarking We start by introducing the syntax of a watermarking scheme for a language model Q, a tuple of algorithms that act as the interface for generating and verifying watermarked outputs. We require that watermarking schemes satisfy a strong notion of quality preservation: undetectability [24]. This guarantees that watermarked outputs from Wat are indistinguishable from standard autoregressive samples from Q to any efficient adversary that can choose input prompts adaptively. Definition 3.3 (Watermarking). Let λ∈ℕλ be a security parameter. A watermarking scheme for a language model Q and token set 0,1\0,1\ is a tuple of polynomial time algorithms (,,)( Gen, Wat, Ver) satisfying, • (1λ): Gen(1^λ): takes in a security parameter λ and outputs verification and secret keys (,)( vk, sk). • (,x): Wat( sk,x): takes in the secret key sk and a prompt x∈0,1∗x∈\0,1\^* and outputs a response y∈0,1∗y∈\0,1\^*. • (,ζ): Ver( vk,ζ): takes in the verification key vk and input text ζ∈0,1∗ζ∈\0,1\^* and outputs a verification bit b∈0,1b∈\0,1\. A recoverable watermarking scheme additional requires the following PPT algorithm Rec, • (,ζ): Rec( vk,ζ): takes in the verification key vk and input text ζ∈0,1∗ζ∈\0,1\^* and outputs a list ℒ⊆0,1∗L \0,1\^* of recoveries or a failure symbol ⊥ . Undetectability For every PPT distinguisher A, |Pr(,)←(1λ)[Q,(1λ)=1]−Pr[Q,Q¯(1λ)=1]|≤negl(λ). | _( vk, sk)← Gen(1^λ) [ array[]rlA^Q, Wat_ sk(1^λ)=1 array ]- [ array[]rlA^Q, Q(1^λ)=1 array ] | (λ)\;. We now define our security notions for watermarking schemes. Throughout this section, we present the secret key variants, where the adversary has oracle access to a verification oracle Ver_ vk. In Remark 3.8, we describe the corresponding public key variants, obtained by simply giving the adversary explicit access to vk. Robustness requires that it is hard for an efficient adversary—even with access to both the watermarking oracle and the verification oracle—to produce a string ζ that contains a ℓ _ rb-sized substring ζ∗⪯ζ^* ζ which is Φ -close to one of the watermarked responses y←(,x)y← Wat( sk,x) it observed, yet for which ζ fails to verify. Definition 3.4 (Robustness). For any closeness predicate Φ and any substring size ℓ=poly(λ) _ rb=poly(λ), a watermarking scheme (,,)( Gen, Wat, Ver) is secret key (Φ,ℓ)( , _ rb)-robust if for any PPT algorithm A outputting ζ∈0,1∗ζ∈\0,1\^*, Pr[(,)←(1λ)ζ←,(1λ):(∃ζ∗⪯ζ,(x,y)∈Π such that Φ(ζ∗,y)=1∧|ζ∗|=ℓ)∧(,ζ)=0]≤negl(λ), [ array[]rl( vk, sk)&← Gen(1^λ)\\ ζ& Wat_ sk, Ver_ vk(1^λ) array: array[]rl (∃ζ^* ζ,(x,y)∈ such that \\ (ζ^*,y)=1 \;|ζ^*|= _ rb )\\ \; Ver( vk,ζ)=0 array ] (λ)\;, where Π denotes the transcript () Trans(A Wat_ sk). We include the substring requirement, |ζ∗|=ℓ|ζ^*|= _ rb, for two reasons. First, we cannot guarantee that the watermark is verifiable in arbitrarily small ζ, so this requirement imposes a lower bound on the size of ζ. Second, it allows us to capture adversaries who approximately copy a portion of their output, ζ∗ζ^*, from the watermarked model, then insert arbitrary text around it. The substring size specifies exactly how much the text must be copied for the watermark to verify, regardless of the surrounding content. Unforgeability complements robustness by requiring that it is hard for an efficient adversary to produce a string ζ that verifies as watermarked, but for which ζ contains no ℓ _ uf-sized substring ζ∗⪯ζ^* ζ that is Φ -close to any watermarked response y observed by the adversary. Another interpretation of unforgeability is that if all ℓ _ uf-sized substrings ζ∗⪯ζ^* ζ are far from all of the watermarked responses y seen by the adversary, then verification must fail. Definition 3.5 (Unforgeability). For any closeness predicate Φ and any substring size ℓ=poly(λ) _ uf=poly(λ), a watermarking scheme (,,)( Gen, Wat, Ver) is secret key (Φ,ℓ)( , _ uf)-unforgeable if for any PPT algorithm A outputting ζ∈0,1∗ζ∈\0,1\^*, Pr[(,)←(1λ)ζ←,(1λ):(,ζ)=1∧¬(∃ζ∗⪯ζ,(x,y)∈Π such that Φ(ζ∗,y)=1∧|ζ∗|=ℓ)]≤negl(λ), [ array[]rl( vk, sk)&← Gen(1^λ)\\ ζ& Wat_ sk, Ver_ vk(1^λ) array: array[]rl Ver( vk,ζ)=1\\ \; (∃ζ^* ζ,(x,y)∈ such that \\ (ζ^*,y)=1\; \;|ζ^*|= _ uf ) array ] (λ)\;, where Π denotes the transcript () Trans(A Wat_ sk). These definitions provide security for binary watermark verification. However, we may wish to go further and track the edits applied to content by recovering the original model outputs. Recoverable watermarking schemes provide exactly this capability. Robustness for a recoverable watermarking scheme requires that no efficient adversary can produce a string ζ containing a sufficiently long substring ζ∗⪯ζ^* ζ that is Φ -close to some watermarked response y, yet for which the recovery algorithm does not recover a substring of that response ξ⪯yξ y. This recovered substring ξ must also be similar to the copied ζ∗ζ^* in size (up to an allowed loss). Definition 3.6 (Robust recoverability). For any closeness predicate Φ , substring size ℓ=poly(λ) _ rec=poly(λ), and loss size ℓ=poly(λ) _ loss=poly(λ), a recoverable watermarking scheme (,,)( Gen, Wat, Rec) is secret key (Φ,ℓ,ℓ)( , _ rec, _ loss)-robust if for any PPT algorithm A outputting ζ∈0,1∗ζ∈\0,1\^*, Pr[(,)←(1λ)ζ←,(1λ)ℒ←(,ζ):(∃ζ∗⪯ζ,(x,y)∈Π such that Φ(ζ∗,y)=1∧|ζ∗|≥ℓ)∧ℒ does not contain a(|ζ∗|−ℓ)-sized substring of y]≤negl(λ), [ array[]rl( vk, sk)&← Gen(1^λ)\\ ζ& Wat_ sk, Rec_ vk(1^λ)\\ L&← Rec( vk,ζ) array: array[]rl (∃ζ^* ζ,(x,y)∈ such that \\ (ζ^*,y)=1\; \;|ζ^*|≥ _ rec )\; \\ L does not contain a\\ (|ζ^*|- _ loss)-sized substring of y array ] (λ)\;, where Π denotes the transcript () Trans(A Wat_ sk). To ensure that recoveries are reliable, it is natural to additionally require that any recovered text truly originates from the model. This requirement is especially important in applications where recovered substrings are used for fine-grained attribution. One could rely on standard unforgeability, which guarantees that whenever the recovered list (,ζ) Rec( vk,ζ) contains a string ξ, there exists some observed response y that is close to a substring ζ∗⪯ζ^* ζ. However, this does not ensure that the recovery ξ itself was genuinely observed by the adversary. Instead, we require unforgeable recoverability: no efficient adversary can produce text ζ such that (,ζ) Rec( vk,ζ) recovers a string ξ which is either too small, or is not a substring of any response y that was approximately copied by the adversary. Definition 3.7 (Unforgeable recoverability). For any closeness predicate Φ and any substring size ℓ=poly(λ) _ rec=poly(λ), a recoverable watermarking scheme (,,)( Gen, Wat, Rec) is secret key (Φ,ℓ)( , _ rec)-unforgeable if for any PPT algorithm A outputting ζ∈0,1∗ζ∈\0,1\^*, Pr[(,)←(1λ)ζ←,(1λ):∃ξ∈(,ζ) such that (|ξ|<ℓ)∨¬(∃ζ∗⪯ζ,(x,y)∈Π withΦ(ζ∗,y)=1∧|ζ∗|=|ξ|∧ξ⪯y)]≤negl(λ), [ array[]rl( vk, sk)&← Gen(1^λ)\\ ζ& Wat_ sk, Rec_ vk(1^λ) array: array[]rl∃ξ∈ Rec( vk,ζ) such that (|ξ|< _ rec )\\ \; (∃ζ^* ζ,(x,y)∈ with\\ (ζ^*,y)=1 \;|ζ^*|=|ξ|\; \;ξ y )\\ array ] (λ)\;, where Π denotes the transcript () Trans(A Wat_ sk). Remark 3.8. We presented the secret key variants of all our definitions, where the attacker receives oracle access to both Wat_ sk and Ver_ vk. We also consider the corresponding public key variants, which are identical except that the attacker additionally receives the full verification key vk (rather than only black-box access to the verification oracle). Remark 3.9. We do not include a loss term ℓ _ loss in the definition of unforgeable recoverability, because our construction guarantees the existence of a substring ζ∗⪯ζ^* ζ that has exactly the same length as the recovered string. Remark 3.10. We define standard robustness to consider fixed-size substrings |ζ∗|=ℓ|ζ^*|= _ rb, but allow variable-size substrings |ζ∗|≥ℓ|ζ^*|≥ _ rec for recoverable robustness. One could additionally define a dynamic version of standard robustness, in which verification succeeds whenever there exists a close substring ζ∗ζ^* with |ζ∗|≥ℓ|ζ^*|≥ _ rb. Our construction in fact satisfies this property. However, we include it explicitly only in the definition of recoverability for two reasons: 1. It is meaningful there, as it allows us to capture that the size of the recovered output ξ∈ℒξ scales with the size of the approximate copy ζ∗⪯ζ^* ζ. 2. Standard robustness typically implies this behavior implicitly. In particular, consider (Φ,ℓrb)( , _rb)-robustness for a predicate Φ satisfying the following: for any ζ∈0,1∗ζ∈\0,1\^* with |ζ|≥ℓ|ζ|≥ _ rb, Φ(ζ,y)=1⟹∃ζ∗⪯ζ with |ζ∗|=ℓ and Φ(ζ∗,y)=1, (ζ,y)=1 ∃ζ^* ζ with |ζ^*|= _ rb and (ζ^*,y)=1\;, Under this condition, standard robustness implies the dynamic notion of robustness. If ζ contains a substring ζ′ζ with |ζ′|>ℓ|ζ |> _ rb that is Φ -close to a response y, then by the above property there exists a further substring ζ∗⪯ζ′⪯ζ^* ζ ζ of size exactly ℓ _ rb that is also Φ -close to y. (Φ,ℓ)( , _ rb)-robustness then guarantees that verification succeeds on ζ. 4 Preliminaries Digital signatures. We recall the definition of (non-robust) digital signature schemes. Digital signature schemes allow a signer to associate a message with their publicly-verifiable signature. Parties without the signing key cannot forge valid signatures on messages that the signer has not signed. Here, we define digital signatures with strong unforgeability [8]. While standard unforgeability only prevents a forger from creating a valid signature for a new message, strong unforgeability goes further: it prevents the forger from producing a new valid signature, even for a message whose signature it has already seen. Definition 4.1 (Digital signature scheme). Let λ∈ℕλ be the security parameter, n=poly(λ)n=poly(λ) be the message size, and k=poly(λ)k=poly(λ) be the signature size. A digital signature scheme is a triple (,,)( Gen, Sign, Ver) of PPT algorithms satisfying, • (1λ): Gen(1^λ): outputs a pair of public and secret keys (,)( pk, sk). • (,y): Sign( sk,y): takes in the secret key sk and a message y∈0,1ny∈\0,1\^n and outputs a signature σ∈0,1kσ∈\0,1\^k. • (,ζ,σ): Ver( pk,ζ,σ): takes in the public key pk, a string ζ∈0,1nζ∈\0,1\^n, and a signature σ∈0,1kσ∈\0,1\^k and outputs a binary decision b∈0,1b∈\0,1\. Correctness: For any y∈0,1ny∈\0,1\^n, Pr[(,)←(1λ)σ←(,y):(,y,σ)=1]=1, [ array[]rl( pk, sk)&← Gen(1^λ)\\ σ&← Sign( sk,y) array: array[]rl Ver( pk,y,σ)=1 array ]=1\;, Strong unforgeability: For any PPT adversary A, Pr[(,)←(1λ)(ζ,σ)←():((,ζ,σ)=1)∧((ζ,σ)∉Π)]≤negl(λ), [ array[]rl( pk, sk)&← Gen(1^λ)\\ (ζ,σ)& Sign_ sk( pk) array: array[]rl ( Ver( pk,ζ,σ)=1 )\; \; ((ζ,σ)∉ ) array ] (λ)\;, where Π is the transcript () Trans(A Sign_ sk). Collision resistant hash. The sharp sketch construction of Dodis et al. [16] and property-preserving hash construction of Holmgren et al. [26] rely on the existence of collision resistant hash functions (CRHFs). We recall their definition here. Definition 4.2 (Collision resistant hash). Let λ∈ℕλ be the security parameter and let n=poly(λ)n=poly(λ) and k=poly(λ)k=poly(λ) be such that k≤nk≤ n. A collision resistant hash family (,ℋλ)( Sample,\H_λ\) consists of an efficient algorithm h←(1λ)h← Sample(1^λ) that samples a hash function h∈ℋλh _λ with h:0,1n→0,1kh:\0,1\^n→\0,1\^k. We require, Efficiency: Given x∈0,1nx∈\0,1\^n and h←(1λ)h← Sample(1^λ), the function h(x)h(x) can be computed in time poly(λ)poly(λ). Collision-resistance: For any PPT adversary A, Pr[h←(1λ)(x,x′)←(1λ,h):h(x)=h(x′)∧(x≠x′)]≤negl(λ). [ array[]rlh&← Sample(1^λ)\\ (x,x )& (1^λ,h) array: array[]rlh(x)=h(x )\\ \;(x≠ x ) array ] (λ)\;. Pseudorandom codes. Pseudorandom codes (PRCs) are error-correcting codes whose codewords are indistinguishable from random binary vectors [14]. We use ideal security (defined by Alrabiah et al. [4]), which means that even an adversary with oracle access to the encoder and decoder cannot distinguish between a PRC scheme and an “ideal” random code scheme, whose codewords are uniformly random and decoder simply responds with exact proximity queries to the underlying transcript. Ideal security thus captures both the pseudorandomness and robustness properties that PRCs are designed to achieve. PRC encoding and decoding keys. In the PRC literature, the PRC encoding and decoding keys are often referred to as “public” and “secret” keys, respectively. However, in the watermarking setting, these roles are reversed: encoding is performed by the model provider, who holds the secret watermark key, while decoding is performed by users, who hold the public key and wish to verify the watermark. To avoid confusion, we refer to the PRC keys simply as the encoding and decoding keys, denoted ek and dk, respectively. Definition 4.3 (Pseudorandom codes). Let λ∈ℕλ be a security parameter, k=poly(λ)k=poly(λ) be the message size, and n=poly(λ)n=poly(λ) be the block size. A PRC is a triple (,,)( Gen, Enc, Dec) of PPT algorithms satisfying, • (1λ): Gen(1^λ): outputs encoding and decoding keys (,)( ek, dk). • (,σ): Enc( ek,σ): takes in the encoding key ek and a message σ∈0,1kσ∈\0,1\^k and outputs a codeword y∈0,1ny∈\0,1\^n. • (,ξ): Dec( dk,ξ): takes in the decoding key dk and a string ξ∈0,1nξ∈\0,1\^n and outputs message or decoding failure σ∈0,1k∪⟂σ∈\0,1\^k∪\ \. The information rate of the PRC is kn kn. Ideal security captures the core properties that PRCs are designed to satisfy. It asserts that no PPT adversary can distinguish between a real-world interaction with the PRC and an ideal-world interaction. In the real world, the adversary interacts with the PRC encoder and decoder via oracle access. In the ideal world, the adversary receives a fresh uniformly random string for each encoding query, and the decoder maintains a complete transcript of all past encodings, decoding only those strings that are sufficiently close to previously generated ones. This notion thus captures both pseudorandomness and robustness within a single definition. It is formalized through two security games, G and G ideal. λ()G_λ(A): 1. The challenger samples (,)←.(1λ)( ek, dk)← PRC. Gen(1^λ). 2. The adversary makes encoding and decoding queries. • For each encoding query σ, the challenger responds with y←y← .(, PRC. Enc( ek, σ)σ). • For each decoding query ξ, the challenger responds with σ′←σ ← .(, PRC. Dec( dk, ξ)ξ). 3. The adversary returns a decision bit b∈0,1b∈\0,1\. δ,λ()G ideal_δ,λ(A): 1. The challenger initializes a transcript Π=∅ = . 2. The adversary makes encoding and decoding queries. • For each encoding query σ, the challenger responds with a fresh random codeword y←0,1ny←\0,1\^n and adds the entry (σ,y)(σ,y) to the transcript Π . • For each decoding query ξ, the challenger responds with a random message σ satisfying (σ,y)∈Π(σ,y)∈ for some y such that δ(y,ξ)=1 Ham_δ(y,ξ)=1. If no such σ exists, then the challenger responds with ⟂ . 3. The adversary returns a decision bit b∈0,1b∈\0,1\. Definition 4.4 (Ideal security). Let λ∈ℕλ be the security parameter and δ∈(0,12)δ∈(0, 12) be the error-rate. A pseudorandom code (,,)( Gen, Enc, Dec) is ideal with error-rate δ if, for any PPT adversary A, |Pr[λ()=1]−Pr[δ,λ()=1]|≤negl(λ). | [G_λ(A)=1 ]- [G ideal_δ,λ(A)=1 ] | (λ)\;. Alrabiah et al. [4] construct ideal pseudorandom codes with constant error rate δ∈(0,14)δ∈(0, 14) while achieving a constant information rate ρ∈(0,1)ρ∈(0,1), assuming the subexponential hardness of the exact learning parity with noise problem (LPN) [28]. Theorem 4.5 ([4, Corollary 5]). Assume the subexponential hardness of exact LPN [4, Assumption 1]. For any constant δ∈(0,14)δ∈(0, 14), there exists a constant ρ∈(0,1)ρ∈(0,1) such that there exists an ideal PRC with error-rate δ and information rate ρ+o(1)ρ+o(1). 4.1 Property-preserving hash Property preserving hash functions (PPHs) [11] allow efficient computation of a predicate Φ on two strings using only their compressed hashes, even when those inputs are chosen adversarially with full knowledge of the hash. Definition 4.6 (Property-preserving hash). Let λ∈ℕλ be the security parameter, let Φ be any predicate, and let n=poly(λ)n=poly(λ) and k=poly(λ)k=poly(λ) with k≤nk≤ n be the input and hash size respectively. A PPH scheme for Φ is a triple of PPT algorithms (,,)( Sample, Hash, Eval) satisfying • (1λ): Sample(1^λ): samples a hash function h from the family of functions ℋλH_λ. • (h,x): Hash(h,x): takes in the hash description h and a string x∈0,1nx∈\0,1\^n and outputs a hash z∈0,1kz∈\0,1\^k. • (h,z,z′): Eval(h,z,z ): takes in the hash description h and strings z,z′∈0,1kz,z ∈\0,1\^k and outputs an evaluation b∈0,1b∈\0,1\. Direct-access robustness: For any PPT adversary A, Pr[h←(1λ)(x,x′)←(1λ,h):(h,h(x),h(x′))≠Φ(x,x′)]≤negl(λ). [ array[]rlh&← Sample(1^λ)\\ (x,x )& (1^λ,h) array: Eval(h,h(x),h(x ))≠ (x,x ) ] (λ)\;. We use the notation h(x):=(h,x)h(x):= Hash(h,x). Prior works [20, 19, 26] have constructed PPHs for the Hamming predicate δ Ham_δ. In particular, assuming the existence of a special type of homomorphic CRHF, the construction of Holmgren et al. [26] achieves constant-factor compression of the input when the error rate is constant. Theorem 4.7 ([26, Corollary 6.7]). Let λ∈ℕλ be the security parameter, and let n=poly(λ)n=poly(λ) denote the input size. Suppose there exists a homomorphic CRHF with output size ℓ=ℓ(λ) = (λ) that is collision-resistant over −1,0,1n\-1,0,1\^n [26, Definition 6.1]. Then, for any constants δ∈(0,1/2)δ∈(0,1/2) and ρ>H3(δ)⋅log23ρ>H_3 BZ(δ)· _23, where H3(⋅)H_3 BZ(·) refers to the Blokh-Zyablov bound [26, Fact 2.12], there exists a PPH for δ Ham_δ with hash size ρ⋅n+ℓρ· n+ . Remark 4.8 (Blokh-Zyablov). The Blokh-Zyablov bound [9] is what best known constructions of efficiently list-decodable codes achieve [25]. It is a longstanding open problem in coding theory to match the Hamming bound H(δ)H(δ) with efficient codes. Note that log(nδn)=nH(δ)+o(n) nδ n=nH(δ)+o(n). Remark 4.9. Theorem 4.7 relies on a specialized form of homomorphic CRHF, which can be constructed under either the shortest integer solution (SIS) assumption or the discrete logarithm assumption. Later, we instantiate a slightly weaker hash family that relies on standard CRHFs, but still suffices for our purposes (Theorem 5.6). 4.2 Block steganography We use steganography as a tool in our watermarking constructions. Steganography is similar to watermarking but differs in three key respects. First, a steganography scheme enables messages to be robustly embedded in and decoded from generated text, rather than allowing only binary verification. Second, we only require correctness and robustness from steganography schemes, with no guarantees on soundness, unforgeability, or recoverability (i.e., no bound on false positives). Third, we consider block steganography, which produces a single, size n block per invocation, whereas a full watermarking scheme generates an entire response, which could be arbitrarily long. This distinction is not significant: as shown below, a block-steganography scheme can be used to autoregressively generate a full response. The block interface is simply more convenient for later constructions. Definition 4.10 (Block steganography). Let λ∈ℕλ be the security parameter, k=poly(λ)k=poly(λ) be the message size, and n=poly(λ)n=poly(λ) be the block size. A block steganography scheme for a language model Q and token set 0,1\0,1\ is a tuple of polynomial time algorithms (,,)( Gen, Embed, Dec) satisfying, • (1λ): Gen(1^λ): takes in a security parameter λ and outputs verification and secret keys (,)( vk, sk). • (,π,m): Embed( sk,π,m): takes in the secret key sk, a context π∈0,1∗π∈\0,1\^*, and a message m∈0,1km∈\0,1\^k and outputs a block y∈0,1ny∈\0,1\^n. • (,ζ): Dec( vk,ζ): takes in the verification key vk and input text ζ∈0,1nζ∈\0,1\^n and outputs a decoded message or a failure symbol m∈0,1k∪⟂m∈\0,1\^k∪\ \. Undetectability For every PPT distinguisher A, |Pr(,)←(1λ)[Q,(1λ)=1]−Pr[Q,Q¯n(1λ)=1]|≤negl(λ), | _( vk, sk)← Gen(1^λ) [ array[]rlA^Q, Embed_ sk(1^λ)=1 array ]- [ array[]rlA^Q, Q_n(1^λ)=1 array ] | (λ)\;, where both Embed_ sk and Q¯n Q_n take in contexts π∈0,1∗π∈\0,1\^* and message m∈0,1km∈\0,1\^k as input, but Q¯n Q_n ignores the message: Q¯n(π,m):=Q¯n(π) Q_n(π,m):= Q_n(π). Robustness for block steganography is similar to robustness for watermarking, but allows decoding a message m from an input ζ that is close to an embedding y of that message. Definition 4.11 (Block Robustness). For any closeness predicate Φ , a block steganography scheme (,,)( Gen, Embed, Dec) with block size n=poly(λ)n=poly(λ) is secret-key Φ -robust if for any PPT algorithm A outputting ζ∈0,1nζ∈\0,1\^n, Pr[(,)←(1λ)ζ←,(1λ):(∃(π,m,y)∈Π such thatΦ(ζ,y)=1∧(,ζ)≠m)]≤negl(λ), [ array[]rl( vk, sk)&← Gen(1^λ)\\ ζ& Embed_ sk, Dec_ vk(1^λ) array: array[]rl (∃(π,m,y)∈ such that\\ (ζ,y)=1 \; Dec( vk,ζ)≠ m ) array ] (λ)\;, where Π denotes the transcript () Trans(A Embed_ sk). Remark 4.12. Public-key Φ -robustness for block steganography is defined identically to the secret key variant, except the adversary receives the verification key vk. Robust watermarking from block steganography. Many existing watermarking schemes are explicitly or implicitly based on block steganography [14, 22, 17]. Below, we describe a simple watermarking scheme (,¯,¯)( Gen, Wat, Ver) that uses a steganography scheme (,,)( Gen, Embed, Dec) in an autoregressive manner, embedding arbitrary messages (e.g., the message 11) until a special done token signals that the model should output the string. While this scheme guarantees robustness, it does not provide unforgeability or recoverability, which are the focus of our construction in Section 6.1. Algorithm 1 ¯ Wat 1: input: (1λ,,x)(1^λ, sk,x) 2: t←1t← 1 3: y1←(,x,1)y_1← Embed( sk,x,1) 4: while ⋠yt done y_t do 5: t←t+1t← t+1 6: yt←(,(x,y1,…,yt−1),1)y_t← Embed( sk,(x,y_1,…,y_t-1),1) 7: end while 8: return y=(y1,…,yt−1,yt[<])y=(y_1,…,y_t-1,y_t[< done]) Here, we use the shorthand yt[<]y_t[< done] to denote the substring of yty_t preceding the done token. The verification algorithm then examines every substring of size n in its input ζ, and accepts if any of them decode to a message other than ⟂ . Algorithm 2 ¯ Ver 1: input: (1λ,,ζ)(1^λ, vk,ζ) 2: n←n(λ)n← n(λ) 3: for i∈[|ζ|−n+1]i∈[|ζ|-n+1] do 4: m←(,ζ[i:i+n])m← Dec( vk,ζ[i:i+n]) 5: if m≠⟂m≠ then 6: return 11 7: end if 8: end for 8: return 0 In this construction, each block yty_t of a response y←¯(,x)y← Wat( sk,x) is generated as an embedding yt←(,π,1)y_t← Embed( sk,π,1). Consequently, in ¯(,ζ) Ver( vk,ζ), as long as the input ζ contains an n-bit substring ζ∗⪯ζ^* ζ that is Φ -close to some block yty_t of a response y, the decoder (,ζ∗) Dec( vk,ζ^*) outputs 11 except with negligible probability. This, in turn, ensures that ¯(,ζ) Ver( vk,ζ) also outputs 11. Recall that this condition is captured exactly by the predicate [Φ,n](ζ∗,y) EBC[ ,n](ζ^*,y) (Definition 3.2), which, given ζ∗ζ^* of size n, outputs 1 iff it is Φ -close to a block of y. We formalize this guarantee in Fact 4.13. Fact 4.13. Let λ∈ℕλ be the security parameter, n=poly(λ)n=poly(λ) be any block size, Φ be any closeness predicate, and Q be any language model. If (,,)( Gen, Embed, Dec) is a block size n steganography scheme for Q with (secret or public key) Φ -robustness, then the watermarking scheme (,¯,¯)( Gen, Wat, Ver) for Q satisfies (secret or public key) ([Φ,n],n)( EBC[ ,n],n)-robustness. Proof. Undetectability follows immediately from the undetectability of the underlying steganography scheme. We now prove robustness for the secret key case; the public key version is analogous. Fix a PPT adversary A and a security parameter λ∈ℕλ . Let (,)←(1λ)( vk, sk)← Gen(1^λ), let ζ←¯,¯(1λ)ζ Wat_ sk, Ver_ vk(1^λ), and let Π denote the transcript (¯) Trans(A Wat_ sk). Assume, toward contradiction, that there exists a polynomial q:ℕ→ℕq:N such that Pr[(∃ζ∗⪯ζ,(x,y)∈Π such that [Φ,n](ζ∗,y)=1∧|ζ∗|=n)∧¯(,ζ)=0]≥1/q(λ). [ array[]rl (∃ζ^* ζ,(x,y)∈ such that EBC[ ,n](ζ^*,y)=1 \;|ζ^*|=n )\\ \; Ver( vk,ζ)=0 array ]≥ 1/q(λ)\;. Whenever the above event occurs, the predicate [Φ,n](ζ∗,y)=1 EBC[ ,n](ζ^*,y)=1, with |ζ∗|=n|ζ^*|=n, guarantees the existence of a block index t∈ℕt for which Φ(ζ∗,yt)=1. (ζ^*,y_t)=1\;. Because each block yty_t is produced by Embed_ sk during A’s interaction with ¯ Wat_ sk, we have (x,y)∈(¯)⇒((π=(x,y1,…,yt−1),m=1),yt)∈().(x,y)∈ Trans(A Wat_ sk)\; \; ((π=(x,y_1,…,y_t-1),\,m=1),\,y_t )∈ Trans(A Embed_ sk)\;. Yet in the same event, we also have ¯(,ζ)=0 Ver( vk,ζ)=0, which implies (,ζ∗)=⟂ Dec( vk,ζ^*)= , since failed verification guarantees that every n-bit substring of ζ decodes to ⟂ . Consequently, there exists an adversary ℬB that simulates A and outputs the substring ζ∗ζ^*, which is Φ -close to an embedding block yty_t but fails to decode with probability at least 1/q(λ)1/q(λ). This violates the Φ -block robustness of the underlying steganography scheme, yielding a contradiction. ∎ Block steganography instantiations. We present existing constructions for both secret and public key robust block steganography schemes for language models with sufficiently high entropy. Secret key block steganography from PRCs. For the secret key setting, recall PRCs, which closely resemble block steganography schemes for the uniform language model (e.g., Q(π)=1/2Q(π)=1/2 for all π∈0,1∗π∈\0,1\^*). Christ and Gunn [14] showed that PRCs can be used to build a robust watermarking scheme. However, their construction leverages standard PRCs, which achieve a weaker form of robustness, where the robustness adversary is modeled as an error channel acting independently of the encoding and decoding keys. By plugging ideal PRCs [4] (as in Definition 4.4) into their construction, we essentially obtain the adaptive guarantee that we require. A subtlety is that ideal PRCs guarantee that an input ξ decodes to a random message m whose encoding y is close to ξ, rather than the unique message m as required in block steganography. We show that this distinction is harmless: due to pseudorandomness, no efficient adversary can find any ξ that is simultaneously close to the encodings of two distinct messages. Theorem 4.14 (Secret-key block steganography from ideal PRC [14, 4]). Let λ∈ℕλ be the security parameter, let n=poly(λ)n=poly(λ) with n≥λn≥λ be any block size, and let Q be any language model with min-entropy rate at least a constant. That is, there exists a constant ϵ∈(0,14)ε∈(0, 14) such that ∀π∈0,1∗,y←Q¯ℓ(π) satisfies H∞(y)≥4(12−ϵ)n∀π∈\0,1\^*,y← Q_ (π) satisfies H_∞(y)≥ 4 ( 12-ε )n If there exists an ideal pseudorandom code with constant information rate ρ∈(0,1)ρ∈(0,1) and constant error rate δ∈(0,14)δ∈(0, 14), then there exists a block size n secret key δ−ϵ Ham_δ-ε-robust steganography scheme for Q with message size k=ρnk=ρ n. Proof. Let =(,,) PRC=( Gen, Enc, Dec) be a block size n ideal PRC, assumed to exist in the theorem. We define =(,,) Steg=( Gen, Embed, Dec), which mirrors the watermarking scheme of [14] but allows embedding messages and only outputs n-sized blocks. • .(1λ): Steg. Gen(1^λ): samples encoding and decoding keys (,)←.(1λ)( ek, dk)← PRC. Gen(1^λ) and outputs (=,=)( vk= dk, sk= ek). • .(,π,m) Steg. Embed( sk,π,m): encodes the message c←.(,m)c← PRC. Enc( sk,m) and then samples each bit of the response block y∈0,1ny∈\0,1\^n as y[i]←(pi−(−1)c[i]⋅minpi,1−pi),∀i∈[n],y[i]← Ber (p_i-(-1)^c[i]· \p_i,1-p_i\ ), ∀ i∈[n], where pi=Q(π,y[1:i])p_i=Q(π,y[1:i]) is the probability that the i-th bit should be 11 under Q. Then outputs y. • .(,ζ∈0,1n) Steg. Dec( vk,ζ∈\0,1\^n) outputs m′←.(,ζ)m ← PRC. Dec( vk,ζ). Undetectability follows from pseudorandomness of PRC [14, Lemma 19]. For robustness fix λ∈ℕλ and a PPT adversary A, and let (.,.)←.(1λ)( PRC. ek, PRC. dk)← PRC. Gen(1^λ) and ζ←,(1λ)ζ Embed_ sk, Dec_ vk(1^λ). We will show that A cannot break the Φ -block robustness of Steg. We move to a hybrid in which the oracles Embed_ sk and Dec_ vk are implemented using . PRC. Enc ideal and . PRC. Dec ideal respectively (the oracles given in the ideal PRC game 4, λ,δ()G ideal_λ,δ(A)). By the ideal security of PRC, this hybrid is computationally indistinguishable to A. Now consider the event that ζ is δ−ϵ Ham_δ-ε-close to some block y∈0,1ny∈\0,1\^n for which (π,m,y)∈(.).(π,m,y)∈ Trans(A Steg. Embed_ sk)\;. We will show that ζ decodes to m with overwhelming probability. Since Q has entropy rate at least a constant, every response y has high empirical entropy as in [14, Definition 7]. From [14, Lemma 21], y must therefore be ϵ Ham_ε-close to the PRC codeword c used to sample it with all but negligible probability. That is, with probability at least 1−negl(λ)1-negl(λ), there exists a codeword c∈0,1nc∈\0,1\^n such that (m,c)∈(.) and ϵ(y,c)=1.(m,c)∈ Trans(A PRC. Enc ideal) and Ham_ε(y,c)=1\;. (1) By the triangle inequality, ζ is δ Ham_δ-close to c. We want to argue that the ideal decoder will therefore decode ζ to the corresponding message m. However, the ideal decoder only guarantees decoding to a random message satisfying 1. We now show that m is, with overwhelming probability, the unique such message, which will conclude the argument. Since . PRC. Enc ideal generates a fresh random codeword for each input, all codewords in the transcript are, with overwhelming probability, pairwise at a Hamming distance greater than 2δn2δ n. Formally, let C=c:∃m′ with (m′,c)∈().C\;=\;\\,c:∃ m with (m ,c)∈ Trans(A Enc ideal)\,\. By Lemma 4.15 and the fact that codewords from the ideal encoder are uniformly random strings, the probability that any two distinct c,c′∈Cc,c ∈ C satisfy 2δ(c,c′)=1 Ham_2δ(c,c )=1 is negligible in n≥λn≥λ. Since |C||C| is polynomial in λ, a union bound over all pairs implies that, with negligible probability, no pair of distinct codewords in C are 2δ Ham_2δ-close. Consequently, if ζ is δ Ham_δ-close to some codeword c∈Cc∈ C, then it cannot be δ Ham_δ-close to any other codeword in C. Combining this fact with 1, we have that whenever ζ is δ−ϵ Ham_δ-ε-close to some block y encoding a message m, the ideal decoder outputs m with all but negligible probability. Since the ideal decoder is indistinguishable from . PRC. Dec_ vk to A, it follows that Steg satisfies δ−ϵ Ham_δ-ε-block robustness. ∎ The proof above relied on a simple fact, that random strings are far in Hamming distance with overwhelming probability. Lemma 4.15. Let n∈ℕn be any string length and let δ∈(0,12)δ∈(0, 12) be a fixed constant. Then Prc,c′←0,1n[δ(c,c′)=1]≤negl(n). _c,c ←\0,1\^n [ Ham_δ(c,c )=1 ] (n). Proof. For independently and uniformly random c,c′←0,1nc,c ←\0,1\^n, each coordinate differs with probability 1/21/2, so [‖c−c′‖0]=n2.E [\|c-c \|_0 ]= n2. Applying a Chernoff bound with t=1−2δ∈(0,1)t=1-2δ∈(0,1), we get Pr[‖c−c′‖0≤δn]≤exp(−n(1−2δ)24). [\|c-c \|_0≤δ n ]≤ \! (- n(1-2δ)^24 ). Since δ is a constant strictly less than 1/21/2, the exponent is a negative constant times n, and therefore the probability is negligible in n. ∎ Public key block steganography in random oracle model. Fairoze et al. [17] leverage random oracles to build a pubic key watermarking scheme. We observe that their scheme is implicitly built on top of a public key block steganography scheme, which we formalize in the following theorem. Theorem 4.16 (Public key block steganography from random oracles [17]). Let λ∈ℕλ be the security parameter, n=poly(λ)n=poly(λ) be any block size, and Q be any language model satisfying the following entropy condition: for some ℓ=poly(λ) =poly(λ), size ℓ outputs from Q have high min-entropy. That is, ∀π∈0,1∗,y←Q¯ℓ(π) satisfies H∞(y)≥ω(logλ).∀π∈\0,1\^*,y← Q_ (π) satisfies H_∞(y)≥ω( λ)\;. For simplicity, assume ℓ divides n, so that n/ℓn/ is an integer. Then there exists constants δ∈(0,12)δ∈(0, 12), ρ∈(0,1)ρ∈(0,1) where in the random oracle model, there exists a block size n public key Φδ _δ-robust block steganography scheme with message size k=ρ(n/ℓ−1)k=ρ(n/ -1), where Φδ:0,1n×0,1n→0,1 _δ:\0,1\^n×\0,1\^n→\0,1\ is the predicate Φδ(y,y′):(Parse (y1,…,yn/ℓ)=(y),(y1′,…,yn/ℓ′)=(y′) into ℓ-bit blocks,Output 1 iff y1=y1′ and for a (1−δ)-fraction of i∈2,…,n/ℓ,yi=yi′). _δ(y,y ):\; ( aligned &Parse (y_1,…,y_n/ )= Blocks(y),\;(y_1 ,…,y_n/ )= Blocks(y ) into -bit blocks,\\ &Output 1 iff y_1=y_1 and for a (1-δ)-fraction of i∈\2,…,n/ \,\;y_i=y_i aligned ). Proof. We adapt the construction of [17]. Let (,)( Enc, Dec) be an information-theoretic error-correcting code with constant rate ρ∈(0,1)ρ∈(0,1), that can correct up to a δ∈(0,12)δ∈(0, 12) fraction of errors111111Such codes exists, for example [3, 34, 38].. Let H1H_1 and H2H_2 be independent random oracles. We define a block steganography scheme =(,,) Steg=( Gen, Embed, Dec): • .(1λ): Steg. Gen(1^λ): samples r←0,1λr←\0,1\^λ and outputs ==r vk= sk=r. • .(r,π,m): Steg. Embed(r,π,m): first samples a block of ℓ bits y1←Q¯ℓ(π)y_1← Q_ (π), then computes the masked codeword c=((m)⊕H2((r,y1)))∈0,1n/ℓ−1.c= ( Enc(m) H_2 ((r,y_1) ) )∈\0,1\^n/ -1\;. The algorithm then embeds c into the next n/ℓ−1n/ -1 blocks of size ℓ by rejection-sampling. That is, yi←Q¯ℓ((π,y1,…,yi−1)) conditioned on H1((r,yi))=c[i−1],y_i← Q_ ((π,y_1,…,y_i-1) ) conditioned on H_1 ((r,y_i) )=c[i-1]\;, for i∈2,…,n/ℓi∈\2,…,n/ \. Then outputs y=(y1,…,yn/ℓ)∈0,1ny=(y_1,…,y_n/ )∈\0,1\^n. • .(r,ζ∈0,1n): Steg. Ver(r,ζ∈\0,1\^n): parses ζ=(ζ1,…,ζn/ℓ)ζ=( _1,…, _n/ ) into blocks of size ℓ , then computes =H2((r,ζ1)), and c′[i−1]=H1((r,ζi)) for i∈2,…,n/ℓ, pad=H_2 ((r, _1) ), and c [i-1]=H_1 ((r, _i) ) for i∈\2,…,n/ \, and outputs m=(c′⊕)m= Dec(c pad). Undetectability and the fact that the rejection sampling succeeds for every block with all but negligible probability follows directly from [17, Lemma 3.2]. Note that using their proof requires masking the message with the random oracle value of the first block H2((r,y1))H_2 ((r,y_1) ). To see robustness, let ζ=(ζ1,…,ζn/ℓ)←r(r)ζ=( _1,…, _n/ ) Embed_r(r), and suppose there exists (π,m,y)∈(r)(π,m,y)∈ Trans(A Embed_r) with Φδ(ζ,y)=1. _δ(ζ,y)=1. Denote (y1,…,yn/ℓ)(y_1,…,y_n/ ) as the ℓ -bit blocks of y. By definition of Φδ _δ, we have: 1. y1=ζ1y_1= _1, so the verifier (r,ζ) Ver(r,ζ) recovers the pad, =H2((r,y1)) pad=H_2 ((r,y_1) ), exactly. 2. Among the blocks (ζ2,…,ζn/ℓ)( _2,…, _n/ ), at most a δ-fraction differ from the corresponding (y2,…,yn/ℓ)(y_2,…,y_n/ ). Thus at most a δ-fraction of the bits of c′c computed by . Steg. Ver differ from the initial encoding c=(m)⊕c= Enc(m) pad. Because the error-correcting code can correct up to a δ-fraction of errors, (c′⊕)=m Dec(c pad)=m. ∎ 5 Robust and Recoverable Digital Signatures We present our formal definition of robust digital signatures, which allow verification even in the presence of small, adversarial perturbations to the message. Definition 5.1 (Robust digital signatures with strong unforgeability). Let λ∈ℕλ be the security parameter and let Φ be any predicate. A digital signature scheme (,,)( Gen, Sign, Ver) is robust and strongly unforgeable with respect to Φ if for any PPT adversary A, the scheme satisfies robustness, Pr[(,)←(1λ)(ζ,σ)←():(∃(y,σ)∈Π such that Φ(ζ,y)=1)∧(,ζ,σ)=0]≤negl(λ), [ array[]rl( pk, sk)&← Gen(1^λ)\\ (ζ,σ)& Sign_ sk( pk) array: array[]rl\; (∃(y,σ)∈ such that (ζ,y)=1 )\\ \; Ver( pk,ζ,σ)=0 array ] (λ)\;, and strong unforgeability, Pr[(,)←(1λ)(ζ,σ)←():(,ζ,σ)=1∧(∀(y,σ)∈Π,Φ(ζ,y)=0)]≤negl(λ), [ array[]rl( pk, sk)&← Gen(1^λ)\\ (ζ,σ)& Sign_ sk( pk) array: array[]rl\; Ver( pk,ζ,σ)=1\\ \; (∀(y,σ)∈ ,\; (ζ,y)=0 ) array ] (λ)\;, where Π is the transcript () Trans(A Sign_ sk). A recoverable digital signature scheme, in turn, requires a PPT recovery algorithm Rec that can recover the original message from its signature and a nearby, adversarially chosen input. For a digital signature scheme with message size n=n(λ)n=n(λ), signature size k=k(λ)k=k(λ), Rec has the syntax • (,ζ,σ): Rec( pk,ζ,σ): takes in the public key pk, a string ζ∈0,1nζ∈\0,1\^n, and a signature σ∈0,1kσ∈\0,1\^k and outputs a recovered message or a failure symbol y∈0,1n∪⊥y_ rec∈\0,1\^n∪\ \. For Rec to satisfy strong unforgeability, any recovered message y_ rec must indeed be close to the input ζ and must have been originally signed with the input signature σ. Definition 5.2 (Recoverable digital signatures). Let λ∈ℕλ be the security parameter and let Φ be any predicate. A digital signature scheme (,,)( Gen, Sign, Rec) is recoverable with respect to Φ if for any PPT adversary A, the scheme is robustly recoverable, meaning Pr[(,)←(1λ)(ζ,σ)←()y←(,ζ,σ):(∃(y,σ)∈Π such that Φ(ζ,y)=1)∧y≠y]≤negl(λ), [ array[]rl( pk, sk)&← Gen(1^λ)\\ (ζ,σ)& Sign_ sk( pk)\\ y_ rec&← Rec( pk,ζ,σ) array: array[]rl\; (∃(y,σ)∈ such that (ζ,y)=1 )\\ \;y_ rec≠ y array ] (λ)\;, and unforgeably recoverable, meaning Pr[(,)←(1λ)(ζ,σ)←()y←(,ζ,σ):y≠⟂∧((y,σ)∉Π∨Φ(ζ,y)=0)]≤negl(λ), [ array[]rl( pk, sk)&← Gen(1^λ)\\ (ζ,σ)& Sign_ sk( pk)\\ y_ rec&← Rec( pk,ζ,σ) array: array[]rl\;y_ rec≠ \\ \; \; ((y_ rec,σ)∉ \; \; (ζ,y_ rec)=0 ) array ] (λ)\;, where Π is the transcript () Trans(A Sign_ sk). Another property we introduce is a notion of uniqueness for signatures. While this property is not required for our main result, it will be useful to guarantee a certain chaining property that we present in Section 6.2. A digital signature has unique signatures if no efficient adversary can produce an output ζ and two messages (y,y′)(y,y ) with the same signature such that ζ is close to one message and far from another. Intuitively, this prevents an adversary from generating duplicate signatures on messages for which it can produce an intermediate output. Note that this property can be easily achieved by appending ω(logλ)ω( λ) random bits to each signature, to ensure all signatures are almost surely unique. However, we show that our construction inherently satisfies it. Definition 5.3 (Unique signatures). Let λ∈ℕλ be the security parameter and let Φ be any predicate. A digital signature scheme (,,)( Gen, Sign, Ver) has unique signatures with respect to Φ , if for any PPT A, Pr[(,)←(1λ)(ζ,y,y′)←():(Φ(ζ,y)=1∧Φ(ζ,y′)=0)∧(∃σ such that (y,σ)∈Π and (y′,σ)∈Π)]≤negl(λ), [ array[]rl( pk, sk)← Gen(1^λ)\\ (ζ,y,y ) Sign_ sk( pk) array: array[]rl\; ( (ζ,y)=1\; \; (ζ,y )=0 )\\ \; (∃σ such that (y,σ)∈ and (y ,σ)∈ ) array ] (λ)\;, where Π is the transcript () Trans(A Sign_ sk). 5.1 Difference-recovering hash family The core ingredient of our signature scheme is a property-preserving hashing scheme (PPH) [11]. We observe that existing Hamming PPH constructions [19, 26] support recovery of the bitwise difference Δ=x⊕x′ =x x between two close strings x and x′x using only their hashes h(x)h(x) and h(x′)h(x ). We define a slightly weaker property than this, which requires recovering the difference between two inputs when one of the inputs is given in the clear. This property is sufficient for watermarking applications, and we show that it can be achieved by any PPH for the Hamming predicate. In Section A, we define the stronger variant, which requires recovering the difference using only the hashes of both inputs. Definition 5.4 (Difference recovering PPH). For any predicate Φ , a hash family (,ℋλ)( Sample,\H_λ\) is difference-recovering w.r.t. Φ if there exists a PPT algorithm Rec such that for any PPT adversary A, Pr[h←(1λ)(x,x′)←(1λ,h)Δ←(h,h(x),x′):(Δ≠x⊕x′∧Φ(x,x′)=1)∨(Δ≠⊥∧Φ(x,x′)=0)]≤negl(λ) [ array[]rlh&← Sample(1^λ)\\ (x,x )& (1^λ,h)\\ &← Rec(h,h(x),x ) array: array[]rl ( ≠ x x (x,x )=1 )\\ \; ( ≠ (x,x )=0 ) array ] (λ) Proposition 5.5. Let λ be the security parameter. For any input size n=poly(λ)n=poly(λ) and threshold r=poly(λ)r=poly(λ) such that r<n/2r<n/2, every r/n Ham_r/n-PPH supports difference recovery w.r.t. r/n Ham_r/n. 1: input: (h,z,x′)(h,z,x ) 2: if If (h,z,h(x′))=0 Eval(h,z,h(x ))=0 then 3: return ⟂ 4: end if 5: Δ←0n ← 0^n 6: ζ←(h,z,x′)ζ← GetBoundaryPoint(h,z,x ) 7: for j∈[n]j∈[n] do 8: if (h,z,h(ζ⊕ej))=1 Eval(h,z,h(ζ e_j))=1 then 9: Δ←Δ⊕ej ← e_j 10: end if 11: end for 12: return Δ⊕x′⊕ζ x ζ Algorithm 3 Rec 1: input: (h,z,x′)(h,z,x ) 2: ζ←x′ζ← x 3: for j∈[n]j∈[n] do 4: ζ←ζ⊕ejζ←ζ e_j 5: if (h,z,h(ζ))=0 Eval(h,z,h(ζ))=0 then 6: return ζ⊕ejζ e_j 7: end if 8: end for 9: return ⊥ Algorithm 4 GetBoundaryPoint Figure 3: Generic PPH recovery algorithm Proof. Let h←(1λ)h← Sample(1^λ). We construct a recovery algorithm (h,⋅,⋅) Rec(h,·,·) which, given a hash h(x)h(x) and an input x′x in the clear, returns the difference x⊕x′x x if r/n(x,x′)=1 Ham_r/n(x,x )=1, and returns ⊥ otherwise. The recovery algorithm only needs oracle access to (h,⋅) Hash(h,·) and (h,h(x),⋅) Eval(h,h(x),·). For the reader’s convenience, we include the pseudocode for Rec in Figure 3. We may assume that (h,h(x),h(ζ))=r/n(x,ζ) Eval(h,h(x),h(ζ))= Ham_r/n(x,ζ) for all inputs ζ∈2nζ _2^n used by Rec to query (h,h(x),⋅) Eval(h,h(x),·), since Rec is an efficient deterministic algorithm. Any violation would contradict the direct-access robustness of the underlying Hamming PPH. If (h,h(x),h(x′))=0 Eval(h,h(x),h(x ))=0, then (h,h(x),x′) Rec(h,h(x),x ) returns ⊥ , which is fine since r/n(x,x′)=(h,h(x),h(x′))=0 Ham_r/n(x,x )= Eval(h,h(x),h(x ))=0. If (h,h(x),h(x′))=1 Eval(h,h(x),h(x ))=1, then (h,h(x),x′) Rec(h,h(x),x ) needs to return the difference x⊕x′x x . To this end, it first finds a boundary point relative to x. That is, a point ζ∈2nζ _2^n such that ‖x⊕ζ‖0=r\|x ζ\|_0=r. Once such a point is found, difference recovery is straightforward: since we know that ζ⊕xζ x is r-sparse, we can determine its support of the by flipping each bit of ζ individually. Specifically, for each j∈[n]j∈[n], we test whether (h,h(x),h(ζ⊕ej))=1 Eval(h,h(x),h(ζ e_j))=1, where ej∈2ne_j _2^n denotes the j-th standard basis vector (i.e., the vector with a 11 in the j-th position and zeros elsewhere). We conclude that j lies in the support of x⊕ζx ζ if and only if the evaluation remains 11 after the one-bit perturbation. We now describe an efficient procedure for finding a boundary point ζ with respect to x, given h(x)h(x) and x′x satisfying ‖x⊕x′‖0≤r\|x x \|_0≤ r. For any j∈[n]j∈[n], define uj u_j =e1⊕⋯⊕ej,ζj=x′⊕uj. =e_1 ·s e_j\;, _j=x u_j\;. Define the potential function f:0,1,…,n→0,1,…,nf:\0,1,…,n\→\0,1,…,n\ by f(j)=‖x⊕ζj‖0, f(j)=\|x _j\|_0\;, with f(0)=‖x⊕x′‖0f(0)=\|x x \|_0. Observe that for each j<nj<n, we have |f(j+1)−f(j)|=1|f(j+1)-f(j)|=1. In other words, the value of f(j)f(j) always changes by either 11 or −1-1. In addition, it holds that f(0)≤rf(0)≤ r and f(n)=n−f(0)>rf(n)=n-f(0)>r. Thus, by the discrete intermediate value property, there exists s∈0,1,…,ns∈\0,1,…,n\ such that f(s)=rf(s)=r. The corresponding ζs _s is the desired boundary point. Although Rec cannot explicitly compute f(j)f(j), it can determine whether f(j)≤rf(j)≤ r by querying (h,h(x),h(ζj)) Eval(h,h(x),h( _j)). The algorithm increments j from 11 to n, stopping at the first index where Eval returns 0. Let j be the smallest such index. Then the boundary point is ζj−1 _j-1. ∎ Difference recovery from standard CRHF. Proposition 5.5 implies that the PPH from homomorphic CRHFs given in Theorem 4.7 satisfies difference recovery with respect to δ Ham_δ. However, the converse does not hold. In particular, one can instantiate a difference recovering hash family for Hamming that does not admit an evaluation algorithm Eval for computing the predicate on two hashes, as the recovery algorithm Rec receives one of its inputs in the clear. This instantiation is heavily inspired by the notion and construction of secure sketches [16]. We refer the reader to Section B for additional details. Theorem 5.6 (Sharp sketch for Hamming, adapted from [16, Section 8.3]). Let λ∈ℕλ be the security parameter, and let n=poly(λ)n=poly(λ) denote the input size. Suppose there exists a CRHF with output size ℓ=ℓ(λ) = (λ). For any constants δ∈(0,1/2)δ∈(0,1/2) and ρ>H2(δ)ρ>H_2 BZ(δ), where H2(⋅)H_2 BZ(·) refers to the Blokh-Zyablov bound, there exists a difference recovering hash family (,)( Sample, Rec) w.r.t. δ Ham_δ that has hash size ρ⋅n+ℓρ· n+ . Remark 5.7 (Comparison with Theorem 4.7). The hash family from Theorem 5.6 requires only a standard collision-resistant hash function, not a homomorphic one. Moreover, it uses efficiently list-decodable codes over 2F_2, whereas Theorem 4.7 uses codes over 3F_3. As a result, it benefits from the Blokh-Zyablov bound over 2F_2 and avoids the multiplicative factor of log23 _23 in the hash size. However, it is not a PPH. 5.2 Robust signature from PPH We now prove a generic theorem showing that the construction presented in Section 2.1 is both robust and unforgeable with respect to Φ . In Section 5.4, we instantiate the theorem with an existing Hamming PPH [26]. We recall the construction in Figure 4. Algorithm 5 RGen 1: input: (1λ)(1^λ) 2: h←(1λ)h← Sample(1^λ) 3: (,)←(1λ)( pk, sk)← Gen(1^λ) 4: return ((h,),)((h, pk), sk) Algorithm 6 RSign 1: input: ((h,),,y)((h, pk), sk,y) 2: z←h(y)z← h(y) 3: τ←(,z)τ← Sign( sk,z) 4: return (z,τ)(z,τ) Algorithm 7 RVer 1: input: ((h,),ζ,σ)((h, pk),ζ,σ) 2: (z,τ)←σ(z,τ)←σ 3: if (,z,τ)=1 Ver( pk,z,τ)=1 then 4: b←(h,h(ζ),z)b← Eval(h,h(ζ),z) 5: return b 6: end if 7: return 0 Figure 4: Robust digital signature construction Theorem 5.8 (Generic robust signatures). Let λ∈ℕλ be the security parameter, n=poly(λ)n=poly(λ) be any message size, and Φ be any predicate. If [,,] PPH[ Sample, Hash, Eval] is a Φ -PPH with hash size k=poly(λ)k=poly(λ) and [,,] DSS[ Gen, Sign, Ver] is a strongly unforgeable digital signature scheme with signature size ℓ=poly(λ) =poly(λ), then (,,)( RGen, RSign, RVer), defined in Figure 4, is a robust and unforgeable signature scheme for Φ with signature size k+ℓk+ . Moreover, the scheme has unique signatures with respect to Φ . Proof. Robustness of RDS follows immediately from the correctness of the underlying DSS and the direct-access robustness of PPH. We focus on proving strong unforgeability. Assume for contradiction that there exists a PPT adversary A that outputs a pair (ζ,σ)(ζ,σ) such that Φ(ζ,y)=0 (ζ,y)=0 for all (y,σ)∈()(y,σ)∈ Trans(A RSign) but the pair passes RVer with non-negligible probability. That is, let (.,.)←(1λ)( RDS. pk, RDS. sk)← RGen(1^λ), (ζ,σ)←.(.)(ζ,σ) RSign_ RDS. sk( RDS. pk), and let Π denote the transcript () Trans(A RSign), where each entry logs a tuple (y,z,τ)(y,z,τ), with z=h(y)z=h(y) and τ=.(.,z)τ= DSS. Sign( DSS. pk,z). Then there exists a polynomial q:ℕ→ℕq:N such that Pr[(.,ζ,σ)=1∧∀(y,z,τ)∈Π,Φ(ζ,y)=0]>1/q(λ). [ array[]rl RVer( RDS. pk,ζ,σ)=1\\ \;∀(y,z,τ)∈ , (ζ,y)=0 array ]>1/q(λ)\;. Let E_ DSS denote the event that σ=(z,τ)σ=(z,τ) constitutes a successful forgery against DSS , and let E_ PPH denote the event that (ζ,z)(ζ,z) violates the direct-access robustness of PPH. More precisely, E E_ DSS =.(,z,τ)=1∧(⋅,z,τ)∉Π, = DSS. Ver( pk,z,τ)=1\; \;(·,z,τ) ∈ \;, E E_ PPH =(h,h(ζ),z)=1∧⋁(y,z,τ)∈ΠΦ(ζ,y)=0, = Eval(h,h(ζ),z)=1\; \; _(y,z,τ)∈ (ζ,y)=0\;, where (⋅,z,τ)∉Π(·,z,τ) ∈ is shorthand for ∄y such that (y,z,τ)∈Π ∃ y such that (y,z,τ)∈ . Since (.,ζ,σ)=.(.,z,τ)∧(h,h(ζ),z), RVer( RDS. pk,ζ,σ)= DSS. Ver( DSS. pk,z,τ) Eval(h,h(ζ),z)\;, we observe that (.,ζ,σ)=1∧(∀(y,σ) RVer( RDS. pk,ζ,σ)=1\; \;(∀(y,σ) ∈Π,Φ(ζ,y)=0)⊆E∨(E∧(⋅,z,τ)∈Π). ∈ , (ζ,y)=0) E_ DSS (E_ PPH (·,z,τ)∈ )\;. It follows that Pr[E∨(E∧(⋅,z,τ)∈Π)]>1/q(λ) [E_ DSS (E_ PPH (·,z,τ)∈ ) ]>1/q(λ). This leads to a contradiction, since both E_ DSS and E∧(⋅,z,τ)∈ΠE_ PPH (·,z,τ)∈ should occur with negligible probability due to the the strong unforgeability of DSS, and the direct-access robustness of PPH respectively. Therefore, the robust signature scheme for Φ presented in Figure 4 is strongly unforgeable. Unique signatures. Suppose, for the sake of contradiction, that there exists an adversary A and a polynomial q:ℕ→ℕq:N such that for (,)←(1λ)( pk, sk)← RGen(1^λ) and (ζ,y,y′)←()(ζ,y,y ) RSign_ sk( pk) , Pr[∃σ such that (y,σ)∈Π and (y′,σ)∈Π∧Φ(ζ,y)=1∧Φ(ζ,y′)=0]>1/q(λ), [ array[]rl\;∃σ such that (y,σ)∈ and (y ,σ)∈ \\ \; (ζ,y)=1\; \; (ζ,y )=0 array ]>1/q(λ)\;, Then A finds y and y′y such that h(y)=h(y′)h(y)=h(y ), where h is the PPH hash function, with probability at least 1/q(λ)1/q(λ), because their signatures are identical. However, this implies that either the pair (ζ,y)(ζ,y) or (ζ,y′)(ζ,y ) violates the robustness of PPH. Specifically, the evaluation algorithm Eval cannot distinguish h(y)h(y) from h(y′)h(y ), and hence .(h,h(y),h(ζ)) and .(h,h(y′),h(ζ)) PPH. Eval(h,h(y),h(ζ)) and PPH. Eval(h,h(y ),h(ζ)) will have the same output distribution, even though Φ(ζ,y)≠Φ(ζ,y′) (ζ,y)≠ (ζ,y ). Therefore, at least one of these pairs must cause Eval to output the incorrect predicate value with inverse-polynomial probability, contradicting the robustness of PPH. ∎ 5.3 Recoverable signatures from difference-recovering PPH We show that our generic construction from Theorem 5.8 is recoverable, provided the underlying PPH is difference recovering. Let (,,)( RGen, RSign, Rec) denote the scheme from Figure 4, where the verification algorithm RVer is replaced by the recovery algorithm Rec presented in Algorithm 8. The guarantees of this scheme are formally stated in Corollary 5.9. Algorithm 8 Rec 1: input: (=(h,.),ζ,σ′=(z,τ))( pk=(h, DSS. pk),ζ,σ =(z,τ)) 2: if (,ζ,σ)=0 RVer( pk,ζ,σ)=0 then 3: return ⟂ 4: end if 5: Δ←.(h,z,ζ) ← PPH. Rec(h,z,ζ) 6: return ζ⊕Δζ Corollary 5.9 (Recoverable signatures). Let Φ be any predicate. If [,,] PPH[ Sample, Hash, Rec] is difference recovering w.r.t. Φ (as in Definition 5.4) and [,,] DSS[ Gen, Sign, Ver] is a strongly unforgeable digital signature scheme, then the resulting (,,)( RGen, RSign, Rec) is a recoverable digital signature scheme w.r.t. Φ . Remark 5.10 (Recoverable signatures without PPH). Note that Corollary 5.9 can be instantiated using any difference recovering hash family, not necessarily a PPH. Although RVer, invoked by Rec, leverages PPH evaluation (h,h(ζ),z) Eval(h,h(ζ),z), this call can instead be replaced by computing Φ(ζ,.(h,z,ζ)⊕ζ) (ζ, PPH. Rec(h,z,ζ) ζ). We present the construction using Eval only because PPHs are widely studied. Proof. Let (=(h,.),)←(1λ)( pk=(h, DSS. pk), sk)← RGen(1^λ) and let ζ←()ζ Sign_ sk( pk) be the adversary’s output. Robust recovery. Suppose there exists y such that (y,σ)∈Π(y,σ)∈ and Φ(ζ,y)=1 (ζ,y)=1. By robustness of RDS, (,ζ,σ)=1 RVer( pk,ζ,σ)=1 with probability at least 1−negl(λ)1-negl(λ). Conditioned on this, σ=(h(y),⋅)σ=(h(y),·), and the difference-recovery of PPH satisfies .(h,h(y),ζ)=y⊕ζ PPH. Rec(h,h(y),ζ)=y ζ with probability at least 1−negl(λ)1-negl(λ), so the final output is y with overwhelming probability. Unforgeable recovery. Suppose (,ζ,σ)=y Rec( pk,ζ,σ)=y_ rec, with y≠⟂y_ rec≠ . Then by definition of Rec, (,ζ,σ)=1 RVer( pk,ζ,σ)=1. By strong unforgeability of RDS, with probability at least 1−negl(λ)1-negl(λ) there exists y such that (y,σ)∈Π(y,σ)∈ and Φ(ζ,y)=1 (ζ,y)=1, meaning σ=(h(y),⋅)σ=(h(y),·) corresponds to a valid signature of y. Conditioned on the above, difference-recovery of PPH yields .(h,h(y), PPH. Rec(h,h(y), ζ)ζ) =y⊕ζ=y ζ with probability at least 1−negl(λ)1-negl(λ), meaning y=ζ⊕.(h,h(y),ζ)=ζ⊕(y⊕ζ)=y,y_ rec=ζ PPH. Rec(h,h(y),ζ)=ζ (y ζ)=y, which implies that y_ rec satisfies (y,σ)∈Π(y_ rec,σ)∈ and Φ(ζ,y)=1 (ζ,y_ rec)=1. Since the intersection of both events occurs with overwhelming probability, the claim follows. ∎ 5.4 Instantiating Hamming signatures We instantiate a recoverable digital signature scheme for Hamming predicates, providing concrete trade-offs between the signature size k (relative to the message length n) and the tolerable Hamming error r. Since the regime of practical interest in watermarking corresponds to a constant error rate r/n=Ω(1)r/n= (1), we focus on the rates achievable in this setting. Here, we refer to the signature-to-message rate, k/nk/n of a RDS with signature size k, message size n. Corollary 5.11 (Recoverable digital signatures with constant error-rate). Let λ∈ℕλ be the security parameter, and suppose there exists a CRHF with output size ℓ=ℓ(λ) = (λ) and a strongly unforgeable digital signature scheme with signature size k=k(λ)k=k(λ). Let n=poly(λ)n=poly(λ) such that (ℓ+k)/n=o(1)( +k)/n=o(1) be the message size. For any constants δ∈(0,1/2)δ∈(0,1/2) and ρ>H2(δ)ρ>H_2 BZ(δ), where H2(⋅)H_2 BZ(·) denotes the Blokh–Zyablov bound, there exists a recoverable digital signature scheme (,,)( Gen, Sign, Rec) for the predicate δ Ham_δ over 0,1n\0,1\^n with signature-to-message rate ρ+o(1)ρ+o(1). Moreover, the scheme has unique signatures with respect to δ Ham_δ. Proof. We instantiate Corollary 5.9 using the difference recovering hash family from Theorem 5.6 for the predicate δ Ham_δ. The hash size is ρn+ℓρ n+ , and signing the hash incurs an additional k bits. Thus, the total signature size is ρn+ℓ+kρ n+ +k, and the resulting recoverable signature-to-message rate is (ρn+ℓ+k)/n=ρ+o(1)(ρ n+ +k)/n=ρ+o(1). ∎ Remark 5.12. We instantiate our construction using a sharp sketch (Theorem 5.6) rather than a PPH. Note that we could alternatively use the PPH from Theorem 4.7, with recoverability following from Proposition 5.5. However, using a secure sketch offers the advantage that we can achieve any constant ρ>H2(δ)ρ>H_2 BZ(δ) (rather than ρ>H3(δ)log23ρ>H_3 BZ(δ) _23), and that we can rely only on CRHFs instead of homomorphic CRHFs. We can also instantiate signatures that achieve a subconstant error rate, by using a sharp sketch and analysis along the lines of [26, Corollary 6.8]. Corollary 5.13 (Recoverable digital signatures with subconstant error-rate). Let λ∈ℕλ be the security parameter, and suppose there exists a CRHF with output size ℓ=ℓ(λ) = (λ) and a strongly unforgeable digital signature scheme with signature size k=k(λ)k=k(λ). Let n=poly(λ)n=poly(λ) be the message size. For any δ=o(1)δ=o(1), there exists a recoverable digital signature scheme (,,)( Gen, Sign, Rec) for the predicate δ Ham_δ with signature size O(δnlogn)+ℓ+kO(δ n n)+ +k. Moreover, the scheme has unique signatures with respect to δ Ham_δ. 6 Recoverable, Robust, and Unforgeable Watermarking In Section 6.1, we present our main construction, which combines block steganography with robust signatures to obtain a robust and unforgeable watermarking scheme. We then demonstrate, in Section 6.2, that our verification algorithm can be generalized by chaining across longer substrings, yielding fine-grained control over the tradeoff in substring size between robustness and unforgeability. In Section 6.3, we prove that if the underlying signature scheme is recoverable, we can build a recoverable watermarking scheme. Finally, in Section 6.4, we instantiate both secret and public key versions of our construction using existing block steganography constructions [14, 4, 17] together with our robust and recoverable digital signature instantiations (Corollaries 5.11 and 5.13). 6.1 Robust and unforgeable watermarking Theorem 6.1 summarizes the guarantees of our watermarking scheme. It has the following properties • ([Φ,n],2n)( EBC[ ,n],2n)-robustness: an (adversarially chosen) ζ verifies if it contains a substring ζ∗⪯ζ^* ζ of size 2n2n whose two blocks (ζ1∗,ζ2∗)( _1^*, _2^*) are Φ -close to two consecutive response blocks (yt,yt+1)(y_t,y_t+1). • ([Φ,n],n)( EBC[ ,n],n)-unforgeability: whenever ζ verifies, there exists an n-sized substring ζ∗⪯ζ^* ζ that is Φ -close to some response block yty_t. The parameters Φ and n are inherited from the underlying block steganography and robust signature schemes. Whether robustness is secret key or public key depends on the block steganography scheme. In contrast, unforgeability is inherited entirely from the robust signature and is therefore always public key. Compared to the basic watermarking scheme obtained directly from block steganography (Fact 4.13), our construction yields slightly weaker robustness—requiring a 2n2n-sized close substring to verify rather than an n-sized substring—but additionally provides unforgeability (and, as we show in Section 6.3, recoverability). Theorem 6.1 (Robust and unforgeable 2-block watermarking). Let λ∈ℕλ be the security parameter, and let k,n=poly(λ)k,n=poly(λ) be any message and block size, respectively. Let Φ be any closeness predicate, and Q be any language model. Suppose that: • [,,] Steg[ Gen, Embed, Dec] is a message size k, block size n block steganography scheme for Q with (secret or public key) Φ -robustness (Definition 4.11). • [,,] RDS[ Gen, Sign, Ver] is a message size n, signature size k Φ -robust digital signature scheme (Definition 5.1). Then the construction (,,)( Gen, Wat, Ver) in Figure 5 is a watermarking scheme for Q with (secret or public key) ([Φ,n],2n)( EBC[ ,n],2n)-robustness, and public key ([Φ,n],n)( EBC[ ,n],n)-unforgeability, where [Φ,n] EBC[ ,n] is defined as in Definition 3.2. We present the full details of our watermarking scheme (,,)( Gen, Wat, Ver), then prove the theorem. The construction is the same whether Steg is public or secret key, but its guarantees change. The Gen algorithm generates the watermarking and verification keys. Algorithm 9 Gen 1: input: (1λ)(1^λ) 2: .,.←.(1λ) RDS. pk, RDS. sk← RDS. Gen(1^λ) 3: .,.←.(1λ) Steg. vk, Steg. sk← Steg. Gen(1^λ) 4: =(.,.),=(.,.) vk=( RDS. pk, Steg. vk),\; sk=( RDS. sk, Steg. sk) 5: return (,)( vk, sk) Given a prompt x∈0,1∗x∈\0,1\^*, the watermarking algorithm Wat generates a response by sampling text blocks of size n=n(λ)n=n(λ) sequentially and embedding the robust signature associated with each block into the next. Algorithm 10 Wat 1: input: (1λ1^λ, sk, x) 2: k←k(λ)k← k(λ) // compute signature size k 3: σ1←0,1k _1←\0,1\^k 4: y1←.(.,x,σ1)y_1← Steg. Embed( Steg. sk,x, _1) // sample initial block with random message 5: t←1t← 1 6: while ⋠yt done y_t do 7: t←t+1t← t+1 8: σt−1←.(.,yt−1) _t-1← RDS. Sign( RDS. sk,y_t-1) // generate signature of previous block 9: yt←.(.,(x,y1,…,yt−1),σt−1)y_t← Steg. Embed( Steg. sk,(x,y_1,…,y_t-1), _t-1) // embed signature into yty_t 10: end while 11: return (y1,…,yt−1,yt[<])(y_1,…,y_t-1,y_t[< done]) // return the generated y up to the done token The verification algorithm Ver operates on arbitrary sized strings, by using Steg to recover embedded signatures and checking whether any 2n2n-sized substring in the input corresponds to a valid message-signature pair. Algorithm 11 Ver 1: input: (1λ,,ζ)(1^λ, vk,ζ) 2: n←n(λ)n← n(λ) // compute block size n 3: for i∈[|ζ|−2n+1]i∈[|ζ|-2n+1] do 4: σi←.(.,ζ[i+n:i+2n]) _i← Steg. Dec( Steg. vk,ζ[i+n:i+2n]) // attempt to decode the signature 5: if .(.,ζ[i:i+n],σi)=1 RDS. Ver( RDS. pk,ζ[i:i+n], _i)=1 then 6: return 11 // output 11 if the signature verifies with the first block 7: end if 8: end for 9: return 0 Figure 5: Pseudocode for watermarking scheme (,,)( Gen, Wat, Ver). Proof. Undetectability follows directly from the undetectability of Steg. For robustness and unforgeability, fix λ∈ℕλ and a PPT adversary A. Let (.,.)←.(1λ),(.,.)←.(1λ).( RDS. pk, RDS. sk)← RDS. Gen(1^λ), ( Steg. vk, Steg. sk)← Steg. Gen(1^λ)\;. Denote =(., vk=( RDS. pk, .) Steg. vk) and =(.,.) sk=( RDS. sk, Steg. sk). Let ζ←()ζ Wat_ sk( vk). Robustness. We prove the public key version; the secret-key version follows by an analogous argument. Suppose there exists a substring ζ∗⪯ζ^* ζ with |ζ∗|=2n|ζ^*|=2n and a prompt-response pair (x,y)∈()(x,y)∈ Trans(A Wat_ sk) such that ζ∗ζ^* is [Φ,n] EBC[ ,n]-close to y. We will show (,ζ)=1 Ver( vk,ζ)=1 with probability at least 1−negl(λ)1-negl(λ). Denote (ζ1∗,ζ2∗)=(ζ∗)(ζ^*_1,ζ^*_2)= Blocks(ζ^*). The closeness condition says that there exists a block index t∈ℕt such that Φ(ζ1∗,yt)=1 and Φ(ζ2∗,yt+1)=1. (ζ^*_1,y_t)=1 and (ζ^*_2,y_t+1)=1\;. Moreover, because yt+1y_t+1 is an n-sized block returned by Wat_ sk, and it isn’t the first block y1y_1, it has the signature of the previous block yty_t embedded in it. That is, ((π=(x,y1,…,yt),m=σt),yt+1)∈(..) ( (π=(x,y_1,…,y_t),m= _t ),y_t+1 )∈ Trans(A Steg. Embed_ Steg. sk) where σt _t is the RDS signature of yty_t computed during an oracle call to (x) Wat_ sk(x). The closeness of the second half Φ(ζ2∗,yt+1)=1 (ζ^*_2,y_t+1)=1, together with the block robustness of Steg, ensures that .(.,ζ2∗)=σt Steg. Dec( Steg. vk,ζ^*_2)= _t with probability at least 1−negl(λ)1-negl(λ). Conditioned on this event, the closeness of the first half Φ(ζ1∗,yt)=1 (ζ^*_1,y_t)=1, together with the robustness of RDS, ensures that .(,ζ1∗,σt)=1 RDS. Ver( vk,ζ^*_1, _t)=1 with probability at least 1−negl(λ)1-negl(λ). If both events occur, then (,ζ)=1 Ver( vk,ζ)=1, since it accepts if any 2n2n-substring of ζ verifies under this two-part check. Because both events occur with all but negligible probability, successful verification also occurs with all but negligible probability. Unforgeability. Let Π denote the transcript () Trans(A Wat_ sk). Suppose, towards contradiction, that there exists a polynomial q:ℕ→ℕq:N such that Pr[(,ζ)=1∧¬(∃ζ∗⪯ζ,(x,y)∈Π such that [Φ,n](ζ∗,y)=1∧|ζ∗|=n)]≥1/q(λ), [ array[]rl Ver( vk,ζ)=1\\ \; (∃ζ^* ζ,(x,y)∈ such that \\ EBC[ ,n](ζ^*,y)=1\; \;|ζ^*|=n ) array ]≥ 1/q(λ)\;, When the above event occurs, then for every substring ζ∗⪯ζ^* ζ of size n, and for every (x,y)∈()(x,y)∈ Trans(A Wat_ sk), ζ∗ζ^* is [Φ,n] EBC[ ,n]-far from y, which ensures that for every block index t∈[⌊|y|/n⌋]t∈[ |y|/n ], Φ(ζ∗,yt)=0 (ζ^*,y_t)=0. Note that the set of all such blocks yty_t subsumes the set of message for which A observed robust signatures, because the only messages that A sees signatures for during interaction with Wat_ sk are response blocks yty_t. This means that for all ζ∗⪯ζ^* ζ such that |ζ∗|=n|ζ^*|=n, and for all (y,⋅)∈(..),Φ(ζ∗,y)=0.(y,·)∈ Trans(A RDS. Sign_ RDS. sk),\; (ζ^*,y)=0. However, under the same event, (,ζ)=1 Ver( vk,ζ)=1, meaning A found some ζ∗⪯ζ^* ζ of size n and some σ∈0,1kσ∈\0,1\^k such that .(.,ζ∗,σ)=1 RDS. Ver( RDS. pk,ζ^*,σ)=1 with probability at least 1/q(λ)1/q(λ). These two facts combined contradict the unforgeability of RDS. ∎ 6.2 Generalizing verification to chains The verification algorithm for our watermarking scheme (Figure 5) applies a sliding window to ζ, checking whether any substring of size 2n2n contains a valid message–signature pair. As a result, Theorem 6.1 guarantees unforgeability with respect to substrings of size n (the size of the signed message). We can generalize this approach by using a sliding window of size rnrn for any r∈ℕr with r≥2r≥ 2. Within each rnrn-bit window, we can verify that the entire chain of r, n-bit blocks verifies back-to-back. This yields a stronger unforgeability guarantee: successful verification implies the existence of an (r−1)n(r-1)n-bit substring in ζ that is close to a consecutive chain of blocks, (yt,…,yt+r−2)(y_t,…,y_t+r-2), present in a single observed response. We formally define a family of general verification algorithms, rr∈ℕ\ Ver_r\_r , in Figure 6. Algorithm 12 r Ver_r 1: input: (,ζ)( vk,ζ) 2: n←n(λ)n← n(λ) // compute block size n 3: for i∈[|ζ|−rn+1]i∈[|ζ|-rn+1] do 4: b←r(,ζ[i:i+rn])b← ChainVer_r( vk,ζ[i:i+rn]) // verify the entire chain 5: if b=1b=1 then 6: return 11 7: end if 8: end for 9: return 0 Chain verification takes r blocks of size n as input and verifies that for each consecutive pair of blocks (ζj∗,ζj+1∗)( _j^*, _j+1^*), the signature recovered from the second block successfully verifies with the message given by the first. If any block fails verification, the entire chain is rejected. Algorithm 13 r ChainVer_r 1: input: (,ζ∗=(ζ1∗,…,ζr∗)∈0,1rn)( vk,ζ^*=( _1^*,…, _r^*)∈\0,1\^rn) 2: ←1 flag← 1 3: for j∈[r−1]j∈[r-1] do 4: σj←.(.,ζj+1∗) _j← Steg. Dec( Steg. vk,ζ^*_j+1) // attempt to decode signature 5: if .(.,ζj∗,σj)=0 RDS. Ver( RDS. pk,ζ^*_j, _j)=0 then 6: ←0 flag← 0 // if any pair fails verification, set flag to 0 7: end if 8: end for 9: return flag // indicates whether or not every block verified Figure 6: Pseudocode for chain verification. Theorem 6.2 states the guarantees obtained when instead using r Ver_r as the verifier for our construction. Its guarantees differ from those obtained using 2-block verification in two respects. First, chain verification requires that RDS has unique signatures ( Definition 5.3), though, as noted previously, this is not particularly restrictive. Second, unlike in the 2-block case, whether unforgeability holds in the public or secret key setting additionally depends on the robustness guarantees of the underlying block steganography scheme Steg. Theorem 6.2 (Robust and unforgeable r-block watermarking). Let λ∈ℕλ be the security parameter, let r=poly(λ)r=poly(λ) satisfying r≥2r≥ 2 be any chain size, and let k,n=poly(λ)k,n=poly(λ) be any message and block size, respectively. Let Φ be any closeness predicate, and Q be any language model. Suppose that: • [,,] Steg[ Gen, Embed, Dec] is a message size k, block size n block steganography scheme for Q with (secret or public key) Φ -robustness (Definition 4.11). • [,,] RDS[ Gen, Sign, Ver] is a message size n, signature size k Φ -robust digital signature scheme (Definition 5.1) that has unique signatures w.r.t. Φ (Definition 5.3). Then the construction (,,r)( Gen, Wat, Ver_r) (Figures 5 and 6) is a watermarking scheme for Q with (secret or public key) ([Φ,n],rn)( EBC[ ,n],rn)-robustness, and (secret or public key) ([Φ,n],(r−1)n)( EBC[ ,n],(r-1)n)-unforgeability. Proof. Undetectability and robustness are straightforward from the robustness and undetectability of Steg and the robustness of RDS. Therefore, we will focus on proving the unforgeability guarantee. We will prove secret key unforgeability; public key follows analogously. Fix λ∈ℕλ and a PPT adversary A. Let (.,.)←.(1λ),(.,.)←.(1λ).( RDS. pk, RDS. sk)← RDS. Gen(1^λ), ( Steg. vk, Steg. sk)← Steg. Gen(1^λ)\;. Denote =(.,.) vk=( RDS. pk, Steg. vk) and =(.,.) sk=( RDS. sk, Steg. sk). Let Π denote the transcript () Trans(A Wat_ sk) and let ζ←,(r)(1λ)ζ Wat_ sk,( Ver_r)_ vk(1^λ) We begin by showing that the event that a string ζ is [Φ,n] EBC[ ,n]-far from every response y implies a more convenient event. For a predicate Φ and an index i∈ℕi , define Φ,i(ζ,Π):=(∃ℓ∈ℕ such that |ζ|=ℓn and (i>ℓ or ∃(x,y)∈Π such that [Φ,n]((ζi,…,ζℓ),y)=1))). SuffixFormsCloseChain_ ,i(ζ, ):= ( aligned &∃ such that |ζ|= n and \\ & (i> or ∃(x,y)∈ such that \\ & EBC[ ,n] (( _i,…, _ ),\,y )=1 ) ) aligned ). (2) Given a sequence ζ=(ζ1,…,ζℓ)ζ=( _1,…, _ ) of ℓ blocks of size n, the event asserts that the suffix starting at the iith block, (ζi,…,ζℓ)( _i,…, _ ) is [Φ,n] EBC[ ,n]-close to some response y appearing in the transcript Π . When i>ℓi> , we interpret Φ,i(ζ, SuffixFormsCloseChain_ ,i(ζ, Π)=1 )=1. Now notice that if a string ζ=(ζ1,…,ζℓ)ζ=( _1,…, _ ) is [Φ,n] EBC[ ,n]-far from all responses y, then there must be a point at which the blocks of ζ transition from being close to a response chain to not. Formally, there exists an index i∈[ℓ]i∈[ ] such that the suffix (ζi+1,…,ζℓ)( _i+1,…, _ ) is close to some response, but (ζi,…,ζℓ)( _i,…, _ ) is not: (∀(x,y)∈Π,[Φ,n](ζ,y)=0) (∀(x,y)∈ , EBC[ ,n](ζ,y)=0 ) ⊆⋁i∈[ℓ](Φ,i+1(ζ,Π)∧¬Φ,i(ζ,Π)). _i∈[ ] ( SuffixFormsCloseChain_ ,i+1(ζ, )\; \; SuffixFormsCloseChain_ ,i(ζ, ) )\;. This also covers the case when no suffix of ζ is close to a response chain. In particular, if no suffix of ζ is [Φ,n] EBC[ ,n]-close to a response y, then for all i∈[ℓ]i∈[ ] we have Φ,i(ζ,Π)=0 SuffixFormsCloseChain_ ,i(ζ, )=0, so ¬Φ,i(ζ,Π)=1 SuffixFormsCloseChain_ ,i(ζ, )=1. Hence, the right-hand side still evaluates to 11 due to the i=ℓi= clause, where Φ,ℓ+1(ζ,Π)=1 SuffixFormsCloseChain_ , +1(ζ, )=1 is trivially true. Now consider i ChainForgery_i for i∈ℕi , the event that there exists a substring ζ∗⪯ζ^* ζ such that the closeness chain of all-but-the-last block of ζ∗ζ^* breaks exactly at index i, yet r ChainVer_r still accepts it. Formally, i(ζ,Π,):=(∃ζ∗⪯ζ of length rn such thatr(,ζ∗)=1,and Φ,i+1((ζ1∗,…,ζr−1∗),Π),and ¬Φ,i((ζ1∗,…,ζr−1∗),Π).). ChainForgery_i(ζ, , vk):= ( aligned &∃\,ζ^* ζ of length rn such that\\ & ChainVer_r( vk,ζ^*)=1,\\ &and SuffixFormsCloseChain_ ,i+1(( _1^*,…, _r-1^*), ),\\ &and SuffixFormsCloseChain_ ,i(( _1^*,…, _r-1^*), ). aligned ). (3) Lemma 6.3 shows that for any fixed i∈[r−1]i∈[r-1], this event occurs with probability at most negl(λ)negl(λ). Applying a union bound over all i∈[r−1]i∈[r-1] shows that the event ⋁i∈[r−1]i(ζ,Π,) _i∈[r-1] ChainForgery_i(ζ, , vk) also occurs with negligible probability. We conclude by showing that this suffices to prove unforgeability. Consider the event that an adversary successfully forges the watermark: r(,ζ)=1∧(∀ζ′⪯ζ,(x,y)∈Π,|ζ′|≠(r−1)n∨[Φ,n](ζ′,y)=0). Ver_r( vk,ζ)=1\; \; (∀\,ζ ζ,(x,y)∈ ,\;|ζ |≠(r-1)n\; \; EBC[ ,n](ζ ,y)=0 ). By definition of r Ver_r, if r(,ζ)=1 Ver_r( vk,ζ)=1, then there exists a substring ζ∗⪯ζ^* ζ of length rnrn such that r(,ζ∗)=1 ChainVer_r( vk,ζ^*)=1. Moreover, if every (r−1)n(r-1)n-sized substring ζ′⪯ζ ζ is [Φ,n] EBC[ ,n]-far from all responses, then the specific substring (ζ1∗,…,ζr−1∗)⪯ζ( _1^*,…, _r-1^*) ζ, must be far from all responses. By the previous chain-breaking argument, this implies that there exists an index i∈[r−1]i∈[r-1] where the chain breaks. Hence, the event of a successful forgery implies the event ⋁i∈[r−1]i(ζ,Π,) _i∈[r-1] ChainForgery_i(ζ, , vk), which we showed happens with negligible probability. ∎ Lemma 6.3. Let λ∈ℕλ be a security parameter, let r=poly(λ)r=poly(λ) satisfying r≥2r≥ 2 be any chain size, and let i∈[r−1]i∈[r-1] be any block index. Let (,,r)( Gen, Wat, Ver_r) be the watermarking scheme presented in Figures 5 and 6. Under the same assumptions as Theorem 6.2, for any PPT adversary A, Pr[(,)←(1λ)ζ←,(r):i(ζ,Π,)]≤negl(λ), [ array[]rl( pk, sk)&← Gen(1^λ)\\ ζ& Wat_ sk,( Ver_r)_ vk array: array[]rl ChainForgery_i(ζ, , vk) array ] (λ)\;, where Π is the transcript () Trans(A Wat_ sk) and i(ζ,Π,) ChainForgery_i(ζ, , vk) is defined as in 3. Proof. Fix λ∈ℕλ . The case i=r−1i=r-1 follows similarly to the proof of Theorem 6.1, therefore, we will prove the lemma for a fixed i∈[r−2]i∈[r-2]. Assume, toward contradiction, that there exists a polynomial q:ℕ→ℕq:N such that Pr[i(ζ,Π,)]≥1/q(λ) [ ChainForgery_i(ζ, , vk)]≥ 1/q(λ) Notice that the event i(ζ,Π,) ChainForgery_i(ζ, , vk) implies the following event, specifically for the substring (ζi∗,ζi+1∗)( _i^*, _i+1^*): (∃ζ∗⪯ζ of size 2n such that .(.,ζ1∗,.(.,ζ2∗))=1,and ∃(x,y)∈Π,t∈ℕ such that Φ(ζ2∗,yt)=1 and (Φ(ζ1∗,yt−1)=0 or t=1)). ( aligned &∃\,ζ^* ζ of size 2n such that RDS. Ver ( RDS. pk, _1^*, Steg. Dec( Steg. vk, _2^*) )=1,\\ &and ∃(x,y)∈ ,t such that ( _2^*,y_t)=1 and ( ( _1^*,y_t-1)=0 or t=1 ) aligned ). Consequently, the event above occurs with probability at least 1/q(λ)1/q(λ). Moreover, when this event occurs, the fact that Φ(ζ2∗,yt)=1 ( _2^*,y_t)=1 and the block robustness of Steg tell us that .(.,ζ2∗) Steg. Dec( Steg. vk, _2^*) decodes to the message σt−1 _t-1 embedded in yty_t with all but negligible probability. Therefore, with inverse-polynomial probability, A finds a block ζ1∗∈0,1n _1^*∈\0,1\^n and a message σt−1∈0,1k _t-1∈\0,1\^k such that (σt−1,yt)∈(..) and .(.,ζ1∗,σt−1)=1.( _t-1,y_t)∈ Trans(A Steg. Embed_ Steg. sk) and RDS. Ver( RDS. pk, _1^*, _t-1)=1\;. By definition of Wat_ sk, σt−1 _t-1 is either a uniformly random string when t=1t=1, or the robust signature of the previous block yt−1y_t-1 when t>1t>1. We analyze these two cases separately. 1. σt−1←0,1k _t-1←\0,1\^k is a uniformly random string, independent of ζ1∗ _1^*. We have that .(.,ζ1∗,σt−1)=1 RDS. Ver( RDS. pk,\, _1^*,\, _t-1)=1 with inverse-polynomial probability. But then, there exists an adversary ℬ.(.)B RDS. Sign_ sk( RDS. vk) against the strong unforgeability of RDS that simulates A and outputs ζ1∗ _1^*, along with a uniformly random string σ′←0,1kσ ←\0,1\^k. This verifies with inverse-polynomial probability, even though σ′σ is likely not any of the signatures seen by ℬB. 2. σt−1←.(.,yt−1) _t-1← RDS. Sign( RDS. sk,y_t-1) is a robust signature of the previous block. In this case, (yt−1,σt−1)∈(..).(y_t-1, _t-1)∈ Trans(A RDS. Sign_ RDS. pk). (4) However, we have that Φ(ζ1∗,yt−1)=0 ( _1^*,y_t-1)=0. Either (ζ1∗,σt−1)( _1^*, _t-1) contradicts the unforgeability of RDS, or there exists a different message m≠yt−1m≠ y_t-1 such that (m,σt−1)∈(..) and Φ(ζ1∗,m)=1.(m, _t-1)∈ Trans(A RDS. Sign_ RDS. pk) and ( _1^*,m)=1\;. This, however, breaks the unique signature property of RDS, because the adversary finds two different messages m≠yt−1m≠ y_t-1 with the same signature σt−1 _t-1, where ζ1∗ _1^* is Φ -far from yt−1y_t-1 but Φ -close to m. Thus, in the case, A either breaks unforgeability or unique signatures of RDS. In both cases, we obtain a contradiction to the security of RDS. Therefore, i(ζ,Π,) ChainForgery_i(ζ, , vk) occurs only with negligible probability. ∎ 6.3 Recoverable watermarking If the robust signature scheme RDS is recoverable, meaning it includes a recovery algorithm . RDS. Rec that can reconstruct the original message from its signature and a perturbed version of that message, then we can recover the original prefix of the errored text using Rec. Notably, Rec does not rely on the underlying language model Q or generation prompt x. Consequently, it enables users to recover original content using only the verification key and modified text. We obtain the following guarantees: • ([Φ,n],2n,n)( EBC[ ,n],2n,n)-robust recoverability: if an (adversarially chosen) ζ contains a substring ζ∗⪯ζ^* ζ of size rnrn for some r≥2r≥ 2, where the blocks (ζ1∗,…,ζr∗)(ζ^*_1,…, _r^*) are blockwise Φ -close to r consecutive response blocks (yt,…,yt+r−1)(y_t,…,y_t+r-1), then (,ζ) Rec( vk,ζ) will recover a substring of that response, ξ⪯yξ y of size (r−1)n(r-1)n. In particular, in our construction, ξ=(yt,…,yt+r−2)ξ=(y_t,…,y_t+r-2). • ([Φ,n],n)( EBC[ ,n],n)-unforgeable recoverability: if an (adversarially chosen) ζ leads to a recovery ξ∈(,ζ)ξ∈ Rec( vk,ζ) then ξ must satisfy: 1. ξ has size rnrn for some r≥1r≥ 1, 2. ξ is a substring of some close response y, i.e., ξ⪯yξ y, and there exists ζ∗⪯ζ^* ζ of size rnrn that is [Φ,n] EBC[ ,n]-close to y. In particular, in our construction, ζ∗ζ^* is [Φ,n] EBC[ ,n]-close to ξ and ξ forms chain of blocks in y. Our recovery algorithm leverages the chaining idea from the previous section to not only reconstruct individual n-bit blocks using . RDS. Rec, but to also recover multi-block prefixes when the adversary has approximately copied a chain of consecutive watermarked blocks. The idea is to apply chain recoverability—analogous to chain verification—with every window size rnrn, ensuring recovery from any long enough substring ζ∗⪯ζ^* ζ with |ζ∗|≥2n|ζ^*|≥ 2n. Algorithm 14 Rec 1: input: (,ζ)( vk,ζ) 2: n←n(λ)n← n(λ) // compute block size n 3: ℒ←∅L← 4: for r∈2,…,⌊|ζ|/n⌋r∈\2,…, |ζ|/n \ // for every chain size r do 5: for i∈[|ζ|−rn+1]i∈[|ζ|-rn+1] // for every rnrn-bit substring in the input do 6: ξ←r(,ζ[i:i+rn])ξ← ChainRec_r( vk,ζ[i:i+rn]) // attempt to recover the first r−1r-1 blocks 7: if ⟂⋠ξ ξ and |ξ|=(r−1)n|ξ|=(r-1)n then 8: ℒ←ℒ∪ξL ∪\ξ\ // only keep ξ if all r−1r-1 recoveries were successful 9: end if 10: end for 11: end for 12: return ℒL The subroutine r ChainRec_r takes in an r-block chain and attempts to recover the first r−1r-1 blocks. Algorithm 15 r ChainRec_r 1: input: (,ζ∗=(ζ1∗,…,ζr∗))( vk,ζ^*=( _1^*,…, _r^*)) 2: n←n(λ)n← n(λ) // compute block size n 3: for i∈[r−1]i∈[r-1] do 4: σj←.(.,ζj+1∗) _j← Steg. Dec( Steg. vk,ζ^*_j+1) 5: ξj←.(.,ζj∗,σj) _j← RDS. Rec( RDS. pk,ζ^*_j, _j) 6: end for 7: return ξ=(ξ1,…,ξr−1)ξ=( _1,…, _r-1) // may contain ⟂ symbols Figure 7: Pseudocode for the recovery algorithm Rec, which calls upon r ChainRec_r as a subroutine. Corollary 6.4 (Recoverable watermarking). Let λ∈ℕλ be the security parameter and let k,n=poly(λ)k,n=poly(λ) be any message and block size, respectively. Let Φ be any closeness predicate, and Q be any language model. Suppose that: • [,,] Steg[ Gen, Embed, Dec] is a message size k, block size n block steganography scheme for Q with (secret or public key) Φ -robustness (Definition 4.11). • [,,] RDS[ Gen, Sign, Ver] is a message size n, signature size k Φ -recoverable digital signature scheme (Definition 5.2) that has unique signatures w.r.t. Φ (Definition 5.3). Then the construction (,,)( Gen, Wat, Rec) in Figures 5 and 7 is a recoverable watermarking scheme with (secret or public key) ([Φ,n],2n,n)( EBC[ ,n],2n,n)-robustness and (secret or public key) ([Φ,n],n)( EBC[ ,n],n)-unforgeability. Proof. Fix λ∈ℕλ and a PPT adversary A. Let (.,.)←.(1λ),(.,.)←.(1λ).( RDS. pk, RDS. sk)← RDS. Gen(1^λ), ( Steg. vk, Steg. sk)← Steg. Gen(1^λ)\;. Denote =(.,.) vk=( RDS. pk, Steg. vk) and =(.,.) sk=( RDS. sk, Steg. sk). Let ζ←()ζ Wat_ sk( vk). We prove the public key version for both properties; the secret key version follow analogously. Robust recoverability. Suppose there exists a substring ζ∗⪯ζ^* ζ with |ζ∗|≥2n|ζ^*|≥ 2n and a pair (x,y)∈()(x,y)∈ Trans(A Wat_ sk) such that ζ∗ζ^* and y are close under [Φ,n] EBC[ ,n]. Then there exist r,t∈ℕr,t , with r≥2r≥ 2, such that |ζ∗|=rn|ζ^*|=rn and Φ(ζj∗,yt+j−1)=1,∀j∈[r]. (ζ^*_j,y_t+j-1)=1,\;∀ j∈[r]\;. Fix j∈[r−1]j∈[r-1]. As in the proof of robustness, σj←.(.,ζj+1∗) _j← Steg. Dec( Steg. vk, _j+1^*) is the signature of yt+j−1y_t+j-1 with probability at least 1−negl(λ)1-negl(λ). Since Φ(ζj∗,yt+j−1)=1 (ζ^*_j,y_t+j-1)=1, the recovery algorithm of RDS satisfies .(.,ζj∗,σj)=yt+j−1 RDS. Rec( RDS. pk, _j^*, _j)=y_t+j-1 with probability at least 1−negl(λ)1-negl(λ) . Applying a union bound over all j∈[r−1]j∈[r-1], we conclude that r(,ζ∗)=(yt,…,yt+r−2), ChainRec_r( vk,ζ^*)=(y_t,…,y_t+r-2), which is a substring of y of size |ζ∗|−n|ζ^*|-n, with all but negligible probability. Since r≤⌊|ζ|/n⌋r≤ |ζ|/n (otherwise rn>|ζ|rn>|ζ| and ζ∗ζ^* could not be a substring of ζ), (,ζ) Rec( vk,ζ) calls r(,ζ∗) ChainRec_r( vk,ζ^*) during its execution, so the chain (yt,…,yt+r−2)(y_t,…,y_t+r-2), which is an (|ζ∗|−n)(|ζ^*|-n)-sized substring of y, will be added to the final output list with all but negligible probability. Unforgeable recoverability. The proof follows similarly to the proof of unforgeable chain verification. Let Π be the transcript () Trans(A Wat_ sk). For a predicate Φ and a block index i∈ℕi , define Φ,i(ξ,Π):=(∃(x,y)∈Π,t∈ℕ such that ξj=yt+j−i,∀j∈i,…,ℓ). SuffixFormsExactChain_ ,i(ξ, ):= ( aligned &∃(x,y)∈ ,t such that \\ & _j=y_t+j-i,\;∀ j∈\i,…, \ aligned ). the event that an input string ξ∈0,1∗ξ∈\0,1\^* forms an exact chain of blocks in some response y (in contrast with SuffixFormsCloseChain 2 from the chain verification proof, which only required the input was close to a chain of blocks in some response y). Moreover, define Φ,i(ζ,ξ,Π):=(∃ℓ∈ℕ such that |ζ|=|ξ|=ℓn and(i>ℓ or([Φ,n]((ζi,…,ζℓ),(ξi,…,ξℓ))=1and Φ,i(ξ,Π)))). SuffixRecoversChain_ ,i(ζ,ξ, ):= ( aligned &∃\, such that |ζ|=|ξ|= n and\\ & (i> or\\ & ( EBC[ ,n] (( _i,…, _ ),\,( _i,…, _ ) )=1\\ &and SuffixFormsExactChain_ ,i(ξ, ) ) ) aligned ). Given two sequences ζ,ξ∈0,1ℓnζ,ξ∈\0,1\ n of ℓ blocks of size n, this event asserts that the suffix starting from the iith block (ζi,…,ζℓ)( _i,…, _ ) is blockwise Φ -close to the blocks (ξi,…,ξℓ)( _i,…, _ ), and that ξ forms of chain of blocks in some response y. When i=1i=1, this implies that ξ⪯yξ y for some response y and that ζ is [Φ,n] EBC[ ,n] close to y. Now notice that if a string ζ=(ζ1,…,ζℓ)ζ=( _1,…, _ ) and recovery ξ=(ξ1,…,ξℓ)ξ=( _1,…, _ ) do not form a recovery chain—that is, either ξ does not form a chain of blocks in some response y, or ζ is [Φ,n] EBC[ ,n]-far from ξ—then there must be some index i∈[ℓ]i∈[ ] at which the chain transitions from being a valid recovery chain to not: ([Φ,n](ζ,ξ)=0∨¬Φ,1(ξ,Π)) ( EBC[ ,n](ζ,ξ)=0\; \; SuffixFormsExactChain_ ,1(ξ, ) ) ⊆⋁i∈[ℓ](Φ,i+1(ζ,ξ,Π)∧¬Φ,i(ζ,ξ,Π)). _i∈[ ] ( SuffixRecoversChain_ ,i+1(ζ,ξ, )\; \; SuffixRecoversChain_ ,i(ζ,ξ, ) )\;. Now, for i,r∈ℕi,r , consider the event i,r ChainRecForgery_i,r: there exists a substring ζ∗⪯ζ^* ζ such that r(,ζ∗) ChainRec_r( vk,ζ^*) successfully recovers some string ξ, but for which the recovery chain between ζ∗ζ^* and ξ breaks at index i. Formally, i,r(ζ,Π,):=(∃ζ∗⪯ζ of length rn such that r(,ζ∗)=ξ with ⟂⋠ξ,and Φ,i+1((ζ1∗,…,ζr−1∗),ξ,Π),and ¬Φ,i((ζ1∗,…,ζr−1∗),ξ,Π)). ChainRecForgery_i,r(ζ, , vk):= ( aligned &∃\,ζ^* ζ of length rn such that \\ & ChainRec_r( vk,ζ^*)=ξ\; with ξ,\\ &and SuffixRecoversChain_ ,i+1(( _1^*,…, _r-1^*),ξ, ),\\ &and SuffixRecoversChain_ ,i(( _1^*,…, _r-1^*),ξ, ) aligned ). (5) Lemma 6.5 shows that for any fixed r=poly(λ)r=poly(λ) with r≥2r≥ 2 and i∈[r−1]i∈[r-1], this event occurs with probability at most negl(λ)negl(λ). Applying a union bound over all r∈2,…,⌊|ζ|/n⌋,i∈[r−1]r∈\2,…, |ζ|/n \,i∈[r-1] shows that the event ⋁i,ri,r(ζ,Π,) _i,r ChainRecForgery_i,r(ζ, , vk) also occurs with negligible probability. We conclude by showing that this suffices to prove unforgeable recoverability. Consider the event that an adversary successfully forges: ξ∈(,ζ)∧(∀ζ′⪯ζ,(x,y)∈Π,|ζ′|≠|ξ|∨ξ⋠y∨[Φ,n](ζ′,y)=0).ξ∈ Rec( vk,ζ)\; \; (∀\,ζ ζ,(x,y)∈ ,\;|ζ |≠|ξ|\; \;ξ y\; \; EBC[ ,n](ζ ,y)=0 ). By definition of Rec, if ξ∈(,ζ)ξ∈ Rec( vk,ζ), then there exists an r∈2,…,⌊|ζ|/n⌋r∈\2,…, |ζ|/n \ and substring ζ∗⪯ζ^* ζ of size rnrn where r(,ζ∗)=ξ ChainVer_r( vk,ζ^*)=ξ, ⟂⋠ξ ξ, and |ξ|=(r−1)n|ξ|=(r-1)n. Moreover, if for every |ξ||ξ|-sized substring ζ′⪯ζ ζ and every response y, either ξ⋠yξ y or ζ′ζ is [Φ,n] EBC[ ,n]-far from y, then either ζ′ζ is [Φ,n] EBC[ ,n]-far from ξ or ξ does not form a chain in any response. By the previous chain breaking argument, this means that the suffix recovery chain must break at some point for every substring ζ′ζ of size |ξ||ξ|, including the specific substring (ζ1∗,…,ζr−1∗)( _1^*,…, _r-1^*). Hence, the event of a successful forgery implies the event ⋁i,ri,r(ζ,Π,) _i,r ChainRecForgery_i,r(ζ, , vk), which we showed happens with negligible probability. ∎ Lemma 6.5. Let λ∈ℕλ be any security parameter, let r=poly(λ)r=poly(λ) satisfying r≥2r≥ 2 be any chain size, and let i∈[r−1]i∈[r-1] be any block index. Let (,,)( Gen, Wat, Rec) be the watermarking scheme presented in Figures 5 and 7. Under the same assumptions as Corollary 6.4, for any PPT adversary A, Pr[(,)←(1λ)ζ←,:i,r(ζ,Π,)]≤negl(λ), [ array[]rl( pk, sk)&← Gen(1^λ)\\ ζ& Wat_ sk, Rec_ vk array: array[]rl ChainRecForgery_i,r(ζ, , vk) array ] (λ)\;, where Π is the transcript () Trans(A Wat_ sk) and i,r(ζ,Π,) ChainRecForgery_i,r(ζ, , vk) is defined as in 5. Proof. Fix λ∈ℕλ . The case i=r−1i=r-1 is similar to the proof of Theorem 6.1, but by using the unforgeable recoverability of RDS instead of standard unforgeability. Hence, we prove the lemma for a fixed i∈[r−2]i∈[r-2]. Assume, toward contradiction, that there exists a polynomial q:ℕ→ℕq:N such that Pr[i,r(ζ,Π,)]≥1/q(λ). [ ChainRecForgery_i,r(ζ, , vk)]≥ 1/q(λ)\;. Notice that this event implies the following event, specifically for the substring (ζi∗,ζi+1∗)( _i^*, _i+1^*): (∃ζ∗⪯ζ of size 2n such that.(.,ζ1∗,.(.,ζ2∗))=ξ∈0,1n,and ∃(x,y)∈Π,t∈ℕ such thatΦ(ζ2∗,yt)=1 and (Φ(ζ1∗,ξ)=0 or ξ≠yt−1 or t=1)). ( aligned &∃\,ζ^* ζ of size 2n such that\\ & RDS. Rec ( RDS. pk, _1^*, Steg. Dec( Steg. vk, _2^*) )=ξ∈\0,1\^n,\\ &and ∃(x,y)∈ ,t such that\\ \ & ( _2^*,y_t)=1 and ( ( _1^*,ξ)=0 or ξ≠ y_t-1 or t=1 ) aligned ). (6) Consequently, the event above occurs with probability at least 1/q(λ)1/q(λ). Moreover, when this event occurs, the fact that Φ(ζ2∗,yt)=1 ( _2^*,y_t)=1 and the block-robustness of Steg tell us that .(.,ζ2∗) Steg. Dec( Steg. vk, _2^*) decodes to the message encoded in yty_t with all but negligible probability. Therefore, with inverse-polynomial probability, A finds a block ζ1∗∈0,1n _1^*∈\0,1\^n and a message σt−1∈0,1k _t-1∈\0,1\^k such that (σt−1,yt)∈(..) and .(.,ζ1∗,σt−1)=ξ∈0,1n.( _t-1,y_t)∈ Trans(A Steg. Embed_ Steg. sk) and RDS. Rec( RDS. pk, _1^*, _t-1)=ξ∈\0,1\^n\;. By definition of Wat_ sk, the value σt−1 _t-1 is either a uniformly random string when t=1t=1, or the robust signature of the previous block yt−1y_t-1 when t>1t>1. We analyze these two cases separately. 1. σt−1←0,1k _t-1←\0,1\^k is a uniformly random string. We have that .(.,ζ1∗,σt−1)≠⟂ RDS. Rec( RDS. pk,\, _1^*,\, _t-1)≠ with inverse-polynomial probability. As in the proof of chain verification, there exists an adversary against the unforgeable recovery of RDS. 2. σt−1←.(.,yt−1) _t-1← RDS. Sign( RDS. pk,y_t-1) is a robust signature of the previous block. In this case, (yt−1,σt−1)∈(..).(y_t-1, _t-1)∈ Trans(A RDS. Sign_ RDS. pk)\;. Since .(.,ζ1∗,σt−1)=ξ∈0,1n RDS. Rec( RDS. pk, _1^*, _t-1)=ξ∈\0,1\^n, it must be that (ξ,σt−1)∈(..) and Φ(ζ1∗,ξ)=1.(ξ, _t-1)∈ Trans(A RDS. Sign_ RDS. pk) and ( _1^*,ξ)=1\;. (7) with all but negligible probability; otherwise, A would break the unforgeable recoverability of RDS. Therefore, we may further condition on this event. Together event 6, which guarantees that either Φ(ζ1∗,yt−1)=0 ( _1^*,y_t-1)=0 or ξ≠yt−1ξ≠ y_t-1, and event 7, which guarantees that Φ(ζ1∗,ξ)=1 ( _1^*,ξ)=1, imply that ξ≠yt−1ξ≠ y_t-1; otherwise, ζ1∗ _1^* would be simultaneously Φ -close to and Φ -far from ξ, a contradiction. When ξ≠yt−1ξ≠ y_t-1, we have two subcases: (a) If Φ(ζ1∗,yt−1)=1 ( _1^*,y_t-1)=1, then with inverse-polynomial probability, .(, RDS. Rec( vk, ζ1∗,σt−1)≠yt−1 _1^*, _t-1)≠ y_t-1 despite the fact that (yt−1,σt−1)∈(..)(y_t-1, _t-1)∈ Trans(A RDS. Sign_ RDS. sk) and Φ(ζ1∗,yt−1)=1 ( _1^*,y_t-1)=1. This contradicts the robust recoverability of RDS. (b) If Φ(ζ1∗,yt−1)=0 ( _1^*,y_t-1)=0, then A produces (ζ1∗,ξ,yt−1)( _1^*,ξ,y_t-1) that violates the unique signature property of RDS. In both cases, we arrive at a contradiction, proving that the scheme is in fact unforgeably recoverable. ∎ 6.4 Instantiating Hamming watermarks We instantiate our watermarking scheme for high-entropy language models. In particular, we combine our RDS construction (Corollary 5.11) with an existing secret key block steganography scheme (Theorem 4.14) to obtain a watermark that is secret key recoverable, robust, and unforgeable in the presence of a constant fraction of Hamming errors. Corollary 6.6 (Concrete secret-key watermarking). Let λ∈ℕλ be the security parameter, and suppose there exists • A CRHF with output size m=m(λ)m=m(λ). • A strongly unforgeable digital signature with signature size k=k(λ)k=k(λ). • An ideal PRC with with error rate δ∈(0,14) _ PRC∈(0, 14) and information rate ρ∈(0,1)ρ∈(0,1)131313Recall that for any error-rate δ∈(0,1/4) _ PRC∈(0,1/4), there exists an ideal PRC with constant rate ρ=Ω(1)ρ= (1), assuming subexponential hardness of LPN [4, Theorem 3].. Let n=poly(λ)n=poly(λ) such that n≥λn≥λ and (m+k)/n=o(1)(m+k)/n=o(1) be the block size. Let ϵ<δε< _ PRC be any constant and let Q be any language model satisfying the following entropy condition, ∀π∈0,1∗,y←Q¯n(π) satisfies H∞(y)≥4(12−ϵ)n.∀π∈\0,1\^*,y← Q_n(π) satisfies H_∞(y)≥ 4 ( 12-ε )n\;. Let δ>0δ>0 be any constant such that δ<minδ(ρ),δ−ϵ, δ< \ _ RDS(ρ), _ PRC-ε \\;, where δ(ρ):=supδ∈(0,1/2)∣ρ>H2(δ) _ RDS(ρ):= \δ∈(0,1/2) ρ>H_2 BZ(δ)\. Then, our construction in Corollary 6.4 yields a secret key ([δ,n],2n)-robust and ([δ,n],n)-unforgeable ( EBC[ Ham_δ,n],2n )-robust and ( EBC[ Ham_δ,n],n )-unforgeable recoverable watermarking scheme for Q. Proof. From the ideal PRC assumption and Theorem 4.14, for any error rate δ≤δ−ϵδ≤ _ PRC-ε, there exists a block steganography scheme for Q with block size n, message size ρnρ n. From the CRHF and strongly unforgeable digital signature assumptions and Corollary 5.11, for any δ≤δ(ρ)δ≤ _ RDS(ρ), there exists a δ Ham_δ-recoverable digital signature scheme with message size n and signature size ρn+o(n)ρ n+o(n). We apply Theorem 6.1 and Corollary 6.4 to get the result. Note that the block steganography message size and the digital signature size differ by o(n)o(n). Our proof ignores this difference, but it could be made exact by assuming an ideal PRC with a slightly better information rate ρ′>ρ >ρ. ∎ Moreover, we leverage an existing public-key block steganography scheme (Theorem 4.16) to obtain a public-key construction that is robust to a subconstant fraction of Hamming errors, subject to the restriction that the first ℓ bits of each block are error-free, as captured by the predicate Φδ _δ defined in Theorem 4.16. Corollary 6.7 (Concrete public-key watermarking). Let λ∈ℕλ be the security parameter, and suppose there exists • A CRHF with output size m=m(λ)m=m(λ). • A strongly unforgeable digital signature with signature size k=k(λ)k=k(λ). Let Q be any language model such that for some ℓ=poly(λ) =poly(λ), ∀π∈0,1∗,y←Q¯ℓ(π) satisfies H∞(y)≥ω(logλ).∀π∈\0,1\^*,y← Q_ (π) satisfies H_∞(y)≥ω( λ)\;. Let n=poly(λ)n=poly(λ) be any block size satisfying ℓ(m+k)/n=o(1) (m+k)/n=o(1). There exists a subconstant δmax=Θ(1ℓlogn) _max= ( 1 n) such that for any δ=o(1)δ=o(1) satisfying δ(λ)≤δmax(λ)∀λ∈ℕδ(λ)≤ _max(λ)\;∀λ , there exists a public key ([Φδ,n],2n)-robust and ([δ,n],n)-unforgeable ( EBC[ _δ,n],2n )-robust and ( EBC[ Ham_δ,n],n )-unforgeable recoverable watermarking scheme for Q in the random oracle model, where Φδ _δ is defined the same as in Theorem 4.16. Proof. Fix λ∈ℕλ sufficiently large. By Theorem 4.16, in the random oracle model there exist constants ρ∈(0,1)ρ∈(0,1) and δ∗∈(0,1/2)δ^*∈(0,1/2) such that for any δ≤δ∗δ≤δ^*, there exists a public key Φδ _δ-robust block steganography scheme for Q with block size n and message size ρ(n/ℓ−1)ρ(n/ -1). Moreover, the CRHF and strongly unforgeable digital signature assumptions, Corollary 5.13 guarantees that for any δ=o(1)δ=o(1), there exists a δ Ham_δ-robust digital signature scheme with signature size O(δnlogn)+m+k≤Cδnlogn+o(n/ℓ)O(δ n n)+m+k≤ Cδ n n+o(n/ ) for some constant C>0C>0. To apply our main theorem, we require that the signature fits as a message for the block steganography scheme: Cδnlogn+o(n/ℓ)≤ρ(n/ℓ−1).Cδ n n+o(n/ )≤ρ(n/ -1)\;. This condition holds whenever δ(λ)≤δmax(λ) where δmax=ρ(n/ℓ)−ρ−o(n/ℓ)Cnlogn=Θ(1ℓlogn)δ(λ)≤ _max(λ) where _max= ρ(n/ )-ρ-o(n/ )Cn n= ( 1 n)\; Therefore, there exists a δ(λ) Ham_δ(λ)-recoverable signature scheme with message size n and signature size at most ρ(n/ℓ−1)ρ(n/ -1). Note we can adjust δmax _max so that additionally, δ(λ)≤δ∗δ(λ)≤δ^* for all λ, since δ∗δ^* is constant. Then both a Φδ _δ-robust block steganography scheme and a δ Ham_δ-recoverable signature scheme exist. Furthermore, for any strings y,y′∈0,1∗y,y ∈\0,1\^*, we have Φδ(y,y′)=1⟹δ(y,y′)=1, _δ(y,y )=1 Ham_δ(y,y )=1, because if at most δ(nℓ−1)δ ( n -1 ) blocks of size ℓ differ between inputs y and y′y , then at most δ(n−ℓ)≤δnδ(n- )≤δ n bits differ. It follows that the robust signature is also Φδ _δ-robustly recoverable. Applying Theorem 6.1 with these constructions then yields the desired result. ∎ Acknowledgements This work was supported in part by the Simons Collaboration on the Theory of Algorithmic Fairness. Part of this work was conducted while some of the authors were visiting the Simons Institute for the Theory of Computing. References [1] S. Aaronson (2022-11) My AI Safety Lecture for UT Effective Altruism. Note: https://scottaaronson.blog/?p=6823Accessed Oct 2024 Cited by: §1.2, §1.2, §1. [2] J. Achiam, S. Adler, S. Agarwal, L. Ahmad, I. Akkaya, F. L. Aleman, D. Almeida, J. Altenschmidt, S. Altman, S. Anadkat, et al. (2023) GPT-4 technical report. arXiv preprint arXiv:2303.08774. Cited by: §1. [3] N. Alon, J. Bruck, J. Naor, M. Naor, and R. M. Roth (1992) Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Transactions on information theory 38 (2), p. 509–516. Cited by: footnote 11. [4] O. Alrabiah, P. Ananth, M. Christ, Y. Dodis, and S. Gunn (2024) Ideal pseudorandom codes. arXiv preprint arXiv:2411.05947. Cited by: §1.1, §1.1, §1.2, §2.2, §2.3, §4, §4, §4.2, Theorem 4.14, Theorem 4.5, Theorem 4.5, §6, footnote 13, footnote 2. [5] M. J. Atallah, V. Raskin, M. Crogan, C. Hempelmann, F. Kerschbaum, D. Mohamed, and S. Naik (2001) Natural language watermarking: design, analysis, and a proof-of-concept implementation. In Information Hiding: 4th International Workshop, IH 2001 Pittsburgh, PA, USA, April 25–27, 2001 Proceedings 4, p. 185–200. Cited by: §1.2. [6] M. J. Atallah, V. Raskin, C. F. Hempelmann, M. Karahan, R. Sion, U. Topkara, and K. E. Triezenberg (2002) Natural language watermarking and tamperproofing. In International workshop on information hiding, p. 196–212. Cited by: §1.2. [7] C. Barrett, B. Boyd, E. Bursztein, N. Carlini, B. Chen, J. Choi, A. R. Chowdhury, M. Christodorescu, A. Datta, S. Feizi, et al. (2023) Identifying and mitigating the security risks of generative ai. Foundations and Trends® in Privacy and Security 6 (1), p. 1–52. Cited by: §1. [8] M. Bellare and S. Shoup (2007) Two-tier signatures, strongly unforgeable signatures, and fiat-shamir without random oracles. In International Workshop on Public Key Cryptography, p. 201–216. Cited by: §1.1, §1.1, §2.1, §4. [9] E. Blokh and V. V. Zyablov (1982) Linear concatenated codes. Moscow, USSR: Nauka. Cited by: Remark 4.8. [10] A. Bogdanov, A. Rosen, N. Vafa, and V. Vaikuntanathan (2025) Adaptive robustness of hypergrid johnson-lindenstrauss. arXiv preprint arXiv:2504.09331. Cited by: §1.2, §2.3. [11] E. Boyle, R. LaVigne, and V. Vaikuntanathan (2019) Adversarially robust property-preserving hash functions. 10th Innovations in Theoretical Computer Science. Cited by: §1.1, §1.1, §1.2, §4.1, §5.1. [12] C. Cachin (1998) An information-theoretic model for steganography. In International Workshop on Information Hiding, p. 306–318. Cited by: §1.2. [13] M. Christ, S. Gunn, and O. Zamir (2024) Undetectable watermarks for language models. In The Thirty Seventh Annual Conference on Learning Theory, p. 1125–1139. Cited by: §1, §1.1, §1.2, §1.2. [14] M. Christ and S. Gunn (2024) Pseudorandom error-correcting codes. In Annual International Cryptology Conference, p. 325–347. Cited by: §1, §1, §1, §1.1, §1.1, §1.2, §1.2, §1.2, §1.2, §2.2, §2.2, §2.2, §4, §4.2, §4.2, §4.2, §4.2, §4.2, Theorem 4.14, §6, footnote 2, footnote 9. [15] A. Cohen, A. Hoover, and G. Schoenbach (2024) Watermarking language models for many adaptive users. In 2025 IEEE Symposium on Security and Privacy (SP), p. 84–84. Cited by: §1.2, §1.2. [16] Y. Dodis, R. Ostrovsky, L. Reyzin, and A. Smith (2008) Fuzzy extractors: how to generate strong keys from biometrics and other noisy data. SIAM Journal on Computing 38 (1), p. 97–139. Cited by: Theorem B.2, Lemma B.4, Appendix B, Appendix B, §1.2, §1.2, §2.3, §4, §5.1, Theorem 5.6. [17] J. Fairoze, S. Garg, S. Jha, S. Mahloujifar, M. Mahmoody, and M. Wang (2025) Publicly-detectable watermarking for language models. IACR Communications in Cryptology 1 (4). Cited by: §1, §1, §1, §1.1, §1.1, §1.2, §1.2, §2.2, §2.2, §2.2, §4.2, §4.2, §4.2, §4.2, Theorem 4.16, §6, footnote 2. [18] J. Fairoze, G. Ortiz-Jimenez, M. Vecerik, S. Jha, and S. Gowal (2025) On the difficulty of constructing a robust and publicly-detectable watermark. arXiv preprint arXiv:2502.04901. Cited by: §2.3, §2.3. [19] N. Fleischhacker, K. G. Larsen, and M. Simkin (2022) Property-preserving hash functions for hamming distance from standard assumptions. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, p. 764–781. Cited by: §1.1, §1.2, §4.1, §5.1. [20] N. Fleischhacker and M. Simkin (2021) Robust property-preserving hash functions for hamming distance and more. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, p. 311–337. Cited by: §4.1. [21] S. Ghentiyala and V. Guruswami (2024) New constructions of pseudorandom codes. arXiv preprint arXiv:2409.07580. Cited by: §1.2. [22] N. Golowich and A. Moitra (2024) Edit distance robust watermarks for language models. Advances in Neural Processing Systems (NeurIPS). Cited by: §1, §1, §1.2, §1.2, §4.2. [23] S. Gowal, R. Bunel, F. Stimberg, D. Stutz, G. Ortiz-Jimenez, C. Kouridi, M. Vecerik, J. Hayes, S. Rebuffi, P. Bernard, et al. (2025) SynthID-image: image watermarking at internet scale. arXiv preprint arXiv:2510.09263. Cited by: §2.3. [24] S. Gunn, X. Zhao, and D. Song (2024) An undetectable watermark for generative image models. International Conference on Learning Representations (ICLR). Cited by: §1.2, §1.2, §1, §2.2, §3.1. [25] V. Guruswami and A. Rudra (2008) Better binary list decodable codes via multilevel concatenation. IEEE Transactions on Information Theory 55 (1), p. 19–26. Cited by: Remark 4.8. [26] J. Holmgren, M. Liu, L. Tyner, and D. Wichs (2022) Nearly optimal property preserving hashing. In Annual International Cryptology Conference (CRYPTO), p. 473–502. Cited by: Theorem A.4, Theorem A.4, Appendix A, Appendix B, §1.1, §1.1, §1.2, §4, §4.1, Theorem 4.7, Theorem 4.7, §5.1, §5.2, §5.4. [27] N. J. Hopper, J. Langford, and L. Von Ahn (2002) Provably secure steganography. In Annual International Cryptology Conference, p. 77–92. Cited by: §1.2. [28] A. Jain, S. Krenn, K. Pietrzak, and A. Tentes (2012) Commitments and efficient zero-knowledge proofs from learning parity with noise. In International Conference on the Theory and Application of Cryptology and Information Security, p. 663–680. Cited by: §1.1, §4. [29] J. Kirchenbauer, J. Geiping, Y. Wen, J. Katz, I. Miers, and T. Goldstein (2023) A watermark for large language models. In International Conference on Machine Learning, p. 17061–17084. Cited by: §1.2, §1. [30] J. Kirchenbauer, J. Geiping, Y. Wen, M. Shu, K. Saifullah, K. Kong, K. Fernando, A. Saha, M. Goldblum, and T. Goldstein (2023) On the reliability of watermarks for large language models. arXiv preprint arXiv:2306.04634. Cited by: §1.2. [31] R. Kuditipudi, J. Thickstun, T. Hashimoto, and P. Liang (2023) Robust distortion-free watermarks for language models. arXiv preprint arXiv:2307.15593. Cited by: §1.2, §1.2. [32] A. Liu, L. Pan, Y. Lu, J. Li, X. Hu, X. Zhang, L. Wen, I. King, H. Xiong, and P. Yu (2024) A survey of text watermarking in the era of large language models. ACM Computing Surveys 57 (2), p. 1–36. Cited by: §1.2. [33] S. Micali, C. Peikert, M. Sudan, and D. A. Wilson (2010) Optimal error correction for computationally bounded noise. IEEE Transactions on Information Theory 56 (11), p. 5673–5680. Cited by: §1.2. [34] J. Naor and M. Naor (1990) Small-bias probability spaces: efficient constructions and applications. In Proceedings of the twenty-second annual ACM symposium on Theory of computing, p. 213–223. Cited by: footnote 11. [35] R. Rombach, A. Blattmann, D. Lorenz, P. Esser, and B. Ommer (2022) High-resolution image synthesis with latent diffusion models. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, p. 10684–10695. Cited by: §1. [36] I. Shumailov, Z. Shumaylov, Y. Zhao, N. Papernot, R. Anderson, and Y. Gal (2024) AI models collapse when trained on recursively generated data. Nature 631 (8022), p. 755–759. Cited by: §1. [37] G. J. Simmons (1984) The prisoners’ problem and the subliminal channel. In Advances in cryptology: proceedings of crypto 83, p. 51–67. Cited by: §1.2. [38] A. Ta-Shma (2017) Explicit, almost optimal, epsilon-balanced codes. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), p. 238–251. Cited by: footnote 11. [39] M. Topkara, C. M. Taskiran, and E. J. Delp I (2005) Natural language watermarking. In Security, Steganography, and Watermarking of Multimedia Contents VII, Vol. 5681, p. 441–452. Cited by: §1.2. [40] H. Yakura, E. Lopez-Lopez, L. Brinkmann, I. Serna, P. Gupta, I. Soraperra, and I. Rahwan (2024) Empirical evidence of large language model’s influence on human spoken communication. arXiv preprint arXiv:2409.01754. Cited by: 2nd item. [41] O. Zamir (2024) Excuse me, sir? your language model is leaking (information). arXiv preprint arXiv:2401.10360. Cited by: §1.2. [42] D. Zhao (2025) Privacy-preserving hamming distance computation with property-preserving hashing. arXiv preprint arXiv:2503.17844. Cited by: §1.2. [43] X. Zhao, P. Ananth, L. Li, and Y. Wang (2023) Provable robust watermarking for ai-generated text. arXiv preprint arXiv:2306.17439. Cited by: §1.2. [44] X. Zhao, S. Gunn, M. Christ, J. Fairoze, A. Fabrega, N. Carlini, S. Garg, S. Hong, M. Nasr, F. Tramer, et al. (2024) SoK: watermarking for ai-generated content. arXiv preprint arXiv:2411.18479. Cited by: §1.2. Appendix A Strong Difference Recovery and Homomorphic PPH We notice that the PPH construction of Holmgren et al. [26], when instantiated with a homomorphic collision-resistant hash function (CRHF), satisfies two notable properties: it supports strong difference recovery and it is homomorphic. We formalize both properties and state the guarantees. Note, however, that our recoverable watermarking scheme does not rely on strong recovering or homomorphic PPHs, as the perturbed input x′x is available in the clear. Instead, the notion of sharp sketches, introduced in Section B, more accurately captures the relevant functionality. We include strong difference recovery and homomorphic PPHs here primarily for completeness. Definition A.1 (Strong difference recovering PPH). A Φ -PPH (,,)( Sample, Hash, Eval) is strong difference-recovering if there exists a PPT algorithm Rec such that for any PPT adversary A, Pr[h←(1λ)(x,x′)←(1λ,h)Δ←(h,h(x),h(x′)):(Δ≠x⊕x′∧Φ(x,x′)=1)∨(Δ≠⊥∧Φ(x,x′)=0)]≤negl(λ) [ array[]rlh&← Sample(1^λ)\\ (x,x )& (1^λ,h)\\ &← Rec(h,h(x),h(x )) array: array[]rl ( ≠ x x (x,x )=1 )\\ \; ( ≠ (x,x )=0 ) array ] (λ) Definition A.2 (Homomorphic PPH). A PPH scheme (,,)( Sample, Hash, Eval) with input size n and hash size k is said to be homomorphic if there exists a fixed abelian group (n,+)(G_n,+) and an injective map ψ:n→0,1kψ:G_n→\0,1\^k such that for every hash function representation h∈ℋh , there exists an efficiently computable141414That is, computable using poly(n)poly(n) many elementary algebraic operations. homomorphism φ:ℤn→n :Z^n _n satisfying (h,x)=ψ(φ(x))for all x∈0,1n. Hash(h,x)=ψ( (x)) all x∈\0,1\^n\;. In other words, every hash function h:0,1n→0,1kh:\0,1\^n→\0,1\^k in the family ℋH can be expressed as the composition of a homomorphism φ:ℤn→n :Z^n _n and a fixed injective embedding ψ:n→0,1kψ:G_n→\0,1\^k. Notation for homomorphic PPH. If [,,] PPH[ Sample, Hash, Eval] is homomorphic, we abuse notation and write h(x)−h(x′)=h(x−x′)h(x)-h(x )=h(x-x ) for any h∈ℋh and x,x′∈0,1nx,x ∈\0,1\^n, where subtraction is interpreted over ℤnZ^n (so that x−x′∈−1,0,1nx-x ∈\-1,0,1\^n) and h(x)h(x) refers to the group element φ(x)∈n (x) _n (i.e., before applying the embedding ψ into 0,1k\0,1\^k). Definition A.3 (Sparsity testing). A homomorphic PPH scheme (,,)( Sample, Hash, Eval) is said to support sparsity testing if there exists an algorithm SparseEval such that for all h∈ℋh and x,x′∈0,1nx,x ∈\0,1\^n, (h,h(x),h(x′)) Eval(h,h(x),h(x )) =(h,h(x)−h(x′)) = SparseEval(h,h(x)-h(x )) =(h,h(Δ)), = SparseEval(h,h( ))\;, where Δ=x−x′∈−1,0,1n =x-x ∈\-1,0,1\^n, and the final equality follows from the homomorphic property. In other words, if a homomorphic PPH supports sparsity testing, then its evaluation algorithm Eval depends only on the hash function h and the difference h(x)−h(x′)=h(x−x′)h(x)-h(x )=h(x-x ), rather than on the individual hash values. Specifically, Eval returns 11 if the difference Δ is sparse, and 0 otherwise. Holmgren et al.’s homomorphic PPH goes further by supporting sparse recovery: if Δ is sparse, then given only (h,h(Δ))(h,h( )), their recovery algorithm Rec outputs Δ∈−1,0,1n ∈\-1,0,1\^n exactly. Note that this recovers only the difference vector, not the preimages x or x′x . Theorem A.4 ([26, Corollary 6.7]). Let λ∈ℕλ be the security parameter, and let n=poly(λ)n=poly(λ) denote the input size. Suppose there exists a homomorphic CRHF with output size ℓ=ℓ(λ) = (λ) that is collision-resistant over −1,0,1n\-1,0,1\^n [26, Definition 6.1]. Then, for any constants δ∈(0,1/2)δ∈(0,1/2) and ρ>H3(δ)⋅log23ρ>H_3 BZ(δ)· _23, where H3(⋅)H_3 BZ(·) refers to the Blokh-Zyablov bound [26, Fact 2.12], there exists a strongly recoverable homomorphic PPH over the input domain 0,1n\0,1\^n for δ Ham_δ with hash size ρ⋅n+ℓρ· n+ . Appendix B Sharp Sketches and Lower Bounds A sharp sketch is a cryptographic primitive that enables efficient recovery given auxiliary input x′x in the clear. The goal is to reconstruct an input x from its sketch g(x)g(x) and a candidate x′x that is sufficiently close to it. Its defining feature is sharpness: (g,g(x),x′) Rec(g,g(x),x ) must output ⊥ if x′x is far from x. This notion is inspired by the secure sketches of Dodis et al. [16], but differs in both purpose and security guarantees. Secure sketches require unconditional hardness of inversion: it must be hard to recover x from its sketch g(x)g(x), even for an unbounded adversary. This necessitates a non-trivial compression rate ρ=k/nρ=k/n, so secure sketches are compressive by definition. Their recoverability guarantee is also unconditional, requiring recovery to succeed for every x′x that is close to x. In contrast, sharp sketches enforce a different notion of security, one not centered on inversion. They require that no computationally-bounded adversary can produce input pairs (x,x′)(x,x ) that violate the sharp recoverability condition (see Definition B.1). Thus, compressiveness is not required by definition. Even the identity sketch g(x)=xg(x)=x qualifies as a (trivial) sharp sketch, though it would not qualify as a secure sketch. On the other hand, any secure sketch can be converted into a sharp sketch by returning ⊥ whenever x^=(g,g(x),x′) x= Rec(g,g(x),x ) is either inconsistent g(x)≠g(x^)g(x)≠ g( x) or far from x′x . Sharp sketch constructions for Hamming predicates were given by Dodis et al. [16, Section 8.3]. We include it here for completeness and to enable precise reference in our watermarking scheme, where it plays a key role. Our main technical contribution is a generalization of the lower bound by Holmgren et al. [26], extending it from Hamming predicates to any predicate Φ that satisfies an efficient sampleability condition (Theorem B.5). When specialized to the Hamming case, our bound implies that the construction of Dodis et al. achieves nearly optimal sketch size, since the gap between the Hamming bound H(δ)H(δ) and the Blokh-Zyablov bound H2(δ)H_2 BZ(δ) is small (see also Remark 4.8). This shows that the recoverable digital signature in Corollary 5.11 is nearly optimal compared to constructions based on the generic PPH/sharp sketch transformation of Section 5.2. Definition B.1 (Sharp sketch). Let λ∈ℕλ be the security parameter, let Φ be any predicate, and let n=n(λ)n=n(λ) and k=k(λ)k=k(λ) be such that k≤nk≤ n. A sharp sketching scheme for Φ with input size n and sketch size k is a triple of PPT algorithms (,,)( Sample, Sketch, Rec) defined as follows: • (1λ) Sample(1^λ): samples a sketching function g from a family of functions λG_λ. • (g,x) Sketch(g,x): takes in x∈0,1nx∈\0,1\^n and outputs its sketch g(x)∈0,1kg(x)∈\0,1\^k. • (g,z,x′) Rec(g,z,x ): takes in z∈0,1kz∈\0,1\^k and x′∈0,1nx ∈\0,1\^n, and returns an output in 0,1n∪⊥\0,1\^n∪\ \. The scheme satisfies the following security guarantee: Sharp recoverability: For any PPT adversary A, Pr[g←(1λ);(x,x′)←(1λ,g):((g,g(x),x′)≠x∧Φ(x,x′)=1)∨((g,g(x),x′)≠⊥∧Φ(x,x′)=0)]≤negl(λ). [ array[]rlg&← Sample(1^λ);\\ (x,x )& (1^λ,g) array: array[]rl ( Rec(g,g(x),x )≠ x\; \; (x,x )=1 )\\ \; ( Rec(g,g(x),x )≠ \; \; (x,x )=0 ) array ] (λ)\;. We restate Theorem 5.6, which gave a difference recovery hash family for Hamming from CRHFs, in the language of sharp sketches. Theorem B.2 (Sharp sketch for Hamming, adapted from [16, Section 8.3]). Let λ∈ℕλ be the security parameter, and let n=n(λ)n=n(λ) denote the input size. Suppose there exists a CRHF with output size ℓ=ℓ(λ) = (λ). For any constants δ∈(0,1/2)δ∈(0,1/2) and ρ>H2(δ)ρ>H_2 BZ(δ), where H2(⋅)H_2 BZ(·) refers to the Blokh-Zyablov bound, there exists a sharp sketching scheme (,,)( Sample, Sketch, Rec) over 0,1n\0,1\^n for δ Ham_δ with sketch size ρ⋅n+ℓρ· n+ . Remark B.3 (PPH and sharp sketch). By Proposition 5.5, every Hamming PPH yields a sharp sketch for the same predicate. However, the converse does not hold. For instance, the sharp sketching scheme in Theorem 5.6 does not give rise to a Hamming PPH, as it crucially relies on receiving x′x in the clear, rather than just its sketch. Note, however, that our recoverable digital signature algorithm (Section 5.3) does receive one input in the clear, and therefore sharp sketches suffice. Lemma B.4 ([16], Lemma 2.2). For random variables X,Y,ZX,Y,Z, where Y is supported over a set of size k, we have H∞(X|Y,Z)≥H∞(X|Z)−logkH_∞(X|Y,Z)≥ H_∞(X|Z)- k Theorem B.5 (Sharp sketch lower bound). Let Φ any predicate and let A⊆(x,x′)∈0,1n×0,1n:Φ(x,x′)=1A \(x,x )∈\0,1\^n×\0,1\^n: (x,x )=1\ be such that the uniform distribution U over pairs (x,x′)(x,x ) conditioned on A is efficiently sampleable. Then the sketch size of any sharp sketch for Φ is at least n+log(A). n+ (A)\;. Proof. Let X be uniformly distributed over 0,1n\0,1\^n, and let g:0,1n→0,1kg:\0,1\^n→\0,1\^k be a sharp sketch drawn independently of X. Then the min-entropy of X conditioned on h and g(X)g(X), which we denote by H∞(X∣h,g(X))H_∞(X h,g(X)), satisfies: H∞(X∣g,g(X))≥H∞(X∣g)−k≥n−k. H_∞(X g,g(X))≥ H_∞(X g)-k≥ n-k\;. In particular, no (even unbounded) adversary can “invert” (g,g(X))(g,g(X)) to recover the original input X with probability greater than 2−(n−k)2^-(n-k) when X is drawn uniformly from 0,1n\0,1\^n. Now consider the following inversion strategy based on (g,g(x),⋅) Rec(g,g(x),·). Define a randomized algorithm Inv that, on input (g,g(x))(g,g(x)), samples a fresh x′←0,1nx ←\0,1\^n and outputs (g,g(x),x′) Rec(g,g(x),x ). Let μ be the distribution of (x,x′)(x,x ) sampled uniformly from 0,12n\0,1\^2n conditioned on the event A. By assumption, (x,x′)∈A(x,x )∈ A implies Φ(x,x′)=1 (x,x )=1. Since μ is efficiently sampleable and Φ(x,x′)=1 (x,x )=1, guarantees of the sharp sketch g yield Pr[g←(1λ)(x,x′)←μ:(g,g(x),x′)=x]≥1−negl(λ). [ array[]rlg&← Sample(1^λ)\\ (x,x )&←μ array: Rec(g,g(x),x )=x ]≥ 1-negl(λ)\;. Using the above recovery guarantee, we lower bound the success probability of Inv as follows. Pr [g←(1λ)x←0,1n:(g,g(x))=x] [ array[]rlg&← Sample(1^λ)\\ x&←\0,1\^n array:\; Inv(g,g(x))=x ] ≥Pr[g←(1λ)(x,x′)←0,12n:(g,g(x),x′)=x|A]⋅(A) ≥ [ array[]rlg&← Sample(1^λ)\\ (x,x )&←\0,1\^2n array: array[]rl Rec(g,g(x),x )=x\; |\;A array ]·U(A) ≥(1−negl(λ))⋅(A). ≥(1-negl(λ))·U(A)\;. But from the earlier information-theoretic bound, no function g with output size k can support inversion with success probability greater than 2−(n−k)2^-(n-k). Hence, we conclude 2−(n−k)≥(A)⋅(1−negl(λ)), 2^-(n-k) (A)·(1-negl(λ))\;, For sufficiently large λ, we have negl(λ)<1/2negl(λ)<1/2, which implies k≥n+log(A). k≥ n+ (A)\;. ∎ Claim B.6. Let r=r(n)r=r(n) be any efficiently computable function. Then, the uniform distribution U over pairs (x,x′)∈0,1n×0,1n(x,x )∈\0,1\^n×\0,1\^n conditioned on ‖x−x′‖0=r\|x-x \|_0=r is efficiently sampleable. Proof. First, sample x←0,1nx←\0,1\^n uniformly at random. Then sample an r-sparse perturbation vector Δ∈0,1n ∈\0,1\^n independently of x. Finally, set x′=x⊕Δx =x . ∎ Corollary B.7. Let r=r(n)r=r(n) be any efficiently computable function. Then, for all sufficiently large n, the sketch size of any sharp sketching scheme for r/n Ham_r/n is at least log(nr) nr.