A hash is an efficient deterministic function that takes an arbitrary length input and produces a fixed length output (digest, hash). Letbe a function where
- = message space
- = digest space
The hash function must be a one way function. Givenfinds.t
Givenit should be hard to findwith
An adversaryis given a messageand outputs a message.wins the game if he findsHis advantage iswhereis a probability
An adversaryoutputs two messageswins the game if he findsHis advantage is
A hash functionis collision resistant if for all efficient and explicit adversaries the advantage is negligible
Assuming a functionis preimage resistant for every element of the range ofis a weaker assumption than assuming it is either collision resistant or second preimage resistant.
Assuming a function is second preimage resistant is a weaker assumption than assuming it is collision resistant.