can a deep learning algorithm approximate or resolve exactly to an analytic algorithm? Consider the lempel-ziv compression algorithm. Suppose I generate one billion pairs of uncompressed and compressed data. Consider this the training set. Could a deep learning algorithm be trained to give an uncompressed answer given a compressed sample as a test? Which deep learning model would be best for this? It might seem this problem is congruent to language translation where word pairs are equated. Beyond the simple case of comparing words in isolation, more advanced deep learning algorithms look at words in context but this has no analog in the example I gave above. Is there a way to measure the 'accuracy' of the deep learning algorithm' based on the size of the training set?
Beyond this trivial example (which I unfortunately do not have the resources to test) is a more useful problem. Can deep learning be applied to cryptanalysis in this way. Suppose I have a bunch of encrypted messages and their clear text equivalents but I do not have the algorithm for encryption/decryption. Can a deep learning algorithm be trained to decrypt anything encrypted by this algorithm from the freetext/encrypted pairs that I have? Is there a way to calculate 'error bars' for this algorithm as a function of the number of freetext/encrypted pairs?
 A: My answer is certainly NO for cryptography, and maybe YES sometimes for compression. Artificial neural nets (ANN) can't be trained to decrypt data. The reason is that the inverse problem is too stiff.
Encryption
In cryptography, by design, encryption transforms input X into output Y=f(X) using a very rough function f(). That's the whole idea of encryption so that  $\frac{f(X+\Delta X)-f(X)}{\Delta X}=\infty$. A small change in input X will create a huge difference in output Y. Vice versa, the inverse problem is as stiff: a small change in encrypted message Y would lead to a huge change in decrypted message X: $\frac{f^{-1}(Y+\Delta Y)-f^{-1}(Y)}{\Delta Y}=\infty$
Now, this type of function is the worst kind for the ANN, as it is incompatible with assumptions of universal approximation theorem which is a theoretical intuition behind the efficacy of deep learning networks in particular.
Example
Here's an example. I encrypt two similar words with RSA 1024bit key. Although the inputs are very similar, the outputs are very different.
X: test
Y: Eb9BVmTVaoqsMM4j3PFDGhOEETNm1bpy2Xab/IlNAIkUKnV5Oss+kPBEzcHNiGZEaVxtIxEMb8yZk8Jam1jFmv0b1dqj5bRQgaczQIeOfAV89rl3gDJed++HIO0WUyVljfe71TgQZTcimbAcJZoUvSqZEG//p42cHeV54ppt75M=
X: tess
Y: sWilkbwWJF99oAvCnEFle6jhwxbH9Voge6LEsGq0SD/dPKgvJCq2SkPyVOQOkN1BOXhrtL+TLhXhpzXOE4f6BTxgKCrUl1ixZ9tn1BCAj3VwoM1RJUMZvlI+bs7FmWSysr56h1S2SATOVEHfRGz6Ht1oRSDnek86F6tVTCYyTf0=
The Hamming distance between Xs is 1, and between Ys is 169.
Compression
The compression is a different case. It doesn't by design have to be a stiff problem, and in fact we'd rather prefer it to be non stiff at all. However, I'm afraid it ends up being quite stiff in case of best compression algorithms, I speculate. There is a research on using LZ algorithm to measure algorithmic (Kolmogorov) complexity of strings. There are also papers on measuring Kolmogorov complexity of ANNs. I conjecture that a large ANNs can have enough complexity to decode at least some compressed strings, maybe simple ones like LZ
Example
The same inputs compressed with gz compression produce quite similar outputs, i.e. transformation can be quite smooth. Hence, with compression ANNs should be able to deal with.
X: test
Y: H4sIAAAAAAAA/ytJLS4BAAx+f9gEAAAA
X: tess
Y: H4sIAAAAAAAA/ytJLS4GAK/rG0YEAAAA
The Hamming distance between Xs is 1, and between Ys is 7.
