Users are typically authenticated by their passwords. Because people are known to choose convenient passwords, which tend to be easy to guess, authentication protocols have been developed that protect user passwords from guessing attacks. These proposed protocols, however, use more messages and rounds than those protocols that are not resistant to guessing attacks. This paper gives new protocols that are resistant to guessing attacks and also optimal in both messages and rounds, thus refuting the previous belief that protection against guessing attacks makes an authentification protocol inherently more expensive.