Paper 2006/332

Improved Efficiency for Private Stable Matching

Matthew Franklin, 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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. This is the full version of an article to appear at CT-RSA 2007.
Keywords
stable matchingstable marriageGale-Shapleyprivacy-preserving
Contact author(s)
mohassel @ cs ucdavis edu
History
2006-10-05: received
Short URL
https://ia.cr/2006/332
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/332,
      author = {Matthew Franklin and Mark Gondree and Payman Mohassel},
      title = {Improved Efficiency for Private Stable Matching},
      howpublished = {Cryptology ePrint Archive, Paper 2006/332},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/332}},
      url = {https://eprint.iacr.org/2006/332}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.