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

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

[Ckwop]

No no no no no. How many more times? Cryptography has absolutely nothing to do with the question of P?=NP.

P?=NP refers to the asymptotic complexity as the problem. i.e. as the input size goes to infinity. It quite possible to have a problem whos complexity is approximately linear at the 100-1000-bit range and still NP-Complete. Conversely, it's possible to have a p-time algorithm for solving a problem that has a O(n^100) so it's still difficult to solve. While resolving P?=NP might bring new tricks to the table it's difficult to legislate for these tricks. There might not even be any we don't already know.

Another point, p?=np has no bearing on the security proof of the one-time pad or quantum mechanical key exchange. The latter will become practical over large distances to enable the former long before p?np is resolved. Cryptography will die when the last human draws its breath.

Simon.

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

[strictfoo]

These guys couldn't even figure out when the century began.

"There was a little bit of a controversy as to when the entry of the century was," he recalls. "Was it January 1, 2000, or January 1, 2001?

Come on now. They can't figure out that and we're looking to them to figure out the whole P=NP mess?

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

[Geiger581]

What you say is very true, but there are two big exceptions to note:
1) 1TP/QKE require as much storage/bandwidth for the key as for the message, and the key can never be resused. These are both severe drawbacks.
2) Crypto is useful for more than just hiding information. Digital signatures/integrity hashes are both very important and impossible to achieve -reuseably- with either of the schemes mentioned above.

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

[dmeranda]

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.

So even IF the P?=NP question applies, it doen't mean that cryptography itself is doomed. Just that harder problems might need to be used as the basis.

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

[Kippesoep]

Cryptography will die when the last human draws its breath. Probably one human before that. The last human won't need encryption, will he?

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

[tsg]

These guys couldn't even figure out when the century began.

This could, quite possibly, be the only time the answer to that question actually mattered, and it turned out it didn't anyway...

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

[Ckwop]

So even IF the P?=NP question applies, it doen't mean that cryptography itself is doomed. Just that harder problems might need to be used as the basis.

Let me illustrate this a bit clearer. P could equal NP but lets say that the result is that for every NP problem the P time solution has a O(n^100). At infinity this is still quicker than the old solution NP-time based solution but at the usable key ranges it's totally useless.

Simon.

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

[Anonymous Coward]

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.

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

[plover]

Perhaps the author expressed the idea poorly by stating it in terms of solving P?=NP, but the ultimate point he was trying to get across is: will the currently difficult* problems that are the basis of modern cryptography remain difficult into the future? And for how long?

* I'm deliberately leaving 'difficult' undefined to dodge abuse from the language lawyers.

I've always wondered what would happen if some 15-year-old math wiz who is playing around in Mathematica comes up with a novel approach to factoring; and then what effect that would have on modern cryptography and communications. This article simply inflates that idea into a paranoia for the masses. Which, as you said, is nothing to see here, move along...

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

[jo42]

Only if he doesn't want Alien Archeologists reading his writings...

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.

[jfengel]

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).

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

[John Courtland]

So if you have a channel secure enough to send the one time pad, you may as well sent the message instead.

I wouldn't go so far as to say that. The pad has no bearing on the message sent aside from the ability to decrypt it, so you send the OTP via quantum-encrypted channels and verify its integrity at the recipient end. If the pad has not been comprimised *then* you send an OK (via the same quantum-encrypted channel, just in case) to recieve the encrypted message. This gives you one extra layer of security that pretty much defeats any monkey in the middle style attacks, because you need not send data unless the recipient is sure the pad is secure.

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

[gweihir]

So even IF the P?=NP question applies, it doen't mean that cryptography itself is doomed. Just that harder problems might need to be used as the basis.

Not really. The P vs. NP problem is used mostly for one-way functions (P for the user, NP for the attacker). But, say, x^2 for the user and x^8 for the attacker could work as well, depending on the constant.

In an extreme case even x for the user and x^2 for the attacker might be enough. And there are plenty of problems with that profile.

And of course, there is no impact at all on block ciphers and hash-functions.

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

[Anonymous Coward]

The problem is this: If you have a problem that is solvable in O(n^100), there will soon be an algorithm that can do it within O(n^5) or less. I don't think that there exists **ANY** polynomial time problem whose complexity is > O(n^feasiblenumber).

P?=NP is very correctly the real hard-nut which is holding the world of cryptography together.

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

[Anonymous Coward]

Well, the "O(n^k) with k>1000" situation is a possibility, yes. But it would nevertheless be quite an awkward situation for someone worried about their privacy. If someone proves "P==NP" without proving some incredibly strong tight lower bound on the exponent k, it would be almost criminal to not become incredibly worried about all online transactions (I mean transaction in a very broad sense here.)

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

[RWerp]

quantum computing poses another threat to "classic" public key cryptography.

Not in predictable future. Quantum computing is still on the level of manufacturing single cubits and making them work together. It's worse than Babbage machine, when it comes to practical use.

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

[RWerp]

I've always wondered what would happen if some 15-year-old math wiz who is playing around in Mathematica comes up with a novel approach to factoring

If anybody does something about factoring, he will do it with pencil and paper (or blackboard and chalk), not with Mathematica. Mathematica is only as good as the mathematicians are, it's not a magic box sent from heaven.

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:Nope, wrong, invalid.. nothing to see here.

[Anonymous Coward]

Yup. If P=NP, then current cryptography is almost certainly dead. Sad that someone making a big deal about a technical detail that is unlikely to matter gets +5 Insightful, but hey, this is Slashdot.

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

[shawn(at)fsu]

This article simply inflates that idea into a paranoia for the masses

Can't that be said for every article on /.?

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

[swillden]

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.

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

[Scorillo47]

>>> Cryptography will die when the last human draws its breath.

You meant, cryptography will die when the third to last human draws its breath, correct? When you have two humans left there is no need for cryptography.

Remember: Alice, Bob, Eve...

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

[Anonymous Coward]

You're wrong, sorry:

1) The expresion "asymptotic complexity" it is non-sense as you used it: the complexity of *every* problem it is a mathematical limit (not a dynamic structure nor a dynamic anything nor a graphical representation).
2) O(n^(constant)) implies *polynomial* time, there is no need to find a "p-time" algorithm, as for giving the O() you previously had to do a model (!) (how you can tell the complexity of something without an algorithm?!).
3) As often, instead of working hard to find a nice solution, you go for the mystic/magic way: "quantum computing", id est, you want some magic apparatus/engine that solves the problem with few brain usage. What a curious world.

Other focus:

1) Actually, and since many years ago, there are lots of people working on these problems. I still can tell a bit more: the main vital target for many computer science entusiasts it is to pursue the holly grial of complexity, on work hours or at home, not for money, may be just for two lines inside a enciclopaedia.
2) There are heuristics, of course, that allow to you to take some short cuts when attempting to lowering time complexity via time to space complexity transfer.
3) Exist an interesting aproach, being studied at least in Barcelona: reducing the complexity of the problem rewriting it as other problem; the new problem generates to signals, the second one it is used as redundant storage for driving the main signal avoiding the generation of new redundancies . Nowdays this technique it is not still a solution for the problem discussed here. A trivial analogy it is the butterfly diagrams that helps to reduce the complexity of the FFT (discrete Fourier transform for discrete time).

ngorafa

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

[CodeBuster]

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.

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

[swillden]

The last human won't need encryption, will he?

Depends on how paranoid he is. Given that he murdered the other plotting bastard in his sleep, he may very well need to encrypt his diary. Just in case. He'll keep his tinfoil hat on, too.

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

[attam]

i took ron rivest's crypto class my senior year at MIT and simson was the TA (one of two TAs actually). oh man, is this guy high on himself! he might be the most condescending person i've ever talked to and the worst part is that he doesn't even seem to realize it. he has crazy articles in techreview all the time and sometimes it just seems like he is fishing for "a good idea."
all in all, i know he's a sharp guy, but i think sometimes his ambition wins over his better judgement.

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

[Coryoth]

Factoring is overrated. A good solution to factoring will only really kill RSA. What you really want is a fast solution to the discrete Log Problem for arbitrary groups. Solve that and Diffie-Hellman, El-Gamal systems (pretty much all public key crypto, including elliptic curve crypto) are out the window, and serious problems result.

Jedidiah

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

[CodeBuster]

The set of NP problems refers to the set of problems which cannot be solved in time polynomial in the size of the input. However it has been proved that any problem in NP can be reduced to any other problem in NP. For example it is possible to reduce the all pairs shortest path problem to the satisfiability problem by some reduction function. Therefore, if P WAS equal to NP then any problem in NP could be reduced to a problem in P and solved in polynomial time. Thus if P = NP then it does not make sense to look at 'harder' problems since they could always be reduced to P. In effect there would be no 'harder' problems.

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

[DavidTC]

In fact, you don't even need to make the pad in advance, if you can write a quantum data stream that changes when intercepted. (Which has actually already been done.)

What you can do is just split the data in half. For each bit, come up with a random value, XOR it with the data, and transmit one of those now, and the other one later, when you're sure the first half got there. (For speed, you might want to do that in large blocks, 1024 bytes or whatever.)

At the other end, you need to, every X bytes, make a checksum and send it back the other way. (Of course, you need some way of making sure that the line hasn't been completely cut and the data retransmitted. Which you can do if you constantly keep the data line running, transmitting a known pattern.)

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

[Greedo]

He'll still need to hide his porno from the aliens.

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

[Surt]

So when it's down to Alice and Bob, Bob can leave his diary unlocked?

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.

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

[Captain Segfault]

No no no no no no! Your first sentence is wrong! See Wikipedia's complexity article

In any case, we could use a problem with, say, exponential complexity (in particular, not in NP) such that the reverse is also exponential, but with a larger exponent, such that it would still be exponentially easier to encode than to decode.

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

[EveryTroll]

Except, of course, that this only protects against eavesdropping, not against a true man-in-the-middle attack.

If the quantum data stream (or any data stream, ever) is received by the man-in-the-middle, then a new data stream is transmitted to the original destination, there is still vulnerability. You only get link security, not end-to-end security.

There's a *lot* you can do with that to make communication more secure, but it's not omnipotent. In particular, it's vulnerable to the insider with unlimited access to the communications infrastructure, which is -- humorously enough -- where it's being marketed to. For long range military applications I'd say it's pretty darn good (hard to intercept satellite communications without being detected) but it's still not perfect.

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

[Zeinfeld]

P?=NP refers to the asymptotic complexity as the problem. i.e. as the input size goes to infinity. It quite possible to have a problem whos complexity is approximately linear at the 100-1000-bit range and still NP-Complete. Conversely, it's possible to have a p-time algorithm for solving a problem that has a O(n^100) so it's still difficult to solve. While resolving P?=NP might bring new tricks to the table it's difficult to legislate for these tricks. There might not even be any we don't already know.

Early on people tried to create public key algorithms out of known NP complete knapsack problems. They ended up with exactly this problem, most NP complete problems have subsets that are way simpler. With cryptography you want a problem that is predictably difficult to break.

Factorization is not an NP complete problem, a solution to the travelling salesman problem will not solve factorization. [BTW the gender is intentional, the reason the salesman is visiting the cities in the first place is he has a mistress in each town]

When you get to something like a block cipher the difficulty is not even characterisable in terms of a single dimension. You have the number of bits of key, the number of rounds, etc. etc. The exponential difficulty in the length of the key is the consequence of the number of rounds, the mixing caused by the interchange function etc. etc.

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

[PatientZero]

So if you have a channel secure enough to send the one time pad, you may as well sen[d] the message instead.

You're forgetting about time. It may be the case that you have a secure channel for the OTP now that won't be available when you need to send the message.

For example, you can exchange huge sets of pads face-to-face that can later be used to send messages over insecure channels.

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

[DavidTC]

Right, that's why I said you should transmit data constantly, a known pattern. (A known pattern before being encrypted, that is.)

This doesn't ensure that the line wasn't tapped before being purchased, but it does keep it from being so afterwards without people noticing.

There may be possibly a way to use photon entanglement to ensure the line is not tapped, now that I think of it. They may be able to retransmit the photon, but they couldn't re-entagle it.

Erm, actually, maybe they could just entangle another photon, and then read that one after you already read the other end. Ugh. There has to be a way to set it up securely, it's inane to have a link that's untappable without being noticed while in use, but no way to secure it beforehand.

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

[mvdw]

Wouldn't he just have to put them in Morse Code?

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

[NarrMaster]

Ok, look at it this way. RSA: Complexity based on factoring a large number with two large prime factors. Assume a reasonable algorithm for say, 3-sat (an NP-complete problem). Encode a multiplier circuit in 3-sat(follows from 3-sat's NP-Completeness). Number to factor = output. Solve. Answer = input to circuit = factors of said number.

Also: Encode a hash function in 3-sat. Solve for desired input. etc, etc. the list goes on.

Basically, P=NP? can be stated a different way: are there such things as true one-way functions? Most, but not all encryption methods rely on one-way functions.

I am currently engaged in a research paper to explore probabilistic methods for factoring in this exact way (i.e. with 3-sat).

Of course, this assumes a fast algorithm for NP-complete problems. But, of course, OTP and QMKE are still secure.

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

[CodeBuster]

Granted, but please understand that it has been several years since I last looked at this material in a university course on Algorithm Design and Complexity Analysis. That having been said, what I meant (and should have said) was the NP-C or NP Complete problems. It follows from the formal definition that:

A decision problem C is NP-complete if:

1) it is in NP and

2) every other problem in NP is reducible to it. Where reduction means that for every problem L, there is a polynomial-time many-one reduction, a deterministic algorithm which transforms L into instances of C, such that the answer to C is yes if and only if the answer to L is yes.

Sigh...formalisms are so tedious, but some people live for this sort of thing. Anyway, since NP-C is a subset of NP and NP overlaps P it follows that IF someone proves that P = NP then the problems in NP-C can be reduced so that they are equivalent to solving a problem in P which is bad for current cryptography methods for obvious reasons. My previous post was an honest mistake and I stand corrected.

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

[Cpt. Fwiffo]

And what would it mean to use a harder problem?

a problem is in NP, iff it has a polynomial time verifier.
Thus, by definition, NP includes all problems in P (yet not the other way round).

IF a problem has a non polynomial verifier, it is useless for cryptography as it would take too much time to verify the correctness of the input recieved. It would be nonpolynomial.
Not even that, it would be beyond NP to verify (as P=NP would imply that any nonpolynomial verification would also be polynomial).

We thus end up in PSPACE. Yet these problems are

SO, P=NP is certainly important for cryptography, as it would require to fall back on other methods.

One time pads may be nice, but they're simply unworkable. If we were to use one-time pad passwords, it would mean that for every password you had, you would have to use a list of 'one time' codes. Security then would become no better then the place where that piece of machinery is stashed. It cannot be paper, because we cannot expect people to continually write down long, long lines as passwords - especially if they were to be random characters (which you would want for security).
So it would have to be an electronic device.

That would require that we have an electronic device for *every* password we have (of course, we *can* make a 'master device' which functions as all, but that is a major security risk I would not want to take).

In short, first think of what it would mean if we were to use harder problems. The current NP class is a perfect class: it is (nigh) impossible to break, yet easy to prove the correctness of a token.

Regards,

Koos

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

[Mark J Tilford]

<>

Wrong; to be in NP, it is only necessary that the solution can be verified in polynomial time; every problem in P is also in NP. You may have been thinking of NP-complete.

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

[Hast]

In case you don't know why this is a question the reason is that there is no year 0. Thus the second decennium began year 11 and so forth which leads to the conclusion that the second milennium began year 2001.

However 1 year wrong on the scale of 2000 years is a pretty marginal error considering what usually happens in this world fill with people who can't grasp basic math and statistics so I say we should let it pass.

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

[swillden]

Wrong; to be in NP, it is only necessary that the solution can be verified in polynomial time; every problem in P is also in NP.

Correct. I was describing NP \ P. My mistake.

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

[bobbozzo]

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.

OTP is EXTREMELY cumbersome...

Not only do you have the key exchange problem, but if you want to store the encrypted text, you also have to keep a copy of the pad somewhere, for EACH document.

Therefore, OTP isn't really unbreakable either.

With key-based crypto, you can keep a password-protected copy of the key(s) on a usb token or whatever, and you only need one key for infinite documents.

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.

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

[russellh]

I've always wondered what would happen if some 15-year-old math wiz who is playing around in Mathematica comes up with a novel approach to factoring; and then what effect that would have on modern cryptography and communications.

Such people may be hired by the NSA

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

[HuguesT]

I don't think so,

All the *NP-Complete* are in the same class and therefore equivalent to TSP, which is not approximately linear anywhere.

What you are describing are some problems in P and some in NP\P, not the NP-complete problems.

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

[djfray]

perhaps we shouldn't speak of what quantum computing makes possible until quantum computing is itself feasible? people seem to make it out to be more than it is

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

[whiteknight31]

With Quantum encryption you have the ability to tell whether the data you have sent was read before it reached the final destination. So you can send the one time pad and tell whether it was read. If it was read you either find where it was read or simply resend another one time pad until your message is not read. If you sent the plain text you would know it was read, but that wouldn't help you much if it was important data.

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

[strictfoo]

In case you don't know why this is a question the reason is that there is no year 0.

Yes, everyone (with a mildly scientific brain) knows that and agrees with that. First century 1-100, 2nd century 101-200, and so on. That was the point. The answer is clear to anyone with half a brain.

1 year wrong on the scale of 2000 years is a pretty marginal error

It may be a marginal error, but it's an error none the less.

considering what usually happens in this world fill with people who can't grasp basic math and statistics so I say we should let it pass

But these aren't supposed to be just normal people, they're the people who are supposed to be "trying to prove that there's really no difference between 'hard' and 'not hard' problems".

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

[DarkMantle]

But did it ACTUALLY begin then? remember there was the issue of missing 10 days (section 2.3) If the Julian calendar was (and is) right then it's August 20th today instead of september 2nd

So maybe we're all wrong.

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

[jasgo]

the second decennium began

Erm, decade?

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

[ktakki]

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.

There's nothing stopping one from sending more than one "one time pad" through that initial secure channel. Consider the example of a DVD-R filled with random data in a diplomatic pouch (or a USB keychain drive working its way through a courier's intestines). I'm sure you can send enough data for a year's worth of one time pads that way. Or for that matter, an agreement to use the King James Bible as a pad, starting at Exodus 9:3.

It's my impression that cryptography is all about sending secure messages over an insecure channel (e.g., the Venona intercepts of Soviet telegraph messages, Enigma, JP-25). Transmission of timely intelligence or operational data can't always wait for a secure channel.

k.

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

[SpootFinallyRegister]

you have roundly missed the point.

any device, convention, or algorithm for any secure exchange falls into one of two categories.

the first is algorithmic. this is where NP-complete comes in, as well as NP-hard. first off, no, there are not approximately linear heuristic solutions to np-complete problems. you may feel smart tossing that out like its a fact, but i invite you to give me one example of a near linear (hell, near polynomial) np-complete problem heuristic that holds for a large probelm space. ill make you a bet: if you can, you have already won both a nobel prize and a fields medal. you are straightforwardly proving that you are out of your element discussing P vs NP.

second, there is the topic of a direct physical security. yes, quantum key exchange does obviate algorithmic security. however, quantum key exchange requires a physical implementation, and the improtant parts of security and cryptography in our time are based on security over an insecure link. if we had the luxury of a lower bandwidth, completely secure link for pad exchange, none of this would matter. however, pad exchange is a reality; and has been ever since caesar was tattooing one time pads on his messengers heads. why? because that was the closest he could get to a secure link.

while physically secure links obviate the need for algorithmic security, physically secure links are not widely available, and the interesting problem at hand is security over physically insecure links. thus, algorithmic security is what is important in the argument.

as for algorithmic security, the discovery of a P solution to an NP-complete problem would immediately destory current cryptography, period. even such a solution to an NP-hard would provide a clear path of research that would likely result in a NP-complete P solution in short time. such a solution would enable an efficient search of an entire solution space, and in case you dont understand that, a brute force password (or hash collision, certificate, any other damn thing) search could be implemented in time logarithmic to the size of the key.

you have officially left the signal and become part of the noise.

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

[cLOUDFAn]

i might be wrong but according to what i know, if P=NP then we can do factorization in time P, which means its doable (might be a polynomial w/ huge power, but mathematically doable). and if we can do factorization in time P, then we can break RSA in time P (again, doable but might take a lot of time). so my point is P?=NP does have something to do w/ cryptography.

-Fan

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

[Anonymous Coward]

Be careful: NP \ P != NP-complete.

A problem is only NP-complete if it is both in NP and in NP-hard. Many problems exist which we know are not P, but have not been able to show to be NP-complete.

In fact, according to this article, although we know that integer factorization is in NP, "[i]t is suspected to be outside of all three of the complexity classes P, NP-Complete, and co-NP-Complete".

Another interesting problem (not necessarily related to prime factoring) is graph isomorphism, which "seems to fall in a crack between P and NP-complete".

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

[nachoboy]

There's nothing stopping one from sending more than one "one time pad" through that initial secure channel ... Or for that matter, an agreement to use the King James Bible as a pad, starting at Exodus 9:3

Bzzzzzt. Wrong answer. The security of a one-time pad lies in the fact that the pad contains truly random data and that the pad is only used once. Pseudo-random number generators, or, worse, English text can NOT substitute for real random data. Read the first chapter of any cryptography text for more details. (Personally I recommend Schneier.)

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

[Anonymous Coward]

what? Yes it would! Practically by definition, if you can solve ANY np problem in p time (for example the travelling salesman problem) then you can solve EVERY NP problem in p time.

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

[stuktongue]

Not that I have anything against Mr. Garfinkel, but...

"Simson Garfinkel ... SUCKS!"

Those of you who watched an LSC show in 26-100 ~20 years ago will recognize what I am referring to. (Sorry for ending with a preposition :-)

-- Adam Grenberg, MIT '87

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

[nachoboy]

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!).

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

[logpoacher]

Everyone knows that the 3rd Millenium began on 1st Jan 2000, because that's when the big parties happened! Thus indicating a dangerous difference between theory and practice....

Of course, the whole disparity can be trivially fixed by declaring that the first decade was a nine year decade!

Next problem?

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

[thisfred]

Exactly. This:

Most of these problems are so easy, in fact, that we hardly even consider them to be problems at all. For example, multiplying two numbers together is a P problem: the solution can be found in polynomial time.

so stupid, that even if there was *any* news in the rest of the article, I'd question its veracity. Multiplying two numbers together is a Linear problem. (Linear problems may be considered P, but noone who knew what he was talking about would use muliplication as an example of P.)

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

[Anonymous Coward]

Huh? there should be an automatic -5 moderation for spelling mistakes ...

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

[ashar]

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.

Just remember that using e.g. an X-complete problem for such an X as a basis for a cryptosystem means that decryption even with a key is going to be a hard problem.

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

[nickco3]

perhaps we shouldn't speak of what quantum computing makes possible until quantum computing is itself feasible? people seem to make it out to be more than it is.

So that would be now then?

SAN JOSE, Calif., December 19, 2001 - Scientists at IBM's Almaden Research Center have performed the world's most complicated quantum-computer calculation to date. They caused a billion-billion custom-designed molecules in a test tube to become a seven-qubit quantum computer that solved a simple version of the mathematical problem at the heart of many of today's data-security cryptographic systems.

http://researchweb.watson.ibm.com/resources/news /2 0011219_quantum.shtml

Or perhaps by feasible you mean available on the mass market? How would we know which shops were offering the best deal if we didn't speak about it?

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

[GrandMJ]

Actually cryptography will die when the person before the last person dies. Only if you want to hide something from someone else, you would encript it. If there is nobody else, there is no need to encode information. ;-)

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

[Anonymous Coward]

dead link

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

[amorsen]

Factorization is not an NP complete problem, a solution to the travelling salesman problem will not solve factorization.

That is the wrong way around. If you solve travelling salesman, you have solved factorization. On the other hand, if you solve factorization, you have not necessarily solved travelling salesman.

[BTW the gender is intentional, the reason the salesman is visiting the cities in the first place is he has a mistress in each town]

No wonder it is difficult for large N.

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

[starrsoft]

You RTFA? You must be new here...

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

[swillden]

Be careful: NP \ P != NP-complete.

Right, which is why when the other poster said maybe I was thinking of NP-complete, I responded by saying I was thinking of NP \ P.

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

[bobbozzo]

So, where do you store the pads if you want to keep the encrypted messages??

Thats why I said OTP isn't really secure. (In practice. I know it's secure in theory.)

What do you do if you want to keep your laptop hard drive encrypted with OTP?
You'd have to carry around the OTP on a DVD, and then what do you do when you update a file on the HD? You need a new OTP for the whole drive. Or you need a OTP for each file on the HD each time the file changes!

And if you get arrested, the spooks will find the DVD with the pad(s).

Also note that Quantum-generated OTPs won't solve any of these problems. It only would solve the key-exchange problem.

OTP is a LOT less practical for general use than people here seem to think.

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

[jovlinger]

nope. Symmetric key cryptography relies completely on P != NP.

The easy definition of NP is the set of problems, which given a candidate solution, it is easy (P) to decide whether the solution is correct.

Given a known ciphertext and key, I can easily see whether the key decrypts the ciphertext. Thus, symmetric key encryption is in NP.

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

[Tellalian]

In case you don't know why this is a question the reason is that there is no year 0. Thus the second decennium began year 11 and so forth which leads to the conclusion that the second milennium began year 2001.

Not quite. Think about this for a second. When you were born, you were 0 years old, going through your first year. When you became 1 that means you had completed your first year of life, and were now going through your second year. When you turned 10, you had covered 10 years of life. Consequentially, if you lived to turn 2000, you'd have covered 2000 years of life. Thus the proper year to celebrate the new millenium was indeed in 2000.

So yes, there can be a "zero" year, of sorts, although that's a crude way to conceptualize it. The point is that the year doesn't mark where your at, but what you've covered. This is the same reason we say we're in the 21st century even though the year is now in the 2000s.

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

[mekkab]

If the Julian calendar was (and is) right then it's August 20th today instead of september 2nd

Sweet! My credit card payment isn't late afterall!

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

[nachoboy]

So, where do you store the pads if you want to keep the encrypted messages??

The same place you keep all your secret keys. Locked up in a secure place. Secrecy requirements for keys are hardly unique to one-time pads.

Thats why I said OTP isn't really secure. (In practice. I know it's secure in theory.)

It's still, when used properly, 100% secure in practice.

Cryptography, when it comes down to it, is simply a matter of exchanging big secrets for smaller ones. The amount of security you desire can be viewed as a trade-off.

One time pads: large key size (equal to the size of the data you wish to protect) but truly impenetrable security.
Public/private key-based systems: greatly reduced key size but may be vulnerable to brute force or other forms of analysis.

And if you get arrested, the spooks will find the DVD with the pad(s).

I'm not sure why a one-time pad will be more vulnerable than your private key. Either way, if the spooks get your keys, the jig is up.

(Note: if your counter-argument here is the "size" of the keys relative to the pads, I have a 1 GB flash memory card here roughly the size of a postage stamp. And this is consumer-grade equipment. Governments and multi-national organizations most certainly have access to technology orders of magnitude greater.)

OTP is a LOT less practical for general use than people here seem to think.

I'm not arguing the relative practicality of one-time pads. Yes, it's cumbersome. We all know that. That's why it's only used in situations requiring the utmost security (typically international diplomatic matters, nuclear warfare administration, etc.).

Your earlier statements regarding using "commonly available documents, images, binaries, whatever as the pad" indicate you do not have even the most basic understanding of cryptographic theory. Try chapter 1 of any cryptography text.

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

[Anonymous Coward]

I always hated discussing this problem.

I believe that the "holy rollers" like to call year 0 "the year of the lord." Which is a little BS, since Jesus of Nazareth more than likely lived more than one year. And if you did a little research, you'd find that A.D. isn't "After Death" but "anno Domini." Which loosly translated means in the Christian era.... which is also funny because Jesus of Nazareth was supposidly born in AD 200.

Since there was little correction of the julian calendar were often not done... let alone correctly, it's easly to say that we should be lucky if our calendar is only off by 5 years or less.

I for one would love to thank Zeno's Paradox for helping westerner's believe in the number 0 - which is in the root of this entire conversation.

- Cephus

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

[zakharin]

I don't know who's going to read this 5 days later, but this is not true. When you're year old, which year is it now, counting from your birth? It's the second year. Thus when you are 2000, you begin the 2001st year, so you turn 2000 t the end of the 2000th year and it is now year 2001.

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

[Tellalian]

I don't know who's going to read this 5 days later, but this is not true. When you're year old, which year is it now, counting from your birth? It's the second year. Thus when you are 2000, you begin the 2001st year, so you turn 2000 t the end of the 2000th year and it is now year 2001.

It is true, and you've just agreed with me (at least I think so; your grammar is somewhat confusing). Saying "I'm one year old" means you've completed one year of life. Period. It's pretty simple.

This also means you would currently be "traveling" through your second year of life. You're not actually 2 years old, but you're working on it. But like I said, the date we write down only indicates what time we've already traveled. So saying it's the year 2000, means 2000 years have happened and that you would currently be working through the 2001st year. Like I said, this is the same reason why we call this the 21st century even though we only write 2004.

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

[cbiltcliffe]

There's a big difference here, though.
When you're talking about birthdays, you're talking about the point in between your first and second year.
The year 2000, however, is 365.25 days long.
When a kid celebrates his first birthday, it's at the end of his first year. When all those idiots celebrated the new millennium at the beginning of the year 2000, it was just that....the beginning of the year.
Saying it's the year 2000 doesn't mean 2000 years have already happened. It means you're working on your 2000th year.
In the year 1, there hadn't been a full year yet, but it's still called 1. You celebrate that first year at the end, not at the beginning.

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

[Tellalian]

In the year 1, there hadn't been a full year yet, but it's still called 1.

Actually, you're right about this. After some research, I now see the error in my logic. The confusion lies in the difference between the ordinal and cardinal counting systems. Unlike most modern cardinal systems we use for measuring time and distance, which count by measuring a "quantity traveled" (i.e. they start at 0), the Gregorian calendar starts counting at 1. So 2001 is indeed the first year of the new millenium. Otherwise, my logic is sound. Oh well. At least I was only off by 1 ;)

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

[Anonymous Coward]

Actually cryptography will die when then 'third to the last' human draws its last breath.

Who needs it?

[romper]

Guvf jbexf whfg svar sbe zr!

Re:Who needs it?

[Anonymous Coward]

How is this offtopic? I smell an idiot.

Re:Who needs it?

[Anonymous Coward]

That's not encrypted. That's in German!

w00t

Re:Who needs it?

[romper]

Guess they've never seen ROT13 before. =)

Re:Who needs it?

[Lispy]

Es ist nicht auf deutsch. Soviel ist sicher.

Re:Who needs it?

[iabervon]

Fbzrubj V pna'g unir zhpu pbasvqnapr va n grpuavdhr juvpu crbcyr nccyl va gurve urnqf. Be vf gung whfg zr?

Re:Who needs it?

[iabervon]

The moderators couldn't find "Shaal"?

Re:Who needs it?

[rock_climbing_guy]

eythei evernei illwei ackkrei aimei odekay!!!

Re:Who needs it?

[Anonymous Coward]

Sernx!

Re:Who needs it?

[Lev13than]

Guvf jbexf whfg svar sbe zr! Bu pbzr ba, lbh pna qb orggre guna gung!

Re:Who needs it?

[Anonymous Coward]

you fail it!

Re:Who needs it?

[Anonymous Coward]

its all greek to me.

Re:Who needs it?

[thebitch]

Recht hat er!
Ab heute wird zurueck geschossen!
greetings

Re:Who needs it?

[oxygene2k2]

too many characters >v for that, I'd guess it's some eastern european language

Re:Who needs it?

[discovercomics]

Nah those wors are too short to be German, Maybe its Wynandott

Re:Who needs it?

[spellraiser]

Nu lbh frr, gur gevpm vf gb abg gryy nalbar jung zrgubq lbh ner hfvac. Jbemf rirel gvzr. :P

Kl gur jnl, lbh fcryyrq 'pbasvqrapr' vapbeerpgyl.

Re:Who needs it?

[UserGoogol]

Ubbintubberubbestubbing fubborm ubbof Pubbig Lubbatubbin. Thubby stubbaile ubbof ubbuzubbing "ubbei" ubbinstubbead ubbof "ubbay" ubbiz nubbete.

Re:Who needs it?

[Anonymous Coward]

Alright boys, break's over. Lucas needs you back on set pronto... And if any one sees Jar Jar, tell him that the studio is NOT going to pay for the damage to the concession cart.

Re:Who needs it?

[Anonymous Coward]

Nah, not enough/right sort of distribution of vowels.

(I live in a place with a lot of names being old wyandott, delaware, and cherokee words. I live near the "River of Evil Spirits". =))

Re:Who needs it?

[iabervon]

V svaq gung guvf fbeg bs grkg whfg whzcf bhg ng zr. Pyrneyl V'ir ernq gbb znal fcbvyref ba erp.tnzrf.ebthryvxr.argunpx bire gur lrnef. Zl oenva fubhgf "Ybbx! Nqivpr!"

Ba gur bgure unaq, zl fcryypurpxre trgf bqqyl haunccl...

Re:Who needs it?

[Anonymous Coward]

How about NEW German jokes? Sorry, as a German I'm really bored by that old, ever repeating stuff from Adolf & Co.

Here I have a very sublime German PR text (maybe its a good cypher as well):

"Lieber Katzenfreund, heute ist ein ganz besonderer Tag. Denn mit der von ihnen angeforderten Probepackung der neuen KmPstr-Produkte geht der geheimste Wunsch Ihres kleinen Feinschmeckers in Erfüllung. Der Wunsch nach einem einzigartigen Hochgenuss, den es so noch nie gegeben hat. Darauf hat Ihre Katze lange gewartet: cremiger Genuss von Joghurt und Frischkäse. Zubereitet mit reinen, natürlichen Zutaten. Veredelt durch neue, köstliche Rezepturen und ausgewählte Stückchen von Pute, Kalb und Lachs. Ganz nach den Bedürfnissen und dem Geschmack Ihrer kleinen Samtpfote. Für die verwöhnenden Momente zwischendurch. Erfüllen Sie die geheimsten Wünsche Ihrer kleinen Samtpfote doch ruhig öfter - mit den drei verführerischen Geschmacksrichtungen der neuen KmPstr. Mit Sicherheit wird sie diesen einzigartig cremigen Genuss lieben. Wir wünschen Ihnen und Ihrer Katze alles Gute."

Hint: Its all about cat food

Re:Who needs it?

[jimi the hippie]

Wyandotte in the hizzous!! :-P

Sound of Silence

[MikeMacK]

Simson Garfinkel

Is he related to Simon & Garfunkel?

Re:Sound of Silence

[baylanger]

In other words, cryptography is dust in the air?

Re:Sound of Silence

[Anonymous Coward]

Apt title for your joke.

Re:Sound of Silence

[MikeMacK]

No, your're thinking of Kansas - Dust in the Wind.

Re:Sound of Silence

[jejones]

As one would say to Mycroft in The Moon is a Harsh Mistress, that's a "funny only once" joke...and the "once" was probably decades ago.

Re:Sound of Silence

[MikeMacK]

Yeah, I did an apt-get title - gotta love that Debian.

Re:Sound of Silence

[dr_dank]

Cecilia, you're breaking my cipher...

Re:Sound of Silence

[Max von H.]

Is he related to Simon & Garfunkel?

No, but his parents obviously thought he did ;)

Re:Sound of Silence

[MikeMacK]

Yeah, I much prefer Heinlein reference humor.

Re:Sound of Silence

[Anonymous Coward]

Man you don't stop, do you?

I heard a good one earlier, actually.

"I want turtle soup... and make it snappy!"

Re:Sound of Silence

[Anonymous Coward]

From now on, any stories that mention Simson Garfinkel should carry a note saying that the joke's been done. Any attempt to post it again will result in you only being able to make the sound of silence.

Re:Sound of Silence

[Anonymous Coward]

Is he related to Simon & Garfunkel?

*** sound of Mt. Dew going through my nose *** BWAAAHHAAAHHAAAHAAH! That is PRICELESS! You, Sir, are a COMEDIC GENIUS! The next CARSON! Have you ever tried stand up? *** /me literally rolls on the floor, in pain from the laughing *** Please, next time, give us some warning so we don't choke on our food from your rapier-like wit!

A modern day classic, that post! Will Rogers had NOTHING on you, Sir! Thank you! You made my day!

Re:Sound of Silence

[MikeMacK]

One tries. Hope you didn't hurt yourself - geez, Mt. Dew through the nose - that's gotta burn.

First time I read...

[gracenix]

thought it said Simon n Garfunkel

Re:First time I read...

[Anonymous Coward]

The mods aren't punishing him with a redundant claim, they are moderating the discussion so it is more useful to the average reader.

The truth is, it is a redundant comment.

Didn't that guy...

[Skiron]

... write 'Bridge over encrypted waters ~(__8-(0) Doh!'?

Re:Didn't that guy...

[Anubis350]

or "Patterns", wait.....

Re:Didn't that guy...

[Anonymous Coward]

Didn't that guy...
... write 'Bridge over encrypted waters

Geeez, I hate when people write half their message in the Subject, and half in the Body.

YES! I AGREE!!!! speak in whole sentences!

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.

Re:Easy killer...

[Christopher Thomas]

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.

Re:Easy killer...

[wraithgar]

>we aren't really much closer to solving it than 10 or 20 years ago.

That's a prediction in and of itself. If the solution was even 100 years off, we'd be measurably closer (~20% closer) to the solution via timeline alone. If we truly aren't really much closer to solving it than 10 or 20 years ago, that would mean the solution is tens of thousands of years off.

/not an opinion, just an observation

Re:Easy killer...

[Anonymous Coward]

the machines have been invented - they just haven't been built yet

Also, it hasn't been proved that it is possible to build such a machine yet. It may well be physically impossible to build a quantum computer of a useful size.

Re:Easy killer...

[Christopher Thomas]

Also, it hasn't been proved that it is possible to build such a machine yet. It may well be physically impossible to build a quantum computer of a useful size.

I'm placing my money on the "possible" side. There are plenty of engineering challenges, but no fundamental physics reasons it can't be done, and regular announcements of new techniques for overcoming the engineering problems. This is the hallmark of most new technologies, so I expect quantum computing to get very interesting as the engineering aspects begin to mature.

Re:Easy killer...

[Urkki]

• 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.

So, how many bits (or digits or whatever) long numbers can we currently factor with quantum computers? My impression is that the answer is 'zero', ie we have no working quantum computer that can actually perform any kind of factoring. And this means there can be any number of practical problems we don't even know about yet. So trying to guess when we actually have quantum computers that do something is like trying to guess when Duke Nukem Forever comes out...

But please correct me if I'm wrong, 'cos I'd be delighted to be wrong here... And preferably provide a link to a page reporting that an actual quantum computer was used to factor a number of any size, or solve some other practical problem with real data.

Re:Easy killer...

[bobbozzo]

4-qbit q computers have already been built (as of 2002).
(They can factor a 4-bit number.)

Not very useful, but a great demonstration.

These claims were presented by a Physics prof at DefCon 10.
http://www.defcon.org/html/defcon-10/defcon-10-spe akers.html#walterdaugherity

And, According to /., IBM built a 5-qbit computer in 2000.

Re:Easy killer...

[Overzeetop]

"Qubit? What's a Qubit?"
.
.
.
"How long can you tread water?"

(sorry, BC just hit me, and I had to share it with the group. Yes, its cubit, and it's 45.72cm according to google, but _I_ thought it was funny)

Mandatory

[jchawk]

Maybe it's mandatory that the guys writing these articles take an intro to computer science class before writing these pieces...

Although someone I'm sure will counter with me that maybe I should have RTFA. :-P

Re:Mandatory

[TheFlyingGoat]

He's actually a pretty smart guy. Has written a lot of tech
books. Didn't RTFA myself, but normally he's pretty accurate.

Re:Mandatory

[That's Unpossible!]

Well, since he's a graduate student at MIT, I'll wager he has.

"Garfinkel holds three degrees from the Massachusetts Institute of Technology and a masters of science degree from Columbia University. He is a member of the Association for Computing Machinery (ACM), Computer Professionals for Social Responsibility (CPSR), and has a certification in computer security (CISSP) from International Information Systems Security Certifications Consortium."

Re:Mandatory

[mec]

Actually, the article's not all that bad.

Two problems: in his explanation of "P", the author says that P-time algorithms consume an amount of time proportional to the input size. That's way incomplete. P-time problems consume time proportional to some polynomial function of the input size, such as O(n^2), O(n^3), O(n^100), in addition to just plain O(n).

The second problem is where the author states that fast solutions to NP-complete problems would open up vulnerabilities to "hackers and viruses". Well, I'm not up on the latest virus developments, but AFAIK most viruses exploit known vulnerabilities rather than trying to crack algorithmically hard problems. Maybe there's some subtle way a virus could use a powerful P-time factorizer, but I think the author really just stated "hackers and viruses" because it sounded nice.

The article's also incomplete, as other posters have pointed out, because plenty of P-time algorithms are useless for real attacks. If your algorithm takes (1000 years) * (n^1000), where "n" is the key length, that is polynomial time, but it's still too damn long.

I've seen much worse in the trade press.

Re:Mandatory

[julesh]

Well, I'm not up on the latest virus developments, but AFAIK most viruses exploit known vulnerabilities rather than trying to crack algorithmically hard problems. Maybe there's some subtle way a virus could use a powerful P-time factorizer, but I think the author really just stated "hackers and viruses" because it sounded nice.

Neither am I, but if you asked me to hazard a guess, I would probably say that investigating the code of an operating system in order to find security flaws with it is an NP problem. Being able to do this automatically in a reasonable time frame would assist virus writers. It would also, of course, assist operating system designers.

Eventually

[StevenHenderson]

I think that eventually we will reach near-perfect, if not perfect encryption algorithms. Pardon my "n00b"-ness, but I am basing my limited knowledge off of Digital Fortress by Dan Brown, but an algorithm such as that - if you cannot comprehend it being created, you cannot think of it being cracked.

Re:Eventually

[ChipMonk]

"Anyone can think of an encryption algorithm that he cannot crack." I forget who said it, though (Ed Felten?). It came up during the SHA-0 discussion here on /.

Re:Eventually

[savagedome]

You are thinking of One time pads

The only encryption theoretically unbreakable.

Re:Eventually

[Control Group]

I don't know if he was first to say it, but I first saw it said in Schneier's Applied Cryptography.

Re:Eventually

[chill]

Digital Fortress was a complete piece of shit. Please don't base anything off that rag. It was written with the express purpose of capitalizing off of Dan Brown's momentum being made into a movie. The "visuals" described fit Hollywood nicely -- meaning they have no basis in reality.

It is easy for a person to come up with an algorithm that THEY can't crack. Most are painfully obvious to outsiders with any experience.

Other than proper implementation of a one-time pad, you'll probably find any encryption will eventually fall.

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:Eventually

[caluml]

From your sig: --I have gmail invites to give away!

Don't you know enough people without advertising your invites to anonymous web people? :)

Re:Eventually

[caluml]

It's a shame that whoever wrote this is posting as an AC, at score 0. (And that I'm unable to use my mod points, as I posted a meaningless comment earlier).

Woever wrote this, sign up, get an account, and use it to inform the Slashdot masses.

Re:Eventually

[Anonymous Coward]

No. The sort of dork who's interested in GMail is the sort of pathetic dork who will never have friends.

Re:Eventually

[Coryoth]

Mod the parent up please. Dan Brown is probably the most clueless person writing about encryption I have ever encountered.

As for chained encryption: In the end there's only so much shuffling of bits you can do before your algorithm isn't making any improvements to randomness of the output. If there's an exploitable hole in the algorithm (which is a given for being able to break any symmetric algorithm of significatn key size) then further rounds don't necessarily represent any significant extra difficulty. Check up on why 2DES is never used if you're curious - it effectively provides NO extra security.

Jedidiah.

Re:Eventually

[StevenHenderson]

Not when they have given me over 30 in the last week and 20 or so before then. I have been in the beta since the beginning...

Re:Eventually

[Minna Kirai]

but I am basing my limited knowledge off of Digital Fortress by Dan Brown

If you want to actually learn something about codes from an adventure novel, try Cryptonomicon. (Warning- 1000 pages)

The premise for Digital Fortress was completely backwards from reality. It suggested that today the NSA can break any code, and that chaos would result if a breakthrough changed that. But actually, any competent code is unbreakable already, even to the biggest government supercomputer- and if that changed, we'd see a good bit of rioting in the streets.

Re:Eventually

[DrHyde]

The ONLY perfect encryption is a one-time-pad. If there is a key it can be broken.

The one-time pad *is* a key, and the encryption algorithm usually used is XOR or a caesar-style rotate.

Re:Eventually

[StevenHenderson]

Thanks for the tip. I have heard many good things about the book you recommend so maybe I will check that out. Seems that I was a m0r0n for thinking that a DB book could have a good fact base. :)

Welcome to third year comp-sci

[ShieldWolf]

Is this what slashdot has come to: P vs. NP arguments/explanations?

If I was a subscriber I would be bitter with what is happening to this site, as it is I am just saddened. :|

Re:Welcome to third year comp-sci

[Anonymous Coward]

2nd year, where I come from ;)

Re:Welcome to third year comp-sci

[ShieldWolf]

Depends whether you are doing an honours or not. ;)

I also meant when you do the actual analysis of P, NP and NP-Complete etc., not when you FIRST look at the these two classes.

Re:Welcome to third year comp-sci

[Anonymous Coward]

Troll? Funniest thing here for a while. And 3rd year comp-sci? 1st year 'round our way...

Get /. back to what it should be. After all there must be a(nother) million ways to suggest Microsoft=evil, OSS=good. (Personally I'm still waiting for the day that "Microsoft employee saves drowning orphan" gets reported here. This will still be interpreted that MS is an evil monopoly and Open Office is better than MS Office and Windows is fundamentally flawed.)

Re:Welcome to third year comp-sci

[Anonymous Coward]

First year - where I teach it >;)

More than Just P=NP

[SparafucileMan]

"For more than 30 years, mathematicians have sought in vain the answer to a simple problem in theoretical computer science. The problem is what's known as an open question --it's a simple equation that is either true or false. It can't be both."

Which is not exactly true. It could be true but not provable. It could be false but not provable. It could be provably true, or provably false. Or, it could be neither true nor false.

Re:More than Just P=NP

[Iamthewalrus]

No it couldn't. Either P=NP or P!=NP. There's no "neither" option allowed.

Re:More than Just P=NP

[sploo22]

Well, it could be proven to be theoretically undecidable like the halting problem, couldn't it? Then I guess it would be true or false, but nobody would ever know so it's all semantics.

Re:More than Just P=NP

[Anonymous Coward]

If you've taken a CS Theory class in college, retake it and listen this time.

If you've never taken a CS Theory, take one and shut up.

Re:More than Just P=NP

[sploo22]

You know, it would be a lot more helpful if you pointed out what I said that was incorrect, instead of just insulting me.

Re:More than Just P=NP

[Welpa]

It's really sad how many people keep bringing up this "well, it could be undecidable" line.

Firstly, the halting problem is trivially decidable for any particular program, the program either halts or it doesn't. There is no mystery here, it is just impossible to write a program that will *check* whether an *arbitrary* program will halt or not. There is no magical program that will do both or neither, this is because programs halt or they do not. The undecidability of the halting problem demonstrates the limitations of computers, not the limitations of mathematicians.

Similarly, it's trivially decidable whether a particular program is in P or NP. It's either true or false.

Returning back to the topic P=NP is either true or false. It's a matter of set equality:

1) Let P denote the set of all programs in P
2) Len NP denote the set of all programs in NP
3) compare the two sets, there are only two possible outcomes, since P is in NP
a) there is a program in NP which is not in P, then P is not equal to NP
b) there isn't, then P=NP

It's as simple as that. And when I say program, I mean program: that means you can choose whichever formalism you want, as long as it's turing complete: this includes C, Java, Perl and whatever else you want.

Unfortunately, this fallacy persists because people just do not understand Godel. I even read a book about the Riemann Hypothesis recently where some serious mathematicians were quoted as saying that the Hypothesis could be undecidable... bullshit.

Re:More than Just P=NP

[TheUz]

"a simple problem in theoretical computer science."

"Which is not exactly true. It could be true but not provable. It could be false but not provable. It could be provably true, or provably false. Or, it could be neither true nor false."

Context. In computer science, all objects may have only one of two states. zero or one. on or off.
Now, whether zero maps to true or zero maps to false, *that's* an open question. = )

Re:More than Just P=NP

[twbecker]

Which is not exactly true. It could be true but not provable. It could be false but not provable. It could be provably true, or provably false. Or, it could be neither true nor false.

I was with you until the last possibility. Just because we may never know the answer does not mean that there isn't an answer. It IS either true or false, even though we may never discover which.

Re:More than Just P=NP

[gweihir]

No it couldn't. Either P=NP or P!=NP. There's no "neither" option allowed.

Correct, but there is a twist: It may be impossible to prove either (impossible in the mathematical sense), even when one of the two is clearly true. (See Gödels incompleteness theorem)

And it may also be impossible to prove that there is no proof for either.

Recurse as desired ;-)

Re:More than Just P=NP

[ksorim]

The continuum hypothesis is undecidable in certain versions of set theory. Why couldn't the Riemann hypothesis be undecidable too?

My understanding of Gödel is that in any sufficiently strong system of axioms there will always be statements that are neither provable nor disprovable. That is: there is a statement S such that S isn't provable and the negation of S isn't provable.

Is my understanding of Gödel wrong?

Re:More than Just P=NP

[AJWM]

Firstly, the halting problem is trivially decidable for any particular program, the program either halts or it doesn't.

Okay, suppose you're given a program that computes successive digits of, say, pi. Trivially we can say that it won't halt (not counting physical or architectural limitations of the computer), by definition.

Suppose we now add a test wherein the program halts if it detects a particular sequence of digits. Will it halt or not?

Show the trivial method by which you decide your answer.

Re:More than Just P=NP

[PaulBu]

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.

Re:More than Just P=NP

[Welpa]

Decidability means: there exists a program which decides this problem.

Consider program A: "ignore input, write YES" and program B: "ignore input, write NO". One of these programs decides whether your program halts. I don't have to tell you which one, and indeed it may be difficult to say which one, but the problem is *trivially* decidable.

Re:More than Just P=NP

[Abcd1234]

Umm... correct me if I'm wrong, but the statement "the hypothesis could be undecidable" could be translated to "there is no way to generate a procedure which can determine if an arbitrary problem in P is, in fact, in NP", just as there is "no procedure which can determine if an arbitrary program halts". ie, the problem really can be "undecidable".

Re:More than Just P=NP

[Anonymous Coward]

Let's go paragraph by paragraph.

A lot of top theorists bring up the "it could be undecidable" line - and a lot of them also say "but there's no good reason to think so."

Yes, the halting problem is trivially decidable for any particular program, if you have an infinite amount of time to wait. ... But this is not an algorithm for deciding whether ANY program halts, because it is not guaranteed to terminate in finite time.

Programs are neither in P nor NP. PROBLEMS are in P or NP. Even making this correction, you're still stuck with bruteforce: trying an infinite number of polynomial-time solutions to a problem to "trivially decide" if it's in P.

"Let P denote the set of all programs in P" is self-referential and meaningless. Ditto for "NP". I agree with your conclusion (3), but (yet again) there is no guarantee that your method will ever halt.

There is nothing simple about infinite-time "algorithms".

Do you have a good mathematical reason to believe that RH is decidable? Or are you just high on a Logical Positivist emotion?

**And the most important question, which you left unposed, Did I just fall for a ridiculously perserve Troll?**

Re:More than Just P=NP

[Welpa]

Is my understanding of Gödel wrong?

Bluntly, yes. The continuum hypothesis is independent of the axioms of standard set theory. This means that there exist set theories where the continuum hypothesis is true and there exist set theories where it is false.

On the other hand, the Riemann hypothesis is a particular question about a precisely stated function on the precisely defined set of complex numbers. There is only one such function and only one such set of complex numbers, no matter which set theory you are talking about. The hypothesis is either true or false: there either exists a zero not on the strip or there doesn't. There is no third option.

Re:More than Just P=NP

[Anonymous Coward]

You're beside the point.
You just don't understand what decidability means.
Following your argument, for every proposition P, either P is true or P is false. So every proposition P is decidable.
That's not how it works. There are cases is reasoning where you cannot decide which side you're in. And then you have to add to your theory "P is true" or "P is false" (but not both, or your theory is trivially absurd), or complete the set of axioms so that the proposition becomes decidable.

I guess the mathematicians were right :)

Re:More than Just P=NP

[alunharford]

So who says we're limited to BINARY computers?

Re:More than Just P=NP

[Anonymous Coward]

"Firstly, the halting problem is trivially decidable for any particular program, the program either halts or it doesn't."

What you wrote is technically correct however the use of the word "decidable" may be confusing: The predicate decidable to languages (in this context, think of sets of programs) - if there exists a program that for any given program can decide if it is in the set (in this case, the set of halting programs) then this language is decidable. One would usually not use the word decidable about a specific instance/program. However, it is true that the language consisting of one particular program is always decidable because we can easily create a Turing-machine that recognizes this program. However, what I think you inteded to say is that each particular program must either halt or not.

The same (sort of) applies to the P / NP paragraph.

As for the Riemann hypothesis matters are a bit more complex because many people do not distinguish between models and formal proof systems. For a given proof system there may be many satisfying models however these models may be different in certain apsects. Theoretically, the Riemann hypothesis could be true in some models and false in other. In this case, we would not be able to prove either in the formal system. If on the other hand we are able to prove that its either true or false in the formal proof system, then this must be true in all satisfying models. If we are able to prove that its BOTH false and true then it just shows us the system is inconsistent, and this means no models satisfies the system.

Re:More than Just P=NP

[AJWM]

I don't have to tell you which one,

Yes you do. Otherwise you might just as well say "it is decided by the flip of this coin", without specifying whether heads or tails means it will halt.

Indeed, in the example I gave, the program will certainly halt on some target sequences ("14159" for example) but may or may not halt on others (a sequence of 67 "1"s? Unlikely but not provable.)

Program B is provably wrong in some but not all cases. Program A is not provably correct except in trivial cases (eg a single-digit sequence). Therefore the problem is not "decided" at all.

indeed it may be difficult to say which one,

That's hardly "trivial", then, is it?

Re:More than Just P=NP

[Anonymous Coward]

That's exactly the problem. You're confusing "there's no third option" (-principe du tiers exclu in french, i don't know in english) and the fact that a question is decidable.
I guess that won't be easy to admit for you, because some of your fundations will be shaken... Mathematics can have weaknesses, and it is a fact that in some theories, you cannot decide of certain fact. Even when the premices seem to be clear enough (guess what, they always are).

Re:More than Just P=NP

[Anonymous Coward]

What you wrote makes sense but on the other hand, why is it that if the Riemann hypothesis is, say, true in all set theories that there is no formal proof that it is true? In first-order-logic there's a completeness theorem (in fact by Gödel too) that states that if something is true in all models satisfying the system, it has a proof in the system. Note that the incompleteness theorems are also true in first-order-logic - the completeness and the incompleteness theorems are NOT negations of each other.
However, if what you are saying is true, it would imply that the theory in which the Riemann problem exists can't be done in first-order even with an infinite (but recursive) amount of axioms. Is this really so? I thought first-order-logic was quite rich.

Re:More than Just P=NP

[Welpa]

I never claimed that the P=NP problem is easy or trivial. In fact it is proving to be one of the hardest problems of mathematics. I just said that it is definitely not undecidable.

This means that either P=NP or not.

Do you have a good mathematical reason to believe that RH is decidable? Or are you just high on a Logical Positivist emotion?

Igonring the second question, I'll answer the first ;) Yes, it is definitely decidable. This is because the zeta function is a function on the complex numbers. Questions about the complex numbers are either true or false. There is either a zero which disproves the Riemann hypothesis, meaning that it is false, or there isn't, meaning that it is true. Of course, I'm not claiming that it is an easy problem, just decidable.

Re:More than Just P=NP

[Anonymous Coward]

I don't know much about computability, but couldn't it be independent of
the axioms, like the continuum hypothesis in set theory?

Re:More than Just P=NP

[Anonymous Coward]

No!

There could exist a set of complex numbers in which the Riemann Hypothesis is true, and a set of complex numbers in which it is false.

Re:More than Just P=NP

[Anonymous Coward]

You really have no fucking idea, do you?

Re:More than Just P=NP

[Welpa]

Godel's theorem is about formal systems of axioms. Axiom systems are for reasoning about particular models. It may well be that your particular axiom system is not powerful enough to prove the Riemann hypothesis in a model which includes the set of complex numbers. But the hypothesis is true or false, independent of the axioms -- the model is defined up to isomorphism and exists independently of axiom systems.

Re:More than Just P=NP

[Jerf]

Yes you do. Otherwise you might just as well say "it is decided by the flip of this coin", without specifying whether heads or tails means it will halt.

No he doesn't; Welpa explicitly said one program, and he is right in that case. The Halting Problem is that you can't create a program that does it in all cases. Any finite number of cases can be solved by a lookup table. Populating it may take some work in the real world but in the math world we can just assert its existance confidently.

Some people then take this to mean since computers are finite, the halting problem is not an issue in real life. These people miss that the lookup table will be exponentially larger then the machine the table works for, which means it is still a real problem, since the problem is always larger than the machine, for any size machine.

(I do think he was wrong about the Riemann hypothesis, though; it is possible that it is undecidable. You might have to take it as a axiom.)

Re:More than Just P=NP

[Anonymous Coward]

Let him dream, guys.
He's a troll.

Re:More than Just P=NP

[Welpa]

Look, surely you have to agree with me that any particular program halts or it doesn't. It certainly can't change it's mind halfway through. We are talking about deterministic programs and it is determined from the start whether a particular program will halt or not.

So let's get our definitions straight. The question: "does program x halt or not?" is always trivially decidable - meaning that either program A or program B decides it. Of course, figuring out which of these programs decides it may be hard, but that is a different question which has nothing to do with decidability.

Re:More than Just P=NP

[Welpa]

This is where we disagree. You see, there is only one set of complex numbers. It is defined up to isomorphism, let's say by Dedekind cuts. There is only one zeta function. The hypothesis is true or false.

Of course, there could be many axiom systems for reasoning about the complex numbers. And you could, conceivably, change the definition of complex numbers to something more general; but then what you have is not the Riemann hypothesis anymore and I grant you that it may turn out that whatever that is, it may be independent of some set of axioms.

But the real Riemann hypothesis is either true or false, there is not other way around it.

Re:More than Just P=NP

[2short]

I'm not sure what you mean by "independent of the axioms", but the continuum hypothesis is in fact either true or false. However, it has been proved that if it is true, it cannot be proved to be true. It is possible it could be proved to be false, but noone really thinks it is, so not much work is being done there.

Re:More than Just P=NP

[pjt33]

I'm not the grandparent poster, but... The property of termination is undecidable, but the question "Is there a program which for any program P will determine whether or not P halts" is not undecidable: the answer is "No".

Re:More than Just P=NP

[42forty-two42]

Firstly, the halting problem is trivially decidable for any particular program, the program either halts or it doesn't. There is no mystery here, it is just impossible to write a program that will *check* whether an *arbitrary* program will halt or not. There is no magical program that will do both or neither, this is because programs halt or they do not. The undecidability of the halting problem demonstrates the limitations of computers, not the limitations of mathematicians.

And what about humans? There must be some program X such that the entire human race cannot evaluate whether X halts. Granted, most likely the human race cannot construct X either.

Re:More than Just P=NP

[lildogie]

> it's a simple equation that is either true or false. It can't be both.

Meet Goedel.

"This statement cannot be proven by any method of logic."

Re:More than Just P=NP

[Dr. Zowie]

No, er, actually, decidability is all about being able to determine, in advance, whether program 'A' or program 'B' is right for a particular set of inputs.

The whole point of the halting problem is that there are computational sequences of all lengths (including aleph-null) that are irreducible. You can't know the result of such an irreducible sequence unless you've run through a certain minimum number of logical steps. In some sense, you can't know the answer to an irreducible computing problem unless you've brute-forced the answer already.

Saying "of course it's decidable -- either program A or program B is the correct answer" is not legitimate. The whole point of the halting problem is that it's impossibly hard to decide which (of A or B) is the correct answer in all cases. There are a few cases for which you'd have to wait literally forever.

Of course, there's a very large class of computations that are in fact decidable. In a lot of cases, it's enough to say "this halts in less time than X" or "this doesn't halt in less time than X", for a finite value of X.

Re:More than Just P=NP

[bigg_nate]

On the other hand, the Riemann hypothesis is a particular question about a precisely stated function on the precisely defined set of complex numbers. There is only one such function and only one such set of complex numbers, no matter which set theory you are talking about.

I think you're confusing two possible definitions for "the set of complex numbers".

The first is mathematical -- we can call a set S a set of complex numbers if it satisfies certain axioms. With this definition, the set of complex numbers is precisely defined, but there may be many such sets. It may be the case that RH is true in some of these sets and false in others.

The other definition is more philisophical -- you could say that numbers are actual entities, and that there is an actual set of complex numbers that exists in some sense. But while this set is unique, it certainly isn't precisely defined.

Mathematicians use the first definition almost exclusively, because precise definitions are necessary in order to construct valid proofs. So I would say it is possible that RH is neither true nor false.

Re:More than Just P=NP

[Anonymous Coward]

What do you make of this then?
The continuum hypothesis, first proposed by Georg Cantor, Eric Weisstein's World of Biography holds that the cardinal number of the continuum is the same as that of Aleph-1. The surprising truth is that this proposition is undecidable, since neither it nor its converse contradicts the tenets of set theory.

Re:More than Just P=NP

[Welpa]

We've been talking about programs without inputs. Or if you like, a program P with a fixed input x, and the question is "does P halt on x?". This is trivially decidable, because either it does or it doesn't. But of course you are right, it is impossible to write a program which takes as its input a description of a program P and a description of an input x and decides whether P halts on x.

Re:More than Just P=NP

[Anonymous Coward]

You're saying that every problem is decidable, because in any case, either A or B answers your problem.

However, a problem is decidable if there exists an algorithms that answers _correctly_. Always answering yes (or no) is not a solution.

Let's take the halting problem. Let's say we have program 1, which halts, and program 2, which doesn't.

We apply both of them to program A, which answers yes every time. It's wrong on program 2, so it's no solution to the halting problem. Then we apply both of them to program B, which answers no every time. It's wrong on program 1, so it's no solution either.

A solution would be:
if (program halts) then use program A
else use program B

Which means that the halting problem is decidable if we can decide for any given program whether to use A or B, ie. whether to answer yes or no.

Re:More than Just P=NP

[Dr. Zowie]

Hmmm... Thanks for the "...of course you are right...", but, er, you just described the definition of decidability. If it's "impossible to write a [n algorithm] which takes as input a description of a program P and a description of an input x and decides whether P halts on x", then the question of whether P halts on x is not decidable.

See some of the definitions online...

Re:More than Just P=NP

[Anonymous Coward]

a program P with a fixed input x, and the question is "does P halt on x?". This is trivially decidable, because either it does or it doesn't.
Well, I suppose you have a (trivial) way to decide this whithout actually running P on x. If not, you're wrong, because you'll never know that P doesn't halt. Imagine P is running on input x. Wait a bit. Still running. Wait a bit. Still running. So far, it's running, so you might think it won't stop. But what if you waited juste a little bit more ? Maybe it would have stopped.

Re:More than Just P=NP

[TRACK-YOUR-POSITION]

Maybe undecideable is just the wrong word. If you take all number theory knowledge of human civilization--or all civilizations in our physical universe--and create an axiomatic proof system encompassing all of that, there are certainly going to be a lot of true statements that are not provable in that system, right? P!=NP and the Riemann hypothesis could be such statements, I suppose.

Re:More than Just P=NP

[Anonymous Coward]

Well,
before I start please excuse my bad English.

It can easily be proben that every recursivly enumerable problem (i.e. formal language) is partially decidable, i.e. undecidable unless proven otherwise.

The Hilbert's 10th problem has been proven to be undecidable.

Gödel on the other hand proved that there always are arithmetic formulas that are true but not proovable.

So there are of course undecidable and unproovabe problems.
Cheers.

Re:More than Just P=NP

[Welpa]

Just about any first-year university mathematics introductory textbook on calculus will define the real numbers using dedekind cuts or cauchy completions. These definitions are second-order logic statements and they provably define the set of real numbers up to isomorphism. Once you have the real numbers, you use one of two equivalent methods of obtaining the set complex numbers, which is again defined up to isomorphism.

Summing up, the complex numbers, like the natural numbers, are a well-defined entity, up-to isomorphism (renaming of the individual components). Thus, just as there is only one set of of natural numbers, there is only one set of complex numbers.

Re:More than Just P=NP

[abb3w]

Disclaimer: I am not a mathematician, so don't rely on this as advice when counting to ten.

Is my understanding of Gödel wrong?

Bluntly, yes.

Bluntly, no; it seems his understanding of the Reimann hypothesis is.

On the other hand, the Riemann hypothesis is a particular question about a precisely stated function on the precisely defined set of complex numbers. There is only one such function and only one such set of complex numbers, no matter which set theory you are talking about.

To be perhaps marginally more understandable, construction of the complex numbers requires the axioms for construction (and infinite inductive properties) of the Natural numbers, and axioms for construction of addition and multiplication. Complex powers require (briefly) the use of calculus, which merely requires adding axioms for how to take a limit into the mix.

The Reimann Zeta function of a complex number is the infinite sum of every integer when taken to the power of the additive inverse of the complex number being considered. The behaviors of this function (such as where it has zeros, as the Reimann hypothesis considers) are therefore only reliant on the axioms necessary for the above constructions. Proof of this is left as an exercise to the student. =)

The hypothesis is either true or false: there either exists a zero not on the strip or there doesn't. There is no third option.

...or at least, no third option as long as you work with the axioms describing what any normal mathematician considers the Complex Numbers. One may feel free to construct your own Complex/Real/Integer/Natural Numbers out of your own axioms and belly button lint if you will, but I doubt it will be more interesting than the belly button lint itself.

Of course, proving this degree of axiomatic dependence rigorously is more than I am able to do. This is also left as an exercise for....

Re:More than Just P=NP

[kap1]

Oof! Undecidable is not the same thing as not computable. Undecidable, to simplify, means that a statement has no truth value in a system of axioms, i.e. its positive or negative could be added as an axiom and the system would still be consistent.

Not computable, by contrast, means we can't write a program to compute correct results for all inputs. So, while every program either halts or it doesn't, we can't write a program that determines whether it does or it doesn't. The Halting Problem is thus decidable, i.e. the Theorem "The characteristic function for the set of all non-halting turing machines is computable" is false and thus has a truth value.

Whew. Still, all digital computers are actually FSA's, since they don't have an infinite tape, so the halting problem there is computable. :-)

Re:More than Just P=NP

[Anonymous Coward]

This is trivially decidable, because either it does or it doesn't.

No, either it does, or you're still waiting to find out.

Re:More than Just P=NP

[Sam Nitzberg]

Actually on the notion of ...
"More than Just P=NP"
I will mention that there are entire complexity classes harder than (or at the very least, believed harder than) NP.

These include EXPSPACE.
This is mentioned here:
http://www.demarcken.org/carl/papers/ITA-so ftware- travel-complexity/img24.html

I don't have my old texts with me here, but one of the texts by Papadimitriou has an excellent diagram of the relationship between complexity classes, and has a bunch "worse" than NP.

Of course, if you can prove things like P=NP, or similiarly break down barriers between the other complexity classes, there are big implications to the diagram......

Sam

Re:More than Just P=NP

[Dr. Zowie]

"Mathematicians use the first definition almost exclusively..."

Well, certainly. That just means that mathematicians know precisely the thing about which they are talking (the "complex numbers" has a very precise meaning, to someone who has followed the formal definition of the set). Since the Riemann hypothesis deals with functions defined on the set of complex numbers (and limits of functions), it is very precisely posed.

I will not go through the exercise of proving so here, but there really isn't any way to come up with more than one answer, without speaking of something other than the usual complex numbers.

You "...could say that numbers are actual entities, and that there is an actual set of complex numbers that exists in some sense ... [that] isn't precisely defined." -- but such a set would not be the "complex numbers" that are being described by mathematicians. It would be something else entirely.

Re:More than Just P=NP

[angst_ridden_hipster]

Just because we may never know the answer does not mean that there isn't an answer. It IS either true or false, even though we may never discover which.

Well, maybe. It could be that with deeper knowledge, the question is not meaningful. For example, I state that the Gostak distims the doshes. This is neither true nor false if the Gostak is nonexistant, distimming is actually fragonarding, and doshes are really just an observable side-effect of boradas nikto-ing a Klatuu.

That's probably not the best example, but it seems to me that there are questions that are in and of themselves not valid.

I suppose someone who actually knows something about logic can correct me here :)

Re:More than Just P=NP

[Dr. Zowie]

There you go with "undecidable".

That word. I do not think it means what you think it means.

Re:More than Just P=NP

[HiThere]

It's quite possible to have a postulate which is either true or false (your choice) depending on the interpretation that you apply to the rest of the system. One example of this is Euclid's parallel postulate. This was for a long time considered true, even though there appeared no way to prove it. But...

Eventually it was denied in two different ways, which lead to two different forms of non-Euclidean geometries. So both considering it to be true, and considering it to be false in two different ways all work to produce useful geometries.

I suppose that this isn't quite the same as saying it was neither true nor false, though.

Re:More than Just P=NP

[Hatta]

The undecidability of the halting problem demonstrates the limitations of computers, not the limitations of mathematicians.

What's the difference? The conscious mind is a computer, is it not?

Re:More than Just P=NP

[AJWM]

It certainly can't change it's mind halfway through.

Unless you know that it halts, how do you know when "halfway through" is? My example doesn't know itself when (if ever) it will halt until it does, so it can hardly "change its mind".

Of course, figuring out [i.e, deciding] which of these programs decides it may be hard, but that is a different question which has nothing to do with decidability.

No, it's the same question, you're just trying to push it back a step.

And I'm beginning to think I have been trolled.

Re:More than Just P=NP

[Anonymous Coward]

>Whew. Still, all digital computers are actually
>FSA's, since they don't have an infinite tape, so
>the halting problem there is computable. :-)

Not quite true. You must be thinking of the hard drive or the volatile memory store as the tape. I think you're forgetting the keyboard.

In _most_ modern computers, it's simply not possible to predict the outputs based on full knowledge of the computer's initial state, because of these damned "tape drives".

Re:More than Just P=NP

[tc]

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.

Re:More than Just P=NP

[Anonymous Coward]

Dismissing an argument as "all semantics" is ridiculous. Nothing is more important than the words we use to communicate; it is not merely trivial details.

Re:More than Just P=NP

[mesterha]

Which is not exactly true. It could be true but not provable. It could be false but not provable. It could be provably true, or provably false. Or, it could be neither true nor false.

How could it be true/false and not provable? What is truth if not a proof based on the rules of you system and the axioms. If no proof exists then by what standard do you claim the result is true. Now it could be neither true nor false. In this case, the system is incomplete and some statements are neither true or false.

Re:More than Just P=NP

[CoughDropAddict]

Oof! Undecidable is not the same thing as not computable. Undecidable, to simplify, means that a statement has no truth value in a system of axioms, i.e. its positive or negative could be added as an axiom and the system would still be consistent.

Wikipedia (see here and here) and my Theory of Computation textbook disagree with you.

From Theory of Computing -- a Gentle Introduction:

We will use the term decidable language as a synonym for Turing computable language.

Re:More than Just P=NP

[Anonymous Coward]

You're a fucking moron.

Re:More than Just P=NP

[tunah]

No, it can't be true but not provable.

If P=NP then there exists an algorithm for (say) 3-SAT that runs in polynomial time. Exhibiting such an algorithm would be a proof. It could, however, be false but not provable.

I'm not sure what you even mean by neither true nor false, P and NP are sets of problems. Sets are equal if they contain the same elements. Either there is a problem that is in NP that's not in P, or there isn't.

Re:More than Just P=NP

[tunah]

Well then that would make it false, wouldn't it? "Every nontrivial zero of zeta has real part 1/2"

Re:More than Just P=NP

[Piquan]

Firstly, the halting problem is trivially decidable for any particular program, the program either halts or it doesn't.

Excellent! Then let's trivially decide whether this program halts or not.

$n = 1;
start:
$i = $n;
%seen = ();
while ($i != 1) {
die "$n is not wondrous!\n" if $seen{$i};
$seen{$i} = 1;
$i = ($i % 2 == 0) ? $i/2 : 3*$i+1;
}
print "$n is wondrous.\n";
$n++;
goto start;

This was taken from "Godel Escher Bach", which discusses this sort of thing and related problems. It sounds like you might enjoy it.

Re:More than Just P=NP

[a_n_d_e_r_s]

Correct. The world as we know seams to be incomplete.

This can be because of two things
- either our understanding of the world are incomplete
- or the world is incomplete

Right now the first are what many think. However the second might be true too... we dont know ... yet.

Re:More than Just P=NP

[dkf]

The proof that the halting problem is undecidable comes about through constructing a program that says it halts only if it doesn't halt. This is trivially easy to do if you have a finite program that computes whether a program halts (exercise for the reader) so the only conclusion is that there cannot be any such finite program. This result is well-known; every so often some crackpot comes along and claims it is false, but that's usually just an indication that they were asleep in their CS logic class...

However, it is possible to prove that virtually all normal finite programs halt (or not). Horrendously non-trivial - trust me on that as someone who has worked on state-space enumeration engines and model checkers - but possible.

Infinite programs are more interesting; you tend to need exotic theoretical machinery to tackle that sort of thing...

Re:More than Just P=NP

[David Gould]

(-principe du tiers exclu in french, i don't know in english)

"Principle of the excluded middle" is what we called it in school -- basically an exact word-for-word translation between the English and the French, in this case.

There's always OTP

[ikewillis]

OTP will always remain a viable means of private key cryptography. When you interleave signal with noise, the result will always have the properties of noise.

Re:There's always OTP

[Soul-Burn666]

But has many drawbacks:
1. The length of the pad/key needs to be the same as the encrypted data.
2. It may be only used once, therefore the two sides need to meet to exchange pads, continuously.

If the sides to need to be in contact to agree on the pad, then the sides can pass the information already. If you pass the pad encrypted, you need a method of encrypting it, and you enter an endless loop.

Re:There's always OTP

[gweihir]

OTP will always remain a viable means of private key cryptography.

Theoretiocal OTP: yes.

However the existence of randomness in nature if a pure observation and may be an oversimplification. There is not much indication this may be so, but when I look at what quantum physicists currently believe, I am pretty much convinced we don't understand this universe yet.

Re:There's always OTP

[Wumpus]

It's a time shifting problem. It works when you have a secure channel right now, but you won't have it later. You transmit the key over the temporary secure channel (i.e. Alice hands the OTP to Bob over lunch) and then transmit the secured message when the secure channel isn't available (Bob encrypts and emails a message to Alice a week later).

You're right that it doesn't have as many useful applications as other cryptosystems in use today.

It's also very hard to produce good (secure) one time pads.

Re:There's always OTP

[Viking Coder]

You're absolutely right. Except for the "very hard" part.

It costs about a hundred bucks to buy a good (secure) random number generator. Noisy diodes, for instance, work great. Hell, taking photos of lava lamps works, too.

QRNG

SafeXcel

VIA C3 RNG

Re:There's always OTP

[DavidTC]

It also allows you to convert two 'mostly secure' channels into one rather secure channel.

For example, let's say you're sending data into a hostile country that's trying to steal data from you, but they don't want to make it obvious. And you know your lines are tapped.

So you mail one CD, containing the OTP, to a trusted address, and you carry one CD containing the encrypted data in physically.

It's possibly they could intercept the mail in transit and copy that, and they could come up with some excuse and have to 'examine' the CD in customs, but they'd have to do both to get the stuff. If you stagger them, for example carry it in first, you can then choose to only mail the CD if they didn't have a chance to copy it during customs.

And I don't want to get into the math, but you can keep 'splitting' the data as much as you want. You can even make situtations where you need four of five CDs to get the data, or one of a set of two CDs and three of a set of seven. And this isn't some insecure password situtation, they are true OTPs, where you cannot mathmatically reconstruct the data until you get enough CDs.

Re:There's always OTP

[SLOGEN]

Anyone who can guess what fluctuations in background radiation, or gieger count-intervals i used to generate my OTP is worthy of the predicate "GOD"

Re:There's always OTP

[Wumpus]

Yes, in theory. In theory, other cryptosystems are easy well understood, standard, and easy to put in security products, which is true to an extent, but there's still a lot implementors can do to misuse a cryptographically secure RNG. A famous example is how the Russians used some of their one time pads multiple times, making it possible for the Americans to crack their encryption.

Implementing OTP isn't harder than implementing any other cryptosystem, but it isn't easier, either, and relying on hardware solutions introduces yet another thing that could break (What happens if your lava lamp burns and the lava stops bubbling? Is your system still as secure? Chances are that you don't really know. I certainly don't.)

Re:There's always OTP

[Anonymous Coward]

$100? You're being charged for convenience.

Here's a hardware RNG that you can build with some spare parts: a couple of caps, couple of transistors, a few resistors, and a quad inverter.

Re:There's always OTP

[prockcore]

OTP will always remain a viable means of private key cryptography

OTP is not viable. The reason is that the pad has to be at least as long as the data you're encrypting. Both parties must have the pad. If you can deliver the pad securely to both parties.. you can deliver the data securely the exact same way.

In other words, the places where OTP would be secure are the exact same places where OTP is redundant.

Re:There's always OTP

[Viking Coder]

Well, I really, really think that you're wrong when you say that "OTP isn't harder... but it isn't easier, either."

I hardly know anything about cryptosystems, but I know for certain, as though my life depended on it, that I could develop a completely secure OTP-based communications channel with a second, trusted party. As long as the physical computers aren't compromised, the system would be secure.

Ha!

[chill]

For 90% of the public, ALL math problems more complex than 2+2 are hard!

Re:Ha!

[Anonymous Coward]

Because we all know 2 + 2 = 5.

Re:Ha!

[platinumflame]

87% of all statistics are made up on the spot...

Re:Ha!

[Anonymous Coward]

seems like you are the one whom has maths problems.. not *cough* "90% of the public".

Re:Ha!

[Anonymous Coward]

we all know 2 + 2 = 5

The preceding statement was brought to you by the Swift Boat Veterans for Math.

Re:Ha!

[DrSkwid]

yes, for sufficiently large values of 2

Re:Ha!

[kallisti]

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

Quantum Computers / Shor's Algorithm

[Anonymous Coward]

"Cryptography will die when the last human draws its breath."

Or a quantum computer is made that can break all these passwords.

From Wikipedia: http://en.wikipedia.org/wiki/Shor's_algorithm

Shor's algorithm is a quantum algorithm for factoring a number N in O((log N)3) time and O(log N) space, named after Peter Shor.

Many public key cryptosystems, such as RSA, will become obsolete if Shor's algorithm is ever implemented in a practical quantum computer.

Re:Quantum Computers / Shor's Algorithm

[wwest4]

> 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.

Re:Quantum Computers / Shor's Algorithm

[Tongo]

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 :)

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:Quantum Computers / Shor's Algorithm

[Anonymous Coward]

In theory. But I would then like to suggest that a codebreaker could feed a series of qubits into a quantum computer of the same length as the message, hit compute, and have a perfect decryption of the message dump out in one universe.

The ability to feed the correct message back from that universe to the rest of us may be a bit tricky, but could perhaps be done by having the individual in the lucky universe set all quanta to 0xFF in a bank of LEDs in a pattern representing the plaintext.

Re:Quantum Computers / Shor's Algorithm

[wwest4]

Agreed, on the grounds that the difference between P and NP is not the same as conventional vs. non-conventional computing... worth saying, since I think it might be quite natural to assume that there must be such a correlation.

Re:Quantum Computers / Shor's Algorithm

[Anonymous Coward]

A quantum computer trying to break a OTP is equivalent to choosing the right message from all possible messages with the same length. In other words: Without knowing the pad, tell me if "ghwf0oclw" decrypts to "Star Trek" or "Star Wars".

Re:Quantum Computers / Shor's Algorithm

[Anonymous Coward]

Yeah and 640KB should be enough for anybody.

Re:Quantum Computers / Shor's Algorithm

[IBitOBear]

I thought that all the public key (etc) systems relied on a "hard math problem" to produce the public-key secret-key pair. When I generate my DES and AES keys I go through that "mostly prime" exercise.

So quantum computing should be able to do the "large nubmer factoring" exercise necessary to crack the key...

Or I am full of shite... 8-)

Re:Quantum Computers / Shor's Algorithm

[swillden]

Thank you for making my point. Quantitative changes occur incrementally over time, like memory requirements. Qualitative changes, however, like the fundamental difference between quantum computers and Von Neumann computers, and the algorithms that can be executed on each, don't.

Re:Quantum Computers / Shor's Algorithm

[swillden]

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.

Re:Quantum Computers / Shor's Algorithm

[Anonymous Coward]

I'd tell you the answer, but that would cause the universe to split in two, one for each possibility. And I don't feel like putting up with that right now, since it's dinnertime.

Tell you what, though. I'll whisper the answer to my cat, and he'll meow when the right program comes on the TV.

-- Schroedinger

Re:Quantum Computers / Shor's Algorithm

[Hatta]

Those don't rely on hard math problems as much as on non-linearity and complexity.

What's the difference?

Re:Quantum Computers / Shor's Algorithm

[Eric119]

Some formatting was lost when you copied from Wikipedia. It's O((log N)^3) time, not O((log N)3) time.

Re:Quantum Computers / Shor's Algorithm

[swillden]

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.

Re:Quantum Computers / Shor's Algorithm

[bobbozzo]

So quantum computing should be able to do the "large nubmer factoring" exercise necessary to crack the key...

That's the idea, and as of last year, people have been able to build 4-qbit quantum computers that can instantly factor a 4-bit number.

Obviously that's not very useful as I can factor a 4-bit number in my head in about a second, but if larger q computers can be stabilized, then factoring larger numbers instantly will be possible.

Re:Quantum Computers / Shor's Algorithm

[HuguesT]

The question I'm always asking myself is: is creating an (n+1) qbit computer twice as hard (or harder) than creating a n qbit computer? If so really this QC approach is doomed.

Re:Quantum Computers / Shor's Algorithm

[bobbozzo]

I'm too tired to think right now, but IIRC the problem is that the atoms or molecules are hard to keep in the correct position(s).

So I'd guess it'd be an O(2^n) problem, but like I said, I can't think right now.

Re:Quantum Computers / Shor's Algorithm

[Anonymous Coward]

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.

Re:Quantum Computers / Shor's Algorithm

[God! Awful 2]

Or I am full of shite... 8-)

Yes, you are full of shite.

-a

Re:Quantum Computers / Shor's Algorithm

[bobbozzo]

Replace that 2 with another N if there the qbits can be in more than 2 possible positions.
e.g. if they can be in 4 positions, and only one will work, then it's O(4^n). I think.

Re:Quantum Computers / Shor's Algorithm

[HuguesT]

Let me see if I get this right: if it takes more than 18 months to upgrade n-qbit computers into (n+1)-qbit computers and if Moore's law holds, then we'll have a way of factoring 128-bit numbers faster via the conventional route quicker than via QC?

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

[jejones]

Could be argued, for that matter the entire concept of "random" is truly just a human thought construct.

You might want to read some of Chaitin's work, and then reconsider.

Re:Could be argued

[ShieldWolf]

Randomness is not a human construct, I am not sure where you are getting this idea from. There are certain events that are PROVABLY unpredictable, e.g. radioactive decay and certain quantum effects. To say that we don't know enough is disengenuous: based on our current models of time and space quantum effects HAVE to be random. If you want to throw out the accepted model of physics you better have a better explanation than we don't know enough yet.

Not everything has a pattern either, try finding the pattern of a .zip file and I have a perpetual motion machine I would like to sell you.

Re:Could be argued

[Christopher Thomas]

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.

Even in a purely classical universe, sensitivity to starting conditions makes things like coin tosses and die rolls impossible to predict if set up carefully. This is that whole "chaos" topic you may have heard about in the press in the 1980s. You'd have to have excruciatingly accurate knowledge of the state of everything in the past light-cone of the event you're trying to predict, as of the time of prediction, for it to work with perfect reliability.

In our quantum universe, the uncertainty principle makes it impossible even in principle to measure starting state to the required precision, for the schemes that are used for true random number generation in electronic systems. Additionally, if quantum processes are accepted as truly random, they inject enough noise to taint macroscopic events with true randomness if the consequences of the noise are given enough time to propagate.

In summary, true randomness exists as a very fundamental result of the laws of nature, and won't go away no matter how good our measurements get.

Re:Could be argued

[captnitro]

Mathematics is a 'human thought construct', man. The interesting part about it is that these ideas reliably correspond to real things. There's nothing inherent in the universe to say that three apples can't be described some other way, but mathematics describes it as '3' and if I add '2' more, I get '5'.

Realistically, I could argue "what constitutes an apple?" or "are these apples really '1' each?", but as far as mathematics goes, it's the ideals of the numbers matter.

"Random" isn't random when you're talking about coin tosses or roulette, just a very complex and physical "pseudo-random". "Random" is a mathematical ideal, just like "2" apples. While we can't generate truly random, we can get damn close, and certainly close enough to use. (Example: Via's C3 'Padlock' encryption engine takes electrical noise off the chip. Not truly random, but good enough to keep people from reading your e-mail.)

For that reason, when we're talking about one-time pads and the like, the proof of uncrackability has to do with the ideal, not the fact that we're getting our random data set from a monkey at the zoo. Obviously if your "random" data set was a monkey who sat on the "A" key for twenty minutes, that's a factor. But the ideal is what we're talking about, and if we can get close *enough*, we should be fine.

Re:Could be argued

[Hepkat]

I agree that "random" could be a human construct that doesn't actually happen, things just appear that way due to a the relavitely small sample set we are given....
but it also has little to do w/ the degree of predictability. Something could be entirely "random", or as "random" as we percieve it, but even in those cases we can still formulate the probability of the next value.
Probability does not prove or disprove randomness...

Re:Could be argued

[Abcd1234]

Dude, you are very wrong. The idea that "God does not throw dice" is directly contradicted by Quantum Mechanics (which is why Einstein rejected the theory, thus originating that quote) which necessarily requires the concept of "true randomness". Thus, in this case, Einstein was probably wrong, as another poster pointed out (things like radioactive decay being provably random).

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.

Re:Could be argued

[Anonymous Coward]

Randomness is not a human construct

You've obviously never heard Bush speak off the top of his head.

Re:Could be argued

[onyxruby]

I thought I made it clear enough that I wasn't trying to apply what I said to quantam states. Apparently not clear enough. That being said, I was simply leaving the door open to new science on the matter. I am familiar with Heisenbergs uncertainty principal. Outside of quantum physics, I truely believe it can be argued that everything can ulitmately be predicted to a certain point.

Too many times have people thought something was random only to later discover that it had a pattern as yet unknown.

Re:Could be argued

[gweihir]

Randomness is not a human construct, I am not sure where you are getting this idea from. There are certain events that are PROVABLY unpredictable, e.g. radioactive decay and certain quantum effects.

Wrong. Sorry. Physics cannot prove things. They can only show that things are very likely and they can have theories that predict things. Often this works, but from time to time it fails. All physical deductions relating to reality are derived from experiments. Experiments are allways imprecise and frequently deliver wrong results.

Ask any physicist. They know that they just have a best guess, but no hard facts.

Re:Could be argued

[onyxruby]

I agree that probability does not prove or disprove randomness. What I said was

anything can eventually be learned and predicted on some level

I was distinctly leaving open probability. With time and knowledge probability can be reduced to a known state.

Re:Could be argued

[DarkMan]

The problem is, however, that the random nature of quantised states exerts some influcence on macroscopic states. It's not very big. In fact, it's posivtly tiny (other wise the quantum nature of things would have explored sooner). Let me give an example.

Light has momentum. The solar sail is the most direct application of this.

Consider a coin toss. In the average place where it takes place, there is uneven illumination. That is, as the coin is spinning, there will be time where the illumination on one side is different to the other. So far this is still accontable for.

However, some of the incoming light will be absorbed by the material of the 'coin', which will enter an excited state, and then later re-emit that light. There is a hugh amount of photochemistry which relies on this sort of behaviour.

So, as the coin is spining in the air, the momentum from reflected light is calculable. Let's ignore the effect of absorbing the light, and focus on the re-emmision which will apply some momentum. In what direction is the light re-emited?

Well, that's a tough question. Most importantly, as the coin is spinning in the air, it depends on the time between absorbtion and re-emmision. That's a quantum phenonema, and is randomly distributed in a Gaussian disribution about some mean.

So, to calculated the effect of the coin toss exactly, you need to account for all those quantum effects. Which is impossible, because they are random.

I accept my example is a little contrived, in that the effect of the differential momentum transfer by photonic processes is negligable for any real coin, compared to other factors. It is, however, not zero, and is a solid example of how the randomness of quantum events effects macroscopic observables.

Given enough time, the fuzzyness of the quantum states gradually takes over. For most things that's a long time - it is, however, non zero.

Re:Could be argued

[Hepkat]

ah... sorry... I misunderstood what I said...

Re:Could be argued

[mindstrm]

No.. it can't. Some things are truly random, and you cannot predict a known state, with time or knowledge or research.

Re:Could be argued

[johne_ganz]

In our quantum universe, the uncertainty principle makes it impossible even in principle to measure starting state to the required precision, for the schemes that are used for true random number generation in electronic systems. Additionally, if quantum processes are accepted as truly random, they inject enough noise to taint macroscopic events with true randomness if the consequences of the noise are given enough time to propagate.

In summary, true randomness exists as a very fundamental result of the laws of nature, and won't go away no matter how good our measurements get.

Well, let's be clear here. Our best models (ie, quantum mechanics) have a statistical nature at their core. They are quite capable of predicting a large body of phenomena. Not all observed phenomena, and there's a few odd points here and there, but it's pretty damn good.

This does not, however, mean that this is the way the universe works. It's just a mathematical model. Newton's models gave us VERY good results, but it ended up folding. Not quite folding, but being superceded by something that was a bit more accurate.

So, given this, the "uncertainty principle" is the best we have. It's also somewhat axiomatic. It just is. But why? What gives rise to it at a very fundamental level?

So, it works for now, but that doesn't mean that's the way things are. Who knows? Maybe at a fundamental level, at plank scale and time, it just looks like that because we are fundamentally incapable of making such tiny, minute measurements that the whole thing is really just a big pinball machine that changes depending on the initial conditions. It may seem the same to you and I, that atom right there letting go of that photon... but it may be at the plank scale the difference of between say, earth and mars.

Re:Could be argued

[iwadasn]

We know enough about quantum mechanics to know this. There is a great deal of science (from space craft to transistors and beyond) based on the fact that quantum uncertainty is truly random. This is (there is reason to believe) the actual source of randomness in the universe, and it is really random, it's not an illusion. This was shown by disproving the "hidden variable" conjecture, you can look it up easily on google, and it's been experimentally (and theoretically) tested.

Re:Could be argued

[iwadasn]

In addition, beware of chaotic systems, for there quantum uncertainty truly can barge into the macroscopic world. For instance, the electricity and chemicals swirling around in your brain is probably a fairly chaotic system. This interaction magnifies the quantum effects, and your state of mind diverges (probably quite slowly) from the state that would be predicted given complete initial information.

As time goes on, one driver in a car slows down by 2 MPH for no discernable reason. You could not have predicted this if you were given just the state of his mind in the morning and all the inputs since then, because there are "random" inputs as well coming from the chaotic system that makes up the human brain. So, he slows down, then other drivers have to slow down, then the carrying capacity of the road decreases, eventually causing a traffic jam. Time goes on and the traffic jam vanishes just as mysteriously as it began. We've all seen it, and though it is heavily influenced by measurable phenomena (weather, etc...) there is a (probably) not insignificant random component caused by quantum uncertainty magnifying through two chaotic systems (a human brain, and a bunch of drivers interacting with each other on the road).

Re:Could be argued

[Anonymous Coward]

FWIW, there's a huge pendulum at FermiLab at Batavia, Illinois that gives a nice demonstration of chaotic systems.

Re:Could be argued

[iwadasn]

By "prove" we mean to some disgusting (like 20) number of sigma. The odds of us all dying of a stroke on the same day is greater than the odds of us being wrong about that.

The odds aren't ever zero, but they're usually close enough.

Re:Could be argued

[Anonymous Coward]

The quality of the arguments in this sub-thread are why I read /.! Thanks!

Re:Could be argued

[Maltheus]

Whenever the debate between a random universe and a deterministic universe comes up, people always pull quantum mechanics out of their pocket and say, "Since we can never predict the future (Heisenberg), then the universe must be random." The inability predict the future has absolutely nothing to do with whether or not the universe is deterministic. It just means that you can't know the future without changing it. That's just a reassertion of deterministic principles in itself. If our observations of the universe changes it, then that is an extension of determinism as our decision to observe is based on our genetics and upbringing. Randomness is only our inability to understand the causes behind effects.

People just don't want to live in a deterministic universe because they want to believe they have free will. Well, if you lived in a random universe and your leg just started kicking out and flailing without any decision, chemical factor or message from the brain, then would you be any more free? It seems to me that a person only has freedom in a deterministic universe anyway. Only then can my decisions have any consequence.

Re:Could be argued

[DavidTC]

Even if none of that was true (Which it is.), I'm always baffled by people who claim it matters.

Even if chaos theory and quantum mechanics didn't exist and we could predict future events based on measurements of the the initial systems...why are you letting strangers come in and install complicated measuring equipment inside your random noise generator? Even if it was possible to know the initial state enough to predict the random numbers, which it isn't, how the hell would attackers manage to do it?

Randomness isn't some mathmatical ideal, it's just the inverse of predictablity. It doesn't matter how the numbers come into existence, it just matters whether or not bad guys can predict them. It's completely irrelevent whether or not someone with microscopic vision magically located inside your random number generator could figure things out...because they aren't there.

And, yes, on top of that, there are things that literally are impossible to predict, like atomic decay.

Re:Could be argued

[Thundersnatch]

You seem to be missing some of the language nuances. A scientific theory can become a physical law though a large accumulation of evidence which is called a proof. So yes, scientist can "prove" things, insofar as as these terms are defined in the scientific method.

As for your thoery, "physics cannot prove things"... I think it is invalid. It seems to have a logical flaw in that does not appear to be falsifiable if you choose not to accept the large accumulation of evidence that defines a scientific proof.

Re:Could be argued

[rcamans]

Recent studies indicate that coin tosses and die rolls are not random.
The coin will end up same as it started a little more often than not.
do google search on Diaconis coin random to see paper.
coin spins on edge are no-where 50-50 because the coin weighs more on the head side, so tails comes up 80% of the time, so coin spins are not random either

Re:Could be argued

[tholomyes]

Keeping in mind: "chaos" != randomness. Chaos is data that appears to have randomness, but discernible patterns can be found in the data; chaos doesn't really come into play with dice rolls, but is found in animal populations, the stock market, weather patterns, and many other seemingly "random" systems.

I would argue that perhaps chaos exists as a fundamental result of the laws of nature, but true randomness can be difficult to find on a macroscopic scale.

Re:Could be argued

[Kiryat Malachi]

He correctly described chaos as extreme sensitivity to initial conditions. In a classical (read: non-quantum, non-probabilistic) world, chaos is the effect that makes effects very difficult to predict from a starting state, due to the initial condition problem.

Since we don't appear to live in a classical world, not only do we have sensitive dependence, which means that macro-scale events can appear effectively random, we also have quantum mechanics, which implies that many things (decay of radioactive particles, Brownian noise, Johnson noise) are fundamentally random in nature.

Re:Could be argued

[tholomyes]

Thanks for that clarification!

Re:Could be argued

[Christopher Thomas]

Well, let's be clear here. Our best models (ie, quantum mechanics) have a statistical nature at their core. They are quite capable of predicting a large body of phenomena. Not all observed phenomena, and there's a few odd points here and there, but it's pretty damn good.

This does not, however, mean that this is the way the universe works.

That's why I put a great big "if" in front of "if quantum processes are accepted as truly random", and provided an argument showing that even if they aren't (e.g. if one of the hidden-variables models is correct, or what-have-you), the uncertainty principle limits what you can do in practice. Falling even farther back from that, chaos limits what you can do even in a perfectly deterministic universe where you can measure things to arbitrary precision, as there are parts of the past light-cone that you just plain can't see until you're past the measurement you're interested in, that have impact on the system.

So, given this, the "uncertainty principle" is the best we have. It's also somewhat axiomatic. It just is. But why? What gives rise to it at a very fundamental level?

It arises from the fact that any measurement requires an interaction, and any interaction perturbs the state of the system being measured in such a way as to destroy some of the information you're trying to measure. Look up the "gamma ray microscope" thought-experiment for a discussion of this.

To have this not hold, you'd have to revoke the wave/particle duality, which would cause a very large number of models to come crashing down (and more importantly, go against just about all experimental evidence to date).

Re:Could be argued

[Christopher Thomas]

Whenever the debate between a random universe and a deterministic universe comes up, people always pull quantum mechanics out of their pocket and say, "Since we can never predict the future (Heisenberg), then the universe must be random." The inability predict the future has absolutely nothing to do with whether or not the universe is deterministic.

It does, however, mean that we can produce a RNG that is "random enough for all practical purposes", as we can never predict its outcome. That was the point of the original post.

That's why my first argument was made assuming a deterministic universe. Non-determinism isn't required (and was stated as a separate, third scenario component in my original post - the uncertainty principle was cited in the _second_ scenario to place further limits on what was knowable in the deterministic system).

Re:Could be argued

[Christopher Thomas]

Even if chaos theory and quantum mechanics didn't exist and we could predict future events based on measurements of the the initial systems...why are you letting strangers come in and install complicated measuring equipment inside your random noise generator? Even if it was possible to know the initial state enough to predict the random numbers, which it isn't, how the hell would attackers manage to do it?

The idea is that they'd exploit knowledge of the system's workings to use its past output - which they could conceivably infer from your system's behavior - to derive the internal state, and from there attack the system. Alternatively, they could look at the state of the rest of the observable environment, and from knowing how that environment interacts with the RNG, either determine its internal state or drastically narrow down the possibilities. Or a combination of these.

If these sound like attacks on PRNGs to you, you're catching on. What a predictable universe does is turn any attempt at a true random number generator into a pseudo-random number generator, which can then be attacked using any of the standard approaches.

My point is that even in a deterministic universe, and especially in universes where you have both the uncertainty principle and nondeterminism to deal with, you can't produce meaningful predictions if the system is set up right, meaning you _can_ build what are for all intents and purposes true RNGs.

Re:Could be argued

[onyxruby]

Interesting, I shall look into this to learn further upon this. I have always had a some interest in quantum mechanics. I will think on your coin flip idea. On your coin flip analogy I think you might find the following story over at NPR to be of some interest.

I have always thought quantum mechanics and physics were rather like micro and macro economics. Both are fundamentally correct within their own context. Both also happen to be largely mutually exclusive from the other. Have you ever heard a micro and macro economics duo get into a debate?

Re:Could be argued

[onyxruby]

I will check this out this weekend. Please bear in mind a clarification in a follow up comment that I am not strictly referring Heisenburgs uncertainty principal or quantum mechanics.

Re:Could be argued

[onyxruby]

No problem, it's nice to discuss such things and have people go after the arguement and not the person :)

Re:Could be argued

[DarkMan]

Heh, I did think that a coin was a bit too large for photonic momentum to have an observable effect. Looks like that's already proven. Ah, well, ignore the specifics, and just look at the principle

The think about physics rather than economics is that physics is based of repeated and repeatable observations. Economics, at the mico level at least, is based of human preferences - where you can end up with (where x > y should be read as 'x is preffered over y') a > b AND b > c AND c > a.

There is no good mathematical way of doing much with that set of relationships. within physics, however, the field of statistical mechanics is all about relating microstates to macroscopic observables. There is no generally applicable equivelent in economics.

Quantum mechanics and newtonian physics are not mutually exclusive. As you increase the sizes of things involved, the equations that govern QM reduce to the Newtonian equivelents. Newtonian physics (that which is obervable to most people) is a simpler model.

Likewise, the equations for relativistic motion reduce to the Newtonian equations as you slow things down. There is some disconnect between QM and relativity, but that's getting esoteric - for the most part they coincide.

Prehaps the most direct example of the connection between microstates and macroscopic observables is within something like the Onsager solution [0] for a 2 dimensional square lattice. This has direct applications for a single layer of a magnetic material, and has been observed with a single layer of NiO. Onsager's particularly impressive (and turgid) analysis calculates the partition function of the system - from which all of the macroscopic observables related to the microstates can be derived.

Anyway, the partition function is the key that link the microscopic states and macroscopic states. If you want to look into the link between micro and macro, that is where to start (it's part of statistical mechanics).

Not heard micro/macro economists debate directly, but I've heard it mentioned before.

[0] Lars Onsager, Phys. Rev. 65, 117 (1944). I'd advise against reading it - I've yet to meet more than a handful of people who understand it all. Still, it's an impressive piece of work.

Re:Could be argued

[Anonymous Coward]

Complete bollocks. A law isn't a theory that has been 'proved', a theory is a law with the addition of explantory power. That's why we have Newton's laws of motion (which only predict what happens next, but not why), and Einstein's theory of relativity (which attempts an explanation for why its predictions happen).

Re:Could be argued

[Anonymous Coward]

You'd have to have excruciatingly accurate knowledge of the state of everything in the past light-cone of the event you're trying to predict, as of the time of prediction, for it to work with perfect reliability.

I thought someone else would point this out, but they haven't...

A chaotic system is *not* a random one, because, as you point out, given identical starting conditions, you get identical outputs. It's completely deterministic. I've still yet to see a convincing argument that randomness is more than a useful model for a set of deterministic processes we don't yet understand fully.

Re:Could be argued

[tetabiate]

Remember that physical theories are just a
caricature of nature and have limited
applicability. Quantum physics was formulated long
time ago, but 78 years is apparently not enough
time to explore all of its consequences and
discover its faults. Adopting a phylosophical
position about the statistical or deterministic
behaviour of nature is entering metaphysics,
pursuing the ultimate consequence of a limited
theory is nonsense. One, as a physicist, should
keep a critical and skeptical attitude, but
nobody taughts students about this, we suppose
they catch it by osmosis as Richard Feynman
says in his well know talk "cargo cult science".

Re:Could be argued

[hankwang]

>>PROVABLY unpredictable, e.g. radioactive decay and certain quantum effects.
>Wrong. Sorry. Physics cannot prove things.

You can't prove physical phenomena in a mathematical sense (based on axiomas), but you can prove them within a framework of theories. In the case of the unpredictability of quantum-mechanical effects: if they were predictable, an enormous part of the theory of quantum mechanics would be fundamentally flawed.

How do you prove that you are reading this message? You only have a best guess that you are reading this and that you are not having a dream or that you actually are a character in a computer game that I (a supersentient creature) am playing. Maybe I only need to terminate the program and you are no more? Can you disprove that?

Re:Could be argued

[rugger]

> If these sound like attacks on PRNGs to you,
> you're catching on. What a predictable universe
> does is turn any attempt at a true random number
> generator into a pseudo-random number generator,
> which can then be attacked using any of the
> standard approaches.

Most well written crypto random number generaters make it computationally complex to determine the current state or previous states of the "random" source. It does this by using either an encryption or hashing algorithm to generate derivatives of the "random" source, rather then exposing the "random" source itself.

Re:Could be argued

[DavidTC]

But that's stupid. The data generated depends on thousands of tiny variables, and you have to admit that, even if you claim they are measurable, in contradiction to QM, and the math is doable, in contradiction to chaos theory.

These variables include external variables, like the air pressure in the room and the exact temperature of the device. You can't just 'calculate' them and somehow have future results, because they change.

Of course, at this point, I realize the people claiming there are no random numbers are just crackheads who somehow need to insist there is no such thing as 'random' for some philosophical reason, and don't actually have any logic to back them up.

Even in a completely predictable universe, there are still truely random numbers, because random is just the inverse of unpredictable, and prediction requires knowledge of the original state. I could drive to the moon, pick up a slice of moon rock, and generate random numbers based on the placement of the atoms, and then keep that chunk of rock hidden away forever. Good luck figuring out those numbers mathmatically.

Re:Could be argued

[Christopher Thomas]

A chaotic system is *not* a random one, because, as you point out, given identical starting conditions, you get identical outputs. It's completely deterministic. I've still yet to see a convincing argument that randomness is more than a useful model for a set of deterministic processes we don't yet understand fully.

Look up "hidden variables" interpretations of quantum mechanics for discussions about this. The upshot is that while it's very difficult to prove the case one way or the other (and there are still people trying), you end up with a far cleaner model if quantum processes are treated as truly random. From there, in the absence of evidence of determinism, Occam's Razor kicks in.

I vaguely recall that there were actually experiments that ruled out some of the simpler "hidden variables" interpretations, strengthening the case for true randomness in quantum events, but you'll have to ask someone other than me for the details.

Re:Could be argued

[Iainuki]

Bell's Inequality only rules out local hidden variables theories, not all hidden variables theories.

Music and mathmatics from one person?

[Spokehedz]

In an article on TechnologyReview.com, Simson Garfinkel spells out the real-world consequences of this mathematical conundrum.

Who else read that as Simon Garfunkle? Come on... I couldn't be the only person here, could I?

And besides... if you want real security, just do double encryption. use two common, off-the-shelf encryption methods, one encrypting the other's data and your data is now as safe as it can get. further encryptions in encryptions will only add to bloat and time to decrypt.

Re:Music and mathmatics from one person?

[Anonymous Coward]

And besides... if you want real security, just do double encryption.

I suggest using double ROT-13.

Re:Music and mathmatics from one person?

[Anonymous Coward]

Nobody did, except for you and the moderator that modded you up :)

Re:Music and mathmatics from one person?

[Froggert]

Actually, Simon Garfunkle is the near prime public key for Simson Garfinkel. What's the current Slashdot karma factor for incredibly bad puns?

Re:Music and mathmatics from one person?

[rick-o]

if you want real security, just do double encryption.

Yeah, it works great with ROT13.

Re:Music and mathmatics from one person?

[Anonymous Coward]

I did. First I read Simon Garfunkel, and I thought "hm, poetry about mathematichs?", then I read it again, and again I read Simon Garfunkel. "What!?", I thought, "the hell is going on??", but the third time I got it right. So no I think I'll be able to sleep. If I dont dream about "The Village", as I just saw the movie. Then I think I'll get so bored, sleep will be impossible.

Re:Music and mathmatics from one person?

[sparcnut]

And besides... if you want real security, just do double encryption. use two common, off-the-shelf encryption methods, one encrypting the other's data and your data is now as safe as it can get. further encryptions in encryptions will only add to bloat and time to decrypt.

That works fine until you try double encrypting with ROT13 :-)

BTW, doubling the number of layers of encryption really doesn't make a whole lot of difference: at most it increases the complexity as much as if you had increased a single cipher by one bit. 8 levels of encryption at 128-bit each, you have at most a cipher of strength equivalent to 131 bits.

Re:Music and mathmatics from one person?

[pjt33]

You appear to be advocating security by obscurity. Please tell me I'm misunderstanding you.

Re:Music and mathmatics from one person?

[Anonymous Coward]

This is absurd. Lets assume I encrypt with a 256 bit key and then use another encryption method with another 256 bit key. It is roughly twice as hard to crack as before. No big deal. About the same as using a 257 bit key.

Re:Music and mathmatics from one person?

[Yogurt Earl]

Simon Garfunkle?? You mean Paul Simon and Art Garfunkle? no I didn't read it that way.

Re:Music and mathmatics from one person?

[slagheap]

Music and mathmatics from one person?
Who else read that as Simon Garfunkle? Come on... I couldn't be the only person here, could I?

Well, for starters, Simon & Garfunkle are already two people... then add this Simson Garfinkel guy, and you've got three. Music and math from three people... not so impressive.

It's still a "what if" piece...

[bersl2]

So far as we know, P != NP.

And that's it. And I haven't seen a shred of evidence to the contrary.

Yes, the article is somewhat truthful, in that if P == NP, the world will have been turned on its head, but the same thing is true about thousands of scientific and/or mathematical assertions, each of which is more likely to be overturned than P != NP.

Re:It's still a "what if" piece...

[Welpa]

if P == NP, the world will have been turned on its head

Not necessarily, what if P=NP but the fastest P algorithm which computes an NP complete problem is n^100000? The complexity of this is still much larger than anything feasible.

Which is why compexity theory is a bit funny, since for a complexity theorist, if a problem is in P, it's easy.

P=NP is really a purely mathematical question. It's solution will have absolutely no impact on software engineering, although of course it will have a huge impact on theoretical computer science.

Re:It's still a "what if" piece...

[Anonymous Coward]

> So far as we know, P != NP.
> And that's it. And I haven't seen a shred of
> evidence to the contrary.

Ain't that the truth.

One of the most frustrating thing about coming up with a proof is that just as you close in on the solution, you find that it depends on a solving a problem that's also NP. You can go in NP circles for months and not even realize it because NP is such a weird problem space.

It's not at all obvious that the following problems are really the same:
* packing a knapsack the most efficient way possible
* finding the shortest path between 50 cities
* finding out how to colour a graph so that no two adjacent points have the same colour.

But they are. If you can solve one, you're able to solve them all.

Re:It's still a "what if" piece...

[gweihir]

Yes, the article is somewhat truthful, in that if P == NP, the world will have been turned on its head

Nor necessarily. If it turns out that NP only has problems with complexity n^100 in it, then for most paractical purposes we are still in business, since practical algorithms in P may range up to complexity n^4, if that.

For crypto (on-way functions) it just needs to be very hard in one direction and very easy in the other. Choosing N and NP is a nice pair of things were this works, but not the only one.

Re:It's still a "what if" piece...

[sugarmotor]

You write:

* finding out how to colour a graph so that no two adjacent points have the same colour.

I thought it was a remarkable feature of the 4-colour theorem that it came with a polynomial time algorithm for producing a colouring. I think it was quadratic time.

I think you have the 3 colour problem in mind. Let me know if I'm wrong.

Stephan

Re:It's still a "what if" piece...

[Anonymous Coward]

Those problems are not just NP, but also NP-Complete. To understand why they are all equivalent to each other, there's a trick. It is to build a Turing-machine using the problem as an engine. For example, on the travelling salesman problem you choose the placement of cities so that the shortest route path forms logical operations and has the solution to an arbitrary problem that is verifiable in polynomial time.
Once you realize that it becomes a lot more obvious.

Re:It's still a "what if" piece...

[HorsePunchKid]

Too tired to think about this really, but I think you're thinking of region coloring, whereas the post you responded to was talking about vertex coloring. It's easy to make graphs that require more than four colors to color neighboring vertices differently, see here. Sounds like you're aware of this, just got switched around when you read it. Hope that helps. (I can tell I'm tired because it took me three tries to get "vertices" right...)

Re:It's still a "what if" piece...

[HorsePunchKid]

You're right about the quadratic algorithm, of course. It's just not what he was talking about. Just to clarify.

Re:It's still a "what if" piece...

[sugarmotor]

Yes, that makes sense. Thanks - Stephan

Wow that pair are smart

[Anonymous Coward]

I thought they just did hits like "Bridge over Troubled Wa .. "

Oh wait. Simpson Garfunkel. "Post Anonymously" checkbox then.

setec astronomy

[PetoskeyGuy]

Did they also put their whole project into a microchip that connects to a modem and can figure out the username and password of any system no matter what it is from a generic login prompt?

I hope people start making better movies soon. I don't want to see I,Robot come true.

Re:setec astronomy

[Anonymous Coward]

I don't wan't to see you come true.

Another magical no more secrets box

[syousef]

When will people learn that as long as people have secrets to keep they'll find ways of keeping them? There may be advances in technology which will render certain methods of keeping the secret obsolete, but this search for a magic algorithm is silly.

I imagine one day there may be an advance that will mean a total security overhaul will be required though, and that could provide a window of chaos in the most extreme circumstances. However every advance in decryption tends to quickly lead to an advance in encryption that can beat it. At least historically that's been the way it is.

Until they can literally read the contents of my brain, I'm not too worried.

Re:Another magical no more secrets box

[Country_hacker]

Until they can literally read the contents of my brain, I'm not too worried.

/me adjusts tinfoil hat
You'll never have to worry about that if you keep your dome chromed! ;-)

Re:Another magical no more secrets box

[chadjg]

Well, I do believe they are working on that. What if you could stick somebody inside a scanner that would tell you if a person recognizes an object or had seen that object or a person before. Would that be useful for password cracking? How about a brain-scan tells when a person is lying?

Unless you can make a tinfoil helmet that is strong enough to keep "them" from whacking you on the head with a baseball bat and then draging your unconscious body back to the lab, you're secrets are not safe.

Or "they" could skip the high tech crap and threaten you with goatse type pics.

Re:Another magical no more secrets box

[metaomni]

Until they can literally read the contents of my brain, I'm not too worried.

Don't worry. We know.

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:All he does is explain P and NP

[Vaevictis666]

Encryption cannot die, algorithms can.

True - and if NP is found to be P, then it will effectively hose encryption as we know it today. Your private-key/public-key encryption that relies on those big primes you know and love? Well then would be easily broken - the standard is private key is the two prime factors, public key is their product, and if an easy way to factor is found, then from the public key I can deduce the private, thus breaking your encryption.

They're not as unrelated as you'd think, but it's true that it's not the be-all end-all of encryption.

Re:All he does is explain P and NP

[Chris Burke]

Yeah, it's not a great article, though I do welcome the opportunity to broaden peoples' mathematical horizons. Still.

He starts off making it sound like P?=NP could be resolved soon in favor of P=NP, but Adelman says we aren't any closer to solving it than we were in the 70's, and the only one the author quotes as saying a solution may be imminent predicts that it will be shown that P != NP (the answer i think most mathematicions expect).

There's a lot more than just encryption riding on the answer (and as you say, encryption not so much) as tons of useful algorithms would go from intractable (exponential) to tractable (polynomial), and that's why people have been looking at the problem for so many years. Without success.

Re:All he does is explain P and NP

[Anonymous Coward]

Forgive my ignorance, but can someone else explain the difference between P and NP? What I got from the article was that a P problem is one that is bounded (e.g. finding a book in a bunch of boxes in your basement) and an NP problem was really realy hard. But the example the reporter gave was of key based encryption being brute forced. Shouldn't that, by his definition, be a bounded problem? There are only so many x bit numbers. If you use 128 bit encryption, then you have =2^128 possible keys to try. Granted that is a lot, but it is still a matter of trying each one until one works, same as looking in every box until you find the book. How is it different?

Re:All he does is explain P and NP

[pthisis]

if NP is found to be P, then it will effectively hose encryption as we know it today. Your private-key/public-key encryption that relies on those big primes you know and love? Well then would be easily broken

Not true at all.

Being inside P doesn't necessarily make a problem fast or easy to solve. If an algorithm is found that can factor an n-bit number in google*(n^google) steps, then factoring is in P. That doesn't make it particularly easy to factor large numbers, though. Being in NP if NP>P implies that a problem is harder for sufficiently large n, but "sufficiently large" may be REALLY large--it might even be "n has to be larger than the total number of atoms in the universe".

Aside 1: The same is true of lower complexity classes as well. As a simple example, for small n, insertion sort is faster than quicksort even though it's abysmal for large n. There are problems that have a solution thats O(n) and a solution that's O(n^2), but the O(n) solution requires someconstant*n time while the O(n^2) solution requires n^2 time. Until n is at least someconstant, the O(n^2) solution is faster.

Aside 2: There's no proof that factoring is outside of P even if P!=NP. It's widely believed to be true but unproven.

Re:All he does is explain P and NP

[Frizzle Fry]

It's not about bounded vs. unbounded, it's about polynomial vs. exponential (or worse). Problems in P can be solved in polynomial time.

You're right that you can brute force an answer. But that will require trying all 2^128 keys (in this case). So you can see that the amount of work you have to do will grow exponentially with the input.

Re:All he does is explain P and NP

[Dastardly]

There's a lot more than just encryption riding on the answer (and as you say, encryption not so much) as tons of useful algorithms would go from intractable (exponential) to tractable (polynomial), and that's why people have been looking at the problem for so many years. Without success.

Great point. Showing NP=P would probably result in more benfits than harm. There are tons of efficiency sorts of problems (analogous to traveling saleman) that are NP that if they could be solved in polynomial time would result in huge increases in efficiency.

But, I expect if any proof occurs it will be that P != NP.

Re:All he does is explain P and NP

[falsifian]

But the example the reporter gave was of key based encryption being brute forced. Shouldn't that, by his definition, be a bounded problem? There are only so many x bit numbers. If you use 128 bit encryption, then you have =2^128 possible keys to try.

128-bit brute-force anything is a bounded problem. Since there are only 2^128 possible inputs, all you have to do is pick the longest time it takes your program to run out of all those 2^128, and you can say your program runs in constant time (or better).

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:

• A problem is NP-hard if every problem in NP is reducable to it. For example, the satisfiability problem is NP-hard. If you give me a problem that can be solved in NP, I can make a very simple and quick program that will take any input to your problem and turn it into an equivalent input for the satisfiability problem.
• A problem is NP-complete if it is NP-hard and also in NP. Satisfiability is NP-complete because it's NP-hard but can be solved in NP. A program that is NP-hard but not in NP is more difficult to solve than problems in NP.

I hope I didn't just confuse you more... just read the wikipedia article if this doesn't help.

Re:All he does is explain P and NP

[finkployd]

It won't hurt symetric key cyphers, just public key which are based on P != NP

There goes my bank account

[freedom_india]

Iam Nigerian dictator's brother Sani Abacha.
I have $25,000,0000 of money that we are not allowed to take out of Nigeria. I have an NP and i got your account number and bank name while you were checking your account online routed through Nigeria.

Iam pleased to inform you that using my NP i have access to your account, and iam transferring the $25,000,0000 to your account after withdrawing $16,781 from your account for transaction fees and security deposit.
God Bless.

Solution

[Paulrothrock]

I propose we make every computer solve the meaning of Life, the Universe and Everything. Computers that have figured this out already know it is 42, and it would take the fastest supercomputer in the universe eons to calculate it, making it ultra-secure!

I saw this movie

[revery]

I saw a movie about this exact same thing. Luckliy Robert Redford and his team won and the world was made safe from Ben Kingsley, but it was touch and go there for a little bit.

I was worried.

The one way to tell for sure if the good guys win, is if the Republican National Committee goes bankrupt and GreenPeace gets a sizable donation. Also, you might see Sydney Poitier in Tahiti and Dan Akroyd in a brand spanking new RV.

--
Pain?

Try Prison.

Re:I saw this movie

[Dr_Barnowl]

Adelman was an advisor on "Sneakers".

Re:I saw this movie

[bobdehnhardt]

Yeah, but sombody needs to teach Akroyd the ins and outs of local pronunciations.

DUNbarton, Dan! DUNbarton!

Re:I saw this movie

[ErikTheRed]

The one way to tell for sure if the good guys win, is if the Republican National Committee goes bankrupt

Yes, I know this is funny, but keep in mind that a few years ago on the Clipper Chip issue it was also Kerry vs. Ashcroft - but it was Kerry pushing for the Clipper Chip and then Senator Ashcroft pushing for individual privacy. Ashcroft has since done a post-9/11 180-degree flip on his views here, but nothing suggests that Kerry has done the same (insert Kerry flip-flop joke here if you want, but no one really knows what he really thinks right now - maybe not even Kerry).

The bottom line - no political party can be trusted to secure your privacy, civil liberties, etc. Pick your candidates on their individual stances on the issues important to you. Depressingly, most of the time the only difference between the parties (and candidates) is how much lubrication they'll use when fucking you in the ass.

Yep, its doomed.

[boulat]

In 1995 Shor published a paper in which he devised an algorithm which would allow quantum factorization using qubits and gates. In short, his method would allow really [really-really] fast code breaking using quantum 'computers'.

http://tph.tuwien.ac.at/~oemer/doc/quprog/node18 .h tml

Re:Yep, its doomed.

[0123456]

"In short, his method would allow really [really-really] fast code breaking using quantum 'computers'."

AFAIR the best known quantum algorithm for breaking conventional crypto merely reduces search time to about its square root. So increase your key length from 128 to 256 bits, and it will take about as long to crack a key as a current computer would for a 128-bit key.

This is one reason why most new crypto algorithms have 256-bit keys rather than 128-bit.

Re:Yep, its doomed.

[wwest4]

Shor's algorithm doesn't necessarily have anything to do with complexity theory. It's simply an exploitation of our existing knowledge of quantum mechanics, whereas the article is talking about exploitation of potential advancements in mathematics.

Re:Yep, its doomed.

[Anonymous Coward]

In 1995 Shor published a paper...

The same year he did this masterpiece ?

Yawn

[Anonymous Coward]

Some scientists are trying to make a faster-than-light drive. Sell your car now before it's obsolete!

Someone wake me when they actually prove it.

I have discovered...

[CSG_SurferDude]

I have discovered a truly remarkable proof which this post is too small to contain.

Re:I have discovered...

[FisherRider]

I have discovered a truly remarkable proof which this post is too small to contain. Does no one else get this reference? This should definitely be modded 5, Funny. A reference to Fermat's last theorem was scribbled in the margins of one of his notebooks, saying the above post. It has so far not been proven if there any powers n >2 such that a^n + b^n = c^n for integers a b and c and n.

Re:I have discovered...

[Anonymous Coward]

I have discovered a truly remarkable proof which this post is too small to contain. Does no one else get this reference? This should definitely be modded 5, Funny. A reference to Fermat's last theorem was scribbled in the margins of one of his notebooks, saying the above post. It has so far not been proven if there any powers n >2 such that a^n + b^n = c^n for integers a b and c and n.

Man, that cracks me up.

Re:I have discovered...

[Anonymous Coward]

Actually, Fermat's last theorem was proved about 10 years ago. It's highly unlikely that Fermat actually had a valid proof though.

Re:I have discovered...

[piquadratCH]

It has so far not been proven if there any powers n >2 such that a^n + b^n = c^n for integers a b and c and n.

Andrew Wiles proved it 10 years ago. Time to catch up on number theory anecdotes ;)

Re:I have discovered...

[Anonymous Coward]

Damned lameness filter ;-)

Re:I have discovered...

[FuzzyFox]

Prove it!

Re:I have discovered...

[gcaseye6677]

Nothing like a little math humor...

Re:I have discovered...

[TheoMurpse]

if for no other reason than to deflate your ego, i reply that yes, i too got the reference...you just beat me to reading it, or i would have posted the same thing you did...

incidentally, MOD PARENT UP ^_^

Re:I have discovered...

[Nate Eldredge]

Clearly you're not a mathematician and are also new to slashdot. Yes, dammit, we know about Fermat, but it's way overused as a joke. It's an old joke now in mathematics, and on slashdot as well. Every time there's an article about any sort of theorem or proof someone posts this damn joke.

Bah.

Get with the times!

[Otter]

Ask Slashdot dealt with this issue three years ago! When it comes to uninformed, idle speculation, this site is way ahead of MIT!

"last human draws its breath"

[aristus]

Cryptography will die when the last human draws its breath. Er.... shouldn't that be third-to-last human?

Re:"last human draws its breath"

[Anonymous Coward]

No, the last few humans will be extremely paranoid because they will continue to expect more people to exist but won't see any. Therefore it is absolutely possible that even the last human will use encryption to protect his/her secrets from Them.

Re:"last human draws its breath"

[Issue9mm]

Actually, I'm thinking second-to-last really. As the third-to-last person on the earth, I may choose to encrypt a document entitled "How to kill Fred and Bill" so that that the other two may not access it.

-9mm-

Re:"last human draws its breath"

[Anonymous Coward]

Actually, I'm thinking second-to-last really. As the third-to-last person on the earth, I may choose to encrypt a document entitled "How to kill Fred and Bill" so that that the other two may not access it.


But as you'll be dead I don't think it matters to Bill and Fred anymore.

Re:"last human draws its breath"

[Janek Kozicki]

"How to kill Fred and Bill"

I humbly prefer killing Bill only. If I may.

Re:"last human draws its breath"

[Anonymous Coward]

I guess that depends on good you are at keeping secrets from yourself.

Re:"last human draws its breath"

[networkBoy]

Er.... shouldn't that be third-to-last human?
only if you want to communicate privately. If you want to keep recorded secrets then encryption is useless after only one human remains.
-nB

Re:"last human draws its breath"

[Puff Daddy]

Er.... shouldn't that be third-to-last human?

Eff that, ain't no one getting to see my e-mail come Hell, high water, or the end of the human race.

Re:"last human draws its breath"

[fitten]

Cryptography will die when the last human draws its breath. Er.... shouldn't that be third-to-last human?

Depends if you believe there is intelligent life elsewhere in the universe or not... I guess they could know about encryption.

Re:"last human draws its breath"

[N8w8]

Apparently, you forgot about Skynet.

Re:"last human draws its breath"

[orasio]

That wasn't funny, Uma.

Re:"last human draws its breath"

[Anonymous Coward]

Not if it is me and my girlfriend, and I'm still trying to hide my porn. Crypto isn't just for hiding from the state.

Now, she'll still be pissed that I'm hiding something.

Re:"last human draws its breath"

[abb3w]

No, Cryptography might not die even then, because I for one will not welcome our new alien overlords, even after they wipe out the rest of the human race. I want my notes on driving them off the planet (and, umm... cloning Jeri Ryan for replenishing the species) to be completely unreadable to them until after I've finished implementation.

Re:"last human draws its breath"

[MarsDefenseMinister]

Eve. Her name is Eve. Bob and Alice are going to kill her.

Re:"last human draws its breath"

[MarsDefenseMinister]

I just know someone's going to mod me down because they don't understand.

http://www.google.com/search?hl=en&lr=&ie=UTF-8&sa fe=off&q=bob+alice+eve&btnG=SearchThis Google search will help.

Re:"last human draws its breath"

[whovian]

Unless any of them turns out to be Alice. Or Bob.

Re:"last human draws its breath"

[Anonymous Coward]

Third to last human? What if human A decides to send human B an email. Well we wouldn't want our 'friends' the Klingons to intercept said message now would we?

Re:"last human draws its breath"

[Anonymous Coward]

How to kill Fred and Bill
Don't you mean Alice and Bob?

If you don't get it, then you haven't read enough crypto textbooks.

Re:"last human draws its breath"

[DARKFORCE123]

Don't forget Eve. If Alice can't perform, then you still have Eve.

Re:"last human draws its breath"

[James Turpin]

Cryptography will outlast the human race as warring factions of intelligent robots battle for domination of the galaxy.

Re:"last human draws its breath"

[kayak334]

I'd prefer the other two were named "Britney" and "Christina" and that my document was titled something a bit different.

Re:"last human draws its breath"

[ffub]

i think thats what he meant, mate.

Re:"last human draws its breath"

[Chandon Seldon]

If the only humans left are you, Britney, and Christina, we might as well give up on the continuation of the human race anyway...

Re:"last human draws its breath"

[Eric119]

No, no, no, you're both wrong! It's after the second-to-last human dies. People have diaries and such they want to keep private.

Re:"last human draws its breath"

[Carewolf]

I think that would be mostle Alice trying to kill Eve, as Bob would just be trying to convince his girlfriend Alice that they should have a triangle with Eve; you know to save the human race and all...

The new SGEP

[ARRRLovin]

Simon Garfunkel Encryption Protocol. "Hello aklsdj=2vxcwe (( my old friend." SYN: Are you going to Scarborough Fair? ACK: Parsley, sage, rosemary and thyme.

I'm sorry ...

[hotspotbloc]

An NP computer, if one existed, could try all of the possible keys at the same time, and recognize instantly which key was correct. Code breaking is an NP problem.

... but isn't he confusing real science with the moive "Sneakers"?

Re:I'm sorry ...

[zalas]

However, what would be scary is if the 2^80 complexity needed to find a collision in SHA-1 all of a sudden became 80^2.

Re:I'm sorry ...

[pjt33]

The word you're looking for is mathematics, not science, and it's not a bad description of a non-deterministic Turing machine given that it's aimed at laymen who don't know what a finite state automaton is. I just wish he'd stop using the term "NP computer".

Umm...

[cybermage]

Wasn't this covered in the movie sneakers? As I recall, it didn't work out too well for the mathematician involved.

The article sums it up best

[GreenCrackBaby]

Adelman thinks that we'll be waiting for the solution for a long time. Resolving the question of P and NP, he says, "would require new and brilliant ideas and not routine incremental progress. From my perspective, we are no nearer to solving the problem now that we were when bell-bottom pants were cool."

The whole thing is a bunch of alarmist speculation.

Re:The article sums it up best

[Anonymous Coward]

The majority of the slashdot science articles have been misunderstood by the editor. This sounds like a troll, but sadly it's the truth.

Re:The article sums it up best

[Thuktun]

From my perspective, we are no nearer to solving the problem now that we were when bell-bottom pants were cool.

Indeed, why is this news?

Re:The article sums it up best

[izakage]

You mean bell-bottom pants aren't cool?

You should have told me years ago!

Ok...

[Anonymous Coward]

now let's see you do it.

FLAME ME!!!!!

[Anonymous Coward]

feel free to flame

This is Crazy

[jetkust]

But some mathematicians are trying to prove that there's really no difference between 'hard' and 'not hard' problems

Well, it's always better to have the hard problem. You may have to seek medical attention, but at least your pride remains intact.

Re:This is Crazy

[InfraMan]

... prove that there's really no difference between 'hard' and 'not hard' problems

Okay I'll give it a shot.

How about the classification of this problem?

If proving the there's no difference between 'hard' and 'not hard' IS itself not hard, then it should have been done by now...

If it is 'hard' and true then it's also 'not hard', but if it's not hard it should have been proven already.

So it must be false, or atleast an unprovable statement,(apologies to Godel, et al) everybody back to bed.

It's not "the end of encryption" at all

[Bruce Perens]

You mean public-key encryption . I fail to see how the one-time pad would be effected by new ways to solve NP-hard problems.

Bruce

Re:It's not "the end of encryption" at all

[Control Group]

True, but OTPs aren't reusable, and the key needs to have as much information as the message, so they're not an answer to digital signatures or secure transactions online. Or at least, not an answer that's easy enough for me to comprehend.

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.

Re:It's not "the end of encryption" at all

[OdinHuntr]

True, but OTPs aren't reusable

OH MY GOD, THEY'RE NOT???

Re:It's not "the end of encryption" at all

[Bruce Perens]

Agreed.

But it's interesting that with all of the interest in encryption, there is so little interest in the one form of encryption for which a mathematical attack isn't possible.

Thanks

Bruce

Re:It's not "the end of encryption" at all

[Beautyon]

And to think, I spunked off my mod points on some carp earlier today!

I just laughed my ASS off!!!!

Re:It's not "the end of encryption" at all

[UnknowingFool]

I don't think this would affect quantum encryption either, but I wouldn't say I was fully knowledgeable about quantum encryption.

Re:It's not "the end of encryption" at all

[Anonymous Coward]

It's not really interesting at all. To use a one-time pad, you have to transmit (SECURELY, mind you) the same amount of keydata as plaintext. In that case, why not use this secure method of transfer to send your data in the first place?

Re:It's not "the end of encryption" at all

[Bruce Perens]

AC wrote: It's not really interesting at all. To use a one-time pad, you have to transmit (SECURELY, mind you) the same amount of keydata as plaintext. In that case, why not use this secure method of transfer to send your data in the first place?

Because you don't have to transfer the cyphertext at the same time as the keytext. You can be reasonably assured that you can move a DVD securely every few years, though you may have long periods of being under surveilance and interception between then. Having moved that DVD, as long as you store it securely you can dribble out a few K at a time in sending messages for a long time.

Bruce

Re:It's not "the end of encryption" at all

[Thuktun]

True, but OTPs aren't reusable, and the key needs to have as much information as the message, so they're not an answer to digital signatures or secure transactions online. Or at least, not an answer that's easy enough for me to comprehend.

Imagine REALLY, REALLY large sets of cryptographically random data exchanged between two communicating parties to be used as a one-time pad. (c.f. Vinge's A Fire Upon the Deep, where one-time pads where the only form of encryption used. Multiple separate XORs would be separately shipped in secrecy and combined to the form the final pad at the destination.)

Of course, there are plent of implementation issues before doing something like this, like having that data securely available when you need it. You might have to trust to physical data security or steganography to protect your data when not on point-to-point OTP-protected links.

Re:It's not "the end of encryption" at all

[ThousandStars]

Actually, Mr. 4152 5145 5148 9376, exp. 03/05, they are.

Re:It's not "the end of encryption" at all

[finkployd]

Not just one time pads, pretty much any symmetric key system is safe if P == NP. Greanted you still have a serious key distribution problem (although kerberos still works nicely), since that is all we really use PK encryption for these days anyway (well, and encrypting hashes for signatures).

I also kinda fail to see how if someone figures out P=NP that will give them the ability to factor primes any easier. Anyone want to explain that to little old me? (yes, I know what P=NP means, I want to know how it will suddenly be used in practice)

Finkployd

Re:It's not "the end of encryption" at all

[pontifier]

Because you may be able to transmit securely at some times and not others.

Re:It's not "the end of encryption" at all

[andrewagill]

True, but OTPs aren't reusable

OH MY GOD, THEY'RE NOT???

OdinHuntr, sit down. I've got something I need to tell you. Remember that magical night we spent trading ciphertexts?

Re:It's not "the end of encryption" at all

[Animats]

Most "one time pad" systems found on the Internet aren't. They generate their "one time pad" with a pseudorandom number generator. That is not a one time pad. It's a short-key system based on the seed of the random number generator.

A real one-time pad key generator using current technology would have a hardware device like a noise diode that generated random bits at a high rate and created two identical DVDs. That would be useful. With 4GB of random bits, you could encrypt about 5000 minutes of phone-grade voice.

Re:It's not "the end of encryption" at all

[Bruce Perens]

I have at times been tempted to manufacture a noise diode product. Intel CPUs have one, but there seems to be some continuing suspicion regarding whether it has been "influenced" to be less than random.

A verifiable noise diode setup would have to display the same bits in the data that you'd see on an oscilliscope. USB 2 certainly provides enough bandwidth to fill the disk, so that might be a good way to connect it.

Bruce

Out of fashion, I guess.

[jlowery]

"From my perspective, we are no nearer to solving the problem now that we were when bell-bottom pants were cool."

Bell-bottom pants aren't cool anymore? Man... what a bummer. I got to quit bogarting those roaches.

Re:Out of fashion, I guess.

[kaos.geo]

"...that we were when bell-bottom pants were cool." You mean in 1973, no...maybe 1990, no... i guess perhaps you mean 1997..damn.I give up!!!... Fashion is cyclic.Perhaps the answer to this problem is cyclic too! That would explain why is it so hard to find. :P

Swallow content

[Anonymous Coward]

1. None of the popular encryption algorithms is known to use NP-hard problems.
   
2. There are many people which believe that P!=NP is one of the theorems which come from Goedels incompleteness results, e.g. they are true but can't be proven. In fact some researchers try to prove that P!=NP can't be proven.
   
3. The sentences "In practical terms, that would spell the end of encryption as we know it. The Internet would be vulnerable to hackers and computer viruses." are a gem of its own - this doesn't need any further comment.
   

Summa summarum it's MIT science at its best swallow and full of hype.

Re:Swallow content

[Anonymous Coward]

None of the popular encryption algorithms is known to use NP-hard problems.

Uh, except for like all symmetric crypto perhaps? What is it trying to mimic if not an extremely complex instance of circuit satisfiability problem?

If I were working on the problem

[eric76]

If I were working on that problem, I would be trying to prove that P and NP are different classes.

That is, that P != NP.

I just don't think that P = NP has any chance of being true.

My favorite Simson Garfinkel work

[Anonymous Coward]

"50 Ways to Break Encryption"...
just calculate the key, Lee
hack the algorithm, Jim
reverse-engineer, Samir

sleep, what's that?

Re:My favorite Simson Garfinkel work

[Coryoth]

sleep, what's that?

A severely debilitating disease usually associated with malnutrition in the form of severe caffeine deficiency.

Jedidiah.

Re:My favorite Simson Garfinkel work

[Anonymous Coward]

Sleep, who's Lint?
We got a fuckin' Pinto.

Factoring is another NP problem -- NO!

[Randym]

Factoring is another NP problem.

I'm surprised that Simson made this elementary mistake.

Factoring has *not* been proved to belong to either P or NP. It's an "open problem".

Re:Factoring is another NP problem -- NO!

[mrtroy]

Factoring is another NP problem. I'm surprised that Simson made this elementary mistake.
Factoring has *not* been proved to belong to either P or NP. It's an "open problem".

Exactly. RSA will not die...factoring still will take a long period of time, with larger keys.

Re:Factoring is another NP problem -- NO!

[Anonymous Coward]

Factoring has *not* been proved to belong to either P or NP. It's an "open problem".

Well, it's definitely in NP, as are all problems in P. I think it's even known to be easier than NP-hard.

The conjecture is that factoring is harder than problems in P. But that would be incorrect if P=NP, and it might be incorrect even if not.

Re:Factoring is another NP problem -- NO!

[Anonymous Coward]

Why not replace one elementary mistake with another?

Factoring IS in NP. One can rig up a polytime NTM without much difficulty that will decide whether n has a factor between k and l for a 3-tuple (k, l, n) k < l < n. Even easier would be to rig up a polytime DTM which verifies against a witness to factoring, which would also prove factoring to be in NP.

What's still open is whether factoring is in NP-hard (and hence NP-complete), and whether factoring is in P.

Re:Factoring is another NP problem -- NO!

[Anonymous Coward]

Hands up, who idiot modded this down?

Re:Factoring is another NP problem -- NO!

[techno-vampire]

He also tries to prove his case about crypto with a false dichotomy. He shows that it's impractical to break a 128-bit encryption by trial and error because there are so many keys possible and claim that this proves they can't be broken. Of course, as we all know, there are other methods, and trial and error is almost always the least effective of them.

Re:Factoring is another NP problem -- NO!

[TheLink]

Is proving "whether P==NP or not" a P or NP problem? :)

Re:Factoring is another NP problem -- NO!

[Anonymous Coward]

It it was known it is easier than NP-hard it would be known thap P!=NP, because if P=NP then all Problems in P are NP-hard (as these would be solveable in polynominal time, too)

Reading for Comprehension

[Anonymous Coward]

In an article on TechnologyReview.com, Simson Garfinkel spells out the real-world consequences of this mathematical conundrum."

I read that as Simon Garfunkel the first time through and thought this had to be a joke.

Old news even for slashdot

[Anonymous Coward]

The P=NP problem is a century old and it's been an integral part of modern encryption since the current algorithms were originally invented.

I thought the article would have had something to do with researchers cracking the P=NP problem. There's no news here that's not older than I am.

Think twice

[Anonymous Coward]

You don't want the aliens decoding your pr0n collection.

Re:Think twice

[strider44]

they then want to conduct some experiments on Alice and Bob.

Sneakers

[zoloto]

Funny. I saw this movie just last saturday and loved it. Though I laughed when watching it after 5+ years and the concepts seemed - hollywood. :P

Sneakers rocked.

Re:Sneakers

[revery]

yeah, I'm wondering how many people will get the reference. Sneakers in one of my favorite movies ever.

Glad to know others like it as well.

I have a proof

[rumblin'rabbit]

I have a proof that proving P = NP is an NP-complete problem. Unfortunately this posting is too small to hold the proof.

Re:I have a proof

[Eric_Cartman_South_P]

I have a proof that proving P = NP is an NP-complete problem. Unfortunately this posting is too small to hold the proof.

N = 1

What's the problem? Posted perfectly.

Re:I have a proof

[Soul Brother #1]

Unfortunately this posting is too small to hold the proof.

Prove it.

Re:I have a proof

[rumblin'rabbit]

Okay, I haven't actually proven that proving P=NP is an NP-complete problem. I have proven, however, that if you did have a proof that proving P=NP is an NP-complete problem, then verifying its correctness would be easy. Unfortunately this posting is too large to hold the proof.

Hard and tedious are different things

[GoClick]

Adding 2 numbers and 25 billion numbers is really not that dissimilar in ways of difficulty, however it still takes a lot longer to do one than the other. The strength of cryptography doesn't come from how hard something is so much as how long it takes to do all that simple math.

Re:Hard and tedious are different things

[puppetman]

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).

Re:Hard and tedious are different things

[mesterha]

It's called non-determinstic polynomial because a non-deterministic Turing machine can solve the decision problem in a polynomial amount of time. However, most people don't use this definition to explain NP. Most people use the equivalent definition that you use a Turing machine to check a solution (certificate) of the problem in polynomial time. The two are equivalent since a non-deterministic Turing machine can just generate all the certificates and check them all in polynomial time.

for instance "Primes is in P"

[joaodk]

check out http://www.cse.iitk.ac.in/primality.pdf

The primality problem, closely related to most public-key algorithms,(since we have to decompose a big composite in two big primes),it is not even a NP problem.

Re:for instance "Primes is in P"

[Anonymous Coward]

The problem the paper references is determining whether or not a number is prime or not. It has nothing to do with factoring, which is the "hard" part of many public-key algorithms. Indeed, if PRIMES wasn't in P, creating a key for use in RSA would be compicated somewhat.

Re:for instance "Primes is in P"

[skeptikos]

Primality testing is in NP. Every problem in P is in NP. What you meant was primality testing is not NP-hard.

for those dense souls..

[Anonymous Coward]

This works just fine for me!

Well...

[Theatetus]

The point of GP joke was "anyone can think of encryption that he (ie, the person doing the thinking) cannot crack."

Sort of like Groucho Marx's "no club that would accept me" paradox.

Hard vs not hard

[kmo]

But some mathematicians are trying to prove that there's really no difference between 'hard' and 'not hard' problems

If they succeed, won't it be humiliating for those mathematicians that have spent decades studying this problem to find it isn't harder than solving 2 + 2.

As I thought I understood it...

[Ayanami Rei]

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.

I completely wrong about this, right?

Re:As I thought I understood it...

[RWerp]

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.

Re:As I thought I understood it...

[mengel]

But that description is remarkably similar to the definition of the nondeterministic turing machine which is basis of the NP set of problems -- it isn't that it tries every permutation in parallel, it's that it *could* do every permutation, and the right permutation takes polynomial time.

So the concern is that a quantum computer is equivalent to the nondeterministic turing machine, as a current boolean-state computer is equivalent to a deterministic turing machine, at which point the NP problems take polynomial time on such a computer.

Re:As I thought I understood it...

[RWerp]

But that description is remarkably similar to the definition of the nondeterministic turing machine

As I said, IANAQCE. Take everything I write with a grain of salt. I wouldn't be surprised if a quantum computer was similar, or equivalent, to a nondeterministic Turing machine. After all, quantum mechanics is nondeterministic.

which is basis of the NP set of problems -- it isn't that it tries every permutation in parallel, it's that it *could* do every permutation, and the right permutation takes polynomial time.

The problem is, how to know which permutation is "right"? This is the advantage of quantum computing, that you don't need to know it beforehand.

So the concern is that a quantum computer is equivalent to the nondeterministic turing machine, as a current boolean-state computer is equivalent to a deterministic turing machine, at which point the NP problems take polynomial time on such a computer.

Even polynomial time can be extremely long, if the order of the polynomial is high.

Re:As I thought I understood it...

[Anonymous Coward]

Hmm.. I've viewed it as follows. It's probably not quite accurate but here it goes anyway:

The more bits you do at once, the harder the result becomes to measure. So at one end you need to bruteforce 2^128 combinations (for a 128-bit cipher) but get the result right and on the other end you just try one fuzzy input and get the answer with so much noise that the probability of it being correct is 2^-128.
However, there's something in between the extremes and you can get away with about 2^64 operations plus overhead. Kind of like a birthday attack. Naturally the benefit goes down the drain by simply using AES-256.

Re:As I thought I understood it...

[Minna Kirai]

A good defense before such attack would be to change the cipher in such a way as to make the corresponding quantum algorithm useless,

So you depend on the security (and novelty) of the cipher, rather than the key? That's called "security through obscurity", and it gets laughed at.

Re:As I thought I understood it...

[RWerp]

I shouldn't have written "A good defense", only "first kind of defense I can think of". Probably wise people know better defences. I did not, though, write that it depends on the security (e.g. secrecy) of the cipher.
Today we use the same approach: when the DES ceased to be secure, someone came up with a new cipher, AES (well, not at once). Some day, AES will cease to be secure. Then we will use other cipher... Is it really "security through obscurity"?

Re:As I thought I understood it...

[Minna Kirai]

Today we use the same approach:

No. It's not the same. Holes in DES or AES arise only because of human error in creating the cipher. (And if you wanted better security, you'd be using Diffie-Hellman anyhow). They are not expected, anticipated, or unavoidable.

But in a hypothetical future with quantum computing, breaking the encryption doesn't rely on discovering a flaw, just going through the work. Fundamentally so much easier.

Like a bridge over troubled waters....

[servoled]

In an article on TechnologyReview.com, Simson Garfinkel spells out the real-world consequences of this mathematical conundrum.

Was anyone else wondering why Simon and Garfunkel were writing about P=NP?

Re:Like a bridge over troubled waters....

[lukateake]

Well, Garfunkel has been out of (meaningful) work for a while now!

This is silly

[hugesmile]

How hard is this?

P=NP
P/P=NP/P
1=N

Therefore, P=NP for all problems where N=1.

See, that clearly wasn't a NP problem!

That still means "either true or false"

[aclidiere]

> Which is not exactly true. It could be true but not provable. It could be false but not provable.

"true but not provable" is still makes the equation true. "false but not provable" still makes it false.
That's the logic. Either true or false, not both; regardless of what humans can prove.

On the other hand, the four possible states in our understanding of the equation can be either:

• Proved unprovable
• Proved true
• Proved false
• Not proved anything yet

Re:That still means "either true or false"

[Anonymous Coward]

>> Which is not exactly true. It could be true but not provable. It could be false but not provable.

> Either true or false, not both;

According to Gödel's Theorem, all formal systems (like mathematics) can be used to construct paradoxes, i.e. statements that are neither true nor false.

Even human language, though not exactly a formal system, exhibits this property. The statement "this statement is a lie" cannot be proven either true or false, because it is neither.

Re:That still means "either true or false"

[Anonymous Coward]

Some people would argue that nothing is true until it has been proved.

Re:That still means "either true or false"

[DavidTC]

NP!=P is not unprovable. The only options are the last three. Although proving that NP is not P is rather difficult compared to proving NP is P...it just takes one example for the latter, whereas the first requires a lot of math.

It's rather akin to claiming 'all people are under 50 feet tall'. It's trivial to prove that false if you can find a person over it. It's difficult, but possible, to map the human genome and prove that humans cannot possibly be that tall. (Assuming you can define 'human' correctly, but you get my point.) And it's currently not proven yet.

There are things that are provable unprovable, but NP!=P can't be one of them.

Re:That still means "either true or false"

[TRACK-YOUR-POSITION]

Proving that P!=NP is unprovable would be proving that it is true. Any algorithm that does NP work in P time is a proof that P=NP. If you prove that no such proof exists, then you've proven that P!=NP. I suppose its possible that P!=NP is unprovable--but you cannot prove that it is unprovable. I think.

Keeping the honest people honest

[mysterious_mark]

Like many security features, no encryption scheme will ever be completely secure, if someone is willing to throw enough CPU cycles at it, they can crack it. The purpose of security is to make it more trouble to steal or de-crypt something than the item or information is worth, not be completely un-crackable since there very well may be no such thing. M

Re:Keeping the honest people honest

[DylanQuixote]

Well, "enough CPU cycles" is usually so high a number that it isn't possible to compute before the end of the universe.

I'll be the first...

[helmespc]

"SCO Claims Encryption Doesn't Exist"

Mod parent up

[Anonymous Coward]

About time someone said it.

Re:MOD PARENT UP

[WuphonsReach]

Of course now we know that there are no lesser of two evils. Kerry and Bush will both screw over the country hard.

I generally vote Republican, but I think Kerry is a good match against Bush. Heck, the Democrats managed to field a number of decent candidates this year.

Still don't know who I'm voting for this year... maybe I'll just take a coin into the voting booth to decide.

read the whole article! the answer is NO

[Anonymous Coward]

yes the article dose not indicate
that an answer is getting close.

Why P!=NP

[26199]

There's no mathematical proof, but consider this: a lot of problems have been shown to be NP complete. That is, if they can be solved quickly (in polynomial time), every NP problem can also be solved quickly (in polynomial time).

Some of these problems would make you a very, very rich person if you came up with a way to solve them quickly.

Nobody has.

That's enough evidence for every-day use, IMO.

Re:Why P!=NP

[Krisbee]

I think you would end up as a very, very dead person very very quickly if you publish a way to crack RSA in a very very short time.

Re:Why P!=NP

[Anonymous Coward]

" I think you would end up as a very, very dead person very very quickly if you publish a way to crack RSA in a very very short time."

You would simply disappear. It has been happening for some time now, in the US.

Don't believe me ? Oh well...

Wow - Where is MIT's Fact checker

[MerlynEmrys67]

I am completely befuddled as to how this article could be posted by MIT, wild inaccuracies (several weeks for a 40 bit key ??? how about a few hours for a 56 bit key) and their description of P vs NP is horrible

Note I made absolutely no comment on how this made it into Slashdot - it is poorly written, inflamitory, and accurate enough that a novice in the field will take it as accurate. Perfect for Slashdot

Not really..

[d_jedi]

If P=NP, then we don't have a set of problems that are difficult to solve, but easy to verify. That means we're left with problems that are easy to solve and easy to verify (useless for cryptography, obviously.. ) and problems that are difficult to solve and difficult to verify (potentially more useful.. but proper decryption becomes just as difficult as cracking the code).

Bah Humbug!

[Anonymous Coward]

Over my cold, dead, plaintext body!!

what nonsense

[jeif1k]

Even if P==NP, that doesn't automatically make all NP-complete problems "instantaneously" solvable. Overly exhuberant theorists referred to problems in P as "tractable", but just because they are called "tractable" doesn't make them so. Conversely, many problems in NP are so "tractable" already as to be useless for cryptography.

But more importantly, there is not a shred of evidence that P==NP, so talking about what terrorists would do if P==NP makes about as much sense as speculating about what terrorists would do if they had teleportation or Voodoo dolls.

Re:what nonsense

[argent]

What if they have teleporting voodoo dolls? What if they have painkillers? Painkillers are much more deadly than terrorists.

Re:what nonsense

[Mongoose Disciple]

But more importantly, there is not a shred of evidence that P==NP, so talking about what terrorists would do if P==NP makes about as much sense as speculating about what terrorists would do if they had teleportation or Voodoo dolls.

Wow, that's scary. They could blind me by jabbing needles in my doll's eyes from thousands of miles away, then instantaneously pop up next to me and steal my pants.

I feel an orange alert coming on...

Re:what nonsense

[cpghost]

Exactly. Even if P==NP, some problems could still be, say, O(n^10000000000000), and therefore practically unsolvable with current and foreeable hardware. And even for O(n^smallnum), the constants could be still prohibitively high or the algorithms so incredibly complex, that they still wouldn't bear any relevance today.

Uhh..

[mindstrm]

After reading the article, it says nothing at all abouut anyone proving that P=NP, or breaking encryption...

just that if they COULD prove this, then encryption would be meaningless.

So.. what's the big deal?

"Some mathematicians are trying to prove"

[arodland]

that P=NP. Of course some of them are. But almost every other mathematician with at least three brain cells is reasonably convinced of the opposite. The article covers the "consequences" of P=NP that anyone who's read an introductory text already understands, but fails to mention that a single NP-complete problem inside P is about as likely as finding a number without Goldbach property. It's just silly sensationalism for the sake of ... um, something about uninformed people that starts with 's'.

Simon and Garfunkel??!?!?

[Anonymous Coward]

eom

Well, that's technically correct...

[PedanticSpellingTrol]

but I think you're either a bit behind the times, or making an incredibly subtle joke, but either I should bring to the attention of the less-informed readers that Fermat's theorem, which states that there are NOT any such powers n>2, has been proven. http://www.pbs.org/wgbh/nova/proof/

Re:Well, that's technically correct...

[CSG_SurferDude]

Personally, I prefer to think it was an incredibly subtle joke.

Also, I'm amazed I got a chain of 9 replies to what was basically a throw away comment I just happened to make before anyone else did.

And, for the record, it stands at 80%funny, 20% overrated. I would have hoped that somebody would have modded it as interesting or informative. ;-)

Misleading headline ...

[wayne606]

Yeah, yeah, if P==NP we're all doomed. So what? If pigeons evolved flamethrowers in their eyes tomorrow we'd be doomed too. That doesn't make it reasonable to write an article headlined "Better bring lots of breadcrumbs when you go out, otherwise there's a chance you will be burnt to a crisp, experts say".

You could argue that, but you'd be wrong.

[mindstrm]

True randomness does exist, it's all around us.

You are probably thinking "If we just knew everything about the starting conditions, we could predict the outcome."

In this universe, however, you CANNOT know the starting conditions to an infinite degree of accuracy. I don't mean "it's difficult" or "we can't do it with today's technology" but that it's fundamentally not possible. No state exists whereby you can know waht you would need to know. Such predictions are not possible.

You can say we don't know enough about quantum mechanics yet or whatever.. but look at something as simple as the Heisenberg uncertainty principle: you cannot know the speed and location of a particle at the same time. The more accurately you know one, the less you know of the other. This coupled with chaos theory means things really are random.

You are correct in that some things can be predicted.. we COULD measure enough about a roulette wheel to predict with a high degree of accuracy what is going on.. same with a coin toss. But look at something like nuclear decay, for instance... and we will NEVER be able to predict when a given atom is going to decay... it's buried in the quantum noise and in the uncertainty principle.

Go read 'Antibodies' by Stross

[Scott Laird]

Go read Charlie Stross's "Antibodies." It's a fascinating SF short story that starts out with a proof of P=NP and goes off from there. To the best of my knowledge, it's not available online anywhere, but it's not too hard to track down on paper.

Or, for that matter, go read anything of his. It's pretty much all good.

P = NP a Wolfram Problem?

[CodeBuster]

Isn't the P = NP proof one of the Million Dollar problems over there at Wolfram Research?

Re:P = NP a Wolfram Problem?

[Anonymous Coward]

No, Clay Institute of Mathematics. One of the millenium problems.

Argh!

[Anonymous Coward]

Yet another poor explanation of the basics of P and NP. You can't talk about a problem like 2+2 being in P or NP. 2+2 is an instance of a problem, not a problem itself. For example, checkers, with an N x N board, is EXP (I think), but you can't say that checkers itself is an EXP problem. Checkers on an 8 x 8 board is an instance of the more general N x N problem.

Short SF story(stolen).

[maysonl]

The last human sat in a room. There was a lock on the door.

Divide check

[td]

P=NP
P/P=NP/P
1=N

Your proof fails when P=0, in which case any value of N will work.

Re:Divide check

[rk]

But, if P == 0, and 0 represents false, the problem is therefore no longer polynomial at all!

Plus 0/0 is undefined, so you can't really say anything about N. I guess that makes N non-deterministic.

Re:Divide check

[div_B]

Plus 0/0 is undefined, so you can't really say anything about N.

Maybe if you took the limit and applied l'Hopital's rule.

Nah, that's just sad. Sorry.

Re:Divide check

[Anonymous Coward]

Here's a simple trick I use to avoid divide by zero when I'm trying to prove something or solve an equation when you start with an equation that uses multiplication.

Using the (admittedly silly) example:

P = NP
P - NP=0
P (1-N) = 0

Either P=0 or 1-N=0 => N=1. This neatly avoids the whole problem of special casing the divide-by-zero case. You can't always use it (if you start with an equation that contains a division to begin with, you need to be sure your assumptions hold before trying to multiply stuff out), but it does avoid the need to justify why certain special cases are OK.

Re:Divide check

[linuxhansl]

Can't resist... The following holds (assuming both N and P are real numbers): P=NP N=1 v P=0 So, if P=0 the equation is trivially true.

Re:Divide check

[hugesmile]

As the author of the silly solution, I am quite embarassed with my divide error.

I remember typing it in a hurry, and I just didn't think it through. You see, at the time, I had to take a P.

Seti is settled then!

[xactuary]

You're saying interstellar radio waves are crammed with all kinds of good stuff (including alien pr0n) but it's all noise to me. Foiled again!

Best Quotation

[Juiblex]

"In practical terms, that would spell the end of encryption as we know it. The Internet would be vulnerable to hackers and computer viruses." Made me laugh :p~~~

Vulnerable to hackers and computer viruses, oh my!

[paco verde]

Best article quote:

In practical terms, that would spell the end of encryption as we know it. The Internet would be vulnerable to hackers and computer viruses.

Yikes! Er, um, wait, isn't that how the Internet is now?

A trivial method

[fireboy1919]

Actually, this has been proven using a direct proof. It will halt every time, given enough time.

Simson Garfinkel

[cyclist1200]

Poor man was only two letters away from being a music sensation...

I'm sure he's never heard that before in his life.

Michael you got an F in automata theory

[McNihil]

Please don't post that kind of headline again.

Actually, the implications are likely real

[po8]

It is considered likely by many that a polytime algorithm for deciding instances of NP-complete problems would also provide efficient keyspace search for cryptanalysis. This is a consequence of the "polytime thesis" (sorry about the crufty link, but I didn't spot anything better offhand: look way down near the end), which states that any real-world problem that has a polytime algorithm has a feasible algorithm. Note that this is both fuzzy and a thesis rather than a theorem, but I am not aware of any counter-examples. So, based on empirical evidence of past discoveries, we might well expect that if we can find a polytime algorithm for keyspace search, we can also find a feasible algorithm.

Consider the problem of deciding whether a number is prime. This problem was recently shown to be in P, but the algorithm given requires around |n|**12 steps in practice. Obviously, this is still not a feasible algorithm. Proponents of the polytime thesis, however, are not concerned: they believe that a low-order polytime algorithm will soon be found. I tend to agree with them.

Re:Actually, the implications are likely real

[ccoakley]

heh. You still have the problem of implementing the "feasible" algorithm. Take triangulation of simple polygons. It was shown that a linear time algorithm exists -- in the decades that have passed nobody has ever implemented it. People typically use a randomized algorithm that is linear expected time with nlogn worst case.

Yes, I know that nlogn is still "feasible", but the point is that even the discovery of an algorithm doesn't imply that it has an easy implementation.

Re:Actually, the implications are likely real

[po8]

Yes, even the discovery of an algorithm doesn't imply that it has an easy implementation. But I know of no realistic polytime examples where the provably best worst-case running time is worse than cubic, or where the algorithm commonly used is dramatically worse in practice than the best algorithm because no one can implement the good one.

The obvious example is LP, where everyone used Simplex for a long time because Kachian's method is such a pain to implement and has lousy constants. However, Simplex was used precisely because its expected running time in practice is small, whereas in practice naive Kachian's tends to achieve its worst-case bound. When improvements on Kachian's method made it more efficient for very large problems, a lot of folks implemented it and switched. You'll see both kinds out there now.

You can implement priority queues in a fairly complicated way to get insertion to be O(1): this constitutes a fairly dramatic improvement over O(log n) to some ways of thinking :-). When I ran into a situation where it mattered, I spent a long time doing this. You do what you've got to do.

Of course, you might correctly point out that the proof that P=NP might be non-constructive, in the sense that it might not come with an algorithm. But wait... Of course, this still doesn't give you a feasible answer.

Funny world.

Mod Parent Down. Mixed up NP and NP-complete

[Dulimano]

As many of his other repliers already pointed out, parent mixed up the NP and NPC (NP-complete) classes. Factoring is in NP. On the other hand, it is very-very unlikely that it is NP-complete (more precisely NP-hard), because this would imply that NP=co-NP.

What does NP=co-NP mean, you ask? You can consult http://en.wikipedia.org/wiki/Co-NP for the details. But the important point is that it is just as unlikely as P=NP.

Re:Mod Parent Down. Mixed up NP and NP-complete

[mesterha]

What does NP=co-NP mean, you ask? You can consult http://en.wikipedia.org/wiki/Co-NP for the details. But the important point is that it is just as unlikely as P=NP.

Why is it just as unlikely? Would there be any interesting consequences if NP=co-NP? It doesn't help resolve the P=NP question.

Re:Mod Parent Down. Mixed up NP and NP-complete

[Dulimano]

Why is it just as unlikely? Would there be any interesting consequences if NP=co-NP? It doesn't help resolve the P=NP question.

I'll give two different answers. Neither will be fully convincing.

1. Some of the most interesting mathematical theorems have this form: "The existence of an object and the nonexistence of another object are logically equivalent." Linear algebra and linear programming duality, the Nullstellensatz and the theory of matchings are nice examples of this. NP=co-NP would mean that we automatically get such theorems for any possible NP search question, like the existence of cliques, satisfying assingments and so on.

2. Both P=NP and NP=co-NP are stronger versions of "the polynomial hierarchy collapses" statement. Speaking in metaphors, P=NP says that "every imaginable bounded-round two-player game is easy to play". NP=co-NP says that "every imaginable bounded-round two-player game is as easy as solitaire". The collapse statement says something like "many-round two-player games are no harder than k-round two-player games, for some fixed k." Even this much weaker statement is considered very unlikely by computer scientists.

P, NP, and something in between

[Anonymous Coward]

Last I remember of algorithm class back in college was this:

1. We don't know if P==NP or P!=NP.
2. If P!=NP, then there exists a class of problems, FP, that lie between P and NP. That is, this set is a proper superset of P, and a proper subset of NP. This has been proven (don't know the source, sorry).
3. Encryption algorithms in use today all (I think) fall under this set FP.
4. Encryption algorithms based on NP are, for some reason, easy to crack (Kleinberg didn't go into too much detail about this).

Basically, P has polynomial running time, NP has exponential running time, and FP has something of the sort of O(N!) running time.

I'll Tell You What The Consequences Are

[s5fb29330]

The consequences are that I won't be able to safely browse Slashdot from work over an ssh tunnel without getting in trouble, anymore.

I've had secure, non-snoopable access to the Internet for my entire professional life. If I actually have to start working I don't think I'll be able to handle it.

Re:I'll Tell You What The Consequences Are

[RedCard]

My favorite little gem from this article:

"...In practical terms, that would spell the end of encryption as we know it. The Internet would be vulnerable to hackers and computer viruses... "

heh.

While we're OT, here's a little piece of fiction that I encountered on kuro5hin once, about what would happen if a large corporation were to locate an NP-oracle.

I'm down with OTP

[blunte]

You down with OTP?

Random Thoughts

[jefu]

There is a definition of random that seems fairly convincing to me (and to others). In that definition a bit string is defined as random when the smallest program (turing machine, lisp program) needed to compute it is longer than it is. See Greg Chaitin's work for more info, or this wikipedia page . And this kind of work seems to have some practical implications for cryptography as well.

Re:Random Thoughts

[loqi]

IANAC, but this makes a sort of intuitive sense to me. However, it seems like there's still something arbitrary involved. You mention a lisp program, so are you then including the code for the lisp interpreter? The microcode on the CPU?

Also, wouldn't there have to be "random" bit strings which turn out to be easily computable (i.e., the value of a polynomial at some X)? This makes me think that I'm missing something in the definition of random here.

Re:Random Thoughts

[jefu]

Yup, there is something arbitrary, but it turns out not to matter much (just a constant factor, if I remember correctly). The ultimate representation though is not as (say) lisp, but as a TM.

And a "random" bit string that turns out to be easily computable isn't really random, is it? (And since this was brought up in a crypto context, think crypto here.)

Breaking news!

[Silik]

How can a big slashdot story /possibly/ be that "Mathematicians are trying to determing P ?= NP"? That's like the breaking news, "SCO is suing someone"!

Oh.

Nevermind.

Some critical notes on the article

[Stygius]

(1) The terminology is misleading. The author speaks of "NP problems" without further qualification, and calls these problems "hard problems". NP problems, in the sense of problems belonging to the complexity class NP, however, are not "hard" in general, because all problems in P belong to NP (this is a trivial theorem). And no problem has been shown to be in NP but outside P. He might be referring to the so-called NP-hard problems, which formally are the problems at least as hard as the hardest problems in NP. But this wouldn't make much sense, since he doesn't bring up the NP-complete problems (the only NP-hard problems we know of inside the class NP) until the end of the article.

(2) Suppose P=NP. I, for one, would see this to be a good thing. The gain in the field of e.g. combinatorial planning and scheduling would be enormous, far outweighing any loss in the field of cryptography.

Amazing

[networkGhettoWhore]

Simon of Simon & Garfunkel was indeed a math teacher, but a crypto expert? I don't think so.

http://www.superseventies.com/1976_9singles.html

Slow research?

[Anonymous Coward]

From my perspective, we are no nearer to solving the problem now that we were when bell-bottom pants were cool.

Meaning no closer than we were in 1998?

Re:What tasks require high-speed interconnects?

[Bruce Perens]

I learned about quantum encryptuon, and then I couldn't use it any more :-)

Bruce

Math is not the "end of encryption"

[Anonymous Coward]

IANAC (I am not a cryptographer) but it seems to me there is an important point to be made. There are math-related encryption algorithms/schemes and there are non-math-related ones. RSA (or any other algorithm that relies on factoring huge numbers) are at the mercy of fundamental math advances. If someone figures out how to factor giant numbers with ease, things will be rocked hard for sure, but you have to realize that not all encryption is based on math. DES, Triple DES, and AES are widely used "bit twiddling" algorithms. They massage the data at the bit level, they don't "calculate" encrypted values. It's just a serious of steps you go through designed to be one-way. You could be a factoring wizard and it would not help you at all breaking/exploiting those algorithms. Now I did RTFA and if you had a machine that _could_ try all possible keys simultaneously, then all bets are off. Poof, brute force becomes a single click attack. But just because someone discovers a new math trick or some computer can power through large factoring problems, things don't _all_ come tumbling down. Cryptography had to be fluid. Algorithms and key lengths are designed to be good enough for the length of time they need to encrypt the data. I don't think any serious cryptographer thinks there has ever been (or will be) an implementation that can truly be permanent. Breaking encryption isn't "impossible" it's "impracticle". By that statement, yes I realize that I've just lumped every second that has ever existed in the entire universe (undoubtedly you've heard the stories of how long it would take to brute force every possible key of x-bits for y-algorithm at z keys per second) into the "impractical" bin, but you have to admit, timescale aside, brute force is always "possible". We just need to stay well ahead of the curve of what's practical to use. I think it's a good thing different algorithms/schemes/etc are used in various places. It helps keep all our eggs out of one basket.

Re:What tasks require high-speed interconnects?

[Bruce Perens]

And I'm sorry that my spelling is entangled today.

Bruce

Time to hurry up

[SirLestat]

"with a $1 million prize offered to the person (or machine) that can solve each problem"
I better find the solution before my computer do or I won't get anything !

Re:What tasks require high-speed interconnects?

[Anonymous Coward]

Bruce, every time you try to make a joke - another kitten is murdered. Please stop.

You arrogant jerk

[M.C. Hampster]

Only on Slashdot would such a comment be moderated "Insightful". I guess the reason that any comment that insults the majority of the populace gets modded up on Slashdot is the social insecurity felt by the moderators. Does it make you feel good to insult a huge portion of the populace? Does it make everyone feel so much smarter and better than all those evil "jocks" that picked on you in high school?

Grow up. Nerds, geeks, computer experts are not the only intelligent people out there.

Yeah, mod me as flamebait, whatever.

Re:You arrogant jerk

[chill]

It was meant to be humor, but with a point. Yes, it was an exaggeration, but it emphasized what is an issue I perceive with many people I have met.

A profound ignorance of math and science beyond the basics.

Thus, it really counts as both insightful and funny.

Re:You arrogant jerk

[BryanR1977]

You've obviously never worked a helpdesk :) Do that for any lenght of time and you will begin to tink that there are WAY to many stupid people out there. Unfortunatly you never talk to the ones that don't need help.

Re:You arrogant jerk

[Anonymous Coward]

It WAS interesting to see the foundations of a simple equation, people take for granted the foundations of current mathmatical logic. if that "theory" was never proved then the foundations of math/science itself would have been violated. math and science both are based on the fact that even the most simplest of "truths" should be either proved or disproved.
it's too easy to say "well i learned that in school" and never have to question it. think for yourself.
Theory is in quotes 'cause it's funny to call it one nowadays.

BFD....

[drew]

From the article.....

This is not any more news now than it was "when bell-bottom pants were cool."

Quantum Chosen-Plaintext Attack ?

[Mad Bad Rabbit]

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.

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:

• Encrypt a chosen plaintext P1 and get a cypertext X1
• Take an unknown cyphertext X2, and replace X1 with a superposition of X1 and X2
• Step backwards through the encryption, to get a superposition of P1 and P2 (the unknown plaintext)
• Use the known value of P1 to get P2 from the superposition

(Or is the above stupid and wrong, and I'd need an actual course in quantum physics to even understand why?)

Re:Quantum Chosen-Plaintext Attack ?

[RWerp]

Step backwards through the encryption, to get a superposition of P1 and P2 (the unknown plaintext)

If we could do that, we wouldn't have to do anything else. We'd just take the cyphertext X2 and "step backwards". Besides, it doesn't give us any clue about the key, which is the goal of the attack.

Re:Quantum Chosen-Plaintext Attack ?

[Vengie]

I spot a troll! I mean...informed reader? I haven't seen anyone else use the terms "bra" or "ket".....so you strangely have some knowledge that doesn't belong on slashdot. ;)

-b

What the heck?!

[Grendel Drago]

I've read this three times, and it gets more confusing with each one. Perhaps you're using a weird definition of 'trivial'---from what I can tell, you're saying that it's easy to just run any particular program to see if it halts or not.

So...

1. Run Program on Input.
2. Wait an infinite amount of time.
3. If Program is still running, return DOESNT_HALT. Else, return HALT.

"Wait an infinite amount of time", to me, is a nontrivial step. Were you seriously suggesting otherwise?

--grendel drago

Re:You ignorant jerk

[Anonymous Coward]

don't bash that post just becuase it's right and while it is a little too harsh it is right. The majority of people don't know hardly any math. Math takes a lot of work to understand and most people are not willing to do it. And seriously if you spend your time studying math and science instead of just bashing heads playing football, you are smarter and better than the jocks. People who are just jocks don't create cellphones, or computers, or medicine. Give the people who study math and science the respect they deserve and don't say the jocks are their equals becuase they arn't. It's not social insecurity, it's well earned pride, and while it's obvious that computer experts are not the only intelligent people out there and there are even some smart jocks, the majority are still afraid of math.

Re:Factoring is another NP problem -- NO! - YES!

[Anonymous Coward]

The above post should be moderated as -1, Wrong.

It is trivial that factoring (well, technically speaking, the corresponding decision problem) is in NP. It is not known whether it is NP-complete or not and it is not known whether it is in P or not.

Mod down parent pls

[Anonymous Coward]

Hello... Heisenberg's uncertainty principle... Provable that some things are unknowable, and the definition of randomness is unpredictability.

Blech.

it may have been covered but...

[riprjak]

... it seems to me that most forms of modern encryption actually P problems already.

"If you can search thoroughly you will find the book" from the article.

Their solution time is comparable to their complexity; assuming you can try all possible combinations, you will find the answer... (unless you get a false positive and decrypt plain, readable yet different text)??

I understood that encryption relied upon it being complex enought that it is computationally infeasible to "crack" in a short enough time for the retrieved information to be useful. You increase the solution time by increasing the size/complexity of the key, a polynomial relationship as far as I can tell...

Or should I have paid more attention in math lectures???

err!
jak.

Re:it may have been covered but...

[vidarh]

Their explanation is crap. I'm sure I'll make tons of mistakes and get flamed to death by people who actually paid attention when this was covered at school, but here's an attempt at a more complete explanation...

A "P" problem is a decision problem (a yes/no question essentially) that can be solved in polynomial time: Worst case for searching for a book in a finite collection is a multiple of the worst case time it takes to search one book in the house and the number of books - a straight linear search of all books in the house.

An "NP" problem is a decision problem where a solution can be verified in polynomial time. If P=NP then any problem where a solution can be verified in polynomial time can also be solved in polynomial time. Solving the problem here refers to finding the answer (is the book I seek in the house?) while verifying the solution refers to controlling that the answer is correct.

An P problem is also an NP problem - if you can solve a problem in polynomial time you can by definition also verify an answer in polynomial time: solve the problem, and compare the result with the proposed answer.

However the problem is that while it is thought that not all NP problems are also in P, it is not proven, and may be unprovable. But we don't know which, and don't have a simple way of verifying whether an NP problem is in P or not.

This is what sucks for encryption. Encryption currently rely on it being hard to solve a specific problem but easy to verify the solution (the key) by trying to decrypt an encrypted message, and if it fails (or presents us with gibberish) we know the key presented to us was not the right solution. This can be done in polynomial time

However, it only protects us because nobody (at least as far as we know) can solve the problems posed by the encryption methods in less than exponential time. Exponential time to solve the problem means that the effort could for instance (but not necessarily) double for each extra bit added to the key. The general rule is that the effort is 2^p(n) where p() is a polynomial function of n, and n is the size of the information space of the problem. The problem asked by encryption is essentially "will this key slotted into this encryption function give the original message?"

Let's go back to the book search, and twist it so that it fits the situation with encryption now. In the book search, the question is "does the book I seek exist in the house?". In a normal world, this problems worst case solution increases in effort by a constant factor for each extra book added, but to make it comparable to encryption we need to complicate the problem.

Imagine a crazy world where the best way we have to look for a solution to the book problem is to compare all the books with eachother and a paper strip with the title of the book we want, and only when we happen to compare the paper slip with the right book have we found the solution. In that case, each time we add a book, the problem increases (the number of direct relationships between n entities n(n-1), where n in this case would include the paper strip with the solution) but where we can still verify the final solution by comparing the book we finally found with the paper strip.

The kind of twisted scenario above is what most encryption algorithms are today: A problem that gives protection only because we don't know how to quickly solve it, but where there could be a simple way of solving them right around the corner. If P=NP all encryption algorithms that depend on this relationship can be broken in polynomial time.

However even proving that P and NP are not equal only means that "safe" encryption using this relationship is possible, not that current algorithms are safe - to prove that an algorithm is safe you'd need to separately prove that the problem can only be solved in exponential time. But a proof that P!=NP would give us an indication that it might at least be possible for such a proof to exist, as proving that the problem posed by an encryption algorithm can only be solved in exponential time would at the same time prove that P!=NP.

Re:it may have been covered but...

[riprjak]

:) Thanks for taking the time to respond...

Re:Vulnerable to hackers and computer viruses, oh

[elhaf]

Really, what a gem. I was about to post the same thing when I saw your post. It seems like that article was written by a first-year computer science student. So many facts misstated. And it's all just speculation anyway, because the "scientists" in question just broke MD5, not P=NP?. And prime factorization hasn't been proven NP-complete (because it probably isn't). Yes, it's in NP, like all of P, but that doesn't make it "hard". Also, NP-Hard is not exactly the same as NP-complete anyway. Of course, the biggest error that they make is saying that P=NP can be proven either true or false. Some theoreticians believe the question may actually be independent of the axioms of mathematics. This kind of crap coming out of MIT is just wrong.

Proof of provability in this post

[moultano]

Suppose P?=NP is unprovable.
The existence of an algorithm to solve an NP-complete problem in polynomial time would constitute a proof that P=NP.
Therefore there can be no such algorithm.
Therefore P!=NP.
This is a contradiction.
Therefore P?=NP must be provable.

Re:Proof of provability in this post

[Anonymous Coward]

Suppose the existence of the supernatural is unprovable.
The existence of a supernatural event would constitute a proof of the supernatural.
Therefore there can be no such event.
Therefore there are no supernatural events.
This is a contradiction.
Hence, the (non)existence of supernatural events must be provable.

Re:Proof of provability in this post

[moultano]

The existence of a supernatural event would constitute a proof of the supernatural.

I'm not sure this is true. Supernatural events are hardly something that we can describe in formal terms, in particular the terms that we using to write proofs.

There is most likely a logical flaw in what I posted since this logic could be used to show that any statement of a formal construct's existance if provable. I'd be interested to see it hashed out if you care to take the time.

Re:Proof of provability in this post

[Anonymous Coward]

The existence of an algorithm to solve an NP-complete problem in polynomial time would constitute a proof that P=NP.
Therefore there can be no such algorithm.


What if there is such an algorithm but it is unprovable that is really works or that it requires only polynomial time?

The Simpsons already showed us the truth here

[Anonymous Coward]

If you'll recall the episode where Homer gets sucked into the 3 dimensional world, one of the equations in the background is "P=NP"; if a sight gag in The Simpsons isn't credible proof of something, I don't know what is.

The End of Light?

[Various Assortments]

Researchers have shown that simply throwing a thick blanket over a subject can result in a Denial of Light attack. Pundits have suggested that with this knowledge, there is no longer any point in using light any more, when it can be denied so simply. Experts are working overtime to come up with a solution.

Nop Last person encrypts something

[Anonymous Coward]

I would encrypt a Message with the most junk filled encryption I could think up.

The Message would be simple

Yep you are reading this If you think this is something I did not want you to read good. If you are a history studing thing who has cracked this encryption. Good at least something knowns that I died alown. And if you had looked to the /. records you would not have wasted you time cracking this. At least something less can feel what it is like to completly stuffup a few days of there life.

At least I would have the last Human practical joke if some thing found it.

Just hope they try it find paper based /. records.

P=NP

[Uncle Jimmy]

P = NP

Divide both sides by P.

1 = N

Clearly, N = 1. Next?

Re:P=NP

[Anonymous Coward]

Division by zero error.

MOD PARENT UP

[finkployd]

Few people know that Ashcroft was once a crusader for personal freedom and privacy and took a stance against the Clipper Chip. Oh course, NOW he is a total fucktard who wipes various parts of his body with the bill of rights, I guess prolonged exposure to government does that to people.

Incidently most of the geeks I know (myself included) who voted for Bush did so because at the time he appeared to be the lesser of two evils. Al "Mr Clipper Chip" Gore certainly was no friend of the technology industry or anyone interested in privacy while he was VP.

Of course now we know that there are no lesser of two evils. Kerry and Bush will both screw over the country hard. Let's face it, nobody likes either of these two failures. They just hate the other guy enough to pretend to like one of them. It is a sad say in the US when these two are the best options we have.

Finkployd

Thats serious spin on events

[dilvish_the_damned]

I see, so a couple brilliant math guys made a bet some time ago that it 'would'/'would not' not be proven that P does not equal NP by the end of the century. And due to the fact that its not been proven, this means that its possble?
I dont see that. I submit this only means that it hasnt been proven that its not possible, and further that all of our assumptions still hold.
Once you get passed all the fear this article tries to incite by way of background and inference; this article, at the meat of it, only suggests that nothing has changed in 30 years.

But isn't proving P!=NP proving P==NP?

[Joseph_Daniel_Zukige]

I never could quite figure that out.

P==NP

[Joseph_Daniel_Zukige]

But only if you live forever.

P Complete

[U96]

One important class of problems which should be included in this discussion is the class of P Complete problems.

These are problems for which there exists a polynomial time reduction to the P Problem, which is the ability to optimally distribute P straight pegs in U linearly arranged slots (where P less than or equal to U), so as to maximize the distance between pegs.

For example, for (P=2, U=5), the optimal solution is a peg at the first and last slots. For (P=3, U=5), optimal is U0, U2, U4, etc.

It can be shown that any problem which can be reduced in polynomial time to straight men at a row of urinals is P Complete.

I stand corrected

[hotspotbloc]

You're correct and I should've known better. From Mathematics is not...:

Mathematics is not a science, in the proper connotation of the word. Some thinkers see mathematicians as scientists, regarding physical experiments as inessential or mathematical proofs as equivalent to experiments. But they themselves do not see mathematics as a science, since it does not require experimental test of its theories and hypotheses. In either case, the fact that mathematics is such a useful tool in describing the universe is a central issue in its philosophy. But in any case, mathematics is essential to science, being its most important function the role it plays in the expression of scientific models.

Example of conjectured non LOGSPACE transform?

[ccoakley]

By the way, since you seem knowledgable: Is there any NP-C reduction that is conjectured not to be a log space (LOG) reduction?

From what I remember, most polytime reductions are trivially in LOG. I am also aware that LOG!=P is open, but it is conjectured that it is true.

Re:Example of conjectured non LOGSPACE transform?

[CodeBuster]

I dont know, however if you are interested in the details then I would start with a search of the ACM transactions papers on the subject. They contain many of the recent research results in these areas:

ACM

Solution for P=NP

[Anonymous Coward]

If P=NP, then N=1!

Re:Solution for P=NP

[Anonymous Coward]

Or P=0.

Your point well taken...

[PaulBu]

... but I still think that it was not what the grandposter had in mind! To my mind, "trivially decidable" means "computable" (note the "trivially" part!), and I do not think it is that trivial to get the answer to the halting problem -- yes, someOne with an infinite (though countable) number of computers and infinite -- either (countable) number of clock cycles or (continuous) amount of time on its hands, I do not know which is required -- can know all the answers. But that entity is usually referred to as "God" and its existance is a bit beyond the scope of this discussion... ;-)

Paul B.

No, you can't

[r6144]

Disclaimer: IANAQCE.

To be simple, we suppose the encryption is done by multiplication by 3 (X1=3*P1), then it can be done by adding P1 to itself left-shifted one bit, in which the shifting can be omitted (it doesn't do anything real to the bits) and replaced by some crazy bit-twiddling. After it is done you will see not only X1 but also a copy of P1, and possibly some intermidiate results.

Now it is difficult to get rid of the P1 (i.e. make the bits zero) using only reversible operations. If you don't do that, when mixing X2 and X1 you will also need a correct P2=X2/3 to mix with the P1, before the reverse operation will work. So you see that it isn't easy to reverse things in QC, whether it is multiplying by 3 or the DES transform.

A bit OT, but no less interesting point...

[pVoid]

I don't remember whether it was an Arthur C. Clarke invention or not, but there was a way to have a perfect one time pad...

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.

Re:A bit OT, but no less interesting point...

[gordlea]

Just record the random data, then as long as i have some idea of when you wrote the message, i'll just brute force it (if he encrypted it at 12:00 would it work, if not, 12:01, etc..)

Even if the data changed every ns it still wouldn't be very secure (assuming i have access to the sat signal)

Re:A bit OT, but no less interesting point...

[ixmo]

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.

As long as both listen to the same satellite(s) at the same time.
-> Sender and recipient can't be more than a couple of hundred miles away.

ix

Re:A bit OT, but no less interesting point...

[DavidTC]

You've just turned a OTP into something that can, and will, be decrypted. And never, ever, ever, ever, ever talk about 'sheer amount of data...will make it prohibitive'. Haven't you paid any attention to the world? We eat sheer amounts of data for brunch.

This is another psuedo-OTP solution. Psuedo-OTPs are not OTPs. What's worse, is that's a psuedo-OTP via obscurity.

Re:A bit OT, but no less interesting point...

[pVoid]

What's worse, is that's a psuedo-OTP via obscurity

Just as much as SSH is a encryption protocol by obscurity: you need to hide the key. If the synchronization timestamp of the communication is hidden, it is the best OTP you can ever get. It comes down the basics of cryptography: you need at least one secret to protect. And that's the weekest link in the whole chain.

Sheer amount of data

is the only reason why SSH and any type of encryption works today: because it would take billions of years to crunch through the possible data set (of a single 128 bit key).

So if a satelite is broadcasting at say 1 MB/s, purely random data (not pseudo-random), and you want to decrypt a 1 meg file by brute force:

First off, you can't just try and decrypt the first 10 bytes to see if you've got the correct sequence: it's an OTP, so only the first 10 bytes might be right, the rest might be wrong.

As a corrolary to that, you have no real way of verfying that what you have decrypted is that actual OTP, since you could coincidentally arrive on an OTP that reveals just parts of the plain text, but not all.

Second, in just one hour 3.6 Gigs of data is generated... that means you need to decrypt the 1 Meg file 3.6 billion times. Assuming you have recorded the stream.

It's as good an OTP as you'll get man.

Re:A bit OT, but no less interesting point...

[DavidTC]

First of all, it's obviously not as good an OTP as someone will get, because, duh, a real OTP is better.

As for decrypting part of it...that's exactly how you'd do it. You keep decrypting it until the whole file seems to make sense.

And I have to point out we currently have places storing petabytes of data.

That idea might make sense if we could somehow transmit at a septillion times as fast as we currently do. Right now, it would be trivial to store entire days worth of data, or more, as fast as we can possible transmit. And, no, people aren't going to use some sort of goofy encryption that makes them wait a week to decode their data. Might as well just put the OTP on a CD and fly across the country with it.

And note that the faster we transmit, the harder it is to syncronize on the signal and receive it. At some point the price and technology level is prohibitive. So you can't solve the problem by just making it faster and faster. (And even if you could make it near infinitely fast, you'd then find the time-stamp is getting rather long., so you gain nothing over using an actual OTP.)

Not to mention, even if the idea could work as of this moment, we're getting bigger and bigger hard drives, whereas we're not getting better satellite transmission. We're fitting more in via compression, but by defination you cannot compress random data. 'How much data can we send down from satellite' is limited, because there's only so many frequencies we can use. Whereas storage space show absolutely no signs of stopping.

And this, again, is not a OTP. It's a psuedo-OTP, which is a 'one time pad' generated from something else. In this case, the actual pad is easily available in stores, and you're trying to confuse the issue by making it hard to find. Well, it may, indeed, be hard to find. But it is not impossible, and thus, by defination, what you have is not a OTP.

And there's the rather goofy problem that you've now got a timestamp accurate to a millionth of a second that you have to transmit instead of a pad. Have fun reading 12 digits over the phone, and hope the line isn't tapped. Want to up it from a MB/s? Well, you just made the timestamp longer.

What's that you say? You're not going to read it over the phone, you're going to carry it in person? Why the hell don't you just carry the pad, then?

This is classic 'Let's make a OTP encryption taht doesn't involve keeping the entire pad secret and transmitting the entire pad.'. Those aren't OTPs, and thus they are not unbreakable, and thus there's already plenty of perfectly good encryption out there to use instead, ones that have been mathmatically proven to require more energy to brute-force than our sun will ever give off. No need to invent more while mumbling to ourselves 'It's like a OTP'. Just use 1024 bit symetrical encryption and God himself couldn't decode it before the sun goes out.

Re:A bit OT, but no less interesting point...

[gumbi west]

The difference between what you are talking about and a one time pad is that a one time pad is completely unbreakable. Yours can be broken, given enough time.

Re:A bit OT, but no less interesting point...

[pVoid]

Ah, the clarity man. Thanks for answering so clearly.

I'd mod you up myself if I had points, and had I not posted...

Re:A bit OT, but no less interesting point...

[pVoid]

By chance, I found the article about this...

Sorry it has a registration...

Watch out for confusion

[carlossch]

NP is not equal to NP-Complete. I know this is a common misconception, but it helps not to spread the confusion.

Factoring _is_ in NP. What is not known is whether factoring is NP-Complete or not. A problem is in NP if the corresponding decision problem is in P. In other words, if you can check if a solution for a problem is valid in polynomial time, the original problem is P.

NP doesn't mean non-polynomial: it means non-deterministically polynomial, which means you can build a non-deterministic Turing Machine that solves the problem in polynomial time.

It is easy to see that NP is a superset of P. What is not proven yet is if it is a _proper_ superset, that is: if there are problems in NP that aren't in P.

NP Hard vs NP Complete

[Charles Dodgeson]

Unless I've understood things incorrectly (a very real possibility), I believe that there is a class of NP-hard problems which are provably not N. It is the class of NP-complete problems which may or may not be P. We certainly need to add the the repetoire of PK algorithms, and ideally we should try to find some among the NP-hard problems.

Of course, I could be very wrong about this. It's been decades since I studied this stuff.

Misleading...

[VE3MTM]

I saw this article and thought, "WHAT? Someone proved P=NP?". I was disappointed.

As it is, I see nothing enlightening about this article whatsoever... As people so often say here, "nothing to see here, move along".

Re:What tasks require high-speed interconnects?

[UnknowingFool]

I do believe that this is the first time I've been razzed by someone of your stature. I bow to your four digit ID.

I'M NOT WORTHY!
I'M NOT WORTHY!
I'M NOT WORTHY!

the Grover algorithm

[r6144]

Actually a QC can do simultaneous computations by using superpositioned states, although getting the desired result out can be challenging.

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".

Re:the Grover algorithm

[RWerp]

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.

Double, or raise to the power of two?

Re:the Grover algorithm

[r6144]

N=2^n where n is the key length, so doubling the key length is enough.

The End of Encryption

[wetdogjp]

In practical terms, that would spell the end of encryption as we know it. The Internet would be vulnerable to hackers and computer viruses.

Oh, well, then I guess we're still safe for now...

Re:What tasks require high-speed interconnects?

[Bruce Perens]

It was meant in good nature. I was just trying to make a few quantum-mechanical puns.

Bruce

Re:What tasks require high-speed interconnects?

[Bruce Perens]

Geez. I have to teach Mozilla to not fill in "What tasks require high-speed interconnects?" every time I make a posting. Duh.

Invalid questions...

[Otto]

Normally, I'd agree with you. However, P?=NP is a slightly different kind of problem, as it's almost a metaproblem. It's a problem about other problems.

See, unlike your example, the terms are well defined in something we do know about. Essentially, it breaks down to the fact that people came up with problems to which nobody could find a good answer to. So instead of solving them, which was proving inordinately difficult, they decided to start describing them differently.

This led to grouping them, which eventually led to classifying them, which eventually led to a new kind of problem since they couldn't prove that their classifications actually had any real meaning. They couldn't figure out how to prove P != NP.

So my point here is that P and NP are not really terms that are poorly defined. They are extremely well defined, mainly because nobody could work out how to really get good solutions to the problems that they are describing in the first place.

Basically, P and NP are extremely well defined sets and there's rigorous proofs to show that if an NP-Complete problem turns out to be P, then P=NP. The question does have meaning, because if the answer to it could be determined, it would either eliminate or validate the classifications that have been setup to create the terms P and NP in the first place.

It may not be provable, but either those groups have real significance as they are described or they do not. There's no real in-between state there.

Factoring is not known to be NP-complete

[JoeBuck]

Because factoring is not known to be NP-complete, there might turn out to be a polynomial-time algorithm for factoring, but no polynomial-time algorithm for NP-complete problems. If this were true, RSA might be broken, but other public-key algorithms might still be strong enough.

Re:Factoring is not known to be NP-complete

[jfengel]

True. But factoring is easier to explain in a short example than TSP or (God forbid) 3-SAT.

Re:Factoring is not known to be NP-complete

[sangdrax]

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.

Simson Garfinkel?

[Ferzelic]

I think my parents had some of their albums...

Re:What tasks require high-speed interconnects?

[UnknowingFool]

I got it. It's just nobody as notable as you has ever responded to one of my comments. The only brush with fame I've ever had was when I met President Clinton one time. I even shook his hand. Knowing what I know now, I should have washed my hands afterwards. :)

The Ultimate Encryption Scheme

[strannik]

.....quantum rot 13 plus a secret handshake!

Obligatory Futurama Reference

[ari_j]

There's a scene in Futurama (I forget the episode, sorry die-hards) where we see a closet with a bookshelf. On one of the shelves are two books, entitled "P" and "NP". Evidently, in the year 3000 we'll have proven that they are separate problem spaces.

Re:Obligatory Futurama Reference

[strider44]

I love the futurama in-jokes. My favourite is Klein's Beer.

... and here is a proof of its unprovability

[Anonymous Coward]

http://journal-ci.csse.monash.edu.au/edit/uploads/ argall01/PNP%20Proof.txt

Notoriety

[Bruce Perens]

I try not to take myself that seriously. I'm afraid I can't agree about Clinton, though. I'd smoke Clinton's damn cigar myself if it would get him back in office. Bush really scares me.

Bruce

Re:Notoriety

[UnknowingFool]

What I meant was not his personal character but what his late-night activities (especially with cigars) :)

Are they any closer...

[Kjella]

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. ...to building a quantum cryptography computer that can scale? Adding qubits isn't like adding transistors, all the bits need to be in a shared quantum state. Generating one of thousands of bits is going to be a much harder problem than a handfull.

Kjella

umm....

[Anonymous Coward]

Simson Garfinkel spells out the real-world consequences

Shouldn't that be Simon & Garfunkel? :)

We know P != NP

[rpiaggio]

We just don't know how to prove it. (Or IF we can prove it).

This russian guy Or NP ~ = P

[RedLaggedTeut]

There was this paper/algorithm by a russian guy.
I downloaded it once but was too much lazy and stupid to understand. And I doubt that you can still find it, because either it is too valuable or stupid to still be online.

It was an algorithm to do with MST and triangles I think to solve a problem considered NP-complete.

Now I guess he might have made a mistake in his algorithm, but what if it turns out that it works most of the time, so you can solves 99% of the cases of a specific NP problem with a good heuristic that is in P ?

After all, for some travelling salesman problems, some parts of the solution are obvious.

For PKC, this means you first have to check your keys whether they are easy to crack, and in fact I've read that for RSA/PGP, keys should be chosen smartly. However, where does the smartness end ? Maybe knowing all weak keys IS in NP~-P.

Re:This russian guy Or NP ~ = P

[PantsWearer]

Now I guess he might have made a mistake in his algorithm, but what if it turns out that it works most of the time, so you can solves 99% of the cases of a specific NP problem with a good heuristic that is in P ?

If it doesn't solve 100% of the problems, nope. Doesn't prove a thing about P's relation to NP. Assuming his algorithm is correct, it's just a clever algorithm.

Of course, it also might be the case that he just managed to prove that this problem was never really an NP to begin with, much less NP-complete. If it was only assumed NP and he managed to completely solve it (100% of the cases) in P time, then it has no effect on the group of NP-complete problems since you'd be unable use this MST-based solution for all NP-complete problems.

After all, for some travelling salesman problems, some parts of the solution are obvious.

Again, if parts are obvious, but the whole is not, this has no effect on the P/NP relationship. Heck, given a set of cities in a line, the TSP can be solved with a Nearest Neighbor solution (O(n^2)), perfectly, every time. Or even more silly, given only two cities, the solution is obvious. It's the general solution for all cases that's the big deal. If I remember right, to guarantee a perfect TSP solution, it's along the lines of O(n!) or possibly O(n^n) though I believe the first one is correct.

Mostly wrong

[Paul Crowley]

The OTP is a special case.

If we find an efficient way to solve NP-style problems, then conventional keyed encryption (eg AES in EAX mode) falls too, because we can efficiently search for the key that makes the plaintext make sense (and MAC correctly).

However, P?=NP doesn't directly bear on these problems, because they are not organised in families of increasing problem size, such that there are always larger and more difficult problems.

And if there's a way of factoring large numbers whose compute time grows on the fiftieth power on the length of the number, then it wouldn't in practice make any problem for those using RSA, even though it brings the problem into P.

Quantum computing still dangerous

[Llurien]

I agree that quantum computing will simultaneously benefit cde making and code breaking, so it would seem it balances out. However, in all likelyhood the first decade of quantum-computing will be mostly in the hands of government and possibly big corporations, because until someone figures out a low-cost way of making quantum-computers, they will be the only ones able to afford it. That means that during that time, they will be able to break just about any encryption that you can generate. Echelon++, here we come !

Offcourse, all this is not a problem if you trust your government (and everyone in it) not to misuse their power.

Ask Homer Simpson

[RandySC]

"If something's hard to do, it is not worth doing."

So, theoretically there is nothing between hard and not hard problems. Is there an assumption somewhere in there that you have infinite computing resources and an infinite number of monkeys to monitor them?

Try telling this to students to students that just failed an engineering, science, or math test:)

Yes, factoring is in NP

[ashar]

Of course factoring is in NP. It's just not (known to be) NP-complete. And many suspect it isn't, since it is in NP (intersect) co-NP.

Not just public-key encryption

[ashar]

If your cryptosystem has the property that an encrypted message has only one meaningful decryption, then P-decryptable implies NP-crackable.

The thing with OTP is that an encrypted message has several plausible decryptions, so OTP is unaffected, but most symmetric-key systems would definitely be affected.

Oh yeah...? Well then would you mind solving this?

[gd23ka]

Okay... so you say symmetric ciphers are not based on 'hard' mathematical problems. Would you mind solving this?

DES(k, 0x8c08280811114444) = 0x1ce2fd0a908b1cc3
DES(k, 0x111144448888dddd) = 0x2088c2bf0a3dfc24
DES(k, 0xcccc000000000000) = 0x1bff2081f3259304

Find k which yields above results for each k assuming function DES is electronic code book mode DES. Do not brute force or use quantum computing. Do not channel or employ other parapsychological phenomena.

When I was a high school senior, and mind you back then we were very naive about cryptography, I thought, gee I got a bunch of cipher/plaintext pairs and I know it is DES. Given the ciphertext, it should be easy to roll back the algorithm and get at the key bits. To cut a long story short, at least for me, there is simply no way to reverse the algorithm and derive key text from the cipher/plain-text, though I am sure a mathematician could formally describe the reversing process and classify the mathematical problems involved.

Perhaps our algorithms have already been broken

[HuskyDog]

Have you noticed how often we read that incrimenating evidence has been found on the hard drive of a suspected terrorist? Possible explanations:

1) Despite having a lot to lose and plenty of resources, terrorists don't use encryption properly or even at all.

2) The police get to the computer in advance and insert some sort of key logging technology.

3) The terrorist uses the tools OK, but some other flaw in the OS allows the police to extract the key (for example from the swap partition).

4) They simply torture the suspect until the tells them the pass phrase (I think that this is the most likely).

5) We only get to hear about the cases where the suspect made a mistake. Meanwhile, the NSA have a room full of media which they can't decrypt yet.

6) The NSA know how to crack all of the common algorithms in a reasonable period of time.

If 6 is true, it could be a long time before we hear about it.

proof of P=NP without supplying an algorithm

[sangdrax]

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.

Re:proof of P=NP without supplying an algorithm

[David Gould]

I think I agree, though I'm having some trouble imagining what form such an "existence proof" could take, other than providing a P algorithm for some particular NP-Complete problem. Or at least, providing enough of an outline of such an algorithm that, even if the proof can stand with a few details of the actual algorithm left as an exercise for the reader, filling in the gaps wouldn't be too much harder.

I understand you're probably talking about something completely different, namely, a completely abstract existence proof that would work without even hinting at any actual algorithm. But like I said, I'm having trouble imagining how that would go.

I haven't studied that much algorithm theory, but all the NP-Completeness proofs I've seen have consisted of providing an actual algorithm for reducing problem X to some already-known-to-be-NP-Complete problem Y (plus verifying the succinct certificate property of X's solution, which is usually relatively trivial). Of course I realize a P=NP proof would be a very different sort of thing, but I've always imagined it taking a similar form.

Re:proof of P=NP without supplying an algorithm

[Pseudonym]

I think I agree, though I'm having some trouble imagining what form such an "existence proof" could take, other than providing a P algorithm for some particular NP-Complete problem.

Well, it could be a contrapositive-type of proof. Show that if there is no algorithm in P which solves a certain NP-hard problem, then there is a P algorithm which solves a problem in EXPTIME or something like that. (It is known that P != EXPTIME.)

However, we are now pretty sure that the problem will never be settled. The reason is a rather nice theorem from last year that any proof that P != NP must be exponential in the size of the model used to construct the proof. So P is probably not equal to NP, but the proof is intractable.

Re:proof of P=NP without supplying an algorithm

[Alsee]

I'm having some trouble imagining what form such an "existence proof" could take

A perfect example would be to assume non-existance and derive a contradiction. Knowing the solution can't NOT exist gets you no closer to finding it. (Damn double negatives, chuckle.)

-

Re:proof of P=NP without supplying an algorithm

[Anonymous Coward]

Actually, there exists an algorithm for solving an NP-complete problem (SAT, but any other will work) that has the following property:
"If P=NP, then this algorithm works in polynomial time"
So no, in the case of P=NP, there is no such possibility.

Re:Oh yeah...? Well then would you mind solving th

[swillden]

Okay... so you say symmetric ciphers are not based on 'hard' mathematical problems.

Right.

Would you mind solving this?

You're not understanding me. I'm not trying to claim that DES is easy to break. Quite the opposite, actually, and DES is a very well-respected algorithm.

DES is hard because of the complex and non-linear way in which it employs bunches of different simple, easy operations. Shifts, rotates, S-box substitutions, pre- and post- permutations, etc. are all simple, reversible and easily breakable functions. But enough of them ganged together, in the right way, creates a mathematical function that is very hard to describe in any kind of an accessible, closed form. It's inherently iterative, sequential and algorithmic. The best known attack on DES is a linear cryptanalytic attack that essentially tries to create an accessible, closed-form function for 14 of the 16 rounds. It's not a very successful attack (it requires 2^43 known ciphertext-plaintext pairs).

RSA, in contrast, is extremely simple to describe and to understand. And one excellent way to break it is blatantly obvious: Factor the public key (it's not known if there is a better way to break it, but factoring is certainly sufficient). The problem is, factoring products of large numbers is a hard problem.

See the difference?

Do not ... use quantum computing.

My point is that QC wouldn't help me, even if I had a functioning quantum computer, because QCs can't really model iteration.

To cut a long story short, at least for me, there is simply no way to reverse the algorithm and derive key text from the cipher/plain-text

I should hope not, since that would render the algorithm completely useless for cryptography. Or, rather, you should hope you can find a way, because doing it, where so many other very bright people have failed, would guarantee you a good academic career.

Re:Oh yeah...? Well then would you mind solving th

[gd23ka]

You're not understanding me. I'm not trying to claim that DES is easy to break. Quite the opposite, actually, and DES is a very well-respected algorithm.

Where did I say I believe your think DES is easy to break?

DES is hard because of the complex and non-linear way in which it employs bunches of different simple, easy operations. Shifts, rotates, S-box substitutions, pre- and post- permutations, etc. are all simple, reversible and easily breakable functions. But enough of them ganged together, in the right way, creates a mathematical function that is very hard to describe in any kind of an accessible, closed form. It's inherently iterative, sequential and algorithmic.[...]

Yes. I see where you draw the distinction. The way I see it, even when things get "algorithmic", in other words, even when the result of the substition step is a parameter for a transposition step and back and forth, even then certain patterns will emerge and mathematicians will have to find formal ways of describing those patterns.

Ever wonder what a 3D space looks like where X is all plaintext values from 0 to 2^64-1, Y is all key values from 0 to 2^56-1 and Z is of course DESECB(X,Y)? I wonder what rythms or maybe even geometry there is to be found in something like that. Then I wonder what a autistic but gifted child might notice that we wont :-)

Please mod parent up

[mu22le]

it answers a post (already modded up, unfortunately) wich stated something incorrect, and needs to be reconsidered by the readers.
btw I would have corrected it myself.

Re:There's always OTP - alternate: DH and BBS

[iamcf13]

Use the Diffie-Helman key exchange method to securely transmit the parameters to a Blum-Blum-Shub pseudorandom number generator from one party to another party.

Once that is done, the BBS output can be used (in paranoid '1-bit only' mode for maximum security) to encrypt, send, and decrypt information between both parties.

It's not OTP but its the next best thing, yes?

Re:Oh yeah...? Well then would you mind solving th

[swillden]

even then certain patterns will emerge and mathematicians will have to find formal ways of describing those patterns

This is precisely what cryptanalysts try to do, and exactly what cipher designers try to make impossible (descriptions simple enough to be useful, anyway).

Ever wonder what a 3D space looks like where X is all plaintext values from 0 to 2^64-1, Y is all key values from 0 to 2^56-1 and Z is of course DESECB(X,Y)?

Several papers have been published that explore the structure of this space, mostly looking for subgroups and semi-groups.

I wonder what rythms or maybe even geometry there is to be found in something like that. Then I wonder what a autistic but gifted child might notice that we wont :-)

:-)

Likely not much. The space is simply too large for even the best human pattern analysis. Math provides better tools, but the space still resists too much description -- which is desirable in a cipher. DES is a good choice to explore such questions, though; as the pre-eminent block cipher in the world for nearly 30 years, it's been studied more heavily than any other.

Actually O(n^19) is enough.

[Philip Dorrell]

It depends on the exact numbers, but considering a 128 bit key, and assuming n is the number of bits, and treating O(f(n)) as being f(n), we have 128^19 = (2^7)^19 = 2^133 > 2^128. Which leads to the following predictions:

The Future Solution to the NP problem

• 3 Feb 2016. A solution to the NP/P problem is announced with all NP shown to be in P with complexity O(n^d) for some d.
• 15 Feb 2016. Controversy arises given that the proof is non-constructive, and there is no procedure for computing d (not even in principle).
• 6 July 2016. The solution is followed up by another solution from the same mathematician which is constructive. The upper bound for d is so large that it gets into the Guiness Book of Records as the largest number ever appearing in a mathematical proof.
• 7 August 2006. Someone else comes up with an improved upper bound for d which is 2467.
• 3 March 2007. Guiness Book of Records split their "largest number used in a proof" entry into two entries: one for "largest number used in a proof", and one for "largest number used in a proof not yet superseded by a better proof with a smaller upper bound".