Pith. sign in

REVIEW 2 major objections 5 minor 2 cited by

On the Difficulty of Constructing a Robust and Publicly-Detectable Watermark

T0 review · 2 major / 5 minor · reviewed 2026-08-08 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A robust, unforgeable, publicly-detectable image watermark is provably possible by composing signatures, post-hoc watermarks, and collision-resistant embeddings; the paper shows current embeddings fail the needed collision resistance.

desk verdict The framework and empirical evaluation are worth a look, but the central composition theorem is not proven as written. read the letter →

arxiv 2502.04901 v2 pith:VIWVKJ5O submitted 2025-02-07 cs.CR cs.LG

Jaiden Fairoze , Guillermo Ortiz-Jimenez , Mel Vecerik , Somesh Jha , Sven Gowal This is my paper · ORCID
classification cs.CRcs.LG
keywords imagewatermarkingpublicly-detectableunforgeabilityrobustembeddingspost-hocadversarialrobustnesscontentprovenancecollisionresistance
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Platforms and users need to know whether an image is authentic even after it has been cropped, recompressed, or lightly edited, and ideally anyone, not just a watermark vendor, should be able to check it. This paper asks whether a single watermark can be unforgeable, robust to natural transformations, and publicly detectable, and answers that such a scheme is provably possible if three building blocks exist. The construction signs an embedding of the image, then hides the signature and embedding inside the image with a post-hoc watermark; detection decodes the payload and checks both signature and embedding similarity. Unforgeability reduces to the signature's security and to the embedding's collision resistance, and the paper shows that this collision resistance is exactly what current image-embedding models lack: mild adversarial perturbations destroy their similarity comparisons. The result is a precise blueprint for a robust public watermark whose only missing component is an adversarially robust embedding.

What carries the argument

The load-bearing object is the robust embedding function of Definition B.1: an embedding model with correctness (transformed copies compare as similar) and collision resistance (no white-box adversary can make an arbitrary image compare as similar to a signed image). Around it, the paper wraps a post-hoc watermarking scheme, which acts as a high-capacity communication channel hidden in the image, and a cryptographic signature scheme, which makes the embedded payload unforgeable. The composition's central identity is the payload equation $c \geq \delta + n$: the watermark capacity must fit the signature plus the embedding. The detection predicate is the conjunction of signature verification and embedding comparison, so the scheme inherits robustness from both primitives and security from their individual guarantees.

What would settle it

Run the paper's own white-box PGD collision attack against any candidate robust embedding: if an adversary can, within an $\ell_\infty$ budget of $4/255$ (or any imperceptible bound), make two visually different images compare as similar with non-negligible probability, the collision-resistance premise behind unforgeability fails. The paper already reports this collapse for the SSCD model (ROC AUC drops from 0.986 to 0.057); a model that keeps near-perfect ROC AUC under the same attack would remove the stated barrier and make the construction deployable.

Watch

Extended reading notes

Core claim

The paper's central claim is that a robust, unforgeable, and publicly-detectable watermarking scheme exists, and it proves this by construction (Theorem 5.1). Starting from a robust embedding function $(\mathrm{Embed}, \mathrm{Compare})$, a post-hoc watermarking scheme $(\mathrm{Encode}, \mathrm{Decode})$, and a cryptographic signature scheme $(\mathrm{Sign}, \mathrm{Verify})$, the watermark embeds the image $x$ as $e = \mathrm{Embed}(x)$, signs $e$ to obtain $\sigma$, and produces $\mathrm{Encode}(x, \sigma \| e)$. To detect, one decodes $\sigma' \| e'$, checks $\mathrm{Verify}(pk, e', \sigma')$, and checks $\mathrm{Compare}(\mathrm{Embed}(x'), e')$. The theorem states that if the embedding and watermark share transformation robustness and the watermark capacity satisfies $c \geq \delta + n$, the composed scheme is a $(\mathcal{T}_{\mathrm{REF}} \cap \mathcal{T}_{\mathrm{PGWS}},\ \epsilon_{\mathrm{REF}}+\epsilon_{\mathrm{PGWS}}+\mathrm{negl}(\lambda))$-publicly-detectable watermark, robust to the transformations common to both primitives and unforgeable unless either the signature is forged or the embedding collides. Empirically, the paper finds the embedding half of this condition currently fails: all evaluated models, including the best ones, are broken by standard white-box PGD attacks, so the theorem is a blueprint whose load-bearing primitive does not yet exist.

Load-bearing premise

The load-bearing premise is that a robust embedding function exists whose similarity comparisons cannot be fooled by a white-box adversary, meaning no one without the secret key can slightly modify an image so its embedding matches a signed embedding of a different image; the paper's own experiments show every evaluated model violates this today.

Editorial extensions

If this is right

  • If a collision-resistant robust embedding is ever built, the paper's construction immediately yields a watermark that is unforgeable, robust to transformations shared by the embedding and the watermark, and verifiable by anyone with the public key.
  • The same composition applies to any high-entropy data supporting post-hoc watermarking and robust embeddings, such as audio and video.
  • With current models the embedding primitive fails the required collision-resistance, so the practical bottleneck is adversarial robustness rather than signature size or watermark capacity.
  • A valid instantiation would inherit the imperceptibility of the underlying post-hoc watermark, including its PSNR and SSIM values.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • An implication the authors leave implicit is that any deep-learning component in a public detector faces the same white-box attack surface, so alternative public watermark designs must either solve embedding collision resistance or avoid differentiable components entirely.
  • The paper's observed correlation between embedding accuracy and attack resistance suggests a concrete research target: track collision resistance under fixed PGD attacks as a standard benchmark, since adversarial robustness may arrive with better perception rather than dedicated defenses.
  • The same construction could serve as an adversarially robust perceptual hash, giving progress on collision-resistant embeddings applications in content moderation and copy detection beyond watermarking.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper asks whether an image watermark can simultaneously be robust to natural transformations, unforgeable, and publicly detectable. It introduces formal definitions for robust embedding functions, post-hoc watermarking schemes, and robust publicly-detectable watermarking schemes; describes a warmup LSB-based scheme; and states a composition theorem (Theorem 5.1) claiming that any secure robust embedding, post-hoc watermark, and signature scheme, with suitable parameters, yield a robust, unforgeable, and publicly-detectable watermark. The paper then empirically evaluates several state-of-the-art image embedding models under white-box PGD attacks and reports that none of them currently satisfies the required collision-resistance property, concluding that the construction is theoretically possible but not yet practically deployable.

Significance. If the composition theorem were established, the paper would provide a clean modular reduction: robustness from a robust embedding and post-hoc watermark, unforgeability from collision resistance and signatures, and public detectability from a public verification procedure. The empirical study is a useful negative result, quantifying how quickly current embeddings such as SSCD and DINOv2 degrade under small ℓ∞ and ℓ1 perturbations, and the paper is explicit that the required primitive does not yet exist. The paper does not fit parameters to obtain its claim; the theorem is conditional on stated primitives, and the self-citation to Fairoze et al. is contextual rather than load-bearing. The central existence claim is, however, currently not proven because the reduction in Supplement B.2 has a load-bearing gap; this makes the significance conditional on a repair.

major comments (2)
  1. [Supplement B.2, Claim 2] The reduction A_REF is not a valid adversary for Definition B.1. Definition B.1 fixes a challenge x and requires the adversary to output x* such that Compare(Embed(x), Embed(x*)) = true and x* ∉ Γ(x). The constructed A_REF ignores its input x, runs A_RPWS(pk) to obtain x*, and submits (e, e*) with e = Embed(x*) and e* decoded from x*. This pair is a collision between x* and the source of e*—typically one of A_RPWS's watermark queries—not between x* and the challenge x; nothing forces A_RPWS to interact with x. The same gap affects A_SIG: if A_RPWS reuses a legitimately signed embedding e_i from an oracle query, then (e*, σ*) is not a valid signature forgery. The assertion that at least one of A_SIG or A_REF will succeed therefore requires a multi-query hybrid that tracks whether the forged embedding was signed during a watermark query, and no such hybrid is supplied. Until Definition B.1 is strengthened to pair-finding collision resistance and the reduction is reworked, Theorem 5.1 is not proven.
  2. [Supplement B.2, Claim 1] The correctness argument concludes that Detect(pk, T(Watermark(sk,x))) succeeds whenever SIG.Verify and REF.Compare succeed, but the hypotheses do not imply the required Compare condition. For T ∈ T_REF ∩ T_PGWS, the verification requires REF.Compare(Embed(T(Encode(x, σ∥e))), e) = true. REF correctness only guarantees Compare(Embed(x), Embed(T'(x))) = true for each T' ∈ T_REF, and the condition 'PGWS.Encode ∈ T_REF' is not formally defined; in any case, membership of Encode in T_REF does not imply that the composition T∘Encode(x,·) is in T_REF unless T_REF is closed under composition. The proof needs an explicit closure condition or a different correctness argument before the stated ε_REF + ε_PGWS + negl(λ) bound can be accepted.
minor comments (5)
  1. [Supplement B.2, end of Claim 1] The displayed equation '1 − (ε_REF + ε_PGWS + negl(λ)) =: 1 − ε_PGWS' appears to define the final error probability as ε_PGWS, which is inconsistent; it should introduce a new parameter such as ε_RPWS.
  2. [Definition B.3] The private unforgeability property contains a malformed line ', Decode ← Generate(1λ, c,T)' that is missing the Encode algorithm, and the heading contains the typo 'Unforegability'; these should be corrected.
  3. [Theorem 5.1] The condition 'PGWS.Encode ∈ T_REF' is ambiguous because T_REF is a set of transformations while Encode is an algorithm with an additional message input; the paper should specify that for every message m, the map x ↦ Encode(x,m) is a transformation in T_REF.
  4. [Section 4, Theorem 4.2] The claimed collision resistance of the floor hash is asserted for 'natural images' without a formal distribution or definition of visual similarity; if this warmup scheme is intended as a formal result, the image class and the transformation set Γ should be made precise.
  5. [Section 6.2] The text refers to Figure 5 for ℓ1 results, but Figure 5 appears only in Supplement C; the main-text reference should point to the supplement explicitly or the figure should be moved into the main text.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 5.1 is a transparent conditional composition of independently stated primitives; the only self-citation is contextual, and the paper explicitly tables deployment on a currently-unavailable collision-resistant embedding.

full rationale

The claimed derivation chain in Theorem 5.1 is a conditional composition: it assumes a (T_REF, m, n, epsilon_REF)-robust embedding function, a (T_PGWS, c, epsilon_PGWS)-post-hoc watermarking scheme, and a (delta, lambda)-signature scheme with c >= delta + n and PGWS.Encode in T_REF, and then defines Watermark/Detect by embedding the image, signing the embedding, and encoding signature and embedding through the post-hoc watermark. Unforgeability is argued by reduction to signature unforgeability and robust-embedding collision resistance; no parameter is fitted from data and then renamed as a prediction, and no derived quantity is inserted into the definitions by construction. The only self-citation, Fairoze et al. 2023, is referenced as the text-domain analogue and is not load-bearing for the image construction or its proof. The paper also states a clear practical limitation rather than hiding it: Section 6.2 reports that all evaluated embedding models fail the required collision-resistance property, e.g., SSCD's ROC AUC drops to 0.057 under a small L_infinity attack, so the theorem is explicitly conditional on a primitive that does not yet exist. Separately, the Supplement B.2 reduction for A_REF does not appear to bind the challenge x to the adversary's output, which is a proof-soundness concern about Claim 2 rather than a circularity of the construction; the scheme is still a genuine composition of stated assumptions, not an equation that reduces to its own inputs. Overall, no circular step of any of the enumerated kinds is present.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the assumed existence of three primitives: cryptographic signatures (standard), a post-hoc watermark with sufficient capacity (domain assumption), and a collision-resistant robust embedding (defined by this paper and not yet realized). The warmup scheme additionally assumes a heuristic collision-resistance property of its non-keyed floor hash.

assumptions (4)
  • standard math Existence of (delta, lambda)-cryptographic signature schemes (e.g., RSA, ECDSA)
    Used as building block in Theorem 5.1; standard cryptographic assumption.
  • ad hoc to paper Existence of a (T_REF, m, n, epsilon_REF)-robust embedding function satisfying correctness and collision resistance per Definition B.1
    The paper defines this primitive and assumes it exists for the theorem; Section 6.2 shows no current model satisfies it.
  • ad hoc to paper Existence of a (T_PGWS, c, epsilon_PGWS)-post-hoc watermarking scheme with capacity c >= delta + n and such that Encode is in T_REF
    Section 5.3; couples the watermarking perturbation to the embedding's robustness set.
  • ad hoc to paper The floor-hash in the warmup scheme is collision-resistant for natural images (Section 4)
    Used in Theorem 4.2 proof; only a heuristic, not a formal collision-resistance notion.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Difficulty of Constructing a Robust and Publicly-Detectable Watermark." pith.science (2026). https://pith.science/paper/VIWVKJ5O

@misc{pith2026250204901,
  author       = {Pith},
  title        = {Pith review of: On the Difficulty of Constructing a Robust and Publicly-Detectable Watermark},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VIWVKJ5O}},
  note         = {Machine review of arXiv:2502.04901}
}
read the original abstract

This work investigates the theoretical boundaries of creating publicly-detectable schemes to enable the provenance of watermarked imagery. Metadata-based approaches like C2PA provide unforgeability and public-detectability. ML techniques offer robust retrieval and watermarking. However, no existing scheme combines robustness, unforgeability, and public-detectability. In this work, we formally define such a scheme and establish its existence. Although theoretically possible, we find that at present, it is intractable to build certain components of our scheme without a leap in deep learning capabilities. We analyze these limitations and propose research directions that need to be addressed before we can practically realize robust and publicly-verifiable provenance.

Figures

Figures reproduced from arXiv: 2502.04901 by the authors.

Figure 1
Figure 1. The three main approaches to content provenance. Metadata-based provenance [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Specification of our unforgeable and publicly-detectable watermark. The keys [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. A robust and publicly-detectable watermark built from a cryptographic signature [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (11 more)
Figure 4
Figure 4. Figure 4: Resistance to ℓ∞ attacks slightly increases with model performance. The y-axis of the right graph is calculated as the area under the corresponding curve in the left graph. Evaluation. We measure the following: 1. Clean performance. We calculate the area under the rece…
Figure 5
Figure 5. Figure 5: Resistance to ℓ1 attacks slightly increases with model performance. The y-axis of the right figure is calculated as the area under the corresponding curve in the left figure. 27 [PITH_FULL_IMAGE:figures/full_fig_p027_5.png]
Figure 6
Figure 6. Figure 6: Base image. 28 [PITH_FULL_IMAGE:figures/full_fig_p028_6.png]
Figure 7
Figure 7. Figure 7: ℓ∞-attacked positive image for ϵ ∈ {0/255, 1/255, 2/255, 4/255, 8/255, 16/255, 32/255} over DINOv2 (giant) [PITH_FULL_IMAGE:figures/full_fig_p029_7.png]
Figure 8
Figure 8. Figure 8: ℓ∞-attacked negative image for ϵ ∈ {0/255, 1/255, 2/255, 4/255, 8/255, 16/255, 32/255} over DINOv2 (giant) [PITH_FULL_IMAGE:figures/full_fig_p029_8.png]
Figure 9
Figure 9. Figure 9: ℓ1-attacked positive image for ϵ ∈ {0/255, 1/255, 2/255, 4/255, 8/255, 16/255, 32/255} over DINOv2 (giant) [PITH_FULL_IMAGE:figures/full_fig_p029_9.png]
Figure 10
Figure 10. Figure 10: ℓ1-attacked negative image for ϵ ∈ {0/255, 1/255, 2/255, 4/255, 8/255, 16/255, 32/255} over DINOv2 (giant). 29 [PITH_FULL_IMAGE:figures/full_fig_p029_10.png]
Figure 11
Figure 11. Figure 11: ℓ∞-attacked positive image for ϵ ∈ {0/255, 1/255, 2/255, 4/255, 8/255, 16/255, 32/255} over SSCD (imagenet-advanced) [PITH_FULL_IMAGE:figures/full_fig_p030_11.png]
Figure 12
Figure 12. Figure 12: ℓ∞-attacked negative image for ϵ ∈ {0/255, 1/255, 2/255, 4/255, 8/255, 16/255, 32/255} over SSCD (imagenet-advanced) [PITH_FULL_IMAGE:figures/full_fig_p030_12.png]
Figure 13
Figure 13. Figure 13: ℓ1-attacked positive image for ϵ ∈ {0/255, 1/255, 2/255, 4/255, 8/255, 16/255, 32/255} over SSCD (imagenet-advanced) [PITH_FULL_IMAGE:figures/full_fig_p030_13.png]
Figure 14
Figure 14. Figure 14: ℓ1-attacked negative image for ϵ ∈ {0/255, 1/255, 2/255, 4/255, 8/255, 16/255, 32/255} over SSCD (imagenet-advanced). 30 [PITH_FULL_IMAGE:figures/full_fig_p030_14.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. First-Place Solution to NeurIPS 2024 Invisible Watermark Removal Challenge

    cs.CV 2025-08 conditional novelty 4.0 of 10

    A competition-winning pipeline removes 95.7% of StegaStamp and TreeRing watermarks on the NeurIPS 2024 benchmark by combining VAE fine-tuning, diffusion purification, and translation tricks.

  2. README: Robust Error-Aware Digital Signature Framework via Deep Watermarking Model

    cs.CR 2025-07 reject novelty 4.0 of 10

    By cropping an image and adding a learned error-painting correction module, an off-the-shelf 64-bit watermarking model is claimed to carry 2048-bit signatures with 86.3% zero-bit-error image rate under JPEG compression.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages · cited by 2 Pith papers

  1. [1]

    Generate takes the input size m, output size n, and the security parameter λ, outputting the robust embedding function in time poly(λ)

    Generate(1λ, m, n,T ) → (Embed, Compare). Generate takes the input size m, output size n, and the security parameter λ, outputting the robust embedding function in time poly(λ)

    work page

  2. [2]

    The function Embed : {0, 1}m → {0, 1}n takes an arbitrary object x and maps it to a discrete point in the embedding space e

    Embed(x) → e. The function Embed : {0, 1}m → {0, 1}n takes an arbitrary object x and maps it to a discrete point in the embedding space e

    work page

  3. [3]

    The function Compare : {0, 1}n × {0, 1}n → {0, 1} takes two embed- dings x and y and outputs a single bit b such that b is true when x and y are similar, and false otherwise

    Compare(x, y) → b. The function Compare : {0, 1}n × {0, 1}n → {0, 1} takes two embed- dings x and y and outputs a single bit b such that b is true when x and y are similar, and false otherwise. A valid robust embedding function must satisfy the following two properties: 22

    work page

  4. [4]

    Output x′. Detect. Given a public key pk and candidate watermarked object x′,

    work page

  5. [5]

    Output b1 ∧ b2. Claim 1. The above scheme is correct if the underlying signature scheme and post-generation watermarking scheme are both correct. Proof. Observe that this RPWS is robust to the intersection of the input transformation sets, i.e., TRPWS = TREF ∩ TPGWS—any transformation applied to the image that is not in this set will result in either inco...

    work page

  6. [6]

    For all x and transformations T ∈ T, Pr Compare(Embed(x), Embed(T (x))) = true : Embed, Compare ← Generate(1λ, m, n,T ) ≥ 1 − ϵ

    Correctness. For all x and transformations T ∈ T, Pr Compare(Embed(x), Embed(T (x))) = true : Embed, Compare ← Generate(1λ, m, n,T ) ≥ 1 − ϵ

    work page

  7. [7]

    For any choice of x, it must be that Pr   Compare(Embed(x), Embed(x∗)) = true ∧ x∗ ̸∈ Γ(x) : Embed, Compare ← Generate(1λ, m, n,T ) x∗ ← AEmbed(·)(m, n,T , x)   ≤ ϵ

    Collision-resistance. For any choice of x, it must be that Pr   Compare(Embed(x), Embed(x∗)) = true ∧ x∗ ̸∈ Γ(x) : Embed, Compare ← Generate(1λ, m, n,T ) x∗ ← AEmbed(·)(m, n,T , x)   ≤ ϵ. Definition B.2 (Cryptographic signature scheme). A (δ, λ)-cryptographic signature scheme SIG is a 3-tuple ( Generate, Sign, Verify) defined as follows:

    work page

  8. [8]

    Takes in the target security bits number λ and outputs a fresh secret key sk and public key pk pair in time poly(λ)

    Generate(1λ) → (sk, pk). Takes in the target security bits number λ and outputs a fresh secret key sk and public key pk pair in time poly(λ)

    work page

Show all 38 references
  1. [9]

    Given the secret key sk and a object to signx, Sign computes σ ∈ {0, 1}δ: a signature of sk on x

    Sign(sk, x) → σ. Given the secret key sk and a object to signx, Sign computes σ ∈ {0, 1}δ: a signature of sk on x

  2. [10]

    Given a public key pk, object x, and signature σ, Verify checks if σ is a valid signature of the corresponding secret key of pk on x and encodes the result into one bit b

    Verify(pk, x, σ) → b. Given a public key pk, object x, and signature σ, Verify checks if σ is a valid signature of the corresponding secret key of pk on x and encodes the result into one bit b. It returns either true or false depending on if verification succeeded or not. A va...

  3. [11]

    It holds that for all x, Pr Verify(pk, x,Sign(sk, x)) = true : (sk, pk) ← Generate(1λ) ≥ 1 − negl(λ)

    Correctness. It holds that for all x, Pr Verify(pk, x,Sign(sk, x)) = true : (sk, pk) ← Generate(1λ) ≥ 1 − negl(λ)

  4. [12]

    Let X denote the set of oracle queries that the adversary makes to Sign(sk, ·)

    Unforgeability. Let X denote the set of oracle queries that the adversary makes to Sign(sk, ·). It holds that for all x, Pr   Verify(pk, x∗, σ∗) = true ∧ x∗ ̸∈ X : (sk, pk) ← Generate(1λ) (x∗, σ∗) ← ASign(sk,·)(pk)   ≤ negl(λ). Definition B.3 (Post-hoc watermarking sch...

  5. [13]

    Takes in the target security bits number λ, the capacity size in bits c, and the set of possible transformations T and outputs the encode and decode algorithms in time poly(λ)

    Generate(1λ, c,T ) → (Encode, Decode). Takes in the target security bits number λ, the capacity size in bits c, and the set of possible transformations T and outputs the encode and decode algorithms in time poly(λ)

  6. [14]

    Given a message m such that m ∈ {0, 1}c and target object x, Encode plants m a watermark in x producing x′

    Encode(x, m) → x′. Given a message m such that m ∈ {0, 1}c and target object x, Encode plants m a watermark in x producing x′. 23

  7. [15]

    Given a potentially watermarked object x∗, Decode recovers m ∈ {0, 1}c if it exists

    Decode(x∗) → m. Given a potentially watermarked object x∗, Decode recovers m ∈ {0, 1}c if it exists. Let X and M be the set of all valid objects and messages respectively. A valid PGWS must satisfy correctness with optional private unforgeability:

  8. [16]

    For all choices of x, m, and T , Pr Decode(T (Encode(x, m))) = m : Encode, Decode ← Generate(1λ, c,T ) ≥ 1 − ϵ

    Correctness. For all choices of x, m, and T , Pr Decode(T (Encode(x, m))) = m : Encode, Decode ← Generate(1λ, c,T ) ≥ 1 − ϵ

  9. [17]

    Let X be the list of object queries that A makes to the decoding oracle and let Γ(X) be the set containing all neighboring query objects

    Private Unforegability. Let X be the list of object queries that A makes to the decoding oracle and let Γ(X) be the set containing all neighboring query objects. It must be that for all x, m, and A, Pr   Decode(x∗, m) = m ∧ x∗ ̸∈ Γ(X) : , Decode ← Generate(1λ, c,T ) x∗ ← A...

  10. [18]

    Takes in the security parameter λ and outputs a fresh secret key sk and public key pk pair

    Generate(1λ) → (sk, pk). Takes in the security parameter λ and outputs a fresh secret key sk and public key pk pair

  11. [19]

    Given a secret key sk and target object x, Watermark plants a watermark in x under sk producing x′

    Watermark(sk, x) → x′. Given a secret key sk and target object x, Watermark plants a watermark in x under sk producing x′

  12. [20]

    Given a potentially watermarked object x∗, Detect checks if there is valid watermark under the corresponding secret key to pk

    Detect(pk, x∗) → b. Given a potentially watermarked object x∗, Detect checks if there is valid watermark under the corresponding secret key to pk. It outputs true or false as a single bit depending on if verification succeeds or not. A valid RPWS must satisfy the following properties:

  13. [21]

    It holds that for all x, Pr Detect(pk, T(Watermark(sk, x))) = true : (sk, pk) ← Generate(1λ) ≥ 1 − ϵ

    Correctness. It holds that for all x, Pr Detect(pk, T(Watermark(sk, x))) = true : (sk, pk) ← Generate(1λ) ≥ 1 − ϵ

  14. [22]

    Let X denote the set of oracle queries that the adversary makes to Watermark(sk, ·)

    Unforegability. Let X denote the set of oracle queries that the adversary makes to Watermark(sk, ·). It holds that for all x, Pr   Detect(pk, x∗) = true ∧ x∗ ̸∈ Γ(X) : (sk, pk) ← Generate(1λ) (x∗) ← AWatermark(sk,·)(pk)   ≤ ϵ. 24 B.2 Constructing a Robust and Publicly-...

  15. [23]

    Compute the robust embedding e = REF.Embed(x)

  16. [24]

    Sign the embedding σ ← SIG.Sign(sk, e)

  17. [25]

    Plant σ and e into x: x′ ← PGWS.Encode(x, σ∥ e)

  18. [27]

    Compute the aggregated hash e = REF.Embed(x′)

  19. [28]

    Decode the embedded payload if it exists σ′ ∥ e′ ← PGWS.Decode(x′)

  20. [29]

    Attempt signature verification b1 ← SIG.Verify(pk, e′, σ′)

  21. [30]

    Attempt closeness verification b2 ← REF.Compare(e, e′)

  22. [32]

    Run ARPWS(pk) to obtain x∗ such that with high probabilityRPWS.Detect(pk, x∗) = true

  23. [33]

    Compute σ∗ ∥ e∗ ← PGWS.Decode(x∗)

  24. [34]

    Similarly, we construct AREF that breaks the collision-resistance of the underlying robust embedding function as follows: Construction of AREF

    Return ( e∗, σ∗) as a forgery. Similarly, we construct AREF that breaks the collision-resistance of the underlying robust embedding function as follows: Construction of AREF. On input x, T :

  25. [35]

    Run ARPWS(pk) to obtain x∗ such that with high probability Detect(pk, x∗) = true

  26. [36]

    Compute the output of REF.Embed: e ← REF.Embed(x∗)

  27. [37]

    Decode the payload σ∗ ∥ e∗ ← Decode(x∗)

  28. [38]

    cropped and affine-transformed

    Submit ( e, e∗) as a collision. We know that with high probability,Detect(pk, x∗) = SIG.Verify(pk, e∗, σ∗) ∧ REF.Compare(e, e∗) = true implying that either Verify or Compare has been forged such that x∗ ̸∈ Γ(x). It is easy to see that at least one of ASIG or AREF will succeed:...

    2019

  29. [2003]

    Their techniques formed the backbone of Shazam [Wang, 2006]

    developed a highly effective audio fingerprint for identifying music. Their techniques formed the backbone of Shazam [Wang, 2006]. Feature extraction. We highlight key works that are relevant to this paper. We refer the reader to the DINOv2 paper [Oquab et al., 2023] for a mor...

    2006

  30. [2019]

    granularity

    developed Multigrain: a network architecture designed to produce compact descrip- tors for image classification and object retrieval downstream tasks. It crucially leverages different levels of image “granularity” to learn generalized features. Bootstrap Your Own Latents (BYOL...

    2020

Pith tools

Reviewed August 8, 2026 · model on record in the stance chip above.