A Private Stable Matching AlgorithmAuthor: P. Golle.
To address these limitations, this paper proposes a private stable matching algorithm, based on the famous algorithm of Gale and Shapley [GS62]. Our private algorithm is run by a number of independent parties whom we call the Matching Authorities. As long as a majority of Matching Authorities are honest, our protocol correctly outputs a stable match, and reveals no other information than what can be learned from that match and from the preferences of participants controlled by the adversary. The security and privacy of our protocol are based on re-encryption mix networks and on an additively homomorphic semantically secure public-key encryption scheme such as Paillier.