Title: UNSUPERVISED CIPHER CRACKING USING DISCRETE GANS

Abstract: This work details CipherGAN, an architecture inspired by CycleGAN used for inferring the underlying cipher mapping given banks of unpaired ciphertext and plaintext. We demonstrate that CipherGAN is capable of cracking language data enciphered using shift and Vigenère ciphers to a high degree of fidelity and for vocabularies much larger than previously achieved. We present how CycleGAN can be made compatible with discrete data and train in a stable way. We then prove that the technique used in CipherGAN avoids the common problem of uninformative discrimination associated with GANs applied to discrete data.

1. INTRODUCTION:

Humans have been encoding messages for secrecy since before the ancient Greeks, and for the same amount of time, have been fascinated with trying to crack these codes using brute-force, frequency analysis, crib-dragging and even espionage. Simple ciphers have, in the past century, been rendered irrelevant in favor of the more secure encryption schemes enabled by modern computational resources. However, the question of cipher-cracking remains an interesting problem since it requires an intimate understanding of the structure in a language. Nearly all automated cipher cracking techniques have had to rely on a human-in-the-loop; grounding the automated techniques in a human's preexisting knowledge of language to clean up the errors made by simple algorithms such as frequency analysis. Across a number of domains, the use of hand-crafted features has often been replaced by automatic feature extraction directly from data using end-to-end learning frameworks (Goodfellow et al., 2016) . The question to be addressed is as follows:

Can a neural network be trained to deduce withheld ciphers from unaligned text, without the supplementation of preexisting human knowledge?

The implications for such a general framework would be far-reaching in the field of unsupervised translation, where each language can be treated as an enciphering of the other. The decoding of the Copiale cipher (Knight et al., 2011 ) stands as an excellent example of the potential for machine learning techniques to decode enciphered texts by treating the problem as language translation. The CycleGAN (Zhu et al., 2017) architecture is extremely general and we demonstrate our adaptation, CipherGAN, is capable of cracking ciphers to an extremely high degree of accuracy. CipherGAN requires little or no modification to be applied to plaintext and ciphertext banks generated by the user's cipher of choice.

In addition to presenting a GAN that can crack ciphers, we contribute the following techniques:

• We show how to stabilize CycleGAN training: our CipherGAN achieves good performance in all training runs, compared to approximately 50% of runs for the original CycleGAN.

• We provide a theoretical description and analysis of the uninformative discrimination problem that impacts GANs applied to discrete data.

• We introduce a solution to the above problem by operating in the embedding space and show that it works in practice.

1.1. SHIFT AND VIGEN ÈRE CIPHERS:

The shift and Vigenère ciphers are well known historical substitution ciphers. The earliest known record of a substitution cipher is believed to have dated back to 58 BCE, when Julius Caesar replaced each letter in a message with the letter that was three places further down the alphabet (Singh, 2000) .

Plain alphabet a b c d e f g h i j k l m n o p q r s t u v w x y z Using Figure 1 , the message "attackatdawn" can be encrypted to "DWWDFNDWGDZQ". This message can be easily deciphered by the intended recipient (who is aware of the particular shift number used) but looks meaningless to a third party. The shift cipher ensured secure communication between sender and receiver for centuries, until the ninth century polymath Al-Kindi introduced the concept of frequency analysis (Singh, 2000) . He suggested that it would be possible to crack a cipher simply by analyzing the individual characters' frequencies. For instance, in English the most frequently occurring letters are 'e' (12.7%), 't' (9.1%) and 'a' (8.2%); whereas 'q', 'x' and 'z' each have frequency of less than 1%. Moreover, the code-breaker can also focus on bigrams of repeated letters; 'ss', 'ee', and 'oo' are the most common in English. This structure in language provides an exploit of efficiency to the code-breaker.

Shifted alphabet D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

Polyalphabetic substitution ciphers, including the Vigenère cipher, were introduced to inhibit the use of n-gram frequency analysis in determining the cipher mapping. Instead, the encrypter further scrambles the message by using a separate shift cipher for each element of a key that is tiled to match the length of the plaintext. Increasing the key length greatly increases the number of possible combinations and thus prevents against basic frequency analysis. In the mid nineteenth century, Charles Babbage recognized that the length of the used key could be determined by counting the repetitions and spacing of sequences of letters in the cipher (Singh, 2000) . Using the determined length, we can then apply frequency analysis on the index of the cipher base. This method makes it possible to break the Vigenère cipher, but is very time consuming and requires strong knowledge of the language itself.

There is a rich literature of automated shift-cipher cracking techniques (Ramesh et al., 1993; Forsyth & Safavi-Naini, 1993; Hasinoff, 2003; Knight et al., 2006; Verma et al., 2007; Raju et al., 2010; Knight et al., 2011) many of which achieve excellent results which is what one would expect from hand-crafted algorithms targeting specific ciphers and vocabularies. Work on automated cracking of polyalphabetic ciphers (Carroll & Martin, 1986; Toemeh & Arumugam, 2008; Omran et al., 2011) has seen similar success on small vocabularies. It is a difficult matter to compare the results of previous work with our own as their focus ranges from inferring cipher keys (Carroll & Martin, 1986; Ramesh et al., 1993; Omran et al., 2011) , to inferring the mappings given limited quantities of ciphertext (determining unicity distance) (Carroll & Martin, 1986; Ramesh et al., 1993; Hasinoff, 2003; Verma et al., 2007) , to analyzing the unicity distance required to solve small percentages of the cipher mappings (i.e. 20% in Carroll & Martin (1986) ).

In comparison to these past works, we afford ourselves the advantage of an unconstrained corpus of ciphertext, however, we prescribe ourselves the following constraints: our model is not provided any prior knowledge of vocabulary element frequencies; and, no information about the cipher key is Instead, GANs balance the optimization of a generator network which attempts to produce convincing samples from the data distribution, and a discriminator which is trained to distinguish between samples from the true data distribution and the generator's synthetic samples. GANs have been shown to produce compelling results in the domain of image generation, but comparatively weak performance in domains using discrete data (discussed in Section 2).

The original GAN discriminator objective as introduced in Goodfellow et al. ( 2014) is:

EQUATION

Where F is the generator network and D is the discriminator network. This loss is vulnerable to the problem of 'mode collapse' where the generative distribution collapses to produce a generating distribution with low diversity. In order to more broadly distribute the mass, the Wasserstein GAN (WGAN) objective (Arjovsky et al., 2017) considers the set of K-Lipschitz discriminator functions D : X → R and minimizes the earth movers (1st Wasserstein) distance. The Lipschitz condition is enforced by clipping discriminators weights to fall within a predefined range.

EQUATION

An improved WGAN objective, introduced by Gulrajani et al. (2017) , enforced the Lipschitz condition using a Jacobian regularization term instead of the originally proposed weight-clipping solution. This resulted in more stable training, avoiding capacity under-use and exploding gradients, and improved network performance over weight-clipping.

EQUATION

Here X are samples taken along a line between the true data distribution X and the generator's data distribution X g = {F (z)|z ∼ Z}.

1.3. CYCLEGAN:

CycleGAN (Zhu et al., 2017 ) is a generative adversarial network designed to learn a mapping between two data distributions without supervision. Three separate works (Zhu et al., 2017; Yi et al., 2017; Liu et al., 2017) share many of the core features we describe below, however, for simplicity we will refer to CycleGAN as the basis for our work as it is the most similar to our model. It acts on distributions X and Y by using two mapping generators: F : X → Y and G : Y → X ; and two discriminators:

D X : X → [0, 1] and D Y : Y → [0, 1].

CycleGAN optimizes the standard GAN loss L GAN :

EQUATION

While also considering a reconstruction loss, or 'cycle' loss L cyc :

EQUATION

Taken together the losses are balanced using a hyperparameter λ: This leads to the training objectives:

L(F, G, D X , D Y , X , Y) = L GAN (F, D Y , X , Y) + L GAN (G, D X , Y, X ) + λ • L cyc (F, G, X , Y)

F * = arg min F L cyc (F, G, X , Y) + L GAN (F, D Y , X , Y) G * = arg min G L cyc (F, G, X , Y) + L GAN (G, D X , Y, X ) D * X = arg max D X L GAN (G, D X , Y, X ) D * Y = arg max D Y L GAN (F, D Y , X , Y)

CycleGAN uses L cyc to avoid mode collapse by preserving reconstruction of mapping inputs from outputs. It has demonstrated excellent results in unpaired image translation between two visually similar categories. Our architecture is the first example of this unsupervised learning framework being successfully applied to discrete data such as language.

2. DISCRETE GANS:

Applying GANs to discrete data generation is still an open research problem that has seen great interest and development. The primary difficulty with training discrete data generators in a GAN setting is the lack of a gradient through a discrete node in the computation graph. The alternatives to producing discrete outputs -for instance, generators producing a categorical distribution over discrete elements -are prone to uninformative discrimination (described below), in that, the discriminator may use an optimal discrimination criterion that is unrelated to the correctness of the re-discretized generated data. In our example of a continuous distribution over discrete elements, the produced samples all lie within the standard simplex ∆ k with dimension k equal to the number of elements in the distribution. In this case, samples from the true data distribution always lie on a vertex v i of the simplex, while any sub-optimal generator will produce samples within the simplex's interior ∆ k \{v 1 , ..., v k }. In this example, a discriminator which performs uninformative discrimination might evaluate a sample's membership in the vertices of the simplex as an optimal discrimination criterion, which is entirely uninformative of the correctness of re-discretized samples from the generator.

A number of solutions to training generators with discrete outputs have been proposed: SeqGAN (Yu et al., 2017) (Arjovsky et al., 2017) were suggested as a remedy to the uninformative discrimination problem by ensuring that the discriminator's rate of change with respect to its input is bound by some constant.

Our work utilizes both the Wasserstein GAN (Gulrajani et al., 2017; Arjovsky et al., 2017) and relaxation of discrete random variables (such as Concrete/Gumbel-softmax). It has been noted multiple times in implementations of CycleGAN as well as in the original paper itself that the architecture was sensitive to initialization and requires repeat attempts in order to converge to a satisfactory mapping (Bansal & Rathore, 2017; Sari, 2017) . Our architecture suffered the same instability before the WGAN Jacobian norm regularization term was added to the discriminator's loss. In addition, we found that having the discriminator operate over embedding space instead of directly over softmax vectors produced by our generator has improved performance.

Our hypothesis, which is justified by Proposition 1 below, is that the embedding vectors may act as continuous relaxations of discrete random variables as small, noisy updates are applied throughout training; Proposition 1 asserts that by replacing discrete random variables with continuous ones, our discriminator is prevented from arbitrarily approximating a Dirac delta distribution. Figure 2 shows simple discriminators trained on the toy task of identify a single vertex of a simplex as true data; it is clear that a lack of regularization leads to the discriminator collapsing to the vertex of the simplex, leaving approximately zero gradient everywhere; while the Jacobian regularization of Wasserstein GANs leads to the space covered by lines leading from the true data vertex to the generated data having a lower rate of change (note that the gradient is still close to zero in the remaining area of the simplex); and finally, replacing the discrete random variables of the true data with continuous samples about the vertex results in a much more gradual transition, which is desirable since it provides a stronger gradient signal from which to learn.

Unique to CycleGAN is the auxiliary cycle loss described in Section 1.3. The effect of this additional objective is the generated samples regularly being forced away from the discriminator's minimum in favor of a mapping that better-satisfies reconstruction. For instance, it may be the case that the discriminator favors a particular cipher mapping that is not bijective; in this case, the model will receive a strong signal from the cycle loss away from the discriminator's minimum. In these cases where the model moves against the gradient it receives from the discriminator it may be the case that this region has near zero curvature (as is visually discernible from Figure 2 ); this is because the WGAN curvature regularization (see Equation 3) has not been applied in this region.

'Curvature' here refers to the curvature of the discriminator's output with respect to its input; this curvature determines the strength of the training signal received by the generator. Low curvature means little information for the generator to improve itself with. This motivates the benefits of having strong curvature globally, as opposed to linearly between the generators samples and the true data. Kodali et al. (2017) proposes regularizing in all directions about the generated samples, which would likely remedy the vanishing gradient in our case as well; for our experiments, the relaxed sampling technique proved effective. It should also be noted that Luc et al. (2016) propose something similar to relaxed sampling whereby they replace the ground-truth discrete tokens with a distribution over the vocabulary that distributes some of the mass across the remaining incorrect tokens.

Let us now introduce the definitions needed for the formal presentation of Proposition 1.

Definitions.

• (Continuous relaxation of a discrete set). A continuous relaxation of a discrete set X is a proper, path-connected metric space X satisfying X ⊂ X .

• (Rediscretization function). A rediscretization function is an injective function:

R : X → X from a continuous relaxation X of discrete space X satisfying ∀x ∈ X , ∃ > 0 s.t. R ≡ x on B [x].

Note that R defines an equivalence relation in X .

• (Uninformative Discrimination:

). A discriminator D X is said to perform uninformative discrimination under rediscretization function R if: ∃x ∈ X , x ∈ X s.t. (R(x) = x) ∧ (D X (x) ≈ D X (x)).

• (Continuous relaxation of a function). A continuous relaxation of a function over discrete sets F :

X → Y is another function F : X → Y (where X , Y are continuous relaxations of X , Y) such that F is continuous and F (x) = F (x), ∀x ∈ X .

The following proposition (proved in the Appendix) forms the theoretical basis of the technique.

Proposition 1 (Reliable Fooling Via Relaxation). Given:

• discrete spaces X , Y and continuous relaxations X , Y • generators F : X → Y, G : Y → X bijections satisfying F = G -1

• discrete discriminators D X , D Y both optimal for fixed F, G

• rediscretization functions R X , R Y Suppose: F is approximately volume preserving in a small region about each x ∈ X . Consequently the same is true for G about each y ∈ Y.

If: during training, we replace discrete random variables from X which lie in the continuous metric space X with samples from regions about them. Then: the optimal relaxed discriminators D X and D Y have a non-empty region about each x ∈ X and y ∈ Y where they are expected to assign values close to D X (x) and D Y (y).

Figure 3 compares a model trained with embedding vectors versus one with only the softmax outputs. It becomes clear on a harder task, such as Vigenère, that the embeddings vastly outperforms softmax in terms of speed of convergence and final accuracy; however we found that the simpler task of a shift cipher showed little difference between embeddings and softmax, suggesting an increase in task complexity increases the benefits provided by the stronger gradient signal of embeddings.

3. METHOD:

3.1 CIPHERGAN GANs applied to text data have yet to produce truly convincing results (Kawthekar et al.) . Previous attempts at discrete sequence generation with GANs have generally utilized a generator outputting a probability distribution over the token space (Gulrajani et al., 2017; Yu et al., 2017; Hjelm et al., 2017) . This leads to the discriminator receiving a sequence of discrete random variables from the data distribution, and a sequence of continuous random variables from the generator distribution; making the task of discrimination trivial and uninformative of the underlying data distribution. In order to avoid such a scenario, we perform all discrimination within the embedding space by allowing the generator's output distribution to define a convex combination of corresponding embeddings. This leads to the following losses:

L GAN (F, D Y , X , Y) = E y∼Y [log D Y (y • W Emb )] + E x∼X [log(1 -D Y (F (x • W Emb ) • W Emb ))] L cyc (F, G, X , Y) = E x∼X [ G(F (x • W Emb ) • W Emb ) -x 1 ] + E y∼Y [ F (G(y • W Emb ) • W Emb ) -y 1 ]

We perform an inner product between the embeddings W Emb and the one-hot vectors in x as well as between the embeddings and the softmax vectors produced by generators F and G. The former is equivalent to a lookup operation over the table of embedding vectors, while the latter is a convex combination between all vectors in the vocabulary. The embeddings W Emb are trained at each step to minimize L cyc and maximize L GAN , meaning the embeddings are easily mapped from and are easy to discriminate. As was discussed in Section 2, training with the above loss functions was unstable, with approximately three of every four experiments failing to produce compelling results. This is a problem we observed with the original CycleGAN horse-zebra experiment, and one that has been noted by multiple re-implementations online (Bansal & Rathore, 2017; Sari, 2017) . We were able to significantly increase the stability by training the discriminator loss along with the Lipschitz conditioning term from the improved Wasserstein GAN (Gulrajani et al., 2017) (see Equation 3and Fedus et al. ( 2017)), resulting in the following loss (DualGAN (Yi et al., 2017) opted to use weight-clipping to enforce the Lipschitz condition):

L GAN (F, D Y , X , Y) = E y∼Y [D Y (y • W Emb )] -E x∼X [D Y (F (x • W Emb ) • W Emb )] + α • E ŷ∼ Ŷ [( ∇ ŷ D Y (ŷ) 2 -1) 2 ]

As a consequence of Proposition 1, discriminators trained on non-stationary embeddings will be unable to approximate Dirac delta distributions to arbitrary accuracy; implying there are dedicated 'safe-zones' about members of X where the generator can reliably fool the discriminator and uninformative discrimination is prevented.

In our experiments, we jointly train the embedding vectors as parameters of the model. The gradient updates applied to these vectors introduces noise between training iterations; we observed that embedding vectors tend to remain in a bounded region after the initial steps of training. We found that simply replacing the data with embedding vectors had a similar effect to performing the random sampling described in Proposition 1 (see Figure 3 ).

4. EXPERIMENTS 4.1 DATA:

Our experiments use plaintext natural language samples from the Brown English text dataset (Francis & Kucera, 1979) . We generate 2 * batch size plaintext samples, the first half are fed as the CycleGAN's X distribution and the second half is passed through the cipher of choice and fed as the Y distribution.

For our natural language plaintext data we used the Brown English-language corpus which consists of over one million words in 57340 sentences. We experiment with both word-level "Brown-W" and character-level "Brown-C" vocabularies. For word-level vocabularies, we control the size of the vocabulary by taking the top k most frequent words and introducing an 'unknown' token which we use to replace all words that are not within the taken vocabulary. We demonstrate our method's ability to scale to large vocabularies using the word-level vocabularies; more modern enciphering techniques rely on large substitution-boxes (S-boxes) with many (often hundreds of) elements.

4.2. TRAINING:

As in Zhu et al. (2017) we replace the log-likelihood loss with a squared difference loss which was originally introduced by Mao et al. (2016) . The original motivation for this replacement was improved stability in training and avoidance of the vanishing gradients problem. In this work we found the effect on training stability substantial.

L GAN (F, D Y , X , Y) = E y∼Y [(D Y (y • W Emb )) 2 ] + E x∼X [(1 -D Y (F (x • W Emb ) • W Emb )) 2 ] + α • E ŷ∼ Ŷ [(1 -∇ ŷ D Y (ŷ) 2 ) 2 ]

Hence, our total loss is:

L Total (F, G, D X , D Y , X , Y) =L cyc (F, G, X , Y) + L GAN (F, D Y , X , Y) + L GAN (G, D X , X , Y)

We adapted the convolutional architecture for the generator and discriminator directly from Zhu et al. (2017) . We simply replace all two dimensional convolutions with the one dimension variant and reduce the filter sizes in our generators to 1 (pointwise convolutions). Convolutional neural networks have recently been shown to be highly effective on language tasks and can speed up training significantly (Zhang & LeCun, 2015; Kalchbrenner et al., 2016; Yu et al., 2017) . Both our generators and discriminators receive a sequence of vectors in embedding space; our generators produce a softmax distribution over the vocabulary, while our discriminator produces a scalar output. For all our experiments we use a cycle loss with regularization coefficient λ = 1. In order to be compatible with the WGAN we replace batch normalization (Ioffe & Szegedy, 2015) with layer normalization (Ba et al., 2016) . We train using the Adam optmizer (Kingma & Ba, 2014) with batch size 64 and learning rate 2e -4, β 1 = 0 and β 2 = 0.9. Our learning rate is exponentially warmed up to 2e -4 over 2500 steps, and held constant thereafter. We use learned embedding vectors with 256 Table 2 : Average proportion of characters correctly mapped in a given sequence. The "Freq. Analysis" column is simple frequency analysis applied to the same corpus our model observes. For Vigenère we also show the score if the key were known (note: the key is left unknown to our model).

dimensions. The WGAN Lipschitz conditioning parameter was set to α = 10 as was prescribed in Gulrajani et al. (2017) .

For the Vigenère cipher, positional information is critical to the network being able to perform the mapping. In order to facilitate this we experimented with adding the timing signal described in Vaswani et al. (2017) ("Transformer Timing" in Figure 3 ) and found that performance increased relative to no explicit timing signal; we found that the best option was concatenating a learned positional embedding vector specific to each position onto the sequence ("Concat Timing" in Figure 3 ), this dramatically improved performance, however this means that the architecture can not generalize to sequences longer than those in the training set. A potential solution to the issue of generalizing to longer sequences would be making a 'soft' choice at each position for which positional embedding vector to concatenate using a softmax distribution over a set of embedding vectors larger than the expected key length, however, we leave this to future work.

4.3. DISCUSSION:

Table 2 shows that CipherGAN was able to solve shift ciphers to near flawless accuracy, with all three vocabulary sizes being easily decoded by the model. CipherGAN performs extremely well on Vigenère, achieving excellent results on the character-level cipher and strong results on the challenging word-level cipher with a vocabulary size of 200. The vocabulary size of 58 for our character level, containing punctuation and special characters, is more than double what has been previously explored. In comparison to the original CycleGAN architecture, we found CipherGAN to be extremely consistent in training and notably insensitive to the random initialization of weights; we attribute this stability to the Jacobian norm regularization term.

For both ciphers, the first mappings to be correctly determined were those of the most frequently occurring vocabulary elements, suggesting that the network does indeed perform some form of frequency analysis to distinguish outlier frequencies in the two banks of text. Another interesting observation is that of the mistakes made by the network: the network would frequently confuse punctuation marks with one another, perhaps suggesting that these vocabulary elements' skip-gram signatures were similar enough to lead to the repeated confusion observed across many training runs.

5. CONCLUSION:

CipherGAN is a compelling demonstration of the potential generative adversarial networks hold to act on discrete data to solve difficult tasks that rely on an extremely sensitive and nuanced discrimination criterion. Our work serves to redouble the promise of the CycleGAN architecture for unsupervised alignment tasks for multiple classes of data. CipherGAN presents an algorithm that is both stable and consistent in training, improving upon past implementations of the CycleGAN architecture. Our work theoretically motivates -and empirically confirms -the use of continuous relaxations of discrete variables, not only to facilitate the flow of gradients through discrete nodes, but also to prevent the oft-observed phenomena of uninformative discrimination. CipherGAN is highly general in its structure and can be directly applied to a variety of unsupervised text alignment tasks, without excess burden of adaptation. On the one hand, CipherGAN is an early step towards the goal of unsupervised translation between languages and has shown excellent performance on the simplified task of cipher map inference. On the other hand, the methods we introduce can be used more broadly in the field of text generation with adversarial networks.

B PROOF OF PROPOSITION 1:

Proposition 1 (Reliable Fooling Via Relaxation). Given:

• discrete spaces X , Y and continuous relaxations X , Y • generators F : X → Y, G : Y → X bijections satisfying F = G -1

• discrete discriminators D X , D Y both optimal for fixed F, G

• rediscretization functions R X , R Y Suppose: F is approximately volume preserving in a small region about each x ∈ X . Consequently the same is true for G about each y ∈ Y.

If: during training, we replace discrete random variables from X which lie in the continuous metric space X with samples from regions about them.

Then: the optimal relaxed discriminators D X and D Y have a non-empty region about each x ∈ X and y ∈ Y where they are expected to assign values close to D X (x) and D Y (y).

Proof. We'll prove one side of the CipherGAN as the proof for both sides are similar.

Given bijective function between continuous relaxations of X and Y:

F : (X , d X ) → (Y, d Y ),

where X and Y contain finite sequences (length n) of vectors laying on the vertices of the simplex ∆ k , and are supports of data distributions p X , p Y respectively.

Let:

• X = Y = ∆ k × • • • × ∆ k n

with k equal to the number of elements in our vocabulary.

• the rediscretization function R X : X → X : R X (x) = arg min x∈X d X (x, x); similarly for R Y . Now, for each x ∈ X consider the infinite set S x with cardinality of the continuum constructed according to:

x ∈ S x ⇐⇒ x ∈ X , s.t. R X (x) = x and R Y (F (x)) = F (x) Equivalently, S x = R -1 X (x) ∩ F -1 (R -1 Y (F (x)

)) Note. S x is never of cardinality less than the continuum since the following is implied by the definitions of R X , S x and the fact that F is continuous:

x ∈ X =⇒ x ∈ S x ∧ ∃ closed ball B [x] with radius 0 < < min z∈X R Y (F (z)) =R Y (F (x)) d X (x, z)

So, for each element x ∈ X there exists a closed set of points in X which are rediscretized, under R X , to x. Since S x is a Borel Set we can sample uniformly from it. Therefore, during training suppose we replace each element of x ∈ X with a sample x ∼ S x :

We begin with the discrete objective:

x∈X p X (x) log(D X (x)) + p F (x) log(1 -D X (x))

As was noted in Goodfellow et al. (2014) , this objective is optimized in D X : X → [0, 1] when:

D X = p X p X + p G

which is undesirable as p X is a sum of Dirac delta distributions p X (x) = xi∈X δ xi (x) and lacks a non-zero gradient to train the generator function with. Instead, let us consider a continuous relaxation D X : X → [0, 1] of the discriminator D X and observe where it optimizes.

Published as a conference paper at ICLR 2018 Suppose ∀x ∈ X , ∃ x ≥ 0, ∀x ∈ S x

EQUATION

That is, suppose F is approximately volume preserving within a small region about each x ∈ X .

Lemma 1. ∀y ∈ Y, G(S y ) = S G(y)

Proof of Lemma 1. For all y ∈ Y with G(y) = x ⇔ y = F (x):

G(S y ) = G[R -1 Y (y) ∩ G -1 (R -1 X (G(y)))] = G(R -1 Y (y)) ∩ G(G -1 (R -1 X (G(y)))) = G(R -1 Y (y)) ∩ R -1 X (G(y)) = F -1 (R -1 Y (F (x))) ∩ R -1 X (x) = S x = S G(y)

Corollary 1. 

x∼S G(y) 1 -x |S y | dx ≤ x∼S G(y) 1 |S G(y) | dx ≤ x∼S G(y) 1 + x |S y | dx =⇒ 1 -x |S y | |S G(y) | ≤ 1 ≤ 1 + x |S y | |S G(y) | =⇒ (1 -x )|S G(y) | ≤ |S y | ≤ (1 + x )|S G(y) | =⇒ 1 (1 -x )|S G(y) | ≥ 1 |S y | ≥ 1 (1 + x )|S G(y) |

Corollary 1 leads to the following: x∼S G(F (x))

1 -x (1 + x )|S G(F (x)) | log(1 -D X (x))dx = x∈X x∼Sx 1 |S x | p X (x) log(D X (x)) + 1 -x 1 + x p G (x) log(1 -D X (x)) dx

Which is maximal at:

D X (x ∼ S x ) = p X p X + 1-x 1+ x p G x ≈ D X =⇒ E x∼Sx [D X (x)] x ≈ D X

And similarly, we find Equation 7 is upper-bounded by: Which is maximal in D X at:

D X (x ∼ S x ) = p X p X + 1+ x 1-x p G x ≈ D X =⇒ E x∼Sx [D X (x)] x ≈ D X

Hence, asymptotically as F becomes approximately volume-preserving about each discrete x ∈ X the bounds maximize to the same loss value in the same class of functions E x∼Sx [D X (x)] = D X , application of the squeeze theorem concludes the proof.

:



Figures and Tables:

Figure 1: An example of a right-shift-3 cipher.

Figure 2: Discriminators trained on the toy example of recognizing the bottom-right corner of a simplex as true data. From left to right the discriminators were regularized using: nothing; WGAN Jacobian norm regularization; and, the relaxed sampling technique.

Figure 3: Left: Comparison of different timing techniques for Brown-C Vigenère. Right: Comparison of embedding vs. raw softmax on Brown-W with vocab size of 200.

x )|S G(y) | Proof of Corollary 2. By Equation 6 and Corollary 1:

x∈X [E x∈Sx [log(D X (x))]] + E y∈Y [E ȳ∈Sy [log(1 -D X (G(ȳ)))]] = x∈X p X (x) x∼Sx 1 |S x | log(D X (x))dx + y∈Y p Y (y) ȳ∼Sy 1 |S y | log(1 -D X (G(ȳ)))dȳ = x∈X p X (x) x∼Sx 1 |S x | log(D X (x))dx + y∈Y p Y (y) x∼G(Sy) |∇ xF (x)| |S y | log(1 -D X (x))dx(7)Using Lemma 1 and Corollary 2, we obtain the following lower-bound of Equation 7:

x )|S G(F (x)) | log(1 -D X (x))dx = x∈X x∼Sx 1 |S x | p X (x) log(D X (x)) + 1 + x 1x p G (x) log(1 -D X (x)) dx

uses the REINFORCE gradient estimate to train the generator; Boundary-seeking GANs(Hjelm et al., 2017) and maximum-likelihood augmented GANs(Che et al., 2017)  proposed a gradient approximation with low bias and variance that resembles the REINFORCE (Williams, 1992) estimator. Gumbel-softmax GANs (Kusner & Hernández-Lobato, 2016) replace discrete variables in the simplex with continuous relaxations called Concrete(Maddison et al., 2016) or Gumbel-softmax(Jang et al., 2016) variables; WGANs

Table content: <table/>

Previous results on automated shift cipher cracking with limited ciphertext length.

Table content: <table><tr><td>Work</td><td colspan="2">Ciphertext Length Accuracy</td></tr><tr><td>Hasinoff (2003)</td><td>500</td><td>∼ 97%</td></tr><tr><td colspan="2">Forsyth &amp; Safavi-Naini (1993) 5000</td><td>∼ 100%</td></tr><tr><td>Ramesh et al. (1993)</td><td>160</td><td>∼ 78.5%</td></tr><tr><td>Verma et al. (2007)</td><td>1000</td><td>∼ 87%</td></tr></table>

Peer review (iclr2018):
 The paper proposed to replace the 2-dim convolutions in CycleGAN by one dimension variant and reduce the filter sizes to 1, while leave the generator convex embedding and using L2 loss function. The proposed simple change help with the dealing of discrete GAN. The benefit of increased stability by adding Jacobian norm regularization term to the discriminator*s loss is nice. The paper is well written. A few minor ones to improve: * The original GAN was proposed/stated as min_max, while in Equation 1 didn*t defined F and was not clear about min_{F}. Similar for Equations 2 and 3. * Define abbreviation when first appear, e.g. WGAN (Wasserstein ...). * Clarify x- and y- axis label in Figure 3.