International Association
for Cryptologic Research

<p> We present a publicly-detectable watermarking scheme for LMs: the detection algorithm contains no secret information, and it is executable by anyone. We embed a publicly-verifiable cryptographic signature into LM output using rejection sampling and prove that this produces unforgeable and distortion-free (i.e., undetectable without access to the public key) text output. We make use of error-correction to overcome periods of low entropy, a barrier for all prior watermarking schemes. We implement our scheme and find that our formal claims are met in practice. </p>

Incoming regulation on AI such as the EU AI act, requires impact assessment and risk management to ensure fairness, accountability, and provide transparency for “high-risk” AI systems. This seems to require that companies provide unfettered access to a third party auditor who will provide a “seal of approval” before an AI system can be deployed. This often creates a tension between companies trying to protect trade secrets and auditors who need “white box” access to the data and models. In this talk, we examine how cryptography can, not only help resolve this tension, but additionally provide stronger transparency guarantees to the end user. The talk will consist of two parts: 1) An overview of the AI Policy landscape tailored to a cryptographers. The goal of which is to "distill" policy demands into research questions that cryptographers can tackle. 2) Next we will present our construction for "zero-knowledge proofs of training" and discuss challenges and lessons that were learned along the way. The technical paper "Experiment with Zero-Knowledge Proofs of Training" was accepted at CCS 2023.

Consider a coin tossing protocol in which n processors P_1,...,P_n agree on a random bit b in n rounds, where in round i P_i sends a single message w_i. Imagine a full-information adversary who prefers the output 1, and in every round i it knows all the finalized messages w_1,...,w_{i-1} so far as well as the prepared message w_i. A k-replacing attack will have a chance to replace the prepared w_i with its own choice w'_i \neq w_i in up to k rounds. Taking majority protocol over uniformly random bits w_i = b_i is robust in the following strong sense. Any k-replacing adversary can only increase the probability of outputting 1 by at most O(k/\sqrt{n}). In this work, we ask if the above simple protocol is tight. For the same setting, but restricted to uniformly random bit messages, Lichtenstein, Linial, and Saks [Combinatorica'89] showed how to achieve bias \Omega(k/\sqrt{n}) for any k \in [n]. Kalai, Komargodski, and Raz [DISC'18, Combinatorica'21] gave an alternative polynomial-time attack when k \geq \Theta(\sqrt{n}). Etesami, Mahloujifar, and Mahmoody [ALT'19, SODA'20] extended the result of KKR18 to arbitrary long messages. In this work, we resolve both of these problems. - For arbitrary length messages, we show that k-replacing polynomial-time attacks can indeed increase the probability of outputting 1 by \Omega(k/\sqrt{n}) for any k, which is optimal up to a constant factor. By plugging in our attack into the framework of Mahloujifar Mahmoody [TCC'17] we obtain similar data poisoning attacks against deterministic learners when adversary is limited to changing k=o(\sqrt{n}) of the n training examples. - For uniformly random bits b_1,...,b_n, we show that whenever Pr[b=1]=Pr[\sum b_i \geq t]=\beta[t]_n for t \in [n] is the probability of a Hamming ball, then online polynomial-time k-replacing attacks can increase Pr[b=1] from \beta[t]_n to \beta[t-k]_n , which is optimal due to the majority protocol. In comparison, the (information-theoretic) attack of LLS89 increased Pr[b=1] to \beta[t-k]_{n-k}, which is optimal for adaptive adversaries who cannot see the message before changing it. Thus, we obtain a computational variant of Harper's celebrated vertex isoperimetric inequality.