Cryptology ePrint Archive: Report 2006/332
Improved Efficiency for Private Stable Matching
Matthew Franklin and Mark Gondree and Payman Mohassel
Abstract: At Financial Crypto 2006, Golle presented a novel framework for the privacy preserving computation of a stable matching (stable marriage). We show that the communication complexity of Golle's main protocol is substantially greater than what was claimed in that paper, in part due to surprising pathological behavior of Golle's variant of the Gale-Shapley stable matching algorithm. We also develop new protocols in Golle's basic framework with greatly reduced communication complexity.
Category / Keywords: stable matching, stable marriage, Gale-Shapley, privacy-preserving
Publication Info: This is the full version of an article to appear at CT-RSA 2007.
Date: received 29 Sep 2006, last revised 29 Sep 2006
Contact author: mohassel at cs ucdavis edu
Available format(s): PDF | BibTeX Citation
Version: 20061005:144356 (All versions of this report)
Short URL: ia.cr/2006/332
[ Cryptology ePrint archive ]