Biometrics, such as fingerprints, provide a great tool for personalized authentication. While people are usually willing to submit their biometric information to government agencies, they are less likely to do so for commercial companies without a guarantee of privacy protection. This project will have significant societal impact by triggering wide acceptability of large-scale biometrics enabled applications. The primary technological hurdle faced by large scale biometric systems today is the ability to address two competing objectives: (1) provide fast matching of a biometric against a large database of stored biometric readings and (2) provide privacy of the biometrics in the database such that it can withstand malicious attacks. Existing solutions tackle either of the two problem but not both simultaneously. Tackling the two problems in an integrated fashion is non-trivial as any solution to conceal the biometric data to ensure privacy involves breaking down the structure inherent in the biometric template, thus making it extremely challenging to index the records efficiently. This project presents a unified approach by developing "cryptographically hidden" biometric templates which will lend themselves to fast searches. This effort will draw upon new research in the fields of biometrics, databases, and coding theory.