Attribute-based authentication is considered a cornerstone component to achieve scalable fine-grained access control in the fast growing market of cloud-based services. Unfortunately, it also poses a privacy concern. Users attributes should not be linked to the users identity and spread across different organizations. To tackle this issue, several solutions have been proposed such as Privacy Attribute-Based Credentials (Privacy-ABCs), which support pseudonym-based authentication with embedded attributes. Privacy-ABCs allow users to establish anonymous accounts with service providers while hiding the identity of the user under a pseudonym. However, Privacy-ABCs require the selective disclosure of the attribute values towards service providers. Other schemes such as Attribute Base Signatures (ABS) and mesh signatures do not require the disclosure of attributes; unfortunately, these schemes do not cater for pseudonym generation in their construction, and hence cannot be used to establish anonymous accounts. In this paper, we propose a pseudonym-based signature scheme that enables unlinkable pseudonym self-generation with embedded attributes, similarly to Privacy-ABCs, and integrates a secret sharing scheme in a similar fashion to ABS and mesh signature schemes for attribute verification. Our proposed scheme also provides verifiable collusion, enabling users to share attributes according to the service providers policies.