# How is pre-image resistance defined, formally?

Earlier today, forest asked in our chat, The Side Channel whether the definition of first pre-image security actually requires that an input that evaluates to the challenge hash result must be known to exist a-priori.

This got me thinking. How does one actually, formally define first pre-image security for hash functions?

This is also motivated by the fact that formal definitions are crucial in cryptography to actually understand what is needed to break security. For example, the RSA problem isn't "given $c$ that was constructed as $c=m^e\bmod n$, find $m$" but rather requires specific properties from $n$ (by requiring correct key generation) and requires correct choice (uniformly at random) of $m$ as well.

• "Many other security notions can be reduced to this one (there's a nice graph in the paper), so it would appear to be the most useful, even though it's also stronger than the previous one which captures the case of one concrete hash function a bit better." Did you intend for this to be under the aPre paragraph perhaps? As per the paper, aPre implies Pre, but not the other way around (see Thm. 16.(2)). Thus, it does't make sense to talk about Pre as being a stronger notion than aPre (nor ePre for that matter). In fact, it is weaker. – hakoja Apr 24 '18 at 17:56
• @hakoja so the original idea of that paragraph was to reflect the idea that everything implies Pre, but I now see that's not so useful... (removed the paragraph) – SEJPM Apr 24 '18 at 18:01