We study two-stage biometric identification systems that allow authentication without privacy leakage. In the enrollment phase, secret keys and two layers of the helper data for each user are generated. Additional to the helper data and secret keys, we also introduce private keys in the systems. In the identification phase, an unknown but previously enrolled user is observed, and the user's private key is also presented to the system. The system firstly compares the user with the first layer helper database, outputs a list, and obtains a set of user indices. Then the system compares the observed user with the users in the set. Therefore, the identification procedure avoids an exhaustive search and only has to do a comparison with some part of the users in the system, which leads to a systematic reduction of the search complexity. Fundamental trade-offs among the identification rate, the secret key rate, the private key rate, the helper data rate, and the list size rate are derived in the imposed two-stage biometric identification systems without privacy leakage. Moreover, the obtained results show that a private key can boost the identification rate and the secret key rate, as well as preserve privacy.
