1. bookVolume 2017 (2017): Issue 1 (January 2017)
Journal Details
First Published
16 Apr 2015
Publication timeframe
4 times per year
access type Open Access

Toward Practical Secure Stable Matching

Published Online: 22 Dec 2016
Page range: 62 - 78
Received: 31 May 2016
Accepted: 02 Sep 2016
Journal Details
First Published
16 Apr 2015
Publication timeframe
4 times per year

The Stable Matching (SM) algorithm has been deployed in many real-world scenarios including the National Residency Matching Program (NRMP) and financial applications such as matching of suppliers and consumers in capital markets. Since these applications typically involve highly sensitive information such as the underlying preference lists, their current implementations rely on trusted third parties. This paper introduces the first provably secure and scalable implementation of SM based on Yao’s garbled circuit protocol and Oblivious RAM (ORAM). Our scheme can securely compute a stable match for 8k pairs four orders of magnitude faster than the previously best known method. We achieve this by introducing a compact and efficient sub-linear size circuit. We even further decrease the computation cost by three orders of magnitude by proposing a novel technique to avoid unnecessary iterations in the SM algorithm. We evaluate our implementation for several problem sizes and plan to publish it as open-source.


[1] Atila Abdulkadiroglu, Parag A Pathak, and Alvin E Roth. The New York city high school match. American Economic Review, pages 364-367, 2005.Search in Google Scholar

[2] Gilad Asharov, Yehuda Lindell, Thomas Schneider, and Michael Zohner. More efficient oblivious transfer and extensions for faster secure computation. In ACM CCS’13, pages 535-548. ACM, 2013.Search in Google Scholar

[3] Mihir Bellare, Viet Tung Hoang, Sriram Keelveedhi, and Phillip Rogaway. Efficient garbling from a fixed-key blockcipher. In IEEE S&P’13, pages 478-492. IEEE, 2013.Search in Google Scholar

[4] Ivan Damgård and Mads Jurik. A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system. In PKC’01, volume 1992 of LNCS, pages 119-136. Springer, 2001.Search in Google Scholar

[5] Pierre-Alain Fouque, Guillaume Poupard, and Jacques Stern. Sharing decryption in the context of voting or lotteries. In FC’01, volume 1962 of LNCS, pages 90-104. Springer, 2001.Search in Google Scholar

[6] Matthew Franklin, Mark Gondree, and Payman Mohassel. Improved efficiency for private stable matching. In CTRSA’ 07, volume 4377 of LNCS, pages 163-177. Springer, 2006.Search in Google Scholar

[7] Matthew Franklin, Mark Gondree, and Payman Mohassel. Multi-party indirect indexing and applications. In ASIACRYPT’07, volume 4833 of LNCS, pages 283-297.Springer, 2007.Search in Google Scholar

[8] David Gale and Lloyd S Shapley. College admissions and the stability of marriage. American Mathematical Monthly, pages 9-15, 1962.Search in Google Scholar

[9] David Gale and Marilda Sotomayor. Ms. Machiavelli and the stable matching problem. American Mathematical Monthly, pages 261-268, 1985.Search in Google Scholar

[10] Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious rams. Journal of the ACM (JACM), 43(3):431-473, 1996.Search in Google Scholar

[11] Philippe Golle. A private stable matching algorithm. In FC’06, volume 4107 of LNCS, pages 65-80. Springer, 2006.Search in Google Scholar

[12] S Dov Gordon, Jonathan Katz, Vladimir Kolesnikov, Fernando Krell, Tal Malkin, Mariana Raykova, and Yevgeniy Vahlis. Secure two-party computation in sublinear (amortized) time. In ACM CSS’12, pages 513-524. ACM, 2012.Search in Google Scholar

[13] Dan Gusfield and Robert W Irving. The stable marriage problem: Structure and algorithms, volume 54. MIT press Cambridge, 1989.Search in Google Scholar

[14] Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank. Extending oblivious transfers efficiently. In CRYPTO’03, volume 2729 of LNCS, pages 145-161. Springer, 2003.Search in Google Scholar

[15] Marcel Keller and Peter Scholl. Efficient, oblivious data structures for MPC. In ASIACRYPT’14, volume 8874 of LNCS, pages 506-525. Springer, 2014.Search in Google Scholar

[16] Vladimir Kolesnikov and Thomas Schneider. Improved garbled circuit: Free XOR gates and applications. In ICALP’08, volume 5126 of LNCS, pages 486-498. Springer, 2008.Search in Google Scholar

[17] Yehuda Lindell and Benny Pinkas. An efficient protocol for secure two-party computation in the presence of malicious adversaries. In EUROCRYPT’07,Search in Google Scholar

[18] Yehuda Lindell and Benny Pinkas. A proof of security of Yao’s protocol for two-party computation. Journal of Cryptology, 22(2):161-188, 2009.Search in Google Scholar

[19] Yehuda Lindell and Benny Pinkas. Secure two-party computation via cut-and-choose oblivious transfer. Journal of Cryptology, 25(4):680-722, 2012.Search in Google Scholar

[20] Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995.Search in Google Scholar

[21] Moni Naor and Kobbi Nissim. Communication preserving protocols for secure function evaluation. In STOC’01, pages 590-599. ACM, 2001.Search in Google Scholar

[22] Moni Naor, Benny Pinkas, and Reuben Sumner. Privacy preserving auctions and mechanism design. In ACM conference on Electronic Commerce (EC’99), pages 129-139.ACM, 1999.Search in Google Scholar

[23] National Residency Matching Program. http://www.nrmp.org.Search in Google Scholar

[24] Jesper Buus Nielsen and Claudio Orlandi. LEGO for twoparty secure computation. In TCC’09, volume 5444 of LNCS, pages 368-386. Springer, 2009.Search in Google Scholar

[25] Michael Ostrovsky. Stability in supply chain networks. American Economic Review, 98(3):897-923, 2008.Search in Google Scholar

[26] Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT’99, volume 1592 of LNCS, pages 223-238. Springer, 1999.Search in Google Scholar

[27] Vasilis Pappas, Fernando Krell, Binh Vo, Vladimir Kolesnikov, Tal Malkin, Seung Geol Choi, Wesley George, Angelos Keromytis, and Steve Bellovin. Blind seer: A scalable private dbms. In 2014 IEEE Symposium on Security and Privacy, pages 359-374. IEEE, 2014.Search in Google Scholar

[28] Benny Pinkas and Tzachy Reinman. Oblivious RAM revisited. In CRYPTO’10, volume 6223 of LNCS, pages 502-519. Springer, 2010.Search in Google Scholar

[29] Alvin E Roth. The economics of matching: Stability and incentives. Mathematics of operations research, 7(4):617-628, 1982.Search in Google Scholar

[30] Abhi Shelat and Chih-hao Shen. Two-output secure computation with malicious adversaries. In EUROCRYPT’11, volume 6632 of LNCS, pages 386-405. Springer, 2011.Search in Google Scholar

[31] Elaine Shi, T-H Hubert Chan, Emil Stefanov, and Mingfei Li. Oblivious RAM with O(log3 n) worst-case cost. In ASIACRYPT’11, volume 7073 of LNCS, pages 197-214. Springer, 2011.Search in Google Scholar

[32] Ebrahim M Songhori, Siam U Hussain, Ahmad-Reza Sadeghi, Thomas Schneider, and Farinaz Koushanfar. Tiny- Garble: Highly compressed and scalable sequential garbled circuits. In IEEE S&P’15, pages 411-428. IEEE, 2015.Search in Google Scholar

[33] Stable Matching Algorithms. http://www.dcs.gla.ac.uk/research/algorithms/stable/.Search in Google Scholar

[34] Emil Stefanov, Elaine Shi, and Dawn Song. Towards practical oblivious RAM. In NDSS’12, 2012.Search in Google Scholar

[35] Synopsys inc. Design compiler. http://www.synopsys.com/Tools/Implementation/RTLSynthesis/DesignCompiler, 2000.Search in Google Scholar

[36] Chung-Piaw Teo, Jay Sethuraman, and Wee-Peng Tan. Gale-Shapley stable marriage problem revisited: Strategic issues and applications. In Integer Programming and Combinatorial Optimization (IPCO’99), volume 1610 of LNCS, pages 429-438. Springer, 1999.Search in Google Scholar

[37] Chung-Piaw Teo, Jay Sethuraman, and Wee-Peng Tan. Gale-Shapley stable marriage problem revisited: Strategic issues and applications. Management Science, 47(9):1252-1267, 2001.Search in Google Scholar

[38] Xiao Wang, Hubert Chan, and Elaine Shi. Circuit ORAM: On tightness of the Goldreich-Ostrovsky lower bound. In ACM CCS’15, pages 850-861. ACM, 2015.Search in Google Scholar

[39] Andrew Yao. How to generate and exchange secrets. In FOCS’86, pages 162-167. IEEE, 1986.Search in Google Scholar

[40] Samee Zahur, Mike Rosulek, and David Evans. Two halves make a whole. In EUROCRYPT’15, volume 9057 of LNCS, pages 220-250. Springer, 2015.Search in Google Scholar

[41] Samee Zahur, Xiao Wang, Mariana Raykova, Adria Gascon, Jack Doerner, David Evans, and Jonathan Katz. Revisiting square root ORAM: Efficient random access in multi-party computation. 2016. In IEEE S&P’16. Online: http://ieeesecurityorg/TC/SP2016/papers/0824a218.pdf. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo