Function with no inverse My friend asked once a question which sounds very interesting:


  If a function does not have inverse, does it mean that the message cannot be deciphered ?


What is the answer to this question ? In my opinion it is a definitely yes
A function that doesn't have an inverse still has an inverse image or preimage.  I.e., if we have $f : P \to C$, and we can efficiently compute the set $f^{-1}(c) = \{p \in P\; |\; f(p) = c\}$, then that tells us information about what are the possible plaintexts $p$ for a ciphertext $c$.  It doesn't tell you which one of the alternatives is the "true" one, but in real life you very often have other, independent information about what the plaintext is likely to say.  If you put that independent information together with the preimage of the ciphertext, you may well end up inferring the plaintext.

Or an even dumber attack, you can just enumerate your independently- generated guesses at the content of the plaintext, from more likely to less likely, apply the function to each them, and see if the result matches the ciphertext.  Password cracking works precisely like this—the dictionaries and other tricks of the trade (masks, mutations, etc.) can be understood as hypotheses about which passwords real-world users are likely to pick, and the stolen outputs of the password hashes—which are functions without inverses—are used to test these hypotheses.  It's wildly successful.

So I would not look at it as a yes/no question, but as a quantitative one: how much does the attacker's knowledge of the function and ciphertext help them achieve their goal, relative to whatever independent knowledge they have?