Biometrics provides the user with an effective tool for authentication and is becoming a strong competitor in current authentication mechanisms. However, the concerns about biometrics regarding template security, privacy and revocability impede its further application to network-based scenarios. The authors propose a novel fingerprint minutiae-based scheme to achieve reliable mutual authentication over insecure channels. In the proposed scheme, a private template is generated which is completely random and independent of the minutiae, thus providing template protection, privacy preservation and revocability. A private matching scheme is embedded in an authentication protocol to ensure that both a server and a user can verify each other by matching the template against the query minutiae without revealing their respective inputs.