A method authenticates an encryption of a probe vector of biometric data based on an encryption of an enrollment vector of the biometric data using consistency of discriminative elements of the biometric data. The method determines an encryption of a first distance between discriminative elements of an enrollment vector stored at a server and a probe vector presented for an authentication. The method also determines an encryption of a second distance between discriminative elements of a first consistency vector stored at the server and a second consistency vector presented for the authentication. Next, the biometric data is authenticated based on encryptions of the first and the second distances.