  Biometric recognition encompasses two operating modes. The first one is
biometric identification which consists in determining the identity of an
individual based on her biometrics and requires browsing the entire database
(i.e., a 1:N search). The other one is biometric authentication which
corresponds to verifying claimed biometrics of an individual (i.e., a 1:1
search) to authenticate her, or grant her access to some services. The matching
process is based on the similarities between a fresh and an enrolled biometric
template. Considering the case of binary templates, we investigate how a highly
populated database yields near-collisions, impacting the security of both the
operating modes. Insight into the security of binary templates is given by
establishing a lower bound on the size of templates and an upper bound on the
size of a template database depending on security parameters. We provide
efficient algorithms for partitioning a leaked template database in order to
improve the generation of a master-template-set that can impersonates any
enrolled user and possibly some future users. Practical impacts of proposed
algorithms are finally emphasized with experimental studies.
