How is injective, inverse, surjective & oneway related to cryptography?

Question

Just researching cryptography concepts and finding it really hard to absorb them. I would love to know how these functions (injective, inverse, surjective & oneway) are related to cryptography.

Note that I am just looking for a brief answer. Something that makes sense to someone researching Crypto for the first time. I surely don’t expect a full-fledged (too broad) explanation.

Answer 1

In mathematics these terms have very specific meanings. In cryptography these meanings do not really change, however the terms used to describe them have more specific meanings or examples.

One way function

A one way function is a function that processes the input in such a way that there is not an easy way to get back to to the input using only the output and knowledge of the function. When I say easy, I mean less than the expected security provided by the function to be practical, which may still be quite hard. It may take $2^{-10}$ seconds to compute, but require at least $2^{54}$ to "uncompute" using the same hardware.

For example, a cryptographic hash function is a one way function, and to get an input from an output, you can either brute force it, or try to attack the hash function and find a preimage, which may or may not match the input you are looking for.

Bijective function

A bijective function is one which is a 1 to 1 mapping of inputs to outputs. These would include block ciphers such as DES, AES, and Twofish, as well as standard cryptographic s-boxes with the same number of outputs as inputs, such as 8-bit in by 8-bit out like the one used in AES.

A bijective function is an injective surjective function. The codomain of a function is the set of possible outputs due to the size of the set. The image of a function is the subset of the codomain in which the output of the function may exist. In a bijective function, the image and the codomain are the same set.

Surjective function

A surjective function is one which has an image equal to its codomain, this means that if the set of inputs is larger than the set of outputs, there must be more inputs than outputs. These may include the general cryptographic hash functions.

In the case of SHA-1, we have $2^{160}$ possible outputs of a 160-bit function, but it is not proven that all outputs of SHA-1 are possible. Out of the real set of possible SHA-1 outputs, there are substantially more than $2^{160}$ possible inputs. Therefore SHA-1, IF computing all $2^{160}$ outputs for all possible inputs is possible, is a surjective function. If all outputs are not possible, it is not surjective.

Injective function

An injective function is kind of the opposite of a surjective function. Injective functions are one to one, even if the codomain is not the same size of the input.

An example of an injective function with a larger codomain than the image is an 8-bit by 32-bit s-box, such as the ones used in Blowfish (at least I think they are injective). These have 256 inputs, a codomain of $2^{32}$, and an image set size of 256.

Inverse Function

This is exactly like it sounds, the inverse of another function. This would be the decryption function to an encryption function. An inverse of a function may or may not have the same computational requirement as the forward function, and if keyed, may or may not use the same key. A keyed encryption algorithm that uses the same key for its inverse is a symmetric algorithm, whereas one that needs a different key is an asymmetric algorithm.

I would not consider an algorithm that returns multiple possible inputs of function $f()$ for a given output to be the inverse function of $f()$, but others may disagree. This would include hash function preimages, where the algorithm may continue processing and return multiple preimages, resulting in a set of possible inputs to $f()$ that generate the desired output. Only when the algorithm could return the entire set of preimages would I consider it the inverse.