2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The question which may be too abstract is ' can any combination of linear equations give an exact solution to an unknown function for which we only have inputs and outputs'. In its simplest sense, the analogy would be 'can an infinite sum approximate the value of a function at a point' and we know the answer to this is 'yes' (Taylor series). So the abstract answer to my question might be yes, but I am trying to understand a more quantative way that a DLN converges to an analytical function. $\endgroup$ – aquagremlin Feb 11 at 15:54
  • $\begingroup$ You may be interested in reading about neural cryptography. en.wikipedia.org/wiki/Neural_cryptography $\endgroup$ – Sycorax says Reinstate Monica Feb 11 at 16:03
  • $\begingroup$ There's been a paper out recently that claims that, assuming infinite floating point precision, Transformers are Turing-complete, even without requiring external memory access. Hadn't read it myself yet though, plus it's obviously it's super unrealistic in the real world. arxiv.org/abs/1901.03429 $\endgroup$ – jkm Feb 11 at 16:09
  • $\begingroup$ I'd change the question headline. "Analytic algorithm" doesn't correlate well with encryption or even a compression, it's not even a common term in comp science or math $\endgroup$ – Aksakal Feb 11 at 16:30
  • $\begingroup$ @SycoraxsaysReinstateMonica I am still trying to digest the maths in that wiki link . Really dense. I wish people would use the same language as Grant Sanderson (3blue1brown) $\endgroup$ – aquagremlin Feb 11 at 20:28
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ You may be interested in reading about neural cryptography. en.wikipedia.org/wiki/Neural_cryptography $\endgroup$ – Sycorax says Reinstate Monica Feb 11 at 16:02
  • $\begingroup$ @aksakal. I like your use of the word 'stiff' and I agree with it although I find your resounding 'NO' to be a bit harsh. I guess the property of DNNs that is amazing is their ability to recognize a cat for example despite the diversity of animals that resemble them. Certainly, if we were to calculate the equivalent measure of similarity between images using a 'distance measure of various parameters' we would find some hamsters similar to a particular cat and more diversity within the class of cats using the same measure. $\endgroup$ – aquagremlin Feb 11 at 19:48
  • $\begingroup$ @aquagremlin, in a cat recognizer ANN, small changes to the input picture, such as lighting and shadows, would yield the same "cat" tag. This is clearly not the case with encryption, where one bit change in the encrypted file will most likely make it un-decryptable. Therefore, with all the advances of AI/ML I'll still bet that RSA is safe in foreseeable future. Also, consider that humans are pretty good at image recognition, but we can't do anything with encrypted passwords. the complexity is beyond the power of our brains $\endgroup$ – Aksakal Feb 11 at 20:09
  • $\begingroup$ Off topic but there is the idea of homomorphic encryption schemes. Clearly if I can do an algorithm to encrypted text and get a decrypted result that matches the algorithm done to the freetext-then shouldnt an ANN be able to make the same 1 to 1 correspondence that the algorithm makes between the freetext and the encrypted result. $\endgroup$ – aquagremlin Feb 11 at 20:35
  • $\begingroup$ @aquagremlin Regarding your last comment: There is no 1-to-1 correspondence between plaintext and ciphertext for homomorphic encryption (at least not the schemes I know). If there was, one could encode all possible inputs (of a given length) and compare the ciphertext... $\endgroup$ – sebhofer Feb 13 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.