PEAK: Privacy-Enhanced Incentive Mechanism for Distributed <i>K</i>-Anonymity in LBS

Abstract

To motivate users' assistance for protecting others' location privacy by distributed <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i> -anonymity in Location-Based Service (LBS), many incentive mechanisms have been proposed, where users obtain monetary compensation for their assistance. However, most existing distributed <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i> -anonymity incentive mechanisms rely on trusted third parties and ignore users' malicious strategies, which destroys LBS's distributed structure as well as leads to users' privacy leakage and incentive ineffectiveness. To solve the above problems, we propose a <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">P</u> rivacy- <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">E</u> nhanced incentive mech <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A</u> nism for distributed <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><u>K</u></i> -anonymity (PEAK). With determining the monetary transaction relationship and location transmission between users, PEAK enables the anonymous cloaking region construction without the trusted server. Meanwhile, PEAK devises role identification mechanism and accountability mechanism to restrain and punish malicious users, which protects users' location privacy and implements effective motivation on users' assistance. Theoretical analysis based on the game theory shows that PEAK constrains users' malicious strategies while satisfying individual rationality, computational efficiency, and satisfaction ratio. Extensive experiments based on the real-world dataset demonstrate that PEAK improves security and feasibility, especially reaching the success rate of anonymous cloaking region construction to more than 90 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\%$</tex-math></inline-formula> and decreasing the malicious users' utilities significantly.