A one-way function is not just a hash function – a function that loses information – but a function f
for which, given an image y
, it is difficult to find a pre-image x such that f(x)=y
.
A very simple example of a hash function that does not use any advanced math, is this simple parity function:
def hash(n: Nat)
if n.even?
0
else
1
end
end
As you can see, it maps a large input space (the natural numbers) into a small output space (the set {0, 1}
). And it is one-way: if I tell you that the result is 1
, you can’t tell me what the input was.
This is why they are called one-way: you can compute an image but you can’t find a pre-image for a given image.