With the rapid growth of electronic and mobile commerce today, how to design a secure and efficient remote user authentication scheme with resource-limited devices over insecure networks has become an important issue. In this paper, we present a robust authentication scheme for the mobile device (a non-tamper-resistant device in which the secret authentication information stored in it could be retrieved) to solve the challenging lost device problem. It tries to satisfy the following advanced essential security features: (1) protecting user privacy in terms of anonymity and non-traceability, (2) supporting session keys with perfect forward secrecy, and (3) secure even for the case of lost devices, in addition to the conventional security requirements. The security of our scheme is based on the quadratic residue assumption, which has the same complexity as in solving the discrete logarithm problem. However, the computation of the quadratic congruence is very efficient. It only needs one squaring and one modular operations in the mobile device end, which is much cheaper than the expensive modular exponentiation used in those schemes based on the discrete logarithm problem. Thus, using the quadratic congruence, our scheme can achieve robustness and efficiency, even for the non-tamper-resistant mobile device.