Provably Secure Anonymous-yet-Accountable Crowdsensing with Scalable Sublinear Revocation

Group signature schemes enable anonymous-yetaccountable communications. Such a capability is extremely useful for applications, such as smartphone-based crowdsensing and citizen science. However, the performance of modern group signature schemes is still inadequate to manage large dynamic groups. In this paper, we design the first provably secure verifier-local revocation (VLR) - based group signature scheme that supports sublinear revocation, named Sublinear Revocation with Backward unlinkability and Exculpability (SRBE). To achieve this performance gain, SRBE introduces time bound pseudonyms for the signer. By introducing lowcost short-lived pseudonyms with sublinear revocation checking, SRBE drastically improves the efficiency of the groupsignature primitive. The backward-unlinkable anonymity of SRBE guarantees that even after the revocation of a signer, her previously generated signatures remain unlinkable across epochs. This behavior favors the dynamic nature of real-world crowdsensing settings. We prove its security and discuss parameters that influence its scalability. Using SRBE, we also implement a prototype named GROUPSENSE for anonymousyet- accountable crowdsensing, where our experimental findings confirm GROUPSENSE’s scalability. We point out the open problems remaining in this space.