Paper 2023/1789

Fast and Secure Oblivious Stable Matching over Arithmetic Circuits

Arup Mondal, Ashoka University
Priyam Panda, Ashoka University
Shivam Agarwal, Georgia Institute of Technology
Abdelrahaman Aly, Technology Innovation Institute
Debayan Gupta, Ashoka University

The classic stable matching algorithm of Gale and Shapley (American Mathematical Monthly '69) and subsequent variants such as those by Roth (Mathematics of Operations Research '82) and Abdulkadiroglu et al. (American Economic Review '05) have been used successfully in a number of real-world scenarios, including the assignment of medical-school graduates to residency programs, New York City teenagers to high schools, and Norwegian and Singaporean students to schools and universities. However, all of these suffer from one shortcoming: in order to avoid strategic manipulation, they require all participants to submit their preferences to a trusted third party who performs the computation. In some sensitive application scenarios, there is no appropriate (or cost-effective) trusted party. This makes stable matching a natural candidate for secure computation. Several approaches have been proposed to overcome this, based on secure multiparty computation (MPC), fully homomorphic encryption, etc.; many of these protocols are slow and impractical for real-world use. We propose a novel primitive for privacy-preserving stable matching using MPC (i.e., arithmetic circuits, for any number of parties). Specifically, we discuss two variants of oblivious stable matching and describe an improved oblivious stable matching on the random memory access model based on lookup tables. To explore and showcase the practicality of our proposed primitive, we present detailed benchmarks (at various problem sizes) of our constructions using two popular frameworks: SCALE-MAMBA and MP-SPDZ.

Available format(s)
Cryptographic protocols
Publication info
privacy-preservingarithmetic circuitsmulti-party computationstable matching
Contact author(s)
arup mondal_phd19 @ ashoka edu in
priyam panda @ alumni ashoka edu in
s agarwal @ gatech edu
abdelrahaman aly @ tii ae
debayan gupta @ ashoka edu in
2023-11-24: approved
2023-11-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Arup Mondal and Priyam Panda and Shivam Agarwal and Abdelrahaman Aly and Debayan Gupta},
      title = {Fast and Secure Oblivious Stable Matching over Arithmetic Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1789},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.