AbstractBiometrics make human identification possible with a sample of a biometric trait and an associated database. Classical identification techniques lead to privacy concerns. This paper introduces a new method to identify someone using his biometrics in an encrypted way. Our construction combines Bloom Filters with Storage and Locality‐Sensitive Hashing. We apply this error‐tolerant scheme, in a Hamming space, to achieve biometric identification in an efficient way. This is the first non‐trivial identification scheme dealing with fuzziness and encrypted data. Copyright © 2010 John Wiley & Sons, Ltd.