In many mobile crowdsensing scenarios it is desirable to give micro-payments to contributors as an incentive for their participation. However, to further encourage participants to use the system, one important requirement is protection of user privacy. In this work we present a reverse auction mechanism as an efficient way to offer incentives to users by allowing them to determine their own price for the data they provide, but also as a way to motivate them to submit better quality data. At the same time our auction protocol guarantees bidders’ anonymity and suggests a new rewarding mechanism that enables winners to claim their reward without being linked to the data they contributed. Our protocol is scalable, can be applied to a large class of auctions and remains both computation- and communication-efficient so that it can be run to the mobile devices of users.