Authentication is a fundamental step in achieving security. Most often the authentication is asymmetric, in the sense that the server authenticates a client, while the client has no means to ascertain it is interacting with the legitimate server. Many attacks leverage this asymmetry. Consequently mutual authentication becomes a crucial aspect. There are only a few mutual authentication protocols mostly based on passwords or certificates. However, due to the emergent requirements of user privacy what is needed is a mutual authentication mechanism that preserves user privacy while providing strong security guarantees. Further, any practical mutual authentication scheme must support a versatile mechanism for user account recovery. Bilinear pairings is a mathematical tool that enables a party to prove the possession of a secret without having to reveal the secret, and is the basis for many modern cryptographic constructs such as Zero-Knowledge Proofs. In this paper, we propose a novel mutual authentication scheme, BP-MAP, that leverages bilinear pairings to provide a secure, efficient, and convenient mutual authentication system. BP-MAP scheme consists of protocols for client registration, mutual authentication, account recovery and reset. This is achieved by a non-trivial application of bilinear pairings to realize a fruitful combination of privacy, security and user-convenience. Security of BP-MAP scheme and its constituent protocols is established, and it is argued that BP-MAP is computationally efficient when compared to state-of-the-art protocols that provide similar functions.