Anonymous single sign-on systems allow users to use a single credential to access multiple services protected by verifiers without revealing their personal information, which is especially important due to privacy regulations such as GDPR. In this paper, we introduce a new strong privacy-preserving single sign-on scheme, dubbed PriSign, based on our proposed attribute-based credential with traceability (ABCT), attribute-based credential with blindness (ABCB), and threshold inner-product functional encryption (TIPFE). Compared with the existing state-of-the-art solutions, PriSign presents three improvements: (1) users can obtain different types of tickets according to the attribute disclosure policies enforced by the ticket issuer to support fine-grained access control; (2) users can hide access tokens and designate a verifier for tokens according to a verifier’s policy jointly issued by multiple policymakers, meaning that non-designated verifiers cannot obtain any information about the tokens; (3) we innovatively use a threshold approach to issue policy keys online in order for verifiers to achieve proxy re-verification services in an unstable cloud environment. We implement PriSign and compare the performance with other ASSO systems in the personal laptop, and the results prove its practicability.