In one embodiment, a set of servers generates at least one challenge that is sent to a client. The servers receive from the client a response that includes a message generated as a function of the challenge. The response also includes a digital signature computed on the message using a secret key of a key pair generated for a current epoch. The client is authenticated based on indications from respective ones of the servers as to whether or not the received response is accepted as valid by that server. Other embodiments involve interaction between a set of servers and a relying party in authenticating a passcode, password or other information received from a client. The client in some embodiments may comprise a connected authentication token or other type of hardware or software authentication token.