Secure authentication protocols, particularly well-suited for use in authenticating mobile communications devices having limited computational resources, are disclosed. In an illustrative embodiment, a network-based communication system includes a client device and at least two servers. First and second shares are generated from a first password associated with the client device, and stored in respective first and second servers. The client device submits additional information associated therewith to at least one of the first and second servers. Each of the first and second shares has the property that it is infeasible to determine solely therefrom correspondence of the additional information with the first password. The first and second servers then utilize the respective first and second shares to collectively determine said correspondence of the additional information with the first password.