  In location-based services(LBSs), it is promising for users to crowdsource
and share their Point-of-Interest(PoI) information with each other in a common
cache to reduce query frequency and preserve location privacy. Yet most studies
on multi-user privacy preservation overlook the opportunity of leveraging their
service flexibility. This paper is the first to study multiple users' strategic
cooperation against an adversary's optimal inference attack, by leveraging
mutual service flexibility. We formulate the multi-user privacy cooperation
against the adversary as a max-min adversarial game and solve it in a linear
program. Unlike the vast literature, even if a user finds the cached
information useful, we prove it beneficial to still query the platform to
further confuse the adversary. As the linear program's computational complexity
still increases superlinearly with the number of users' possible locations, we
propose a binary obfuscation scheme in two opposite spatial directions to
achieve guaranteed performance with only constant complexity. Perhaps
surprisingly, a user with a greater service flexibility should query with a
less obfuscated location to add confusion. Finally, we provide guidance on the
optimal query sequence among LBS users. Simulation results show that our
crowdsourced privacy protection scheme greatly improves users' privacy as
compared with existing approaches.

Cryptography and Security;Computer Science and Game Theory