GSM is the most popular standard for wireless cellular networks with 3 billion handsets in use worldwide. One of the critical components in the GSM architecture is the authentication protocol. The current protocol has several drawbacks such as one- way entity authentication, memory overhead in the VLR and bandwidth consumption between the HLR and VLR. Several solutions have been proposed to establish mutual entity authentication and to improve performance. However, they either cannot provide flaw-free bilateral entity authentication or impose more network overhead. In this paper, we propose a new approach to mutual entity authentication based on symmetric polynomials. In the proposed protocol, each MS is allocated a share of the symmetric polynomial during initial authentication. In subsequent authentication requests, the MS and VLR authenticate each other using the polynomial share. The proposed solution not only provides secure bilateral authentication, but also decreases the memory overhead in the VLR and the required connection bandwidth