An authentication server transmits a random number to and receives a other information from a service provider. Later, the first random number is received from a requester and a provider identifier, the received other information and provider authentication policy requirements are transmitted to the requester. A user identifier and validation information are received from the requester. The received validation information is determined to correspond to the provider authentication policy requirements, and compared with stored user validation information associated with the received user identifier to authenticate the requester. A message, including both the random number and other information, signed with a credential of the requesting user is received and transmitted to the first provider.