Verification Protocol for Stable Matching from Conditional Disclosure of Secrets

Stable matching is an important problem that receives attention from researchers in several fields. In the problem setting, there are two sets with the same number of members. Each member has its matching preference. The goal is to find a one-to-one matching between each member of the two sets such that no pairs want to change the matching result. Since an instance of the stable matching problem may have more than one possible stable matching, Nakamura et al. proposed a multi-stakeholder environment with selectability property, and applied it to the stable matching problem as an example use case. In their setting, the computing server could freely choose to return any stable matching depending on the benefits of the clients and the computing server. Their protocol also offered verifiability, but only against a semi-honest verifying server. To address this issue, we propose a verification protocol for stable matching against a malicious server. Our verification protocol is constructed from CDS schemes for stable matching, which do not require any asymmetric-key cryptographic primitives. From the implementation result, our proposed protocol is 4 to 5 orders of magnitude faster than the previous work.