The End of Encryption?

An anonymous reader writes "The encryption algorithms that make virtually all electronic commerce possible work only because certain mathematical problems are very, very hard to solve. But some mathematicians are trying to prove that there's really no difference between 'hard' and 'not hard' problems--known in the math biz as P and NP. In an article on TechnologyReview.com, Simson Garfinkel spells out the real-world consequences of this mathematical conundrum."

Comments

Easy killer...

[danielrm26]

This is really quite simple - the type of machine that can render Prime-based and Discrete Log-based encryption "useless" has not been invented yet. Furthermore, as the article points out, most (including Adelman) belive it'll be a long time before one is.

The problem (P vs. NP) is still just as difficult, and we aren't really much closer to solving it than 10 or 20 years ago.

Could be argued

[onyxruby]

Could be argued, for that matter the entire concept of "random" is truely just a human thought construct. Since crypto is heavily dependent upon the concept of random, this will become a bigger problem as time goes on.

It can well be argued that absolutely nothing is in fact random. From coin flips to roulette anything can eventually be learned and predicted on some level. The only point where I might even question this is with quantam states, and even there we really know precious little. It is simply too early to say one way or another on quantam.

Re:Could be argued

[DarkMan]

The only point where I might even question this is with quantam states, and even there we really know precious little.

Uh, sort of. Heisenbergs uncertinty principle can be read as "We can never know the details" of quantum states. If it is true, then it does not matter whether or not a quantum state could be determanitsic if we can measure the things we need to determine it.

Now, there is an awful lot of discoveries and technology that have been predicated on Heisenbergs principle being true (or, at least, true enough, for some value of enough) [0]. Thus, the burden of proof is heavily on the side of anyone claiming that it's not valid (just as it is for anyone claiming Einsteins relativity is wrong, and as it was for Einstien when he showed Newton was wrong [1]).

So, I refute your claim on 'It's too early', by Schottky diodes, Mossbauer spectroscopy and quantum computing, which all rely on quantum states having true randomness [2].

Furthermore, by the way, there was a bunch of work on something called the Bell inequality, which, although painfully esoteric in testing, has disproved the existance of hidden variables. That is, it is _not_ the case that quantum states are deterministic, by data we can't measure. There are no such hidden bits of data.

Moreover, pretty much every macroscopic physical observable is a statistical average of very many microscopic states or events. These microstates are randomly distributed within some known distribution (e.g. disribution individual molectular kinetic energies for a given temperature of a set of particles). The various physical laws that we depend on (in the case of temperature, the predicability of the increase in the rate of some chemical reaction with increasing temperature, for example) have the concept of this random disribution so inherent in them, that I must argue that if 'random' is a a human thought construct, it is fortunate that the laws of nature also think that way (i.e. random is a physical concept)

Such is the opinion of this quantum physicist, at any rate.

[0] E.g Mossbauer spectroscopy
[1] Strictly, Newton was farsighted enough to state his basic assumptions expcitly. Einstein just showed that one of them ("Time is the same for all men") was incorrect, and the consequences of it.
[2] Or, at very least, something that is indistinguisable from it.

All he does is explain P and NP

[GillBates0]

and ponders over whether the recent MD5 news from the Mathematics conference (in an earlier /. story today) will lead to any discoveries that may help answer whether P=NP.

Ignoring the fact that the answer to P?=NP has little to do with breaking encryption for a moment, even if an NP computer is conceived and developed, it'll just lay down a *huge* plethora of computing possibilities at our disposal, including new encryption techniques.

Encryption cannot die, algorithms can.

Re:Quantum Computers / Shor's Algorithm

[swillden]

Quantum computing does not pose a threat to a OTP system that employs quantum key exchange.

In practice it may never pose a threat to symmetric ciphers, like AES, either. Those don't rely on hard math problems as much as on non-linearity and complexity. Quantum computers may someday be good at solving simple but hard problems, but it's likely they'll never be able to attack complex problems, easy or hard.

Re:Nope, wrong, invalid.. nothing to see here.

[J.R. Random]

Sure there are harder complexity classes than NP, but they are irrelevant to cryptography. The point of cryptography is that for some encrpted message E there is a key K that makes E easy to decode. So the problem is in NP -- the NP machine guesses K and does the decryption. If you make your decryption problem harder than NP, then even with the key it will take a ridiculous amount of time to decode the message. Here of course I'm talking about public key encryption. The complexity issues are irrelevant to a one time pad, but a one time pad has to be as big as the message. So if you have a channel secure enough to send the one time pad, you may as well sent the message instead.

Re:Nope, wrong, invalid.. nothing to see here.

[mmusson]

Also, if a P=NP proof was found it would not necessarily gives us a procedure for generating the P algorithm that solves the NP complete problem. This would be an unfortunate situation.

Re:Eventually

[Anonymous Coward]

Digital Fortress was a total piece of crap. While A moderatly interesting book, the crypto is totally wrong. The ONLY perfect encryption is a one-time-pad. If there is a key it can be broken. The whole "make it impossible to figure out it its really cleartext" is just a not-so-clever plot device.

Think about it this way, when you use PGP/GPG to encrypt something, it compresses the file first. The argument Dan Brown used was that when you try a key on this "unbreakable" crypto that you get garbage out and can't use the typical language statistics to figure out if the result is valid or not. If this was true, then any form of binary data would be impossible to decrypt.

A more mathish approach. The idea was to take a cleartext, M, run it through a "magic function" Z then encrypt that, or Encrypt(Z(M)). Well, a little digging will find that chained encryption doesn't buy much. Thats why AES is around, rather than using 3DES or 5DES. or nDES. All his digital fortress was doing was using two encryption methods. But, this just doesn't work.

Dan Brown doesn't think or do any research whatsoever before he writes a book. Virtually ALL of the crypto related information was WRONG. Skipjack was a problem, not because of any backdoor, but because it was only availible as a tamper-proof hardware chip, noone got to look at it. The Caesar cipher was an alphabetic rotation, not a geometric cipher. Hell, there simply isn't enough energy given out by a star in a year to power a machine capable of brute-forcing 256-bit encryption, schieder wrote an essay on it.

Under current theory, the ONLY perfect encryption scheme is a OTP.

Re:Ha!

[kallisti]

If you think 2+2=4 is simple, then you haven't seen this!

Re:Nope, wrong, invalid.. nothing to see here.

[iwadasn]

This is why you use extremely long keys and strong algorithms. Use 4k RSA keys guys. It doesn't guarantee against attacks, but it does dramatically extend the time horizon. Even if there is a means of making factoring easier, it might not make it easy enough if the key is very big.

Make a key 10^10 as hard as the biggest one that can be broken (at least), and then only a very severe break will put you in danger.