Multi Party Computation Motivated by the Birthday Problem

Keywords: ecure multi-party computation, birthday paradox, privacy-preserving, communication complexity


Suppose there are n people in a classroom and we want to decide if there are two of them who were born on the same day of the year. The well-known birthday paradox is concerned with the probability of this event and is discussed in many textbooks on probability. In this paper we focus on cryptographic aspects of the problem: how can we decide if there is a collision of birthdays without the participants disclosing their respective date of birth. We propose several procedures for solving this in a privacy-preserving way and compare them according to their computational and communication complexity.


Download data is not yet available.


Abramson, Morton and Moser, WOJ. More birthday surprises. The American Mathematical Monthly, 77(8):856--858, 1970.

Alon, Noga, Caro, Yair, and Yuster, Raphael. Covering the edges of a graph by a prescribed tree with minimum overlap. journal of combinatorial theory, Series B, 71(2):144--161, 1997.

Bárász, Mihály, Ligeti, Péter, Lója, Krisztina, Mérai, László, and Nagy, Dániel A. Another twist in the dining cryptographers’ protocol. Tatra Mountains Mathematical Publications, 57(1):85--99, 2013.

Bondy, John Adrian, Murty, Uppaluri Siva Ramachandra, et al. Graph theory with applications, volume 290. Citeseer, 1976.

Boudot, Fabrice, Schoenmakers, Berry, and Traore, Jacques. A fair and efficient solution to the socialist millionaires problem. Discrete Applied Mathematics, 111(1-2):23--36, 2001.

Chaum, David. The dining cryptographers problem: Unconditional sender and recipient untraceability. Journal of cryptology, 1(1):65--75, 1988.

Dor, Dorit and Tarsi, Michael. Graph decomposition is npc-a complete proof of holyer's conjecture. In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 252--263. ACM, 1992.

Ergun, Ozlem, Kuyzu, Gultekin, and Savelsbergh, Martin. The lane covering problem. Manuscript, 2003.

Goldreich, Oded. Foundations of Cryptography: Volume 2, Basic Applications. Cambridge University Press, New York, NY, USA, 2004.

Hirt, Martin. Multi Party Computation: Efficient Protocols, General Adversaries, and Voting. Hartung-Gorre, 2001.

Holyer, Ian. The np-completeness of some edge-partition problems. SIAM Journal on Computing, 10(4):713--717, 1981.

Jukna, Stasys and Kulikov, Alexander S. On covering graphs by complete bipartite subgraphs. Discrete Mathematics, 309(10):3399--3403, 2009.

Lin, Hsiao Ying and Tzeng, Wen Guey. An efficient solution to the millionaires problem based on homomorphic encryption. In International Conference on Applied Cryptography and Network Security, pages 456--466. Springer, 2005.

Mathis, Frank H. A generalized birthday problem. SIAM Review, 33(2):265--270, 1991.

Maurer, Ueli. Secure multi-party computation made simple. Discrete Applied Mathematics, 154(2):370--381, 2006.

Pinkas, Benny. Fair secure two-party computation. In International Conference on the Theory and Applications of Cryptographic Techniques, pages 87--105. Springer, 2003.

Shyu, Tay Woei. Decomposition of complete graphs into paths and stars. Discrete Mathematics, 310(15-16):2164--2169, 2010.

Wagner, David. A generalized birthday problem. In Annual International Cryptology Conference, pages 288--304. Springer, 2002.

Yao, Andrew C. Protocols for secure computations. In Foundations of Computer Science, 1982. SFCS'08. 23rd Annual Symposium on, pages 160--164. IEEE, 1982.

Yao, Andrew Chi-Chih. How to generate and exchange secrets. In Foundations of Computer Science, 1986., 27th Annual Symposium on, pages 162--167. IEEE, 1986.

How to Cite
Hudoba, P., & Burcsi, P. (2019). Multi Party Computation Motivated by the Birthday Problem. Acta Cybernetica, 24(1), 29-41.
Special Issue of the 11th Conference of PhD Students in Computer Science