DISTRIBUTED CHALLENGE-RESPONSE AUTHENTICATION

A distributed challenge-response protocol is carried out between a verifier and a prover. The verifier comprises servers storing respective shares of a set of challenge-response pairs. A particular challenge of one of the challenge-response pairs is sent to the prover, and a response to the challenge is received from the prover. The received response is authenticated as an appropriate response to the particular challenge based on indications from respective ones of at least a subset of the servers as to whether or not the received response matches respective reconstructed responses computed by those servers. A given one of the servers may be configured to reconstruct the particular challenge using information associated with the share stored in the given server and information associated with at least one other share stored in at least one other server, with the reconstructed challenge being to be sent to the prover as the particular challenge.