  Computationally efficient, accurate, and privacy-preserving data storage and
retrieval are among the key challenges faced by practical deployments of
biometric identification systems worldwide. In this work, a method of protected
indexing of biometric data is presented. By utilising feature-level fusion of
intelligently paired templates, a multi-stage search structure is created.
During retrieval, the list of potential candidate identities is successively
pre-filtered, thereby reducing the number of template comparisons necessary for
a biometric identification transaction. Protection of the biometric probe
templates, as well as the stored reference templates and the created index is
carried out using homomorphic encryption. The proposed method is extensively
evaluated in closed-set and open-set identification scenarios on publicly
available databases using two state-of-the-art open-source face recognition
systems. With respect to a typical baseline algorithm utilising an exhaustive
search-based retrieval algorithm, the proposed method enables a reduction of
the computational workload associated with a biometric identification
transaction by 90%, while simultaneously suffering no degradation of the
biometric performance. Furthermore, by facilitating a seamless integration of
template protection with open-source homomorphic encryption libraries, the
proposed method guarantees unlinkability, irreversibility, and renewability of
the protected biometric data.
