The paper presents a solution for securing password-based authentication using Shamir’s $(k,n)$ threshold scheme, where $n$ password-derived secrets (shares) are created, and $k\leq n$ shares are necessary and sufficient for reconstructing the password. The solution is information-theoretically secure, with each share stored on a different host (Shareholder), requiring an attacker to compromise $k$ Shareholders to reconstruct the secret. To resist compromising the coordinating server (Dealer), the authors define a variant of Shamir’s scheme where the abscissas are unknown to the Dealer and Shareholders, making reconstruction impossible even if they are compromised. The authors have designed protocols for registration and authentication, analyzed scenarios with partially/totally compromised Dealer and/or Shareholders, and developed a prototype demonstrating the correct, effective, and efficient operation of the proposed method, providing a feasibility study for future cloud-based “authentication-as-a-service” implementations.