This work addresses the critical problem of authentication in mobile ad hoc networks. It includes a new approach based on the Zero-Knowledge cryptographic paradigm where two different security levels are defined. The first level is characterized by the use of an NP-complete graph problem to describe an Access Control Protocol, while the highest level corresponds to a Group Authentication Protocol based on a hard-on-average graph problem. The main goal of the proposal is to balance security strength and network performance. Therefore, both protocols are scalable and decentralized, and their requirements of communication, storage and computation are limited.