Sure, nobody may have an algorigthm to crack your digital signatures now, but there is considerable risk that one could emerge without warning, and anything you've transmitted in the past could have been saved and then cracked.
This is true of public-key encryption, today, even with quantum computers out of the picture. An efficient factoring algorithm may be one clever insight away from reality.
Hell, someone could prove that P=NP "without warning," and then public-key crypto will really be impossible.
The point is that quantum computers do not automatically negate public-key cryptography.
PKE is based on the idea that some math problems are harder to solve than to verify. Given a large enough quantum computer, that really is no longer the case.
The statement "quantum computers can break any public-key encryption" is probably not true.
For example, there are PK encryption schemes based on lattice problems (e.g., Ajtai-Dwork). No quantum algorithms are known for these lattice problems, despite lots of effort. Therefore, PKE may still be a viable approach even in the presence of quantum computers.
I wouldn't trust any page that says something like this:
One of the most interesting categories contains problems that are called NP-complete. These all have the feature that in order to solve the problem all possible solutions must be tried, and the number of possible solutions grows exponentially with the problem size.
"All possible solutions must be tried" is just wrong, and has nothing to do with NP-completeness.
I am not a Quantum Computing expert, but as far as I know there hasn't been much progress in making good quantum algorithms (even approximations) for NP-complete problems. Factoring and discrete log and "hidden subgroup" problems, yes. But these are not likely to be NP-complete.
Hey, you worked with the U Alberta group; cool. One question: how come they never put up the academic paper about vexbot? That seems to be the most interesting project from a theory point of view, and the most successful practically.
About your sig: it is highly unlikely that any form of prime factorization is NP-complete. The reason is that the problem is contained in both NP and co-NP. So if it's NP-complete, then NP=co-NP, which nobody seriously believes is true and would be very surprising.
A bot could have a perfect memory of a player's betting patterns in previous rounds and what their cards were, and could use this info in subsequent rounds - just like real players, except the bot would have a perfect analysis vs fuzzy human memory.
All true, but it is very hard for a computer to "summarize" all this information and generalize it for the future. (Good) human players tend to be able to do this pretty quickly with very few instances, but we still don't know how to program a computer to do it, even when it has tons of data at its disposal.
OK, you have no idea what you are talking about. Every game of poker, whether played in real life or on computer, is played with a standard 52-card deck. Further, there is no sense in which "card counting" helps in Texas Hold'em.
You make a lot of good points, but more importantly (I think) it's very hard for a computer to get a good model of its opponent's playing style, to infer what cards the opponent is likely to have.
All the statistical calculations in the world won't help you decide whether to call or fold, if you don't have any idea what cards your opponent has.
Without bluffing you play the odds and it just becomes a simple game of chance
Not true at all. To be a successful player, you must detect patterns in your opponents' play so you can infer whether you are likely to be ahead of them, and how to maximize the pot when you think you're going to win. This is very difficult for computers to do, even with sophisticated learning algorithms.
Don't let the posters who say "just enumerate all possibilities" fool you.
The hardest part of playing poker is "reading" your opponents' hands -- learning how they tend to play, and inferring what cards they are likely to hold, whether they are bluffing or slow-playing, etc.
It may be easy to read a poker bot's style of play, but reading good human players is extremely difficult. So even if a certain bot crushes the competition in this tournament, it may not do so well against humans.
Regarding your Jan news item -- have you looked into madman?
I am now disillusioned with IMMS. It was great to start with, but quickly got stuck in some 'local optima' and never played anything outside my top-top-top favorites (which quickly became no-so-top). Also, it has a lot of annoying playback quirks. So thanks for those pointers to AutoDJ and Madman....!
This attack shows us all once again that there is that the procedures for using cryptography are as important as the mathematical theories and proofs on which cryptography is based.
I see what you are saying, but I think you're taking exactly the wrong lesson.
The lesson is that exceedingly strong, conservative notions of security are needed for cryptographic primitives, because you can't predict/constrain their use in any meaningful way. You shouldn't be happy with a hash function that just resists collisions on text documents, because it will fail in unpredictable ways, and those failures may be "amplifiable." Even if you think you'll be dealing only with text-only documents, written in English, less than 2KB in size, you still want a function that resists collisions on any binary string.
People like to believe that it's just the algorithm that's important, and once you have such an algorithm it's equally applicable to messages of all sorts and formats.
That should be the case for any well-designed algorithm. If the algorithm doesn't work for arbitrary data in any format, it is no good and should not be used.
Secret sharing is a good start, but it doesn't get you all the way there.
Suppose it's time to sign a new build: then some parties reconstruct the secret key, and *poof* all of a sudden all the parties knows the secret key, and you're back to a single point (or even multiple points) of (security) failure.
What is needed is a threshold signature scheme (in which the key is never explicitly reconstructed). But I don't know of any free or even cheap implementations (they tend to complicated protocols).
When Adi Shamir (the "S" of "RSA") discovered zero-knowledge proof systems, the US millitary tried to suppress all of his work on it
Do you have any evidence for this? Goldwasser, Micali and Rackoff discovered zero-knowledge proof systems. And while it took awhile for their paper to be published, it wasn't due to censorship -- it was because they had trouble convincing anybody that these would be of any use.
By the way, the original proof of the PCP theorem wasn't just due to Sanjeev Arora. It spanned a long sequence of works, and a ton of people were involved in proving it.... more than I can remember or list here.
The PCP theorem is a beautiful piece of computer science and mathematics.
What's it good for? Well, for starters:
One can use it to show that not only are some problems very hard to get exact answers to, they are very hard to even get approximate answers to! In the most extreme case, it's hard to tell whether a graph has an enormous clique (taking up almost all the vertices), or just a very small one.
PCPs can be used to build very low-communication zero-knowledge proofs. So you can prove a mathematical statement to someone, using much less communication than it takes to even write down that statement, and giving her no idea why the statement is true, even though she will be absolutely convinced that it really is true!
PCPs can also be used to write down a (long) proof of a mathematical theorem, so that to check the theorem only requires you to look in a few random places. If the theorem is false, you'll detect it, otherwise you'll be convinced that it's true. It's as if there was a huge book of mathematics, and you opened to a random page, read a few characters, and said, "yep, it's definitely all true."
Since there are only finitely many possibly files of a given size, there are also only finitely many possible pairs of files of that size. Since the number of collisions is at most the number of pairs, that means there are only finitely many collisions of a files of that given size.
All I said is that you can find an infinite number of pairs of colliding files where both files in each pair are the same size as each other. Since the size of these files is unbounded, there are an infinite number of such pairs.
Number one, the article says nothing about hashing. The submitter just made that up.
Number two, one need not find hash collisions in order to poison P2P networks. Just hack up a client that claims to have a file with a certain hash, but delivers chunks of random garbage to swarming peers. When the downloader hashes the entire file, one bad chunk is enough to cause a mismatch and the entire file is scrapped. It's a denial-of-service attack, it works, and it's being done.
This attack can be countered using 'tree hashing,' but I don't know of any P2P protocols that use it. (BitTorrent works with hashes of individual chunks, which is good, but not great.)
Now, what the company has to do is create a file of the SAME FILE SIZE
The MD5 collisions that have already been found are for files that are of the same size. All it takes is to find one pair of blocks that collide, and you can build infinitely many pairs of same-size colliding files.
This has nothing to do with the claims of this company, though -- the article doesn't even mention hashing.
The linked article says nothing about hashing, period. However, it is definitely true that there are entities on P2P networks that are 'poisoning' files. This is how it works: the peers claim to have files with a popular hash value, but when you download pieces from those clients (using swarming), they give you garbage. When the entire file is pieced together, even one 'poison piece' is enough to cause a bad hash value, and the entire file gets scrapped.
There are solutions to this that use 'tree hashing', which allows you to identify corrupt pieces without having to throw everything out. If P2P protocols don't start implementing tree hashing, the poisoners will likely succeed.
Slashdot Mirror
Sure, nobody may have an algorigthm to crack your digital signatures now, but there is considerable risk that one could emerge without warning, and anything you've transmitted in the past could have been saved and then cracked.
This is true of public-key encryption, today, even with quantum computers out of the picture. An efficient factoring algorithm may be one clever insight away from reality.
Hell, someone could prove that P=NP "without warning," and then public-key crypto will really be impossible.
The point is that quantum computers do not automatically negate public-key cryptography.
PKE is based on the idea that some math problems are harder to solve than to verify. Given a large enough quantum computer, that really is no longer the case.
The statement "quantum computers can break any public-key encryption" is probably not true.
For example, there are PK encryption schemes based on lattice problems (e.g., Ajtai-Dwork). No quantum algorithms are known for these lattice problems, despite lots of effort. Therefore, PKE may still be a viable approach even in the presence of quantum computers.
I wouldn't trust any page that says something like this:
One of the most interesting categories contains problems that are called NP-complete. These all have the feature that in order to solve the problem all possible solutions must be tried, and the number of possible solutions grows exponentially with the problem size.
"All possible solutions must be tried" is just wrong, and has nothing to do with NP-completeness.
I am not a Quantum Computing expert, but as far as I know there hasn't been much progress in making good quantum algorithms (even approximations) for NP-complete problems. Factoring and discrete log and "hidden subgroup" problems, yes. But these are not likely to be NP-complete.
Hey, you worked with the U Alberta group; cool. One question: how come they never put up the academic paper about vexbot? That seems to be the most interesting project from a theory point of view, and the most successful practically.
About your sig: it is highly unlikely that any form of prime factorization is NP-complete. The reason is that the problem is contained in both NP and co-NP. So if it's NP-complete, then NP=co-NP, which nobody seriously believes is true and would be very surprising.
A bot could have a perfect memory of a player's betting patterns in previous rounds and what their cards were, and could use this info in subsequent rounds - just like real players, except the bot would have a perfect analysis vs fuzzy human memory.
All true, but it is very hard for a computer to "summarize" all this information and generalize it for the future. (Good) human players tend to be able to do this pretty quickly with very few instances, but we still don't know how to program a computer to do it, even when it has tons of data at its disposal.
OK, you have no idea what you are talking about. Every game of poker, whether played in real life or on computer, is played with a standard 52-card deck. Further, there is no sense in which "card counting" helps in Texas Hold'em.
You make a lot of good points, but more importantly (I think) it's very hard for a computer to get a good model of its opponent's playing style, to infer what cards the opponent is likely to have.
All the statistical calculations in the world won't help you decide whether to call or fold, if you don't have any idea what cards your opponent has.
Without bluffing you play the odds and it just becomes a simple game of chance
Not true at all. To be a successful player, you must detect patterns in your opponents' play so you can infer whether you are likely to be ahead of them, and how to maximize the pot when you think you're going to win. This is very difficult for computers to do, even with sophisticated learning algorithms.
Don't let the posters who say "just enumerate all possibilities" fool you.
The hardest part of playing poker is "reading" your opponents' hands -- learning how they tend to play, and inferring what cards they are likely to hold, whether they are bluffing or slow-playing, etc.
It may be easy to read a poker bot's style of play, but reading good human players is extremely difficult. So even if a certain bot crushes the competition in this tournament, it may not do so well against humans.
But you also get a free frogurt!
Regarding your Jan news item -- have you looked into madman?
I am now disillusioned with IMMS. It was great to start with, but quickly got stuck in some 'local optima' and never played anything outside my top-top-top favorites (which quickly became no-so-top). Also, it has a lot of annoying playback quirks. So thanks for those pointers to AutoDJ and Madman....!
This attack shows us all once again that there is that the procedures for using cryptography are as important as the mathematical theories and proofs on which cryptography is based.
I see what you are saying, but I think you're taking exactly the wrong lesson.
The lesson is that exceedingly strong, conservative notions of security are needed for cryptographic primitives, because you can't predict/constrain their use in any meaningful way. You shouldn't be happy with a hash function that just resists collisions on text documents, because it will fail in unpredictable ways, and those failures may be "amplifiable." Even if you think you'll be dealing only with text-only documents, written in English, less than 2KB in size, you still want a function that resists collisions on any binary string.
People like to believe that it's just the algorithm that's important, and once you have such an algorithm it's equally applicable to messages of all sorts and formats.
That should be the case for any well-designed algorithm. If the algorithm doesn't work for arbitrary data in any format, it is no good and should not be used.
I agree wholeheartedly. That's why I'm surprised that Slashdot paid attention to the PS trick and not the result on certs. (Wait, am I surprised??)
How exactly could they create junk documents that also match the expected filesize.
The collisions that have been found for MD5 are for pairs of documents that are the same size. The size constraint is not a problem.
Lenstra and others came up with a way to generate syntactically-correct X509 certificates that collide under MD5.
Here's a link to the paper: Lenstra et al.
Secret sharing is a good start, but it doesn't get you all the way there.
Suppose it's time to sign a new build: then some parties reconstruct the secret key, and *poof* all of a sudden all the parties knows the secret key, and you're back to a single point (or even multiple points) of (security) failure.
What is needed is a threshold signature scheme (in which the key is never explicitly reconstructed). But I don't know of any free or even cheap implementations (they tend to complicated protocols).
Dismissing Intelligent Design as not being science
ID is not science for one simple reason: it is not falsifiable. That is, it does not provide any criterion under which we can say "ID is false."
Every other scientific theory is falsifiable. It's the fundamental requirement of the scientific method.
It is not "closed minded" to say "this is not science, because it doesn't even satisfy the main requirement of a scientific theory."
When Adi Shamir (the "S" of "RSA") discovered zero-knowledge proof systems, the US millitary tried to suppress all of his work on it
Do you have any evidence for this? Goldwasser, Micali and Rackoff discovered zero-knowledge proof systems. And while it took awhile for their paper to be published, it wasn't due to censorship -- it was because they had trouble convincing anybody that these would be of any use.
I think parent is a troll...
By the way, the original proof of the PCP theorem wasn't just due to Sanjeev Arora. It spanned a long sequence of works, and a ton of people were involved in proving it.... more than I can remember or list here.
- One can use it to show that not only are some problems very hard to get exact answers to, they are very hard to even get approximate answers to! In the most extreme case, it's hard to tell whether a graph has an enormous clique (taking up almost all the vertices), or just a very small one.
- PCPs can be used to build very low-communication zero-knowledge proofs. So you can prove a mathematical statement to someone, using much less communication than it takes to even write down that statement, and giving her no idea why the statement is true, even though she will be absolutely convinced that it really is true!
- PCPs can also be used to write down a (long) proof of a mathematical theorem, so that to check the theorem only requires you to look in a few random places. If the theorem is false, you'll detect it, otherwise you'll be convinced that it's true. It's as if there was a huge book of mathematics, and you opened to a random page, read a few characters, and said, "yep, it's definitely all true."
In short: amazing!Yes, bittorrent uses block hashes. But this requires a centralized tracker to be an arbiter of what the "good" hash values are.
Most fully-distributed protocols like gnutella don't do hash trees (using a majority vote to determine the "good" root hash value), and they should.
Since there are only finitely many possibly files of a given size, there are also only finitely many possible pairs of files of that size.
Since the number of collisions is at most the number of pairs, that means there are only finitely many collisions of a files of that given size.
All I said is that you can find an infinite number of pairs of colliding files where both files in each pair are the same size as each other. Since the size of these files is unbounded, there are an infinite number of such pairs.
Number one, the article says nothing about hashing. The submitter just made that up.
Number two, one need not find hash collisions in order to poison P2P networks. Just hack up a client that claims to have a file with a certain hash, but delivers chunks of random garbage to swarming peers. When the downloader hashes the entire file, one bad chunk is enough to cause a mismatch and the entire file is scrapped. It's a denial-of-service attack, it works, and it's being done.
This attack can be countered using 'tree hashing,' but I don't know of any P2P protocols that use it. (BitTorrent works with hashes of individual chunks, which is good, but not great.)
Now, what the company has to do is create a file of the SAME FILE SIZE
The MD5 collisions that have already been found are for files that are of the same size. All it takes is to find one pair of blocks that collide, and you can build infinitely many pairs of same-size colliding files.
This has nothing to do with the claims of this company, though -- the article doesn't even mention hashing.
The linked article says nothing about hashing, period. However, it is definitely true that there are entities on P2P networks that are 'poisoning' files. This is how it works: the peers claim to have files with a popular hash value, but when you download pieces from those clients (using swarming), they give you garbage. When the entire file is pieced together, even one 'poison piece' is enough to cause a bad hash value, and the entire file gets scrapped.
There are solutions to this that use 'tree hashing', which allows you to identify corrupt pieces without having to throw everything out. If P2P protocols don't start implementing tree hashing, the poisoners will likely succeed.