A zero-bit watermarked language model produces text that is indistinguishable
from that of the underlying model, but which can be detected as
machine-generated using a secret key. But merely detecting AI-generated spam,
say, as watermarked may not prevent future abuses. If we could additionally
trace the text to a spammer's API token, we could then cut off their access to
the model.
We introduce multi-user watermarks, which allow tracing model-generated text
to individuals or to groups of colluding users. We construct multi-user
watermarking schemes from undetectable zero-bit watermarking schemes.
Importantly, our schemes provide both zero-bit and multi-user assurances at the
same time: detecting shorter snippets as well as the original scheme and
tracing longer excerpts to individuals. Along the way, we give a generic
construction of a watermarking scheme that embeds long messages into generated
text.
Ours are the first black-box reductions between watermarking schemes for
language models. A major challenge for black-box reductions is the lack of a
unified abstraction for robustness -- that marked text is detectable after
edits. Existing works give incomparable robustness guarantees, based on bespoke
requirements on the language model's outputs and the users' edits. We introduce
a new abstraction -- AEB-robustness -- to overcome this challenge.
AEB-robustness provides that the watermark is detectable whenever the edited
text "approximates enough blocks" of model-generated output. Specifying the
robustness condition amounts to defining approximates, enough, and blocks.
Using our new abstraction, we relate the robustness properties of our
constructions to that of the underlying zero-bit scheme. Whereas prior works
only guarantee robustness for a single text generated in response to a single
prompt, our schemes are robust against adaptive prompting, a stronger
adversarial model.

零比特的水印语言模型能产生与底层模型无法区分的文本，但可以通过密钥检测为机器生成，我们通过多用户水印技术实现追踪模型生成文本的个人或合谋用户，同时提供零比特和多用户保证，以及构建了将长信息嵌入生成文本的水印技术。同时，通过引入 AEB 鲁棒性，解决了黑盒降维中对鲁棒性缺乏统一抽象的挑战，使我们的构建方案与底层零比特方案的鲁棒性属性关联，并且我们的方案对自适应提示是强鲁棒的。