VOW: Verifiable and Oblivious Watermark Detection for Large Language Models

arXiv:2604.27666 · cs.CR · Submitted 2026-04-30 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: Today's paper: "VOW: Verifiable and Oblivious Watermark Detection for Large Language Models".

Elias: The gist Large Language Model (LLM) watermarking is crucial for establishing provenance, but most existing methods rely on centralized trust models that force users to reveal sensitive text,

Nadia: First, who's behind it and why it matters.

Title and authors: Nadia: So we're looking at VOW: Verifiable and Oblivious Watermark Detection for Large Language Models. This paper tackles a big problem where you want to know if AI generated text came from a specific model, but current methods force you to show the AI what you wrote.

Elias: Exactly. Most existing methods rely on centralized trust models that make users reveal sensitive text just to get a detection result, and VOW proposes something different that keeps your input private while still letting you verify the result.

Nadia: It's about moving away from forcing users to reveal plaintext for auditing, which is a major privacy hurdle.

Elias: And it’s not just about privacy; they’re trying to solve the problem of trust with malicious providers who might lie about detection outcomes.

Priya: I'm curious how this actually works on the technical side and what that means for real-world usage, because privacy sounds good but implementation is everything.

The paper's summary: Nadia: So, VOW reformulates watermark detection as a secure two-party computation problem. They use something called a Verifiable Oblivious Pseudorandom Function, or VOPRF, to let users and providers check for watermarks without either party seeing the other's text.

Elias: That VOPRF is the core mechanism here. It sets up a secret key and a public key through a Setup lambda algorithm so that detection can happen locally using just the public key later on.

Nadia: They outline three main phases for this whole process: setup, then watermark insertion which happens on the provider's side, and finally the detection phase where both parties compute the result.

Priya: What I see in that is a focus on making sure the provider can't just claim they found a watermark when they didn't. That part feels really important for accountability.

Elias: Right, because without that verification, a bad provider could easily lie about an SLA violation by hiding the fact that their model isn't watermarked correctly.

The paper's improvements: Nadia: The authors highlight several improvements they made to the original ideas. They focus on making it practical for real use cases, especially when dealing with short outputs.

Elias: They addressed the issue where traditional asymmetric schemes need long text sequences, often hundreds of tokens just to embed enough cryptographic payload for detection. VOW aims to solve that practicality problem by doing something different.

Nadia: They introduce specific optimizations, like using rejection sampling for unbiased multinomial sampling and an accelerated top-k filtering using an adaptive sieve with an early exit. These are designed to speed things up without losing accuracy too much.

Priya: That efficiency stuff is key because if it takes too long or uses way too much data, nobody will actually use it for checking AI outputs on the go.

Elias: And they show that even with these optimizations, VOW maintains a true positive rate of zero point nine four six at seventy-five tokens, which suggests strong detectability even when the text is relatively short.

Conclusion: Nadia: So to wrap up, VOW provides this combination of cryptographic verifiability and user privacy while keeping the detection efficient enough for short texts. It shows accountability can happen without compromising user privacy or requiring massive amounts of text input.

Elias: It really boils down to making the detection process secure through two-party computation using that Verifiable Oblivious Pseudorandom Function, which is a solid theoretical foundation for auditing AI outputs.

Priya: What I'm taking away is that while this protocol has these efficiencies, the paper also flags some real limitations. They state that none of the evaluated schemes maintain reliable detection against modern paraphrasing attacks like GPT-five point one, which means we can't just assume perfect security against creative text manipulation.

Nadia: True. And there's another practical point they make: this interactive detection protocol requires cooperation between the user and the provider, which isn't always easy in practice.

Elias: Exactly. So while VOW is a significant step toward privacy-preserving auditing, it’s not a complete solution yet for everything we need to know about AI provenance.

Peking University

cs.CR

Submitted: 2026-04-30

Updated: 2026-10-09

Code: https://github.com/luan-xiaokun/voprf-llm-watermark

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 88/100

The gist: The gist Large Language Model (LLM) watermarking is crucial for establishing provenance, but most existing methods rely on centralized trust models that force users to reveal sensitive text, which

Key concepts

First-Party Provenance Audit (FPA): This is an internal process where an organization examines sensitive content it owns. The goal is to verify if specific, sensitive text has been marked with a watermark without exposing the actual text being audited to external services or the public.
Verifiable Oblivious Pseudorandom Function (VOPRF): This cryptographic tool allows two parties—the user and the detector service—to perform a computation. The user provides their input (text) privately, and the function computes a result that is verifiable by anyone, yet neither party learns the other's private input.
Setup Record: A signed document published before text generation begins. It fixes essential parameters like the public key and detector specifications. This record acts as a contract, allowing auditors to later reconstruct or verify the detection result without needing the secret watermarking key.

Terminology

Core — 1× in this paper · explained in 2 episodes
Large Language Model (LLM) — 1× in this paper · explained in 3 episodes
Provenance — 1× in this paper · explained in 4 episodes
Robustness — 1× in this paper · explained in 5 episodes

Summary

The gist Large Language Model (LLM) watermarking is crucial for establishing provenance, but most existing methods rely on centralized trust models that force users to reveal sensitive text, which VOW addresses by proposing a privacy-preserving and cryptographically verifiable detection protocol.

How it works

VOW reformulates watermark detection as a secure two-party computation problem, instantiating the core logic with a Verifiable Oblivious Pseudorandom Function (VOPRF) to allow users and providers to perform detection without revealing the user’s text while ensuring the provider’s result is verifiable. The protocol involves three phases: setup, insertion, and detection.

Key Components of the Protocol

Setup phase: The Provider runs the Setup(λ) algorithm of the VOPRF scheme to generate a secret key sk and a corresponding public key pk.
Watermark insertion: This is carried out locally by the Provider during text generation by modifying logits based on the IsGreen predicate.

Security and Threat Model

The threat model considers both a malicious provider S∗ and a malicious user C∗. For the malicious provider S∗, Property 1 requires Privacy, ensuring that the protocol must ensure that the provider learns nothing about the user’s input text beyond its length. Property 2 requires Verifiability, ensuring a malicious provider cannot forge a detection result. For the malicious user C∗, Property 3 focuses on Computational unforgeability, requiring the probability of a computationally bounded adversary successfully outputting a forged text T∗ is at most negligibly higher than the probability of a random text naturally satisfying the detection threshold.

Practicality and Evaluation

VOW achieves practical efficiency through several optimizations, such as rejection sampling for unbiased multinomial sampling and accelerated top-k filtering using an adaptive sieve with an early exit. The scheme demonstrates strong detectability on short texts, achieving a True Positive Rate of 0.946 at 75 tokens and maintains usable performance on low-entropy downstream tasks.

Conclusion

VOW provides a balanced combination of cryptographic verifiability and user privacy, strong detectability on short texts with controllable FPR, and practical overhead. The work demonstrates that achieving accountability in generative AI need not come at the cost of user privacy.

Limitations

VOW's interactive detection protocol requires cooperation between the User and Provider, and its robustness against advanced paraphrasing attacks remains limited. Furthermore, none of the evaluated schemes maintain reliable detection against GPT-5.1.

Open Science

The artifacts associated with this work are publicly available, including source code, datasets, and evaluation scripts. The repository provides the necessary code and instructions to reproduce our main results.

References

[1] Maryam Amirizaniani, Elias Martin, Tanya Roosta, Aman Chadha, and Chirag Shah. 2024. AuditLLM: A Tool for Auditing Large Language Models Using Multiprobe Approach (CIKM ’24). Association for Computing Machinery, New York, NY, USA, 5174–5179. doi:10.1145/3627673.3679222

[2] Dan Boneh. 1998. The Decision Diffie–Hellman problem. In Algorithmic Number Theory, Vol. 1423. Springer, 48–63. doi:10.1007/BFb0054851

[3] Will Cai, Tianneng Shi, Xuandong Zhao, and Dawn Song. 2025. Are You Getting What You Pay For? Auditing Model Substitution in LLM APIs. In NeurIPS 2025 Workshop on Regulatable ML. https://openreview.net/forum?id=thhrtv9P0s.

[4] Silvia Casacuberta, Julia Hesse, and Anja Lehmann. 2022. SoK: Oblivious Pseudorandom Functions. In 2022 IEEE 7th European Symposium on Security and Privacy (EuroS&P). IEEE Computer Society, Los Alamitos, CA, USA, 625–646. doi:10.1109/EuroSP53844.2022.00045

[5] David Chaum and Torben P. Pedersen. 1992. Wallet Databases with Observers. In Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology. Springer, 89–105

[6] Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger. 2021. Evaluating Large Language Models Trained on Code. arXiv:2107.03374 [cs.LG] https://arxiv.org/abs/2107.03374

[7] Miranda Christ and Sam Gunn. 2024. Pseudorandom Error-Correcting Codes.

Improvements for AI systems

Bold header: Verifiable Provenance Auditing for LLM APIs

This system can verify if a generated text originated from a specific provider’s model by performing detection without revealing sensitive user input, addressing the need to verify the provenance of an API response to ensure it originates from the claimed premium model.

Bold header: Privacy-Preserving Detection via 2PC

The improved system can perform detection using a secure two-party computation problem, instantiating the watermark’s core logic with a Verifiable Oblivious Pseudorandom Function (VOPRF), allowing users and providers to perform detection without the user’s text being revealed.

Bold header: Efficiency for Short Texts

The protocol is designed for practicality on limited outputs, as it achieves both privacy-preserving and cryptographically verifiable watermark detection with high efficiency even for short texts, overcoming the limitation of traditional asymmetric schemes requiring long text sequences.

Bold header: Robustness against Paraphrasing Attacks Reassessment

The system provides a critical recalibration of robustness by showing that existing methods are fragile, as the evaluation reveals that the robustness of all evaluated watermarks, including VOW, has been overestimated against modern paraphrasing attacks like GPT-5.1.

Bold header: Controllable Watermark Strength

Users gain a practical mechanism to balance security and quality by adjusting parameters such as delta from 2.5 to 2.0, allowing practitioners to balance utility and watermark strength based on their specific needs.