One Way Functions

A mathematical function can be said to be one way if:

1) For every preimage (input), it is “easy” to calculate the corresponding image (output)

2) For every image (output), it is “hard” to calculate the corresponding preimage (input)

Note that the terms “easy” and “hard” above are based on an exponential difference in time complexity

Proof of Existance

Although the modern world relies heavily on certain functions being assumed to be on-way, there is no formal proof that such a thing actually exists. That said, the functions in wide-spread use today have withstood the test of time and intense scrutiny. It is worth keeping in mind here that one thing that is mathematically proved is that not everything can be formally proved

Candidate Functions

Some candidate functions that are in use today for cryptographic purposes include:

Notes mentioning this note

Discrete Logarithm Problem
Modular exponentiation is one candidate for a [[one way functions one way function]].
Integer Factorization
Integer factorization of large semi-primes is one candidate for a [[one way functions one way function]].