Home > general > example of Collision resistance and one-way function

example of Collision resistance and one-way function

Collision Resistant fun:
from Definition, if f(.) is a collision resistant function, then it is hard to hard find different x and x’ such that f(x)=f(x’).

Lets see some example:
let, f(x) = x*x.
For this function we can find f(-2) = f(2) = 4. So, we find two different x and x’ such that f(x) = f(x’). So, given f(x)=x*x is not collision resistant.

Again, if f(x) = x, then this is collision resistant because, we cannot find two different x such that f(x)=f(x’).

Likewise, there are lots of examples for collision resistant and non collision resistant function.

One-way function:
given a function y=f(x), it is hard to find x when y is given.
for example, f(x)=x*x, is trivially not one-way function because given y=x^2, we can readily find sqrt(y) to find x.
There is an excellent example at [1] about one-way function which I excerpt verbose.

Alice and Bob procure the same edition of the white pages book for a particular town, say Cambridge. For each letter Alice wants to encrypt, she finds a person in the book whose last name starts with this letter and uses his/her phone number as the encryption of that letter.

To decrypt the message Bob has to read through the whole book to find all the numbers. The decryption will take a lot more time than the encryption. If the book increases in size the time it takes Alice to do the encryption almost doesn’t increase, but the decryption process becomes more and more draining.

This example is very good for teaching one-way functions to non-mathematicians.

[1] http://blog.tanyakhovanova.com/?p=277

Categories: general
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: