Optimal Strategies Against Generative Attacks
Authors: Roy Mor
Erez Peterfreund
Matan Gavish
Amir Globerson
Venue:  (2020)

Abstract: Generative neural models have improved dramatically recently. With this progress comes the risk that such models will be used to attack systems that rely on sensor data for authentication and anomaly detection. Many such learning systems are installed worldwide, protecting critical infrastructure or private data against malfunction and cyber attacks. We formulate the scenario of such an authentication system facing generative impersonation attacks, characterize it from a theoretical perspective and explore its practical implications. In particular, we ask fundamental theoretical questions in learning, statistics and information theory: How hard is it to detect a "fake reality"? How much data does the attacker need to collect before it can reliably generate nominally-looking artificial data? Are there optimal strategies for the attacker or the authenticator? We cast the problem as a maximin game, characterize the optimal strategy for both attacker and authenticator in the general case, and provide the optimal strategies in closed form for the case of Gaussian source distributions. Our analysis reveals the structure of the optimal attack and the relative importance of data collection for both authenticator and attacker. Based on these insights we design practical learning approaches and show that they result in models that are more robust to various attacks on real-world data.

Published as a conference paper at ICLR 2020
OPTIMAL STRATEGIES AGAINST GENERATIVE ATTACKS
Roy Mor
Erez Peterfreund
Tel Aviy University
The Hebrew University of Jerusalem Jerusalem, Israel
Tel Aviv, Israel
Matan Gavish
Amir Globerson
The Hebrew University of Jerusalem Jerusalem, Israel
Tel Aviv University
Tel Aviv, Israel
ABSTRACT
Generative neural models have improved dramatically recently. With this progress comes the risk that such models will be used attack systems that rely on sensor data for authentication and anomaly detection. Many such learning systems are installed worldwide, protecting critical infrastructure or private data against mal- function and cyber attacks. We formulate the scenario of such an authentication system facing generative impersonation attacks, characterize it from a theoretical perspective and explore its practical implications. In particular, tal theoretical questions in learning, statistics and information theory: How hard is it detect "fake reality"? How much data does the attacker need to collect before it can reliably generate nominally-lookin artificial data? Are there optimal strategies for the attacker the authenticator? We cast the problem as a maximin game, characterize the optimal strategy for both attacker and authenticator in the general case, and provide the optimal strategies in closed form for the case of Gaussian source distributions. Our analysis reveals the structure of the optimal attack and the relative importance of data collection for both authenticator and at- tacker. Based on these insights we design practical learning approaches and show that they result in models that are more robust to various attacks on real-world data.
ask fundamen-
INTRODUCTION
Generative models have attracted considerable attention since the introduction of Generative Adver- sarial Networks (Goodfellow et al., 2014a)). Empirically, GANs have been shown generate novel data instances that resemble those in the true distribution of the data. The success of GANs also comes with the risk that generative models will be used for attacking sensor-based security systems. One example is identity authentication systems, where an individual is identified via her images, and GANs might be able to generate such images to gain access (Thies al. 2016). Another anomaly detection systems protecting critical infrastructure. As demonstrated by recent cyber-attacks (no- tably the Stuxnet attack) sensors of these systems can be hijacked, so that GANs can be used to generate "normal" looking activity while the actual system is being tampered with. The latter is, in fact, new form man-in-the-middle attack.
Our goal here is to construct a theoretical framework for studying the security risk arising from generative models and explore its practical implications. We begin with simple key insight. the attacker (i.c., the generative model) has unlimited observations of the source it is trying to imitate, it will be able to fool any authenticator. On the other hand, the attacker has access to fewer sensor observations than the number of fake observations it needs to generate, it seems intuitively clear that it cannot always succeed (as we indeed prove in Sec. 4 Therefore, the optimal defense and attack strategies depend crucially on the amount of information available to the attacker and authenticator.
Motivated by the above insight, we cast the authentication setting as a two-player maximin game (authenticator vs. attacker) where all observations finite. Specifically, there are three key obser-

---

Published as a conference paper at ICLR 2020
vation sets to consider: those available to the attacker, those that the attacker needs to generate, and those available to the authenticator when designing the system. Our goal is to understand how these three information sources determine the optimal strategies for both players. Under the realistic as- sumption that cyber attackers are sophisticated enough to play optimal or close to optimal strategies, characterization of the maximin authentication strategy can be of significant value.
We prove several theoretical results characterizing the optimal strategy for both players. These results highlight the role played by the available observations as well as the functional form for an optimal attacker and authenticator. We refer to the setting above as "GAN in The Middle" (GIM) due its similarity to "man in the middle" attacks. After describing our theoretical results, we show how to learn both authenticator and attacker policies in practice, where both are based on neural architectures. Our GIM method can be applied to multiple practical problems. The first is building an authentication system that is robust to impersonation attacks. The second is build building a data generating mechanism that can generate novel data instances. Finally, we evaluate the method empirically, showing that it outperforms existing methods in terms of resilience to generative attacks, and that can be used effectively for data-auummentation in the few-shot learning setting.
PROBLEM STATEMENT
We begin by motivating our problem and formulating it as two-player zero-sum game. As a sim- ple illustrative example, consider a face authentication security system whose goal is to maximize authentication accuracy. The system is initialized by registering k images of an individual (the "source"), whose identity is to be authenticated. At test-time, each entity claiming to be @ is re- quired to present the system of its images, and the authentication system decides whether the entity is 0 or an impersonator. We let m denote the maximum number of "leaked" images any at- tacker obtained. We observe that if an attacker obtained m > n images of 0, it can present n of those images. Thus the observations generated by the attacker are indistinguishable from ones generated by 0, leading to failure of the authentication system (see Sec. 4.2 below). Hence, the number of images of that the attacker obtains and the size of the authentication sample are of key importance.
We now turn to formally stating the problem.
Notation. The set of possible observations is denoted by X. Let H denote the known set of possible sources 0, where each source 0 e H is defined by probability density Sa. and an ob- servation of a source 0 H is an X'-valued random variable with density So- We assume that subsequent observations of the source are IID, so that n sequential observations have density 1f (xi,..., ) == II;-, fo(a;). We allow 0 to be sampled from known distribution Q on H and denote the corresponding H-valued random variable by e. In what follows we will denote the number of observations leaked the attacker by m, the number of "registration" observations available to the authenticator by k and the number of observations required at authentication by n (these may be generated by either the attacker or the true source).
The Authentication Game. The game begins with random source θ being drawn from H accord- ing to Q. The authenticator first receives information about the drawn source, and then chooses a decision rule for deciding whether given test sequence E X is an authentic sequence of obser- vations sampled from f(() or fake sequence generated by the attacker. Formally, the authenticator learns about the source by seeing k IID "registration" observations A AA...... As f(()) The set of all possible decision rules is then D X* X {0, 1} (where a decision of 1 corresponds to the true source and 0 to an attacker). After the authenticator fixes its strategy, the attacker can seek the best attack strategy. We assume that the attacker has access m "leaked" IID observations Y .I....,,. Ym ~ f((m)) as information about the source 0. Then it generates an attack sequence X E X² and presents it to the authenticator, which uses its decision rule to decide whether X is an authentic sequence of observations sampled from (()) or a fake sequence generated by the attacker. Formally, the strategy set of the attacker is all functions g x A(X"), where A(X") is the set of probability distributions over X"", and gxly is the associated conditional probability density. We note that the set H. the parametric family fo, and the prior probability Q are known to both players. Also, note that the leaked sample Y revealed to the attacker is not available to the authenticator, and the "registration" sample A is not available to the attacker.
The goal of the authenticator is to maximize its expected accuracy, and the goal of the attacker is to minimize it (or equivalently maximize its success probability). We define the utility (payoff) of
2

---

Published as a conference paper at ICLR 2020
the game the expected prediction accuracy of the authenticator. To define expected accuracy consider the case of equal priors for attack and real samples Formally, for a pair of strategies (D,G) and a specific source 0, the expected accuracy of the authenticator is then:
1
V(0, D,
= 2 A By- By
[EX-
[D(A, (D(A, + Ex- - D(A,X)]
(2.1)
2
Since this utility only depends on 9 in the second term, minimizing is equivalent to G maximizing its success probability. To obtain the overall utility for the authenticator, we take the expected value w.r.t θ and define gD) = ( D, Finally, we arrive at the following maximin game:
Vgame= = max min (DD,g) DEL GEG
(2.2)
where D, G are the sets of all possible authenticator and attacker strategies, respectively. In Sec. we show that this game has a Nash equilibrium, we characterize the optimal strategies and game value in general, and find them in closed form for the case of Multivariate Gaussian sources.
3 RELATED WORK
Adversarial hypothesis testing (AHT): Hypothesis testing (HT) is a rich field in statistics that studies how one can detect whether sample was generated by one of two sets of distributions. A variant of HT that is related to our work but distinct from it is AHT (c.g.. see Braadão et al. 2014
Barni & Tondi 2013b a 2014, Bao et al., 2011 Zhou et al.) 2019; Brückner & Scheffer 2011
Brückner et al. 2012). These works describe an HT setting where the sample is generated by one of
two hypotheses classes, but is then modified by an adversary in some restricted way. E.g.. in Barni & Tondi (2013b a 2014) the adversary can change the sample of one class up fixed distance (e.g.. Hamming)- Given the quality of current generative models and the rapid pace of progress, when considering on an attacker is on the information it has. This is not captured by prior work since it assumes that the adversary has a restricted strategy set. In contrast, our work considers novel problem setting where both players are not limited in their strategy set in any way. This leads to novel analysis that focuses on the dependence on the finite information available to each player (m, n, n.)
impersonation attack, it seems that the only relevant restriction one can assume
Adversarial Examples: It has been observed (Goodfellow et al. 2014b) that deep learning models can be very sensitive to small changes in their input. Such "misleading" inputs are known as ad- versarial examples and much recent work has analyzed the phenomenon (yyas et al.] 2019; Shamir cct al. 2019 Zhang et al., 2019), addressed the problem of robustness to these "Moosavi-Dezfoo ct al.
2016 Papernot et |0.7| Yuaa et al. 2017), and studied when robusntess can be certified |Raghunathan et af.] 2018) WWon et 20)8). The setting of robust classification in the presence of adversarial examples can also be thought of specific case of AHT (see above), where classi- fier is required to predict the class of an observation that could have been perturbed by a restricted adversary (Wong et al., 2018 2019) or generated by an adversary limited generating examples that will be classified correctly by humans (Song et al. 2018). In contrast, in our setting the attacker not limited in any way, nor does it have another utility in addition to impersonating the source. Furthermore, in ad adversarial examples, there is no notion of limited information for the adversary, whereas our work focuses on the dependence of the game on the information available to the players (sample sizes n. m, k).
GAN: The GAN model is a game between a generator and a discriminator. While our concept of generative attacks is inspired by GAN, it is very different from it: a successful GAN generator is not necessarily a successful attacker in our setting, and vice-versa (e.g., given sufficiently expressive generators and discriminators, GANs can "memorize" the training data, and thus the discriminator will perform at chance level P Such a discriminator will not be useful as a defense against generative attacks). Unlike GANs, in our setting, sample sizes of key importance. Thus, our attacker will not memorize the data it sees, as this will be detected when generating n >> m. examples.
Conditional GANs: In conditional GANs (Mirza& & Osindero 2014) the generator uses side infor- mation for generating new samples. The attacker in our approach (analogous to GAN generator) has input, but this input is not available to the authenticator (analogous to GAN discriminator). Thus,
We give equal prior prohability to attack and real samples for simplicity and clarity, and since this is common in GAN formulations. All results can be trivially generalized to any prior probability for attack.
IIf the generator is not expressive enough, the learned GAN may have small support (Arora al. 2017
3

---

Published as a conference paper at ICLR 2020
the objective of the learning process is fundamentally different.
Few-shot learning and generation: Our work relates to few-shot learning
Snell et al. 2017
Vinyals al. 2016 Finn et al.] 2017: Lake et al. 201I, Koch et al., 2015) and fewtshot genera-
tive models (Rezende et al. 2016] iZakhrrvv et al. 2019 Lake et al., 2015 Edwards & Storkey
2017 Hewitt et al. 2018) the sense that both authenticator and attacker need to learn from limited set of observations. However, in our setting the authenticator is required to predict whether sample came from the true source or an attacker impersonating the source while taking into con- sideration the amount of information both players have. These are notions that are not part of the general few-shot learning setup. Also, in prior work on few-shot generation, the generator is either measured through human evaluation (Lake et al. 2013) or trained to maximize the likelihood of its generated sample (Rezende et al. 2016) Edwards & Storkey 2017 Hewitt et al., 2018). In contrast, in our setting the attacker's s objective is to maximize the probability that its generated sample will be labeled as real by an authenticator. To this end, we show that the attacker must consider the sample sizes m, n, k. which the generative models in prior work do not account for. Furthermore, we show in Sec. [.4] and in Figures 6 that the maximum likelihood (ML) solution is indeed sub-optimal in our setting.
Image to image translation: Several GAN models have been introduced for mapping between two domains (Zhu et al., 2017; Huang et al. 2018 Isola et al. 2017 Wang al.] 2017: Park al. 2019). This relates to our work since the attacker also needs to learn to map the leaked sample to an attack sample. However, in our setting the mapping not a different domain but rather to other images from the same distribution, which results in a different objective.
Data Augmentation: Generative models have also been used for augmenting data in supervised learning. and in particular few-shot learning (Koch et al.) 2015: [Sell et al.) 2017;; Vinyals et al.) 2016 Lake et al., 2011). One such approach is Data Augmentation GAN (DAGAN) (Antoniou et al. 2018), which takes as input an image and generates new image. It relates to our framework in the limited case of m = 1, = 2, l = 1, in the sense that the generator's ss objective is to map one image two. However, in DAGAN the only goal of the discriminator is to improve the generator, and the generator is limited to the functional form of adding a new image to the existing one, which sub-optimal attack strategy, as be seen from the Gaussian case of our problem.
4 THEORETICAL RESULTS
In this section, we study the game defined in Eq. 2.2 First, in Sec. 4.1 we show the existence of a Nash equilibrium and characterize the optimal strategies for both players. Specifically, we show that the optimal attacker strategy minimizes a certain divergence between the source and the attacker's conditional distribution of X given A. Next, Sec. 4.2 shows that when there are more leaked samples m than generated samples n, the authenticator will fail. Finally, in Sec. 4.3 we provide closed-form solution for both attacker and authenticator for the case of multivariate Gaussian distributions and analyze the effect of the dimension of the observations and the sample sizes m. n., and k. Proofs are provided in the appendix.
4.1 CHARACTERIZING THE OPTIMAL STRATEGIES
We begin by showing that the game defined in Eq. admitss a Nash equilibrium. Namely, Theorem below shows that there exists pair of strategies (D*, g*) that satisfy:
max min V V(D,)) = min max V (D, = V(D*.g*) 9eG DED
(4.1)
DED GeG
Theorem 4.1. Consider the attacker G* defined by:
I. (fxI((E|A)- - [xla(x|AA] dx
9XIY E argmin EA-SA gXlr Where, fa(a) = Seen Q(0) (()) (a)d0 is the marginal density of A. Qeta is the poste- rior over H given A, and frla(yla) = Seeu s(()) (e)))od00 Also, fxla(()a)) = Soen f(1) (B)))()) and 9x]a(z]a)- = -Sex x (xlu) (rll))rru(valadd are the conditional densities of X given A, generated by the source and the attacker respectively. Consider the au- thenticator defined by D* (a,x) = fxla(=)a)= 9x1 (xlaa) where is the indicator function.
(4.2)
Then (D*,9*) g.)) ) is solution of Eq. 2.2 that satisfies Eq.
4.1
4

---

Published as a conference paper at ICLR 2020
The proof (see Sec. D follows by first showing that since D(a, .²) E {0, 1), holds that for any G. the optimal authenticator strategy is a MAP test between the two hypotheses (true source or attacker). We then show that given D*, the game objective for G becomes Eq. Namely, the optimal attacker minimizes the & distance over the space X x X between the true source's conditional distribution of X given A, and its own. Therefore, since the proposed G minimizes Eq. 4.2 by definition, it
holds that ming VDD*, g) = V V(D*, g*) = maxp (D) and it follows that D*, G satisfy Eq. 4.1
4.2 REPLAY ATTACKS: AUTHENTICATION FAILURE FOR 7 & m
When n & m, the attacker generates a number of observations that is at most the number of ob- servations it has seen. Intuitively, an optimal attack in this case, is to simply "replay" a subset of size n from the m observations. This known as a replay-attack (Syverson] 1994). This subset constitutes IID sample of length of the observed source, and is, therefore, a legitimate "fresh" sample. In this case, it seems like the attack cannot be detected by the authenticator. Indeed is easy to show using Theorem 4. that this attack is optimal and therefore for & m have: maxDeD minges V(D,g) 0.5 (see Sec.
4.3 THE GAUSSIAN CASE
We now turn to the case of multivariate Gaussian distributions where we can find the exact form of the attacker and authenticator, providing insight into the general problem. Specifically, we consider the setting where the source distributions are d-dimensional multivariate Gaussians with an unknown mean and known covariance, and the prior Q over H the improper uniform prior We assume > m to keep the problem non-trivial. Let the observations be d-dimensional Gaussian vectors with a known covariance matrix Σ Rddd and an unknown mean vector 8 e Rd. The set of possible sources H becomes Rdd the Gaussian mean vectors. For any sample of examples E Raxd we let 2; denote the i'th example, and 2 - ET_ 2; denote the sample mean. Finally, for any E Rd, B Rdxd, we define ||u| v² Bv. The following theorem gives a closed-form solution for both attacker and authenticator for the game defined in Eq. 2.2
Theorem 4.2. Define 5 = m/n & and let p == m/ki Consider the cttacker G* defined by the following generative process: Given leaked sample Y E IRmx G* generates sample X E R
as follows: it first samples n vectors WI,..., Wn üd (O,EE) and then sets: X₃ = W: W + +Y. Define the authenticator D* by:
D* D*(axz) 2), =1 ||2 aa-
d + p) (1+ 1
log p 1 p 8
(4.3)
n(1 - 8)
Then (0* is a solution of Eq.
2.2 that satisfies Eq.
4.1
The proof (see Sec. starts by showing that Va > 0, given D(a, 2) -[| -al < a], the optimal strategy for i to set 5 = ÿ with probability (as done in g*). To prove this, we first use the Prekopa-Leinller inequality (Prékopa 1973) to show that in this case G's maximization objective is log-concave. We then show that any G that satisfies F = ÿ with probability 1 is a local extremum, and since the objective is log-concave it follows that it is the global maximum. We continue by showing that given g*, the proposed D* is optimal. To do so, we first find the distribution of Go's attack sample using the Woodbury matrix identity, and then show that D* indeed the optimal decision rule. Finally, using the max-min inequality, this implies that (D* g*) satisfy Eq. 4.1
There are several interesting observations about the above optimal strategies. Perhaps the most intuitive strategy for the attacker would have been to sample n elements from a Gaussian with mean expectation, this sample would have the correct mean. However, this turns out to be sub-optimal, as can be seen in Figures[[clande ( (we refer to this as an ML attack. See Sec. F.4 in the appendix for the derivation and visualizations). Instead, the optimal attacker begins by drawing an IID sample W from Gaussian distribution with mean 0, and then "forces" the sample mean to be exactly by shifting the sample points by Y - W. This optimal attacker
Y and the known covariance
Similar results can be derived for the conjugate prior case, namely, proper Gaussian priors.
5

---

Published as a conference paper at ICLR 2020
strategy can be viewed as matching the sufficient statistics of the leaked sample Y in the generated sample X. The optimal authenticator is a MAP test for the optimal attacker, as in Theorem 4.1
As corollary to Theorem 4.2 we obtain the value of the game (i.c., the accuracy of D*).
Corollary 4.3. Define å and p as in Theorem 4.2
Then the game value for the Gaussian case is:
2(1 (1)
1 1 7 21(
d d( 111+/ p)
1+ 1
( /d d
log 1 1
log
(++p)
5 5+p)
(4.4)
2
2 2(1 8)
8
Where y is the lower incomplete Gamma function, and is the Gamma function.
The proof (see Sec. F follows by showing that the test statistic used by D* is Gamma distributed. Fig. [ demonstrates several interesting aspects of the above results. First, Fig. la shows that the authenticator accuracy improves as n (the size of the test sample) grows. Furthermore, accuracy also improves as the dimension d grows, meaning that for a specified authentication accuracy, the required ratio n//m becomes smaller with the dimension d. This is a very encouraging result since although this dimensional dependency is proved only for Gaussian sources, it suggests that for real- world high-ding dimensional sources (e.g., faces, video, voice, etc.) the authenticator can achieve high accuracy even when requiring small (and practical) authentication sample.
Intuitively it may seem like authentication is impossible when the authenticator has less data than the attacker (i.e., m k). Surprisingly, this is not the case. As can be seen in Fig. [b even when m k, the authenticator can achieve non trivial accuracy An intuitive explanation of this phenomenon is that the test statistic used by the authenticator is estimation, has higher variance when X is generated by an attacker than when X is generated by the true source. This, in turn, allows the authenticator discriminate between the hypotheses.
Ali. which, due to the variance in the attacker
A closed-form solution for the general case remains an open problem. We believe that solving for Gaussians is an important step forward, since it exposes interesting structural properties of the solution, which we use in practice. Furthermore, if G has an encoder-decoder structure, it is not unreasonable that the source distribution in latent space can be approximately Gaussian (as in VAE).
GAN IN THE MIDDLE NETWORKS
So far we explored the general formalism of authentication games. Here we consider specific archi- tectures for D and g. As in GAN based models (Mirza & Osindero| 2014 Mescheder et al. 2018 Karras et al. 2018 b). we use neural nets to model these, while using insights from our theoretical analysis. Below we provide implementation details for the GIM model (see Sec. H and code for more details). In our analysis, we considered the non-differentiable zero-one loss since it is the real accuracy measure. In practice, we will use cross-entropy used in most GAN approaches.
Authenticator Architecture: The authenticator is implemented as a neural network D(a, x) that maps from source information sample a E x and test sample x E X probability that the test sample came from the true source. Our framework does not restrict the authenticator to any specific function type, but in practice one must implement it using some model. We recall that our theoretical results do suggest certain functional form. The Gaussian results in Sec. 4.3 show that the optimal authenticator is test on the sufficient statistic of the source parameters. Motivated by this result, and in the spirit of Siamese networks (Koch et al. 2015 Chopra et al. 2005). we sider the following form for the authenticator. We define a function To that maps a sample to a fixed sized vector, analogous to the sufficient statistic in the theorem. We apply To to both and x. Then, these two outputs are used as input to a comparison function a which outputs a scalar reflecting their similarity. Thus the authenticator can be expressed as: D(a, x) (a), TT())).
Attacker Architecture: The attacker is implemented as a stochastic neural network ((v) that maps a leaked sample y E X to an attack sample x X". Our theoretical results suggest a certain functional form for this network. The Gaussian analysis in Sec. 4.3 shows that the optimal attacker generates sample whose sufficient statistic matches that of the leaked sample. Motivated by this result, we consider the following functional form for the attacker. First, it applies a function T/ that maps the leaked sample Y to a fixed sized vector (Y), analogous to the sufficient statistic the
*See Sec. C in the appendix, for additional figures showing that the dimension grows, the expected
accuracy goes

---

Published as a conference paper at ICLR 2020
theorem. It then draws random latent vectors W1..... Wn, and matches their mean to the leaked sufficient statistic to obtain the latent vectors Wi. Namely it sets W = W; W + -Y)(Y) as done in Theorem 4.2 Finally, it uses a decoder function yp that maps each latent vector W to the domain X. Thus, the attacker can be expressed as: g(Y); = pW; W + Ty(Y)) Vi E [z]] Optimization Details: Each iteration begins when source 0 is chosen randomly from the set of sources in the training dataset (c.g., a person to be authenticated). Samples A, Y, .e are drawn from the set of examples available for 0, where X9 represents test sample from 0. Then, given leaked sample Y, the generator 9 generates a fake sample Xg. passes it to 'D and suffers the appropriate loss. Finally, D receives as input the source information sample A, outputs a prediction for each of the test samples Xo, Xg. and suffers the appropriate loss. Optimization is done via gradient ascent on authenticator parameters and descent on attacker parameters, as is typical for GAN problems.
6 EXPERIMENTS
We next evaluate our method empirically. In all experiments, we use the model described in Sec. We optimize the model with adversarial training, using the loss suggested by Mescheder et al. (2018 and Adam (Kingma Ba 2015). Our implementation is available https: //git//giuttt thub. com/ roymor1/Opt. ma St ther implementation details. Gaussian sources: For the case of Gaussian sources, arrived at complete characterization of the solution in Sec. 4.3 Thus, we can learn the models using our GIM algorithm and check whether it finds the correct solution. This is important, as the GIM objective is clearly non-convex and GANs are generally hard to train in practice and lack convergence guarantees (Mescheder et al.) 2018). We all experiments using multivariate Gaussian with Σ Ia. and in each game the source mean was drawn from the prior distribution Q = NO0, 107a). This approximates the im- proper uniform prior since the prior has much larger variance than the sources. Fig. Ia shows the empirical game value compared with the theoretical one as function of the test sample size n, for fixed m 1, h 10, and di different values of It can be seen that there is an excellent between theory and experiment.
wnt.rggginnntteerrat....mm veAttacks wtw.enneteeetttttttttt....
Also, see Sec. H for fur-
10
1.0
10
0.0
attarkir
0.9
10"
Caute Vanu
0.8
10-4
0.0
0.65
10-2
0.00
10
0.55
20
40
50
100
150
10
0.2
0.4
0.6
0.6
0.5
3.50
10
8-
m/n
14/99
(a)
(b)
(c)
Figure 1:
Game value (expected authentication accuracy) for the Gaussian case. (a) comparison between
empirical and theoretical game value for different d values (m 1, 10). Solid lines describe the theoretical game values whereas the markers describe empirical accuracy when learning with GIM model. (b) Thcoretical game value function of 5, P (see Corollary 4.3) for d 100. cc) Empirical accuracy of
an optimal authenticator against two attacks: the thcoretically optimal attack g* from Theorem [4.2 and a
maximum likelihood (ML) attack (See See. F.4) for the Gaussian
It can be seen that the ML attack is
inferior in that it results in better accuracy for the authenticator, as predicted by our theoretical results.
Authentication on Faces and Characters: We next evaluate GIM in an authentication setting on two datasets: the VoxCeleb2 faces dataset (Nagrani et al. 2017 Chung & Zisserman, 2018). and the Omniglot handwritten character dataset (Lake et al. (015). Additional information about the Our goal to check whether the GIM authenticator is more robust to generative attacks than state of the art authentication system. To evaluate this, we consider several attackers: 1) A "random source" attacker (RS): a naive attacker that ignores the leaked sample Y. It simply draws random source from the dataset, and samples n real images of that source. From the authenticator's perspective, it's equivalent to a sample version of the verification task (Koch et al. 2015 Schroff al. 2015 Deng et al. 2018), in
datasets, splits, and modeling details provided in GoctiiossGaandlle
7

---

Published as a conference paper at ICLR 2020
Table 1: Accuracy GIM and baselines against attacks, Avg ace denotes average over all attacks.
Authenticator
Dataset
k
RS
Replay
GIM
Avg acc
GIM
VoxCeleb2
5
5
0.897
0.837
0.822
0.852
ArcFace
VoxCeleb2
5
0,998
0.598
0.526
0.707
GIM
Omniglot
5
0,912
0.942
0.868
0.907
Siamese
Omniglot
5
0.994
0,509
0.785
0.763
which agent is presented with pair of real images and needs to decide whether they are from the same source or not. 2) Replay attacker (Replay): an attacker which, upon seeing a leaked sample y, draws random images of the leaked sample (with replacement). 3) A GIM attack, which is the "worst case" attacker G, learned by our GIM model.
For VoxCeleb compare the GIM authenticator to the ArcFace method (Deng et al. 2018). which is currently state of the art in face verification. As baseline for Omniglot, we use the Siamese network suggested by Koch al. (2015), which achieves state of the art in the verification task on Omniglot. Results are shown in Table [ It can be seen that on average across attacks, GIM outperforms the baselines. The only attack for which GIM is inferior RS. This is not surprising as this is the objective that both baselines are trained for.
Qualitative evaluation of attacker: In Fig- we provide images generated by the GIM attacker for the test set of both Omniglot and Voxceleb. The images demonstrate qualitatively the strategy learned by the attacker. In the Voxceleb2 dataset, face images are drawn from a video of the person talking. Note that in real samples from the data, the attack sample varies in pose and expression and not in the background or clothing.
1
4
4
+
+
+
4
m
m
m
m
m
m
m
m
m
(a)
Figure 2: Images generated by the GIM attacker based one leaked image. In each row, the leftmost image the real leaked image, and the rest of the images are an attack sample generated by the GIM attacker. Voxecleb2 dataset. bb Omniglot dataset.
Finally, we use GIM for data augmentation in one-shot classification on Om- niglot. This done by using the GIM attacker generate more data for given class. We first train GIM on the training set with parameters m = 1, = 5, k = 5. Then, during both training and testing of one-shot classification, given an example, we use the attacker augment the single example available for each of the classes, by adding to it the from it. We use Prototypical Nets (Snell al. 2017) as the baseline model. We find that without using our augmentation method, Prototypical Nets achieve 95.9% accuracy on the test split, and with our method, they achieve 96.5%, which is similar to the improvement achieved by Antoniou et al. 2018) with Matching networks (Vinyals et al. 2016) the few-shot classification algorithm.
Data augmentation:
5 examples our attacker generated
7 CONCLUSIONS
We defined the notion of authentication in the face of generative attacks, in which generative model attempts to produce a fake reality based on observations reality. These attacks raise numerous in- teresting theoretical questions and are very important and timely from practical standpoint. We proposed to study generative attacks as a two-person zero-sum game between attacker and authen- ticator. In most general setup both attacker and authenticator have access finite set of
8

---

Published as a conference paper at ICLR 2020
observations of the source. We show that this game has a Nash equilibrium, and we characterize the optimal strategies. In the Gaussian version of the game, a closed form of the optimal strate- gies is available. A nice outcome of the analysis is that the game value depends through their ratios 5 m/n (i.e., the "expansion ratio" between attack and leaked sample sizes) and p m/k (i.e., the "information ratio" between the number of source observations available attacker and authenticator). As we show in Fig. [b] there is large range of values for which high accuracy authentication possible, and as d grows we observe that the high authentication accuracy region in the (5. p) plane grows sharply. We introduce the GIM model, which is practical approach learning both authenticator and attacker, and whose structure is inspired by our analysis. GIM achieves accuracy that is very close to the theoretical rates in the Gaussian case, and is also more robust to attacks when compared to state of the art authenticators on real data. Many theoretical and practical questions remain. For example, finding closed form optimal strategies for other distri- butions, and going beyond IID generation. The non IID setting is of particular importance for the problem of fake video (Thies et al. (2016) and audio (Arik et al. 2018) generation, which we intend to study in the future.
m, n, k only
ACKNOWLEDGEMENTS
This work has been supported by the Blavatnik Interdisciplinary Research Center (ICRC), the Feder- mann Research Center (Hebrew University) and Israeli Science Foundation research grants 1523/16 and 1186/18.
REFERENCES
Antreas Antoniou, Amos Storkey, and Harrison Edwards. Augmenting image classifiers using data augmentation generative adversarial networks. In Artificial Neural Networks and Machine Learning, pp. 594-603, 2018.
Sercan Arik, Jitong Chen, Kainan Peng, Wei Ping, and Yanqi Zhou. Neural voice cloning with few samples. In Advances in Neural Information Processing Systems, pp. 10040-10050, 2018.
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in generative adversarial nets (GANs). In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 224-232 JMLR. org. 2017.
Ning Bao, O. Patrick Kreidl, and John Musacchio. A network security classification game. In Game Theory for Networks 2nd International ICST Conference, GAMENETS 2011, Shang- hai, China, April 16-18, 2011, Revised Selecied Papers, pp. 265-280, 2011. doi: 1007/
978-3-642-30373-99.11 URL http:///bb..rgg1.1007777777 978
19
Mauro Barni and Benedetta Tondi.
hypothesis testing under adversarial con- ditions. In 2013 IEEE International Workshop Information Forensics and Security, WIFS 2013, Guangzhou, China, November 18-21, 2013, pp. 91-96, 2013a. doi: 10. 10110///FSS201. 6707800. UtL.https: http:////oooogg//////// 1109 /90/9//FFFF. 201 6707800
Mauro Barni and Benedetta Tondi. The source identification game: An information-theoree per- spective. IEEE Trans. Information Forensics and Security, 83)):5004433, 2013b. doi: 10. 109/ TIFS.2012.223733
1ttp://///1..1111111111010 2012.2237397
Mauro Barni and Benedetta Tondi. Binary hypothesis testing game with training data. IEEE Trans. Information Theory, 60(8):4848 4866, 2014. doi: 10. 10.1109/11:30142325577
https:
Fernando G. S. L. Brandão, Aram Wettroth Harrow, James R. Lee, and Yuval Peres. Adversarial hypothesis testing and a quantum stein's 's lemma for restricted measurements. In Innovations in
Theoretical Computer Science, ITCS 14, Princeton. NJ, USA, Jamuary 12-14, 2014, pp. 183-194, 2014. doi: 0211445/255499722554888 URL https: //oii wwt.o/gg///..oo /ttp:/.....01111.1///////5/77771
2554816

---

Published as a conference paper at ICLR 2020
Michael Brückner and Tobias Scheffer. Stackelberg games for adversarial prediction problems. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA. USA. August 21-24, 2011, pp. 547-555, 2011. doi: 10.1145/
(020408.2020433
org htt.hhtps::///. orge 100 1111///011111/2200010 2020499
Michael Brückner, Christian Kanzow, and Tobias Scheffer. Static prediction games for adversarial learning problems. J. Mach. Learn. Res., 13:2617-2654, 2012. bttp:////a acm. .cm.org/ org/
citation. cmw.:m-250322222222222
Sumit Chopra, Raia Hadsell, and Yann LeCun. Learning similarity metric discriminatively, with application to face verification. In IEEE Computer Society Conference on Computer Vision and Puttern Recognition, pp. 539-546, 2005.
Arsha Nagrani Chung, Joon Son and Andrew Zisserman. Voxceleb2: Deep speaker recognition. In Interspeech, 2018.
Jiankang Deng, Jia Guo, and Stefanos Zafeiriou. Areface: Additive angular margin loss for deep face recognition. arXiv preprint arXi:: 2018.
Harrison Edwards and Amos Storkey. Towards neural statistician. In International Conference on Learning Representations, 2017.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. CoRR, abs/ 030400 2017. URL http:::/arxivv..rg/a/ba.s
03400
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems, pp. 2672-2680, 2014a.
Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In International Conference on Learning Representations, 2014b.
Luke B Hewitt, Maxwell I Nye, Andreea Gane, Tommi Jaakkola, and Joshua B Tenenbaum. The variational homoencoder: Learning to learn high capacity generative models from few examples. In Proceedings of the Thirty-Fourth Conference on Uncertainty in Artificial Intelligence, pp. 988- 997, 2018.
Xun Huang and Serge J. Belongie. Arbitrary style transfer in real-time with adaptive instance nor- malization. In IEEE International Conference Computer Vision, pp. 1510-1519, 2017.
Xun Huang, Ming-Yi Yu Liu, Serge Belongie, and Jan Kautz. Multimodal unsupervised image-to- image translation. In Proceedings of the European Conference on Computer Vision, pp. 172-189, 2018.
Andrew Ilyas, Shibani Santurkar, Dimitris Tsipras, Logan Engstrom, Brandon Tran, and Aleksander Madry. Adversarial examples are not bugs, they are features. ArXiv, abs/1905.02175, 2019.
Phillip Isola, Jun Yan Zhu, Tinghui Zhou, and Alexei A. Efros. image-to-image translation with ditional adversarial networks. In The IEEE Conference on Computer Vision and Pattern Recog- nition, pp. 5967-5976, 2017.
Justin Johnson, Alexandre Alahi, and Li Fei-Fei. Perceptual losses for real-time style transfer and super-resolution. In European Conference on Computer Vision, 2016.
Tero Karras, Timo Aila, Samuli Laine, and Jaakko Lehtinen. Progressive growing of GANs for im- proved quality, stability, and variation. In International Conference on Learning Representations, 2018a.
Tero Karras, Samuli Laine, and Timo Aila. A style- generator architecture for generative adversarial networks. arXiv preprint arXiv:1812.049953 2018b.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference Learning Representations, 2015.
10

---

Published as a conference paper at ICLR 2020
Gregory Koch, Richard Zemel, and Ruslan Salakhutdinov. Siamese neural networks for one-shot image recognition. In ICML deep learning workshop, volume 2, 2015.
Brenden M. Lake, Ruslan Salakhutdinov, Jason Gross, and Joshua B. Tenenbaum. One shot learning of simple visual concepts. Proceedings of the 33th Annual Meeting of the Cognitive Science Society, 2011.
Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 150062666:13322133333 2015.
Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for GANs do actually converge? Proceedings of the 35th International Conference on Machine Learning, pp. 3478-34877 2018.
Mchdi Mirza and Simon Osindero. Conditional generative adversarial nets. arXiv preprint arXiv:1411.1784 2014.
Seyed-Mohsen Moosavi- Dezaooolii Alhussein Fawzi, and Pascal Frossard. Deepfool: simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference on com- puter vision and pattern recognition, pp. 2574-2582, 2016.
A. Nagrani, S. Chung, and Zisserman. Voxceleb: large-scale speaker identification dataset.
In Interspeech, 2017.
Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, 7. Berkay Celik, and Ananthram Swami. Practical black-box attacks against machine learning. In Proceedings of the 2017 ACM on Asia conference on computer and communications security, pp. 506-519, 2017.
Taesung Park, Ming-Yi Liu, Ting-Chun Wang, and Jun- Zhu, Semantic image synthesis with spatially-adaptive normalization. CoRR, abs/ 1bs//999,,7291,, 2019. URL /RLpp://aaxxx/ abs abs/1903. 07291
András Prékopa. On logarithmic concave measures and functions. Acta Scientiarium Mathemati- carum, 34:335-343, 1973.
Aditi Raghumathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial exam- ples. In International Conference Learning Representations, 2018.
Danilo Jimenez Rezende, Shakir Mohamed, Ivo Danihelka, Karol Gregor, and Daan Wierstra. One- shot generalization in deep generative models. In Proceedings of the 33nd International Confer- ence on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, pp. 1521 1529, 2016.
mlr Sa...press/vee (enesss/v8//rzendelll rtw//deeeeeddeeeeeee htmll
Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In The IEEE Conference on Computer Vision and Pattern Recognition, pp. 815- 823, 2015.
Adi Shamir, Itay Safran, Eyal Ronen, and Orr Dunkelman. A simple explanation for the existence of adversarial examples with small hamming distance. CoRR, abs/1901. 2019. URL U 901. 10861
//arxiv.org/ablliii
Jake Snell, Kevin Swersky, and Richard S. Zemel. Prototypical networks for few-shot learning. In Advances in Neural Information Processing Systems, pp. 4080-4090, 2017.
Yang Song, Rui Shu, Nate Kushman, and Stefano Ermon. Constructing unrestricted adversarial examples with generative models. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Gareett (eds.), Advances in Newral Information Processing Systems 31, pp. 8312-8323, Curran Associates, Inc.. 2018. URL http: /tttt:://papess/ wwwpeaaprsssippppe www. - 11152-constrru ruct wwg.errrotoononnnnenneerrireeeee aww.:etaaaadveeearraaaaaaaa.aaaa ott. ve-e pdf
Paul Syverson. A taxonomy of replay attacks [cryptographic protocols]. pp. 187 191, 07 1994.
ISBN 0-81 1881666230-1. doi: 10. N.1109/CSF..1994..111

---

Published as a conference paper at ICLR 2020
Justus Thies, Michael Zollhofer, Mare Stamminger, Christian Theobalt, and Matthias Nießner. Face2face: Real-time face capture and reenactment rgb videos. Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 2387-2395, 2016.
Oriol Vinyals, Charles Blundell, Tim Lillicrap, Koray Kavukcuoglu, and Daan Wierstra. Matching networks for one shot learning. In Advances in Neural Information Processing Systems, pp. 3630- 3638, 2016.
Ting- Ting-Chun Wang, Ming- Liu, Jun Yan Zhu, Andrew Tao, Jan Kautz, and Bryan Catanzaro. High-resolution image synthesis and semantic manipulation with conditional gans. CoRR, abs/1711.11585, 2017. URL httth:/p///xii//// wwwpxiii..rr...ooooooooo httgg/bb//11..111
Eric Wong, Frank Schmidt, Jan Hendrik Metzen, and J. Zico Kolter. Scaling provable adversarial defenses, In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Casa--eeaneee and R. Gamett (eds.), Advances in Neural Information Processing Systems, pp. 8400-8409, Curran Associates, Inc., 2018.
Eric Wong, Frank R. Schmidt, and Zico Kolter. Wasserstein adversarial examples via projected sinkhorn iterations. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pp. 6808-6817, 2019. URL http:
//proceddi ngs. www. press / http////////////// 9a html
Xiaoyong Yuan, Pan He, Qile Zhu, Rajendra Rana Bhat, and Xiaolin Li. Adversarial examples: Attacks and defenses for deep learning. CoRR, abs/1712.07107,, 2017. URL http:://////
arg/abs/1712. 07107
Egor Zakharov, Aliaksandra Shysheya, Egor Burkov, and Victor Lempitsky. Few-shot adversarial learning of realistic neural talking head models. CoRR, 0bss/1905.082333 2019. URL http:
//axxiv.oq/aabs 1905. 08233
Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric P. Xing, Laurent El Ghaoui, and Michael Jor- dan. Theoretically principled trade-off between robustness and accuracy. In Proceedings of the 36th International Conference on Machine Learning, ICML 9-15 June 2019, Long Beach, California, USA, pp. 1472-7482 2019. URL http://prroceedngg. mlr mir.press/vv7/ Zhang19p 9p.ng19p.55m html
Yan Zhou, Murat Kantarcioglu, and Bowei Xi. A survey of game theoretic approach for adversarial machine learning. Wiley Interdiscip. Rev. Data Min. Knowl. Discov, 9(3), 2019. doi: 10.1002/ widm. 1259. PRtLhttss///o.oooo
1002 wi 1259
Jun- Yan Zhu, Taesung Park, Phillip Isola, and Alexei A Efros. Unpaired image-to-image translation using cycle-consistent adversarial networks. Proceedings of the IEEE international conference computer vision, 2017.
12

---

Published as a conference paper at ICLR 2020
A INTRODUCTION TO THE APPENDIX
main paper. Sec. we provide visualization of the game setting. In Sec. C we plot the game value in the Gaussian case for different parameter values. In Sec. D we provide a proof for Theorem 4.1 in Sec. we formally state the theorem discussed in Sec. 4.2 and prove it, and in Sec. F we prove Theorem and also derive the game value for the sub-optimal "ML attacker". Finally, in Sections G details about the experiments and the implementation of GIM.
Here we provide additional information and proofs
we provide additional
B PROBLEM SETUP VISUALIZATION
Our problem setup is illustrated in Fig. for face authentication scenario. A source 0 (in this case an individual) generates IID observations (images). images are used by the authenticator to study the source which it aims authenticate. images "leaked" and obtained by attacker who wishes to impersonate the source and pass the authentication. At test time the authenticator presented with images that were generated either by the true source 0, by the attacker, and decides whether the entity that generated the images was the source 0 or an attacker.
Ap Ap fo
Source
X
Real / Fake
Authenticator
E
X un Xn=
Attacker
Figure 3: An illustration of the game described in the main text. An authenticator receives sample of images and needs decide whether these were generated by known source, or by an adversary that had access to leaked images. In order to decide, the authenticator is supplied with a sample of images from the real source.
C GAME VALUE VISUALIZATIONS
In corollary 4.3 we provide the game value (the expected authenticator accuracy) for the case of multivariate Gaussian sources. In this section, we present additional visualizations of the game value as function of the different parameters of the game. Fig. 4 visualizes the game value function and p, for different values (the observation dimension). å = m is the "expansion ratio" between the source information available to the attacker through the leaked sample and the size the attacker's 's attack sample. p I. observations available attacker and authenticator. One clearly that d, the observation dimension, grows large, so does the accuracy of the authenticator. Even for 8 values higher than 0.5, and p values which intuitively would give the attacker advantage (e.g., T 10).
m is the "information ratio" between the number of source
13

---

Published as a conference paper at ICLR 2020
Fig. 5 visualizes the game value function of 5 and 6, for different values of d (the observation dimension). Where < = a is the "information expansion" of the attacker with respect to the authen- ticator source information. Again, can clearly see that as d, the observation dimension, grows large, so does the accuracy of the authenticator.
&
d=1 1
d= 10
d= 100
d= 1000
10
10
10F
107
107
102
10'
102
10
10
104
104
0.9
10a
102
10
10
m//k
102
105
0.8
10
10
10:
P
10
10a
10
10
10-1
10-1
10
10"1
1
10-2
10"2
10"2
0.6
10-1
10-3
10-1
10-1
10-1
10-1
0.00
0.25
0.50 0.75
1.00
0.00
0.25
0.50 0.75 1.00
0.00
0.25 0.50 0.75 1.00
0.00
0.25
0.50 0.75
1.00
m. /n
Figure 4: Game value as a function of 5, p for different dimensions d.
10
10F
10
10f
102
1000
7.0
10
10a
10a
10a
10
10'
104
101
0.9
10
10a
30a
10a
10
102
102
102
0.8
n/k
30
104
102
10
10
109
10
102
10-1
10-1
10-1
10-9
10-2
10
10
10
10
0.00
0.25
050
100
10
0.00
0.26
0,3
675
100
10-1
0000
6db
6:50 0/5
1.00
10
0.00
0.2)
0.36
9.6
0.5
8
m/
/
Figure Game value as a function of 8, for different dimensions
D ADDITIONAL THEOREMS AND PROOFS FOR SEC. 4.1
We begin with some additional notation. Let
fa(a) = [ (()){( (()) (a)do
JBE
14

---

Published as a conference paper at ICLR 2020
denote the marginal density of A. Let Quja denote the posterior probability over H given A. That is:
Q(0)56 Q0)a(Ola)= = SVER Q(v) (a)dv (a)de
Q(0),f))(o)
fa(a)
Also, let [YJA: /x IX|A, denote the conditional densities defined by:
(rja(ula)
JBH 1 p( (w)0)
[x]a(<](a)
JOEH
9xla(z/a)
yexm 9x1y(alw).rja(xldddd
Lemma D.1. Let G be an attacker defined by the conditional probability distribution 9X Then
Va X x d best response strategy for D is:
D(a, [xx]a(x(a) 9xla(x]a]]
(D.1)
Proof. Given an attacker strategy 9x|y, the objective for D is given by:
argmaxE. ((9,
D
argmax Eg Q 1 E p
[D(A, (D(A,
+ y Ex -x-xxx D(A, xi]
D
argmax EAJA /A
Ey (T -(4A)_
D
S JEEN
argmax
fala)
+ D(a, x]] drda
D
Note that D can be optimized independently for each pair a, E 2 X", Hence, Va, x X* x 8 the objective is:
argmax (fxia())a)((a,²) + - x)]} ((a.))=(0.1)
And thus, the optimal decision rule for D is:
D(a,z) [fx]a(()a)> (xxxa(aa)
As required.
Lemma D.2. Va, X x let the strategy for D be defined by:
x(),x) [fx]a(z))a) > [x|a)=
Then G is best response strategy for G. iff it minimizes the & distance between the distributions fx|A: 9X\A over the spuce X X Namely:
I E argmin EA~sa
[fx]a()AA) [x(a(x]AA] dr
(D.2)
9XIY
Joxxn
15

---

Published as a conference paper at ICLR 2020
Proof. Let DD be defined as in Eq. D.1 the objective for g is:
argmin Ee 2
2
argmin Be 1n fx + -xx- (onts-onnnn-l1((-x)))) -(A,
9X1Y
argmin BA~sa [x-(axi(HH) -ox.aa/l.-... -DAAA)
9x1Y
aargmin 9XlY
dafa(a)
dæ + -
JEN
S de (fxal(fxi)
argmin
daf dafA(a)
(D.3)
9XlY
J0E
JBEZ"
[
argmmn
dafa(a)
del
+ (fx
2 JaEx*
xE
S dx -
argmin 9XIY
dafala)
JaEx
arrginn
dafA(a)
dæ (x](xx((z)))) -x(((((0))
9XIY
Jae
As required. Where in Eq. D.3 we used the definition of D.
Theorem 4.1
Consider the attacker defined by:
[s [[xIa(=|A)- - (xlA(x||
g
E argmin EA-SA
(D.4)
aXlV
and let G* be the corresponding map from xm to the set of probability distributions over X".
Consider the authenticator defined by:
D* = 1 fx]a(z(a) > (x1a)
(D.5)
where I is the indicator function. Then (D* Go) is a solution of Eq. 2.2 that satisfies Eq.
4.1
Proof. From Lemmas D.I D.2 have that maxp V(D, V(D* V*)* ming V(D* 9)
from which it follows that Eq. is satisfied and thus (D* g*)) is solution Eq. 2.2
E THEOREM AND PROOF FOR SEC. 4.2
Theorem E.1. For all n & m it holds that:
min V(Dg9) 0.5 DeD geG
Proof. Consider the attacker Geplay defined by the following generative process: Given a leaked sample Y e mxd Greplay generates a sample X e Raxd such that X; = Yi Vi [n]. (this is possible since we assumed & m). Namely, we have:
(xlr(xly) = I 5(x, v.)
16

---

Published as a conference paper at ICLR 2020
Where d is the Dirac delta. Thus Va, X
x":
(x|a(2la) =
(
yEAm
(
a0 (1)Qe)a(011)
yeam
DE7
{ d0
[ dy
8(z; [
JBE
i-1
d0Qe)a((1a))
[
dy 11 o(: - we dy' 1o 1om- (3))
J0E
yEAr
i=1
d0Q0)a(0(a)
dy 8(xz - -
JAH
(0 (2)
J0E
[x)(A(x(a)
Define:
Do(a, = Va, E X x x
Then according Theorem 4.1 fore:
Do, greplay) is solution of Eq. 2.2 that satisfies Eq. 4.1 and there-
max min V(D,g) -V Greplay)
Del GeG
Be-QB An 1(0) By mm
x (D(A) Ex~e(r[1 D(A, X)]
2
1
Be- A/ B. smmm
E Ex [0] + [x-
2
2
As required.
F ADDITIONAL THEOREMS AND PROOFS FOR SEC. 4.3
F.I NOTATION AND DEFINITIONS
In this section, consider the case where the sources are d-dimensional Gaussian vectors with known covariance matrix
CCT E ddxd and unknown mean vector Rd. That is, the set of possible sources is H. = Rd and given 0 E H. the associated probability density over the domain exp (x - (x-))
X I is fo(x) (2m) (x)
sample of n examples æ x is considered matrix x E Roxd where the first index represents the sample and the second represents the observation space, Rd Le., Zig E R is the i'th element of the i'th example in the sample r e nx
We continue with a few more notations that simplify the proofs. Given matrix Rxxd let und be the concatenation vector representing æ. Given a vector e IRd,
I. = [ .... =
we let 8an TT
or7 E Rnn be the concatenation of n copies of 0. Given a matrix Rd denote its mean along the sample dimension. For any matrix
E Rexd we let T =
n
21
B ddd we denote:
B
0
diag B,k)
E R kdxkd
17

---

Published as a conference paper at ICLR 2020
and
B
B
rep( B,
: B
E R
kd kd
B
Finally, we define strategies for both attacker and authenticator, which we prove in what follows to be the optimal strategies for the game.
Definition F.1. Let G denote atlucker defined by the following generative process: Given leaked sample Y E TRmxd, 9 generates an attack sample X Raxd as follows. first samples n. vectors WI...., Wn ld (0, and then sets:
X; = W W +Y
(F.1)
Also, let y denote its associated conditional probability. Definition F2. For any a E Rt,, let Do denote an authenticator defined as:
D)(a, 1|13 1-a-als- <a
Where T is the indicator function
F.2 TECHNICAL LEMMAS
Lemma F3. Let XI,... X2 id
N(,, Σ) Where μ E Rdd E Rdxd, Then
1 k X, N(p, 1 =
X
Proof. We begin by observing that X, N' (He,ks diag(E, k)). Let B = [Ta Ia] E dg and observe that X = BXc. Therefore, since this an affine transformation of a Gaussian vector have:
X NN(pe (diig(2)k))3)) NN 1 2)
As required.
Lemma F.4. Let X Rdd be Gaussian vector X N(H, E), and let Xen Rad be the concatenation of n copies of X. Then:
Xen ~ Nee,,,
Proof. Let
La
B
Radxd
La
and observe that Xe,. BX. Therefore, since this an affine transformation of Gaussian vector we have:
X ~ (BB, N ( rep( E,n))
As required.
Lemma F.5. Let 0 RRd, E E Rdxd represent the mean and covariance of a Gaussian distribution. Let X E Ra be random sample generated by the attacker defined in Def. F.1 Then:
X. ~ N(e diag(E, + rep(( n m EE n)) = N (ee..n
mn
18

---

Published as a conference paper at ICLR 2020
Proof. Observe that We (0,, Using Lemma
F33
get Y
No Σ and
observe that Wen rep(" = la, n) W Using Lemma define the following block matrices
R.4 get o. N N(0e, re)(E,n)). We
We Yon
Z
B [In re)p(la,)), Ind]
and observe that:
Z Z~V(
Ond
diag(E,n)
0 rep(E,
)
Onn
Note that X We
c, + Ven
BZ and therefore we get:
Ond Ocn
diag(E, Σ, n)
X N(B
B
BT)
rep Σ, m)
N 1 cn. diag (E, rep
nL (n= >
mn
As required.
Lemma F.6. Let CC & Rdxd represent the covariance of a Gaussian distribution, and consider the following covariance matrix:
V = diag(E,n) n) rep(( n m )E n)
Then its inverse is:
T- diag(E n)) n m
rep( E 1.))
n
and the determinant is:
det(w/) (=) (2)
d
m
Proof. We begin by defining the following block matrices:
Σ
U
E
I nddx
(F2)
La
V n - m
:
nnxd
(F.3)
Ta
19

---

Published as a conference paper at ICLR 2020
and note that rep(( -- ]_,n) = UVT Then:
=diigg [, n) + rep(( - }Σ, n))
=(diag(2; (2,)) + UV TATE
diog((i n) diag(2 2, (nnnn))() ULa V diag(E, n) v diag 22 n1
(0) diag(E=11 - diag(> (-- .n) + V diag E-1 n] - V dings E [_-,,,)
La
Pa
=diag(E-1.n)) -
(Ia +
m
[Td
Ta]
n m
717
TumL
Ia
la
Id
=diag(E
m71
La
T1
Σ
n2
Tum
La
Id
=diag(E ,1)
[
E-'
=diag(> .n)
rep(2 1n)
n²
As required. Where in (i) we used the Woodbury matrix identity, and in (ii) we used the inverse of a diagonal block matrix.
Next, we turn to find the determinant of V:
de =det(diag(E,n) + rep(( n m- >
)
mm
dde(ddiag) E, UV?)
(*) dedt(diag(I, () + V diag(E, U)
(e)) del(( + v ding(E= (n))
Σ
=det())" + n - m
[Ta
Ia] diag(E-1 .n)
1m
n Ia) m
(lle(E))dee((A.) (m))
=))
m
Where in (Mi we used the matrix determinant lemma, and in (iv) we used the determinant of diagonal block matrix.
Lemma F.7. Let
N(x,, ()) expl
20 (x
T- 1x [ ((z,u) Ra Rd
x
and define the function:
v(1)= =
dx 1((x (1)
JarRaa
Then (p)) is log-concavee over the space Rdd.
Proof. We begin by noting that the function (x- - (x- (1) is convex w.r.t both and μ,, hence its negative is concave, and thus, by definition the function:
1
expl-
202 (x - -- (x n4]
(F.4)
20

---

Published as a conference paper at ICLR 2020
log-cooee oog-concave w.nt z; ps. We now show that h(2, (4) is log-concave want both x and μ.. First, w.r.t J..
Let 5 E [0, 1], Ui, #22 E R", and observe that:
h(x, 8p1 + (1 - 8)222
expp
2r (x B1n (1 -31)))2 By1 (1 3)p2))1[x²> [ x < a]
()
8
(1- 9)
> expl
(r - -11 11)² T (x - (1)} expl
(x - 12)² I (x -2²)
20²
20²
1Ι Σ x < a|
(1)
expl 202 (I μ1) 2 1 - (z 11)} expl
(1 (3)
(x (22
1'' -22}
20²
E < al) 8 (11-" < a1)
=h(1,, (1), (1) M|,, u22 (1-8)
Therefore h( p)) is log-com cogcconavee w.r./ Where in (i) we used the log-concavity of the function in Eq. F4 and in (iz) we used the fact that [x 'z -i=--'z < a] E {0, 1}.
Now, w.r.t æ. Let 3 E [0, 1]. I1, 12 E R. Observe that for any convex function we have:
1 [g(xx) < a [g(22) < aa (- @ -1(((=)) < [ < <a]
= -1(((<1)
((22)) < aa]
(0) ([]g(1)) + (1 ())(22) a]
(00) 2 [qq(31 + (1 3)x2) al
Therefore [x= < a] is log-concave. Where in (i) we used the fact that [[((z) < a] E (0, in (ii) we used the fact that g(x1) < a g(x2) < a 8y(x1) + (1 - 3)((22) a, and (in)
used the convexity of q. Hence, observing h(,, n)) we have:
h(B11 + (1 (4)
= eeppl- 20 (Bxr + - (1-3) - (Bx1 + - -1--022-- - 11)
[[(3m] + (1 - 3)0²) T (Ba; + (1 - 3)xz) < <a]
(Bxr
(10)
expl B (I1 - 1) (x) 1n) expl (1 (1- 33)
(I2 11) r m}}
20
20"
[[3x] + (1 - ))x2)² T I - (8x1 + (1 - 3)xz) < <a]
expl B
202 (x m1) " x (r - 11)) expl - (1 - 3)
(x - 112) TI- (x=x)}
20²
(1 (I[ < a)) 8( 1 M 82 < (1))
=h(11,11) )1(2,11) (1-))
Therefore h(x, n1) is log-concave w.r.t.r Where in (dv) we used the log-concavity of the function in Eq. R4 and in (v) we used the log-concyvity of - x al.
Finally, by using Prekopa-Leindler inequality (Prékopa required.
1973) we have that vi(μ) is cog-ccncave, as
F.3 PROOF OF THEOREM
Lemma F.8. Consider the allacker G², defined in Def. authenticator against this attacker is:
F.1
The best response strategy for the
D* D*(a,z) x) = [|, alB < a*
Where:
a = d(m + =k)(n + k)
1(m= + k))
log
k2(n m)
m(n + k)
21

---

Published as a conference paper at ICLR 2020
Proof. The best response authenticator satisfies:
D* E Fargmax V(D.g)
DeD
argmax
Te To-QRR A- By y 10 ( + Ex-xxx((1]]-- - D(A, -arteannnli-iXAX-)- X)]
DED
argmax Ee A-16 [ x [D(A, X)] + E Ex-exie(1)) D(A,
DeDD
argmax R A..tt..... DEL
E N dagl(2 (D(A, + [x-NN(e.. D(A,
[ da
[ JEERMO drexpl 1 (a - -eckk) diag(E, k) (
argmax Be.q DED
Ocx)]l
JoRRM
2
expl- 2 (a Dan) diag(E,)) (
expl 7 (x- -,,,) - 0c,))]] (a,
DD can be chosen independently for each pair (a, x) E x* Xx. Therefore, for any (a,z) E 2 xx" the decision rule for D(a, x) is:
n
d0Q(0) expl expl- 51(a- [(o0- Dom)) 0on)) diag(L,n)) Dc,n)+
m BBER
(a- (a,k) diog Σ, (a-0x))11
[ d0Q(() expl [(x 0e,n) T Ben) (a- 0c,k) diag(E, - k)- (a- kcxx]lb
BER4
Observing the LHS integral and using the improper uniform prior assumption we have:
S doQ(0) expl -
---1~=1(1 1 21(x0 O Pc,n) (e.n)"digge diag(2 n2 +c,n)+
JoERd
(a 000 diag(E
:a) 0c,x)]]
k
=
d0 expl
I
T
--
xi + Σ a Σ aj -00 -- + kā) + (n + x300
-a==-aa
BeRd
2
1=1
j=1
n
k
nz + ka T n2 n k
nē + ka n2 + h
expf
1
+
a
aj (n k)(
1
j-1
+ k
nT + kā ,T 100
nJ. + kā
d0 expl
[(0
n + ki }}}
JAERd
2
n + k
= expl
T
03 +
Σ
k
a
1 0j (n k)(
nz + ka -
11 + kā 12 + k }}
n n
2T
yd det(E)
n +
Observing the RHS and using the improper uniform prior assumption we have:
1
doQ(f) expl -
(x - Pc,n) + (a - 0c, (0,0))) 2 =[(x= 0c,n) Tv TT
diag(E=1. 1c,
d
d0 expl - 21(00- - -Oan)" ) w (xx - 0an) + (a - 0c,t)² diag (I-1 (a - 0a,))l
DeRd
d8 expl [[10 0en) (diia((d -n) n - m
rep(E ,n))( (n)(==,n))) dcn)++
AERd
n²
(a 0c,1)² diag -1 1,)((a 0c,
22

---

Published as a conference paper at ICLR 2020
dl expl
2
Σ 1=1
[1 - 0) -)7-~-(10) (z; - 0) + Σ
(a, - 0) (a, - 0)-
BERd
n
n
n
m n²
(x)
Σ (x--0)1
1=1j=1
d0 10epp-
2 1-1
- (2i -) 0) E --1(;; (z: - 0) +
Σ
[a 0) T E (aj - 0)-
JBRd
(n m](s - 8)) E- -x (3- 8]]
k
d0 expl - bーΣ x ア xj + Σ
1 (1
JoEd
j=1
(m + k)0"==
Σ 0- - 20 Σ-
(mx + ka)l]
-cxpl- 1
n
2
Σ
I3
+
aj Σ -a=aa aj (n -mmmmm)-->
1=1
(m + k)( mā + kā
mā + kā
---!
}}}
m + k
m1 + k:
m k [[(
mw kūs " (0-
mI + kā }1}
do expl
BERR
2
m + k
m + k
m + )d det(E)) expl
2T
1
--クーー11 23 +
Σ - 1 ag (n - --
k
2 i-1
(m + k)( mI kā m + k Therefore the decision rule is
mē + kā
}}}
m + k:
VC " y expl "''spp
[I+ I
[)( n + k.
nT + kā -Σ-
nT + kā
1B
2xt
)a
12 + k
n k
expl expl][1m - m) x + (m + k:)(
mā kā T
mā kā
2T d
m + k
m + k
m + k
m(m + k) )a expl [(n + {))(
nē + kä
n2 --
kā }}}
m(n + k)
n + k
n + k
expl 1 [n (01n-m)a'' m) TTTT --'-E 1 (m + k)(
mē + kā TT -1 mm + kā
[
}}}
m + k
k
<>d log n(m= + k)
m + Kō 7 Σ
mā + kā m + k
(n m) シー + (m + k)
m(n + k)
m + k
(n + k)( nT + kā
| x nă + kā
k
n + k
n(m= k)
<>d(m + kn + k) log
m(n + k))
k2 -ーー 2h nn m) 1 - k2 m)aa
d(m k)(n k) kn m) m(n + k)
log n(m k)
> (ā (a--)-=--0 li a)
As required.
Lemma F.9. Consider the authenticator Dar as defined in Def. F2 Then any attacker G, repre-
sented by a conditional probability 9x y, that satisfies the condition T ÿ for any leaked sample y E Rmxx a and attacker generated sample x E (Raxd, (xlv) > 0}, satisfies:
G E argmin V(Dagg") Va R+ geec
23

---

Published as a conference paper at ICLR 2020
Proof.
The best response attacker satisfies:
yx E argmmin
Re-qB
A-1 ( By pbm) Px- - Bx- (A,
aioY 2
argmim
Q A-10
A
By r
- DA(A.
argmax 9XlY
Be 11 E y (x
argmax Ee Q [ (
EX~ / || - Al
- <a]
9x
Lemma
argmax Ee Q N1) BY (x- / ||
Als - <a]
9XlY
| - alا- <a I d0Q(0)
argmax
dy
dxgxir (xly)
dāl
JOER!
yERmxd
JoRRaxd
BeRd
expl
2 aa - 11-0)²
0}} expl - Σ (y) 0)² 0)}
Note that 9x|r (zly) can be chosen independently for each y E Rmd Thus, we can optimize independently for each E Rmxd and we have:
[
|| مزاا_ < a] { d0Q(O)
(-1) argmax
døgxpy (xlw)
däl
gxlr (11)) zeRnxd
JaeRd
DERR
k expl 2 1--0075-- 0)} expl (g) - T l3j - 0))
Note that for any PDF I over Raxd and a function & :
R R it holds that
SuERnxa dx d (x))(() & supx)p(x). Therefore, there exists deterministic distribution ex
8(x x') that achieves the maximum. Thus, it's sufficient to find vector &g that achieves the maximum:
dxl dz' - 2) S dāl | دواا < { d0Q(0)
zg Fargmax
JaERa
DER4
h aa
exp(
0)² 1 (ā- - (0) expl
Σ
(リ) - -0- -0)
2
2 j=1
[ - a|ة g < <a]
arggaax
dāl
d0Q(0)
b (a
exp(
- 2 (a expl
(リ) -) 1-----100 (1; 0))
2
1-1
argmax
dāl
[ a|ل3
d0
neRd
1 expl / [k(a - T--
0) +
Σ
(3) - - (y5-
1=1
argmax
dā expl
[kai x- x-1a]} ||ا a|ل < a DeER
d0
2
exp(
2 [(m
Σ 1)) 1--1-- - 2T 3-m(mmj- + ka)]]
1
1
argmmax 1
dā expl
- 2 =lkaa
I
-- m + k (mğ + kā) T ' (mī + kā)]]
JUERd
I | a
2 s-z < al
d8 expl
(m + k))
(0 my
+ kä T - 1(0
my + kä
+ k }}
BER
2
24

---

Published as a conference paper at ICLR 2020
1
1
argmax
dā exp(
m + (my + "ta)²>" (mg kā)]]
SaER
2
2
1 mk
2mk: 2 Σ
mn
argmax
dä expl
d Đー
Σ-1
a
7 Σ Σーンリ
GER
2
m k
k
+ k
a
argmax
dā expl
2(m + k) [(a ((a-8)-E
mik
(aai-))><((-)))) (a-001}1 || - <a]
Where in (+) we used the fact that Q()) is the improper uniform prior. Note that the expression depends only on the mean F.. Therefore, it's sufficient to find mean vector F that maximizes the expression. We substitute the integration variable to yp à I and obtain:
mk
Fg E argmax
dpexpf 2(m + B) (p
[1v0 [1+ + I - -0" (0+ x-- 7)]
argmaxx ( 5) argmax (1)
Where & is defined as in Lemma E.7 (with o = m=t)), from which it follows that (p)) is log-
concave, and therefore has at most one local extremum which can only be a maximum. Therefore, it is sufficient to show that μ 0 (i.e., Ft 7) is a local extremum by equating the gradient at the point to O.
mk
(p)) Ōu
Ōy (pee de expl 2(m + k) [[p -1) I- - -]]
mk
mk
Apexpl- 2(m k)) |(pp x- [-]]
2 (0 (ppedupps.-1peo
2(m k))
(4)
mk
mk
JiveRtipTS spca)
de
2(m + k)) - x -111 (( p)
(m + 16)
Therefore:
mk
mkk
ōy ~1))===== (m + 16) (p de excxpp- 2(m + k))
15"
Note that since the domain of integration symmetric about the origin with respect to negation and the integrand is odd with respect to the integration variable, the integral is equal to zero. I.e., ou =(())p== = O. Therefore, = y (μ 0) achieves the global maximum, and any attacker that
satisfies the condition: F ÿ for any leaked sample Rmxdd and attacker generated sample a E (Raxd, (xlx) > 0} satisfies:
G E argmin V(Do,g') VaeR,
geeG
As required.
Corollary F.1. Consider an authenticator Da, as defined in Def. F.2 Then the attacker G*, defined in Def. Fl is best response. i.e.:
9" E argmin V(Da,g")
E
g'eC
Proof. Directly from Lemma F9
Theorem F.11. The game value is:
max min (DD,)) min max ((D,)) = V(D* g+)
D
G
G
D
d dn(m + k)
n(m k)
d dma(n + k) 2k(n m)
1a(m + k) m(n + k)
17 2 2T(2)
log
log
2k(n m)
m(n k)
Where ry is the lower incomplete gamma function.
25

---

Published as a conference paper at ICLR 2020
Proof. From the max-min inequality have:
max min (DD g) & min max ())
D
g
g
D
On the other hand, using Lemma F.8 and Corollary
F.10
we have:
max min (2) min V(D", ()
P.00
V(D*, g*)
max V*) > min max (D)
Therefore:
max min ((D,g) = min max V(D,9) - V(D*,g*) D
g
D
The game value is given by: V(D*, 9
Re-qV(() g
2 Ben QE
A
(2 B f
(m)
B P (x [D" x (1) D (A,
Bon
A Ar (1) By:Bynn p
2
E Px-
(n) [1
Al a**)
E xx
1 1[| All a²]]
1
+ Ee 1- X~ (m))
|1 A g-1 < <a
2
Ex 2x (10)
[| - A 3 <aa1]
Observing the first term we have:
BO-QL
12) {())
|1] All <a'l
A-
Re-QBB
(6) E (n)
[[((X E A) < a*]
A~180
Q
(2)
[[[( - A)T(CCT)- A) <)aa]]]
Ee-QU QL
E
- [
-A- (X - <a]]
2
EB-OE
E
E
[[[C-'(8- (C) - A)) < aa]]
Ee-QL
(()
(m) [1="2<aa]
Observe that
7 = A) = -)) 0) - (A- θ)]
X X-
[ θ
C- - la]
=[c-1 -C-1
A θ
A +
Note that:
-
1
Oaxd x Σ
A 9
Oaxd
Therefore:
Z ~ NNO,,, 1,-
1x Oaxd
Oxxd I
C-T C-T
-N(0ss [
K
n
n k
-N((0, nk
c-1o0"a-T)
+ k
~ nk
Ia)
26

---

Published as a conference paper at ICLR 2020
We denote 7
nk n+*
NOoa, Ia), and thus ,1,.., Zu are independent standard normal
random variables and % (d). Therefore, 6 n+h z r'k 1 0 we have:
) 2 2 and
nk
Eo EB-qEE A- xx (m) [1 Z a²]]
Ea E 2T Z - 2
[1| z < a²]]
2
(
1 d nka*
Ee Q
2
[()) 2' 2(n k)
d nka *
2
(g)
2(n + k)
Where in (1) We used the CDF of the Gamma distribution in which y is the lower incomplete gamma function.
Similarly, observing the second term we have:
Ee-
Q
Q
A f Bx Xx (1)
[1| - Al < <a
2
E
E x- x (10) [
Ex
2
= =(*))
Where:
V = C- 0-11X-- A) = [[ - 9) (A- θ)]
X - θ
X
=C -La
Ā = =
Ā θ
Using the definition of G (Definition E. and Lemma
F33
have:
X - θ A θ
Σ
Oaxd x f
NO2aaa
0axd
Therefore:
V N1O,,,
m Oaxd
IE
0dxd
C-T -C-
NoO.,,
m k mk
la)
And similarly to the first term, we get:
d
m + k mk
VTV ~ r(k = 0 2
2'
And thus:
1 1
2( d
mka* * 2(m + k)
(**)
2 (T
Therefore, the game value is given by:
d nkx*
mka *
V(D*,9")
7( 2' 2(m + k)
(()
2' 2(n k:)
d dn(m k)
n(m- + k)
d dmi( + k)
n + k)
log
7( 2 21 n - m)
log
2
(T(
d 2
2 2k((n m)
m(n + k))
ml n + k))
As required.
Finally, we prove Theorem 4.2 and Corollary 4.3
27

---

Published as a conference paper at ICLR 2020
Theorem 4.2
Define 8 m/n Σ 1 and let p m/k. Consider the attacker G" defined by the
following generative process: Given leaked sample Y E IR=xa g* generates a sample X E I xd as follows: first samples vectors Wi,.... Wn lid NO, Σ) and then sets: X; W; W +Y. Define the authenticator D by:
(* = 1 -z-
d(1 + p) (1 po
log
p+1 p
(F.5)
n11
)*) Then (D*, 1*) is a solution of Eg.
2.2 that satisfies Eq.
4.1
Proof. Directly from Lemma F88 Corollary
F.10 and Theorem
F.11 by assigning
m
m
Corollary 4.3 Define å and p as in Theorem 4.2
Then the game value for the Gaussian case is:
[ d d( + p) 1
d(ó p) log 3 5+
1 1+
log +
(F.6
2
2T(2)
2 2( 8) 8)
2(1 8)
Where is the lower incomplete Gamma function, and I' is the Gamma function.
Proof. Directly from Theorem F.11 by assigning 5
K
F.4 GAME VALUE FOR A MAXIMUM LIKELIHOOD ATTACKER
In this section, we consider the most intuitive attacker strategy, which one could naively see as optimal. However, we show that this intuitive "optimal attacker" is sub-optimal as can be seen in Fig. [ in the main paper. We consider an attacker that draws the attack sample from a Gaussian distribution with the maximum likelihood estimate of the mean and the known covariance. We denote this attacker by the name ML attacker. find the best response authenticator to this attacker and the associated game value. Fig. visualizes the difference in theoretical game value between the ML attacker (see Definition 1.12) and the optimal attacker (see Definition F.I) for different values of d (the dimension of observations), and demonstrates that the ML attacker is indeed sub-optimal.
0.8
0.4
0.8
0.8
0.4
61
0.6
63
0.2
81
0.2
61
02
61
80
10
10a 10a 60
1.7
00
10
10"
(a)
(b)
(c)
Figure 6: The difference in game value (expected authentication accuracy the optimal authenticator) tween the MI. attacker and the optimal attacker for different values of the observations' dimension d, as function of the parameters = ence in game value for d 10. bb) Difference in game value for d 100. ic Difference in game value for
m m.d
Namely: maxp ( (V(D, GMez) maxp (V (VD,, (D, ( Differ-
d = 1000.
Definition F.12. Let GAS denote an attacker defined by the following generative process: Given
leaked sample Y E Rmxd GML generates attack sample X NN(Y
Lemma E.13. Let 0 Rd Ee d represent the mean and covariance Gaussian distribution.
Let X E n xdd a random sample generated by the attacker defined in Def. F.12
Then:
X ~ ~N(Ben, diag(E, n) + rep(( m },,n)) = - ((ea, V VML)
28

---

Published as a conference paper at ICLR 2020
Proof. Let W....., W id (00 E), observe that X; Y W; Vi [n]. and thus:
X V c. + We
Where We ~ ~N Idn, (E, n). Using Lemma F.3 we have Y -N 1) and using Lemma F.4 we have Ve, NN repí n)).
We Yan
Let Z
and B [nnxxd Indxna], then X. Wo + Pe, BZ. Note that:
Ond Oenm
diag(E, 0
2 ~ N(
repl rep( E.
and therefore we have:
Ond X ~N
B
(Eigg(In)) 0
B²)
rep( L E, n) m
=N =N(0e, (E, + rep( n))
m
As required.
Lemma F.14. Let CC Ruxd represent the covariance of Gaussian distribution, and
consider the following covariance matrix: MML diag E, n) + rep( 1 L, n). Then:
ML diag(E ,n) + m
rep(==1
and the determinant is:
det (V) det (E) n + m
Proof. To find the inverse of v ML we first define:
Y
La
U
:
gnnxd
V
1
ggnddd
(F.7
m
Σ
Ia
Therefore we have:
v ML =(diag(E, + repl n))
-
1
m (diag(E) (E, n. + UVT)-1
diag( n) diag( E, n) U V diag( E, -U) diag(E,
( diag(E-1 ding(E E--
nn)U nn)U + VT diag 3- n)) - diag
Ia
la
=diag(E-2,)
(Ia + m
[1a
Ia]
Σ
E-
m
la
La
=diag(E-1,)
(Ia m
Ia)
m
Ia
la
=diag(E-),
(( n7 + m
Ma)
1 Σー
E
m
Ia
La
1
=diag(E 11-10---110
Ia [2
Ta
29

---

Published as a conference paper at ICLR 2020
1 m
=diag(>* (20g(2221,00 ,n)
rep(2="1 ,n)
As required. Where in (i) we used the Woodbury matrix identity, and in (ti) we used the inverse of a diagonal block matrix.
Next, we turn to find the determinant of Varz:
det( v) det(diag(Z,, n) + (ep((_)).n))
m
det(diag(E, UV*)
(i8) det(diag(E, n)) det(La La V diag(E, UU)
det(E)" det( + V diag(= nn)))
Σ
del del(Ta + [T
Ia] diag( E ,1)
Σ
det(E)) det(( 12 m 1a)
= det(2))) n + my
m
Where in (ii) we used the matrix determinant lemma, and in (iv) we used the determinant diagonal block matrix.
Lemma E.5. Consider the attacker GMLL defined in F.12 The best response strategy for the au- thenticator against this attacker is:
(a T | alli axrz.
Where:
d(n + k)m + nk + mk)
nim + vok: + mik m(n k)
OML
log(
Proof.
The best response authenticator satisfies:
D* argmax V(D, DeD
argmax DED
Ee-qB
Ee
1
By
E / [D(A, [D(A,,] + - D(A,
2
argmax Re o A~ DED
(k)
B /
- (DA, Ex - D(A,
argmax A DeD
PPx-N(0.. Ie ding P Ex-Nee... D(A,
argmaxx E He-o
da
de expl 7 -c,)) diag(2) k) -t Oc,))
DED
JaERia
JeRRnd
expl expl- 2( Oan) diag(2), " -
det (et(gi E, n))
1
1 expl 11-7-- (en))" ao -
det V ML)
Lemmn F
argmax Ee-Q
da dr expl (a -Oc,)) (h didg (E, k) (a 0c,))l
DeD
JaERta
n + " expl- 1 (0x ddigg n Ocn))
30

---

Published as a conference paper at ICLR 2020
expl- -xp)-
(U
( ML
O2 ((a, x)]]
D can be chosen independently for each pair xr) X x xx" Therefore, for any (a.z) E 2 xx"
the decision rule for D(a, 2) = is:
n + ja jd d)Q(0) expf- 2 (xx - Be,) diag(I, (x Bcn))
m JBERd
expl- (a kerk)² diag Σ, k:) (a 0c,k)²
S d0Q(0) expl -
1 (a 0,,n) n MMMM (x - (cna) expl - 2( ding(E, (a 0c,k))
Observing the LHS integral and using the improper uniform prior assumption, we obtain:
JO dlQ(0) expl b11o= 0c,n)" "iagg(E (x 0c,n)+
(a 0o.k)) diag(Z, E, ka 0c,k)]]
k
d0 expp
x ti + >
" ag a -200000- -200 " + kū) + (n + k))0 = -
J0ER
j=1
n
n.. + kā y アーー
Th. + kā
=expf-
1 Σ
+
Σ
aj
Σ 1
aj (n + k:)
)}
2
k
72 + k
i-1
j-1
+
k
nă +
kā -
nı + kā
d0 expl
[(0
}]}
DoRR
2
+ k
+ h:
eepp( 4/
n
Σ
+
Σ
aj
2 Σ
aj
(n + k)(
nx + kā -
12 + kā 72 + k
k
1=1
j=1
2π k
)d det(x))
Observing the RHS and using the improper uniform prior assumption, we obtain:
d0Q(0) expl - 111----16
[[1xxxxxxx - -o.n) TM N/ (x 0c,n) + (a 0o. ( diag((=-,,,a 0cn)]}
DER4
1
db expl
2 [(x Ben) v " WiLL (x 2e,n) + (a - 02,k) diag(E (E- (i))(E=1,))(a 0c,k)
Dend
7 21100 00 ((diag(dg'' ,n) 1 - ,1)) (1))(= 0c,n)+
d0 expl
aER
n
(a
0 kahh)²
diag(
--1 -)(( 0c,k)]}
d0 expl
(1g -)
(I:; 0)
[aj
-) (aj 0)
DeRd
2 i=1
j=1
n22
(I - 0)) T Σ ( A)}
n + m
(
expl
1
x
T D
m4 Σ a
Σ
aj
n2
---
nmm + nok + mk.
"7 ---Lu]
2
n + m
n + m
1=1
1 nm
+ nk + mk
d0 expl
[0 x---1o w1}
JBRR
2
n + m
1
b Σ
n²
+ nkk mk. TT - '1}}
expl
x
T E
x
a
aj
Σ
2
12 + m
n + m
2n + m)
det(E))
um + nk + mik
31

---

Published as a conference paper at ICLR 2020
Where in (i) denoted
k m mm mm+
Therefore, the decision rule is
nE kā kā T
expl 2xpt2((1 + k)(
I min + k) )d>
n k
n +
expl 1 n2²
nm + nk + mk -
x² Σ x
nm + nk + mk )a
n2 + m
n n+ m
am + nk mkk yd=
m(n + k))
n²
nm nk mk
- (n + k)( 12 ka -
n + kā
expl
nt + m
n1 n m
+ K
12 + k
1m + nk mik
e>d log(
m(n + k)
n² " - x + nm + nuk + mk
nı + kā
11 kā
0. -T - (n+ k)(
"T -1
m
m
+ k:
+ k:
+ nk mik
k2n²
# log(
(E a) ">'=== 13 a)
m(n + k)
(n + (mm + nk + mk)
d(n knmm nk + mk)
n1m + nk + maki
< 10-aa T (x σ)
log(
12
m(n k))
As required.
Theorem F.16. Fix the allacker to be Gusz. defined in F.12 then the game value is:
max
V (D, 9MLL)
Lemmal E1S
(DDML.MML)
D
1
d d(nm nk mk)
log nmm + nk mk m(n + k)
L7(
2
2
((
2nk
d dm (n + k)
nm + nk + mmk
r(
log
2
2nk
m(n+ + k))
1
d d
1 1 1
1 + p 611 p
h
2 7 + p 5) log
- ( 5) log
2
2
p 0+
Where = m2
8 m2 and y is the lower incomplete gamma function.
Proof. The game value is given by:
((DMI,9ML.)
= -Ee-QV(0) V(O, GML)
Eo-OE
A~10 E ((m))
E [DM,,,)) Bx- - (A,((x)))
2
EO
A~
B, p()))
(() 111 -Al All3-
< <amul
+ -x
1 11 - All < avull
Be-q E. (A))
S( (m)
|1| AA amrl]]
Ee-qE A Ex Ex- (1 (19)
||| X All aauil
2
Observing the first term, we can see that by replacing a with aML in the analog part of the proof for Theorem FII we get:
E Ee-QB A~ (
Ex-s(m) s(
[||
All cami]]
7( d nkaML
2
2 (T
2(n + k)
32

---

Published as a conference paper at ICLR 2020
Again, similarly to the analog part of the proof for Theorem F.11 observing the second term
have:
E + Q E (0) Bx
A-10
x
(10)
|||x A amill
Ee Q 1- x (19)
[VV < aam]]]
2
= =())
Where:
V = C- A) -) (A-- 0)
X -
X - θ
= =C- [Td. -Tal
A 6
=
-
Using the definition of JASL (Definition have A ~ ~N(0, E), and thus:
F.12 we have X ~ N(0, n+ Σ), using Lemma F3 we
nm
X -
-N( 00
u Σ
0
A -
0
x Σ
Therefore:
Σ
0
C-T
~NOss, nmn + nkk + vik
V V~ N=000
La)
0
-C-T
nonk
We denote V
V and thus Vi...., Va are independent standard normal random (d). Therefore
nukk
nm ak
variables and
d nm + nk + mk
VTV ~ [[k
2
nmk
And we have:
1
?( d nmkaML
2 (( 2(nm + nk + mk)
Hence, the game value given by:
1 1
nkamL 7( 2(nm + nk + mk) )
nmkaML
V(D*, ge)
2 2T(2) [7( 2' 2(n + k)
1 1 1 d d(nmm + nk mk) log m(n + k)
nin + nk + mnk
2
2 (())
2nk
d dm(n + k)
log nm nk + mk )
) 2
2nk
m(n + k)
As required.
G EXPERIMENTS DATASETS
Below we provide details the datasets used for the authentication experiments on faces and char- acters. The VoxCeleb2 (Nagrani et al. 20177 Chung & Zisserman 2018) dataset contains cropped face videos of 6112 12 identities. We used the original split of 5994 identities for training and 118 for test. For each identity, we saved every fifth frame, resized each frame to 64 x 64, and augmented using horizontal flip. The Omniglot dataset (Lake et al. 2015) contains handwritten character im- ages from 50 alphabets. There are 1623 different characters, and 20 examples for each character. We the splits and augmentations suggested by Vinyals et al. (0066) and used by Snell et al. (2017).
33

---

Published as a conference paper at ICLR 2020
H EXPERIMENTS IMPLEMENTATION DETAILS
In this section, we describe our implementation of the GIM model for the different experiments, in detail. Recall from Sec. 5 that in general, the authenticator is neural network 2)) that can be expressed as D(a, x = a (a), (x))), and the generator is a neural network ( that can be expressed as ((y); <oW,, W Tz(y)) Vi E [n]. In what follows describe our implementation of these models for each of the experiments.
H.1 GAUSSIAN SOURCES
Authenticator Architecture: For the statistic function TD, we use a concatenation the mean and standard deviation of the sample. For the comparison function d, we use the element wise absolute difference between the statistics ( Tz(x), followed by a linear layer.
Attacker Architecture: For the statistic function Tg. we use the sample mean, i..., Ty()) = g. The
noise vectors W; are generated as follows: First, n Gaussian noise vectors Zi...., Zn N Ia) drawn, then each vector Zi is passed through linear layer to obtain W.. Finally, the decoder yp is the identity function.
Optimization details: The model is trained in authentication setup in theoreti- cal setup, using alternating gradient descent as is common in GAN optimization (Mescheder al. 2018). Each iteration begins when source 0 Rd is drawn from the prior distribu- tion Q = No, 10/a). Samples A Rexd, Y E Rmxd Xe Raxd are drawn IID from fe No0 Ia). where X9 represents real sample from 0. The attacker, given the leaked sam- ple Y. generates fake sample Xg = G(Y) E Raxd, passes it to D, and suffers the loss log(sigmoid X)))). The authenticator, D, receives as input the source information sam- ple A, outputs a prediction for each of the test samples Xo. Xg. and suffers the binary cross-entropy loss -0.5 (log (sigmoid( ((A, Xa))) + log (sigmoid(1 D(A, Xg)))) Each experiment trained for 200K iterations with batch size of 4000 using the Adam optimizer (Kingma & Ba 2015) with learning rate 10-4.
H.2 EXPERIMENTS ON VOXCELEB2 AND OMNIGLOT
To deseribe the models begin with notation. We let denote the number of image channels, denote the image size (we only consider square images of size e x x h), and denote the latent dimension of the model.
Authenticator Architecture: As mentioned above, the authenticator is a neural network model that be expressed
D(a, (TD()))
The statistic function TD maps sample of images statistic vector R& in the following way: Each image in the sample is mapped using encoders E EP : [-1, 1jcxhxx R to two latent vectors Vare: Venv RR respectively. Usre designed to represent the source and Vene is designed to represent the environment (c.g., pose, lighting, expression). To represent the source of the sample, the sample mean of Usec is taken. To represent the sample distribution, Veno is passed through a non-linear statistic module Ç which is meant to capture more complex statistical functions of the sample F Finally, (x) is obtained by concatenating Usre and (VVenv). E.g., for x we have:
Tr(x) = concat
Σ (x:), (E2ne ((E
The comparison function a : 6 receives two latent vectors 8, = TD(a), 8, = T>(x) representing the statistics of the samples and respectively. The vectors are concatenated and then passed through a Multi-Layered Perceptron which outputs a scalar reflecting their similarity. Namely:
(sa, 8a) MLP (concat (8a, 8a))
The full architecture of the authenticator is depicted in Fig. 7
$ is implemented the concatenation of the standard deviation and mean of the sample after passing each example through Multi-L.ayered Perceptron.
34

---

Published as a conference paper at ICLR 2020
X
A
E STC
E
D env
E SrC
env
Sampll
concat
concat
T
Tp
concat
MLP
D(A,X)
Figure 7: An overview of the implementation of the GIM authenticator architecture for the experiments on the Voxceleb2 and Omniglot datascts.
Attacker Architecture: Our implementation of the attacker is inspired by the architecture sug- gested by Zakharov et al. (2019). which relies on an implicit assumption that an image could be modeled mapping of two latent vectors image space. The first vector represents the source and is the same for any image of 0, the second vector represents the environment (e.g pose, lighting, expression) and different for each image of the source.
The attacker model consists of the following components: An image encoder (cxkih E' that maps an image to a latent vector representing the source Egre image encoder EC [ - R' that maps image to latent vector representing the environ- ment, Multi-layered Perceptron MLPg IR R that maps Gaussian noise to the environment latent space, an environment decoder &eov R - Rexhxh that maps a latent vector to an environ- ment image which could represent aspects the environment such as facial landmarks and finally, generator Φ x22xxxx x ! []1,1]exhxx exxhxh that maps environment image concatenated to the real image to a new image. The generator is based on the image to image model used by Za- kharov et al. (2019) and Johnson et al. (2016 and uses the source latent vector input for Adaptive instance normalization (Huang & Belongie 2017).
The attacker generates fake sample X 1 based leaked sample Y [_1,1]xxxx xxxch the following way: Each image Y, in the leaked sample is mapped using EG and E to latent vectors uz*e, ugnu E R!. latent environment vector, waav, is constructed for
each fake image X; in the following way: First, n Gaussian noise vectors Zi.... Zn iid N(O, 4))
In Zakharov et al. 2019), our so-called environment image is indeed facial landmarks image which is used input the model. In work, allow the model to learn which environment image is useful.
35

---

Published as a conference paper at ICLR 2020
drawn, then each vector Z₃ is passed through MLPs obtain W,, and finally, of is obtained by matching the mean of the new latent environment vectors to the sample mean umme, Namely:
W; W uew Vie [n]
Each fake image X; is then generated deterministically follows: of is used input to the decoder PPoe which outputs an environment image. This image is concatenated along the channel dimension random image from the leaked sample Y. and then passed input to the generator Φ, which also receives u as imput to its Adaptive instance norm layers. The output of the generator the fake image X; for all [n]. The full architecture of the attacker is depicted in Fig.
Na0,1a)
E STC
emmy
MLP
Sample
Sample
Sample
Tg
Replace maan
Adain input
X
Image
Figure 8: An overview implementation GIM attacker architecture the experiments on Voxecleb2 and Omniglot datasets.
Optimization details: The model is trained an authentication setup as in our theoreti- cal setup, using alternating gradient descent with the regularization parameter suggested by Mescheder et al. (2018). Each iteration begins when a source E Rd is drawn uniformly from the dataset. Samples E 1-1, lxxexxxh, Y [-1,1]mxexe are sampled uniformly from the images available to the source The attacker, given the leaked sample Y, generates a fake sample Xg G(Y), passes log(sigmoo sigmoid (D((, Xg))). The authenticator, D. receives as input the source information sam- ple A, outputs a prediction for each of the test samples Xo. Xg, and suffers the binary cross-entropy loss 00.5 (log (sigmoid( DD A, Xo))) + log (sigmoid(1 - D(A, (())))
Xa [-1,1]"xcxxxl
D, and suffers the loss
The experiments on Omniglot were trained for 520k iterations with batch size 128 using the Adam optimizer (Kingma & Ba 2015) with learning rate 10-6 for D. 10-5 for G, and 10-7 for MLPg (as done by Karras et al. 20 8b)).).. The regularization parameter was set to
The experiments on Voxceleb2 were trained for 250k iterations with batch size 64 using the Adam optimizer (Kingma Ba 2015) with learning rate 10 for both D and G and 10-6 for MLPp to 10 (as done by Karras et al. (2018)) since noticed that
The regularization parameter stabilized and sped up the training, and contrast to Omniglot and the Gaussian experiments did not seem to hurt the results.
36


Reviews:
[{"review_id": "rJliBd199H", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\"Optimal Strategies Against Generative Attacks\" describes just what the title implies - various dimensions of the problem of defending against a generative adversary, with theoretical discussion under limited settings, as well as practical experiments extending on the intuitions gained using the theoretical exploration under limited conditions.\n\nParticularly, one of the key stated goals of the paper is to \"construct a theorectical framework for studying the security risk arising from generative models, and explore its practical implications\". Given this goal, the paper performs admirably.\n\nThe appendix is extensive, and gives a lot more insight into the core paper itself.\n\nI am unclear on how the data augmentation experiment fits into the overall picture - perhaps a more detailed explanation of how and why this would be used to form an \"attack\" would help. The other experiments are sensible, and demonstrate reasonable and expected results. \n\nThis is a solid paper, and most of my critiques are \"out of scope\" and revolve around experiments that would be nice to see. Though GAN-for-text is not simple, showing this type of setup for text would be interesting for a number of reasons, same for audio.\n\nContinual passes through the text, with a focus on clarity could also be helpful - the topic is dense, and the text does a good job describing what is happening, but it is always possible to further distill these complex topics, and relegate some useful-but-not-critical pieces to the appendix.\n\nThese are minor quibbles, and overall this paper was an interesting and useful read, on a relatively underexplored topic. It shows theorectical results, and practical experimental demonstrations of the theories proposed. Given the stated goals of the paper, it performs admirably.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "r1lRr8jocr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper addresses the issue of malicious use of generative models to fool authentication/anomaly detection systems that rely on sensor data. The authors formulate the scenario as a maxmin game between an authenticator and an attacker, with limitations on the number of samples available to the authenticator to fix a decision rule, the number of samples required at test time for the authenticator to take a decision and the number of leaked samples the attacker has access to. The authors prove that the game admits a Nash equilibrium and derive a closed form solution for the case of multivariate Gaussian data. Finally, the authors propose an algorithm called \"GAN In the Middle\" and perform experiments to show consistency with the theoretical results, better authentication performance than state of the art methods and usability for data augmentation.\n\nThis pager should be accepted. Overall, it addresses crucial problems with the recent advances of generative models and provides significant theoretical results. The experiments would benefit from some clarification.\n\nFor the experiments, the following should be addressed:\n* Confidence intervals for all results (specifically in Figure 1a and in Table 1)\n* Figure 1a: it would be interesting to see a similar analysis also for other values of m and k. \n* Table 1: This result would also be more supporting if experiments were performed for varying values of m, n and k. The description of the RS attack could be made more precise: does it mean that the attacker samples images at random? Intuitively, it feels confusing that the GIM authenticator would perform worse on this setting.\n* The experiments on handwritten data would be more similar to what I imagine being a real-world authentication scenario  if performed on a task where a class is a single person writing multiple characters, as opposed to characters being classes.\n\n\nMinor comments:\n* Page 6, second to last row: there is a\"the\" repeated twice.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "SygqiKVl5r", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary\nThe authors investigate an attack-defense problem in which an attacker attempts to pass authentication by generating a faked input, while an authenticator attempts to detect the fraud. They formulate this problem as a zero-sum game and reveal the closed form of the optimal strategies. Furthermore, they reveal a more insightful closed form of the optimal strategies in the Gaussian case. This result clarifies the relationship between the success rate of the attacker and the numbers of the source, registration, and leaked observations. The analysis for the Gaussian case also gives an interesting insight that the optimal attacker’s strategy is to generate fake inputs so that its sufficient statistics are matched to that of the leaked observations. Based on this insight, the authors propose a new learning algorithm for the authenticator and demonstrate by some empirical evaluations that the proposed algorithm is robust against the faked input.\n\n# Detailed comments\nThis is an interesting and well-written paper. I recommend acceptance of this paper.\nThe authors investigate an attack of generating a faked input for passing the authenticator under which the attacker can only observe partial information about the source input. This is an interesting point of view and allows us to analyze a more practical situation. Furthermore, based on the theoretical analyses, they reveal an interesting insight of the optimal attacker’s strategy that the optimal strategy generates a faked input so that its sufficient statistics are matched to that of the leaked observations. This insight introduces the new robust learning algorithm which outperforms the existing robust learning algorithm demonstrated as in the empirical evaluations.\nSome minor refinements would improve the paper:\n- \\bar{x} and \\bar{a} in Theorem 4.2 should be clearly defined.\n- It seems to me that the authors use the term “ML attacker” to denote some different attacking algorithms.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "BJge4FdRFH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new threat model for generative impersonation attacks: The attacker has access to several leaked images of a person; the authenticator knows several registration images per person and decides a person's identify by comparing some newly-sampled images from that person with corresponding registration images. The authors formulate this threat model as a minimax game and analyzed its Nash equilibrium. In the simplified case that observations are multivariate Gaussian, the authors are able to characterize the optimal strategies of the attacker and authenticator explicitly, which gives a nice intuition on how the theoretical optimum changes with respect to data dimension, number of leaked images, etc. Additionally, the authors implemented this attack (named Gan-in-the-middle attack) with an objective similar to GANs, empirically verified the theoretical results, and demonstrated the success of their approach on VoxCeleb2 and \n\nAs far as I know, this formulation of generative impersonation attacks is novel. The threat model nicely captures the most important aspects of impersonation attacks and is relatively realistic.\n\nThe theoretical analysis is insightful. I especially like that the authors can prove no defense is possible when n <= m, which nicely matches the intuition. The results on Gaussian case not only provide intuition, but also provide motivation for the design of attacker and defender architectures in GIM attacks. \n\nThe experiments are well-designed. The model architectures are well-motivated from Theorem 4.2. It is great to see that results of toy experiments match the theoretical analysis in Figure 1(a). The GIM attack on the Voxceleb2 images generates very realistic and reasonable portraits in Figure 2(a). The data augmentation experiment can be naturally fit into the framework of impersonation attacks and the application of their techniques in this direction is very exciting.\n\nI only have two minor suggestions:\n\n1. In Theorem 4.1, the symbol g_{X | Y} was introduced previously, whereas g_{X | A} was never introduced. I have to go to the appendix to understand the definition of g_{X | A}.\n\n2. There is a minor issue in the proof of Lemma D.2 in page 16. The authors seem to miss a 1/2 factor in the second to last row in equation (D.3).\n\n\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper concerns the problem of defending against generative "attacks": that is, falsification of data for malicious purposes through the use of synthesized data based on "leaked" samples of real data. The paper casts the problem formally and assesses the problem of authentication in terms of the sample complexity at test time and the sample budget of the attacker. The authors prove a Nash equillibrium exists, derive a closed form for the special case of multivariate Gaussian data, and propose an algorithm called GAN in the Middle leveraging the developed principles, showing an implementation to perform better than authentication baselines and suggesting other applications.

Reviewers were overall very positive, in agreement that the problem addressed is important and the contribution made is significant. Most criticisms were superficial. This is a dense piece of work, and presentation could still be improved. However this is clearly a significant piece of work addressing a problem of increasing importance, and is worthy of acceptance.
Decision: Accept (Talk)