The proximity-testing problem can be reduced to the private equality testing (PET) problem, in which parties find out whether or not they hold the same input (drawn from a low-entropy distribution) without revealing any other information about their inputs to each other. While previous works analyze the 2-party PET special case (and its LBS application), in this work we consider highly-efficient schemes for the multiparty case with no honest majority. We provide schemes for both a direct-communication setting and a setting with a honest-but-curious mediating server that does not learn the users’ inputs. Our most efficient scheme takes 2 rounds, where in each round each user sends only a couple of ElGamal ciphertexts.
Category / Keywords: cryptographic protocols / Multiparty Computation, Location Privacy Publication Info: Preliminary version at ICALP 2012 Date: received 4 Jul 2012 Contact author: gelles at cs ucla edu Available format(s): PDF | BibTeX Citation Version: 20120705:121931 (All versions of this report) Short URL: ia.cr/2012/378