Secure and Scalable Face Retrieval via Cancelable Product Quantization

Haomiao Tang, Wenjie Li, Yixiang Qiu, Genping Wang, Shu-Tao Xia

Abstract

Despite the ubiquity of modern face retrieval systems, their retrieval stage is often outsourced to third-party entities, posing significant risks to user portrait privacy. Although homomorphic encryption (HE) offers strong security guarantees by enabling arithmetic computations in the cipher space, its high computational inefficiency makes it unsuitable for real-time, real-world applications. To address this issue, we propose Cancelable Product Quantization (CPQ), a highly efficient framework for secure face representation retrieval. Our hierarchical two-stage framework comprises: (i) a high-throughput cancelable PQ indexing module for fast candidate filtering, and (ii) a fine-grained cipher-space retrieval module for final precise face ranking. A tailored protection mechanism is designed to secure the indexing module for cancelable biometric authentication while ensuring efficiency. Experiments on benchmark datasets demonstrate that our method achieves a decent balance between effectiveness, efficiency, and security.

Introduction

Modern face retrieval systems frequently outsource the computationally intensive task of searching through massive databases to third-party cloud providers. However, this practice introduces significant privacy risks, as mathematical embeddings (latent representations) of faces can often be used to reconstruct original user portraits. While Homomorphic Encryption (HE) provides a cryptographic solution by allowing computations on encrypted data, its extreme computational overhead—often requiring seconds or minutes per query—renders it impractical for large-scale, real-time use. Conversely, efficient methods like Product Quantization (PQ) lack the necessary security to protect sensitive biometric data. This work introduces Cancelable Product Quantization (CPQ), a framework designed to bridge the gap between cryptographic security and real-time performance.

The Cancelable Product Quantization Framework

The CPQ framework employs a hierarchical two-stage retrieval pipeline to optimize both speed and security. The workflow involves three main entities: the Query User, the Trustworthy Image Owner, and the Computing Service Provider.

Overview of the proposed hierarchical two-stage retrieval framework, illustrating the interaction between the Image Owner, Query User, and Cloud Provider across the two stages of retrieval.

Stage 1: High-Throughput Cancelable PQ Indexing

Instead of performing an exhaustive search across the entire encrypted database using slow HE operations, the system first utilizes a "Cancelable PQ" module. This module quickly filters the database down to a small set of $K$ candidates. To protect the index, two key-bound obfuscation techniques are applied: random projection (transforming sub-vectors into an anonymized space) and codebook permutation (shuffling the indices of quantization centroids). This ensures that if a biometric template is compromised, the associated "key" (projection and permutation) can be revoked and replaced, similar to resetting a password.

Stage 2: Fine-Grained FHE Ranking

Following the initial filtering, the system employs Full Homomorphic Encryption (FHE) to perform precise similarity calculations on only the top candidates. This hybrid approach ensures "lossless" accuracy for the final ranking while minimizing the use of computationally expensive HE operations.

Experimental Evaluation

The framework was evaluated on the LFW (Labeled Faces in the Wild) and FaceScrub datasets, alongside scalability tests on dummy databases containing up to 100 million entries.

Key Results

  • Efficiency: The proposed method achieved a 566.30× acceleration compared to standard Full-HE and a 502.28× acceleration compared to HERS (the previous state-of-the-art). On the LFW dataset, retrieval time was reduced to just 3.3 milliseconds per query.
  • Scalability: In tests with 100 million entries, CPQ completed searches in 0.71 seconds, whereas the baseline HERS method would require over 13,000 seconds (nearly 4 hours).
  • Accuracy: Despite the obfuscation layers, the system maintained a Recall@1 of 99.62% on FaceScrub, matching the performance of unencrypted plaintext search.
  • Security and Unlinkability: By utilizing unique encryption keys (permutations/projections), the system ensures that the same face generates uncorrelated templates across different databases, preventing cross-matching and tracking.

Conclusion

CPQ demonstrates that cryptographic-level security for face retrieval does not have to come at the cost of performance. By combining a "secure enough" cancelable index for rapid filtering with "perfectly secure" HE for final ranking, the framework achieves the efficiency required for real-world, large-scale biometric applications. Future work will focus on optimizing key management and exploring hardware acceleration to further enhance the system's throughput.

Summary updated

Abstract

Despite the ubiquity of modern face retrieval systems, their retrieval stage is often outsourced to third-party entities, posing significant risks to user portrait privacy. Although homomorphic encryption (HE) offers strong security guarantees by enabling arithmetic computations in the cipher space, its high computational inefficiency makes it unsuitable for real-time, real-world applications. To address this issue, we propose Cancelable Product Quantization, a highly efficient framework for secure face representation retrieval. Our hierarchical two-stage framework comprises: (i) a high-throughput cancelable PQ indexing module for fast candidate filtering, and (ii) a fine-grained cipher-space retrieval module for final precise face ranking. A tailored protection mechanism is designed to secure the indexing module for cancelable biometric authentication while ensuring efficiency. Experiments on benchmark datasets demonstrate that our method achieves an decent balance between effectiveness, efficiency and security.
BibTeX
@inproceedings{tang2025secure,
  author = {Haomiao Tang and Wenjie Li and Yixiang Qiu and Genping Wang and Shu-Tao Xia},
  title = {{Secure and Scalable Face Retrieval via Cancelable Product Quantization}},
  booktitle = {PRCV},
  year = {2025},
  url = {https://openreview.net/forum?id=DF1JSXaQxA},
}
Figure