Paper 2012/378

Multiparty Proximity Testing with Dishonest Majority from Equality Testing

Ran Gelles, Rafail Ostrovsky, and Kina Winoto

Abstract

Motivated by the recent widespread emergence of location-based services (LBS) over mobile devices, we explore efficient protocols for proximity-testing. Such protocols allow a group of friends to discover if they are all close to each other in some physical location, without revealing their individual locations to each other. We focus on hand-held devices and aim at protocols with very small communication complexity and a small number of rounds. 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Preliminary version at ICALP 2012
Keywords
Multiparty ComputationLocation Privacy
Contact author(s)
gelles @ cs ucla edu
History
2012-07-05: received
Short URL
https://ia.cr/2012/378
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/378,
      author = {Ran Gelles and Rafail Ostrovsky and Kina Winoto},
      title = {Multiparty Proximity Testing with Dishonest Majority from Equality Testing},
      howpublished = {Cryptology ePrint Archive, Paper 2012/378},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/378}},
      url = {https://eprint.iacr.org/2012/378}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.