Aspects of group signatures with probabilistic revocation are described. In one example employing these aspects, at least one computing device can map an alias token to an alias code comprising a plurality of alias code segments. Each of the alias code segments is based at least in part on a set of orthogonal codes. Also, each of the alias code segments corresponds to a segment of the alias token. A revocation code is based at least in part on a plurality of revoked alias codes. One of the alias code segments and a corresponding segment of the revocation code can be utilized to determine a revocation status of the alias token.