Embodiments disclosed herein are directed to methods and systems of password-based threshold authentication, which distributes the role of an authentication server among multiple servers. Any t servers can collectively verify passwords and generate authentication tokens, while no t−1 servers can forge a valid token or mount offline dictionary attacks.