Secret values used in a multi-server authentication scheme are updated. Information is authenticated in a system comprising a plurality of processing devices each adaptable for communication with one or more other devices. The information is authenticated by generating at least first and second shares of a first password associated with a first device (such as a client device); storing the first and second shares in respective second and third devices (such as authentication server devices); updating the first and second shares using a secret value T; assigning a version number to the updated first and second shares; and upon submission of additional information associated with the first device to at least one of the second and third devices, the second and third devices utilizing the respective updated first and second shares for a given version number to collectively determine a correspondence of the additional information with the first password.