Lightweight, Practical Encrypted Face Recognition with GPU Support Journal: Computer and Security Gabrielle De Micheli, Syed Mahbub Hafiz, Geovandro Pereira, Eduardo L. Cominetti, Thales B. Paiva, Jina Choi, Marcos A. Simplicio Jr, Bahattin Yildiz Abstract Face recognition models commonly operate in a client-server setting where a client extracts a compact face embedding, and a server performs similarity search over a template database. This raises privacy concerns, as facial data is highly sensitive. To provide cryptographic privacy guarantees, one can use fully homomorphic encryption (FHE) to perform end-to-end encrypted similarity search. However, existing FHE-based protocols are computationally costly and, especially, impose high memory overhead due to large rotation-key sets and bandwidth-bound homomorphic operations. Building on prior work, HyDia (PoPETS 2025), we introduce algorithmic and system-level improvements targeting real-world deployment with resource-constrained (edge) clients. First, we propose BSGS-Diagonal, an algorithm delivering fast and memory-efficient similarity computation, benefiting from precomputed rotations when applying a Baby-Step/Giant-Step strategy to consecutive matrix-vector product evaluations. BSGS-Diagonal substantially shrinks the rotation-key set, lowering both client and server memory requirements, and also improves practical server runtime through up-front rotation reuse and improved parallelism. This yields a 91 % 91\% reduction in the number of rotation keys, translating to approximately 14 GB less memory used on the client, and reducing overall CPU peak RAM from over 30 GB in the original HyDia to under 10 GB for databases up to size 2 20 2^{20} . In addition, runtime is improved by up to 1.57 × 1.57\times for the membership verification scenario and 1.43 × 1.43\times for the identification scenario. Secondly, we introduce GPU-optimized similarity matrix computation kernels, including an efficient homomorphic Chebyshev evaluator. The implementation is built upon FIDESlib, a CKKS-level GPU library based on OpenFHE. Rather than offloading individual CKKS primitives in isolation, the integrated kernels fuse operations to avoid repeated CPU–GPU ciphertext movement and costly FIDESlib/OpenFHE data-structure conversions, which otherwise become dominant overheads and can make naive GPU execution no faster than a CPU-only implementation. As a result, our GPU implementations of both HyDia and our variant achieve up to 9 × 9\times and 21 × 21\times speedups, respectively, enabling sub-second encrypted face recognition for databases up to 2 15 2^{15} entries while further reducing host memory usage. 1 Introduction Face recognition is the task of automatically verifying or identifying a person from an image (or video) of their face. It is increasingly being used across different domains such as healthcare, law enforcement or banking, in which the goal may be either membership verification (“is this person in the database?”) or identification (“which database entries match?”) [ 28 ] . In a typical client-server architecture, the client extracts a real-valued compact face embedding from facial images using deep neural networks. The server then compares those embeddings against templates stored in a database, using a similarity metric (often, a cosine similarity). Albeit simple, such common setups involving transmitting facial data to a remote server raises privacy concerns. Indeed, facial images are considered personally identifiable information (PII) and are subject to strict regulations on their usage and storage. This motivates the study and adoption of privacy-preserving face recognition approaches that limit identity leakage and protect against attempts to recover the original face from transmitted data or intermediate representations (known as reconstruction attacks [ 39 , 23 , 47 , 52 ] ). One example is the deployment of transform-based techniques, where the client applies an irreversible transformation to the face image before it leaves the trusted device. This includes perturbation methods [ 50 , 38 , 37 ] or frequency-domain techniques [ 34 , 41 ] to remove sensitive information while keeping relevant identity information. However, these transformations provide only empirical guarantees and can still leak identity information under strong recovery or adaptive attacks. In light of these concerns, cryptographic schemes that enable matching directly on encrypted data represent a more robust alternative. Using techniques such as fully homomorphic encryption (FHE), garbled circuits, or multi-party computation (MPC), biometric data remains encrypted throughout the entire face recognition pipeline, as similarity computation is performed directly over ciphertexts. In this case, privacy assurance is derived from cryptographic security rather than obfuscation. Among these techniques, FHE is particularly attractive as it requires only a single round of communication between the client and the server, enabling more scalable and lower-latency architectures. Moreover, recent advances in software and hardware acceleration have significantly improved FHE’s practicality [ 27 , 1 ] , making it increasingly viable for real-time private face recognition. Despite these advances, encrypted similarity search under FHE remains computationally demanding. For example, in CPU-based implementations of state-of-the-art schemes like CKKS [ 14 ] , primary bottlenecks are ciphertext rotations, used in diagonal linear transforms and ciphertext-ciphertext multiplications, as well as rescaling operations required for similarity computation and threshold comparison. Profiling reveals that these CKKS operations are largely memory-bandwidth bound, making them promising candidates for GPU acceleration. However, naïvely offloading individual homomorphic operations to a GPU can degrade performance due to costly CPU–GPU ciphertext transfers, which may dominate overall latency unless the pipeline is carefully redesigned to minimize such communications. In this work, we focus on an FHE-based face recognition protocol that supports both membership testing and identification scenarios, with particular emphasis on edge-device clients. Our design reflects realistic deployments in which the client is constrained in computation, memory, and energy, while the server has comparatively greater resources. The proposal builds upon the HyDia [ 40 ] protocol while addressing its main limitation, which is also found in many FHE-based solutions: high RAM memory usage on both the client and server sides, largely due to the number of rotation keys that must be generated, transmitted, and stored. Our contributions include both algorithmic and system-wide improvements, described in what follows. First, we incorporate a Baby-Step/Giant-Step (BSGS) strategy for the encrypted matrix–vector multiplication underlying the scheme’s similarity computation. Our variant, denoted BSGS-Diagonal, reduces computational overheads by precomputing and caching structured rotations before processing a sequence of similarity matrices, thereby significantly decreasing the rotation-key set. This results in 91\% fewer rotation keys compared to HyDia, lowering client-side memory by approximately 14 GB and reducing overall peak RAM usage by up to \approx 4.5\times for databases ranging from 2^{10} to 2^{20} entries. In addition to memory improvements, our BSGS variant is slightly faster than HyDia, reaching up to 1.57\times speedups. As a second improvement, we design an end-to-end GPU-resident architecture for encrypted similarity search, addressing the computational bottlenecks of CPU-based FHE evaluation. Our approach follows a simple principle: upload the encrypted query once, execute similarity calculation, threshold comparison, and aggregation predominantly on the GPU, and minimize host–device transfers. We empirically validate this technique by integrating FIDESlib [ 1 ] , a CUDA-accelerated CKKS library, with our OpenFHE-based framework. This integration includes a custom GPU-native Chebyshev evaluator, developed from scratch using the Paterson–Stockmeyer method, to avoid CPU round-trips for threshold comparison and ensure the entire pipeline remains GPU-resident. Our GPU implementation also incorporates deferred (lazy) relinearization in similarity accumulation and, for the BSGS path, pre-rotated diagonals with on-demand giant-step rotations. We provide GPU implementations for both the original HyDia and our BSGS variant, achieving up to 9\times and 21\times speedups, respectively. As a result, we reduce end-to-end runtimes to sub-second levels for databases up to 2^{15} entries. In addition to latency gains, GPU acceleration reduces host RAM usage by storing ciphertexts and intermediates on the GPU, further improving practicality for real-world deployments. Our main contributions are summarized as follows: 1. Significant client- and server-side memory reduction for FHE-based face recognition, using an improved BSGS-style variant tailored for multi-similarity matrix computation, which lowers rotation-key requirements while yielding better performance. 2. To the best of our knowledge, the first GPU-accelerated implementation of an end-to-end encrypted face recognition protocol bringing membership and identification scenarios to sub-second execution time for databases of size up to 2^{15} . The acceleration comes from the introduction of new dedicated kernels with a custom comparison approach, in addition to a ciphertext multiplication kernel that avoids fused relinearization. 3. An open-source implementation based on OpenFHE [ 6 ] and FIDESlib [ 1 ] tested with databases of varying sizes up to 1M entries for CPU and 2^{16} entries for GPU. Our implementation code (CPU and GPU) can be found here: to be added later Paper organization Section 2 discusses related works on secure K-NN, private database search, secure facial recognition and GPU-based solutions. Section 3 reviews some important background material for our work, including the CKKS scheme, the diagonal and baby-step-giant-step method, the original HyDia [ 40 ] , and security and privacy assumptions hereby considered. Section 4 presents our optimization proposal using of BSGS-Diagonal to replace HyDia’s diagonal method. Section 5 details our GPU-based implementation. Section 6 describes our experimental results, evaluating all the proposed optimizations. Finally, Section 7 presents our final considerations. 2 Related works Secure K-NN A core building block in similarity search is the K -nearest neighbors ( K -NN) problem, sometimes also called top- K selection. Given a query vector, the K -NN problem identifies the K closest points in the dataset under a chosen metric (e.g., Euclidean distance, cosine similarity, or inner product). Many studies in the literature focus on secure K -NN schemes, using a variety of privacy preserving techniques to provide client’s query and/or database confidentiality. Early solutions [ 51 , 32 , 24 , 36 , 44 ] often combine HE with techniques such as MPC, oblivious RAM or garbled circuits. Most of these proposals suffer from significant practical limitations, such as long execution times, large communication complexity, access pattern leakage or multiple rounds of interaction with the client. Many subsequent works have focused on overcoming these limitations. One example is the HE-based approximate classifier proposed by Shaul et al. [ 48 ] , which provides an efficient solution to the k -ish NN problem. However, their implementation based on BGV [ 10 ] still takes several hours to run for medium-sized datasets. Later on, Chen et al. [ 11 ] introduced SANNS, two secure K -NN classifiers relying on homomorphic encryption, MPC, oblivious RAM and garbled circuits that keep both the client’s query and the search result confidential. As drawbacks, their solutions require asymptotically linear communication and are interactive, making them less suitable for outsourced computations. Non-interactive fully homomorphic K -NN algorithms also exist, such as theschemes by Zuber et al. [ 56 ] and Ameur et al. [ 3 ] , both of which use TFHE [ 15 ] and have a quadratic cost in the size of the database. Without relying on HE, Servan-Schreiber et al. [ 46 ] presented PRECO, a first lightweight protocol for private nearest neighbor search where the server-side computation is efficient and the communication overhead is reduced to sublinear. PRECO relies on two non-colluding MPC servers running private NN searches, and achieves obliviousness by using distributed point functions, partial batch retrieval and oblivious masking. Finally, Cong et al. [ 18 ] focused on oblivious top- K selection, describing a TFHE-based non-interactive and secure K -NN classification with significant speedups compared to [ 56 ] . Private database search While secure K -NN protocols address the problem of privately retrieving nearest neighbors, some works have explored private search in broader contexts. In these private search solutions, the goal is often to protect the client’s query itself, while the database may remain in plaintext in some scenarios. Ahmad et al. [ 2 ] presented Coeus, a private Wikipedia search system that uses BFV scheme [ 26 ] for the underlying homomorphic operations. The protocol relies on secure matrix-vector product using private information retrieval (PIR) and the Term Frequency-Inverse Document Frequency (TF-IDF) method [ 45 ] to protect the privacy of the users’ queries. Henzinger et al. [ 31 ] introduced Tiptoe, a private web search engine where clients can efficiently search over millions of public documents while protecting their queries. Tiptoe relies on semantic embeddings, private NN search with fast linearly homomorphic encryption (using BFV), and clustering to reduce communication. The server-side computational cost remains linear per query. More recently, Asi et al. [ 5 ] introduced Wally, another private search system which is efficient for very large databases and many clients. Wally relies both on Somewhat Homomorphic Encryption (SHE) and differential privacy to guarantee the client’s query privacy. Concurrently to Wally, Zhou et al. [ 54 ] presented Pacmann, where clients run a graph-based approximate NN search combined with recent sublinear PIR schemes [ 53 ] to achieve better performance and accuracy than [ 31 ] . Focusing on a specific application, Wang et al. [ 49 ] presented PATHE, a privacy-preserving pattern search framework that integrates FHE (CKKS and TFHE) with hyperdimensional computing (HDC) to achieve high-performance secure mass spectrometry database search. Graph-based similarity search Other recent contributions have explored fully homomorphic encryption for encrypted search more broadly. Notably, the Graph - based Secure Similarity Search (GraSS) proposal [ 35 ] is a secure and scalable FHE - based framework for graph - structured similarity queries with end - to - end privacy. It defines an FHE - friendly graph representation and index encoding that reduces the complexity of neighborhood retrieval, including novel homomorphic algorithms tailored to graph operations. More recently, Zhu et al. [ 55 ] introduced Compass, a search system over encrypted embedding data. It uses a search index that includes the traversal of a graph-based ANN algorithm on top of Oblivious RAM for improved performance. Privacy-preserving facial recognition Bodetti [ 8 ] is one of the first studies on the practicality of using FHE for 1:1 private face recognition systems. The suggested algorithm relies on BFV and uses batching techniques for the homomorphic computation of inner products between vectors, so multiple elements are encrypted into a single encrypted block. In addition to these standard batching techniques, Bodetti also utilizes dimensionality reduction algorithms (in particular, the classical Principal Component Analysis) to further tackle the high computational cost of face matching over encrypted data. Subsequently, Engelsma et al. [ 25 ] introduced a novel data encoding scheme that is tailored for efficient {1:\texttt{many}} representation matching in the encrypted domain, also using BFV. Compared to [ 8 ] , their proposed HERS algorithm scales to larger databases due to a slower increase in computational complexity (namely, number of homomorphic additions and multiplications) and the absence of required rotations. Later, Ibarrondo et al. [ 33 ] proposed replacing element-wise testing by the notion of group testing to significantly reduce the number of non-linear operations in the encrypted domain. More specifically, rather than evaluating all scores individually, their proposed GROTE algorithm derives representative maxima for each group and performs threshold checks only on these values for better efficiency. Their algorithm relies on the CKKS homomorphic scheme. Aiming to improve the efficiency of FHE-based face recognition, Choi et al. [ 16 ] proposed Blind-Match, a CKKS-based scheme where the feature vector is divided into smaller parts and each part is then processed individually. Their custom cosine similarity computation method allows them to reduce the number of additions and rotations compared to prior work [ 8 ] and outperform GROTE for varying database sizes. More recently, Martin et al. [ 40 ] presented HyDia, another CKKS-based protocol for 1:\texttt{many} face recognition that exploits diagonal packing for efficient matrix multiplication and scalability. The proposed algorithm uses a hybrid approximation method to compute homomorphic thresholding with better accuracy. Their study also provides a comprehensive comparison with the aforementioned works, including detailed plots and tables across multiple metrics such as server overhead, network bandwidth, circuit depth, and ciphertext size. Since HyDia is one of the latest works in private face recognition, and delivers state-of-the-art performance for large-scale 1:\texttt{many} matching, we primarily compare our improvements to it, besides building upon their open-source implementation. Another recent related work is CryptoFace [ 4 ] , which targets an end-to-end setting where feature extraction itself is performed under FHE. The client encrypts the probe face image and the server evaluates an FHE-friendly convolutional neural network (CNN) to produce encrypted features for thresholded matching. Even though CryptoFace offers stronger protection by moving more of the pipeline into the encrypted domain, it is primarily evaluated for 1:1 verification, with identification demonstrated only via a small 1:128 closed-set retrieval experiment. In addition, its online latency is dominated by the homomorphic CNN feature-extraction stage (rather than by database-scale 1:\texttt{many} matching), whereas HyDia and our work target and optimize the large-scale encrypted similarity search stage. GPU-based similarity search To the best of our knowledge, no public research articles report results specifically for GPU-accelerated encrypted face recognition. Nevertheless, public information on the topic can be found for CryptoLab’s Encrypted Facial Recognition (EFR) solution, described primarily through product and press material [ 19 ] . In those documents, the authors claim that GPU acceleration enables matching against tens of millions of encrypted face-template vectors in milliseconds, with horizontal throughput scaling as additional GPUs are provisioned. There are also many studies involving GPU acceleration for the FHE backend, rather than face-recognition applications directly. For example, the FIDESlib [ 1 ] library adopted in this work is an open-source, server-side CKKS-on-GPU library designed to interoperate with client-side OpenFHE workflows, including optimized GPU-oriented primitives and multi-GPU support. More broadly, proprietary and emerging libraries such as HEAAN2 [ 20 ] and Desilo [ 22 ] explicitly emphasize CUDA-based GPU acceleration for standard CKKS operations (e.g., rescaling, rotations/key-switching, and bootstrapping). Finally, the Cheddar GPU library [ 17 ] was very recently open-sourced. However, based on our initial investigation, it does not appear to provide support for encrypted matrix–vector multiplication. Therefore, a thorough analysis of its performance and eventual comparison with our FIDESlib-based implementation is left as a topic for future work. 3 Preliminaries 3.1 Mathematical notations Throughout the paper, we use bold capital letters, say \mathbf{M} , to denote matrices and bold letters, say q , to denote vectors. We use the \cdot notation for a standard matrix-vector multiplication operation and \odot to denote the element-wise multiplication operation. 3.2 CKKS The CKKS scheme [ 14 , 12 ] is a single instruction multiple data (SIMD)-style homomorphic encryption scheme that operates over a vector of complex or real values. The scheme relies on RingLWE ciphertexts in {\mathcal{R}_{Q}^{2}} for a given ring \mathcal{R}=\mathbb{Z}[X]/(X^{N}+1) , where N=2^{k} (for k>0 ) is the ring dimension and \mathcal{R}_{Q}=\mathcal{R}/Q\mathcal{R} describes the ring \mathcal{R} reduced modulo an integer Q=\prod_{i=0}^{L}q_{i} . The integer L is known as the multiplicative depth and represents the maximum number of rescaling levels available before decryption fails. CKKS supports element-wise operations, such as addition and multiplication, as well as cyclic rotation. We now describe some of the core operations supported by CKKS that are most relevant to this work. Encoding. Given a real (or complex) vector \textbf{x}\in\mathbb{C}^{N/2} , it is encoded into elements of \mathcal{R}_{Q} using an approximate inverse of a scaled complex canonical embedding. More precisely, one applies an inverse Fast Fourier Transform on the elements of x and scales each output by a factor \Delta . Each element is then rounded to the nearest integer, since encryption is performed over integers modulo Q . This encoding step outputs a plaintext polynomial \textbf{m}(X) that packs N/2 complex values, referred to as the available slots . Encryption. A plaintext polynomial \textbf{m}(X) is encrypted into a ciphertext (\textbf{a},\textbf{b})\in\mathcal{R}^{2}_{Q} with a given public key and the addition of some random noise. Addition. CKKS supports element-wise plaintext-ciphertext and ciphertext-ciphertext additions. The output ciphertext corresponds to the SIMD addition of the underlying complex vectors. Multiplication. CKKS also supports plaintext-ciphertext and ciphertext-ciphertext multiplication. To avoid an exponential growth in the scaling factor over repeated multiplications, each multiplication is followed by a rescaling step. The output polynomial has coefficients in \mathbb{Z}_{Q_{\ell-1}} instead of \mathbb{Z}_{Q_{\ell}} where Q_{\ell}=\prod_{i=0}^{\ell}q_{i} for 0<\ell\leq L . This corresponds to the consumption of one level from the available depth L . Rotation. Cyclic rotations shift the elements of the input vector x by 0\texttt{numSlots} , more than one \mathbf{M}_{k} matrix is produced (in this example, we have \mathbf{M}_{1} and \mathbf{M}_{2} ) to fit all the diagonal matrices. This results in G\cdot\ell ciphertexts (in this figure, \ell=4 and G=2 ). 3.4 Textbook Baby-step Giant-Step The Baby-Step Giant-Step (BSGS) optimization reduces the number of ciphertext rotations needed in a homomorphic matrix-vector product by grouping the diagonals \text{diag}_{i} of \mathbf{M} into n_{2} groups of size n_{1} , such that \ell=n_{1}\cdot n_{2} . By writing a diagonal index as \ jn_{1}+i , with 0\leq j0 and n_{2}>1 then 19: \mathsf{sum}_{j}\leftarrow\textsf{Rot}_{\text{GPU}}(\mathsf{sum}_{j},\;j\cdot n_{1}) \triangleright on-demand giant-step rotation (BSGS-RTX-TBS only) 20: end if 21: \mathsf{acc}_{m}\leftarrow\mathsf{acc}_{m}+\mathsf{sum}_{j} 22: end for 23: \mathsf{cheb}_{m}\leftarrow\textsf{ChebyshevCompare}_{\text{GPU}}(\mathsf{acc}_{m},\,\delta,\,\kappa) \triangleright Algorithm 2 24: end for 25: SynchronizeStreams (w,\ldots,w{+}S{-}1) 26: end for 27: 28: \triangleright Step 3: Aggregation (on GPU) 29: \mathsf{result}\leftarrow\sum_{m=0}^{G-1}\mathsf{cheb}_{m} \triangleright tree-reduce addition on GPU 30: \mathsf{result}\leftarrow\textsf{RotateAndSum}_{\text{GPU}}(\mathsf{result},\,N) \triangleright slot-wise aggregation 31: 32: \triangleright Step 4: Download 33: Download \mathsf{result} from GPU to CPU 34: 35: return \mathsf{result} \triangleright slot 0 encodes the total match count Algorithm 4 GPU query processing — Identification 1: Same as Algorithm 3 2: Vector of G encrypted comparison ciphertexts 3: 4: \triangleright Steps 1–2: identical to Algorithm 3 , yielding \{\mathsf{cheb}_{m}\}_{m=0}^{G-1} on GPU 5: 6: \triangleright Step 3: Bulk download 7: for m=0 to G-1 do 8: Download \mathsf{cheb}_{m} from GPU to CPU 9: end for 10: return \{\mathsf{cheb}_{0},\,\mathsf{cheb}_{1},\,\ldots,\,\mathsf{cheb}_{G-1}\} \triangleright non-zero slots identify matching indices 5.5 Complexity analysis Table 2 summarizes the per-query costs of both GPU variants alongside the CPU baseline. In this table, the per-query upload count refers to uploading the query ciphertext q . Table 2: Per-query operation and transfer costs. \ell{=}512 , n_{1}{=}23 , n_{2}{=}23 , G{=}\lceil K/\texttt{numSlots}\rceil matrix groups. HyDia-RTX-DG’s 516 keys comprise \ell{-}1=511 diagonal rotation keys plus 5 power-of-two EvalSum keys. Resource BSGS-CPU-DG HyDia-RTX-DG BSGS-RTX-TBS BSGS-RTX-TBE Baby-step rotations \ell{-}1 \ell{-}1 (GPU) n_{1}{-}1 (CPU) n_{1}{-}1 (CPU) Giant-step rotations — — (n_{2}{-}1){\cdot}G (n_{2}{-}1){\cdot}G Total online rotations \ell{-}1 \ell{-}1 (n_{1}{-}1){+}(n_{2}{-}1){\cdot}G (n_{1}{-}1){+}(n_{2}{-}1){\cdot}G Mult. per matrix \ell \ell \ell \ell CPU \to GPU upload — 1 ct n_{1} cts n_{1} cts GPU \to CPU download — 1 / G cts 1 / G cts 1 / G cts Rotation keys (total) 44 516 {\sim}75 {\sim}53 Keys on GPU (online) — 516 36 36 Peak GPU memory ( K{=}8192 ) — {\sim}27 GB {\sim}9 GB {\sim}7 GB Pre-rotated diags No No Server (HE) Enroller (PT) Negative rot. keys No No Yes (freed) No Transfer overhead Per-query host–device transfer is dominated by the baby-step ciphertext uploads: 1 ciphertext ( {\sim}5 MB) for HyDia-RTX-DG versus n_{1} ciphertexts ( {\sim}115 MB) for BSGS-RTX-TBS/BSGS-RTX-TBE—in both cases orders of magnitude less than uploading all \ell rotations ( {\sim}2.5 GB). Detailed transfer cost measurements are reported in Section 6.4 . Rotation key tradeoff BSGS-RTX-TBS requires {\sim}10\times fewer online rotation keys on the GPU than HyDia-RTX-DG, freeing GPU memory for larger databases. The trade-off is that BSGS-RTX-TBS requires n_{2}{-}1 on-demand giant-step rotations per matrix, whereas HyDia-RTX-DG performs no giant-step rotations but pre-computes all \ell{-}1 baby-step rotations. Pre-rotation tradeoff (BSGS-RTX-TBS) BSGS-RTX-TBS trades additional offline computation (pre-rotating all diagonals during GPU caching) for a smaller online rotation count. Quantitatively, pre-rotation reduces the online giant-step work from n_{1}\times(n_{2}{-}1) rotations per matrix to n_{2}{-}1 , which is the key cost reduction for GPU execution. Setup vs. query tradeoff HyDia-RTX-DG incurs a substantially higher one-time setup cost because it uploads and initializes the full diagonal-rotation key set, while BSGS-RTX-TBS initializes only the reduced BSGS key subset plus offline pre-rotation keys. The difference in per-query cost arises because HyDia-RTX-DG must compute 511 baby-step rotations per query and then sequentially accumulate 512 diagonal products per matrix, whereas BSGS-RTX-TBS needs only 22 baby-step rotations and evaluates each matrix via 23 giant-step groups—of which 22 require an on-demand GPU rotation. The BSGS structure maps efficiently to GPU parallelism, replacing 512 sequential products with {\sim}23 coarser iterations of n_{1} products each, keeping BSGS-RTX-TBS’s per-matrix cost well below HyDia-RTX-DG’s independent of G . BSGS-RTX-TBE shares the same online pipeline as BSGS-RTX-TBS and therefore has the same per-query rotation and multiplication costs; its advantage lies in a faster offline setup (no homomorphic pre-rotation) and fewer rotation keys ( {\sim}53 vs. {\sim}75 ), at the cost of a small NTT-conversion overhead during the online phase (see Section 5.3.3 ). Concrete setup and query timing comparisons are given in Section 6.4 . 6 Experimental results We run experiments with both CPU and GPU support. For CPU, all of our experiments are run on the same machine, equipped with an Intel Xeon Platinum 8260 CPU at 2.4 GHz and 250 GB of RAM, running Ubuntu 20.04.6 LTS. We use multi-threading to improve the performance for all variants. Parameters are chosen to satisfy a 128-bit security level. We rely on OpenFHE v1.2.3 [ 6 ] as the FHE library to implement our algorithms (building on the framework already set up by [ 40 ] ). Our GPU experiments are run on two GPUs: an NVIDIA Quadro RTX 8000 with 48 GB VRAM and an NVIDIA H200 with 141 GB HBM3e VRAM. We rely on FIDESLib v1.0.0 [ 1 ] for GPU integration mentioned in the previous section. FIDESLib internally builds a patched fork of OpenFHE v1.2.3, compiled with -O3 -march=native and WITH_NATIVEOPT=ON for optimized GPU performance. 6.1 Parameter selection The vector dimension is chosen to be \ell=512 following standard face feature extractors [ 40 , 21 ] . Parameter selection for HyDia (original) We initially do not modify the parameters that were chosen in the original submission for [ 40 ] . Therefore, the ring dimension is 2^{15} resulting in a batch size of 2^{14} . The multiplicative depth is set to 11 with the comparative depth (for Chebyshev) set to \kappa=10 . The scaling factor is set to 45. Other remaining parameters are automatically selected to satisfy a 128-bit security level. In our GPU experiments, we have also tested lowering the comparative depth to \kappa=8 , resulting in a total multiplicative depth of 9 (see Figure 4 and Tables 7 – 8 ). Parameter selection for BSGS-Diagonal For fair comparison, we run our CPU BSGS-Diagonal with the same CKKS parameters, namely the same ring size (resulting in 2^{14} slots), a scaling factor of 45. For the total multiplicative depth, we run experiments with 11 (as in HyDia), but also lower it to 9 for the CPU code. For our GPU experiments, the total multiplicative depth is 8+2+1=11 . For BSGS, we selected the baby-step parameter as n_{1}=23 (manually optimized for performance), and the giant-step parameter is thus n_{2}=\lceil 512/23\rceil=23 . Datasets Our experiments use synthetic datasets and the FRGC 2.0 RGB dataset [ 43 ] . Each synthetic dataset is generated by a Python script that takes as input the database size K , the number of matching vectors K_{m} , and an optional random seed for reproducibility. Every vector has dimension \ell=512 . A query vector q is drawn uniformly at random with integer components in [-99,99] . The K_{m} matching database vectors are created by adding small per-component noise (uniform in [-2,2] ) to q , ensuring reasonable cosine similarity with the query; their positions in the database are chosen uniformly at random as well. The remaining K-K_{m} non-matching vectors are drawn independently and uniformly in [-99,99]^{\ell} . In our benchmarks, we use varying K_{m} matching vectors, and database sizes range from 2^{10} to 2^{20} . For accuracy evaluation, we use the FRGC 2.0 RGB dataset [ 43 ] , following the same experimental setup as the original HyDia work [ 40 ] . On the server side (enroller), a database of 44{,}228 face embeddings ( \ell=512 -dimensional vectors extracted via ArcFace [ 21 ] ) is enrolled and stored in encrypted form. On the client side , 50 probe images are used as queries; for each query, the client encrypts the corresponding 512 -dimensional embedding and submits it to the server for matching against the entire enrolled database. The server performs the encrypted cosine-similarity computation followed by the Chebyshev comparison and returns the encrypted result to the client for decryption and thresholding. Unlike the original HyDia evaluation, which processes a single query in isolation, our setup issues all 50 queries sequentially within the same session (reusing the same key material and encrypted database), providing a more realistic amortized-cost measurement. This yields 50\times 44{,}228=2{,}211{,}400 individual pairwise comparisons in total. 6.2 Benchmarking methodology Each configuration (approach \times database size \times comparison depth) is executed for t=11 independent trials. All experiments use multi-threaded execution via OpenMP with the thread count fixed at 40 . This value was empirically determined to be optimal on our 24-core / 48-thread Xeon Platinum 8260: using all 48 hardware threads incurs hyperthreading contention on memory-bandwidth-bound HE operations, while 40 threads saturates the memory subsystem without excessive context-switching overhead. Trial design. All trials within a configuration share the same cryptographic key pair and encrypted database, isolating query-time variability from key-generation and enrollment randomness. Concretely, the key pair and all database ciphertexts are generated once during the first trial and serialized to disk; trials 2 through 11 deserialize the existing material and proceed directly to query evaluation. The plaintext dataset—a synthetic collection of \ell=512 -dimensional integer vectors with K_{m} planted matching entries—is likewise generated once per (K,K_{m}) pair and held constant across all 11 trials. Measurements. For each trial, an automated benchmark harness launches the system under test as a subprocess and collects four timing measurements: (i) wall-clock time (measured by the harness around the entire subprocess), (ii) enrollment time (reported by the system at the end of database encryption), (iii) membership query time (server-side computation only, excluding client-side encryption, decryption, and network transmission), and (iv) identification query time (same exclusion). A background monitoring thread samples three resource metrics at 0.5 s intervals: peak resident memory (RSS) of the process, peak disk usage of the serialized key and ciphertext store, and—for GPU approaches—peak GPU VRAM via the NVIDIA Management Library. Correctness validation. Every trial automatically checks two correctness conditions: (i) the membership result must match the ground truth (positive iff K_{m}>0 ), and (ii) the identification result must return exactly the set of planted matching indices. A trial is marked pass only if both conditions hold and the process exits successfully; otherwise, it is marked fail and excluded from timing aggregation. Warm-up and aggregation. The first trial in each configuration includes one-time costs that are not representative of steady-state query latency: key generation and serialization, encrypted-database construction, first-touch memory page faults, and—for GPU approaches—lazy CUDA context and memory pool initialization. To separate these setup costs from the per-query performance, we distinguish trial 1 from trials 2 – 11 . For query-time metrics (membership and identification), we report the mean \pm standard deviation over the last N=t{-}1=10 trials (i.e., trials 2 – 11 ), denoted last- N throughout. We use the population standard deviation, since the N measurements constitute the entire set of observations rather than a sample from a larger population. Enrollment time and peak disk usage are inherently one-time costs and are therefore reported from trial 1 only. Peak RAM is reported as the mean \pm std over the last- N trials to reflect steady-state memory consumption. The wall-clock “overall” time reported in summary tables is computed as \text{enroll}(\text{trial\,1})+\text{mean}(\text{wall time},\;\text{last\,}N) , reflecting a realistic end-to-end cost for a first deployment followed by a representative query. Unless otherwise stated, all timing values in our tables and figures refer to the last- N mean \pm std. Remark 1 Note that membership and server timings are not end-to-end in our benchmarks. The network transmission can be simulated following Table 6 of the original HyDia work [ 40 ] , where for network bandwidths of 1 Gbps and above the impact seems to be minimal during a querying phase. 6.3 Performance and memory tradeoffs with BSGS (CPU) Client-side: rotation keys required for HyDia and BSGS-Diagonal Recall that \ell=512 and \texttt{numSlots}=16384 . For HyDia, the number of required rotation keys is \ell-1=511 . Note that this number is independent from the database size and only depends on the ring dimension and the embedding dimension. For BSGS-Diagonal, the number of rotation keys also depends on the BSGS parameter n_{1} and the key count is also independent from the database size. Again, let \ell=512 , \texttt{numSlots}=16384 , and n_{1}=23 . The rotation indices consist of S_{\mathrm{baby}}=\{1,\ldots,22\} and S_{\mathrm{giant}}=\{23,46,\ldots,506\} which results in a total number of 22+22=44 rotation keys. Hence, for any database size, HyDia requires 511 rotation keys while our BSGS-Diagonal only requires 44 rotation keys, i.e., 91\% fewer rotation keys. As a rotation key occupies about 30 MB in RAM based on our experiments, the memory saving in rotation keys is about 14 GB memory, a significant relief for the client. Overall performance and peak RAM To evaluate our BSGS-Diagonal algorithm against the diagonal method used by HyDia, we run both algorithms for membership and index scenarios and compare the execution time (in seconds), the peak RAM (in GB) and the peak disk usage (in GB) for datasets of size 2^{10} to 2^{20} . Figure 3 illustrates our results. In terms of performance, our new variant slightly improves on HyDia with up to a 1.57 \times and 1.43 \times speed-up for the database of size 2^{19} for the membership scenario and for the database of size 2^{20} for the identification scenario respectively. The biggest advantage of our method is in the reduced memory consumption and we get up to 4.6\times reduction of peak RAM and 5\times reduction in disk usage (for databases of size 2^{10} ) and similar reductions for all our databases up to size 2^{18} . Notably, with our method, the peak RAM never exceeds 8 GB for databases up to 2^{18} (as opposed to the 33 GB for HyDia), making our algorithm much more suited to deployment on constrained edge devices. We report our exact experimental results in Table 6 in C . Figure 3: Comparing the original HyDia and our BSGS-Diagonal optimization on CPU for membership and index scenarios execution time and peak RAM and Disk usage for databases from 2^{10} - 2^{20} . Numbers are reported for total multiplicative depth 11. 6.4 GPU acceleration Rotation keys and GPU memory HyDia-GPU uses 511 rotation keys (same as HyDia on CPU) at {\sim}37 MB each ( {\sim}18.7 GB for keys alone). With cached diagonals and intermediate buffers, HyDia-RTX-DG on GPU requires {\sim}24 GB of GPU memory for a database of 8{,}192 vectors – feasible on high-end GPUs (e.g., NVIDIA RTX 8000 with 48 GB or H200 with 141 GB). Transfer overhead HyDia-RTX-DG uploads a single query ciphertext ( {\sim}5 MB) per query and computes all \ell{-}1 baby-step rotations directly on the GPU. BSGS-RTX-TBS and BSGS-RTX-TBE instead upload n_{1}=23 baby-step ciphertexts ( {\sim}115 MB) per query, pre-computed on the CPU. In both cases, this is far less than the \ell=512 ciphertexts ( {\sim}2.5 GB) that would be required if all query rotations were computed on the CPU and uploaded to the GPU. Setup vs. query cost BSGS-RTX-TBS is faster per query than HyDia-RTX-DG: at K{=}1{,}024 , BSGS-RTX-TBS achieves 0.25 s membership latency versus 0.63 s for HyDia-RTX-DG ( 2.5\times faster); at K{=}65{,}536 , HyDia-RTX-DG exceeds GPU memory entirely, while BSGS-RTX-TBS completes in {\sim}3.0 s. HyDia-RTX-DG also incurs a substantially higher one-time setup cost: approximately 39 s wall time versus {\sim}9.5 s for BSGS-RTX-TBS and {\sim}8.5 s for BSGS-RTX-TBE at K{=}1{,}024 , due to the overhead of uploading and initializing all 516 rotation keys. Performance improvement As explained in Section 5 , both HyDia’s original code and our new algorithm were adapted to GPU and Figure 4 illustrates the improvements we obtain by moving from CPU to GPU. More precisely, we improved HyDia-RTX-DG by up to 6.8\times and 9.7\times for the membership and index scenarios, respectively, and BSGS-RTX-TBS by up to 17\times in both scenarios. Note that the improvement for BSGS-RTX-TBS is more significant than for HyDia-RTX-DG (approximately 2\times greater) because BSGS requires far fewer rotation keys ( 44 vs. 511 ), reducing the key material that must reside in GPU memory and freeing more resources for parallel computation. However, these peak speedups are observed at smaller databases ( K\leq 2^{14} ); at K{=}2^{15} , HyDia-RTX-DG’s membership speedup drops to 3.4\times and BSGS-RTX-TBS’s to 7.7\times , and at K{=}2^{16} BSGS-RTX-TBS’s speedup decreases further to 3.2\times , as larger databases increase GPU memory pressure and reduce the available parallelism. This GPU-based improvement enables sub-second performance for both HyDia-RTX-DG and BSGS-RTX-TBS on databases up to 2^{14} , and sub-second performance for BSGS-RTX-TBS alone up to 2^{15} . In terms of peak RAM usage, BSGS-RTX-TBS reduces memory consumption by up to 8.2\times compared to the HyDia-CPU baseline (BSGS-RTX-TBE further reduces it to 11.0\times ), whereas HyDia-RTX-DG yields a modest 1.17\times reduction. For peak disk usage, BSGS-RTX-TBE achieves up to 5.14\times less disk compared to HyDia-CPU (and BSGS-RTX-TBS up to 4.32\times ), whereas HyDia-RTX-DG actually increases disk usage by {\sim}12\% due to additional serialized key material from the GPU library. Using GPU, we were only able to run HyDia-RTX-DG up to databases of size 2^{15} and BSGS-RTX-TBS up to 2^{16} before running into out-of-GPU-memory errors due to the large number of rotation keys and ciphertext intermediates exceeding the available 48 GB of VRAM on the RTX 8000. Figure 4: Comparing the original HyDia and our BSGS-Diagonal optimization on CPU and GPU for membership and index scenarios execution time and peak RAM and Disk usage for databases from 2^{10} – 2^{16} (means over 11 trials). The comparison depth considered in these experiments is \kappa=8 . GPU experiments use an NVIDIA Quadro RTX 8000. The full benchmark results comparing CPU and GPU performances for the original HyDia and the BSGS variant are presented in C.2 , Tables 7 and 8 . 6.5 Accuracy evaluation on FRGC 2.0 To validate that our algorithmic restructuring and computational depth reduction preserve recognition quality, we evaluate both HyDia-CPU and BSGS-CPU-DG on the FRGC 2.0 dataset described above, using 50 probe queries against the full enrolled database of 44{,}228 embeddings. For each approach we test both comparison depths \kappa=10 and \kappa=8 , and compare the encrypted evaluation against the corresponding plaintext baseline. Table 3 summaries the results. Table 3: Accuracy evaluation on FRGC 2.0 ( 50 queries, 44{,}228 database entries, 2{,}211{,}400 total comparisons). All four approach–depth configurations produce identical classification counts. Time is the amortized wall-clock time per query. Approach Mode \boldsymbol{\kappa} TP FP TN FN Prec. Recall F1 Acc. Time/q HyDia-CPU Encrypted 10 6 921 3 2 204 434 42 0.9996 0.9940 0.9968 0.999980 10.34 s Plaintext 10 6 921 2 2 204 435 42 0.9997 0.9940 0.9968 0.999980 HyDia-CPU Encrypted 8 6 921 3 2 204 434 42 0.9996 0.9940 0.9968 0.999980 9.03 s Plaintext 8 6 921 2 2 204 435 42 0.9997 0.9940 0.9968 0.999980 BSGS-CPU-DG Encrypted 10 6 921 3 2 204 434 42 0.9996 0.9940 0.9968 0.999980 8.39 s Plaintext 10 6 921 2 2 204 435 42 0.9997 0.9940 0.9968 0.999980 BSGS-CPU-DG Encrypted 8 6 921 3 2 204 434 42 0.9996 0.9940 0.9968 0.999980 7.13 s Plaintext 8 6 921 2 2 204 435 42 0.9997 0.9940 0.9968 0.999980 Several observations follow from these results. First , all four approach–depth configurations yield identical classification counts ( \text{TP}=6{,}921 , \text{FN}=42 , \text{TN}=2{,}204{,}434 , \text{FP}=3 for encrypted evaluation), confirming that the BSGS restructuring introduces no accuracy degradation whatsoever compared to the original HyDia diagonal method. Second , reducing the Chebyshev comparison depth from \kappa=10 to \kappa=8 has no measurable effect on classification accuracy, despite reducing the total multiplicative depth from 11 to 9 and yielding a noticeable speedup (e.g., from 10.34 s to 9.03 s per query for HyDia-CPU, and from 8.39 s to 7.13 s for BSGS-CPU-DG). This supports our choice of \kappa=8 in the GPU experiments. Third , the encrypted evaluation closely tracks the plaintext baseline: the only discrepancy is a single additional false positive ( \text{FP}=3 vs. 2 ) and correspondingly one fewer true negative, indicating that the FHE noise introduces a negligible error of at most 1 out of 2{,}211{,}400 comparisons ( <5\times 10^{-7} ). Finally , both methods achieve precision >99.95\% , recall \approx 99.40\% , \text{F1}>99.67\% , and accuracy >99.998\% , demonstrating that the encrypted pipeline preserves the recognition quality of the plaintext system on a standard biometric benchmark. 6.6 H200 Results The NVIDIA H200 (141 GB HBM3e) provides roughly 3\times more GPU memory than the RTX 8000 (48 GB), allowing us to extend GPU experiments to larger databases. Figure 5 compares the RTX 8000 and H200 for HyDia-RTX-DG vs. HyDia-H200-DG and BSGS-RTX-TBS vs. BSGS-H200-TBS. Extended database coverage The additional VRAM on the H200 extends GPU feasibility from K{=}2^{15} to K{=}2^{17} for HyDia and from K{=}2^{16} to K{=}2^{17} for BSGS, before out-of-memory errors are encountered. At K{=}2^{17} , BSGS-H200-TBS achieves 8.93 s membership and 14.66 s index time, while HyDia-H200-DG requires 11.05 s and 22.66 s respectively—representing a 1.24\times and 1.54\times advantage for BSGS over HyDia on the same GPU. RTX vs. H200 speedup For databases up to K{=}2^{14} , the H200 offers a modest 1.25\times speedup over the RTX 8000 for BSGS membership (Figure 5 , left), as the computation at these sizes is not memory-bound. At K{=}2^{16} (the largest overlapping point for BSGS), the H200 reduces membership time from 3.02 s to 2.58 s ( 1.17\times ) and index time from 3.16 s to 2.93 s ( 1.08\times ). The speedup narrows at larger K because the computation becomes increasingly dominated by arithmetic operations rather than memory transfers. TBS vs. TBE on H200 Tables 7 and 8 include both BSGS-H200-TBS (server-side pre-rotation) and BSGS-H200-TBE (enroller-side pre-rotation). For K\leq 2^{16} , TBE offers a lower overall RTT than TBS (e.g., 33.2 s vs. 35.9 s at K{=}2^{16} ) and lower RAM ( 3.5 GB vs. 3.9 GB), because the pre-rotation cost is shifted to enrollment. At K{=}2^{17} , however, TBS achieves faster membership ( 8.93 s vs. 9.73 s for TBE) as the server-side pre-rotation strategy benefits from the H200’s higher memory bandwidth at larger working sets. Both variants maintain the same RAM and disk advantages over HyDia-H200-DG. Figure 5: RTX 8000 vs. H200 comparison for membership time (left) and index time (right), \kappa{=}8 . The H200 extends GPU coverage to K{=}2^{17} and provides modest speedups ( 1.08 – 1.25\times ) over the RTX 8000 at overlapping database sizes. 7 Conclusion In this work, we improve the practicality of FHE for encrypted facial matching search in realistic client-server settings where both database and client queries are encrypted. Building on HyDia, we introduced BSGS-Diagonal, a more memory-efficient similarity computation strategy, that reduces the number of required rotation keys while also improving performance. Experimentally on multi-threaded CPUs, it lowers the rotation-key set by 91%, reduces client memory by approximately 14 GB, decreases peak RAM by up to about 4.5\times , and improves runtime by up to 1.57\times in membership verification and 1.43\times in identification. We also show that significant speed gains can be achieved through a GPU-resident execution pipeline while advancing a fully open-source encrypted database search solution, instantiated here through facial matching. By integrating OpenFHE with FIDESlib and adding GPU-native support for encrypted similarity evaluation, including a Chebyshev evaluator and optimized similarity computation kernels, we minimize host-device transfers and improve parallel execution. Our GPU implementations achieve up to 9\times speedup for HyDia and up to 21\times for BSGS-Diagonal, enabling sub-second encrypted face recognition for databases with up to 2^{15} entries while also reducing host memory usage. In particular, our FIDESlib-based design supports full similarity computation inside a GPU kernel, which, to the best of our knowledge, is not currently available in other open-source implementations. Appendix A Operation count for the diagonal method vs textbook BSGS Dimension Diagonal BSGS Multiplications \ell \ell Additions \ell-1 \ell-1 Rotations \ell-1 (n_{1}-1)+(n_{2}-1) Rotation keys \ell-1 (n_{1}-1)+(n_{2}-1) Relinearization keys \ell \ell Asymptotic rotations \Theta(\ell) \Theta(n_{1}+n_{2})=\Theta(\sqrt{\ell}) Overall asymptotic cost \Theta(\ell) \Theta(\ell) Memory for keys (rot + relin) \Theta(\ell) \Theta(n_{1}+n_{2})=\Theta(\sqrt{\ell}) Table 4: Asymptotic operation count and memory usage for diagonal encoding vs BSGS. We assume n_{2}=\lceil\ell/n_{1}\rceil . DB size G Total # of Rotations Memory (# of Rotated CTs) Textbook BSGS BSGS-Diagonal Textbook BSGS BSGS-Diagonal 2^{14} 1 44 511 23 512 2^{16} 4 110 511 23 512 2^{18} 16 374 511 23 512 2^{19} 32 726 511 23 512 2^{20} 64 1430 511 23 512 Table 5: Comparison of rotations performed and memory usage (number of rotated query ciphertexts simultaneously stored) between single-hoisted textbook BSGS and BSGS-Diagonal for varying database sizes and n_{1}=n_{2}=23 . Appendix B HyDia [ 40 ] pseudo-codes Algorithm 5 Enroller (HyDia original): 1: Database \mathcal{D}=\{x_{i}\in\mathbb{R}^{\ell}\}_{i=1}^{K} , public key pk , crypto context cc 2: 3: Normalize database (plaintext): 4: for i=1 to numVectors do 5: x_{i}\leftarrow\mathrm{Normalize}(x_{i},\ \ell) 6: end for 7: 8: Build \ell\times\ell squares and extract diagonals (plaintext): 9: \{S^{(g)}\}\leftarrow\mathrm{SplitIntoSquareMatrices}(\mathcal{D},\,\ell) \triangleright S^{(g)}\in\mathbb{R}^{\ell\times\ell} 10: for each group g do 11: \mathrm{Diags}^{(g)}\leftarrow\mathrm{Diagonals}(S^{(g)}) \triangleright list of \ell diagonals, each length \ell 12: end for 13: 14: Concatenate diagonals into SIMD-sized rows: 15: \{\text{row}_{i}\}\leftarrow\mathrm{ConcatenateRows}\!\left(\{\mathrm{Diags}^{(g)}\}\right) \triangleright packs diagonals linearly into plaintext rows 16: 17: Parallel encryption and async I/O: 18: for i=0 to |\{\text{row}_{i}\}|-1 do \triangleright loop is parallelized in implementation 19: ct\leftarrow\mathrm{Encrypt}(\texttt{pk},\ \text{row}_{i}) 20: \texttt{path}\leftarrow\text{``serial/db\_diagonal/index''}+i+\text{``.bin''} 21: \mathrm{WriteBinaryAsync}(ct,\ \texttt{path}) 22: end for Algorithm 6 ComputeSimilarity 1: Encrypted query q , vector dimension \ell , number of database vectors K , batch size numSlots , cyclotomic order \Omega . 2: G\leftarrow\left\lceil\dfrac{K}{\texttt{numSlots}}\right\rceil \triangleright number of packed matrices / groups 3: \mathsf{similarityCipher}\leftarrow[\,] 4: Precompute for fast hoisted rotations of the query ciphertext 5: \mathsf{rotatedQueryCipher}\leftarrow[\,] 6: \mathsf{rotatedQueryCipher}[0]\leftarrow\textbf{q}[0] 7: \mathsf{queryPrecomp}\leftarrow\textsc{EvalFastRotationPrecompute}(\textbf{q}[0]) 8: 9: for 1\leq i\leq\ell-1 do \triangleright can be parallelized 10: \mathsf{rotatedQueryCipher}[i]\leftarrow\textsc{EvalFastRotation}(\textbf{q}[0],\,i,\,\Omega,\,\mathsf{queryPrecomp}) \triangleright rotate packed query by i slots 11: end for 12: 13: for 0\leq m\leq G-1 do 14: \mathsf{similarityCipher}[m]\leftarrow\textsc{ComputeSimilarityMatrix}(\mathsf{rotatedQueryCipher},\,m) \triangleright compute similarity scores for DB block m (packed in numSlots slots) 15: end for 16: 17: return \mathsf{similarityCipher} Algorithm 7 Membership Scenario 1: Encrypted query q , threshold \tau , comparator depth \kappa , batch size numSlots . 2: \mathsf{scoreCipher}\leftarrow\textsc{ComputeSimilarity}(\textbf{q}) \triangleright vector of group ciphertexts, each packing scores in numSlots slots 3: for 0\leq g\leq|\mathsf{scoreCipher}|{-}1 do 4: \mathsf{scoreCipher}[g]\leftarrow\textsc{ChebyshevCompare}(\mathsf{scoreCipher}[g],\,\tau,\,\kappa) \triangleright \approx 1 if score \geq\tau , else \approx 0 5: end for 6: \mathsf{membershipCipher}\leftarrow\textsc{EvalAddManyInPlace}(\mathsf{scoreCipher}) \triangleright sum all group ciphertexts into a single ciphertext 7: \mathsf{membershipCipher}\leftarrow\textsc{EvalSum}(\mathsf{membershipCipher},\,\texttt{numSlots}) \triangleright sum all numSlots slots into slot 0 8: return \mathsf{membershipCipher} \triangleright slot 0 encodes the total count of matches across all groups/slots Algorithm 8 Index Scenario 1: Encrypted query q , threshold \tau , comparator depth \kappa . 2: \mathsf{scoreCipher}\leftarrow\textsc{ComputeSimilarity}(\textbf{q}) \triangleright vector of group ciphertexts, each packing scores in numSlots blocks 3: for 0\leq g\leq|\mathsf{scoreCipher}|{-}1\} do 4: \mathsf{scoreCipher}[g]\leftarrow\textsc{ChebyshevCompare}(\mathsf{scoreCipher}[g],\,\tau,\,\kappa) \triangleright \approx 1 if score \geq\tau , else \approx 0 5: end for 6: 7: return \mathsf{scoreCipher} Appendix C Full Benchmark Results We present our detailed performance results for both CPU with BSGS-Diagonal and aggregation techniques and GPU compared with the original HyDia code. Reported metrics. Tables 6 , 7 , and 8 report the following columns for each configuration: • K and K_{m} : the number of vectors in the encrypted database (database size) and the number of uniformly at random planted matching vectors relative to the query, respectively. • Approach : the algorithm variant under test. Names follow the convention Method-Platform-Variant : HyDia-CPU-DG (diagonal method, CPU), BSGS-CPU-DG (BSGS-Diagonal, CPU), HyDia-RTX-DG (diagonal method, RTX 8000 GPU), HyDia-H200-DG (diagonal method, H200 GPU), BSGS-RTX-TBS (BSGS with server-side diagonal pre-rotation, RTX 8000 GPU), BSGS-RTX-TBE (BSGS with enroller-side diagonal pre-rotation, RTX 8000 GPU), BSGS-H200-TBS (BSGS with server-side diagonal pre-rotation, H200 GPU), and BSGS-H200-TBE (BSGS with enroller-side diagonal pre-rotation, H200 GPU). • RTT (s) : overall wall-clock time in seconds, computed as \text{enroll}(\text{trial\,1})+\text{mean}(\text{wall time},\;\text{last-}N) . This combines the one-time enrollment cost (database encryption and serialization, measured in the first trial) with the average end-to-end process time over the N=10 steady-state trials. The per-trial wall-clock time spans the full execution of the system under test: key deserialization, query encryption, server-side membership and identification computation, and result decryption. Network transmission is not included. Reported as a single value (no \pm ). • Membership (s) : server-side membership-query computation time in seconds. This measures only the homomorphic computation on the server: encrypted inner-product evaluation via the diagonal (or BSGS-Diagonal) method, Chebyshev sign approximation, and aggregation across database groups. Client-side operations (query encryption, result decryption) and network transfer are excluded. Reported as mean \pm std over the last- N trials. • Index (s) : server-side identification-query computation time in seconds. This measures the per-vector encrypted similarity evaluation and index extraction on the server. Like the membership metric, client-side operations and network transfer are excluded. Reported as mean \pm std over the last- N trials. • RAM (GB) : peak resident set size (RSS) of the process in gigabytes, reflecting the maximum physical memory footprint during the trial. Reported as mean \pm std over the last- N trials. • Disk (GB) : peak on-disk size (in gigabytes) of the serialized cryptographic material—keys, encrypted database diagonals, and any intermediate ciphertexts—measured by summing all files in the serialization directory. The value is deterministic across trials ( \sigma=0 ), as the serialized material is written once during enrollment and remains unchanged in subsequent trials. C.1 CPU-only benchmarks with BSGS-Diagonal Table 6 reports our CPU-only benchmark results with \kappa=10 , i.e., with total multiplicative depth equal to 11 (as in the original HyDia work). We compare HyDia-CPU-DG against BSGS-CPU-DG, where BSGS-CPU-DG corresponds to BSGS-Diagonal. Table 6: CPU-only benchmark results with \kappa=10 . We compare HyDia-CPU-DG against BSGS-CPU-DG, where BSGS-CPU-DG corresponds to BSGS-CPU-DG. Values are reported as mean \pm std over 11 trials. The parenthetical value in gray is the ratio against HyDia-CPU-DG as the baseline. K K_{m} Approach RTT (s) Membership (s) Index (s) RAM (GB) Disk (GB) 2^{10} 16 HyDia-CPU-DG 30.60 (1.00 \times ) 5.67 \pm 0.08 (1.00 \times ) 5.67 \pm 0.24 (1.00 \times ) 33.3 \pm 0.1 (1.00 \times ) 27.84 \pm 0.00 (1.00 \times ) BSGS-CPU-DG 13.10 (2.34 \times ) 4.92 \pm 0.03 (1.15 \times ) 4.76 \pm 0.09 (1.19 \times ) 7.2 \pm 0.1 (4.62 \times ) 5.52 \pm 0.00 (5.04 \times ) 2^{11} 16 HyDia-CPU-DG 30.60 (1.00 \times ) 5.72 \pm 0.07 (1.00 \times ) 5.49 \pm 0.07 (1.00 \times ) 33.3 \pm 0.1 (1.00 \times ) 27.84 \pm 0.00 (1.00 \times ) BSGS-CPU-DG 13.30 (2.30 \times ) 4.97 \pm 0.07 (1.15 \times ) 4.83 \pm 0.06 (1.14 \times ) 7.2 \pm 0.0 (4.62 \times ) 5.52 \pm 0.00 (5.04 \times ) 2^{12} 32 HyDia-CPU-DG 30.70 (1.00 \times ) 5.74 \pm 0.12 (1.00 \times ) 5.61 \pm 0.21 (1.00 \times ) 33.3 \pm 0.1 (1.00 \times ) 27.84 \pm 0.00 (1.00 \times ) BSGS-CPU-DG 13.30 (2.31 \times ) 4.97 \pm 0.06 (1.15 \times ) 4.91 \pm 0.31 (1.14 \times ) 7.2 \pm 0.1 (4.62 \times ) 5.52 \pm 0.00 (5.04 \times ) 2^{13} 32 HyDia-CPU-DG 30.70 (1.00 \times ) 5.72 \pm 0.09 (1.00 \times ) 5.56 \pm 0.12 (1.00 \times ) 33.3 \pm 0.1 (1.00 \times ) 27.84 \pm 0.00 (1.00 \times ) BSGS-CPU-DG 13.30 (2.31 \times ) 4.98 \pm 0.03 (1.15 \times ) 4.82 \pm 0.06 (1.15 \times ) 7.2 \pm 0.1 (4.62 \times ) 5.52 \pm 0.00 (5.04 \times ) 2^{14} 64 HyDia-CPU-DG 30.90 (1.00 \times ) 5.68 \pm 0.08 (1.00 \times ) 5.52 \pm 0.04 (1.00 \times ) 33.4 \pm 0.1 (1.00 \times ) 27.84 \pm 0.00 (1.00 \times ) BSGS-CPU-DG 13.30 (2.32 \times ) 4.95 \pm 0.03 (1.15 \times ) 4.77 \pm 0.04 (1.16 \times ) 7.2 \pm 0.1 (4.64 \times ) 5.52 \pm 0.00 (5.04 \times ) 2^{15} 64 HyDia-CPU-DG 36.50 (1.00 \times ) 7.87 \pm 0.09 (1.00 \times ) 7.67 \pm 0.24 (1.00 \times ) 33.4 \pm 0.1 (1.00 \times ) 30.84 \pm 0.00 (1.00 \times ) BSGS-CPU-DG 18.70 (1.95 \times ) 6.34 \pm 0.09 (1.24 \times ) 6.73 \pm 0.68 (1.14 \times ) 7.3 \pm 0.0 (4.58 \times ) 8.52 \pm 0.00 (3.62 \times ) 2^{16} 128 HyDia-CPU-DG 48.40 (1.00 \times ) 12.09 \pm 0.29 (1.00 \times ) 12.12 \pm 0.38 (1.00 \times ) 33.6 \pm 0.2 (1.00 \times ) 36.84 \pm 0.00 (1.00 \times ) BSGS-CPU-DG 27.40 (1.77 \times ) 8.94 \pm 0.05 (1.35 \times ) 9.55 \pm 0.69 (1.27 \times ) 7.4 \pm 0.1 (4.54 \times ) 14.52 \pm 0.00 (2.54 \times ) 2^{17} 128 HyDia-CPU-DG 77.90 (1.00 \times ) 21.91 \pm 0.75 (1.00 \times ) 23.54 \pm 0.85 (1.00 \times ) 33.9 \pm 0.3 (1.00 \times ) 48.85 \pm 0.00 (1.00 \times ) BSGS-CPU-DG 45.60 (1.71 \times ) 14.18 \pm 0.12 (1.55 \times ) 16.47 \pm 0.77 (1.43 \times ) 7.6 \pm 0.1 (4.46 \times ) 26.53 \pm 0.00 (1.84 \times ) 2^{18} 256 HyDia-CPU-DG 128.10 (1.00 \times ) 39.42 \pm 1.22 (1.00 \times ) 41.87 \pm 2.37 (1.00 \times ) 34.8 \pm 0.3 (1.00 \times ) 72.86 \pm 0.00 (1.00 \times ) BSGS-CPU-DG 114.10 (1.12 \times ) 26.66 \pm 0.47 (1.48 \times ) 30.13 \pm 0.30 (1.39 \times ) 8.0 \pm 0.1 (4.35 \times ) 50.54 \pm 0.00 (1.44 \times ) 2^{19} 256 HyDia-CPU-DG 242.20 (1.00 \times ) 84.12 \pm 3.38 (1.00 \times ) 79.79 \pm 2.25 (1.00 \times ) 35.4 \pm 0.3 (1.00 \times ) 120.88 \pm 0.00 (1.00 \times ) BSGS-CPU-DG 173.00 (1.40 \times ) 53.64 \pm 0.83 (1.57 \times ) 57.91 \pm 0.73 (1.38 \times ) 9.0 \pm 0.1 (3.93 \times ) 98.57 \pm 0.00 (1.23 \times ) 2^{20} 512 HyDia-CPU-DG 483.50 (1.00 \times ) 163.66 \pm 3.53 (1.00 \times ) 165.61 \pm 3.58 (1.00 \times ) 37.3 \pm 0.5 (1.00 \times ) 216.93 \pm 0.00 (1.00 \times ) BSGS-CPU-DG 356.00 (1.36 \times ) 112.33 \pm 1.46 (1.46 \times ) 115.42 \pm 1.83 (1.43 \times ) 11.3 \pm 0.0 (3.30 \times ) 194.61 \pm 0.00 (1.11 \times ) C.2 Additional CPU/GPU benchmark table Tables 7 and 8 report our CPU and GPU benchmark results with \kappa=8 , i.e., the total multiplicative depth is equal to 9. For K=2^{16} , HyDia-RTX-DG observed an out-of-GPU-memory issue on the RTX 8000 (48 GB); all RTX approaches are OOM at K\geq 2^{17} . The H200 (141 GB) extends GPU coverage up to K=2^{17} . Table 7: CPU/GPU benchmark results with \kappa=8 (Part I: K=2^{10} – 2^{14} ). Values are reported as mean \pm std over 11 trials. The parenthetical value in gray is the ratio against HyDia-CPU-DG as the baseline. RTX rows use an NVIDIA Quadro RTX 8000 (48 GB VRAM); H200 rows use an NVIDIA H200 (141 GB VRAM). K K_{m} Approach RTT (s) Membership (s) Index (s) RAM (GB) Disk (GB) 2^{10} 16 HyDia-CPU-DG 24.90 (1.00 \times ) 4.22 \pm 0.02 (1.00 \times ) 4.04 \pm 0.07 (1.00 \times ) 28.7 \pm 0.0 (1.00 \times ) 24.23 \pm 0.00 (1.00 \times ) HyDia-RTX-DG 39.40 (0.63 \times ) 0.63 \pm 0.01 (6.70 \times ) 0.42 \pm 0.00 (9.62 \times ) 24.6 \pm 0.0 (1.17 \times ) 27.23 \pm 0.00 (0.89 \times ) HyDia-H200-DG 44.10 (0.56 \times ) 0.58 \pm 0.03 (7.28 \times ) 0.39 \pm 0.01 (10.36 \times ) 24.6 \pm 0.0 (1.17 \times ) 27.23 \pm 0.00 (0.89 \times ) BSGS-CPU-DG 10.10 (2.47 \times ) 3.64 \pm 0.04 (1.16 \times ) 3.54 \pm 0.07 (1.14 \times ) 6.1 \pm 0.0 (4.70 \times ) 4.71 \pm 0.00 (5.14 \times ) BSGS-RTX-TBS 9.50 (2.62 \times ) 0.25 \pm 0.00 (16.88 \times ) 0.24 \pm 0.00 (16.83 \times ) 3.5 \pm 0.0 (8.20 \times ) 5.61 \pm 0.00 (4.32 \times ) BSGS-RTX-TBE 8.50 (2.93 \times ) 0.25 \pm 0.00 (16.88 \times ) 0.24 \pm 0.00 (16.83 \times ) 2.6 \pm 0.0 (11.04 \times ) 4.71 \pm 0.00 (5.14 \times ) BSGS-H200-TBS 9.30 (2.68 \times ) 0.20 \pm 0.01 (21.10 \times ) 0.19 \pm 0.01 (21.26 \times ) 3.4 \pm 0.0 (8.44 \times ) 5.61 \pm 0.00 (4.32 \times ) BSGS-H200-TBE 7.90 (3.15 \times ) 0.20 \pm 0.01 (21.10 \times ) 0.19 \pm 0.01 (21.26 \times ) 2.5 \pm 0.0 (11.48 \times ) 4.71 \pm 0.00 (5.14 \times ) 2^{11} 16 HyDia-CPU-DG 25.00 (1.00 \times ) 4.21 \pm 0.04 (1.00 \times ) 4.07 \pm 0.08 (1.00 \times ) 28.7 \pm 0.1 (1.00 \times ) 24.23 \pm 0.00 (1.00 \times ) HyDia-RTX-DG 39.30 (0.64 \times ) 0.63 \pm 0.02 (6.68 \times ) 0.42 \pm 0.00 (9.69 \times ) 24.6 \pm 0.0 (1.17 \times ) 27.23 \pm 0.00 (0.89 \times ) HyDia-H200-DG 46.90 (0.53 \times ) 0.60 \pm 0.03 (7.02 \times ) 0.39 \pm 0.01 (10.44 \times ) 24.6 \pm 0.0 (1.17 \times ) 27.23 \pm 0.00 (0.89 \times ) BSGS-CPU-DG 10.10 (2.48 \times ) 3.64 \pm 0.03 (1.16 \times ) 3.56 \pm 0.07 (1.14 \times ) 6.1 \pm 0.0 (4.70 \times ) 4.71 \pm 0.00 (5.14 \times ) BSGS-RTX-TBS 9.60 (2.60 \times ) 0.25 \pm 0.00 (16.84 \times ) 0.24 \pm 0.00 (16.96 \times ) 3.5 \pm 0.0 (8.20 \times ) 5.61 \pm 0.00 (4.32 \times ) BSGS-RTX-TBE 8.50 (2.94 \times ) 0.26 \pm 0.00 (16.19 \times ) 0.24 \pm 0.00 (16.96 \times ) 2.6 \pm 0.0 (11.04 \times ) 4.71 \pm 0.00 (5.14 \times ) BSGS-H200-TBS 8.90 (2.81 \times ) 0.20 \pm 0.01 (21.05 \times ) 0.19 \pm 0.01 (21.42 \times ) 3.4 \pm 0.0 (8.44 \times ) 5.61 \pm 0.00 (4.32 \times ) BSGS-H200-TBE 8.60 (2.91 \times ) 0.22 \pm 0.02 (19.14 \times ) 0.20 \pm 0.01 (20.35 \times ) 2.5 \pm 0.0 (11.48 \times ) 4.71 \pm 0.00 (5.14 \times ) 2^{12} 32 HyDia-CPU-DG 25.00 (1.00 \times ) 4.26 \pm 0.08 (1.00 \times ) 4.00 \pm 0.11 (1.00 \times ) 28.7 \pm 0.0 (1.00 \times ) 24.23 \pm 0.00 (1.00 \times ) HyDia-RTX-DG 39.40 (0.63 \times ) 0.63 \pm 0.01 (6.76 \times ) 0.43 \pm 0.00 (9.30 \times ) 24.6 \pm 0.0 (1.17 \times ) 27.23 \pm 0.00 (0.89 \times ) HyDia-H200-DG 44.80 (0.56 \times ) 0.59 \pm 0.02 (7.22 \times ) 0.41 \pm 0.01 (9.76 \times ) 24.6 \pm 0.0 (1.17 \times ) 27.23 \pm 0.00 (0.89 \times ) BSGS-CPU-DG 10.50 (2.38 \times ) 3.68 \pm 0.04 (1.16 \times ) 3.60 \pm 0.05 (1.11 \times ) 6.1 \pm 0.0 (4.70 \times ) 4.71 \pm 0.00 (5.14 \times ) BSGS-RTX-TBS 9.60 (2.60 \times ) 0.25 \pm 0.00 (17.04 \times ) 0.24 \pm 0.00 (16.67 \times ) 3.5 \pm 0.0 (8.20 \times ) 5.61 \pm 0.00 (4.32 \times ) BSGS-RTX-TBE 8.80 (2.84 \times ) 0.25 \pm 0.00 (17.04 \times ) 0.24 \pm 0.00 (16.67 \times ) 2.6 \pm 0.0 (11.04 \times ) 4.71 \pm 0.00 (5.14 \times ) BSGS-H200-TBS 9.20 (2.72 \times ) 0.20 \pm 0.01 (21.30 \times ) 0.20 \pm 0.01 (20.00 \times ) 3.4 \pm 0.0 (8.44 \times ) 5.61 \pm 0.00 (4.32 \times ) BSGS-H200-TBE 8.40 (2.98 \times ) 0.21 \pm 0.01 (20.29 \times ) 0.20 \pm 0.01 (20.00 \times ) 2.5 \pm 0.0 (11.48 \times ) 4.71 \pm 0.00 (5.14 \times ) 2^{13} 32 HyDia-CPU-DG 25.10 (1.00 \times ) 4.24 \pm 0.07 (1.00 \times ) 4.04 \pm 0.09 (1.00 \times ) 28.7 \pm 0.0 (1.00 \times ) 24.23 \pm 0.00 (1.00 \times ) HyDia-RTX-DG 39.00 (0.64 \times ) 0.63 \pm 0.01 (6.73 \times ) 0.42 \pm 0.00 (9.62 \times ) 24.6 \pm 0.0 (1.17 \times ) 27.23 \pm 0.00 (0.89 \times ) HyDia-H200-DG 44.80 (0.56 \times ) 0.60 \pm 0.05 (7.07 \times ) 0.40 \pm 0.01 (10.10 \times ) 24.6 \pm 0.0 (1.17 \times ) 27.23 \pm 0.00 (0.89 \times ) BSGS-CPU-DG 10.30 (2.44 \times ) 3.69 \pm 0.07 (1.15 \times ) 3.61 \pm 0.06 (1.12 \times ) 6.1 \pm 0.0 (4.70 \times ) 4.71 \pm 0.00 (5.14 \times ) BSGS-RTX-TBS 9.70 (2.59 \times ) 0.25 \pm 0.00 (16.96 \times ) 0.24 \pm 0.00 (16.83 \times ) 3.5 \pm 0.0 (8.20 \times ) 5.61 \pm 0.00 (4.32 \times ) BSGS-RTX-TBE 8.60 (2.92 \times ) 0.25 \pm 0.00 (16.96 \times ) 0.24 \pm 0.00 (16.83 \times ) 2.6 \pm 0.0 (11.04 \times ) 4.71 \pm 0.00 (5.14 \times ) BSGS-H200-TBS 9.30 (2.70 \times ) 0.20 \pm 0.01 (21.20 \times ) 0.19 \pm 0.01 (21.26 \times ) 3.4 \pm 0.0 (8.44 \times ) 5.61 \pm 0.00 (4.32 \times ) BSGS-H200-TBE 8.30 (3.02 \times ) 0.21 \pm 0.01 (20.19 \times ) 0.20 \pm 0.02 (20.20 \times ) 2.5 \pm 0.0 (11.48 \times ) 4.71 \pm 0.00 (5.14 \times ) 2^{14} 64 HyDia-CPU-DG 25.10 (1.00 \times ) 4.24 \pm 0.06 (1.00 \times ) 4.02 \pm 0.10 (1.00 \times ) 28.7 \pm 0.1 (1.00 \times ) 24.23 \pm 0.00 (1.00 \times ) HyDia-RTX-DG 41.70 (0.60 \times ) 0.63 \pm 0.01 (6.73 \times ) 0.42 \pm 0.00 (9.57 \times ) 24.6 \pm 0.0 (1.17 \times ) 27.23 \pm 0.00 (0.89 \times ) HyDia-H200-DG 45.60 (0.55 \times ) 0.61 \pm 0.05 (6.95 \times ) 0.41 \pm 0.02 (9.80 \times ) 24.6 \pm 0.0 (1.17 \times ) 27.23 \pm 0.00 (0.89 \times ) BSGS-CPU-DG 10.50 (2.39 \times ) 3.68 \pm 0.08 (1.15 \times ) 3.60 \pm 0.06 (1.12 \times ) 6.1 \pm 0.0 (4.70 \times ) 4.71 \pm 0.00 (5.14 \times ) BSGS-RTX-TBS 9.70 (2.59 \times ) 0.25 \pm 0.00 (16.96 \times ) 0.24 \pm 0.00 (16.75 \times ) 3.5 \pm 0.0 (8.20 \times ) 5.61 \pm 0.00 (4.32 \times ) BSGS-RTX-TBE 8.70 (2.89 \times ) 0.26 \pm 0.01 (16.31 \times ) 0.24 \pm 0.00 (16.75 \times ) 2.6 \pm 0.0 (11.04 \times ) 4.71 \pm 0.00 (5.14 \times ) BSGS-H200-TBS 9.80 (2.56 \times ) 0.20 \pm 0.01 (21.20 \times ) 0.20 \pm 0.02 (20.10 \times ) 3.4 \pm 0.0 (8.44 \times ) 5.61 \pm 0.00 (4.32 \times ) BSGS-H200-TBE 8.60 (2.92 \times ) 0.20 \pm 0.01 (21.20 \times ) 0.19 \pm 0.01 (21.16 \times ) 2.5 \pm 0.0 (11.48 \times ) 4.71 \pm 0.00 (5.14 \times ) Table 8: CPU/GPU benchmark results with \kappa=8 (Part II: K=2^{15} – 2^{20} ). For K=2^{16} , HyDia-RTX-DG ran out of GPU memory; for K\geq 2^{17} , all RTX approaches ran out of GPU memory. K K_{m} Approach RTT (s) Membership (s) Index (s) RAM (GB) Disk (GB) 2^{15} 64 HyDia-CPU-DG 29.90 (1.00 \times ) 6.00 \pm 0.12 (1.00 \times ) 5.87 \pm 0.12 (1.00 \times ) 28.7 \pm 0.0 (1.00 \times ) 26.73 \pm 0.00 (1.00 \times ) HyDia-RTX-DG 53.00 (0.56 \times ) 1.75 \pm 0.02 (3.43 \times ) 1.66 \pm 0.02 (3.54 \times ) 24.6 \pm 0.0 (1.17 \times ) 30.23 \pm 0.00 (0.88 \times ) HyDia-H200-DG 64.30 (0.47 \times ) 1.69 \pm 0.06 (3.55 \times ) 1.66 \pm 0.07 (3.54 \times ) 24.6 \pm 0.0 (1.17 \times ) 30.23 \pm 0.00 (0.88 \times ) BSGS-CPU-DG 14.60 (2.05 \times ) 4.85 \pm 0.06 (1.24 \times ) 4.80 \pm 0.14 (1.22 \times ) 6.2 \pm 0.0 (4.63 \times ) 7.21 \pm 0.00 (3.71 \times ) BSGS-RTX-TBS 16.80 (1.78 \times ) 0.78 \pm 0.01 (7.69 \times ) 0.81 \pm 0.01 (7.25 \times ) 3.5 \pm 0.0 (8.20 \times ) 8.11 \pm 0.00 (3.30 \times ) BSGS-RTX-TBE 15.30 (1.95 \times ) 0.81 \pm 0.01 (7.41 \times ) 0.81 \pm 0.01 (7.25 \times ) 2.6 \pm 0.0 (11.04 \times ) 7.21 \pm 0.00 (3.71 \times ) BSGS-H200-TBS 16.70 (1.79 \times ) 0.64 \pm 0.01 (9.38 \times ) 0.69 \pm 0.02 (8.51 \times ) 3.4 \pm 0.0 (8.44 \times ) 8.11 \pm 0.00 (3.30 \times ) BSGS-H200-TBE 15.40 (1.94 \times ) 0.68 \pm 0.02 (8.82 \times ) 0.69 \pm 0.02 (8.51 \times ) 2.5 \pm 0.0 (11.48 \times ) 7.21 \pm 0.00 (3.71 \times ) 2^{16} 128 HyDia-CPU-DG 41.30 (1.00 \times ) 9.71 \pm 0.26 (1.00 \times ) 10.15 \pm 0.61 (1.00 \times ) 28.9 \pm 0.1 (1.00 \times ) 31.74 \pm 0.00 (1.00 \times ) HyDia-H200-DG 98.50 (0.42 \times ) 3.04 \pm 0.05 (3.19 \times ) 4.10 \pm 0.03 (2.48 \times ) 24.6 \pm 0.0 (1.17 \times ) 36.23 \pm 0.00 (0.88 \times ) BSGS-CPU-DG 22.80 (1.81 \times ) 7.07 \pm 0.08 (1.37 \times ) 7.48 \pm 0.18 (1.36 \times ) 6.3 \pm 0.0 (4.59 \times ) 12.21 \pm 0.00 (2.60 \times ) BSGS-RTX-TBS 38.50 (1.07 \times ) 3.02 \pm 0.14 (3.22 \times ) 3.16 \pm 0.05 (3.21 \times ) 4.0 \pm 0.0 (7.22 \times ) 13.11 \pm 0.00 (2.42 \times ) BSGS-RTX-TBE 36.10 (1.14 \times ) 3.03 \pm 0.03 (3.20 \times ) 3.13 \pm 0.04 (3.24 \times ) 3.6 \pm 0.0 (8.03 \times ) 12.21 \pm 0.00 (2.60 \times ) BSGS-H200-TBS 35.90 (1.15 \times ) 2.58 \pm 0.08 (3.76 \times ) 2.93 \pm 0.08 (3.46 \times ) 3.9 \pm 0.0 (7.41 \times ) 13.11 \pm 0.00 (2.42 \times ) BSGS-H200-TBE 33.20 (1.24 \times ) 2.60 \pm 0.05 (3.73 \times ) 2.91 \pm 0.03 (3.49 \times ) 3.5 \pm 0.0 (8.26 \times ) 12.21 \pm 0.00 (2.60 \times ) 2^{17} 128 HyDia-CPU-DG 64.60 (1.00 \times ) 17.95 \pm 0.58 (1.00 \times ) 17.56 \pm 0.71 (1.00 \times ) 29.1 \pm 0.1 (1.00 \times ) 41.74 \pm 0.00 (1.00 \times ) HyDia-H200-DG 245.40 (0.26 \times ) 11.05 \pm 0.18 (1.62 \times ) 22.66 \pm 0.26 (0.77 \times ) 24.6 \pm 0.0 (1.18 \times ) 48.24 \pm 0.00 (0.87 \times ) BSGS-CPU-DG 43.30 (1.49 \times ) 11.67 \pm 0.25 (1.54 \times ) 13.53 \pm 0.66 (1.30 \times ) 6.4 \pm 0.1 (4.55 \times ) 22.21 \pm 0.00 (1.88 \times ) BSGS-H200-TBS 97.70 (0.66 \times ) 8.93 \pm 0.22 (2.01 \times ) 14.66 \pm 0.13 (1.20 \times ) 7.5 \pm 0.0 (3.88 \times ) 23.12 \pm 0.00 (1.81 \times ) BSGS-H200-TBE 93.70 (0.69 \times ) 9.73 \pm 0.28 (1.84 \times ) 15.03 \pm 0.54 (1.17 \times ) 6.5 \pm 0.0 (4.48 \times ) 22.21 \pm 0.00 (1.88 \times ) 2^{18} 256 HyDia-CPU-DG 130.90 (1.00 \times ) 34.91 \pm 1.31 (1.00 \times ) 35.71 \pm 1.34 (1.00 \times ) 29.8 \pm 0.2 (1.00 \times ) 61.75 \pm 0.00 (1.00 \times ) BSGS-CPU-DG 102.50 (1.28 \times ) 22.01 \pm 0.48 (1.59 \times ) 24.64 \pm 0.53 (1.45 \times ) 6.7 \pm 0.1 (4.45 \times ) 42.22 \pm 0.00 (1.46 \times ) 2^{19} 256 HyDia-CPU-DG 200.90 (1.00 \times ) 64.21 \pm 2.92 (1.00 \times ) 63.96 \pm 2.69 (1.00 \times ) 31.3 \pm 0.3 (1.00 \times ) 101.77 \pm 0.00 (1.00 \times ) BSGS-CPU-DG 146.90 (1.37 \times ) 44.49 \pm 0.39 (1.44 \times ) 47.09 \pm 0.24 (1.36 \times ) 7.9 \pm 0.1 (3.96 \times ) 82.24 \pm 0.00 (1.24 \times ) 2^{20} 512 HyDia-CPU-DG 384.60 (1.00 \times ) 126.35 \pm 3.74 (1.00 \times ) 127.81 \pm 3.96 (1.00 \times ) 34.6 \pm 0.5 (1.00 \times ) 181.81 \pm 0.00 (1.00 \times ) BSGS-CPU-DG 306.30 (1.26 \times ) 88.99 \pm 2.70 (1.42 \times ) 95.85 \pm 5.51 (1.33 \times ) 10.1 \pm 0.0 (3.43 \times ) 162.29 \pm 0.00 (1.12 \times )