one way function

A one way function is, simply, a function which is easy to compute in one direction, but which is computationally infeasible to compute in the other direction. That is to say, given an output of the function, it is hard to find an input which, when input to that function, will produce that output. Note this is distinct from inversion, where you have to find the original input (otherwise, it would be easy to show that the parity function is one way).

Functions like this are extremely important in cryptography. In fact, given the existence of a one way function, it is possible to prove the existence of secure public key cryptography, and it is also possible to create secure block ciphers, with the Luby-Rackoff transformation (from which one can create secure stream ciphers and hash functions quite easily).

There is just one teensy tiny problem with this. Nobody has ever been able to prove that one way functions actually exist. This is a problem, since if one way functions don't exist, then it's easy to prove that secure public key cryptography is impossible. But we do have some strong candidates for one way functions, including the following:

• Multiplication: It is conjectured that it is hard to find the factors of a number which is the product of two prime numbers. This is the assumption under which RSA is considered secure.
• Exponentiation: If you compute y = g^x (mod p), with p being a prime and g being a generator of the group mod p, then it is hard to find x given y. This is the assumption under which Diffie-Hellman and ElGamal are secure.
• DES: Given the plaintext and ciphertext of a message encrypted with DES, it is hard to find the key used. Of course, in the case of DES, we can be sure that no more than 2⁵⁶ operations are needed. The point is that it is conjectured that you cannot do it in much less than roughly 2⁵⁶ operations.
• SHA-1: Given the SHA-1 hash of some input, it is hard to find that input. (This one is less certain that DES or the ones based on number theory, since SHA-1 hasn't been studied for as long).

Nobody has ever proven that one way functions exist at all, much less that a particular function is actually one way. If you can, congratulations. You just won a Fields Medal. This situation is very similiar to the P != NP debate of complexty theory; everyone is pretty sure that P != NP, but nobody has been able to prove it (yet).