Beyond Bit Matching: Orthogonal Watermarks for Collusion-Resistant Image Fingerprinting

Zhakshylyk Nurlanov, Tobias Weißberg, Florian BernardarXiv 2026 · arXiv

TL;DR

VectorMark is a novel image fingerprinting framework that replaces traditional discrete bit-string watermarks with high-dimensional, near-orthogonal unit vectors. By shifting the problem from bit-matching to directional retrieval (cosine similarity), the system achieves unprecedented resistance to "averaging collusion," successfully identifying all members of a 10-user coalition even in a registry of one million users.

What Problem Does This Paper Address?

Image fingerprinting is the practice of embedding unique, invisible marks into distributed copies of an image to trace leaks back to specific users. However, these systems face a major threat: collusion attacks. If several users combine their uniquely marked copies (e.g., by averaging the pixels), the individual watermarks often cancel each other out or become so degraded that they are unrecoverable.

Most modern neural watermarking methods use discrete bit-strings. When these strings are averaged, the "evidence" for any single bit is pushed toward an ambiguous middle state (0.5), causing the decoder to fail. The authors identify a critical gap: existing methods are either robust to standard distortions (like cropping or noise) but fail under collusion, or they are theoretically collusion-resistant but brittle against real-world image transformations.

Collusion attacks degrade traditional watermarks, but directional signals remain identifiable.

Methods

VectorMark departs from bit-matching by formulating fingerprinting as directional retrieval over a high-dimensional unit sphere.

  1. Near-Orthogonal Keys: Each user is assigned a unique vector key in a 1024-dimensional space. Because of the "blessing of dimensionality," randomly chosen vectors in high-dimensional space are almost always nearly orthogonal.
  2. Neural Architecture: The system uses a U-Net-based encoder to embed these vectors into images. To ensure the marks remain invisible, it employs a Just-Noticeable-Difference (JND) mask, which concentrates the watermark energy in textured areas where the human eye is less sensitive to changes.
  3. Collusion-Aware Training: The model is trained using a progressive curriculum. Crucially, it includes a "collusion loss" that encourages the network to ensure that the average of multiple watermarked images behaves like the embedding of the average of their corresponding vector keys.
  4. Analytic Detection: Instead of empirical testing, the authors use the shifted-Beta distribution to model the null hypothesis (the similarity between a random key and an unwatermarked image). This allows for precise, analytic control over the False Positive Rate (FPR), even in massive databases.
The VectorMark architecture uses a JND-masked encoder and a directional extractor.

Datasets

The authors evaluated VectorMark across diverse image domains to ensure generalization:

  • Training: MS-COCO 2014 (82k images).
  • Evaluation:
    • MS-COCO 2014 validation set (1,000 images).
  • OpenImages V7 (1,000 images) to test natural image generalization.
  • AI-Generated Images: A custom set of 1,000 images from DALL-E 3, FLUX, OpenAI-4o, Nano-Banana, and SDXL to test robustness in the context of generative AI.

Key Insights and Ideas

  • The $1/\sqrt{K}$ Signal: The core mathematical insight is that when $K$ near-orthogonal vectors are averaged, the resulting vector retains a cosine similarity of approximately $1/\sqrt{K}$ with each original vector. In high dimensions, this signal is significantly stronger than the "noise" from unrelated keys, which stays near zero.
  • Soft Evidence > Hard Decisions: By avoiding the "hard" decision of bit-decoding until the very end, VectorMark preserves forensic evidence that would otherwise be lost during collusion.
  • Geometry as a Defense: The spherical geometry of random directions provides a principled way to set detection thresholds, making the system scalable to millions of users without needing to re-calibrate for every new query.

Key Results

VectorMark significantly outperforms state-of-the-art baselines in multi-user scenarios:

  • All-Colluder Detection: It achieves near-perfect detection of all colluders for groups up to $K=10$ at a very strict FPR of $10^{-6}$. In contrast, bit-matching baselines like StegaStamp collapse completely once $K$ exceeds 2 or 3.
  • Large-Scale Scaling: In a simulated registry of one million users, VectorMark maintained a 98% exact-set recovery rate for 10-user coalitions.
  • Robustness: It remains highly effective under standard distortions, including JPEG compression, cropping, and rotations, while maintaining high visual quality (PSNR ~40dB).
Figure 3: Collusion attacks on OpenImages. Each curve shows strict all-colluder TPR at per-key FPR = 10−6 for up to K = 20 colluders. We compare standard averaging collusion with pixelwise median and pixelwise mosaic non-averaging collusions. TrustMark uses bit-agreement scores with a binomial threshold; VectorMark and SS-DFT use calibrated cosine-similarity thresholds.

Limitations and Future Work

  • Computational Scaling: While the neural extraction is fast, searching a million-user database requires $O(ND)$ operations. For billion-user scales, the authors suggest that approximate nearest-neighbor (ANN) search will be necessary, which may introduce a recall-efficiency trade-off.
  • Non-Linear Collusion: While robust to averaging, median, and mosaic collusion, the system's performance is highest under mean averaging. More complex, non-linear adversarial attacks could potentially degrade the signal further.
  • Security vs. Robustness: The authors clarify that this is a forensic tool, not a cryptographic one. An attacker with white-box access to the encoder could still potentially forge watermarks or perform "framing" attacks. Future work could explore securing the embedding process itself.

Summary updated

Abstract

Image fingerprinting assigns each distributed copy a user-specific watermark for source tracing. Averaging collusion is a central threat: several recipients can average their differently marked copies to suppress each individual mark. Discrete bit-string watermarks are especially vulnerable because averaging drives bit evidence toward ambiguous decisions. We introduce \textbf{VectorMark}, which maps user keys to near-orthogonal high-dimensional unit vectors and identifies colluders by cosine similarity to the extracted watermark direction. Under ideal averaging of $K$ vector keys, the normalized average preserves a cosine signal of order $1/\sqrt{K}$ for each colluder, while unrelated keys remain concentrated near zero. The spherical geometry of random directions gives a shifted-Beta null distribution for cosine similarities, enabling analytic per-key false-positive-rate control after validation on unwatermarked images. VectorMark uses a neural watermark encoder and centered extractor trained with JND masking and a progressive curriculum for photometric, geometric, and collusion robustness. Experiments on MS-COCO, OpenImages, and AI-generated images show that VectorMark maintains robust watermark attribution under photometric and geometric distortions, and achieves the best strict all-colluder detection among evaluated methods, while preserving high visual quality. Our code is publicly available: https://github.com/nurlanov-zh/VectorMark
BibTeX
@misc{nurlanov2026beyond,
  author = {Zhakshylyk Nurlanov and Tobias Weißberg and Florian Bernard},
  title = {{Beyond Bit Matching: Orthogonal Watermarks for Collusion-Resistant Image Fingerprinting}},
  year = {2026},
  eprint = {2611.10858},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.10858},
}
Figure