Re:Open Questions about Generative Adversarial Networks
by yorwba on Wednesday April 10, 2019 @05:33PM
(#19629017)
If an encryption scheme is easy to learn in the sense that if f is learnable, then so is g, then it is also easy to break.
Proof: You can easily train an RNN to return the n-th letter of its input and ignore everything else. Take that function to be f_n. Then g_n is the function that takes the encrypted input and returns the n-th letter, encrypted. If the encryption scheme is learnable in the above sense, then you can also train an RNN to perform that task. You can use multiple of those RNNs to extract an encryption of each individual letter in the input, which is equivalent to having the input encrypted with a substitution cipher. Substitution ciphers are so easy to break with frequency analysis that people have been doing it by hand for more than a thousand years.
Conversely, if you have a secure encryption scheme, then all statistical regularities in the input should be obfuscated so that they cannot be exploited by an RNN.
Proof: You can easily train an RNN to return the n-th letter of its input and ignore everything else. Take that function to be f_n. Then g_n is the function that takes the encrypted input and returns the n-th letter, encrypted. If the encryption scheme is learnable in the above sense, then you can also train an RNN to perform that task. You can use multiple of those RNNs to extract an encryption of each individual letter in the input, which is equivalent to having the input encrypted with a substitution cipher. Substitution ciphers are so easy to break with frequency analysis that people have been doing it by hand for more than a thousand years.
Conversely, if you have a secure encryption scheme, then all statistical regularities in the input should be obfuscated so that they cannot be exploited by an RNN.