Watermarking generative models consists of planting a statistical signal
(watermark) in a model's output so that it can be later verified that the
output was generated by the given model. A strong watermarking scheme satisfies
the property that a computationally bounded attacker cannot erase the watermark
without causing significant quality degradation. In this paper, we study the
(im)possibility of strong watermarking schemes. We prove that, under
well-specified and natural assumptions, strong watermarking is impossible to
achieve. This holds even in the private detection algorithm setting, where the
watermark insertion and detection algorithms share a secret key, unknown to the
attacker. To prove this result, we introduce a generic efficient watermark
attack; the attacker is not required to know the private key of the scheme or
even which scheme is used. Our attack is based on two assumptions: (1) The
attacker has access to a "quality oracle" that can evaluate whether a candidate
output is a high-quality response to a prompt, and (2) The attacker has access
to a "perturbation oracle" which can modify an output with a nontrivial
probability of maintaining quality, and which induces an efficiently mixing
random walk on high-quality outputs. We argue that both assumptions can be
satisfied in practice by an attacker with weaker computational capabilities
than the watermarked model itself, to which the attacker has only black-box
access. Furthermore, our assumptions will likely only be easier to satisfy over
time as models grow in capabilities and modalities. We demonstrate the
feasibility of our attack by instantiating it to attack three existing
watermarking schemes for large language models: Kirchenbauer et al. (2023),
Kuditipudi et al. (2023), and Zhao et al. (2023). The same attack successfully
removes the watermarks planted by all three schemes, with only minor quality
degradation.

在本文中，我们研究了强水印方案的（不）可能性。我们证明了在给定合理和自然的假设下，无法实现强水印。即使在私有检测算法设置下，即水印插入和检测算法共享一个对攻击者不知情的秘钥，此结果仍然成立。为了证明这个结果，我们引入了一个通用的高效水印攻击方法；攻击者不需要知道方案的私钥，甚至不需要知道使用的是哪个方案。我们的攻击基于两个假设：（1）攻击者可以访问 “质量 Oracle”，评估候选输出是否对提示有高质量的响应；（2）攻击者可以访问 “扰动 Oracle”，它可以以较高的概率修改输出，同时保持质量，并在高质量输出上诱导有效混合的随机游走。我们认为，这两个假设在实践中可以由比水印模型自身计算能力更弱的攻击者满足，攻击者只能以黑盒方式访问。此外，随着模型的能力和形式多样性的增长，我们的假设很可能随着时间的推移变得更容易满足。我们通过实施攻击来展示我们攻击的可行性，用于攻击大型语言模型的三个现有水印方案：Kirchenbauer 等（2023），Kuditipudi 等（2023）和 Zhao 等（2023）方案。同样的攻击成功去除了所有三个方案植入的水印，仅有轻微的质量降低。

沙滩上的水印：生成模型的强水印化的不可能性

Watermarks in the Sand: Impossibility of Strong Watermarking for  Generative Models

A classification is a surjective mapping from a set of objects to a set of
categories. A classification aggregation function aggregates every vector of
classifications into a single one. We show that every citizen sovereign and
independent classification aggregation function is essentially a dictatorship.
This impossibility implies an earlier result of Maniquet and Mongin (2016), who
show that every unanimous and independent classification aggregation function
is a dictatorship. The relationship between the two impossibilities is
reminiscent to the relationship between Wilson's and Arrow's impossibilities in
preference aggregation. Moreover, while the Maniquet-Mongin impossibility rests
on the existence of at least three categories, we propose an alternative proof
technique that covers the case of two categories, except when the number of
objects is also two. We also identify all independent and unanimous
classification aggregation functions for the case of two categories and two
objects.

每个类别的分类聚合函数本质上都是一个独裁统治，这一不可能性证明了 Maniquet 和 Mongin (2016) 的早期结果，即每个一致且独立的分类聚合函数也是一个独裁统治。

分类聚合无需一致

Classification Aggregation without Unanimity

Information theory plays an indispensable role in the development of
algorithm-independent impossibility results, both for communication problems
and for seemingly distinct areas such as statistics and machine learning. While
numerous information-theoretic tools have been proposed for this purpose, the
oldest one remains arguably the most versatile and widespread: Fano's
inequality. In this chapter, we provide a survey of Fano's inequality and its
variants in the context of statistical estimation, adopting a versatile
framework that covers a wide range of specific problems. We present a variety
of key tools and techniques used for establishing impossibility results via
this approach, and provide representative examples covering group testing,
graphical model selection, sparse linear regression, density estimation, and
convex optimization.

本文介绍信息论在统计估计不可能性问题上的应用，针对 Fano's inequality 及其变体进行详尽探讨，提供了一些关键工具和方法，并给出了若干具体实例，包括了分组测试、图形模型选择、稀疏线性回归、密度估计和凸优化等。