A party can authenticate itself by interacting with multiple servers without revealing the shared secret to any of the involved parties. The stored shared secret is strengthened and broken into shares and saved on the servers. The shared secret is safe against offline brute force attack unless all servers where the shares are stored are compromised. The compromise of any single server, or multiple servers—but less than the maximum number—will not allow the attacker to do a brute force analysis on the shared secret. This back end security enhancement is suitable for probabilistic front end authentication algorithms.