patternMinor
Are hash onions inherently sequential?
Viewed 0 times
areinherentlyhashsequentialonions
Problem
An open problem in complexity theory is whether NC equals P.
I'm somewhat confused because I would have thought that it's obvious that NC != P because of hash onions. A hash onion is when you start with some input $i$ and repeatedly hash $n$ times:
$$H(i), H(H(i)), ..., H^n(i)$$
Given an input $i$ the amount of work to compute $H^n(i)$ is $O(n)$ so hash onions are part of P. And because the hash function $H$ acts like a random oracle you can't do better than sequential queries to $H$, therefore hash onions are not part of NC.
What am I missing?
I'm somewhat confused because I would have thought that it's obvious that NC != P because of hash onions. A hash onion is when you start with some input $i$ and repeatedly hash $n$ times:
$$H(i), H(H(i)), ..., H^n(i)$$
Given an input $i$ the amount of work to compute $H^n(i)$ is $O(n)$ so hash onions are part of P. And because the hash function $H$ acts like a random oracle you can't do better than sequential queries to $H$, therefore hash onions are not part of NC.
What am I missing?
Solution
For all engineering purposes, you are right, if you choose a cryptographically strong hash function $H$.
For theoretical purposes, nope. There's no proof. Your argument is based on unproven assumptions, hence it can't be regarded as a proof that NC $\ne$ P. In particular, we don't know of any hash function $H$ that we can prove is cryptographically strong, or that we can prove is inherently sequential when repeated like this. All of our hash functions are either heuristic (we think they are good but we have no ironclad proof) or are based on other assumptions (such as that factoring is hard; something we suspect but have no proof of). And assuming that $H$ behaves like a random oracle is an unproven assumption. So if you're a theorist and what you care about is proving that NC $\ne$ P, none of these count as a suitable proof.
Personally, I do consider them pretty good evidence that in all likelihood NC $\ne$ P... but it's not a proof.
For theoretical purposes, nope. There's no proof. Your argument is based on unproven assumptions, hence it can't be regarded as a proof that NC $\ne$ P. In particular, we don't know of any hash function $H$ that we can prove is cryptographically strong, or that we can prove is inherently sequential when repeated like this. All of our hash functions are either heuristic (we think they are good but we have no ironclad proof) or are based on other assumptions (such as that factoring is hard; something we suspect but have no proof of). And assuming that $H$ behaves like a random oracle is an unproven assumption. So if you're a theorist and what you care about is proving that NC $\ne$ P, none of these count as a suitable proof.
Personally, I do consider them pretty good evidence that in all likelihood NC $\ne$ P... but it's not a proof.
Context
StackExchange Computer Science Q#91766, answer score: 4
Revisions (0)
No revisions yet.