Authentication is an important security service. Sometimes, key agreement is also included in the authentication scheme. Until now, several authentication protocols, and authentication and key agreement protocols have been proposed. These protocols range from complex public-key cryptosystems to simple hash-based password authentication schemes. Recently, preserving the user anonymity during an authentication process has gained a great deal of attention. In this dissertation, we first provide an overview of various authentication schemes and survey the existing literature. We then present four new authentication protocols: two of which are elliptic curve cryptography-based authentication and key agreement protocols; the third is a simple hash- based password authentication protocol; and finally, there is an RSA-based identification and key agreement protocol. Compared to other protocols, our protocols are not only secure and efficient, but also preserve anonymity during the authentication process.