{"id":"3bba8659-0a6f-493a-98fd-042cae2923ee","arxiv_id":"2502.04901","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A formal proof that robust, unforgeable, publicly-detectable image watermarks are possible if collision-resistant robust embeddings exist, plus evidence that all current embedding models fail that requirement.","lead":"This paper asks whether an image watermark can be both impossible to forge and verifiable by anyone, while still surviving normal edits. It proves such a scheme exists in theory, but shows today's image-embedding models are too easy to attack to build it yet.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of Theorem 5.1 does not reduce unforgeability to collision resistance: A_REF never ties the challenge x to A_RPWS's queries, so the central existence claim is unsupported.","rationale":"The reader identified the existence of a collision-resistant robust embedding as the weakest assumption, but the deeper problem is that the proof of Theorem 5.1 is invalid even granting that assumption. The reduction in Claim 2 (Supplement B.2) is the only argument for unforgeability, and it does not connect the challenge image x of the collision-resistance game to the queries made by the RPWS adversary. A successful RPWS forgery yields a collision with some queried image x_i, but the reduction is given x, not x_i, and cannot force the adversary to query x. Therefore the constructed A_REF does not satisfy the success condition of Definition B.1. This is not a matter of missing formality or a non-uniform argument; the reduction's output is simply not a valid collision for the challenge. The correctness proof in Claim 1 also has a hidden compositionality assumption: robustness of REF to Encode and to T separately does not imply robustness to Encode followed by T unless Compare is transitive or T_REF is closed under composition. Both gaps affect the central conditional-existence theorem. The empirical sections remain valuable, but the paper's main theoretical claim is unsupported as written, so the verdict should move from CONDITIONAL to REJECT unless the proof is repaired or the definitions are revised.","tokens_in":19400,"tokens_out":19805,"duration_ms":203746,"concrete_test":"Re-derive Claim 2 with the success predicate of Definition B.1 made explicit. Write A_REF(input x, oracle Embed) and show the exact probability that its output x* satisfies Compare(Embed(x), Embed(x*)) = true. In the current text, A_REF returns embeddings (e, e*) and never uses x except to pass it to A_RPWS (which ignores it); exhibit the missing step that forces A_RPWS to query x, or else conclude that the reduction is invalid. Additionally, replace Definition B.1 with a pair-finding game (adversary outputs (x, x*)) and check whether Claim 2's proof becomes valid; if so, the theorem relies on a different and explicitly stated assumption than the one given.","verdict_should_be":"REJECT","load_bearing_attack":"Claim 2 in Supplement B.2 constructs an adversary A_REF against Definition B.1 that, on input a challenge image x, runs A_RPWS(pk) to obtain a forgery x*, computes e ← REF.Embed(x*), decodes e*, and submits (e, e*) as a 'collision'. This is not a valid attack on Definition B.1. The game requires the output x* to satisfy Compare(Embed(x), Embed(x*)) = true and x* ∉ Γ(x) for the given challenge x. In the RPWS forgery, Detect(x*) = true gives Compare(Embed(x*), e*) = true and Verify(pk, e*, σ*) = true. If e* equals a signed embedding from a watermark query x_i, the collision is with x_i, not with the challenge x; A_REF's output never involves x unless A_RPWS happens to query x, which the reduction cannot force. The reduction would go through if Definition B.1 allowed the adversary to output both objects (pair-finding), but it does not. Thus Theorem 5.1 is unproven even under the stated assumptions. A secondary issue: Claim 1's correctness requires Compare(Embed(x), Embed(T(Encode(x)))) = true for T ∈ T_REF ∩ T_PGWS, which does not follow from the pairwise correctness of REF unless T_REF is closed under composition and Compare is transitive; the theorem only assumes PGWS.Encode ∈ T_REF.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":19788,"tokens_out":7650,"duration_ms":75742,"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":[{"comment":"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.","section":"Supplement B.2, Claim 2"},{"comment":"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.","section":"Supplement B.2, Claim 1"}],"minor_comments":[{"comment":"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.","section":"Supplement B.2, end of Claim 1"},{"comment":"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.","section":"Definition B.3"},{"comment":"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.","section":"Theorem 5.1"},{"comment":"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.","section":"Section 4, Theorem 4.2"},{"comment":"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.","section":"Section 6.2"}],"recommendation":"major_revision","confidential_remarks":"For the editor: the paper's headline claim is a proof of existence, but the reduction in Supplement B.2 is a sketch with a genuine gap: the collision-resistance adversary is not tied to the challenge input, and no multi-query hybrid is provided. The gap appears fixable by strengthening Definition B.1 to pair-finding collision resistance or by adding a careful hybrid argument, so I do not recommend rejection. I would also suggest that the framing be aligned with the paper's own empirical conclusion: the paper is best read as a barrier analysis plus a conditional blueprint, not as an unconditional existence proof."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read the paper because it gives the field something to argue with, not because the main theorem holds. The definitions of a robust publicly-detectable watermark, post-hoc watermark, and robust embedding are clean and organize the design space usefully. The construction itself is natural: sign the embedding, hide both inside the image, and check signature plus similarity. That's a good framework to have on paper. The empirical study is also genuinely useful: it runs PGD attacks against a wide set of SSL embedding models and shows that clean ROC AUC collapses under small perturbations. The correlation with model performance is weak but visible; the authors do not oversell it. They also honestly state that no current model instantiates the required collision-resistant embedding.\n\nThe problem is the proof of Theorem 5.1. The reduction in Supplement B.2 does not work. A_REF is supposed to break collision-resistance of the embedding, but on challenge x it runs A_RPWS, which may never query x, and then submits (e,e*) where e=Embed(x*) and e* is the decoded signed embedding. The definition of collision-resistance requires the output to be an image x* such that Compare(Embed(x), Embed(x*))=true and x* not in Γ(x). The reduction never ties the challenge x to the adversary's queries, so the output is either a collision with some watermarked image x_i or nothing. Similarly, A_SIG returns the decoded signature on e*, but if e* was signed during a watermarked query, that is not a forgery. The disjunction 'at least one reduction succeeds' is unsupported. The theorem might be true under stronger assumptions, but it is not proven here.\n\nThere is also a smaller correctness gap: the composed scheme needs Compare to be transitive and T_REF closed under composition to guarantee Detect on transformed watermarked images, and the paper assumes neither.\n\nThe empirical section is good enough to report, though it would be stronger with confidence intervals and code. The paper should be sent to reviewers, because the definitions and the negative result are worth polishing, and a referee can force the proof to be fixed or clearly stated as a conjecture. Don't cite the theorem as established; cite it for the framework and the attack evaluation.","headline":"The framework and empirical evaluation are worth a look, but the central composition theorem is not proven as written.","tokens_in":20199,"tokens_out":3242,"would_cite":true,"duration_ms":30930,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["image watermarking","publicly-detectable watermarking","unforgeability","robust embeddings","post-hoc watermarking","adversarial robustness","content provenance","collision resistance"],"falsifier":"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.","tokens_in":19227,"feed_emoji":"🖼️","tokens_out":9432,"duration_ms":80712,"temperature":0.7,"pith_summary":"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.","feed_headline":"An unforgeable public image watermark is provably possible","feed_subtitle":"Composes signatures, watermarks, and embeddings; only a collision-proof embedding is missing for deployment.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the cryptographic signature scheme whose unforgeability the construction inherits.","marker":"Rivest et al., 1978"},{"why":"DINOv2 is one of the state-of-the-art embedding models evaluated for collision resistance, with clean ROC AUC 0.990.","marker":"Oquab et al., 2023"},{"why":"SSCD is the embedding model whose ROC AUC collapses to 0.057 under a 4/255 l-infinity PGD attack, showing the current barrier.","marker":"Pizzi et al., 2022"},{"why":"Provides the projected gradient descent attack used to test whether embeddings are collision-resistant in a white-box setting.","marker":"Madry et al., 2018"},{"why":"TrustMark instantiates the post-hoc watermark, supplying the capacity, PSNR, and SSIM values the scheme would inherit.","marker":"Bui et al., 2023a"},{"why":"The NeuralHash attack demonstrates the practical failure mode of collision resistance in a deployed white-box embedding, motivating the definition.","marker":"Struppek et al., 2022"},{"why":"Provides the NeuralHash deployment context where a robust embedding was exposed to white-box users.","marker":"Apple, 2021"},{"why":"Supplies the least-significant-bit encoding used in the non-robust unforgeable warmup scheme.","marker":"Muyco and Hernandez, 2019"},{"why":"Copydays dataset provides the positive and negative image pairs used to measure embedding performance and attack success.","marker":"Douze et al., 2009"}],"fun_headline_variants":["Public watermark proven possible, but embedding is broken","Unforgeable watermark exists, yet AI gap blocks deployment","Robust public provenance proven, but lacks collision-proof embedding","Watermark theory says yes, practice says not yet","Proof of public watermark, but no robust embedding yet"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Public watermark proven possible, but embedding is broken","Unforgeable watermark exists, yet AI gap blocks deployment","Robust public provenance proven, but lacks collision-proof embedding","Watermark theory says yes, practice says not yet","Proof of public watermark, but no robust embedding yet"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000275,"raw_usage":{"total_tokens":1663,"prompt_tokens":983,"completion_tokens":680,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":599,"completion_tokens_details":{"reasoning_tokens":603}},"tokens_in":599,"tokens_out":680,"duration_ms":7222,"temperature":1.0,"reasoning_tokens":603,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T21:01:14.000766+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}