Cloud-assisted secure biometric identification with sub-linear search efficiency

• DOI: 10.1007/s00500-019-04401-9
• Publication Date: 2019-10-04T06:38:46Z
• Authors: Youwen Zhu; Xingxin Li; Jian Wang; Jing Li
• Keywords: Tree (set theory); Identification

Cloud computing has been one of the critical solutions to reduce heavy storage and computation burden of biometric identification. To protect the privacy of biometric data against untrusted cloud servers, outsourced biometric databases are usually encrypted by users. Performing biometric identification over encrypted data without revealing privacy to cloud servers attracts more and more attention. Several secure biometric identification solutions have been proposed to solve this challenging problem. However, these schemes still suffer from various limitations, such as low search efficiency and heavy computation burden on users. In this paper, we propose a novel cloud-assisted biometric identification scheme based on the asymmetric scalar-product preserving encryption (ASPE) and spatial data structures such as the R-tree index, which simultaneously achieves sub-linear search efficiency and low computation burden on users. Specifically, we construct an R-tree index on the biometric dataset and encrypt the index with ASPE. Then we modify the original search algorithm in the R-tree index and design a secure search algorithm based on ASPE to find the nearest neighbor result over the encrypted R-tree index. Through theoretical analysis and extensive experiments, we demonstrate the effectiveness and efficiency of our proposed approach.