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."
> Or a quantum computer is made that can break all these passwords.
No. To put in plain language: there are forms of encryption more advanced than those that employ difficult math problems. Quantum computing does not pose a threat to a OTP system that employs quantum key exchange. Sorry.
Since those are the areas in which most people encounter encryption, that's what the author was focusing on.
On the other hand, the author also didn't give any reason to think that P?=NP is even coming closer to being resolved, and certainly no reason to think that it will end up being P=NP...so I don't see how PKE is threatened, either.
It's a non-story, if you ask me. Not that anyone did.
Reality has a conservative bias: it conserves mass, energy, momentum...
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.
If by "prime-based" you're talking about deriving prime factors for things like RSA public keys, then the machines have been invented - they just haven't been built yet. Shor's Algorithm allows a quantum computer to factor numbers extremely rapidly, which breaks RSA quite badly. This is due to the nature of factoring, not of quantum computing itself - no quantum computing algorithm _presently_ known can break discrete-log encryption in less than the square root of the number of steps a classical computer would take to do it, for example. However, only time will reveal which algorithms are vulnerable to QC and which aren't.
Quantum computers with enough qubits to do useful RSA public-key factoring will probably be built within about 10-20 years, based on the progress to date. Possibly earlier, but I'm going to be conservative and hedge a bit.
Yes, but there's a reason P=NP is of particular interest for crypto problems.
NP problems as a category are easy to check answers, but hard to compute those answers. So a whole category of challenge-response systems are possible. I use the easy (checking) side of the NP problem and make codebreakers use the hard (computing) side.
For example, it's hard to factor large composite numbers, but easy to check if a set of primes multiplies out to that number.
Sure, there are plenty of other categories of crypto, but they're harder to deal with. One-time pads are hard to distribute, and quantum mechanical stuff isn't ready yet. But public-private key cryptosystems are based on computations like factoring: it's easy to encrypt something based on the large composite number, but harder to decrypt it unless you have the factors at hand. So I can distribute the large composite number (so anybody can send secret documents to me), and be fairly sure nobody will break the crypto.
Unless P=NP, in which case factoring the number will also be easy, and we'll have to resort to something smarter, like quantum crypto (assuming it can be made to work practically).
Firstly, the halting problem is trivially decidable for any particular program, the program either halts or it doesn't.
;-)
Sorry, you are wrong here. Yes, if you ran a program and it stopped you know your answer. But if the program is still running, how would you know if it will eventually halt or not? And if it is one of those programs that do *not* halt, you'd have to wait for infinite amount of time to declare it "non-halting".
As to your solution of "comparing P and NP sets" -- I think you are slightly trolling here!
Paul B.
Actually, it's problems solved in polynomial time vs non-deterministic polynomial time. Your two examples are both problems that can be solved in polynomial time.
It's not simple math. IE find two prime factors to a very very large number. Guesses are made to find the factors. But even though guesses are polynomial in amongst themselves, the number of guesses you need to make before you hit on a solution is non-deterministic. Thus it's NP (non-deterministic polynomial time).
by having a plaintext and cyphertext, a quantum computer can make it very trivial to find the key using certain iterative attacks on the algorithm. I mean, isn't the quantum computer "instantly" backtracking up until the substitution step of each round, as the operations would be reversible up until that point? I would think the complexity to crack is only dependant on the number of rounds.
There is no possibility to use a quantum computer to make simultaneous dictionary attack (guessing the key by trying all possible keys at the same time), because, contrary to what most people think, you can do only one usable computation at the same time on a quantum computer. The difference between classical and quantum computer is that you can 'tune' the quantum computer into doing this one computation which is important -- like the one needed to break the key. If you can do that, you've cracked the cipher. But it requires an algorithm specific to the cipher in question. A good defense before such attack would be to change the cipher in such a way as to make the corresponding quantum algorithm useless, and make attacker think really hard before coming up with another one. A bit more challenging than just increasing the key length.
IANAQCE (I Am Not A Quantum Computing Expert), but that's what I gathered from listening to seminars delivered by people from the field.
"Long run is a misleading guide to current affairs. In the long run we are all dead." (John Maynard Keynes)
While we are on the subject of P = NP here, there remains no proof either way that P = NP or that P != NP. However, a very large body of experimental evidence and related proofs tends to suggest that it is almost certain that P != NP. Many computer scientists are prepared to bet heavily on this outcome considering its near certainty. The threat to cryptography from quantum computing does not, as mentioned by Ckwop, have anything whatsoever to do with the computational complexity of the problem, but rather with the ability of quantum computers to try many solutions simultaneously, thus resulting in a much higher computational throughput. In effect the brute force attack is sped up by orders of magnitude and becomes feasible with today's algorithms and key sizes. However, the paranoid among us need not fear the death of encryption since quantum computing also makes possible new types of cryptography which are not based upon the asymptotic complexity of finding the solution to a problem. Even if all else fails we will always have the one time pad which is completely unbreakable (when proper pad discipline is observed) albeit somewhat cumbersome in practice.
I thought that all the public key (etc) systems relied on a "hard math problem" to produce the public-key secret-key pair.
Sort of. Actually, they rely on the hard math problem to make it so someone who knows the secret key can do something that someone who knows the public key cannot, and, potentially, vice versa. Generation of keys is simpler.
When I generate my DES and AES keys I go through that "mostly prime" exercise.
Umm, no. DES and AES don't care about primes, or factoring, etc., at all. The DES and AES keyspaces are (nearly) flat. To pick a DES/AES key, you just choose a random 56-bit/128-bit number. (I said nearly because DES does have some weak keys, so some people choose to avoid those).
So quantum computing should be able to do the "large nubmer factoring" exercise necessary to crack the key...
For public-key algorithsm like RSA, DSA, Diffie-Hellman, ECC (well, you don't use factoring to attack ECC, but same notion), etc., yes. For secret-key algorithms like DES, AES, IDEA, RC-4, Twofish, etc., no, there is no number factoring exercise or similar that will help. So probably not, which was my point.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.