Hash Properties

1. Collision Free:

Nobody can find x and y such that:

[ x!=y and Hash(x) = Hash(y) ]

How to find collisions:

try 2**(130) randomly chosen inputs
99.8% chance that two will collide

2. Hiding Property:

r is chosen form a probability distribution that has high min-entropy, then given H( r | x), it is infeasible to find x.

high min-entropy means that distribution is “very spread out”, so that no particular value is chose with more than negligible probability.

(com, key) := commit(msg)
match := verify(com, key, msg)

To seal a message:

(com, key) := commit(msg) — then publish com

To open the sealed message:

publish key, msg 
 
anyone can use verify() to check validity

commit(msg) := (H(key | msg), key)
									where key is random 256-bit value
 
verify(com, key, msg) := (H(key | msg) == com)

Infeasible to find the message

Infeasible to find msg ≠ msg

For every possible output value y, if k is chosen from a distribution with high min entropy, then it is infeasible to find x such that H(k | x) = y.
Implies that no solving strategy is much better than trying random values of x.
Y is the target set for various solutions of x.