Mutual authentication between a service provider and its users is essential to prevent unauthorized adversaries from misutilizing system resources. The traditional method of password table lookups is not scalable and is susceptible to overloading. Therefore this paper proposes a Cellular Automata based Remote-Mutual Authentication (CARMA) Scheme to reduce the complexity of encryption and hash-based cryptosystems, as well as avoid table lookups. CARMA also uses cache-based nonces to avoid synchronization problems and thwart replay attacks. The inherent parallelism of cellular automata provides for its fast implementation.