The subject disclosure is directed towards processing requests for accessing a service provider. After examining at least one security token, a public key and a portion of attribute information are identified. An authentication component is accessed and applied to the public key. A unique user identifier is employed in generating the public key. The authentication component is generated using information from at least one revoked security token or at least one valid security token. The authentication component is configured to prove validity of the at least one security token.