Authors: Pablo García, Jeroen van de Graaf, A.H., and Alfredo Viola.
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 always 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 demonstrated by simulations.
Ref: In Proceedings of Latincrypt 2014, Florianópolis, Brazil. Sept. 17-19, 2014. In proceedings, LNCS Volume 8895, 2015, pp 179-198.
Paper: PDF.