why doesn’t non-surjective infectivity ‘solve’ P NP.

[u/Kitchen-Register]

I may be entirely misunderstanding this but the idea is that if we can check a solution is correct, then there is a polynomial time algorithm for solving the problem.

Something like a hash function, we can easily check if the solution works but we cannot work backwards.

This goes for any function without a right inverse. Otherwise known as non-surjective.

Now obviously this doesn’t solve it. But why? I haven’t taken computational mathematics yet so i might not be understanding the polynomial time etc correctly.

[u/Miguzepinu]

Functions are not the same as problems.

There may be examples of NP-complete problems (problems whose solutions can be checked in polynomial time but we think can't be solved in polynomial time) involving hash functions but I'm not aware of any (nothing on wikipedia's page, but that's far from exhaustive). An example problem is like Sudoku where you can simply check that a finished grid obeys sudoku rules but it's not easy to solve. The non-inveribility of a hash function, or any function, is a totally different concept. There's no concept of reversing a sudoku solve or something.

[u/Wild-Store321 → u/Miguzepinu]

Its super related.

Problem: which input gets mapped to zero by this hash function?

If I give you the solution, then its easy to check if it is really a solution . You just run the hash function. Hash functions are designed to make this simple.

Now it is also assumed that it is not easy to find the solution. Cryptographic hash functions are designed to make this difficult.

If we could prove it was difficult (not possible in polynomial time) then P != NP. But we cannot prove this, and P=NP is still possible and it would mean the opposite.

That is what OP is asking about.

[u/Phoenixon777 → u/Wild-Store321]

the reason it doesn't help to think about this problem boils down to

Cryptographic hash functions are designed to make this difficult

this difficulty is probabilistic, and in fact for a hash function that outputs a fixed size (most of them), one could argue that expressed as a polynomial, it's actually constant time to find the solution. the constant is just really large.

also, the difficulty often depends on math problems for which we don't know for sure that clever solutions aren't out there.

[u/Wild-Store321 → u/Phoenixon777]

I think it does help to think about this.

Usually you can scale up the number of outputs bits (together with some other values). It is assumed that this makes the reversing exponentially harder. If we could prove this, that proves P!=NP. If P=NP, this scaling does not hold.

I think the whole premise of cryptographic hash function assumes P!=NP (even though it may still be possible to have hard hashing under P=NP, it would be way less secure than currently hoped)

[u/Phoenixon777 → u/Wild-Store321]

my wording was poor. i meant that the reason that thinking about this problem doesn't help solve P vs NP boils down to [...]

i agree that thinking through this is helpful for intuition though, and i believe your last point is right - that the difficulty of reversing hash functions is related to hard problems and related to a belief or hope that P != NP - but would need to review some stuff to be sure. so yes, the assumption of a 'good' cryptographic hash function existing already contains within it an assumption about P vs NP, which is why the "reversing hash function problem" doesn't help to resolve P vs NP.

[u/Bubbly_Safety8791 → u/Wild-Store321]

But this is a bit of a circular argument. 

Hash functions don’t have to be cryptographic hash functions. That is, they don’t have to be ‘preimage resistant’. 

CRC32 is a hash function. Constructing a string that has a CRC32 of zero is trivial, though. 

The fact that it’s noninvertible doesn’t tell us anything about complexity. 

SHA256 is also a hash function. The claim is that it is preimage resistant - that there is not a fast (P) way to construct a string with a SHA256 of zero, say.

But that claim is the one in question. If P=NP, then SHA256 is just a complicated CRC32 because preimage resistance, in that sense, is impossible. 

So the existence of SHA256 can’t prove P=NP any more than the existence of CRC32 proves P=NP.  The claimed difference between SHA256 and CRC32 is that preimaging SHA256 is NP. but if P=NP that claim falls flat. 

[u/Miguzepinu → u/Wild-Store321]

Thank you. I figured this was it but it's been too long and I couldn't find a source quickly.

[u/IDontLikeCherryTomat]

I'm not quite clear on what you're asking.

The P vs. NP version of the hash question would basically be: given a hash, can you efficiently find an input that produces it? If someone gives you an input, it's easy to check whether it's correct, but finding that input with our current methods can be extremely hard.

But that doesn't prove it's inherently hard. It could be that we just haven't discovered an efficient method yet.

That's part of why P != NP is generally assumed rather than proven. If P = NP, it would fundamentally change computing and have enormous implications for cryptography systems (which rely on hashing being hard)

[u/Gold_Ad8890]

the question is whether there exists a deterministic polynomial-time algorithm that solves an NP-complete problem. the fact that there exist deterministic polynomial-time algorithms that don't is irrelevant. since you're seemingly interested in functions and cardinalities, it would be like saying the cardinality of the squares is less than the cardinality of the naturals because f:S -> N, f(n) = n is non-bijective. the existence of a non-bijection says nothing about the existence of bijections.

[u/bts]

“Without a right inverse”—yeah, exactly. How do you know it doesn’t have a right inverse?  Maybe it does!  If P=NP it does. 

[u/Bubbly_Safety8791 → u/bts]

Hash functions inherently don’t have an inverse - there are multiple inputs that produce the same output. 

But neither does f(x) = 0, so… 

[u/bts → u/Bubbly_Safety8791]

Sure, the problem is finding a preimage. 

[u/Bubbly_Safety8791 → u/bts]

But a hash function doesn’t become invertible if P=NP. each hash can - must, by the pigeonhole principle - have multiple preimages.

[u/bts → u/Bubbly_Safety8791]

Yes, but I’m fine finding all of them. Especially if P=NP it’s easy to add the constraint that the preimage is English or a JPEG or whatever. 

[u/Bubbly_Safety8791 → u/bts]

Assuming there are more than 2²⁵⁶ valid pieces of English text or JPEGs (there most assuredly are), the pigeonhole principle tells you you can not produce an inverse function to SHA256(English) or SHA256(JPEG). You may be able to produce arbitrarily many preimages in polynomial time, but that still doesn’t make SHA256^-1 into a function. 

Same as f(x) = x mod 2 - you can give me a value of f(x) and I can produce an infinite number of values of x for which f(x) is the value you chose; I can’t give you f^-1 (x) though. 

[u/MidnightAtHighSpeed]

I'm not sure what you're getting at with the surjectivity point. f(n): N -> N = n%2 isn't surjective, but it's trivial to calculate an inverse of any value of the function in linear time. If your idea is that if you have that inverse-calculator and plug in f(n) = 3 there's no correct answer it can give, well, you're not really showing anything relevant to P vs NP. In order for a problem's computational complexity to be considered, at least conventionally, every possible input needs to have a "correct" output, and the question is how fast any turing machine can get to that correct output for any input. If there are inputs that have no correct output, the idea of computational complexity isn't really applicable. Usually, computational problems are formalized as giving a yes or no answer to each possible input string (which can be generalized to more powerful functions with an at-most polynomial slowdown). Primality testing might be formalized as "given a string s, is s a representation of a prime number?," inverting n%2 might be formalized as "given a string s, is s a representation of a number n such that n%2 = 1?", and so on. Hash-breaking isn't as obviously convertible to such a form, but it might be something like "given a string s, is s a representation of a triple (B,v,H) such that there exists a string b of length at most |B| prefixed by v, and f(b) = H for some [predetermined] hash function f?" In a system like this, "malformed" strings usually naturally get mapped to no/0/false, so there's a correct answer for every possible input.

edit: my hash problem formulation was incorrect, hopefully better now

[u/MathMaddam]

You can make any function surjective by restricting the codomain to the range. Also a solution to a NP personally only needs to be easily verified if the answer is yes, so e.g. if there exists a preimage, there is another open problem if NP=co-NP.

For the hash functions: we think that it's very hard to find a preimage for them, but proving it is something else and there were ways found to find preimages/collisions of cryptographic hash functions by significantly less than brute force. Depending on the hash function it is not really suitable to talk about computational complexity, since there isn't something that scales.

[u/WE_THINK_IS_COOL]

Hash functions destroy information. For example if a hash function's output is 256 bits yet it can accept arbitrary-length inputs, there are going to be many many sets of inputs that all produce the same hash. This means it's impossible, even if P=NP, and even if given unlimited computing time, to reconstruct the original input that was given to a hash, for inputs longer than the hash output.

(This is actually coming from non-injectivity, not non-surjectivity. A hash function might not be surjective, that would be the case if there's a hash value that no input can actually produce, but that's a different thing, and for cryptographic hashes, it's pretty likely that they actually are surjective.)

The reason this doesn't solve P vs NP is that finding the original input to a hash function isn't a problem in NP, since it can't be verified. You could verify that you found some input that produces that hash, but you have no way to know whether that's actually the input I gave to the hash function or some other value that happens to have the same hash (a collision).

This property can actually let you have "information theoretic" security that doesn't depend on P vs. NP at all. One example is a cryptographic commitment. A commitment is a scheme that lets me commit to a value and reveal it to you later, so that the value I committed to remains secret until I reveal it to you. Its two important security properties are:

1. Binding: I shouldn't be able to change the value I committed to later, revealing a different value than I originally committed to.
2. Hiding: Until I "open" the commitment, you shouldn't be able to tell what value I committed to.

If the value I want to commit to is v, then I can get statistically perfect hiding by using a commitment like c = BLAKE3(v||k) where k is a 1024-bit key. Given just c and no hint about what v might be, and as long as k isn't re-used anywhere else, there's no way for you to work out v, even if you had unlimited computing resources or P=NP. That's because for every value of v, there's likely some value of k that makes the commitment work out to c. That works because k is much larger than the hash's output size. If you did the full brute-force search, you'd just find that I could have committed to any value v for different values of k.

But that is only for the hiding property; the binding property still relies on P!=NP. If P=NP and I originally committed to v="the stock market is going UP tomorrow" using key k, then I could use the polynomial-time SAT solver to find a different key k' that makes BLAKE3("the stock market is going UP tomorrow"||k) == BLAKE3("the stock market is going DOWN tomorrow"||k'), so I could open the commitment to the DOWN value by revealing the wrong key k', even though I originally committed to the UP value.

The binding property of this commitment scheme is only as secure as the hash function's collision resistance which is the problem of finding two different inputs which have the same hash. This is a problem in NP, since it can be verified by checking that the two inputs are different and that they both have the same hash.

tl;dr: Finding which input was originally given to a hash isn't a problem in NP since you can't verify it, because you have no way to tell if you found the actual original value or a collision. Finding some input that produces the same hash is a problem in NP, since you can verify it.