3 ms·
Sure thing. I'll write a blog post about it later tonight (am on work time right now) Brief summary however: The point of a crypto hash function is that you n
by Ono-Sendai 11y ago
Sure thing. I'll write a blog post about it later tonight (am on work time right now)
Brief summary however: The point of a crypto hash function is that you need to try on the order of 2^n inputs (n being length in bits of digest) to find a collision. (greater than polynomial time) However you can check any input in polynomial time. This makes it in NP. (decision problem is computable in polynomial time). I'm probably missing some details which I will think about later :)
- Herpyderp666 11y agoWatch Dan Boneh's coursera cryptography course where he at least mentions that provably secure cipher systems require that P != NP. Combine that with the wikipedia article on cryptographic hash functions which tells you that you can build ciphers from hash functions. Done.
- Ao7bei3s 11y agoO(2^(n/2)) actually, due to the birthday attack.