Crowdsensing requires scalable privacy-preserving authentication that allows users to send anonymously sensing reports, while enabling eventual anonymity revocation in case of user misbehavior. Previous research efforts already provide efficient mechanisms that enable conditional privacy through pseudonym systems, either based on Public Key Infrastructure (PKI) or Group Signature (GS) schemes. However, previous schemes do not enable users to self-generate an unlimited number of pseudonyms per user to enable users to participate in diverse sensing tasks simultaneously, while preventing the users from participating in the same task under different pseudonyms, which is referred to as sybil attack. This paper addresses this issue by providing a scalable privacy-preserving authentication solution for crowdsensing, based on a novel pseudonym-based signature scheme that enables unlinkable-yet-accountable pseudonymity. The paper provides a detailed description of the proposed scheme, the security analysis, the performance evaluation, and details of how it is implemented and integrated into a real crowdsensing platform.