With $hash_n$, I mean a standard cryptographic hash like sha256, scaled up to have arbitrary length $n$ of its output with the same underlying principles. What is the time complexity class of the following problem?

Given an $n \in \mathbb{N}$ and data $d$ with $length(d) = n$, determine whether $\exists p : ((length(p) \le n) \wedge (hash_n(p) = d))$.

I find it really hard to find a class for it because it seems like a hard problem and it's definitely not $\in P$ (except if $P = NP$ or there is a vulnerability of the hash function (assume there isn't one not already known (so sha256 basically just printing the state of a state machine can be used, of course))) but you can't use it to solve any of the classical NP hard problems.

Determining the space complexity is of course trivial: It's only $\mathcal{O}(n)$.

This is of course just one example of a hash decision problem and it's meant to only be an example. I'm more interested in the general classification of hash decision problems.

Edit: You may assume a perfect hash function instead of a commonly used cryptographic hash function. E.g. if you're more comfortable with it, you don't want to exploit properties of cryptographic hash functions which are commonly used in practice, what you want to show is threatened by those properties, etc.

  • $\begingroup$ A colon is read as "such that" but is logically equivalent to an "and", just like "but" is logically equivalent to "and" (if it doesn't assume the meaning of "except", it kind of has 2 meanings in the English language). I'll change it, doesn't matter anyways. I'll also set a few unnecessary parentheses to make things 100% clear. $\endgroup$
    – UTF-8
    Jan 8 '17 at 0:10
  • 1
    $\begingroup$ OK! (If you're curious, that's not how the mathematical notation works, at least as I was taught it. It's not that there is a fixed translation where ":" and "such that" are interchangeable and you can put a ":" anywhere a "such that" would make sense in an English sentence. Rather, $\exists x : P$ is an accepted notation... but $\exists x : P : Q$ isn't anything. The ":" is tied to the preceding $\exists$. Minor nitpick, obviously.) $\endgroup$
    – D.W.
    Jan 8 '17 at 0:15
  • $\begingroup$ I'll accept it. As someone who stands half-way between mathematicians and physicists, I know it's a very bad idea to discuss notation and I just go with whatever notation the people I'm talking to use. I don't want to engage in discussions about notation as that's nothing there is objective truth to without reference to a well-documented standard. $\endgroup$
    – UTF-8
    Jan 8 '17 at 0:19

It's in NP. In particular, it is easy to provide a witness for a yes answer (the witness is such a value $p$) and given a witness, you can verify the yes answer in polynomial time.

As you say, it's not in P if the cryptographic hash function is cryptographically secure.

I don't think it's likely to be NP-complete, but at the moment I can't articulate a specific reason why I think that.

(If you have a one-way permutation, then it's in NP $\cap$ coNP, so unlikely to be NP-complete... but that doesn't apply to your question.)

  • $\begingroup$ Your guess is that it's NP-intermediate? $\endgroup$
    – UTF-8
    Jan 8 '17 at 0:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.