Rafail Ostrovsky - Publications

Multyparty Proximity Testing with Dishonest Majority from Equality Testing

Ran Gelles, Rafail Ostrovsky, Kina Winoto


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 setting with a honest but-curious mediating server that does not learn the user’s inputs. Our most efficient scheme takes 2 rounds where in each round each user sends only a couple of EIGamal ciphertexts.

comment: ICALP 2012 PP:537-548

Fetch PDF file of the paper

Back to Publications List