Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am about to go study for my masters in machine learning, data mining and high performance computing, but have recently become very interested in cryptography after taking Dan Boneh's Cryptography course on coursera.com.

I was wondering if there are any practical applications for machine learning in cryptography? A quick google search didn't seem to reveal much for me so i was wondering if someone here knows something.

My first impression would be that machine learning techniques could be used to learn the inverse function for some cipher and passphrase given enough plaintext/ciphertext pairs, but i am not sure how capable things like neural networks are at learning functions which are not linearly separable.

share|improve this question
1  
The closest thing to automated cryptoanalysis are SAT solvers. –  CodesInChaos Aug 16 '13 at 13:23
1  
We sometimes employ machine learning techniques to show the security of PRNG and hardcore functions in cryptography. –  xagawa Aug 16 '13 at 15:23
add comment

3 Answers 3

up vote 5 down vote accepted

I would personally be very surprised if machine learning was of any use in a known plaintext attack.

We design our ciphers to look a lot like random functions; you give the black box an input, and an output spits out. You give it a second input (possibly the same input in the case of nondetermanistic encryption), and a second output spits out. What we try to achieve is that no one can determine whether the black box was our cipher (with an unknown key), or whether it's just spitting out random outputs.

Now, we assume that the attacker has the complete design of our input (apart from the 'key'); in a successful cipher, he still cannot determine it. In fact, we design things so that the attacker can submit inputs of his own choosing; he still cannot determine whether he's giving inputs to the cipher or a random function.

Now, what machine learning would be trying to do is essentially this, except that you would be ignoring the design (because there's no way to give the design to the machine learning process), and you are limited to a known plaintext attack (because your machine learner has no way to generate the chosen inputs). In addition, your machine learner would also not have the best asset a cryptanalyst has (which is his cleverness; programs aren't good at 'clever').

Now, I don't know enough about machine learning to say that it can't be used elsewhere (or that a clever cryptanalysis couldn't use a machine learning program to help with his cryptanalysis); however it certainly sounds to me that machine learning would not be enough to do the entire cryptanalysis job.

share|improve this answer
    
What about Neural Cryptography? The neural exchange protocol seems interesting but i have never actually heard of a crypto system that uses it. –  Michael Aquilina Aug 16 '13 at 14:36
add comment

Yes, machine learning has applications in cryptography. Probably not in a way that is applicable to your work, though. In the last couple decades cryptographers have been examining machine learning as a source of cryptographic hardness assumptions. The gist of it is that we can use the assumed hardness of learning certain distributions to make new primitives, which form the basis of new protocols.

Ron Rivest wrote a paper on the subject in 1993 called Cryptography and Machine Learning, but a lot of work has happened in the field since then.

More interesting to the OP is Regev's 2005 paper On lattices, learning with errors, random linear codes and cryptography. His results in that paper were really important in developing lattice cryptography and especially the 'learning with errors' assumption. I can't even pretend to understand the results in this area, but Wikipedia can give you a good start.

share|improve this answer
    
ah ! learning with errors is good example , did not strike me thanks for that –  sashank Mar 4 at 6:11
add comment

One possible research topic, appropriate to a Masters level, might be to look at the increase of randomness of common cipher algorithm(s) based of Feistel network, as you progress from round 1 to round n.

The machine learning aspect in this would be to try to find some correlation between input and output of the first round, and see if the machine can extend that knowledge to subsequent rounds. You can play with large datasets, may be with a variety of keys, trying to find data patterns that will help you tune the machine. If you are interested in neural networks, some input / key tuning attempts to minimize output randomness may weed out bad values that would also be useful for cryptanalysts.

I would bet, as poncho stated above, that as you go up the rounds, you will reach to a stage where you can not find I/O correlation anymore (the stage + some safety margin where that cipher becomes a useful tool of the trade). However, if you manage to pull that proposal off, your device would be a useful tool to help determine the min required numbers of rounds in order for a solid Feistel cipher algorithm to be declared "reasonably good".

share|improve this answer
    
would be interested if some body is doing this or want to do this . please reach out to me . –  sashank Mar 4 at 6:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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