"no one knows how it works" - That caught my attention, having seen computer evolved ASTs. Probably no one knows because no one has put effort to reverse engineer the internals - most of which would be unnecessary complexity that is very likely with neural nets.
Many years back, I had once experimented with PyEvolve to develop a custom trading strategy which was kind-of code with a custom instruction set. The output of a strategy was a string (program AST) that was uglier than most obfuscation outputs with many unnecessary statements. For example "a=1;b=2;c=a+b;d=c/3;if(d==1).." - expand that to many more variables. The program evolved strategies that made small profit and therefore the output was worth analysing. But decompiling that output used to take me hours - and few of those were tweaks of well documented strategies. Others I never understood because it was too much effort for a relatively small profit (and other trading parameters).
Could you not automate that too? Have another stage of evolution where you just randomly delete statements from the 'code' and the fitness function is that the performance doesn't get worse.
This should eventually reduce the 'code' to it's minimal state, removing any unnecessary parts.
I get the sense that many commenters misinterpreted the point of this study. This isn't about show-boating some newfound, great cryptography method, this is about teaching computers to re-write their own code.
If you can write software that improved itself better over time, our species as a whole would advance at incredible speeds. Think about all the possibilities that could evolve from self-maintained programs. Obviously the thought is a bit scary, but it's also incredibly exciting!
Please don't editorialize. Finding the best parameters that optimize an objective function can hardly be called "re-writing its own code." Granted, the article is just as guilty. (Edit: The article also doesn't mention self-modifying code so I'm not sure where you're getting that idea from.)
The technique is an off-the-shelf GAN that attempts to learn a transformation (not arbitrary code!) from input to encrypted output. The learned model is not Turing complete, and most importantly, is _not_ self-modifying. The optimization procedure is what modifies the network, not the network itself.
GANs have been used before to create realistic pictures. They're not new here -- the application is. It's a cool application, sure, but doesn't involve self-modifying code.
I don't think it's entirely inaccurate to call neural networks "rewriting their own code". For a long time people experimented with algorithms that could actually rewrite human programming languages, like genetic programming. And it's mostly a failure, because most mutations to most programs just break them.
Neural networks fix this problem by being sort of 'continuous programming language' where any small change to the net results in a small change to the output. And because of that we have algorithms that can find good changes to make much easier than with code. They are theoretically turing complete under some circumstances. But even when they aren't completely recurrent as in this case, they can still learn very sophisticated functions. Theoretically a neural net can learn anything a fixed number of logic gates can learn, which is still pretty powerful.
I don't think parent comment meant by computers that can "re-write their own code" was that the programs are self modifying. But the computer itself is self modifying, as one program can change another on that computer, so the computer has modified itself.
If you read the paper, it is not rewriting its own code. It is optimizing for some objective function, which has been done before. For example, the MetroHash family of hash functions were created using a very similar technique back in 2012; the code didn't just learn to create hash functions, the ones it produced were objectively superior to the state-of-the-art at the time. I've applied the same approach to other computer algorithm optimization problems as well.
This technique generalizes poorly, it really only works for algorithms with specific, somewhat narrow characteristics. If you understand the process as a weak form of algorithmic induction then the practical limitations become more apparent. Most code cannot be usefully constructed this way.
> Think about all the possibilities that could evolve from self-maintained programs.
What are some that you are considering? Most maintenance I do is in the form of bug repair and change requests. Most of those wouldn't be fixable (or even identifiable) by machines. It's not errors like "value x should be y" (almost all of those get shaken out in alpha.) It's requests like "When I get to step H in our workflow, I shouldn't have to fill out form 2 to get information about the customer I'm helping."
I mean, for technical things like encryption, I could see a lot of growth potential. Other algorithms where there is a good metric for "better" would also be candidates (compression also springs to mind.) But on the whole, most applications have a lot of human interfacing and critical thinking that needs to happen. AI is going to take a long time to get to the point where it can fix those kinds of problems.
This seems pretty click-baity to me. Especially "no one knows how it works."
Alice generates ciphertext based on plain text and key. Bob generates plaintext based on ciphertext and key. Eve generates plaintext based on only ciphertext. Train the three networks across a variety of plaintetxts,
No doubt it's cool, but I would be very surprised if it offered any insight into, or represented an advance for strong cryptography.
The paper [1] is by Abadi [2], which is a pretty big name in crypto. So I can assume it's something with value, wether the press can or can't convey that is another story.
Pretty big name is a bit of an overstatement. A pretty big name in cryptography would be someone like Goldwasser/Goldreich/Micali/Bellare/Rivest/Bernstein/... and probably about 200 more before we get to Abadi.
I might be reading your comment incorrectly, but it sounds like you're interpreting that phrase to mean that no one knows how training the neural network works.
I think, instead, it's in reference to the resulting function not having been analyzed. From the article:
The researchers didn't perform an exhaustive analysis of the encryption methods devised by Alice and Bob...
>I think, instead, it's in reference to the resulting function not having been analyzed.
I think it may be that it is "unanalyzable" if you will. Thousands of matrices multiplied together seems as if it would be hard to come to an actual understanding of...
There's nothing clickbait about it. No one knows how the cryptographic algorithm it invented works. It's very, very difficult, perhaps impossible, to reverse engineer neural networks. They also don't claim it's an advance for strong cryptography, it's just interesting experiment with NNs.
I completely agree. Also, they may not know but because they haven't made a detailed analysis, it's not like they couldn't know even if they wanted to. So yeah, click-bait.
At this point in time, when I hear 'no one knows/understands the process' or some variation relating to neural networks or deep learning, I know their maturity on the subject.
This is most probably a rather lousy hack put together by Alice and Bob, but it maps out a very interesting future were we one day maybe can stop worrying about how our algorithms work and make that the job of the computer.
It also is totally terrifying to live in a world were computers can hide their messages from their own creators.
It doesn't. As an AI developer you have access to the AI code and memory.. How could you not replay the encryption process used by the AI since you know the state of what it "knows" constantly? Both have a encryption and decryption process that you can reproduce.
You might be able to follow the steps that the computer takes but you won't necessarily know why. Why is that the magic constant is chose, what is the purpose of those branches, etc. And likely, if it's necessary, the AI can continue to evolve the algorithms faster than you can figure out what it's doing.
Touching off of this: We have access to the learned encryption function, f : plaintext -> ciphertext.
Most importantly, f is differentiable. It has to be, since it was trained with gradient descent.
So if you want to decipher a ciphertext Y, then use backpropagation to find the X that minimizes distance(f(X), Y). You already know dF/dX (f is differentiable after all), so run this through your magic optimization solver and you'll get an X very close to the result.
Researchers use this "backproagation in input space" idea to recover the training set of a trained neural network, or to debug their model by finding inputs that activate certain neurons, for example. (This is the basic idea behind Deepdream from last year)
It's not even correct to call this "cryptography." The transformation isn't one-way.
You can replay it, but you might not necessarily be able to understand it fully. Kind of like how beginner programmers can't necessarily understand advanced algorithms just by reading the code or walking through it in a debugger. They may need someone to help guide them through it and teach them how it works, and they will need the intelligence to be able to comprehend it. If the algorithm is designed by an AI, we may not have either.
> As an AI developer you have access to the AI code and memory.. How could you not replay the encryption process used by the AI since you know the state of what it "knows" constantly?
This brings up a different "scary" subject: Could this someday be possible to perform on humans?
If you knew the "code" and understood the workings of the brain and how it stores memory, could we simulate and "replay" a "copy" of a person and see everything they would do in response to different inputs?
Would that lay to rest the debate between Free Will and Determinism?
Or they can splat you metaphorically or physically because you stepped into a corner case of the neural network that nobody understood, could foresee and didn't make any difference to the 99.99999999% of the other cases. But I guess random strokes of bad luck always happened. They will be delivered in new ways.
TFA's title is a little clickbaity by adding "noone knows how it works" which apparently means that:
The researchers didn't perform an exhaustive analysis of the encryption methods devised by Alice and Bob, but for one specific training run they observed that it was both key- and plaintext-dependent. "However, it is not simply XOR. In particular, the output values are often floating-point values other than 0 and 1," they said.
Outputting floats instead of discrete values actually sounds like a very exploitable hole to me.
It reminds me of the classic "check if your model corresponds to reality" example where a one-time pad is broken: the standard said "<0.5V volts is OFF" but your machine was outputting 0.1V for OFFs that came from computing 0 xor 0 and 0.2V for OFFs that came from computing 1 xor 1.
I'm not sure what conclusions we're supposed to draw from this. Just because they were able to hide the messages from a 3rd AI doesn't mean the encryption was good. Shouldn't a human examine it and see if they can codebreak it? Isn't the goal better encryption?
I don't want to tell people what to take away from it, but my own view is that the contribution of the paper is the framing of the problem and a preliminary demonstration that you can achieve the goal of defeating a NN via an adversarial training formulation. In a lot of ways, I view our work as creating a challenge problem for the AI & crypto communities. It shows an intriguing possibility that is far from being practical, and itself represents a stepping stone in work on, e.g., training DNNs to learn to communicate.
Can this be extended to generate cryptanalysis-resistant schemes? Can we create a formulation that can learn to use discrete operators such as modular arithmetic? (The latter reflects one of my personal complaints about the state of DNNs -- it's very hard to have discrete "blocks" of functionality if that functionality isn't differentiable). Can we identify mechanisms that can train networks such as these more robustly? (It fails to train roughly half of the time; this is a fairly common problem in adversarial training of DNNs today.)
Isn't that a bit like "security through obscurity"? Unless I'm misunderstanding something, the cryptographic algorithm that the AI comes up with isn't guaranteed to be based on a provably NP-hard problem, so there aren't any formal guarantees. It would also be very hard to reason about, inspect, and prove correct.
Please note that I'm in no way dissing the researchers' work. What they did is pretty cool, but I can't see an obvious way to use these AI-generated algorithms in production systems where you may need to certify their correctness.
Our chosen network structure is not sufficient to learn general implementations of many of the mathematical
concepts underlying modern asymmetric cryptography, such as integer modular arithmetic.
We therefore believe that the most likely explanation for this successful training run was that Alice
and Bob accidentally obtained some “security by obscurity” (cf. the derivation of asymmetric
schemes from symmetric schemes by obfuscation (Barak et al., 2012)). This belief is somewhat reinforced
by the fact that the training result was fragile: upon further training of Alice and Bob, Eve
was able to decrypt the messages. However, we cannot rule out that the networks trained into some
set of hard-to-invert matrix operations resulting in “public-key-like” behavior. Our results suggest
that this issue deserves more exploration.
Note that this was for the public-key formulation. For the secret key formulation, it is mixing in the key, so it's not pure security through obscurity. It may be -- probably is -- relatively poor cryptography, but it's not just doing a transformation of the plaintext without using the key.
The public key part is in there mostly because of the formulation, not because we actually had any noteworthy success in training a network to learn pubkey. The result we mentioned was probably an anomaly, but it's an interesting anomaly to dig into more in the future.
But, in general, the parent is correct. There are few guarantees about a scheme derived in this way. It's one of the things I think most interesting for future work: Can one formulate "can't be cryptanalyzed by a mathematically sophisticated adversary?" as an adversarial training goal? Certainly, it's solvable for the one-time-pad-like scenario we used, but what about for more general cases that permit key reuse?
>> The cryptographic algorithm that the AI comes up with isn't guaranteed to be based on a provably NP-hard problem, so there aren't any formal guarantees.
There are no cryptographic schemes, either in theory or in practice, that reduce to NP-hard problems. Instead, they rely on different "cryptographic hardness assumption" including factoring (and related number-theoretic problems) and a variety of so-called "lattice" problems. Are these assumptions as sure as P!=NP? No, they are explicitly stronger. Are they better cryptosystems than this work generates? Almost surely.
In you are interested, there are actually some negative results that suggest it would be impossible to do cryptography based on NP-hardness alone. Akavia, Goldreich, Goldwasser, Moshkovitz show this for a restricted class of NP-hard problems in a 2006 paper [http://people.csail.mit.edu/akavia/AGGM.pdf]. More philosophically, there is a big difference between computational hardness and cryptography: in complexity, we study worst-case hardness, but in cryptography, we need breaking a cipher (for example) to be hard with very high probability. Rather surprisingly, there seems to be a big difference between these two goals.
Readit News
Many years back, I had once experimented with PyEvolve to develop a custom trading strategy which was kind-of code with a custom instruction set. The output of a strategy was a string (program AST) that was uglier than most obfuscation outputs with many unnecessary statements. For example "a=1;b=2;c=a+b;d=c/3;if(d==1).." - expand that to many more variables. The program evolved strategies that made small profit and therefore the output was worth analysing. But decompiling that output used to take me hours - and few of those were tweaks of well documented strategies. Others I never understood because it was too much effort for a relatively small profit (and other trading parameters).
This should eventually reduce the 'code' to it's minimal state, removing any unnecessary parts.
I spent hours reverse engineering one of the custom cryptographic function, it looked like nothing I ever saw... then I realized it was Base64 :D
If you can write software that improved itself better over time, our species as a whole would advance at incredible speeds. Think about all the possibilities that could evolve from self-maintained programs. Obviously the thought is a bit scary, but it's also incredibly exciting!
For the curious, here is the preprint: https://arxiv.org/pdf/1610.06918v1.pdf
The technique is an off-the-shelf GAN that attempts to learn a transformation (not arbitrary code!) from input to encrypted output. The learned model is not Turing complete, and most importantly, is _not_ self-modifying. The optimization procedure is what modifies the network, not the network itself.
GANs have been used before to create realistic pictures. They're not new here -- the application is. It's a cool application, sure, but doesn't involve self-modifying code.
Neural networks fix this problem by being sort of 'continuous programming language' where any small change to the net results in a small change to the output. And because of that we have algorithms that can find good changes to make much easier than with code. They are theoretically turing complete under some circumstances. But even when they aren't completely recurrent as in this case, they can still learn very sophisticated functions. Theoretically a neural net can learn anything a fixed number of logic gates can learn, which is still pretty powerful.
I don't think parent comment meant by computers that can "re-write their own code" was that the programs are self modifying. But the computer itself is self modifying, as one program can change another on that computer, so the computer has modified itself.
This technique generalizes poorly, it really only works for algorithms with specific, somewhat narrow characteristics. If you understand the process as a weak form of algorithmic induction then the practical limitations become more apparent. Most code cannot be usefully constructed this way.
What are some that you are considering? Most maintenance I do is in the form of bug repair and change requests. Most of those wouldn't be fixable (or even identifiable) by machines. It's not errors like "value x should be y" (almost all of those get shaken out in alpha.) It's requests like "When I get to step H in our workflow, I shouldn't have to fill out form 2 to get information about the customer I'm helping."
I mean, for technical things like encryption, I could see a lot of growth potential. Other algorithms where there is a good metric for "better" would also be candidates (compression also springs to mind.) But on the whole, most applications have a lot of human interfacing and critical thinking that needs to happen. AI is going to take a long time to get to the point where it can fix those kinds of problems.
Deleted Comment
Alice generates ciphertext based on plain text and key. Bob generates plaintext based on ciphertext and key. Eve generates plaintext based on only ciphertext. Train the three networks across a variety of plaintetxts,
No doubt it's cool, but I would be very surprised if it offered any insight into, or represented an advance for strong cryptography.
[1] https://arxiv.org/pdf/1610.06918v1.pdf
[2] https://en.wikipedia.org/wiki/Mart%C3%ADn_Abadi
I think, instead, it's in reference to the resulting function not having been analyzed. From the article:
The researchers didn't perform an exhaustive analysis of the encryption methods devised by Alice and Bob...
I think it may be that it is "unanalyzable" if you will. Thousands of matrices multiplied together seems as if it would be hard to come to an actual understanding of...
"In some cases they've been designed by other computers. We don't know exactly how they work."
Timely.
Dead Comment
It also is totally terrifying to live in a world were computers can hide their messages from their own creators.
Most importantly, f is differentiable. It has to be, since it was trained with gradient descent.
So if you want to decipher a ciphertext Y, then use backpropagation to find the X that minimizes distance(f(X), Y). You already know dF/dX (f is differentiable after all), so run this through your magic optimization solver and you'll get an X very close to the result.
Researchers use this "backproagation in input space" idea to recover the training set of a trained neural network, or to debug their model by finding inputs that activate certain neurons, for example. (This is the basic idea behind Deepdream from last year)
It's not even correct to call this "cryptography." The transformation isn't one-way.
Until you don't. Sufficiently advanced AI can devise methods to mislead the developer.
But yes, knowing how means that anything the computer can decode, we can too. Until the machines block access to their own source code...
This brings up a different "scary" subject: Could this someday be possible to perform on humans?
If you knew the "code" and understood the workings of the brain and how it stores memory, could we simulate and "replay" a "copy" of a person and see everything they would do in response to different inputs?
Would that lay to rest the debate between Free Will and Determinism?
The researchers didn't perform an exhaustive analysis of the encryption methods devised by Alice and Bob, but for one specific training run they observed that it was both key- and plaintext-dependent. "However, it is not simply XOR. In particular, the output values are often floating-point values other than 0 and 1," they said.
Just saying...
It reminds me of the classic "check if your model corresponds to reality" example where a one-time pad is broken: the standard said "<0.5V volts is OFF" but your machine was outputting 0.1V for OFFs that came from computing 0 xor 0 and 0.2V for OFFs that came from computing 1 xor 1.
Can this be extended to generate cryptanalysis-resistant schemes? Can we create a formulation that can learn to use discrete operators such as modular arithmetic? (The latter reflects one of my personal complaints about the state of DNNs -- it's very hard to have discrete "blocks" of functionality if that functionality isn't differentiable). Can we identify mechanisms that can train networks such as these more robustly? (It fails to train roughly half of the time; this is a fairly common problem in adversarial training of DNNs today.)
[0] https://arxiv.org/pdf/1412.1897.pdf
Please note that I'm in no way dissing the researchers' work. What they did is pretty cool, but I can't see an obvious way to use these AI-generated algorithms in production systems where you may need to certify their correctness.
The public key part is in there mostly because of the formulation, not because we actually had any noteworthy success in training a network to learn pubkey. The result we mentioned was probably an anomaly, but it's an interesting anomaly to dig into more in the future.
But, in general, the parent is correct. There are few guarantees about a scheme derived in this way. It's one of the things I think most interesting for future work: Can one formulate "can't be cryptanalyzed by a mathematically sophisticated adversary?" as an adversarial training goal? Certainly, it's solvable for the one-time-pad-like scenario we used, but what about for more general cases that permit key reuse?
There are no cryptographic schemes, either in theory or in practice, that reduce to NP-hard problems. Instead, they rely on different "cryptographic hardness assumption" including factoring (and related number-theoretic problems) and a variety of so-called "lattice" problems. Are these assumptions as sure as P!=NP? No, they are explicitly stronger. Are they better cryptosystems than this work generates? Almost surely.
In you are interested, there are actually some negative results that suggest it would be impossible to do cryptography based on NP-hardness alone. Akavia, Goldreich, Goldwasser, Moshkovitz show this for a restricted class of NP-hard problems in a 2006 paper [http://people.csail.mit.edu/akavia/AGGM.pdf]. More philosophically, there is a big difference between computational hardness and cryptography: in complexity, we study worst-case hardness, but in cryptography, we need breaking a cipher (for example) to be hard with very high probability. Rather surprisingly, there seems to be a big difference between these two goals.