Display omitted •We demonstrate privacy breaches into two password authentication schemes for WSNs.•Public-key techniques are indispensible to achieve user untraceability.•Our principle is applicable to two-factor authentication for universal environments.•We discuss the viable solutions to practical realization of user anonymity.•Experimental timings of related public-key operations on small devices are reported. Anonymity is among the important properties of two-factor authentication schemes for wireless sensor networks (WSNs) to preserve user privacy. Though impressive efforts have been devoted to designing schemes with user anonymity by only using lightweight symmetric-key primitives such as hash functions and block ciphers, to the best of our knowledge none has succeeded so far. In this work, we take an initial step to shed light on the rationale underlying this prominent issue. Firstly, we scrutinize two previously-thought sound schemes, namely Fan et al.’s scheme and Xue et al.’s scheme, and demonstrate the major challenges in designing a scheme with user anonymity. Secondly, using these two foremost schemes as case studies and on the basis of the work of Halevi–Krawczyk (1999) 44 and Impagliazzo–Rudich (1989) 43, we put forward a general principle: Public-key techniques are intrinsically indispensable to construct a two-factor authentication scheme that can support user anonymity. Furthermore, we discuss the practical solutions to realize user anonymity. Remarkably, our principle can be applied to two-factor schemes for universal environments besides WSNs, such as the Internet, global mobility networks and mobile clouds. We believe that our work contributes to a better understanding of the inherent complexity in achieving user privacy, and will establish a groundwork for developing more secure and efficient privacy-preserving two-factor authentication schemes.