Multi Party Computation Motivated by the Birthday Problem
Abstract
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.
Downloads
References
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.
