User authentication is a continual problem, particularly with mobile and handheld devices such as Personal Digital Assistants (PDAs), Smartcard, Laptops. User authentication is a difficult for every system providing safe access to precious, private information, or personalized services. User authentication is the primary line of defence for a handheld device that comes into the hands of an unauthorized individual. Password or Personal Identification Number (PIN) based authentication is the leading mechanism for verifying the identity of actual device users. Remote mutual authentication is the best solution for remote accessing in Wi-Fi environment. In this paper we propose a new remote mutual authentication scheme in wireless environment without maintaining the password table. This is based on ElGamal's. It provides high security and mutual authentication at a reasonable computational cost. Furthermore it restricts most of the current attacking mechanisms. It is simple and can be adopted in any kind of lightweight devices. © 2010 Springer-Verlag Berlin Heidelberg.