next up previous
Next: Digital signaturesMerkle, Diffie, Hellman Up: A Whirlwind Tour of Previous: Diffie-Hellman key exchange

One way and collision-free functions


Definition A function f:M-> H is called a one-way function if for every m in M it is easy to compute f(m), but for essentially all y in H, it is computationally infeasible to compute x with f(x)=y.

Example

f(x)=gx mod p for a large prime p

Example

f(x) = x2 mod n when n=pq and p and q are unknown.


Definition A function f:A -> B is called weakly collision free if for essentially all x in A, it is computationaly infeasible to find a y in A with y not equal to x and f(x) = f(y).


Definition A function f:A -> B is called strongly collision free if it is computationally infeasible to construct x and y in A with x not equal to y and f(x) = f(y).



Kevin McCurley
1/23/1998