Hacker News Reader

What relationship do any SHA family hashes have to do with P vs NP? I'm not aware of any. If there is some proof that subset sum reduces to constructing a preimage of anything in the SHA family then I would count that 'mathematically' secure but I don't think any such reduction exists.

View on HN

The relationship is that computing the SHA hashes takes polynomial time. One way you can think of NP is that it is the set of problems whose solutions that can be deterministically verified in polynomial time. So for any hash computable in polynomial time, the pre-image problem is in NP.

Note that this doesn’t prove the security of SHA256, it just says that to prove it secure would be to prove P != NP. You could still prove SHA256 insecure and that proof could be totally separate from P =? NP.

Reply on news.ycombinator.com