Access control systems using the latest biometric technologies can offer a higher level of security than conventional password-based systems. Their widespread deployments, however, can severely undermine individuals' rights of privacy. Biometric signals are immutable and can be exploited to associate individuals' identities to sensitive personal records across disparate databases. In this paper, we propose the Anonymous Biometric Access Control (ABAC) system to protect user anonymity. The ABAC system uses novel Homomorphic Encryption (HE) based protocols to verify membership of a user without knowing his/her true identity. To make HE-based protocols scalable to large biometric databases, we propose the k -Anonymous Quantization (kAQ) framework that provides an effective and secure tradeoff of privacy and complexity. kAQ limits server's knowledge of the user to k maximally dissimilar candidates in the database, where k controls the amount of complexity-privacy tradeoff. kAQ is realized by a constant-time table lookup to identity the k candidates followed by a HE-based matching protocol applied only on these candidates. The maximal dissimilarity protects privacy by destroying any similarity patterns among the returned candidates. Experimental results on iris biometrics demonstrate the validity of our framework and illustrate a practical implementation of an anonymous biometric system.