💻 computer science

Lightweight, Practical Encrypted Face Recognition with GPU Support

This paper presents a lightweight, GPU-accelerated encrypted face recognition system that combines the BSGS-Diagonal algorithm and fused GPU kernels to achieve significant reductions in memory overhead and substantial speedups over existing FHE-based protocols, enabling practical sub-second similarity search on resource-constrained clients.

Original authors: Gabrielle De Micheli, Syed Mahbub Hafiz, Geovandro Pereira, Eduardo L. Cominetti, Thales B. Paiva, Jina Choi, Marcos A. Simplicio, Bahattin Yildiz

Published 2026-06-02

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Gabrielle De Micheli, Syed Mahbub Hafiz, Geovandro Pereira, Eduardo L. Cominetti, Thales B. Paiva, Jina Choi, Marcos A. Simplicio, Bahattin Yildiz

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you want to unlock a high-security door using your face. Usually, you'd send a photo of your face to a server, which compares it against a giant list of stored faces to see if you match. The problem? Sending your face photo is like handing a stranger a copy of your ID card; they could steal it, study it, or even try to rebuild your face from the data.

To fix this, researchers use a magical "encrypted black box" called Fully Homomorphic Encryption (FHE). This allows the server to compare your face against its list without ever seeing the actual faces. Everything stays scrambled (encrypted) the whole time.

However, there's a catch: doing math on scrambled data is incredibly slow and requires a massive amount of computer memory, like trying to solve a puzzle while wearing oven mitts and in a tiny room.

This paper introduces two major upgrades to make this "scrambled face matching" fast and practical enough for real-world use, even on smaller devices.

1. The "Smart Library" Trick (BSGS-Diagonal)

The Problem:
Imagine the server has a library of 1 million face "books." To find a match, the old method (HyDia) had to pull out a specific "rotation key" for every single book to check if it matched your face. If you had 1 million books, you needed 1 million keys. This required a huge amount of memory (RAM), like needing a warehouse just to store the keys.

The Solution:
The authors invented a new method called BSGS-Diagonal. Think of it like a "Baby-Step/Giant-Step" strategy.

Instead of checking every book one by one with a unique key, they group the books into "Baby Steps" (small groups) and "Giant Steps" (big jumps).
They pre-calculate a few "master keys" that can unlock many groups at once.
The Result: They reduced the number of keys needed by 91%.
- Analogy: Instead of needing a unique key for every single door in a skyscraper, you now only need a master key for every floor and a small set of keys for the rooms on that floor.
- Impact: This shrank the memory needed on the client side (your phone or laptop) by about 14 GB and cut the server's peak memory usage by more than 4 times. This makes it possible to run this on smaller, edge devices that don't have massive hard drives.

2. The "All-in-One" GPU Factory

The Problem:
Even with fewer keys, doing the math is still slow. The old way was like a factory where a worker (the CPU) would take a piece of encrypted data, hand it to a super-fast robot (the GPU) to do one calculation, then take it back, hand it to another robot, and so on. The time spent walking the data back and forth (transferring data between the computer's main brain and the graphics card) wasted a lot of time.

The Solution:
The authors built a new system where the entire process happens inside the GPU (the super-fast robot).

The Analogy: Instead of the worker shuttling parts back and forth, they built a complete assembly line inside the robot's workshop. The data goes in, gets processed, compared, and the final answer comes out, all without ever leaving the robot's hands.
They created special "kernels" (custom instructions) that fuse many steps together, including a complex math trick called a "Chebyshev evaluator" (used to decide if the faces match) directly on the graphics card.
The Result:
- The system became 9 to 21 times faster than the previous best methods.
- It can now check a face against a database of up to 32,000 entries (2^15) in less than one second.
- It also saves memory on the main computer (host) because the heavy lifting is done on the graphics card.

Summary of Achievements

Privacy First: Your face data stays encrypted the entire time. No one sees your actual face, not even the server.
Memory Saver: By using the "Smart Library" trick, they cut the memory needed by over 90%, making it feasible for smaller devices.
Speed Demon: By moving the whole process to the GPU and keeping the data there, they made the system nearly 20 times faster, achieving "sub-second" recognition.
Real-World Ready: They tested this on real face datasets (FRGC 2.0) and proved it works just as accurately as non-encrypted methods, with a precision of over 99.9%.

In short, the authors took a privacy-preserving face recognition system that was too heavy and slow for practical use, lightened its load with a smarter algorithm, and turbocharged it with a new GPU workflow, making it fast and efficient enough for real-life applications.

Technical Summary: Lightweight, Practical Encrypted Face Recognition with GPU Support

Problem Statement

Face recognition systems typically operate in a client-server architecture where a client extracts a face embedding and a server performs similarity search against a database. This model raises significant privacy concerns, as facial data constitutes personally identifiable information (PII) subject to strict regulations. While cryptographic approaches like Fully Homomorphic Encryption (FHE) allow similarity search over encrypted data without revealing the plaintext, existing FHE-based protocols (specifically the state-of-the-art HyDia protocol) face severe practical limitations.

The primary bottlenecks in current FHE-based face recognition are:

High Memory Overhead: Existing methods require large sets of rotation keys (often $O(\ell)$ where $\ell$ is the vector dimension) to perform diagonal matrix-vector multiplications. This results in excessive RAM usage on both client and server sides (e.g., over 33 GB for databases up to 1 million entries), making deployment on resource-constrained edge devices infeasible.
Computational Latency: FHE operations, particularly ciphertext rotations and rescaling, are memory-bandwidth bound on CPUs. Naïve offloading of individual operations to GPUs often degrades performance due to costly host-device data transfers and repeated conversions between CPU (OpenFHE) and GPU (FIDESlib) data structures.

Methodology

The authors propose a dual-layer optimization strategy targeting both algorithmic efficiency and system-level hardware acceleration, building upon the HyDia protocol.

1. Algorithmic Improvement: BSGS-Diagonal

To address the memory and rotation key bottleneck, the authors introduce BSGS-Diagonal, an algorithmic variant of the Baby-Step/Giant-Step (BSGS) strategy tailored for encrypted matrix settings.

Mechanism: Unlike standard BSGS which assumes a plaintext matrix, BSGS-Diagonal operates on encrypted database matrices. It precomputes all necessary rotations of the encrypted query vector once and reuses them across all matrix groups ( $G$ ) in the database.
Key Reduction: By precomputing the query rotations, the method amortizes the cost of rotation keys. It reduces the required rotation key set from $\ell-1$ (in HyDia) to approximately $2\sqrt{\ell}$ (specifically $n_1 + n_2 - 2$ keys).
Memory Efficiency: This reduces the client-side rotation key set by 91%, lowering client memory requirements by approximately 14 GB. It also employs an incremental accumulation strategy with multi-threading to reduce peak server RAM usage.
Performance: The approach improves runtime by up to 1.57× for membership verification and 1.43× for identification scenarios compared to the original HyDia.

2. System-Level Improvement: GPU-Resident Architecture

To address computational latency, the authors design an end-to-end GPU-resident pipeline using FIDESlib (a CUDA-accelerated CKKS library) integrated with OpenFHE.

Design Principle: Minimize host-device transfers by keeping the entire query processing pipeline (similarity computation, threshold comparison, and aggregation) on the GPU. Only the initial query ciphertext is uploaded, and the final result is downloaded.
Custom Kernels: The implementation includes:
- GPU-Native Chebyshev Evaluator: A custom implementation using the Paterson–Stockmeyer method to approximate the sign function for threshold comparison entirely on the GPU, avoiding CPU round-trips.
- BSGS-RTX-TBS Variant: A GPU-specific variant that utilizes pre-rotated diagonals (computed offline) and on-demand giant-step rotations. This reduces the online rotation key set on the GPU from ~516 keys to ~36, significantly lowering VRAM usage.
- Lazy Relinearization: Deferred relinearization in similarity accumulation to optimize memory usage.
Variants: The paper evaluates three GPU configurations:
- HyDia-RTX-DG: Direct GPU port of the original HyDia.
- BSGS-RTX-TBS: GPU port with BSGS and server-side homomorphic pre-rotation.
- BSGS-RTX-TBE: GPU port with BSGS and enroller-side plaintext pre-rotation (eliminating negative rotation keys).

Key Contributions

The paper claims three primary contributions:

Significant Memory Reduction: The BSGS-Diagonal algorithm drastically reduces rotation key requirements (91% reduction), lowering client memory by ~14 GB and peak server RAM by up to 4.5× for databases up to $2^{20}$ entries, enabling edge deployment.
First GPU-Accelerated End-to-End Protocol: The authors present the first GPU-accelerated implementation of an encrypted face recognition protocol supporting both membership and identification. This achieves sub-second execution times for databases up to $2^{15}$ entries (and up to $2^{16}$ with the BSGS variant) while reducing host RAM usage.
Open-Source Implementation: A complete, open-source implementation based on OpenFHE and FIDESlib is provided, tested on databases ranging from $2^{10}$ to $10^6$ entries (CPU) and up to $2^{16}$ entries (GPU).

Experimental Results

Experiments were conducted on an Intel Xeon Platinum 8260 (CPU) and NVIDIA Quadro RTX 8000 / H200 (GPU).

CPU Performance (BSGS-Diagonal vs. HyDia):
- Speedup: Up to 1.57× faster for membership and 1.43× for identification.
- Memory: Peak RAM reduced from >33 GB (HyDia) to <11 GB (BSGS-Diagonal) for 1M entries. Client rotation keys reduced from 511 to 44.
- Disk Usage: Reduced by up to 5×.
GPU Performance:
- Speedup: The GPU implementations achieved up to 9× speedup for HyDia and up to 21× speedup for the BSGS variant compared to CPU baselines.
- Latency: Achieved sub-second encrypted face recognition for databases up to $2^{15}$ entries.
- Memory: The BSGS-RTX-TBS variant reduced peak GPU memory usage from ~27 GB (HyDia-RTX-DG) to ~9 GB for 8,192 vectors, allowing deployment on GPUs with 12 GB VRAM.
- Scalability: The H200 GPU (141 GB VRAM) extended support to databases of size $2^{17}$ .
Accuracy:
- Evaluation on the FRGC 2.0 dataset (44,228 embeddings) confirmed that the encrypted pipeline preserves recognition quality.
- Precision > 99.95%, Recall ≈ 99.40%, and Accuracy > 99.998%.
- Reducing the Chebyshev comparison depth from $\kappa=10$ to $\kappa=8$ yielded speedups without measurable accuracy loss.

Significance and Claims

The paper positions its work as a step toward the practical deployment of privacy-preserving face recognition in real-world, resource-constrained environments.

Feasibility: By reducing the memory footprint and computational latency, the authors argue that FHE-based face recognition is no longer restricted to high-end servers but can be viable for edge clients and standard server GPUs.
Privacy: The system provides cryptographic guarantees (based on the Ring Learning with Errors problem) rather than empirical obfuscation, protecting against reconstruction attacks.
Open Science: The authors emphasize the value of their open-source implementation, which integrates state-of-the-art libraries (OpenFHE, FIDESlib) to provide a reproducible baseline for future research in encrypted search.

The authors remain modest, noting that while their GPU implementation achieves sub-second performance for databases up to $2^{15}$ , larger databases still face memory constraints on current hardware, and the trade-offs between setup time (enrollment) and query latency remain a factor in deployment choices.