@inbook {IOPORT.06101173,
    author       = {Gelles, Ran and Ostrovsky, Rafail and Winoto, Kina},
    title        = {Multiparty proximity testing with dishonest majority from equality testing.},
    year         = {2012},
    booktitle    = {Automata, languages, and programming. 39th international colloquium, ICALP 2012, Warwick, UK, July 9--13, 2012. Proceedings, Part II},
    isbn         = {978-3-642-31584-8},
    pages        = {537-548},
    publisher    = {Berlin: Springer},
    doi          = {10.1007/978-3-642-31585-5_48},
    abstract     = {Summary: 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 constant 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.},
    identifier   = {06101173},
}