Toward Practical Secure Stable Matching

TitleToward Practical Secure Stable Matching
Publication TypeJournal Article
Year of Publication2017
AuthorsRiazi, S. M., E. M. Songhori, A. - R. Sadeghi, T. Schneider, and F. Koushanfar
JournalProceedings on Privacy Enhancing Technologies
Start Page62
Date Published01/2017
KeywordsGarbled Circuits, Privacy-Preserving, Stable matching

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.

[Proceedings on Privacy Enhancing Technologies] Toward Practical Secure Stable Matching.pdf847.75 KB


Theme by Danetsoft and Danang Probo Sayekti inspired by Maksimer