5

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?

ire_and_curses
  • 68,372
  • 23
  • 116
  • 141
Mark
  • 1,214
  • 10
  • 24

1 Answers1

4

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.

interjay
  • 107,303
  • 21
  • 270
  • 254
  • just one other thing regarding stack overflow - am I supposed to be updating the status somehow of members here that answer my questions. If so, how is that done. – Mark May 04 '10 at 16:17
  • 1
    @Mark: If you like an answer you can upvote it (click the up arrow to the left of the answer). If an answer solves your problem, you can accept it - click the tick mark to the left of the answer. – ire_and_curses May 04 '10 at 16:21
  • Well it looks like I'll have to register to do that. – Mark May 04 '10 at 16:25
  • If items are not added the list L, or rather periodically deleted from L after L reaches some set maximum (but before a collision is found), any idea on what effect that would have on the 2^(n/2) birthday bound. – Mark May 04 '10 at 17:13
  • @Mark: If you limit the size of L to k where k<2^(n/2), then you would need about (2^n)/k iterations to find a collision. – interjay May 04 '10 at 17:20
  • I really appreciate that. Sorry for not updating your status yet, but when I tried to register just now and, at other times in the past, it gives me some confusing directives about having to join Yahoo or something, so I always bail out. – Mark May 04 '10 at 17:32
  • Maybe you can number crunch this: There are m groups of messages, each group with a maximum of k members. a collision is only relevant if it involves the members of the same group. How many hash evaluations to get such a collision. [So m signifies the number of subgroups of messages - not a particular message] – Mark May 04 '10 at 18:10
  • I mean the collision has to involve members of the same group. – Mark May 04 '10 at 18:11
  • @Mark: If k is much smaller than 2^(n/2) then the birthday paradox won't come into play, and there will be a very small chance that a group will have a collision. So you'll need a lot of hash evaluations: if I'm not mistaken, about 2^(n+1). – interjay May 04 '10 at 21:55