Techniques to allow a security policy language to accommodate anonymous credentials are described. A policy statement in a security policy language can reference an anonymous credential. When the policy statement is evaluated to decide whether to grant access to a resource mediated by the policy statement, the anonymous credential is used. The policy language can be implemented to allow one anonymous credential to delegate access-granting rights to another anonymous credential. Furthermore, an anonymous credential can be re-randomized to avoid linkage between uses of the anonymous credential, which can compromise anonymity.