HERS: Homomorphically Encrypted Representation Search
Joshua J. Engelsma Anil K. Jain Vishnu Naresh Boddeti
cs.CV cs.CR cs.LG







IEEE Transactions on Biometrics, Behavior, and Identity Science
Engelsma et al.: Homomorphically Encrypted Representation Search




We present a method to search for a probe (or query) image representation against a large gallery in the encrypted domain. We require that the probe and gallery images be represented in terms of a fixed-length representation, which is typical for representations obtained from learned networks. Our encryption scheme is agnostic to how the fixed-length representation is obtained and can therefore be applied to any fixed-length representation in any application domain. Our method, dubbed  (Homomorphically Encrypted Representation Search), operates by (i) compressing the representation towards its estimated intrinsic dimensionality with minimal loss of accuracy (ii) encrypting the compressed representation using the proposed fully homomorphic encryption scheme, and (iii) efficiently searching against a gallery of encrypted representations directly in the encrypted domain, without decrypting them. Numerical results on large galleries of face, fingerprint, and object datasets such as ImageNet show that, for the first time, accurate and fast image search within the encrypted domain is feasible at scale (500 seconds; 275× speed up over state-of-the-art for encrypted search against a gallery of 100 million). Code is available at <https://github.com/human-analysis/hers-encrypted-image-search>


Fixed-Length Representation, Dimensionality Reduction, Intrinsic Dimensionality, Homomorphic Encryption, Privacy-Preserving Search



HERS: Homomorphically Encrypted Representation Search
    Joshua J. Engelsma, Student Member, IEEE,
        Anil K. Jain, Life Fellow, IEEE,
        and Vishnu Naresh Boddeti, Member, IEEE
Authors are with the Department of Computer Science and Engineering, Michigan State University, East Lansing, MI, 48824.

E-mail: {engelsm7, jain, vishnu}@msu.edu


    December 30, 2023
===========================================================================================================================================================================================================================================================================================================






§ INTRODUCTION









In 2014, a hack on the US Office of Personnel Management (OPM) left 22 million user records exposed, including millions of fingerprint records. Data breaches, like the OPM hack, could have untold consequences against those whose personal identifiable information (PII [<https://bit.ly/2HD83Pq>]) was compromised, including identity theft, robbery, unauthorized access to secure facilities, and blackmail. Sadly, in today's day and age, data-breaches like these are not isolated incidents [<https://wapo.st/39PQuaT>] [<https://wapo.st/2V3kHPS>] [<https://bit.ly/2OQhlM3>], motivating and necessitating the development of strong encryption techniques which protect the underlying data at all times.



Perhaps the most vulnerable category of stored data still needing adequate protection is that of image representations (e.g. face representations). While many forms of data can be sufficiently secured in a database with a well-known encryption scheme like the Advanced Encryption Standard (AES) <cit.>, image representations present a unique challenge. In particular, query image representations are often searched against other representations already enrolled in the database (e.g. a face search system). Even if the enrolled representations were protected with AES, they would have to be decrypted prior to matching with a query representation, leaving both of them vulnerable at the point of comparison (Fig. <ref>). As such, it is critically important to develop strong encryption techniques to protect image representations in the database and during matching.

While much research continues in the area of improving the discriminative power of image representations (e.g. face recognition <cit.> and image classification <cit.>), relatively little effort has been invested into ensuring the security of the representations after they have been learned. This is alarming considering deep face representations can be (i) reconstructed back into their corresponding face image (Fig. <ref>) <cit.> or (ii) violate user privacy by mining demographic attributes such as age, ethnicity, or gender <cit.>. More generally, it is well known that local features, such as deep CNN representations <cit.>, SIFT <cit.>, HOG <cit.> and Bag-of-Visual-Words <cit.>, can be inverted back into the image space with high fidelity.

A special class of encryption algorithms which enable basic arithmetic operations (multiplications and/or additions) in the encrypted domain are known as homomorphic encryption (HE) systems <cit.>. Since representations extracted by CNNs are typically compared using distance metrics that can be expressed in terms of additions and multiplications, like euclidean distance or cosine similarity, HE systems are a plausible solution to protect the representations within the database, and also during matching. HE systems are an attractive solution for secure feature matching systems. They have many desirable properties <cit.> including  diversity, revocability, security, performance, and privacy. At the same time they do not suffer from any loss in matching performance since the encrypted computations are exact. Figure <ref> shows a comparison of template matching in the unencrypted and the encrypted domain.

The key barrier against using HE schemes “off-the-shelf" <cit.> for protection of image representations is the computational complexity of arithmetic operations directly on the ciphertext (in the encrypted domain). This is especially true of fully-homomorphic encryption schemes (FHE) which enable both additions and multiplications within the encrypted domain <cit.>. For example, the authors in <cit.> showed that a naive implementation of FHE requires 48.7 MB of memory and 12.8 seconds to match a single pair of 512-dimensional encrypted face representations. Such computational requirements restrict the application of FHE schemes in 1:1 matching applications and completely render them impractical in 1:m search applications at scale.

To overcome these limitations, we present a practical solution, dubbed , for 1:m encrypted feature matching at scale. This is achieved through a synergistic combination of dimensionality reduction of features and development of a more efficient FHE scheme. The specific contributions of this paper are as follows,

  
  * A data encoding scheme that is tailored for efficient 1:m representation matching in the encrypted domain by leveraging SIMD[Single Instruction Multiple Data] capabilities of existing FHE schemes. Over a gallery of 1 Million 512-dim templates, this provides an 11× speed-up.
  
  * A dimensionality reduction scheme, dubbed DeepMDS++, based on DeepMDS <cit.>, a state-of-the-art dimensionality reduction technique. For a 192-dim fingerprint representation from DeepPrint <cit.>, this provides a 6× speed-up at an only 0.1% loss in rank-1 search accuracy against a gallery of 100 million.
  
  * Extensive experimental analysis (face, fingerprint, and ImageNet datasets) in terms of accuracy, latency and memory requirements when performing image search in the encrypted domain. Our results indicate that  is the first scheme capable of delivering accurate (within ≈ 2% of unencrypted accuracy) and timely (within 10 minutes) image search in the encrypted domain at scale (100 million gallery). The overall scheme provides a 186× speed-up over a state-of-the-art 1:1 matching of 32-dim encrypted feature vectors.







§ RELATED WORK


Privacy-Preserving Biometric Representations: Methods to secure representations of personally identifying information have been developed over the past decade <cit.>. These are summarized in <cit.> into two categories: (i) cryptographic protection, and (ii) pattern recognition based protection. Visual cryptography <cit.> is a common cryptographic approach for securing biometric data such as fingerprint <cit.> and face <cit.> images. Under some schemes, the visual perturbations need to be removed prior to performing a match, exposing the biometric data during authentication or search. Fuzzy-vaults <cit.> are another cryptosystem which have been utilized for fingerprint <cit.> and iris <cit.> recognition. Pattern recognition based protection schemes have been proposed as an alternative to cryptosystems. Examples include non-invertible transformation functions <cit.> and cancelable biometrics <cit.>. Additionally, key-binding systems have been proposed to merge a biometric template with a secret key <cit.>. More recently, template security approaches based on neural networks <cit.> and representation geometry <cit.> have been designed for face representations. All of these approaches trade-off matching performance for security of the template. In contrast,  does not suffer from this trade-off i.e., it provides very high levels of representation security with minimal loss in matching accuracy.



Privacy-Preserving Visual Recognition: Within the broader context of computer vision there is growing interest in privacy-preserving techniques. These approaches are based on cryptographic methods or computer vision techniques. Cryptographic methods include face detection <cit.> using secure multi-party computation, image retrieval <cit.> by oblivious transfer (a building block of secure multi-party computation), face verification <cit.> using the Paillier Cryptosystem, video surveillance <cit.> using Secret Sharing, learning or inference over private data via differential privacy <cit.> and homomorphic encryption <cit.>. Computer vision techniques include camera localization <cit.> by lifting 2D and 3D points to 2D and 3D lines, embedding features into an adversarially designed subspace <cit.>, detecting private computer screens <cit.> using CNNs, and activity recognition <cit.> through image manipulation. In contrast to the foregoing,  adopts a synergistic combination of computer vision techniques in the form of dimensionality reduction and cryptographic methods (FHE scheme), resulting in both efficient and accurate representation matching in the encrypted domain at scale.



Encrypted Distance Computation: Homomorphic encryption (HE) cryptosystems enable arithmetic directly on ciphertext, and as such can be leveraged to compute distances between feature vectors entirely in the encrypted domain. However, given the extreme computational complexity of HE <cit.> most existing works utilizing HE are limited to binary templates and partial homomorphic encryption (PHE) (supports either encrypted additions or encrypted multiplications), or are computationally impractical <cit.>. From Table <ref> it can be seen that existing methods are orders of magnitude slower than even the best existing baseline <cit.>. The only exception to this is the work described in <cit.>, which uses Paillier Homomorphic encryption (requiring that the client template remain decrypted). Admittedly, many of the benchmarks reported in Table <ref> are benchmarked on slower running CPUs than . However, given the order of magnitude in time difference between  and the benchmarks, it is not plausible that a minor CPU upgrade will come close to bridging the gap in search speed. A few works <cit.> have demonstrated the effective use of Fully Homomorphic Encryption (FHE) schemes <cit.> (supports encrypted multiplications and additions). Cheon  <cit.> and Boddeti <cit.> proposed FHE based schemes which leverage a batching technique to reduce the memory and computational requirements for 1:1 matching of binary iris (Hamming distance) and quantized face representations (cosine distance), respectively, in the encrypted domain. Boddeti showed that two 512-dimensional face representations could be compared with 16 KB of memory and in 2.5 milliseconds. Engelsma  <cit.> adopted the same scheme for 1:1 matching of 192-dimensional encrypted fingerprint representations in 1.25 milliseconds. In contrast, early FHE schemes for the same took 100 seconds per match <cit.>.

Although these algorithmic savings enable using FHE for 1:1 matching applications, the time and space complexity remains intractable for most 1:m matching applications (image search). For example, encrypted search against a m=100,000,000 gallery with representations that are of dimensionality 512 would still take over 38 hours and 9 TB memory with the improved FHE scheme proposed in <cit.>. As such, in this work we develop a FHE based solution that is explicitly designed for efficient 1:m encrypted matching and can be applied to any image search application.



Compressing Representations: A plethora of work has been done to estimate a low dimensional approximation of a data manifold which resides in a high dimensional space. In addition to the time tested classical methods for this task (e.g., PCA, MDS, or Isomap), methods utilizing deep networks to learn more complex non-linear mappings have also been proposed. Some of these approaches combine representation learning together with dimensionality reduction via a primary learning objective (e.g. a classification loss) paired with a regularization loss term <cit.>. In contrast, other approaches <cit.> train a completely separate dimensionality reduction algorithm on top of existing representations, such that access to the representation extraction network is not required. Since we want  to be extendable as a wrapper on top of any existing image search system, we pattern the dimensionality reduction component of  after DeepMDS <cit.>, and significantly improve its performance.




§ APPROACH


We posit that there are two avenues for improving search efficiency in the encrypted domain: (i) the encryption scheme itself can be optimized for faster search, and (ii) the dimensionality of the representation can be compressed as far as possible, such that no accuracy is lost. We achieve fast and accurate search at scale in the encrypted domain by coupling both of these solutions in  (Fig. <ref>). In the following sections, we elaborate on each of these steps individually.



 §.§ Problem Setup

A typical representation matching task involves a database of m template feature vectors P=[p_1,…,p_m]∈ℝ^d× m against which a query representation q∈ℝ^d is matched. The result of the matching process is a score that determines the degree of similarity between q and each template in P. A common metric that is adopted for template matching is the Euclidean distance or the cosine similarity. At the core, both of these metrics involve matrix-vector products of the form: r(P,q) = P^Tq. Hence, the representation matching process is comprised of md scalar multiplications and md scalar additions.

We devise a solution to cryptographically guarantee the security of the database P as well as the query q to prevent leakage of any private information. This can be achieved through a parameterized function that transforms a representation z from the original space into an alternate space, i.e., ℰ(z) = f(z;θ_pk), where f(·;θ_pk) is the encryption function with public-key θ_pk and z = g(ℰ(z);θ_sk), where g(·;θ_sk) is the decryption function with private-key θ_sk. The key idea of our paper is to adopt an encryption function to secure the database and the query while retaining our ability to compute their matching score efficiently at scale and without any loss of accuracy i.e.,

    r(P,q) ≈ g(r(f(P,θ_pk),f(q,θ_pk));θ_sk)


FHE satisfies this property and enables us to preserve user privacy. Even if a malicious attacker can gain access to the database of feature representations or the query, without access to the private-key θ_sk the attacker cannot reconstruct the underlying image or extract any other information inherent to the representation.



 §.§ Fast and Secure Similarity Computation

We use the Fan-Vercauteren (FV) scheme <cit.> as our base FHE scheme[A potentially more efficient but approximate alternative is CKKS <cit.>, which can directly be applied to real-valued arithmetic.]. The mathematical basis of this scheme lies in modular arithmetic. Building upon this scheme, we propose a data encoding technique that is tailored for efficient 1:m representation matching. We now briefly describe the different components of our approach.



Fan-Vercauteren Scheme: Plaintext space of the FV scheme is represented as a polynomial ring over a finite field R_t=ℤ_t[x]/Φ_n(x), where t∈ℤ is an integer and Φ_n(x) is an irreducible polynomial of degree at most n-1. Upon encrypting the plaintext polynomial, the encrypted numbers (ciphertext) are encoded as polynomials in the ring R_q. The FV scheme utilizes three keys, (1) a private decryption key θ_sk, (2) a public encryption key θ_pk, and (3) evaluation keys θ_ev which are necessary for multiplication over encrypted data. Addition and multiplication of two ciphertexts translates to polynomial addition and dyadic multiplication in R_q. As long as the coefficients of the resulting polynomials do not exceed q, correctness is ensured. The exact description of the entire scheme, including encryption, decryption, ciphertext addition and ciphertext multiplication, is deferred to Appendix <ref>.



Encoding Scheme: The FV scheme is designed to act on integers only. As such, we need to encode our real valued representation q∈ℝ^d into an integer valued representation q∈ℤ^d. We quantize a given representation's real-valued features into integers with a precision of 0.004 and represent these integers in base w. The utility of the FV scheme is critically dependent on the encoding scheme chosen to represent the quantized features in the ring R_t. Therefore, to maintain the integrity of ciphertext computations, the choice of the ring R_t needs to ensure that the range of values after the desired ciphertext operations remain within the same ring.



Our key contribution in this paper is a custom encoding scheme for efficient 1:m matching by utilizing the SIMD primitives <cit.> of the FV scheme. The primitives operate over an array of numbers instead of a single number, encoding multiple numbers within the same polynomial using the Chinese Remainder Theorem. The encoding scheme in Boddeti <cit.> is also based on the same principles but is specifically suitable for 1:1 matching.

Given a query q∈ℤ^d and a database of feature vectors P∈ℤ^d× m, the encoding scheme in <cit.> encodes the feature vector of each sample (column) into a single polynomial. In contrast, in , the client node encodes each dimension (row) of the representation into a separate polynomial. A query q is therefore encoded into d plaintexts as,

    g_i = ∑_j=1^mq[i]x^j-1∀ i∈{1,…,d}

Similarly, for the database, each dimension of all the templates P_i·∈ℤ^m are encoded into polynomial, resulting in d plaintexts,

    h_i=∑_j=1^mp_j[i]x^j-1∀ i∈{1,…,d}

In this case, the polynomial which encodes the inner products of the query q and the templates P can be obtained as,

    s = ∑_i=1^d g_i * h_i = ∑_j=1^n<q,p_j>x^j-1

where the product g * h is standard polynomial multiplication. As a consequence, the m < n inner products can be computed through d polynomial multiplications[When m > n we can chunk the m samples into m/n databases of n samples each.]. The FV encryption scheme, the corresponding cryptographic primitives, and ciphertext addition and multiplication, operate on this plaintext representation.



Enrollment Protocol: The client generates a public-private key pair. Given a template p, the client (i) quantizes the features, (ii) encodes the quantized template into a plaintext polynomial, (iii) encrypts the plaintext into a ciphertext using the public key, and (iv) transmits the ciphertext along with metadata of the template to the server. The server then adds the encrypted query to the database. Therefore, the server does not have access to the raw representation of the database at any point. The complete enrollment protocol is described in Algorithm <ref> of the Appendix.



Search Protocol: Given a query q, the client (i) quantizes the features, (ii) encodes the quantized query into a plaintext polynomial, (iii) encrypts the plaintext into a ciphertext using the private key, and (iv) transmits the ciphertext to the server. The server computes the encrypted scores as described above and sends them back to the client. The client now decrypts the encrypted scores using the private-key and obtains the index of the nearest match. This index can then be transmitted back to the server depending on the downstream tasks. Therefore, the server does not have access to the raw representation of the query or the matching scores at any point. The complete search protocol is described in Algorithm <ref> of the Appendix.



Computational Complexity The key technical barrier to realizing homomorphic encryption based representation matching is the computational complexity of the FV scheme, especially ciphertext multiplication. Fundamentally, the addition/multiplication of two integers in the plaintext transforms to addition/multiplication of two polynomials of degree n, leading to a n-fold and 𝒪(n^2)-fold increase[In practice, can be reduced to 𝒪(nlog n) through number theoretic transforms.] in computational complexity for addition and multiplication, respectively. Therefore, mitigating the number of ciphertext multiplications can lead to large gains in practical utility.

Table <ref> compares the computational complexity of different encoding schemes for secure distance computation. A naïve implementation of the FV scheme, i.e., no SIMD, encrypts each element of the representation and performs score matching. Such a scheme has a large computational burden bordering on being impractical for real-world applications. The 1:1 matching scheme in <cit.> is specifically designed for vector-vector inner products by encoding an entire d-dimensional feature vector into a polynomial. A major computational bottleneck in their scheme is the need for expensive ciphertext rotations in order to compute the inner product without access to the individual dimensions of the ciphertext vector. Therefore, this approach scales linearly with the size of the database m. In contrast, we observe that our proposed encoding scheme enables  to scale to larger databases due to slower rate of increase in computational complexity by a factor of ∼𝒪(d/n).



 §.§ Dimensionality Reduction for Faster FHE Matching

From the previous subsection we observe that a smaller feature dimension d provides a greater computational savings for 1:m matching in comparison to existing approaches. Therefore, to further ease the computational burden of , we reduce the dimensionality of a given representation as much as possible, while still retaining accuracy (i.e. we attempt to map a representation from the ambient space to its intrinsic dimensionality[Intrinsic dimensionality <cit.> is the minimum number of dimensions needed to maintain the information present in the ambient representation.]). For example, we show a reduction of a DeepPrint <cit.> fingerprint representation from its 192-dim ambient space to a 32-dim space while losing only 0.1% rank-1 search accuracy, but getting a 6× search speed up within the encrypted domain.

There is growing evidence <cit.> that representations learned by deep convolutional neural networks are highly redundant, i.e., they lie on a low-dimensional manifold whose intrinsic dimensionality is 20× to 30× smaller than the ambient space that the representation is embedded in. Gong <cit.> further learned a non-liner mapping, dubbed DeepMDS, to compress the representation from the ambient space to its intrinsic space.

Although DeepMDS <cit.> is able to learn demonstrably better mappings from the ambient to intrinsic space than existing dimensionality reduction schemes, it suffers from two major limitations which limits its direct utility in . First, DeepMDS is limited in its generalization capability since it needs to be trained separately for each dataset. Furthermore, it was trained and evaluated on the same dataset. However, real-world application of  would necessitate a representation compression approach that generalizes across different datasets. Second, DeepMDS optimizes the average pair-wise loss of the samples in a mini-batch without explicitly accounting for the gross imbalance between the number of impostor and genuine pairs. Consequently, the mappings learned by DeepMDS do not focus sufficiently on preserving the local structure of the representation. Both of these drawbacks manifest themselves downstream in the form of loss in feature matching accuracy in the learned intrinsic space, especially when generalizing across different datasets. Therefore, DeepMDS does not serve our goal of compressing the representation while maintaining feature matching performance.

To mitigate the aforementioned limitations we propose DeepMDS++, a deep neural network based approach for compressing the representation. It is comprised of multiple non-linear layers, and is trained to map an embedding from its ambient space to the intrinsic space, such that pairwise distances are preserved. More formally, let 𝐪∈ℝ^d be a high-dimensional representation in the ambient space and f(·;w) be the DeepMDS non-linear mapping function with parameters w. Then, a representation 𝐲 in the estimated intrinsic space is computed in accordance with 𝐲 = f(𝐱;w)

Let G∈ℝ^b_1 × d and I∈ℝ^b_2 × d be a set of genuine and imposter pair of templates in the ambient space for a mini-batch of size b=b_1 + b_2. Similarly, let Ĝ∈ℝ^b_1 × s and Î∈ℝ^b_2 × s be the corresponding features in the intrinsic space. Given the pairwise similarities between genuine pairs D_G and imposter pairs D_I in the ambient space and in the intrinsic space (D̂_G, D̂_I), respectively, we optimize the distance between the similarities as follows,

    ℒ_D = 1/b_1D_G - D̂_G_F^2 + 1/b_2D_I - D̂_I_F^2




Covariance Penalty: To encourage generalization across datasets, and to explicitly discourage redundancy in DeepMDS++, we adopt a penalty on the covariance of the features. Our loss seeks to minimize the off-diagonal elements of the feature covariance matrix.

    ℒ_c = C - diag(C)_F^2
 where C is the covariance matrix computed across our mini-batch of features [Ĝ; Î] and diag(·) returns a diagonal matrix, with diagonal values of the input matrix.



Hard Pair Mining: To allow DeepMDS++ to focus on preserving the local structure of the features in the low-dimensional space, we introduce a hard-mining strategy <cit.>. This strategy first identifies “hard pairs" and include them in our mini-batch for training. In particular, we select those pairs for which the pairwise distance is not well preserved after their mapping into the intrinsic space. More formally, the mini-batch indices of the hard genuine pairs P_G and the hard imposter pairs P_I can be computed as:

    P_G = argsort(D_G - D̂_G)
          
        P_I = argsort(D_I - D̂_I)
 where argsort(·) will return the indices of the rows in the features of genuine pairs 𝐆 and the impostor pairs 𝐈, with the highest error in pairwise distances following their mapping into the intrinsic space (i.e. the hardest pairs).

As we discuss next, experimental results demonstrate that incorporating these solutions aids DeepMDS++ in minimizing the loss of feature matching accuracy when  compressing representations towards their intrinsic dimensionality, ultimately enabling us to perform matching in the encrypted domain more efficiently.





§ EXPERIMENTS

We conduct numerical experiments to evaluate the different components of , (i) the proposed encoding scheme that is tailored to 1:m matching of features, (ii) DeepMDS++, and (iii) finally the combination the encoding scheme and DeepMDS++.



 §.§ Implementation Details

DeepMDS++ is implemented in Tensorflow. Details of the network architecture are provided in Appendix <ref>. The network is optimized with Adam <cit.> with an initial learning rate of 3×10^-4 and with a weight decay of 4×10^-5. It is trained for 250 epochs using a NVIDIA GeForce RTX 2080 Ti GPU. For hard-pair mining, we used a mini-batch size of N=4,000. At the start of training, we mine 50 hard genuine pairs and 50 hard imposter pairs which are augmented with 200 random genuine pairs and 200 random imposter pairs, respectively. Then, we linearly increase the number of hard genuine and hard imposter pairs from 50 to 250 over the 250 training epochs.

The encrypted search in  is implemented using the SEAL library <cit.>. For all experiments, we used a 10-core Intel i9-7900X processor running at 3.30 GHz. All evaluations of the search were performed in a single-threaded environment. The three main parameters of the encryption scheme (n,t,q) are set to n=4,096, t=1,032,193 and q is the default value[In practice, much smaller values of q are sufficient for our purpose.] in SEAL i.e., a product of 3 very large primes, each 36 bits long.





 §.§ Evaluation Datasets



  
  * FaceScrub + MegaFace <cit.>: MegaFace: 1 million distractor faces; FaceScrub: ≈ 3.5K celebrity faces. These are commonly coupled datasets for evaluating face search performance at scale.
  
  * CASIA <cit.>: 450K face images from 10K subjects. 100K subset used to train DeepMDS++ prior to its application on MegaFace and FaceScrub, ensuring that our evaluation of DeepMDS++ is cross dataset.
  
  * NIST SD4 <cit.> + 100 Million Synthetic Background <cit.>: NIST SD4: Contains 2,000 probe/mate inked-rolled fingerprint pairs. 100 Million Synthetic Fingerprints: 100 million synthetic fingerprint database used to evaluate scalability of ; a separate 100K fingerprints from <cit.> were used to train DeepMDS++.
  
  * ImageNet ILSVRC 2012: 1000 classes with 1.28 million training images and 50K validation images. We randomly select 100 classes from the training and validation set for training/testing classification accuracy and precision/recall, and we use the entire validation set for testing precision @ 10.




 §.§ Representation Models



  
  * ArcFace <cit.>: This model obtained state-of-the-art results on the MegaFace Challenge via (i) architectural refinements, (ii) a well curated training dataset, and (iii) an additive arc margin loss. We extracted 512-dim embeddings using a publicly available [<https://github.com/deepinsight/insightface#pretrained-models>], pre-trained ArcFace model.
  
  * DeepPrint <cit.>: This model is one of only several DCNNs for extracting deep representations from fingerprints (192-dim features for DeepPrint). DeepPrint matches the accuracy of state-of-the-art commercial matchers by incorporating fingerprint domain knowledge into the training process.
  
  * Inception ResNet v2 <cit.>: This model which combines inception modules with residual connections is one of the best models on ImageNet 2012 (Top-1 accuracy 80.3%). We use a pre-trained model[<https://keras.io/applications/#inceptionresnetv2>] to extract ImageNet training and validation features (1,536-dim representations).






 §.§ Evaluation Protocol and Experimental Results


To evaluate the efficacy of , (i) we benchmark its efficiency at different gallery sizes and with different representation dimensions against Boddeti <cit.> , and (ii) we benchmark the matching and search accuracy at different representation dimensions against DeepMDS <cit.>. Finally, we (iiii) introduce a two stage encrypted search algorithm which combines  together with <cit.> to further improve the encrypted search speed at a scale of 100 million.





Efficiency: Figure <ref>, shows the computational complexity of the encryption component of  with <cit.>. Specifically, we consider representations at different dimensions (32-dim, 64-dim, 128-dim, and 512-dim) as we compress them towards their intrinsic dimensionality. This experiment highlights the synergistic benefit of coupling together encryption techniques with dimensionality reduction in order to perform encrypted search at scale. The results indicate that at small gallery sizes 1:1 matching from Boddeti <cit.> is, unsurprisingly more efficient, since it was explicitly designed for 1:1 matching. However, as the gallery increases,  is more efficient. Admittedly these methods are orders of magnitude slower than matching in the unencrypted domain, but  is the first practically scalable search over an encrypted database. In terms of memory, for a 64-dim representation,  requires 5.9 MB for the probe template and 280 GB for a gallery of size 100 million. In comparison <cit.> requires less memory for the probe at 19K, but exhausts 9 TB for the same gallery size. Table <ref> reports the computational complexity of encrypted search, in terms of time and memory, against a gallery of 100 Million for different representation dimensionality. Since HERS is very amenable to parallel processing, we are able to search against 100 million 32-dim representations in 740 seconds (186× faster than <cit.>), with 64× less memory when using 10 processes (cores) running in parallel. Finally, we note that returning the encrypted scores to the client requires transmitting m integers over the network. Even for a gallery size of 100 million, this only amounts to 100 MB of data. Decrypting the 100 million scores on the client device takes less than 1 second. The inference time for dimensionality reduction is 30 milliseconds. We obtained this inference time on an Intel Core i9-7900X CPU @ 3.30 GHz and 32 GB of RAM.



Accuracy: We evaluate the accuracy of DeepMDS++, the dimensionality reduction component of  in terms of: (i) Rank-1 Face Search Performance on MegaFace (1 million distractors), (ii) Rank-1 Fingerprint Search performance (using NIST SD4 against a gallery of 100 million synthetic fingerprints <cit.>), (iii) Top-1 classification accuracy and Precision-Recall curves from a subset of 100 classes of the ImageNet validation set, and (iv) Precision @ 10 (Precision in Top-10 retrieved samples) using the entire ImageNet validation set. For classification experiments on ImageNet, we train a Linear SVM classifier (one-vs-rest) on top of our embeddings. To compute Precision @ 10, we randomly select 10 probes from each validation class, and use the remaining 40 from each class as mates. These mates are combined with the remaining 45,000 distractors with 900 classes and 50 images / class.




Table <ref> and Table <ref> show the Rank-1 accuracy of encrypted face and fingerprint search, respectively, as we compress the representations with DeepMDS++. These results suggest that, practically speaking, we can compress the face representations by a factor of 4× (512-dim to 128-dim) for a performance loss of 2.6% (81.4% to 78.8%). Similarly fingerprint representations can be compressed by a factor of 6× (192-dim to 32-dim) where the performance only drops by 0.1%. The 100 Million fingerprint gallery size indicates that DeepMDS++ is incredibly scalable. The degree of compression of the representation by DeepMDS++ closely mirrors the intrinsic dimensionality estimates[ID estimate code: <https://github.com/human-analysis/intrinsic-dimensionality>] of the respective representations. The intrinsic dimensionalities of ArcFace, DeepPrint and Inception ResNet V2 are 15, 5 and 6 respectively, suggesting that unfolding ArcFace down to 16-dim is about three times as hard as compressing the latter two representations.




Table <ref> reports the performance of DeepMDS++ and DeepMDS on the ImageNet dataset for the task of image retrieval and image classification, respectively. Figure <ref> shows the full precision recall curves at dimensions of 1536, 64, 32 and 16 for Inception ResNet v2 embeddings. We make the following observations from these results,


  
  * It is feasible to compress the image representations by large factors for a small performance penalty. For instance, the representation can be compressed by a factor of 24× (1536-dim to 64-dim) for a performance loss of 1% (92% to 91%) in AP and 1% (86.2% to 85.0%) Top-1 accuracy or by a factor of 48× (1536-dim to 32-dim) for a performance loss of 4% (92% to 88%) in AP and 4.5% (86.2% to 81.8%) in Top-1 accuracy.
  
  * Representations compressed through DeepMDS++ are able to retain more discriminative information compared to DeepMDS, especially at lower dimensions. For instance, at 32-dim DeepMDS++ obtains an average precision of 88% compared to 68% by DeepMDS for image retrieval. Similarly DeepMDS++ Top-1 image classification accuracy is 81.8% compared to  66.1% for DeepMDS.
  
  * From the precision recall curves, we note that as the Inception ResNet v2 ambient embeddings are compressed to a lower number of dimensions, DeepMDS++ has an increasing advantage over the original DeepMDS <cit.>.






Two Stage Search: In Table <ref>, we demonstrated that  obtains encrypted search results against a gallery of 100 million in 740 seconds when the dimensionality of the representation is 32-dim. At 16-dim, this search time could be further reduced to 370 seconds. However, as shown in Table <ref>, the fingerprint search accuracy deteriorates quite heavily when reducing the DeepPrint representation from 32-dim to 16-dim. To leverage the significant time savings from further dimensionality reduction to 16-dim, we propose a two stage encrypted search algorithm. In the first stage, we utilize the 16-dim DeepPrint representation as a “coarse matcher" in conjunction with  to find the top-K candidates. Then, we use the full 192-dim DeepPrint representation in conjunction with the encryption scheme from <cit.> to re-rank the top-K candidates. In this manner, we obtain the benefits of the 16-dim representation for faster search speeds, and by choosing an appropriate value for K, we can obtain nearly identical search accuracy to using the 192-dim representation for the full initial search. Note that we use <cit.> for the second stage of the search since it enables matching against the specific indices of the database returned by our first stage search. Figure <ref> shows the rank-level search accuracy for DeepPrint on NIST SD4 against a gallery of 100 million synthetic fingerprints when (i) the initial 192-dim representation is used and (ii) the 16-dim representation is used as a first stage search algorithm, and then the 192-dim representation is used to re-rank. From these results, we observe that when K=10,000 for the two-stage search, we can match the accuracy of the full 192-dim representation. This in turn enables cutting the encrypted search time against 100 million fingerprints from 4,500 seconds (at 192-dim) to 500 seconds (370 seconds for stage-1 search, 130 seconds for stage-2 re-ranking) without loss of accuracy. 

Admittedly, one downside of the two stage encrypted search scheme is that it requires encrypting the representations twice (once with the  encoding and once with the encoding from <cit.>). This results in the overhead of the 9 TB gallery of <cit.> (for 100 million representations). In general, when designing an encrypted search system, we are looking to optimize along axes of speed, memory, accuracy, and security. Depending on the demands of the particular application, the point at which we land along these axes can be shifted.  explores different points along these axes via dimensionality reduction of features (small amounts of accuracy for significant speed savings), and a data-encoding scheme (sacrificing speed and memory at smaller gallery sizes for gains in both at larger galleries). Likewise, the two-stage search schema trades off memory overhead for encrypted search speed and accuracy gains without compromising security.



Ablation: Finally, we conduct an ablation on DeepMDS++. Table <ref> shows the impact of hard-pair mining and the covariance loss on the ability of DeepMDS++ to compress the representations. We observe that hard-pair mining is effective across all dimensions while the covariance loss is more effective around 32 to 64 dimensions where a noticeable benefit is observed. The ability of DeepMDS++ to retain more discriminative information than DeepMDS affords compression to lower dimensions which in turn synergistically aids in improving the efficiency of encrypted search.







§ SECURITY ANALYSIS

We adopt common assumptions in cryptography, i.e., the entities in our system (client and server) are semi-honest - each entity “follows the protocol properly with the exception that it keeps a record of all its intermediate computations"<cit.>. Under these assumptions, the security of  is built upon the security of the FV scheme, which in turn is based in the hardness of the Ring Learning with Errors problem <cit.>. Practically, this means that the security of our entire protocol hinges upon the fact that the ciphertext cannot be decrypted without access to the private (secret) decryption key which resides only on the client. An attractive property of the FHE scheme <cit.> used in this paper is that it offers post-quantum security for an appropriate choice of encryption parameters as outlined in the homomorphic encryption standard <cit.>. The encryption parameters (n,t,q) chosen by our experiments correspond to 128-bits of post-quantum security.

The  system has three sources of vulnerability to attackers, namely, (1) the client device which holds the secret keys, (2) the communication channel between the client and server, and (3) the database which holds the encrypted representations and performs score computation in the encrypted domain. The physical and digital security of the client is most important in order to protect the secret keys. Indeed, if the secret key were obtained from the client, the encrypted templates could be inverted and the templates exposed. Thus the security of the client is of utmost importance. We also note that in HERS, it is possible that some additional protection is rendered to the templates via our dimensionality reduction algorithm (compact feature vectors may be harder to reconstruct useful information from than the original full length representations). The security of the communication channel and the database server are guaranteed by the security of the FV scheme itself.



Score Inversion: We now consider an attack based on access to the decrypted scores. We posit that access to the decrypted score without access to the unencrypted features does not allow an attacker to estimate the user's biometric signature. From an adversary's perspective, recovering the unknown feature q∈ℝ^d from the scores r=P^Tq can be expressed as an optimization problem,

    min_q     r - P^Tq_2^2 
    
            s.t.      q^Tq = 1

where we assume that the unknown feature is normalized. If the feature is not normalized, the constraint can be removed. The solution of this optimization problem is, q=(PP^T + λI)^-1Pr. Observe that the solution depends on having access to the raw features P in the database. However, without access to the secret decryption keys, the database P is available only in the encrypted form. Therefore, even with access to the unencrypted scores, the unknown feature cannot be recovered.



§ DISCUSSION

Here we briefly comment on our choice of cryptographic solution, namely, FHE, the limitations induced by our choice and contrast it with other plausible cryptographic solutions. Two other alternative cryptographic solutions that can be employed in lieu of or in conjunction with FHE are:



Partial Homomorphic Encryption (Paillier Cryptosystem <cit.>): This scheme supports only homomorphic additions and is significantly more efficient for scalars than the FV scheme we use. However, it does not support massively vectorized SIMD operations, which is the key source of efficiency in .



Secure Multi-Party Computation <cit.>: This scheme can be employed to securely compute the nearest neighbors (including matching score and argmax index) by employing multiple parties that communicate secret shares with each other in such a way that no single party can access all the features. This approach trades-off low computation for high communication costs. Furthermore, it requires that the database be split among multiple parties which may not be desirable in some applications. In contrast, the FHE scheme trades-off low-communication costs for high computational costs. The main drawback of the FV scheme is the limited arithmetic operations supported by it, namely addition and multiplication. Therefore, computing non-linear functions like max and argmax are not supported by [Approximate comparison between homomorphically encrypted numbers is now supported by the CKKS FHE scheme <cit.>. In principle, although this capability can be leveraged to compute the argmax of the encrypted scores, it is computationally too prohibitive and is a topic of future research.]. In the context of search, as opposed to 1:1 verification, it is often sufficient to protect the gallery and query representations, as opposed to the matching scores as discussed in Section <ref>. In such cases, our solution of computing the matching scores in the encrypted domain, having the client decrypt the scores and finally having the server respond with the matched database index should suffice.




§ CONCLUSIONS

In  this paper, we proposed , a scheme for accurate and practical search over homomorphically encrypted representations at scale. The efficiency of  stems from (i) efficient cryptographic primitives for encrypted matrix-vector products, and (ii) DeepMDS++, a non-linear dimensionality reduction technique to reduce operations in the encrypted domain. The accuracy of  stems from (i) the exact computations of our cryptographic primitive, and (ii) the effectiveness of DeepMDS++ in maintaining matching performance at large compression factors. Our experimental results demonstrate, for the first time, practical (under 10 minutes) and accurate (within ≈ 2% of unencrypted accuracy) image search (for face, fingerprint and ImageNet) against 100 Million gallery in the encrypted domain.



§ ACKNOWLEDGEMENTS

This research was supported in part by a grant from The NSF Center for Identification Technology Research (CITeR). Vishnu Boddeti was supported in part by award 60NANB18D210 from U.S. Department of Commerce, National Institute of Standards and Technology.








ieeetr



[
    < g r a p h i c s >
]Joshua J. Engelsma graduated magna cum laude with a B.S. degree in computer science from Grand Valley State University, Allendale, Michigan, in 2016. He obtained a PhD degree in Computer Science and Engineering at Michigan State University, May 2021. His research interests include pattern recognition, computer vision, and image processing with applications in biometrics. He won the best paper award at the 2019 IEEE International Conference on Biometrics (ICB), and the 2020 Michigan State University College of Engineering Fitch Beach Award.


[
    < g r a p h i c s >
]Anil K. Jain is a University Distinguished Professor in the Department of Computer Science at Michigan State University. He is a Fellow of the ACM, IEEE, IAPR, AAAS and SPIE. His research interests include pattern recognition and biometric authentication. He served as the editor-in-chief of the IEEE Transactions on Pattern Analysis and Machine Intelligence, a member of the United States Defense Science Board and the Forensics Science Standards Board. He has received Fulbright, Guggenheim,  Alexander von Humboldt, and IAPR King Sun Fu awards. He is a member of the United States National Academy of Engineering, a member of The World Academy of Science, and foreign members of the Indian National Academy of Engineering and the Chinese Academy of Sciences.


[
    < g r a p h i c s >
]Vishnu Naresh Boddeti is an Assistant Professor in the computer science department at Michigan State University. He received a Ph.D. degree in Electrical and Computer Engineering program at Carnegie Mellon University in 2013. His research interests are in Computer Vision, Pattern Recognition and Machine Learning. He received the best paper award at BTAS 2013, the best student paper award at ACCV 2018, and the best paper award at GECCO 2019.




