Because some problems we lack the ability to solve any other way. There are at least three problems which are famous, as described in the article I linked.
see if you follow this one one, for a real computer:
Suppose I pick a n bit key, and encrypt a phrase with it. I will provide you the plain text phrase and either a real or fake cipher text. You have to determine if a program which loops through all the keys will decrypt the ciphertext into a the phrase.
Either you know weaknesses in the crypto system, or you have no choice but to iterate though each key to see if the output matches the phrase.
There is a relationship with proof of work crypto as well. Even all the Bitcoin mining has trouble finding hashes with a certain number of leading zeroes, add a few more zeros and no one will ever find a working seed again. There is no way to speed up the process beyond iterating over the seeds.
You can tie this to the halting problem by just saying to go back the key 0 once the key space is exhausted.
> Either you know weaknesses in the crypto system, or you have no choice but to iterate though each key to see if the output matches the phrase.
> There is a relationship with proof of work crypto as well. Even all the Bitcoin mining has trouble finding hashes with a certain number of leading zeroes, add a few more zeros and no one will ever find a working seed again.
Yup, I know. But here's the part I think you're missing:
None of those crypto systems you're mentioning are proven not to have weaknesses. In fact, weaknesses in hashing and encryption algorithms are encountered every now and then, even for those that have been considered state-of-the-art.
So yes, I agree that in practice we don't know how to solve this problem efficiently yet. Which means it's currently impractical, and would currently requiring brute forcing through all the states.
But I haven't seen a proof that it's not possible to find a practical algorithm.
There is no proof of that for our crypto systems. There is a proof you can’t prove ZF theory, but you also probably can’t prove it false. If you hide that question in the thing you iterate over, you can take it on faith you won’t find a counterexample and say the program won’t terminate; but you haven’t, and in fact cannot, prove it.
There are also lesser problems that have been around a while which we haven’t been able to prove, but might be provable… you can iterate over numbers looking for an counter example to the Collatz conjecture… I think that’s the best example of a simple program that is outside our current knowledge of math (better than the crypto one), but maybe someday we will have an answer.
see if you follow this one one, for a real computer:
Suppose I pick a n bit key, and encrypt a phrase with it. I will provide you the plain text phrase and either a real or fake cipher text. You have to determine if a program which loops through all the keys will decrypt the ciphertext into a the phrase.
Either you know weaknesses in the crypto system, or you have no choice but to iterate though each key to see if the output matches the phrase.
There is a relationship with proof of work crypto as well. Even all the Bitcoin mining has trouble finding hashes with a certain number of leading zeroes, add a few more zeros and no one will ever find a working seed again. There is no way to speed up the process beyond iterating over the seeds.
You can tie this to the halting problem by just saying to go back the key 0 once the key space is exhausted.