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)
Additionally it should be noted that there are many complexity classes other than just P and NP, and there are many X such that X > P and X > NP.
True, but, in general, NP problems are really ideal for lots of cryptographic applications. The essence of the NP class is that it is the set of decision problems that are "easy" to solve given a particular piece of information and hard to solve otherwise. If I can be loose with terminology, an NP problem is a problem whose answer can be verified in polynomial time, but can only be found (as far as we know), in greater than polynomial time.
(BTW, I know the definition of NP as "non-deterministic polynomial", and what that means. The explanation I've given is equivalent, and easier to apply).
If P=NP, then all problems whose answers can be verified in polynomial time can also be solved in polynomial time. Of course, the polynomials in question could still make verification practical but solution impractical -- which is what we need for a useful public-key crypto algorithm. Or we could look to classes of algorithms of higher complexities, as you suggest, we'd have to find problems whose verification effort, although non-polynomial, was sufficiently low but whose solution effort was enough greater.
The really nice thing about NP is that when you increase the key size you're increasing the verification effort a small amount (it's pretty much linear with key size for the problems we use) and increasing the solution effort a large amount (as far as we know it's roughly exponential with the problems we use). This means that increased computing power always benefits the crypto user and hurts the attacker... because each increment of additional computation the crypto user chooses to perform creates a vastly larger amount of work for the attacker. The difference between linear and exponential is ideal.
None of this means that, in practice, algorithms base on decision problems in P, or EXP, or NEXP may very well be useful. But NP has a perfect structure, if it exists.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
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.
I have time to kill, am very interested in theoretical CS, and am a karma whore. Therefore I will now explain P vs NP in detail, in case anyone wants an explanation. I used this article to verify some of the fine points.
P and NP are classes of decision problems: problems in which you are presented with an input and must say "yes" or "no". For example, "Is this a prime number?" and "Is there a path from A to B on this graph (network)?" are decision problems.
A problem is in P if you can write a computer program to solve it in "polynomial" time. What that means is this: you give me a program, a polynomial (like 3*n^3) and a starting number m. Whenever your program is given an input, it must say "yes" or "no" within 3*n^3 time units. If the program you gave always gives the right answer in 3*n^3 steps (or whatever the polynomial was) for *any* input that's n symbols long, where n>=m, then the problem is in P. If no program and polynomial exist that satisfy this, then the problem is not in P. It's hard to prove that a problem is not in P, because you have to prove that no program at all can solve it.
NP is a bit more complicated. The definition is essentially the same as for P, except the program runs on a very strange kind of computer. One way of thinking of it is that it has a magic coin. Any time the program wants, it can flip the magic coin and decide what to do according to the whether the coin shows heads or tails. For example, if the computer wants to check if a number is composite (not prime), it can flip the coin a whole bunch of times to get the digits of a possible factor of the program. Here's the really confusing part: when you run the program, the computer actually tries every possible sequence of coin flips. If there is at least one sequence of flips that would get the program to say "yes", then the computer says "yes". If every single sequence says "no", then the computer says "no". So if the program wants to check if a number is composite, all it needs to do is flip the coin a few times to get a possible factor, and say whether that factor divides the number. If the number is composite, then at least one sequence of flips will generate a factor and the program will say "yes". NP stands for "non-deterministic", which is a good description of the weird computer.
A problem is in NP if the weird computer can solve it in polynomial time. Note that every problem in P is also in NP: if a normal computer can solve it without a magic coin, then so can the NP computer.
The question P=NP is the following: can every problem that can be solved in polynomial time on the weird computer also be solved in polynomial time (possibly with a larger polynomial) on a normal computer?
Two more definitions:
I hope I didn't just confuse you more... just read the wikipedia article if this doesn't help.
Each language has its purpose, however humble. -- The Tao of Programming
What's the difference?
That's a tough one to answer concisely. The best way to see the difference is probably to look at the algorithms.
Symmetric ciphers work by doing a whole bunch of different operations, mixing and munging the data in complex ways, and doing it over and over again. In the case of DES, for example, there are 16 rounds. AES-128 uses 10 rounds. Each of the individual mathemetical operations are simple, easily reversible and weak, from a security standpoint. The strength is achieved by repeating them many times in particular ways to create an overall structure that is hard to break.
In contrast, public key ciphers, like RSA, consist of only a single mathematical operation, one that has useful properties. An RSA encryption operation just requires calculating m^n mod p. The operation is very simple and straightforward, but there's no known way to reverse it efficently without the private key.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
If there is only one correct key, you can use the Grover algorithm to reduce the complexity to O(sqrt(N)). It first make a superposition of all possible N=2^n keys, then for each iteration the encryption algorithm is applied on it (simulataneously to all keys), yielding a "it is the right key or not" answer for each key, still superposed. Then a conditional 180deg-phase-shift operator and a "diffuse" operator is applied on the resulting superposed state, the result being that the eigenstate containing the correct key now has a larger weight than others in the superposed state, so that it has a higher probability to be observed when measured. By repeating the encryption-conditionPhaseShift-diffuse process O(sqrt(N)) times, the eigenstate containing the correct key will have a sufficiently large weight in the superposed state, and we can measure it and get the correct key with a high probability. So you see the encryption operation is always done simultaneously to every key, but you need to repeat the operation O(sqrt(N)) times to make the desired result strong enough to be measured.
Of course, the Grover algorithm is O(sqrt(N)), as opposed to O(N) of a purely brute-force attack, so just double the key length and you will be safe.
For references, google for "quprog.pdf".