OPTIMAL STRATEGIES AGAINST GENERATIVE ATTACKS
Year: 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.

heading: 1 INTRODUCTION
text: Generative models have attracted considerable attention since the introduction of Generative Adversarial Networks (Goodfellow et al., 2014a). Empirically, GANs have been shown to 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 et al., 2016). Another is anomaly detection systems protecting critical infrastructure. As demonstrated by recent cyber-attacks (notably 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, a new form of a 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 a simple key insight. If the attacker (i.e., 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, if 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 are finite. Specifically, there are three key obser-
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 assumption that cyber attackers are sophisticated enough to play optimal or close to optimal strategies, a 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 to 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 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 it can be used effectively for data-augmentation in the few-shot learning setting.

heading: 2 PROBLEM STATEMENT
text: We begin by motivating our problem and formulating it as a two-player zero-sum game. As a simple 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 required to present to the system n of its images, and the authentication system decides whether the entity is θ or an impersonator. We let m denote the maximum number of “leaked” images any attacker obtained. We observe that if an attacker obtainedm ě n images of θ, it can present n of those images. Thus the observations generated by the attacker are indistinguishable from ones generated by θ, 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 θ, where each source θ P H is defined by a probability density fθ, and an observation of a source θ P H is an X -valued random variable with density fθ. We assume that subsequent observations of the source are IID, so that n sequential observations have density f pnq θ px1, . . . , xnq :“ śn i“1 fθpxiq. We allow θ to be sampled from a known distribution Q on H and denote the corresponding H-valued random variable by Θ. In what follows we will denote the number of observations leaked to 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 a random source Θ being drawn from H according to Q. The authenticator first receives information about the drawn source, and then chooses a decision rule for deciding whether a given test sequence x P Xn is an authentic sequence of observations sampled from f pnqθ or a fake sequence generated by the attacker. Formally, the authenticator learns about the source by seeing k IID “registration” observations A “ A1, . . . , Ak „ f pkqθ . The set of all possible decision rules is then D : X k ˆ Xn Ñ t0, 1u (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 to m “leaked” IID observations Y “ Y1, . . . , Ym „ f pmqθ as information about the source θ. Then it generates an attack sequence X P Xn and presents it to the authenticator, which uses its decision rule to decide whether X is an authentic sequence of observations sampled from f pnqθ or a fake sequence generated by the attacker. Formally, the strategy set of the attacker is all functions G : Xm Ñ ∆pXnq, where ∆pXnq is the set of probability distributions over Xn, and gX|Y is the associated conditional probability density. We note that the set H, the parametric family fθ, 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
the game as the expected prediction accuracy of the authenticator. To define expected accuracy we consider the case of equal priors for attack and real samples.1 Formally, for a pair of strategies pD,Gq and a specific source θ, the expected accuracy of the authenticator is then:
V pθ,D,Gq “ 1 2 E A„fpkqθ E Y„fpmqθ ” E X„fpnqθ rDpA,Xqs ` EX„GpY qr1´DpA,Xqs ı
(2.1)
Since this utility only depends on G in the second term, minimizing it 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 V pD,Gq “ EΘ„QV pΘ,D,Gq. Finally, we arrive at the following maximin game:
Vgame “ max DPD min GPG V pD,Gq (2.2)
where D,G are the sets of all possible authenticator and attacker strategies, respectively. In Sec. 4 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.

heading: 3 RELATED WORK
text: Adversarial hypothesis testing (AHT): Hypothesis testing (HT) is a rich field in statistics that studies how one can detect whether a 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 (e.g., see Brandão et al., 2014; Barni & Tondi, 2013b;a; 2014; Bao et al., 2011; Zhou et al., 2019; Brückner & Scheffer, 2011; Brü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 to a fixed distance (e.g., Hamming). Given the quality of current generative models and the rapid pace of progress, when considering an impersonation attack, it seems that the only relevant restriction one can assume 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 a novel problem setting where both players are not limited in their strategy set in any way. This leads to a novel analysis that focuses on the dependence on the finite information available to each player (m,n, k). 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 adversarial examples and much recent work has analyzed the phenomenon (Ilyas et al., 2019; Shamir et al., 2019; Zhang et al., 2019), addressed the problem of robustness to these (Moosavi-Dezfooli et al., 2016; Papernot et al., 2017; Yuan et al., 2017), and studied when robusntess can be certified (Raghunathan et al., 2018; Wong et al., 2018). The setting of robust classification in the presence of adversarial examples can also be thought of as a specific case of AHT (see above), where a classifier 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 to generating examples that will be classified correctly by humans (Song et al., 2018). In contrast, in our setting the attacker is not limited in any way, nor does it have another utility in addition to impersonating the source. Furthermore, in 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.2 Such a discriminator will not be useful as a defense against generative attacks). Unlike GANs, in our setting, sample sizes are 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 information 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,
1We give equal prior probability 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.
2If the generator is not expressive enough, the learned GAN may have small support (Arora et al., 2017).
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 et al., 2016; Finn et al., 2017; Lake et al., 2011; Koch et al., 2015) and few-shot generative models (Rezende et al., 2016; Zakharov et al., 2019; Lake et al., 2015; Edwards & Storkey, 2017; Hewitt et al., 2018) in the sense that both authenticator and attacker need to learn from a limited set of observations. However, in our setting the authenticator is required to predict whether a sample came from the true source or an attacker impersonating the source while taking into consideration 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., 2015) 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 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. F.4, and in Figures 1c,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 et al., 2017; Park et 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 is not to 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; Snell 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 a new image. It relates to our framework in the limited case of m “ 1, n “ 2, k “ 1, in the sense that the generator’s objective is to map one image to 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 is a sub-optimal attack strategy, as can be seen from the Gaussian case of our problem.

heading: 4 THEORETICAL RESULTS
text: 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 ofX givenA. 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 a 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.

heading: 4.1 CHARACTERIZING THE OPTIMAL STRATEGIES
text: We begin by showing that the game defined in Eq. 2.2 admits a Nash equilibrium. Namely, Theorem 4.1 below shows that there exists a pair of strategies pD˚,G˚q that satisfy:
max DPD min GPG V pD,Gq “ min GPG max DPD
V pD,Gq “ V pD˚,G˚q (4.1)
Theorem 4.1. Consider the attacker G˚ defined by:
g˚X|Y P argmin gX|Y
EA„fA „ ż
xPXn
ˇ ˇfX|Apx|Aq ´ gX|Apx|Aq ˇ ˇ dx

(4.2)
Where, fApaq “ ş θPHQpθqf pkq θ paqdθ is the marginal density of A, QΘ|A is the posterior over H given A, and fY |Apy|aq “ ş θPH f pmq θ pyqQΘ|Apθ|aqdθ. Also, fX|Apx|aq “ ş
θPH f pnq θ pxqQΘ|Apθ|aqdθ and gX|Apx|aq “ ş
yPXm gX|Y px|yqfY |Apy|aqdy are the conditional densities of X given A, generated by the source and the attacker respectively. Consider the authenticator defined by D˚pa, xq “ I ”
fX|Apx|aq ą g˚X|Apx|aq ı , where I is the indicator function.
Then pD˚,G˚q is a solution of Eq. 2.2 that satisfies Eq. 4.1.
The proof (see Sec. D) follows by first showing that since Dpa, xq P t0, 1u, it 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. 4.2. Namely, the optimal attacker minimizes the `1 distance over the space X kˆXn 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 V pD˚,Gq “ V pD˚,G˚q “ maxD V pD,G˚q and it follows that D˚,G˚ satisfy Eq. 4.1.
4.2 REPLAY ATTACKS: AUTHENTICATION FAILURE FOR n ď m
When n ď m, the attacker generates a number of observations that is at most the number of observations it has seen. Intuitively, an optimal attack in this case, is to simply “replay” a subset of size n from the m observations. This is known as a replay-attack (Syverson, 1994). This subset constitutes an IID sample of length n 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 it is easy to show using Theorem 4.1 that this attack is optimal and therefore for n ď m we have: maxDPD minGPG V pD,Gq “ 0.5 (see Sec. E)

heading: 4.3 THE GAUSSIAN CASE
text: 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 is the improper uniform prior.3 We assume n ą m to keep the problem non-trivial. Let the observations be d-dimensional Gaussian vectors with a known covariance matrix Σ P Rdˆd and an unknown mean vector θ P Rd. The set of possible sources H becomes Rd, the Gaussian mean vectors. For any sample of n examples z P Rnˆd, we let zi denote the i’th example, and z̄ “ 1n řn i“1 zi denote the sample mean. Finally, for any v P Rd, B P Rdˆd, we define }v}2B “ vTBv. 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 δ “ m{n ď 1 and let ρ “ m{k. Consider the attacker G˚ defined by the following generative process: Given a leaked sample Y P Rmˆd, G˚ generates a sample X P Rnˆd as follows: it first samples n vectors W1, . . . ,Wn iid„ N p0,Σq and then sets: Xi “ Wi ´ W̄ ` Ȳ .

heading: Define the authenticator D˚ by:
text: D˚pa, xq “ I « }x̄´ ā}2Σ´1 ă d p1` ρq ` 1` ρδ´1 ˘ np1´ δq log ˆ ρ` 1 ρ` δ ˙ ff
(4.3)
Then pD˚,G˚q is a solution of Eq. 2.2 that satisfies Eq. 4.1.
The proof (see Sec. F) starts by showing that @α ą 0, given Dpa, xq “ Ir}x̄´ ā}2Σ´1 ă αs, the optimal strategy for G is to set x̄ “ ȳ with probability 1 (as done in G˚). To prove this, we first use the Prekopa-Leindler inequality (Prékopa, 1973) to show that in this case G’s maximization objective is log-concave. We then show that any G that satisfies x̄ “ ȳ 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 G˚’s attack sample using the Woodbury matrix identity, and then show that D˚ is indeed the optimal decision rule. Finally, using the max-min inequality, this implies that pD˚,G˚q 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 Ȳ and the known covariance Σ. In expectation, this sample would have the correct mean. However, this turns out to be sub-optimal, as can be seen in Figures 1c and 6 (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 a Gaussian distribution with mean 0, and then “forces” the sample mean to be exactly Ȳ by shifting the sample points by Ȳ ´ W̄ . This optimal attacker
3Similar results can be derived for the conjugate prior case, namely, proper Gaussian priors.
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 a corollary to Theorem 4.2 we obtain the value of the game (i.e., the accuracy of D˚). Corollary 4.3. Define δ and ρ as in Theorem 4.2. Then the game value for the Gaussian case is:
1 2 ` 1
2Γpd2 q
„
γ
ˆ
d 2 , dp1` ρq 2p1´ δq log 1` ρ δ ` ρ
˙ ´ γ ˆ d 2 , dpδ ` ρq 2p1´ δq log 1` ρ δ ` ρ ˙
(4.4)
Where γ 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. 1 demonstrates several interesting aspects of the above results. First, Fig. 1a 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 realworld high-dimensional sources (e.g., faces, video, voice, etc.) the authenticator can achieve high accuracy even when requiring a 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. 1b, even whenm ą k, the authenticator can achieve non trivial accuracy.4 An intuitive explanation of this phenomenon is that the test statistic used by the authenticator is › ›X̄ ´ Ā ›
›, which, due to the variance in the attacker 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 to discriminate between the hypotheses.
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).

heading: 5 GAN IN THE MIDDLE NETWORKS
text: So far we explored the general formalism of authentication games. Here we consider specific architectures for D and G. As in GAN based models (Mirza & Osindero, 2014; Mescheder et al., 2018; Karras et al., 2018a;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 as used in most GAN approaches. Authenticator Architecture: The authenticator is implemented as a neural network Dpa, xq that maps from a source information sample a P X k and a test sample x P Xn to a 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 a certain functional form. The Gaussian results in Sec. 4.3 show that the optimal authenticator is a 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 consider the following form for the authenticator. We define a function TD that maps a sample to a fixed sized vector, analogous to the sufficient statistic in the theorem. We apply TD to both a and x. Then, these two outputs are used as input to a comparison function σ which outputs a scalar reflecting their similarity. Thus the authenticator can be expressed as: Dpa, xq “ σpTDpaq, TDpxqq. Attacker Architecture: The attacker is implemented as a stochastic neural network Gpyq that maps a leaked sample y P Xm to an attack sample x P Xn. Our theoretical results suggest a certain functional form for this network. The Gaussian analysis in Sec. 4.3 shows that the optimal attacker generates a 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 TG that maps the leaked sample Y to a fixed sized vector TGpY q, analogous to the sufficient statistic in the
4See Sec. C in the appendix, for additional figures showing that as the dimension grows, the expected accuracy goes to 1.
theorem. It then draws n random latent vectors W1, . . . ,Wn and matches their mean to the leaked sufficient statistic to obtain the latent vectors W 1i . Namely it sets W 1 i “ Wi ´ W̄ ` TGpY q as done in Theorem 4.2. Finally, it uses a decoder function ϕ that maps each latent vector W 1i to the domain X . Thus, the attacker can be expressed as: GpY qi “ ϕpWi ´ W̄ ` TGpY qq @i P rns. Optimization Details: Each iteration begins when a source θ is chosen randomly from the set of sources in the training dataset (e.g., a person to be authenticated). Samples A, Y,Xθ are drawn from the set of examples available for θ, where Xθ represents a test sample from θ. Then, given a leaked sample Y , the generator G 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 Xθ, 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.

heading: 6 EXPERIMENTS
text: We next evaluate our method empirically. In all experiments, we use the model described in Sec. 5. 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 at https://github.com/ roymor1/OptimalStrategiesAgainstGenerativeAttacks. Also, see Sec. H for further implementation details. Gaussian sources: For the case of Gaussian sources, we arrived at a 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 ran all experiments using a multivariate Gaussian with Σ “ Id, and in each game the source mean was drawn from the prior distribution Q “ N p0, 10Idq. This approximates the improper uniform prior since the prior has much larger variance than the sources. Fig. 1a shows the empirical game value compared with the theoretical one as a function of the test sample size n, for fixed m “ 1, k “ 10, and different values of d. It can be seen that there is an excellent fit between theory and experiment.
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., 2015). Additional information about the datasets, splits, and modeling details is provided in Sections G and H. Our goal is to check whether the GIM authenticator is more robust to generative attacks than a 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 a 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 et al., 2015; Deng et al., 2018), in
which an agent is presented with a 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 n 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 we compare the GIM authenticator to the ArcFace method (Deng et al., 2018), which is currently state of the art in face verification. As a baseline for Omniglot, we use the Siamese network suggested by Koch et al. (2015), which achieves state of the art in the verification task on Omniglot. Results are shown in Table 1. It can be seen that on average across attacks, GIM outperforms the baselines. The only attack for which GIM is inferior is RS. This is not surprising as this is the objective that both baselines are trained for.
Qualitative evaluation of attacker: In Fig. 2 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 as in real samples from the data, the attack sample varies in pose and expression and not in the background or clothing.
Data augmentation: Finally, we use GIM for data augmentation in one-shot classification on Omniglot. This is done by using the GIM attacker to generate more data for a given class. We first train GIM on the training set with parameters m “ 1, n “ 5, k “ 5. Then, during both training and testing of one-shot classification, given an example, we use the attacker to augment the single example available for each of the classes, by adding to it the n “ 5 examples our attacker generated from it. We use Prototypical Nets (Snell et 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) as the few-shot classification algorithm.

heading: 7 CONCLUSIONS
text: We defined the notion of authentication in the face of generative attacks, in which a generative model attempts to produce a fake reality based on observations of reality. These attacks raise numerous interesting theoretical questions and are very important and timely from a practical standpoint. We proposed to study generative attacks as a two-person zero-sum game between attacker and authenticator. In our most general setup both attacker and authenticator have access to a finite set of
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 strategies is available. A nice outcome of the analysis is that the game value depends on m,n, k only through their ratios δ “ m{n (i.e., the ”expansion ratio” between attack and leaked sample sizes) and ρ “ m{k (i.e., the “information ratio” between the number of source observations available to attacker and authenticator). As we show in Fig. 1b, there is a large range of values for which high accuracy authentication is possible, and as d grows we observe that the high authentication accuracy region in the pδ, ρq plane grows sharply. We introduce the GIM model, which is a practical approach to 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 distributions, 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.

heading: ACKNOWLEDGEMENTS
text: This work has been supported by the Blavatnik Interdisciplinary Research Center (ICRC), the Federmann Research Center (Hebrew University) and Israeli Science Foundation research grants 1523/16 and 1186/18.

heading: B PROBLEM SETUP VISUALIZATION
text: Our problem setup is illustrated in Fig. 3 for a face authentication scenario. A source θ (in this case an individual) generates IID observations (images). k images are used by the authenticator to study the source which it aims to authenticate. m images are “leaked” and obtained by an attacker who wishes to impersonate the source and pass the authentication. At test time the authenticator is presented with n images that were generated either by the true source θ, or by the attacker, and decides whether the entity that generated the images was the source θ or an attacker.

heading: C GAME VALUE VISUALIZATIONS
text: 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 a function of the different parameters of the game. Fig. 4 visualizes the game value as a function of δ and ρ, for different values of d (the observation dimension). δ “ mn is the “expansion ratio” between the source information available to the attacker through the leaked sample and the size of the attacker’s attack sample. ρ “ mk is the ”information ratio” between the number of source observations available to attacker and authenticator. One can clearly see that as d, the observation dimension, grows large, so does the accuracy of the authenticator. Even for δ values higher than 0.5, and ρ values which intuitively would give the attacker an advantage (e.g., mk “ 10).
Fig. 5 visualizes the game value as a function of δ and , for different values of d (the observation dimension). Where “ nk is the “information expansion” of the attacker with respect to the authenticator source information. Again, one can clearly see that as d, the observation dimension, grows large, so does the accuracy of the authenticator.

heading: D ADDITIONAL THEOREMS AND PROOFS FOR SEC. 4.1
text: We begin with some additional notation. Let
fApaq “ ż
θPH Qpθqf pkqθ paqdθ
denote the marginal density of A. Let QΘ|A denote the posterior probability over H given A. That is:
QΘ|Apθ|aq “ Qpθqf pkqθ paq ş
νPHQpνqf pkq ν paqdν
” Qpθqf pkqθ paq
fApaq
Also, let fY |A, fX|A, gX|A, denote the conditional densities defined by:
fY |Apy|aq “ ż
θPH f pmq θ pyqQΘ|Apθ|aqdθ
fX|Apx|aq “ ż
θPH f pnq θ pxqQΘ|Apθ|aqdθ
gX|Apx|aq “ ż
yPXm gX|Y px|yqfY |Apy|aqdy
Lemma D.1. Let G be an attacker defined by the conditional probability distribution gX|Y . Then @a P X k, x P Xn a best response strategy for D is:
Dpa, xq “ IrfX|Apx|aq ą gX|Apx|aqs (D.1)
Proof. Given an attacker strategy gX|Y , the objective for D is given by:
argmax D
EΘ„QV pΘ,D,Gq
“ argmax D EΘ„QEA„fpkqΘ
”
E X„fpnqΘ rDpA,Xqs ` E Y„fpmqΘ
EX„gX|Y p¨|Y qr1´DpA,Xqs ı
“ argmax D
EA„fA ” EX„fX|Ap¨|AqrDpA,Xqs ` EY„fY |Ap¨|AqEX„gX|Y p¨|Y qr1´DpA,Xqs ı
“ argmax D
ż
aPXk fApaq
ż
xPXn
“ fX|Apx|aqDpa, xq ` gX|Apx|aqr1´Dpa, xqs ‰ dxda
Note that D can be optimized independently for each pair a, x P X kˆXn. Hence, @a, x P X kˆXn the objective is:
argmax Dpa,xqPt0,1u
fX|Apx|aqDpa, xq ` gX|Apx|aqr1´Dpa, xqs (
And thus, the optimal decision rule for D is:
Dpa, xq “ I “ fX|Apx|aq ą gX|Apx|aq ‰
As required.
Lemma D.2. @a, x P X k ˆ Xn let the strategy for D be defined by:
Dpa, xq “ I “ fX|Apx|aq ą gX|Apx|aq ‰
Then G˚ is a best response strategy for G, iff it minimizes the `1 distance between the distributions fX|A, gX|A over the space X k ˆ Xn. Namely:
g˚X|Y P argmin gX|Y
EA„fA ż
xPXn
ˇ ˇfX|Apx|Aq ´ gX|Apx|Aq ˇ ˇ dx (D.2)
Proof. Let D be defined as in Eq. D.1, the objective for G is:
argmin G
1 2 EΘ„QV pΘ,D,Gq
“ argmin gX|Y EΘ„QEA„fpkqΘ
”
E X„fpnqΘ rDpA,Xqs ` E Y„fpmqΘ
EX„gX|Y p¨|Y qr1´DpA,Xqs ı
“ argmin gX|Y
EA„fA ” EX„fX|Ap¨|AqrDpA,Xqs ` EX„gX|Ap¨|Aqr1´DpA,Xqs ı
“ argmin gX|Y
ż
aPXk dafApaq
ż
xPXn dx
“ fX|Apx|aqDpa, xq ` gX|Apx|aqr1´Dpa, xqs ‰
“ argmin gX|Y
ż
aPXk dafApaq
ż
xPXn dxmax
fX|Apx|aq, gX|Apx|aq (
(D.3)
“ argmin gX|Y
1
2
ż
aPXk dafApaq
ż
xPXn dx
“ fX|Apx|aq ` gX|Apx|aq ` ˇ ˇfX|Apx|aq ´ gX|Apx|aq ˇ ˇ ‰
“ argmin gX|Y 1` 1 2
ż
aPXk dafApaq
ż
xPXn dx
ˇ ˇfX|Apx|aq ´ gX|Apx|aq ˇ ˇ
“ argmin gX|Y
ż
aPXk dafApaq
ż
xPXn dx
ˇ ˇfX|Apx|aq ´ gX|Apx|aq ˇ ˇ
As required. Where in Eq. D.3 we used the definition of D.
Theorem 4.1. Consider the attacker defined by:
g˚X|Y P argmin gX|Y
EA„fA „ ż
xPXn
ˇ ˇfX|Apx|Aq ´ gX|Apx|Aq ˇ ˇ dx

(D.4)
and let G˚ be the corresponding map from Xm to the set of probability distributions over Xn. Consider the authenticator defined by:
D˚pa, xq “ I ” fX|Apx|aq ą g˚X|Apx|aq ı
(D.5)
where I is the indicator function. Then pD˚,G˚q is a solution of Eq. 2.2 that satisfies Eq. 4.1.
Proof. From Lemmas D.1, D.2 we have that maxD V pD,G˚q “ V pD˚,G˚q “ minG V pD˚,Gq, from which it follows that Eq. 4.1 is satisfied and thus pD˚,G˚q is a solution of Eq. 2.2.

heading: E THEOREM AND PROOF FOR SEC. 4.2
text: Theorem E.1. For all n ď m it holds that:
max DPD min GPG
V pD,Gq “ 0.5
Proof. Consider the attacker Greplay defined by the following generative process: Given a leaked sample Y P Rmˆd, Greplay generates a sample X P Rnˆd such that Xi “ Yi @i P rns. (this is possible since we assumed n ď m). Namely, we have:
gX|Y px|yq “ n ź
i“1 δpxi ´ yiq
Where δ is the Dirac delta. Thus @a, x P X k ˆ Xn:
gX|Apx|aq “ ż
yPXm dygX|Y px|yqfY |Apy|aq
“ ż
yPXm dygX|Y px|yq
ż
θPH dθf
pmq θ pyqQΘ|Apθ|aq
“ ż
θPH dθ
ż
yPXm dy
n ź i“1 δpxi ´ yiqf pmqθ pyqQΘ|Apθ|aq
“ ż
θPH dθQΘ|Apθ|aq
ż
yPXn dy
n ź i“1 δpxi ´ yiqf pnqθ pyq ż y1PXm´n dy1f pm´nq θ py 1q
“ ż
θPH dθQΘ|Apθ|aq
ż
yPXn dy
n ź i“1 δpxi ´ yiqf pnqθ pyq
“ ż
θPH dθQΘ|Apθ|aqf
pnq θ pxq
“fX|Apx|aq
Define: D0pa, xq “ 0 @a, x P X k ˆ Xn
Then according to Theorem 4.1 pD0,Greplayq is a solution of Eq. 2.2 that satisfies Eq. 4.1, and therefore:
max DPD min GPG
V pD,Gq “V pD0,Greplayq
“1 2 EΘ„QEA„fpkqθ EY„fpmqθ ” E X„fpnqθ rDpA,Xqs ` EX„GpY qr1´DpA,Xqs ı “1 2 EΘ„QEA„fpkqθ EY„fpmqθ ” E X„fpnqθ r0s ` EX„GpY qr1s ı “1 2
As required.

heading: F ADDITIONAL THEOREMS AND PROOFS FOR SEC. 4.3

heading: F.1 NOTATION AND DEFINITIONS
text: In this section, we consider the case where the sources are d-dimensional Gaussian vectors with a known covariance matrix Σ “ CCT P Rdˆd and unknown mean vector θ P Rd. That is, the set of possible sources is H “ Rd and given θ P H the associated probability density over the domain X “ Rd is fθpxq “ 1?p2πqd| detpΣq| exp p´ 1 2 px´ θq TΣ´1px´ θqq
A sample of n examples x P Xn is considered a matrix x P Rnˆd, where the first index represents the sample and the second represents the observation space, Rd. I.e., xij P R is the j’th element of the i’th example in the sample x P Rnˆd. We continue with a few more notations that simplify the proofs. Given a matrix x P Rnˆd, we let xc “ “ xT1 , . . . , x T n
‰T P Rnd be the concatenation vector representing x. Given a vector θ P Rd, we let θc,n “ “ θT , . . . , θT ‰T P Rnd be the concatenation of n copies of θ. Given a matrix x P Rnˆd, we let x̄ ” 1n řn i“1 xi P Rd denote its mean along the sample dimension. For any matrix B P Rdˆd, we denote:
diagpB, kq “
»
—
– B 0 . . .
0 B
fi
ffi
fl
P Rkdˆkd
and
reppB, kq “
»
—
– B ¨ ¨ ¨ B ... . . . ...
B ¨ ¨ ¨ B
fi
ffi
fl
P Rkdˆkd
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 an attacker defined by the following generative process: Given a leaked sample Y P Rmˆd, G˚ generates an attack sample X P Rnˆd as follows. It first samples n vectors W1, . . . ,Wn iid„ N p0,Σq and then sets:
Xi “Wi ´ W̄ ` Ȳ (F.1)
Also, let g˚X|Y denote its associated conditional probability.
Definition F.2. For any α P R`, let Dα denote an authenticator defined as:
Dαpa, xq “ I ” }x̄´ ā}2Σ´1 ă α ı
Where I is the indicator function

heading: F.2 TECHNICAL LEMMAS
text: Lemma F.3. Let X1, . . . , Xk iid„ N pµ,Σq Where µ P Rd,Σ P Rdˆd. Then
X̄ “ 1 k
k ÿ j“1 Xj „ N pµ, 1 k Σq
Proof. We begin by observing that Xc „ N pµc,k, diagpΣ, kqq. Let B “ 1k rId ¨ ¨ ¨ Ids P R dˆkd and observe that X̄ “ BXc. Therefore, since this is an affine transformation of a Gaussian vector we have:
X̄ „ N pBµc,k, BdiagpΣ, kqBT q “ N pµ, 1
k Σq
As required.
Lemma F.4. Let X P Rd be a Gaussian vector s.t X „ N pµ,Σq, and let Xc,n P Rnd be the concatenation of n copies of X . Then:
Xc,n „ N pµc,n, reppΣ, nqq
Proof. Let
B “
»
—
– Id ... Id
fi
ffi
fl
P Rndˆd
and observe that Xc,n “ BX . Therefore, since this is an affine transformation of a Gaussian vector we have:
Xc,n „ N pBµ,BΣBT q “ N pµc,n, reppΣ, nqq
As required.
Lemma F.5. Let θ P Rd,Σ P Rdˆd represent the mean and covariance of a Gaussian distribution. Let X P Rnˆd be a random sample generated by the attacker defined in Def. F.1. Then:
Xc „ N pθc,n, diagpΣ, nq ` reppp n´m mn qΣ, nqq ” N pθc,n,Ψq
Proof. Observe that Wc „ N p0, diagpΣ, nqq. Using Lemma F.3 we get Ȳ „ N pθ, 1mΣq and observe that W̄c,n “ repp 1nId, nqWc. Using Lemma F.4 we get Ȳc,n „ N pθc,n, 1 mreppΣ, nqq. We define the following block matrices
Z “ „
Wc Ȳc,n

, B “ “ Ind ´ 1nreppId, nq, Ind ‰
and observe that:
Z „N p „
0nd θc,n

,
„
diagpΣ, nq 0 0 1mreppΣ, nq

q
Note that Xc “Wc ´ W̄c,n ` Ȳc,n “ BZ and therefore we get:
Xc „ N pB „
0nd θc,n

, B
„
diagpΣ, nq 0 0 1mreppΣ, nq

BT q
“ N ˆ θc,n, diag pΣ, nq ` rep ˆ pn´m mn qΣ, n ˙˙
As required.
Lemma F.6. Let Σ “ CCT P Rdˆd represent the covariance of a Gaussian distribution, and consider the following covariance matrix:
Ψ “ diagpΣ, nq ` repppn´m mn qΣ, nq

heading: Then its inverse is:
text: Ψ´1 “ diagpΣ´1, nq ´ n´m n2 reppΣ´1, nq
and the determinant is:
detpΨq “ ´ n
m
¯d
detpΣqn
Proof. We begin by defining the following block matrices:
U “
»
—
– Σ ... Σ
fi
ffi
fl
P Rndˆd (F.2)
V “ pn´m mn q
»
—
– Id ... Id
fi
ffi
fl
P Rndˆd (F.3)
and note that repppn´mmn qΣ, nq “ UV T . Then:
Ψ´1 “pdiagpΣ, nq ` repppn´m mn qΣ, nqq´1
“pdiagpΣ, nq ` UV T q´1
piq“diagpΣ, nq´1 ´ diagpΣ, nq´1UpId ` V T diagpΣ, nq´1Uq´1V T diagpΣ, nq´1
piiq“ diagpΣ´1, nq ´ diagpΣ´1, nqUpId ` V T diagpΣ´1, nqUq´1V T diagpΣ´1, nq
“diagpΣ´1, nq ´
»
—
– Id ... Id
fi
ffi
fl pId ` n´m nm rId ¨ ¨ ¨ Ids
»
—
– Id ... Id
fi
ffi
fl q´1n´m nm “ Σ´1 ¨ ¨ ¨ Σ´1 ‰
“diagpΣ´1, nq ´
»
—
– Id ... Id
fi
ffi
fl
m n Id n´m nm “ Σ´1 ¨ ¨ ¨ Σ´1 ‰
“diagpΣ´1, nq ´ n´m n2
»
—
– Id ... Id
fi
ffi
fl
“ Σ´1 ¨ ¨ ¨ Σ´1 ‰
“diagpΣ´1, nq ´ n´m n2 reppΣ´1, nq
As required. Where in piq we used the Woodbury matrix identity, and in piiq we used the inverse of a diagonal block matrix.
Next, we turn to find the determinant of Ψ:
detpΨq “detpdiagpΣ, nq ` repppn´m mn qΣ, nqq
“detpdiagpΣ, nq ` UV T q piiiq“ detpdiagpΣ, nqqdetpId ` V T diagpΣ, nq´1Uq pivq“ detpΣqndetpId ` V T diagpΣ´1, nqUq
“detpΣqndetpId ` n´m nm rId ¨ ¨ ¨ Ids diagpΣ´1, nq
»
—
– Σ ... Σ
fi
ffi
fl
q
“detpΣqndetpId ` n´m m Idq
“detpΣqn ´ n
m
¯d
Where in piiiq we used the matrix determinant lemma, and in pivq we used the determinant of a diagonal block matrix.
Lemma F.7. Let
hpx, µq “ expt´ 1 2σ2 px´ µqTΣ´1px´ µquI “ xTΣ´1x ă α ‰ @px, µq P Rd ˆ Rd
and define the function:
ψpµq “ ż
xPRd dxhpx, µq
Then ψpµq is log-concave over the space Rd.
Proof. We begin by noting that the function px´µqTΣ´1px´µq is convex w.r.t both x and µ, hence its negative is concave, and thus, by definition the function:
expt´ 1 2σ2 px´ µqTΣ´1px´ µqu (F.4)
is log-concave w.r.t x, µ. We now show that hpx, µq is log-concave w.r.t both x and µ. First, w.r.t µ. Let β P r0, 1s, µ1, µ2 P Rd, and observe that:
hpx, βµ1 ` p1´ βqµ2q
“ expt´ 1 2σ2 px´ βµ1 ´ p1´ βqµ2qTΣ´1px´ βµ1 ´ p1´ βqµ2quIrxTΣ´1x ă αs piq ě expt´ β
2σ2 px´ µ1qTΣ´1px´ µ1qu expt´ p1´ βq 2σ2 px´ µ2qTΣ´1px´ µ2qu
IrxTΣ´1x ă αs piiq“ expt´ β
2σ2 px´ µ1qTΣ´1px´ µ1qu expt´ p1´ βq 2σ2 px´ µ2qTΣ´1px´ µ2qu
pIrxTΣ´1x ă αsqβpIrxTΣ´1x ă αsqp1´βq
“hpx, µ1qβhpx, µ2qp1´βq
Therefore hpx, µq is log-concave w.r.t µ. Where in piq we used the log-concavity of the function in Eq. F.4, and in piiq we used the fact that IrxTΣ´1x ă αs P t0, 1u. Now, w.r.t x. Let β P r0, 1s, x1, x2 P Rd. Observe that for any convex function q we have:
I rqpx1q ă αsβ I rqpx2q ă αsp1´βq piq“I rqpx1q ă αs I rqpx2q ă αs “I rqpx1q ă α^ qpx2q ă αs piiq ď I rβqpx1q ` p1´ βqqpx2q ă αs piiiq ď I rqpβx1 ` p1´ βqx2q ă αs
Therefore IrxTΣ´1x ă αs is log-concave. Where in piq we used the fact that Irqpxq ă αs P t0, 1u, in piiq we used the fact that qpx1q ă α ^ qpx2q ă α ñ βqpx1q ` p1 ´ βqqpx2q ă α, and in piiiq we used the convexity of q. Hence, observing hpx, µq we have:
hpβx1 ` p1´ βqx2, µq
“ expt´ 1 2σ2 pβx1 ` p1´ βqx2 ´ µqTΣ´1pβx1 ` p1´ βqx2 ´ µqu
I “ pβx1 ` p1´ βqx2qTΣ´1pβx1 ` p1´ βqx2q ă α ‰
pivq ě expt´ β
2σ2 px1 ´ µqTΣ´1px1 ´ µqu expt´ p1´ βq 2σ2 px2 ´ µqTΣ´1px2 ´ µqu
I “ pβx1 ` p1´ βqx2qTΣ´1pβx1 ` p1´ βqx2q ă α ‰
pvq ě expt´ β
2σ2 px´ µ1qTΣ´1px´ µ1qu expt´ p1´ βq 2σ2 px´ µ2qTΣ´1px´ µ2qu
pI “ xT1 Σ ´1x1 ă α ‰ qβpI “ xT2 Σ ´1x2 ă α ‰ qp1´βq
“hpx1, µqβhpx2, µqp1´βq
Therefore hpx, µq is log-concave w.r.t x. Where in pivq we used the log-concavity of the function in Eq. F.4, and in pvq we used the log-concavity of IrxTΣ´1x ă αs. Finally, by using Prekopa-Leindler inequality (Prékopa, 1973) we have that ψpµq is log-concave, as required.

heading: F.3 PROOF OF THEOREM 4.2
text: Lemma F.8. Consider the attacker G˚, defined in Def. F.1. The best response strategy for the authenticator against this attacker is:
D˚pa, xq “ I ” }x̄´ ā}2Σ´1 ă α ˚ ı
Where:
α˚ “ dpm` kqpn` kq k2pn´mq log npm` kq mpn` kq
Proof. The best response authenticator satisfies:
D˚ P argmax DPD V pD,Gq
“ argmax DPD
1 2 EΘ„QEA„fpkqΘ EY„fpmqΘ rEX„fpnqΘ rDpA,Xqs ` EX„gX|Y p¨|Y qr1´DpA,Xqss
“ argmax DPD EΘ„QEA„fpkqΘ rEX„fpnqΘ rDpA,Xqs ` EX„gX|Θp¨|Θqr1´DpA,Xqss
F.5“ argmax DPD EΘ„QEA„N pΘc,k,diagpΣ,kqq “
EX„N pΘc,n,diagpΣ,nqqrDpA,Xqs ` EX„N pθc,n,Ψqr1´DpA,Xqs ‰
F.6“ argmax DPD
EΘ„Q ż
aPRkd da
ż
xPRnd dx expt´1 2 pa´Θc,kqT diagpΣ, kq´1pa´Θc,kqur
expt´1 2 px´Θc,nqT diagpΣ, nq´1px´Θc,nquDpa, xq` d
1 p nm qd expt´1 2 px´Θc,nqTΨ´1px´Θc,nqur1´Dpa, xqss
D can be chosen independently for each pair pa, xq P X kˆXn. Therefore, for any pa, xq P X kˆXn the decision rule for Dpa, xq “ 1 is:
c
p n m qd ż θPRd dθQpθq expt´1 2 rpx´ θc,nqT diagpΣ, nq´1px´ θc,nq`
pa´ θc,kqT diagpΣ, kq´1pa´ θc,kqsu ą ż
θPRd dθQpθq expt´1 2 rpx´ θc,nqTΨ´1px´ θc,nq ` pa´ θc,kqT diagpΣ, kq´1pa´ θc,kqsu
Observing the LHS integral and using the improper uniform prior assumption we have: ż
θPRd dθQpθq expt´1 2 rpx´ θc,nqT diagpΣ´1, nqpx´ θc,nq`
pa´ θc,kqT diagpΣ´1, kqpa´ θc,kqsu
“ ż θPRd dθ expt´1 2 r n ÿ i“1 xTi Σ ´1xi ` k ÿ j“1 aTj Σ ´1aj ´ 2θTΣ´1pnx̄` kāq ` pn` kqθTΣ´1θsu
“ expt´1 2 r n ÿ
i“1 xTi Σ
´1xi ` k ÿ
j“1 aTj Σ
´1aj ´ pn` kqp nx̄` kā n` k q TΣ´1pnx̄` kā n` k qsu
ż
θPRd dθ expt´n` k 2 rpθ ´ nx̄` kā n` k q TΣ´1pθ ´ nx̄` kā n` k qsu
“ expt´1 2 r n ÿ
i“1 xTi Σ
´1xi ` k ÿ
j“1 aTj Σ
´1aj ´ pn` kqp nx̄` kā n` k q TΣ´1pnx̄` kā n` k qsu
c
p 2π n` k q d detpΣq
Observing the RHS and using the improper uniform prior assumption we have: ż
θPRd dθQpθq expt´1 2 rpx´ θc,nqTΨ´1px´ θc,nq ` pa´ θc,kqT diagpΣ´1, kqpa´ θc,kqsu
“ ż θPRd dθ expt´1 2 rpx´ θc,nqTΨ´1px´ θc,nq ` pa´ θc,kqT diagpΣ´1, kqpa´ θc,kqsu
F.6“ ż θPRd dθ expt´1 2 rpx´ θc,nqT pdiagpΣ´1, nq ´ n´m n2 reppΣ´1, nqqpx´ θc,nq`
pa´ θc,kqT diagpΣ´1, kqpa´ θc,kqsu
“ ż θPRd dθ expt´1 2 r n ÿ i“1 pxi ´ θqTΣ´1pxi ´ θq ` k ÿ j“1 paj ´ θqTΣ´1paj ´ θq´
n´m n2
n ÿ
i“1
n ÿ j“1 pxi ´ θqTΣ´1pxj ´ θqsu
“ ż θPRd dθ expt´1 2 r n ÿ i“1 pxi ´ θqTΣ´1pxi ´ θq ` k ÿ j“1 paj ´ θqTΣ´1paj ´ θq´
pn´mqpx̄´ θqTΣ´1px̄´ θqsu
“ ż θPRd dθ expt´1 2 r n ÿ i“1 xTi Σ ´1xi ` k ÿ j“1 aTj Σ ´1aj ´ pn´mqx̄TΣ´1x̄`
pm` kqθTΣ´1θ ´ 2θTΣ´1pmx̄` kāqsu
“ expt´1 2 r n ÿ
i“1 xTi Σ
´1xi ` k ÿ
j“1 aTj Σ ´1aj ´ pn´mqx̄TΣ´1x̄´
pm` kqpmx̄` kā m` k q TΣ´1pmx̄` kā m` k qsu ż
θPRd dθ expt´m` k 2 rpθ ´ mx̄` kā m` k q TΣ´1pθ ´ mx̄` kā m` k qsu
“ c
p 2π m` k q d detpΣq expt´1 2 r n ÿ
i“1 xTi Σ
´1xi ` k ÿ
j“1 aTj Σ ´1aj ´ pn´mqx̄TΣ´1x̄´
pm` kqpmx̄` kā m` k q TΣ´1pmx̄` kā m` k qsu
Therefore the decision rule is c
p n m qd expt1 2 rpn` kqpnx̄` kā n` k q TΣ´1pnx̄` kā n` k qsu c p 2π n` k q d ą
expt1 2 rpn´mqx̄TΣ´1x̄` pm` kqpmx̄` kā m` k q TΣ´1pmx̄` kā m` k qsu c p 2π m` k q d
ô
d
pnpm` kq mpn` kq q d expt1 2 rpn` kqpnx̄` kā n` k q TΣ´1pnx̄` kā n` k qsu ą
expt1 2 rpn´mqx̄TΣ´1x̄` pm` kqpmx̄` kā m` k q TΣ´1pmx̄` kā m` k qsu
ôd log npm` kq mpn` kq ą pn´mqx̄ TΣ´1x̄` pm` kqpmx̄` kā m` k q TΣ´1pmx̄` kā m` k q´
pn` kqpnx̄` kā n` k q TΣ´1pnx̄` kā n` k q
ôdpm` kqpn` kq log npm` kq mpn` kq ą
k2pn´mqx̄TΣ´1x̄´ 2k2pn´mqx̄TΣ´1ā` k2pn´mqāTΣ´1ā
ôdpm` kqpn` kq k2pn´mq log npm` kq mpn` kq ą px̄´ āq TΣ´1px̄´ āq
As required.
Lemma F.9. Consider the authenticator Dα, as defined in Def. F.2. Then any attacker G, represented by a conditional probability gX|Y , that satisfies the condition x̄ “ ȳ for any leaked sample y P Rmˆd and attacker generated sample x P tRnˆd : gX|Y px|yq ą 0u, satisfies:
G P argmin G1PG V pDα,G1q @α P R`
Proof. The best response attacker satisfies:
g1X|Y P argmin gX|Y
1 2 EΘ„QEA„fpkqΘ EY„fpmqΘ rEX„fpnqΘ rDαpA,Xqs ` EX„gX|Y p¨|Y qr1´DαpA,Xqss
“ argmin gX|Y EΘ„QEA„fpkqΘ EY„fpmqΘ EX„gX|Y p¨|Y qr1´DαpA,Xqs
“ argmax gX|Y EΘ„QEA„fpkqΘ EY„fpmqΘ EX„gX|Y p¨|Y qrDαpA,Xqs
“ argmax gX|Y
EΘ„QEA iid„N pΘ,ΣqEY iid„N pΘ,ΣqEX„gX|Y p¨|Y q ” I ” › ›X̄ ´ Ā › › 2 Σ´1 ă α ıı
Lemma F.3“ argmax gX|Y EΘ„QEĀ„N pΘ, 1kΣqEY iid„N pΘ,ΣqEX„gX|Y p¨|Y q ” I ” › ›X̄ ´ Ā › › 2 Σ´1 ă α ıı
“ argmax gX|Y
ż
yPRmˆd dy
ż
xPRnˆd dxgX|Y px|yq
ż
āPRd dāI
” }x̄´ ā}2Σ´1 ă α ı
ż
θPRd dθQpθq
expt´k 2 pā´ θqTΣ´1pā´ θqu expt´1 2
m ÿ j“1 pyj ´ θqTΣ´1pyj ´ θqu
Note that gX|Y px|yq can be chosen independently for each y P Rmˆd. Thus, we can optimize it independently for each y P Rmˆd and we have:
g1X|Y p¨|yq P argmax gX|Y p¨|yq
ż
xPRnˆd dxgX|Y px|yq
ż
āPRd dāI
” }x̄´ ā}2Σ´1 ă α ı
ż
θPRd dθQpθq
expt´k 2 pā´ θqTΣ´1pā´ θqu expt´1 2
m ÿ j“1 pyj ´ θqTΣ´1pyj ´ θqu
Note that for any PDF f over Rnˆd and a function ϕ : Rnˆd Ñ R , it holds that ş
xPRnˆd dxfpxqϕpxq ď supxϕpxq. Therefore, there exists a deterministic distribution g 1 X|Y px|yq “ δpx ´ x1q that achieves the maximum. Thus, it’s sufficient to find a vector xG that achieves the maximum:
xG P argmax x
ż
x1PRnˆd dx1δpx1 ´ xq
ż
āPRd dāI
”
› ›x̄1 ´ ā › › 2
Σ´1 ă α
ı
ż
θPRd dθQpθq
expt´k 2 pā´ θqTΣ´1pā´ θqu expt´1 2
m ÿ j“1 pyj ´ θqTΣ´1pyj ´ θqu
“ argmax x
ż
āPRd dāI
” }x̄´ ā}2Σ´1 ă α ı
ż
θPRd dθQpθq
expt´k 2 pā´ θqTΣ´1pā´ θqu expt´1 2
m ÿ j“1 pyj ´ θqTΣ´1pyj ´ θqu
p˚q“ argmax x
ż
āPRd dāI
” }x̄´ ā}2Σ´1 ă α ı
ż
θPRd dθ
expt´1 2 rkpā´ θqTΣ´1pā´ θq `
m ÿ j“1 pyj ´ θqTΣ´1pyj ´ θqsu
“ argmax x
ż
āPRd dā expt´1 2 rkāTΣ´1āsuI ” }x̄´ ā}2Σ´1 ă α ı
ż
θPRd dθ
expt´1 2 rpm` kqθTΣ´1θ ´ 2θTΣ´1pmȳ ` kāqsu
“ argmax x
ż
āPRd dā expt´1 2 rkāTΣ´1ā´ 1 m` k pmȳ ` kāq TΣ´1pmȳ ` kāqsu
I ” }x̄´ ā}2Σ´1 ă α ı
ż
θPRd dθ expt´pm` kq 2 pθ ´ mȳ ` kā m` k q TΣ´1pθ ´ mȳ ` kā m` k qu
“ argmax x
ż
āPRd dā expt´1 2 rkāTΣ´1ā´ 1 m` k pmȳ ` kāq TΣ´1pmȳ ` kāqsu
I ” }x̄´ ā}2Σ´1 ă α ı
“ argmax x
ż
āPRd dā expt´1 2 r mk m` k ā TΣ´1ā´ 2mk m` k ȳ TΣ´1ā` mk m` k ȳ TΣ´1ȳsu
I ” }x̄´ ā}2Σ´1 ă α ı
“ argmax x
ż
āPRd dā expt´ mk 2pm` kq rpā´ ȳq TΣ´1pā´ ȳqsuI ” }x̄´ ā}2Σ´1 ă α ı
Where in p˚q we used the fact that Qpθq is the improper uniform prior. Note that the expression depends only on the mean x̄. Therefore, it’s sufficient to find a mean vector x̄ that maximizes the expression. We substitute the integration variable to ϕ “ ā´ x̄ and obtain:
x̄G P argmax x̄
ż
tϕPRd:ϕTΣ´1ϕăαu dϕ expt´ mk 2pm` kq rpϕ` x̄´ ȳq TΣ´1pϕ` x̄´ ȳqsu
” argmax x̄ ψpȳ ´ x̄q ” argmax x̄ ψpµq
Where ψ is defined as in Lemma F.7 (with σ “ m`kmk ), from which it follows that ψpµq is logconcave, and therefore has at most one local extremum which can only be a maximum. Therefore, it is sufficient to show that µ “ 0 (i.e., x̄ “ ȳ) is a local extremum by equating the gradient at the point to 0.
B Bµψpµq “ B Bµ
ż
tϕPRd:ϕTΣ´1ϕăαu dϕ expt´ mk 2pm` kq rpϕ´ µq TΣ´1pϕ´ µqsu
“ ´ mk 2pm` kq
ż
tϕPRd:ϕTΣ´1ϕăαu dϕ expt´ mk 2pm` kq rpϕ´ µq TΣ´1pϕ´ µqsu
B Bµ pϕ´ µq TΣ´1pϕ´ µq
“ ´ mkpm` kq
ż
tϕPRd:ϕTΣ´1ϕăαu dϕ expt´ mk 2pm` kq rpϕ´ µq TΣ´1pϕ´ µqsuΣ´1pµ´ ϕq
Therefore: B Bµψpµq|µ“0 “ mk pm` kq ż tϕPRd:ϕTΣ´1ϕăαu dϕ expt´ mk 2pm` kq rϕ TΣ´1ϕsuΣ´1ϕ
Note that since the domain of integration is 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., B Bµψpµq|µ“0 “ 0. Therefore, x̄ “ ȳ (µ “ 0) achieves the global maximum, and any attacker that satisfies the condition: x̄ “ ȳ for any leaked sample y P Rmˆd and attacker generated sample x P tRnˆd : gX|Y px|yq ą 0u satisfies:
G P argmin G1PG V pDα,G1q @α P R`
As required.
Corollary F.10. Consider an authenticator Dα, as defined in Def. F.2. Then the attacker G˚, defined in Def. F.1, is a best response. i.e.:
G˚ P argmin G1PG V pDα,G1q @α P R`
Proof. Directly from Lemma F.9
Theorem F.11. The game value is: max D min G V pD,Gq “ min G max D V pD,Gq “ V pD˚,G˚q “
1 2 ` 1 2Γpd2 q rγpd 2 , dnpm` kq 2kpn´mq log npm` kq mpn` kq q ´ γp d 2 , dmpn` kq 2kpn´mq log npm` kq mpn` kq qs
Where γ is the lower incomplete gamma function.
Proof. From the max-min inequality we have: max D min G V pD,Gq ď min G max D V pD,Gq
On the other hand, using Lemma F.8 and Corollary F.10 we have:
max D min G V pD,Gq ě min G V pD˚,Gq F.10“ V pD˚,G˚q F.8“ max D V pD,G˚q ě min G max D V pD,Gq
Therefore: max D min G V pD,Gq “ min G max D V pD,Gq “ V pD˚,G˚q The game value is given by: V pD˚,G˚q “EΘ„QV pΘ,D˚,G˚q
“1 2 EΘ„QEA„fpkqΘ EY„fpmqΘ ” E X„fpnqΘ rD˚pA,Xqs ` EX„g˚ X|Y p¨|Y q r1´D˚pA,Xqs ı “1 2 EΘ„QEA„fpkqΘ EY„fpmqΘ
”
E X„fpnqΘ
”
Ir › ›X̄ ´ Ā › ›
2 Σ´1 ă α˚s
ı
` EX„g˚ X|Y p¨|Y q
”
1´ Ir › ›X̄ ´ Ā › ›
2 Σ´1 ă α˚s
ıı
“1 2 ` 1 2 EΘ„QEA„fpkqΘ EX„fpnqΘ ” Ir › ›x̄´ Ā › › 2 Σ´1 ă α˚s ı ´
1 2 EΘ„QEA„fpkqΘ EX„g˚X|Θp¨|Θq ” Ir › ›x̄´ Ā › › 2 Σ´1 ă α˚s ı
Observing the first term we have: 1
2 EΘ„QEA„fpkqΘ EX„fpnqΘ
”
Ir › ›X̄ ´ Ā › ›
2 Σ´1 ă α˚s
ı
“1 2 EΘ„QEA„fpkqΘ EX„fpnqΘ “ IrpX̄ ´ ĀqTΣ´1pX̄ ´ Āq ă α˚s ‰ “1 2 EΘ„QEA„fpkqΘ EX„fpnqΘ “ IrpX̄ ´ ĀqT pCCT q´1pX̄ ´ Āq ă α˚s ‰ “1 2 EΘ„QEA„fpkqΘ EX„fpnqΘ “ IrpX̄ ´ ĀqTC´TC´1pX̄ ´ Āq ă α˚s ‰ “1 2 EΘ„QEA„fpkqΘ EX„fpnqΘ “ IrpC´1pX̄ ´ ĀqqT pC´1pX̄ ´ Āqq ă α˚s ‰ ”1 2 EΘ„QEA„fpkqΘ EX„fpnqΘ “ IrZTZ ă α˚s ‰
“p˚q Observe that
Z “ C´1pX̄ ´ Āq “ C´1rpX̄ ´Θq ´ pĀ´Θqs
“ C´1rId,´Ids „ X̄ ´Θ Ā´Θ  “ rC´1,´C´1s „ X̄ ´Θ Ā´Θ 
Note that: „
X̄ ´Θ Ā´Θ
 „ N p02d, „ 1 nΣ 0dˆd
0dˆd 1 kΣ

q
Therefore:
Z „ N p0d, rC´1,´C´1s „ 1 nΣ 0dˆd
0dˆd 1 kΣ
 „
C´T ´C´T  q
“ N p0d, p 1 n ` 1 k qC´1ΣC´T q “ N p0d, n` k nk C´1CCTC´T q “ N p0d, n` k nk Idq
We denote Z̃ “ b
nk n`kZ „ N p0d, Idq, and thus Z̃1, . . . , Z̃d are independent standard normal
random variables and Z̃T Z̃ „ χ2pdq. Therefore, ZTZ “ n`knk Z̃ T Z̃ „ Γpk “ d2 , θ “ 2 n`k nk q and we have:
p˚q “1 2 EΘ„QEA„fpkqΘ EX„fpnqΘ “ IrZTZ ă α˚s ‰
“1 2 EΘ„QEZTZ„Γpk“ d2 ,θ“2n`knk q “ IrZTZ ă α˚s ‰
piq“ 1 2 EΘ„Q 1 Γpd2 q γpd 2 , nkα˚ 2pn` kq q
“1 2 1 Γpd2 q γpd 2 , nkα˚ 2pn` kq q
Where in piqWe used the CDF of the Gamma distribution in which γ is the lower incomplete gamma function.
Similarly, observing the second term we have:
1 2 EΘ„QEA„fpkqΘ EX„g˚X|Θp¨|Θq ” Ir › ›X̄ ´ Ā › › 2 Σ´1 ă α˚s ı
”1 2 EΘ„QEA„fpkqΘ EX„g˚X|Θp¨|Θq “ IrV TV ă α˚s ‰
“p˚˚q Where:
V “ C´1pX̄ ´ Āq “ C´1rpX̄ ´Θq ´ pĀ´Θqs
“ C´1rId,´Ids „ X̄ ´Θ Ā´Θ  “ rC´1,´C´1s „ X̄ ´Θ Ā´Θ 
Using the definition of G˚ (Definition F.1) and Lemma F.3 we have: „
X̄ ´Θ Ā´Θ
 „ N p02d, „ 1 mΣ 0dˆd
0dˆd 1 kΣ

q
Therefore:
V „ N p0d, rC´1,´C´1s „ 1 mΣ 0dˆd
0dˆd 1 kΣ
 „
C´T ´C´T  q “ N p0d, m` k mk Idq
And similarly to the first term, we get:
V TV „ Γpk “ d 2 , θ “ 2m` k mk q
And thus:
p˚˚q “ 1 2 1 Γpd2 q γpd 2 , mkα˚ 2pm` kq q
Therefore, the game value is given by:
V pD˚,G˚q “ 1 2 ` 1 2 1 Γpd2 q rγpd 2 , nkα˚ 2pn` kq q ´ γp d 2 , mkα˚ 2pm` kq qs
“ 1 2 ` 1 2 1 Γpd2 q rγpd 2 , dnpm` kq 2kpn´mq log npm` kq mpn` kq q ´ γp d 2 , dmpn` kq 2kpn´mq log npm` kq mpn` kq qs
As required.
Finally, we prove Theorem 4.2 and Corollary 4.3.
Theorem 4.2. Define δ “ m{n ď 1 and let ρ “ m{k. Consider the attacker G˚ defined by the following generative process: Given a leaked sample Y P Rmˆd, G˚ generates a sample X P Rnˆd as follows: it first samples n vectors W1, . . . ,Wn iid„ N p0,Σq and then sets: Xi “ Wi ´ W̄ ` Ȳ .

heading: Define the authenticator D˚ by:
text: D˚pa, xq “ I « }x̄´ ā}2Σ´1 ă d p1` ρq ` 1` ρδ´1 ˘ np1´ δq log ˆ ρ` 1 ρ` δ ˙ ff
(F.5)
Then pD˚,G˚q is a solution of Eq. 2.2 that satisfies Eq. 4.1.
Proof. Directly from Lemma F.8, Corollary F.10, and Theorem F.11 by assigning δ “ mn , ρ “ m k .
Corollary 4.3. Define δ and ρ as in Theorem 4.2. Then the game value for the Gaussian case is:
1 2 ` 1
2Γpd2 q
„
γ
ˆ
d 2 , dp1` ρq 2p1´ δq log 1` ρ δ ` ρ
˙ ´ γ ˆ d 2 , dpδ ` ρq 2p1´ δq log 1` ρ δ ` ρ ˙
(F.6)
Where γ is the lower incomplete Gamma function, and Γ is the Gamma function.
Proof. Directly from Theorem F.11 by assigning δ “ mn , ρ “ m k .

heading: F.4 GAME VALUE FOR A MAXIMUM LIKELIHOOD ATTACKER
text: 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. 1c 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. We find the best response authenticator to this attacker and the associated game value. Fig. 6 visualizes the difference in theoretical game value between the ML attacker (see Definition F.12) and the optimal attacker (see Definition F.1) for different values of d (the dimension of observations), and demonstrates that the ML attacker is indeed sub-optimal.
Definition F.12. Let GML denote an attacker defined by the following generative process: Given a leaked sample Y P Rmˆd, GML generates an attack sample X
iid„ N pȲ ,Σq Lemma F.13. Let θ P Rd,Σ P Rdˆd represent the mean and covariance of a Gaussian distribution. Let X P Rnˆd be a random sample generated by the attacker defined in Def. F.12. Then:
Xc „ N pθc,n, diagpΣ, nq ` reppp 1
m qΣ, nqq ” N pθc,n,ΨMLq
Proof. Let W1, . . . ,Wn iid„ N p0,Σq, observe that Xi “ Ȳ `Wi @i P rns, and thus:
Xc “ Ȳc,n `Wc Where Wc „ N p0 ¨ 1dn, diagpΣ, nq. Using Lemma F.3 we have Ȳ „ N pθ, 1mΣq and using Lemma F.4 we have Ȳc,n „ N pθc,n, repp 1mΣ, nqq.
Let Z “ „
Wc Ȳc,n

and B “ rIndˆnd , Indˆnds, then Xc “Wc ` Ȳc,n “ BZ. Note that:
Z „ N p „
0nd θc,n

,
„
diagpΣ, nq 0 0 repp 1mΣ, nq

q
and therefore we have:
Xc „N pB „
0nd θc,n

, B
„
diagpΣ, nq 0 0 repp 1mΣ, nq

BT q
“N pθc,n, diagpΣ, nq ` repp 1
m Σ, nqq
As required.
Lemma F.14. Let Σ “ CCT P Rdˆd represent the covariance of a Gaussian distribution, and consider the following covariance matrix: ΨML “ diagpΣ, nq ` repp 1mΣ, nq. Then:
Ψ´1ML “ diagpΣ ´1, nq ´ 1 n`mreppΣ ´1, nq
and the determinant is: detpΨq “ detpΣqnpn`m
m qd
Proof. To find the inverse of ΨML we first define:
U “
»
—
– Σ ... Σ
fi
ffi
fl P Rndˆd, V “ 1 m
»
—
– Id ... Id
fi
ffi
fl
P Rndˆd (F.7)
Therefore we have:
Ψ´1ML “pdiagpΣ, nq ` repp 1 m Σ, nqq´1
“pdiagpΣ, nq ` UV T q´1
piq“diagpΣ, nq´1 ´ diagpΣ, nq´1UpId ` V T diagpΣ, nq´1Uq´1V T diagpΣ, nq´1
piiq“ diagpΣ´1, nq ´ diagpΣ´1, nqUpId ` V T diagpΣ´1, nqUq´1V T diagpΣ´1, nq
“diagpΣ´1, nq ´
»
—
– Id ... Id
fi
ffi
fl pId ` 1
m rId ¨ ¨ ¨ Ids
»
—
– Id ... Id
fi
ffi
fl q´1 1 m “ Σ´1 ¨ ¨ ¨ Σ´1 ‰
“diagpΣ´1, nq ´
»
—
– Id ... Id
fi
ffi
fl pId ` n
m Idq´1
1
m
“ Σ´1 ¨ ¨ ¨ Σ´1 ‰
“diagpΣ´1, nq ´
»
—
– Id ... Id
fi
ffi
fl ppn`m m qIdq´1 1 m “ Σ´1 ¨ ¨ ¨ Σ´1 ‰
“diagpΣ´1, nq ´ 1 n`m
»
—
– Id ... Id
fi
ffi
fl Id “ Σ´1 ¨ ¨ ¨ Σ´1 ‰
“diagpΣ´1, nq ´ 1 n`mreppΣ ´1, nq
As required. Where in piq we used the Woodbury matrix identity, and in piiq we used the inverse of a diagonal block matrix.
Next, we turn to find the determinant of ΨML:
detpΨq “detpdiagpΣ, nq ` reppp 1 m qΣ, nqq
“detpdiagpΣ, nq ` UV T q piiiq“ detpdiagpΣ, nqqdetpId ` V T diagpΣ, nq´1Uq pivq“ detpΣqn detpId ` V T diagpΣ´1, nqUq
“detpΣqn detpId ` 1
m rId ¨ ¨ ¨ Ids diagpΣ´1, nq
»
—
– Σ ... Σ
fi
ffi
fl
q
“detpΣqn detppn`m m qIdq “detpΣqnpn`m m qd
Where in piiiq we used the matrix determinant lemma, and in pivq we used the determinant of a diagonal block matrix.
Lemma F.15. Consider the attacker GML, defined in F.12. The best response strategy for the authenticator against this attacker is:
DMLpa, xq “ I ” }x̄´ ā}2Σ´1 ă αML ı
Where:
αML “ dpn` kqpnm` nk `mkq k2n2 logpnm` nk `mk mpn` kq q
Proof. The best response authenticator satisfies:
D˚ P argmax DPD V pD,GMLq
“ argmax DPD
1 2 EΘ„QEA„fpkqΘ EY„fpmqΘ ” E X„fpnqΘ rDpA,Xqs ` EX„gML X|Y p¨|Y q r1´DpA,Xqs ı
“ argmax DPD EΘ„QEA„fpkqΘ
”
E X„fpnqΘ rDpA,Xqs ` EX„gML X|Θp¨|Θq
r1´DpA,Xqs ı
Lemma F.13“ argmax DPD EΘ„QEA„N pΘc,k,diagpΣ,kqq “
EX„N pΘc,n,diagpΣ,nqqrDpA,Xqs ` EX„N pθc,n,ΨMLqr1´DpA,Xqs ‰
“ argmax DPD
EΘ„Q ż
aPRkd da
ż
xPRnd dx expt´1 2 pa´Θc,kqT diagpΣ, kq´1pa´Θc,kqu
r
d
1 |detpdiagpΣ, nqq| expt´ 1 2 px´Θc,nqT diagpΣ, nq´1px´Θc,nquDpa, xq`
d
1 |detpΨMLq| expt´1 2 px´Θc,nqTΨ´1MLpx´Θc,nqur1´Dpa, xqss
Lemma F.14“ argmax DPD
EΘ„Q ż
aPRkd da
ż
xPRnd dx expt´1 2 pa´Θc,kqT diagpΣ, kq´1pa´Θc,kqur
c
pn`m m qd expt´1 2 px´Θc,nqT diagpΣ, nq´1px´Θc,nquDpa, xq`
expt´1 2 px´Θc,nqTΨ´1MLpx´Θc,nqur1´Dpa, xqss
D can be chosen independently for each pair pa, xq P X kˆXn. Therefore, for any pa, xq P X kˆXn the decision rule for Dpa, xq “ 1 is: c
pn`m m qd ż θPRd dθQpθq expt´1 2 px´ θc,nqT diagpΣ, nq´1px´ θc,nqu
expt´1 2 pa´ θc,kqT diagpΣ, kq´1pa´ θc,kqu ą ż
θPRd dθQpθq expt´1 2 px´ θc,nqTΨ´1MLpx´ θc,nqu expt´ 1 2 pa´ θc,kqT diagpΣ, kq´1pa´ θc,kqu
Observing the LHS integral and using the improper uniform prior assumption, we obtain: ż
θPRd dθQpθq expt´1 2 rpx´ θc,nqT diagpΣ, nq´1px´ θc,nq`
pa´ θc,kqT diagpΣ, kq´1pa´ θc,kqsu
“ ż θPRd dθ expt´1 2 r n ÿ i“1 xTi Σ ´1xi ` k ÿ j“1 aTj Σ ´1aj ´ 2θTΣ´1pnx̄` kāq ` pn` kqθTΣ´1θsu
“ expt´1 2 r n ÿ
i“1 xTi Σ
´1xi ` k ÿ
j“1 aTj Σ
´1aj ´ pn` kqp nx̄` kā n` k q TΣ´1pnx̄` kā n` k qsu
ż
θPRd dθ expt´n` k 2 rpθ ´ nx̄` kā n` k q TΣ´1pθ ´ nx̄` kā n` k qsu
“ expt´1 2 r n ÿ
i“1 xTi Σ
´1xi ` k ÿ
j“1 aTj Σ
´1aj ´ pn` kqp nx̄` kā n` k q TΣ´1pnx̄` kā n` k qsu
c
p 2π n` k q d detpΣq
Observing the RHS and using the improper uniform prior assumption, we obtain: ż
θPRd dθQpθq expt´1 2 rpx´ θc,nqTΨ´1MLpx´ θc,nq ` pa´ θc,kq T diagpΣ´1, kqpa´ θc,kqsu
“ ż θPRd dθ expt´1 2 rpx´ θc,nqTΨ´1MLpx´ θc,nq ` pa´ θc,kq T diagpΣ´1, kqpa´ θc,kqsu
F.14“ ż θPRd dθ expt´1 2 rpx´ θc,nqT pdiagpΣ´1, nq ´ 1 n`mreppΣ ´1, nqqpx´ θc,nq`
pa´ θc,kqT diagpΣ´1, kqpa´ θc,kqsu
“ ż θPRd dθ expt´1 2 r n ÿ i“1 pxi ´ θqTΣ´1pxi ´ θq ` k ÿ j“1 paj ´ θqTΣ´1paj ´ θq´
n2
n`m px̄´ θq TΣ´1px̄´ θqsu
piq“ expt´1 2 r n ÿ
i“1 xTi Σ
´1xi ` k ÿ
j“1 aTj Σ
´1aj ´ n2 n`mx̄ TΣ´1x̄´ nm` nk `mk n`m v TΣ´1vsu
ż
θPRd dθ expt´1 2 nm` nk `mk n`m rv TΣ´1vsu
“ expt´1 2 r n ÿ
i“1 xTi Σ
´1xi ` k ÿ
j“1 aTj Σ
´1aj ´ n2 n`mx̄ TΣ´1x̄´ nm` nk `mk n`m v TΣ´1vsu
c
p 2πpn`mq nm` nk `mk q d detpΣq
Where in piq we denoted v “ nmx̄`kpn`mqānm`nk`mk . Therefore, the decision rule is
expt1 2 rpn` kqpnx̄` kā n` k q TΣ´1pnx̄` kā n` k qsu
d
p 1 mpn` kq q d ą
expt1 2 r n
2 n`mx̄ TΣ´1x̄` nm` nk `mk n`m v TΣ´1vsu
c
p 1 nm` nk `mk q d
ô
d
pnm` nk `mk mpn` kq q d ą
expt1 2 r n
2 n`mx̄ TΣ´1x̄` nm` nk `mk n`m v TΣ´1v ´ pn` kqpnx̄` kā n` k q TΣ´1pnx̄` kā n` k qsu
ôd logpnm` nk `mk mpn` kq q ą
n2 n`mx̄ TΣ´1x̄` nm` nk `mk n`m v TΣ´1v ´ pn` kqpnx̄` kā n` k q TΣ´1pnx̄` kā n` k q
ôd logpnm` nk `mk mpn` kq q ą
k2n2
pn` kqpnm` nk `mkq px̄´ āq TΣ´1px̄´ āq
ôpx̄´ āqTΣ´1px̄´ āq ă dpn` kqpnm` nk `mkq k2n2 logpnm` nk `mk mpn` kq q
As required.
Theorem F.16. Fix the attacker to be GML as defined in F.12, then the game value is:
max D
V pD,GMLq Lemma F.15“ V pDML,GMLq “
1 2 ` 1 2 1 Γpd2 q rγpd 2 , dpnm` nk `mkq 2nk log nm` nk `mk mpn` kq q´ γpd 2 , dmpn` kq 2nk log nm` nk `mk mpn` kq qs “
1 2 ` 1 2 1 Γpd2 q rγpd 2 , d 2 p1` ρ` δq log 1` ρ` δ ρ` δ q ´ γp d 2 , d 2 pρ` δq log 1` ρ` δ ρ` δ qs
Where ρ “ mk , δ “ m n , and γ is the lower incomplete gamma function.
Proof. The game value is given by:
V pDML,GMLq “EΘ„QV pΘ,DML,GMLq
“1 2 EΘ„QEA„fpkqΘ EY„fpmqΘ ” E X„fpnqΘ rDMLpA,Xqs ` EX„gML X|Y p¨|Y q r1´DMLpA,Xqs ı “1 2 EΘ„QEA„fpkqΘ EY„fpmqΘ
”
E X„fpnqΘ
”
Ir › ›X̄ ´ Ā › ›
2 Σ´1 ă αMLs
ı
` EX„gML X|Y p¨|Y q
”
1´ Ir › ›X̄ ´ Ā › ›
2 Σ´1 ă αMLs
ıı
“1 2 ` 1 2 EΘ„QEA„fpkqΘ EX„fpnqΘ ” Ir › ›X̄ ´ Ā › › 2 Σ´1 ă αMLs ı ´
1 2 EΘ„QEA„fpkqΘ EX„gMLX|Θp¨|Θq ” Ir › ›X̄ ´ Ā › › 2 Σ´1 ă αMLs ı
Observing the first term, we can see that by replacing α˚ with αML in the analog part of the proof for Theorem F.11 we get:
1 2 EΘ„QEA„fpkqΘ EX„fpnqΘ ” Ir › ›X̄ ´ Ā › › 2 Σ´1 ă αMLs ı “ 1 2 1 Γpd2 q γpd 2 , nkαML 2pn` kq q
Again, similarly to the analog part of the proof for Theorem F.11, observing the second term we have:
1 2 EΘ„QEA„fpkqΘ EX„gMLX|Θp¨|Θq ” Ir › ›X̄ ´ Ā › › 2 Σ´1 ă αMLs ı
”1 2 EΘ„QEA„fpkqΘ EX„gMLX|Θp¨|Θq “ IrV TV ă αMLs ‰
“p˚q Where:
V “ C´1pX̄ ´ Āq “ C´1rpX̄ ´Θq ´ pĀ´Θqs
“ C´1rId,´Ids „ X̄ ´Θ Ā´Θ  “ rC´1,´C´1s „ X̄ ´Θ Ā´Θ 
Using the definition of GML (Definition F.12) we have X̄ „ N pθ, n`mnm Σq, using Lemma F.3 we have Ā „ N pθ, 1kΣq, and thus:
„
X̄ ´Θ Ā´Θ
 „ N p „
θ θ

,
„ n`m nm Σ 0
0 1kΣ

q
Therefore:
V „ N p0, rC´1,´C´1s „ n`m nm Σ 0
0 1kΣ
 „
C´T ´C´T  q “ N p0d, nm` nk `mk nmk Idq
We denote Ṽ “ b
nmk nm`nk`mkV and thus Ṽ1, . . . , Ṽd are independent standard normal random
variables and Ṽ T Ṽ „ χ2pdq. Therefore
V TV „ Γpk “ d 2 , θ “ 2nm` nk `mk nmk q
And we have:
p˚q “ 1 2 1 Γpd2 q γpd 2 , nmkαML 2pnm` nk `mkq q
Hence, the game value is given by:
V pD˚,G˚q “ 1 2 ` 1 2 1 Γpd2 q rγpd 2 , nkαML 2pn` kq q ´ γp d 2 , nmkαML 2pnm` nk `mkq qs “
1 2 ` 1 2 1 Γpd2 q rγpd 2 , dpnm` nk `mkq 2nk log nm` nk `mk mpn` kq q´ γpd 2 , dmpn` kq 2nk log nm` nk `mk mpn` kq qs
As required.

heading: G EXPERIMENTS - DATASETS
text: Below we provide details on the datasets used for the authentication experiments on faces and characters. The VoxCeleb2 (Nagrani et al., 2017; Chung & Zisserman, 2018) dataset contains cropped face videos of 6112 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ˆ 64, and augmented it using horizontal flip. The Omniglot dataset (Lake et al., 2015) contains handwritten character images from 50 alphabets. There are 1623 different characters, and 20 examples for each character. We use the splits and augmentations suggested by Vinyals et al. (2016) and used by Snell et al. (2017).

heading: H EXPERIMENTS - IMPLEMENTATION DETAILS
text: 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 a neural network Dpa, xq that can be expressed as Dpa, xq “ σpTDpaq, TDpxqq, and the generator is a neural network Gpyq that can be expressed as Gpyqi “ ϕpWi ´ W̄ ` TGpyqq @i P rns. In what follows we describe our implementation of these models for each of the experiments.

heading: H.1 GAUSSIAN SOURCES
text: Authenticator Architecture: For the statistic function TD, we use a concatenation of the mean and standard deviation of the sample. For the comparison function σ, we use the element-wise absolute difference between the statistics TDpaq, TDpxq, followed by a linear layer. Attacker Architecture: For the statistic function TG , we use the sample mean, i.e., TGpyq “ ȳ. The noise vectors Wi are generated as follows: First, n Gaussian noise vectors Z1, . . . , Zn
iid„ N p0, Idq are drawn, then each vector Zi is passed through a linear layer to obtain Wi. Finally, the decoder ϕ is the identity function.
Optimization details: The model is trained in an authentication setup as in our theoretical setup, using alternating gradient descent as is common in GAN optimization (Mescheder et al., 2018). Each iteration begins when a source θ P Rd is drawn from the prior distribution Q “ N p0, 10Idq. Samples A P Rkˆd, Y P Rmˆd, Xθ P Rnˆd are drawn IID from fθ “ N pθ, Idq, where Xθ represents a real sample from θ. The attacker, given the leaked sample Y , generates a fake sample XG “ GpY q P Rnˆd, passes it to D, and suffers the loss ´ logpsigmoidpDpA,XGqqq. The authenticator, D, receives as input the source information sample A, outputs a prediction for each of the test samples Xθ, XG , and suffers the binary cross-entropy loss ´0.5 plog psigmoidpDpA,Xθqqq ` log psigmoidp1´DpA,XGqqqq. Each experiment is trained for 200K iterations with a batch size of 4000 using the Adam optimizer (Kingma & Ba, 2015) with learning rate 10´4.

heading: H.2 EXPERIMENTS ON VOXCELEB2 AND OMNIGLOT
text: To describe the models we begin with some notation. We let c denote the number of image channels, h denote the image size (we only consider square images of size cˆ hˆ h), and l denote the latent dimension of the model.
Authenticator Architecture: As mentioned above, the authenticator is a neural network model that can be expressed as: Dpa, xq “ σpTDpaq, TDpxqq The statistic function TD maps a sample of images to a statistic vector s P R6l in the following way: Each image in the sample is mapped using encoders EDsrc, E D env : r´1, 1scˆhˆh Ñ Rl to two latent vectors vsrc, venv P Rl, respectively. vsrc is designed to represent the source θ, and venv is designed to represent the environment (e.g., pose, lighting, expression). To represent the source of the sample, the sample mean of vsrc is taken. To represent the sample distribution, venv is passed through a non-linear statistic module ζ which is meant to capture more complex statistical functions of the sample.5 Finally, TDpxq is obtained by concatenating v̄src and ζpvenvq. E.g., for x we have:
TDpxq “ concat ˜ 1
n
n ÿ i“1 EDsrcpxiq, ζ ` EDenvpxq ˘
¸
The comparison function σ : R6l Ñ R receives two latent vectors sa “ TDpaq, sx “ TDpxq representing the statistics of the samples a and x respectively. The vectors are concatenated and then passed through a Multi-Layered Perceptron which outputs a scalar reflecting their similarity. Namely: σpsa, sxq “ MLP pconcat psa, sxqq The full architecture of the authenticator is depicted in Fig. 7.
5ζ is implemented as the concatenation of the standard deviation and mean of the sample after passing each example through a Multi-Layered Perceptron.
Attacker Architecture: Our implementation of the attacker is inspired by the architecture suggested by Zakharov et al. (2019), which relies on an implicit assumption that an image could be modeled as a mapping of two latent vectors to image space. The first vector represents the source θ and is the same for any image of θ, the second vector represents the environment (e.g pose, lighting, expression) and is different for each image of the source.
The attacker model consists of the following components: An image encoder EGsrc : r´1, 1scˆhˆh Ñ Rl that maps an image to a latent vector representing the source θ, an image encoder EGenv : r´1, 1scˆhˆh Ñ Rl that maps an image to a latent vector representing the environment, a Multi-layered Perceptron MLPG : Rl Ñ Rl that maps Gaussian noise to the environment latent space, an environment decoder ϕenv : Rl Ñ Rcˆhˆh that maps a latent vector to an environment image which could represent aspects of the environment such as facial landmarks6, and finally, a generator φ : R2cˆhˆh ˆ Rl Ñ r´1, 1scˆhˆh that maps an environment image concatenated to the real image to a new image. The generator is based on the image to image model used by Zakharov et al. (2019) and Johnson et al. (2016), and uses the source latent vector as input for Adaptive instance normalization (Huang & Belongie, 2017).
The attacker generates a fake sample X P r´1, 1snˆcˆhˆh based on a leaked sample Y P r´1, 1smˆcˆhˆh in the following way: Each image Yj in the leaked sample is mapped using EGsrc and EGenv to latent vectors u src j , u env j P Rl. A latent environment vector, venvi , is constructed for each fake image Xi in the following way: First, n Gaussian noise vectors Z1, . . . , Zn iid„ N p0, Ilq
6In Zakharov et al. (2019), our so-called environment image is indeed a facial landmarks image which is used as input to the model. In our work, we allow the model to learn which environment image is useful.
are drawn, then each vector Zi is passed through MLPG to obtain Wi, and finally, venvi is obtained by matching the mean of the new latent environment vectors to the sample mean ūenv . Namely:
venvi “Wi ´ W̄ ` ūenv @i P rns
Each fake image Xi is then generated deterministically as follows: venvi is used as input to the decoder ϕenv which outputs an environment image. This image is concatenated along the channel dimension to a random image from the leaked sample Y , and then passed as input to the generator φ, which also receives usrc as input to its Adaptive instance norm layers. The output of the generator is the fake image Xi for all i P rns. The full architecture of the attacker is depicted in Fig. 8.
Optimization details: The model is trained in an authentication setup as in our theoretical setup, using alternating gradient descent with the regularization parameter as suggested by Mescheder et al. (2018). Each iteration begins when a source θ P Rd is drawn uniformly from the dataset. Samples A P r´1, 1skˆcˆhˆh, Y P r´1, 1smˆcˆhˆh, Xθ P r´1, 1snˆcˆhˆh are sampled uniformly from the images available to the source θ. The attacker, given the leaked sample Y , generates a fake sample XG “ GpY q, passes it to D, and suffers the loss ´ logpsigmoidpDpA,XGqqq. The authenticator, D, receives as input the source information sample A, outputs a prediction for each of the test samples Xθ, XG , and suffers the binary cross-entropy loss ´0.5 plog psigmoidpDpA,Xθqqq ` log psigmoidp1´DpA,XGqqqq. 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. (2018b)). The regularization parameter was set to 0.
The experiments on Voxceleb2 were trained for 250k iterations with batch size 64 using the Adam optimizer (Kingma & Ba, 2015) with learning rate 10´4 for both D and G and 10´6 for MLPG . The regularization parameter was set to 10 (as done by Karras et al. (2018b)) since we noticed that it stabilized and sped up the training, and in contrast to Omniglot and the Gaussian experiments did not seem to hurt the results.

Review summaries:
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.

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 

The 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.