Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Can someone please clarify the Birthday Effect for me?

Please help interpret the Birthday effect as described in Wikipedia:

A birthday attack works as follows:

  1. Pick any message m and compute h(m).
  2. Update list L. Check if h(m) is in the list L.
  3. if (h(m),m) is already in L, a colliding message pair has been found. else save the pair (h(m),m) in the list L and go back to step 1.

From the birthday paradox we know that we can expect to find a matching entry, after performing about 2^(n/2) hash evaluations.

Does the above mean 2^(n/2) iterations through the above entire loop (i.e. 2^(n/2) returns to step 1), OR does it mean 2^(n/2) comparisons to individual items already in L?

like image 246
Mark Avatar asked Oct 14 '22 06:10

Mark


1 Answers

It means 2^(n/2) iterations through the loop. But note that L would not be a normal list here, but a hash table mapping h(m) to m. So each iteration would only need a constant number (O(1)) of comparisons in average, and there would be O(2^(n/2)) comparisons in total.

If L had been a normal array or a linked list, then the number of comparisons would be much larger since you would need to search through the whole list each iteration. This would be a bad way to implement this algorithm though.

like image 110
interjay Avatar answered Oct 18 '22 13:10

interjay