One-way Compression Function - One-way

One-way

A one-way function is a function that is easy to compute but hard to invert. A one-way compression function or (also called hash function) should have the following properties:

• Easy to compute: If you know an input it is easy to calculate the output.
• Preimage-resistance: If an attacker only knows the output it should be unfeasible to calculate an input i.e. given an output h it should be unfeasible to calculate an input m such that hash(m)=h.
• Second preimage-resistance: Given an input m1 whose output is h, it should be unfeasible to find another input m2 that has the same output h i.e. hash(m1)=hash(m2).
• Collision-resistance: It should be hard to find any two different inputs that compress to the same output i.e. an attacker should not be able to find a pair of messages m1 ≠ m2 such that hash(m1) = hash(m2). Due to the birthday paradox (see also birthday attack) a collision can always be found in time of about 2n/2 where n is the number of bits in the hash function's output. An attack on the hash function thus should not be able to find a collision with less than about 2n/2 work.

Ideally one would like the "unfeasibility" in preimage-resistance and second preimage-resistance to mean a work of about 2n where n is the number of bits in the hash function's output. Recent results indicate that in the case of second preimage-resistance this is more difficult than has been expected.