View publication
| Title | Beating the Birthday Paradox in Dining Cryptographer Networks |
| Authors | Pablo Garcia, Jeroen Van de Graaf, Alejandro Hevia, Alfredo Viola |
| Publication date | 2014 |
| Abstract | A Dining Cryptographer Network (DC-Net) allows multiple players to broadcast messages without disclosing the identity of the sender. However, due to their probabilistic nature, message collisions can occur, meaning that two or more messages sent by different participants end up occupying the same slot, causing these messages to be lost. In this work, we evaluate two different strategies to deal with collisions. When repeating a DC-net sequentially, honest parties who see that their message did not collide can switch to sending a null message, effectively decreasing the collision probability in subsequent rounds. When repeating a DC-net in parallel no feedback exists, and there will almost remain a non-zero probability that one message collides in every round. We analyze both strategies with respect to the number of parties, the number of slots, the number of repetitions and the probability of success. We obtain exact but rather convoluted combinatorial formulas for both cases, together with more tractable approximations, the correctness of which has been confirmed by simulations. |
| Pages | 179-198 |
| Conference name | International Conference on Cryptology and Information Security in Latin America |
| Publisher | Springer-Verlag (Berlin/Heidelberg, Germany) |
| Reference URL |
|