Slashdot Mirror
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."
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.
dmiessler.com -- grep understanding knowledge
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.
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.
An Indian-American Hindu committed to non-violent thought/speech/action alarmed by the global explosion of radical Islam
But if a quantum computer can be made to do this, then most likely a quantum computer can be created to securly transmit one time pads to the other end. A one time pad is unbreakable because the key length is the same as the message length. (boy I hope I got that right :)
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.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
Quantum cryptography and one-time-pads don't solve encrypted storage though. Transmission of encrypted data is probably more important, but many new applications of cryptography are about tamper proofing data which is stored over a long time.
I agree on the high exponent/coefficient part, but even if P!=NP or polynomial solutions for formerly NP problems are still impractically complex in the interesting range, quantum computing poses another threat to "classic" public key cryptography.
Summa summarum it's MIT science at its best swallow and full of hype.
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.
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.
SYS 49152
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.
If you think 2+2=4 is simple, then you haven't seen this!
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.
Disclaimer: I don't know a bra from a ket, but...
If you had a quantum computer, could you break any public-key cryptosystem by doing:
(Or is the above stupid and wrong, and I'd need an actual course in quantum physics to even understand why?)
>;k
Whether the continuum hypothesis is true or false depends on your choice of axioms. I'm not sure what your statement about "if it is true, then it can't be proved true" means. If you accept the axiom of choice, then the continuum hypothesis is true, if you accept its negation then it isn't - simple as that, really.
It has been shown that with the standard set of axioms (without the 'axiom of choice'), you can construct models where the continuum hypothesis is either true or false, at your option.
If you incorporate the axiom of choice, then the continuum hypothesis is true.
If you incorporate the negation of the axiom of choice, then the continuum hypothesis is false.
For reference, the axiom of choice simply states that given a set of non-empty sets, it is possible to form another set consisting of one element from each set. Put another way, if I have several boxes, each box containing at least one item, then it is possible to take one item from each box.
When considering finite collections of sets (or even countably finite collection of sets), the statement is trivially true. When you allow uncountable collections of uncountable sets, things get...weird.
For example, if you allow the full form of the axiom of choice, then you can prove things like the Banach-Tarsky paradox, which basically says that you can cut the unit (solid) sphere up into finitely many pieces, and reassemble those pieces using only translation and rotation to form two spheres identical to the original. This is pretty fucked up, which is why the axiom of choice is considered a questionable one.
For an easier to grasp example, consider the set of all non-empty subsets of the reals. The axiom of choice says I can choose an element from each of those subsets. But how do I do that? What procedure do I use? At first you might say, pick the lowest or highest element, but what about those subsets unbounded at one end. Or the element closest to zero - but what about open sets where the infimum or supremum isn't in the set? It's really tricky to come up with a choice procedure, however complex, that works for all cases. After a while of playing with examples, you wonder if perhaps it's not possible.
Personally, I think the axiom of choice is a bad axiom. Choosing one thing from each set sounds like a sort of 'counting' operation to me, and yet the axiom of choice is saying that it's okay to do that even with uncountable collections of things. It's trying to crowbar the uncountable to behave like the countable. If you do that, thinks break.
So, from an intuitive point of view, where we don't like to have things like the Banach-Tarsky paradox, we could say that the axiom of choice is 'bad', and therefore that we prefer to believe its negation, and hence that the continuum hypothesis is false. A strict Platonist would probably take that point of view.
In support of this viewpoint is also the consideration of where axioms come from in the first place. They are things that we hold to be 'self evidently' true. For example, if A implies B and B implies C, then we can deduce by applying the transitive axiom that A implies C. That seems self evident, but to be rigorous we state it as an axiom. To me the axiom of choice just doesn't meet the 'smell test' for a self-evident axiom, but that's only an opinion.
If you're not a strict Platonist, then you might not believe that. Instead you might believe that there is no such thing as absolute truth, and that truth itself is a logical abstract and that one can only rationally ask about the truth or falsity of a statement in respect to a set of self-consistent axioms which can choose freely.
It is by having a satelite system, like the GPS system, constantly broadcast synchronized truly random data. That way, any two recipients can communicate as much data as they want by simply synchronizing their communication to a certain time, and using the one time pad that's being broadcast by the satelites at that point in time.
Now, this turns the one time pad bandwidth issue into a secret key (the timestamp) issue. How do you communicate the timestamp between the two sources?
There's another benefit though, and that's that the sheer amount of data being generated by these satelites will make it prohibitive to analyze a transmission after the fact... only live interceptions could be used.
The thing that makes Quantum Computers a bit scary is that algorithms like Shor's have shown that QC's can give an exponential speed-up to some problems (assuming P!=NP). Prime factorization happens to be one example that is of particular interest to cryptographers. The reason this is possible is because most of our algorithmic complexity analysis to date is based on the assumption that the computers the algorithms are running on are (read: can be modelled as) Turing machines. Quantum computers are not Turing machines, which is why they get to "break" the rules.
Here's another example of an algorithm for which Quantum computers "break" classical algorithmic bounds. It can be proven that no "classical" computer can search for an item in an unsorted list in better than O(n) time. This not only makes intuitive sense, it can be mathematically proven. However, there is an algorithm to do the same thing on QC's in O(sqrt(n)) time.
Therefore, OTP isn't really unbreakable either.
On the contrary, a real (see rules below) one-time pad is truly the only unbreakable cryptosystem. Without access to the key, no amount of brute-forcing or analysis will ever recover the plaintext.
OTP could partially be helped by using commonly available documents, images, binaries, whatever as the pad, but then you increase the chances of someone else finding the pad, and you still have to store an index of which document uses which pad somewhere.
People keep suggesting this sort of thing - eliminate the cumbersome difficulties of a genuine one-time pad by using some sort of public data. Dictionaries, encyclopedias, or virtually any other store of information are NOT suitable for use as one-time pads. Using non-random data for your pad destroys the inherent security of the one-time pad. There is no shortcut.
Rules of one-time pads:
1) Data MUST be completely random. Pseudo-random does not count. "Looks random to me" does not count. "Comes from a much larger set of data" (a la phone book, etc) does not count. How to generate this random data is left as an exercise to the reader.
2) Data must NEVER be reused. Not to the same recipient, not on the same message, not when you run out of pads.
3) Data must only be known to those who can be trusted with the plaintext of the message (duh!).
A proof of P=NP could merely show there must exist a P algorithm for every NP problem. It doesn't necessarily have to give such an algorithm, only show its theoretical existence. While such a proof would prove P=NP, it would still be of little practicle use.
Only once such a conversion algorithm is found then, yes, every NP problem can be actually solved in polynomial time.
What about the NP-complete Mine Sweeper? NP-complete problems in Tetris?
Factoring is in the intersection of NP and coNP, and thus is (with the current knowledge) probably easier than NP-complete problems. Proving P=NP makes NP-complete problems easier, but Factoring never was that difficult.
It draws its strength partially due to the fact that it uses very large numbers. So even a polynomial algorithm (if it has a high degree) may not be fast enough in practice if a key can be generated much faster.