4 ms·

If you can compute a hash in polynomial time then you can also verify a potentiel pre-image (i.e. input) in polynomial time, which puts the problem of finding a

If you can compute a hash in polynomial time then you can also verify a potentiel pre-image (i.e. input) in polynomial time, which puts the problem of finding a pre-image in NP. Hence proving pre-image attack resistency would imply P!=NP unless computing the hash itself can't be done in polynomial time. So for the time being the answer is no, we can't have a hash function that is theoretically secure. Your suggestion just moves the problem onto proving that the public key cryptography is secure, which suffers from the same problem.

contravariant 5y ago
Technically the time is constant since some finite set of inputs is enough to generate all hashes. At the very least we'll need to be careful with respect to what the time is 'polynomial'. For what it's worth I see no reason you couldn't identify some NP-hard problem for which the original input is the solution. This means that reversing the hash directly is out of the question, but this only works if you the way you generate the NP-hard problem is itself difficult (or ideally random) enough that it can't be reverted. Sounds like a lot of effort, but who knows, it might be worth the effort in some cases.
- CaptainNegative 5y ago
  The difficult part of basing a one-way function around NP-hardness isn't so much the reduction itself as it is the ability to sample from the "hard core" core the distribution. For example, say you base the hardness of your OWF on the NP-hard problem of finding a Hamiltonian Cycle in an n-node graph. Your reduction could be completely valid and sound, meaning that pre-imaging your function would require solving an NP-hard problem. But, maybe suprisingly, HamCycle is actually extraordinarily easy for an overwhelming majority of n-node graphs. This is the result of a phase transition that happens when the degree of a random graph passes O(log n) or so, where suddenly the probability of such a graph having a HamCycle becomes 1-o(1) > 0.999999 for n sufficiently large, and a simple greedy algorithm can find them (ref. Pósa '76). And most graphs have average degree closer to n/2 than log(n), meaning that finding a HamCycle is trivial. The crux, finally, is that basing your problem on an overwhelmingly trivial problem, even if technically NP-hard, is still not going to work for security. It will be little consolation that perhaps one customer's account was not broken into when the other hundred million accounts were cracked in milliseconds. A solution to this problem would require researchers to find an NP-hard problem that is hard on average when sampled from an efficiently-sampleable distribution (plus a couple other techcnical caveats). Whether or not there is a good way to do that, for any NP-hard problem, is still mostly a major open question, and not for lack of trying.
  - contravariant 5y ago
    Interesting, I wrongly assumed it would be easy to have an NP-hard problem that's also NP-hard on average. Thanks for the great response.

contravariant 5y ago

Technically the time is constant since some finite set of inputs is enough to generate all hashes. At the very least we'll need to be careful with respect to what the time is 'polynomial'. For what it's worth I see no reason you couldn't identify some NP-hard problem for which the original input is the solution. This means that reversing the hash directly is out of the question, but this only works if you the way you generate the NP-hard problem is itself difficult (or ideally random) enough that it can't be reverted. Sounds like a lot of effort, but who knows, it might be worth the effort in some cases.

CaptainNegative 5y ago
The difficult part of basing a one-way function around NP-hardness isn't so much the reduction itself as it is the ability to sample from the "hard core" core the distribution. For example, say you base the hardness of your OWF on the NP-hard problem of finding a Hamiltonian Cycle in an n-node graph. Your reduction could be completely valid and sound, meaning that pre-imaging your function would require solving an NP-hard problem. But, maybe suprisingly, HamCycle is actually extraordinarily easy for an overwhelming majority of n-node graphs. This is the result of a phase transition that happens when the degree of a random graph passes O(log n) or so, where suddenly the probability of such a graph having a HamCycle becomes 1-o(1) > 0.999999 for n sufficiently large, and a simple greedy algorithm can find them (ref. Pósa '76). And most graphs have average degree closer to n/2 than log(n), meaning that finding a HamCycle is trivial. The crux, finally, is that basing your problem on an overwhelmingly trivial problem, even if technically NP-hard, is still not going to work for security. It will be little consolation that perhaps one customer's account was not broken into when the other hundred million accounts were cracked in milliseconds. A solution to this problem would require researchers to find an NP-hard problem that is hard on average when sampled from an efficiently-sampleable distribution (plus a couple other techcnical caveats). Whether or not there is a good way to do that, for any NP-hard problem, is still mostly a major open question, and not for lack of trying.
- contravariant 5y ago
  Interesting, I wrongly assumed it would be easy to have an NP-hard problem that's also NP-hard on average. Thanks for the great response.