1 Introduction

Biometric techniques have advanced over the past years to a reliable means of authentication, which have been deployed in various application domains. Many governments have already rolled out electronic passports and identities (Naumann and Hogben 2008) that contain biometric information (e.g., face images, fingerprints, and iris scan) of their legitimate holders. Unlike other types of data used for authentication purposes (passwords, key material, secure tokens, etc.), the biometric data cannot be revoked and replaced with a new value, hence it calls for strict protection of such biometric data. In particular, face recognition systems have become more popular due to its unobtrusiveness and ease of use. Thus, face recognition systems have been widely applied in a variety of enterprise, civilian and law enforcement, such as surveillance of public places, access and border control at airports, Facebook in social networking platforms, etc.

The widespread use of face recognition systems, however, can lead to privacy risks as biometric information could be collected and misused without the permission of the owner. These issues raise the desire to construct privacy-preserving face recognition systems. In recent years, many methods for protecting biometric data were proposed, such as methods on fuzzy vault (Juels and Sudan 2006; Chang and Li 2006), secure sketches and fuzzy feature extractors (Dodis et al. 2004; Boyen 2004; Li et al. 2010; Dodis et al. 2008; Bhattacharjee et al. 2010; Liu and Ye 2014), shielding functions (Linnartz and Tuyls 2003; Tuyls et al. 2005), cancelable or revocable biometrics (Ratha et al. 2001), and so on. These methods stored a function of each biometric rather than the biometrics data themselves, but it did not lead to compromise of the biometric data in the case of server compromise. For face recognition systems, in order to protect individuals’ privacy, face recognition was performed over encrypted face images in previous works (Erkin et al. 2009; Sadeghi et al. 2010). However, these results increased the computation cost of clients and database owners of the face images, which may enable face recognition not to be executed. Currently, no existing tools or techniques are readily available to carry out the huge computation task of the database owner. Thus, the problem of secure biometric face identification (or matching) with the aid of untrusted cloud servers is the focus of this work. In the cloud environment, many schemes were proposed, e.g. (Wang et al. 2014; Castiglione et al. 2015; Esposito et al. 2013, 2015; Li et al. 2014, 2013; Chen et al. 2014).

In this paper, we concentrate on efficient privacy-preserving face recognition systems with the aid of untrusted cloud servers. The typical scenario here is a application which consists of three parties, i.e., a client, a database owner of face images and a cloud server. Both the client and database owner have limited (or weak) computing power, but the cloud server has the ability to process magnanimity data and perform parallel computation. The client provides a specific face image and needs to know whether the image is contained in the database of face images. In addition, the face recognition systems satisfies the following requirements: (1) the client believes the database owner correctly performs the matching algorithm for the face recognition but without revealing any useful information to the database owner about the requested image as well as about the outcome of the matching algorithm; (2) the database owner requires privacy of its database beyond the matching results to the client; (3) the database owner needs help from the cloud server which cannot reveal any useful information about real face images and can greatly reduce the database owner’s computation cost using the ability of processing intelligent data and performing parallel computation.

1.1 Related work

Some authors have proposed different complementary techniques for making surveillance cameras more privacy friendly, e.g. (Dufaux and Ebrahimi 2006; Yu et al. 2008; Li et al. 2014a). However, they do not consider face recognition. For privacy-preserving face recognition, Erkin et al. (2009) proposed for the first time a strongly privacy-enhanced face recognition system. They used the standard and popular Eigenface recognition algorithm (Turk and Pentland 1991). The system performs operations on encrypted images by means of homomorphic encryption schemes, more concretely, (Paillier 1999; Damgard and Jurik 2001) as well as a cryptographic protocol for comparing two Paillier encrypted values based on DGK (Damgard, Geisler and Kroigard) cryptosystem (Damgard et al. 2007, 2008). They demonstrate that privacy-preserving face recognition is possible in principle and give required choices of parameter sizes to achieve a good classification rate. However, the proposed protocol requires O(logM) rounds of online communication as well as computationally expensive operations on homomorphically encrypted data to recognize a face in the database of M faces. Due to these restrictions, the proposed protocol cannot be deployed in practical large-scale applications. After that, Sadeghi et al. (2010) given two privacy-preserving face recognition protocols which substantially improved over previous work (Erkin et al. 2009). One is based on homomorphic encryption (see, e.g., Paillier 1999; Damgard and Jurik 2001) and Yao et al.’s Garbled Circuit (GC) (Yao 1986; Lindell and Pinkas 2004), the other is based on GC only. Although the protocols allowed to shift most of the computation and communication into a pre-computation phase, the computation cost of the client and database owner was not reduced. This means that efficiently implementing privacy-preserving face recognition is difficult for the client and the database owner with weak computing power. We improve Sadeghi et al. ’s protocol based on homomorphic encryption and Garbled Circuit in this paper. In the rest of the paper, the protocol in Sadeghi et al. (2010) is based on homomorphic encryption and Garbled Circuit unless stated otherwise.

The related problem of privacy-preserving face detection (Avidan and Butman 2006) allows a client to detect faces on his image using a private classifier held by servers without revealing the face or the classifier to the other party. In order to preserve privacy, faces can be de-identified so that face recognition software cannot reliably recognize de-identified faces, even though many facial details are preserved as described in Newton et al. (2005).

Besides privacy-preserving face recognition, there were a few attempts to make other biometric modalities privacy preserving, such as fingerprints and iris codes (Ratha et al. 2006; Kevenaar 2007). However, these works consider a different setting, where the biometric measurement is matched against a hashed template stored on a server. The server that performs the matching gets to know both the biometric and the detection result (the aim is only to secure storage of templates). In Blanton and Aliasgari (2012), a secure outsourced computation scheme of iris matching was proposed. To the best of our knowledge, there is no prior solution to carry out the huge computation task of the database owner in the secure privacy-preserving face recognition system. In order to reduce the computation cost, we present a new protocol for privacy-preserving face recognition which can outsource lager computation task to a third party (e.g., cloud servers) who has a huge computing power.

1.2 Contribution

We propose an efficient and secure privacy-preserving face recognition protocol with outsourced computation. Our protocol is based on the Eigenfaces recognition algorithm (Turk and Pentland 1991) and a hybrid Encryption based on fully homomorphic encryption (FHE) in Li and Lai (2012). We do not use Garbled Circuits. Our protocol substantially improves over previous works (Erkin et al. 2009; Sadeghi et al. 2010) as it has only one round (two moves) between the client and the database owner. Furthermore, the protocol can efficiently outsource most of the computation to an untrusted cloud server. The remaining computation cost of the client and the database owner is small. Beyond the encryption operations, the online computation cost of the client and the database owner in our protocol is at most 1/2 of the corresponding protocol in the state-of-the-art algorithms, this is especially important for the client and the database owner with weak computing power.

1.3 Organization

The rest of the paper is organized as follows. We summarize our model and security requirements, parameters setting and cryptographic tools used in our constructions in Sect. 2. A summary of the face recognition algorithm using Eigenfaces is reviewed in Sect. 3. Section 4 details our secure privacy-preserving face recognition protocol with outsourced computation. Security and efficiency analysis of our protocol are given in Sect. 5. And Sect. 6 concludes the paper.

2 Preliminaries

In this section, we give the model and the security requirements of our scheme and summarize cryptographic tools used in our constructions.

2.1 Model and security requirements

In this paper, we give a simplified model depicted in Fig. 1. Three parties are involved in our model, that is, a client (C), a database owner (DB) of face images and an untrusted cloud server (CS). Both the client and database owner have limited (or weak) computing power, but the cloud server has the ability to process magnanimity data and perform parallel computation. The client provides a specific face image and needs to know whether the image is contained in the database of face images held by the database owner. Since the computational cost is to high for the DB, the DB may not have the capacity to complete the computation task by itself. Thus, the database owner DB requires assistance from a third party (e.g., cloud servers). Based on the above analysis, we use outsourced computation which can enable the database owner to outsource all or partly computation to the cloud server who has more computational power in this paper. Meanwhile, the cloud server returns the recognition results to the client and the client can verify the correctness of the recognition results. In addition, the scheme should satisfy three requirements which are described in the Sect. 1.

Fig. 1
figure 1

The model

Full size image

We work in the semi-honest model where the client and the database owner are assumed to be honest-but-curious but the cloud server is untrusted.

Similar to Erkin et al. (2009) and Sadeghi et al. (2010), we summarize the notations and the parameters used in this paper in Table 1.

Table 1 Summary of notations and parameters
Full size table

2.2 Cryptographic tools

Hybrid encryption based on FHE We use a semantically secure hybrid encryption (HS) based on FHE scheme in Li and Lai (2012), which is a combination of an ordinary (non-FHE) encryption scheme and a FHE scheme. In Li and Lai (2012), the authors give a detailed hybrid encryption scheme using a symmetric encryption scheme and a FHE scheme. A public-key encryption schemes (e.g., RSA, Paillier) can as well be used as an ordinary encryption scheme. In this paper, we use a semantically secure hybrid encryption (HS) which is a combination of a public-key encryption scheme and a FHE scheme. Let M be a plaintext space, FHE=(FHE.KeyGen, FHE.Enc, FHE.Dec, FHE.Eval) be a FHE scheme, and PE=(PE.KeyGen, PE.Enc, PE.Dec) be a public-key encryption scheme (PE). A hybrid encryption scheme HS=(HS.KeyGen, \(\text {HS.Enc}_{1}\), \(\text {HS.Enc}_{2}\), \(\text {HS.Dec, HS.Eval})\) consists of five PPT algorithms (PPT is shorthand for probabilistic polynomial time), which are described as follows.

  • \(\text {HS.KeyGen}(\lambda )\rightarrow (pk,dk,pk',sk,\kappa )\). Takes as input a security parameter \(\lambda \), runs \(\text {FHE.KeyGen}\) to obtain a public encryption key pk and a secret decryption key dk, runs \(\text {PE.KeyGen}\) to obtain public encryption key \(pk'\) and a secret decryption key sk. Then, encrypts sk under the public key pk to obtain \(\kappa \leftarrow \text {FHE.Enc}(pk,sk)\), outputs \((pk,dk,pk',sk,\kappa )\).

  • \(\text {HS.Enc}_{1}(pk',x)\rightarrow c\). Runs \(\text {PE.Enc}\) to encrypt message \(x\in M\) under the public key \(pk'\), outputs ciphertext c.

  • \(\text {HS.Enc}_{2}(pk,\kappa ,c)\rightarrow c_{x}\). On input \((pk,\kappa ,c)\), outputs a new ciphertext \(c_{x}\) which is equal to \(\text {FHE.Enc}(pk,x)\).

  • \(\text {HS.Dec}(dk,c_{x})\rightarrow x\). Same as \(\text {FHE.Dec}\). Takes as input dk and \(c_{x}\), and decrypts the ciphertext \(c_{x}\) to a plaintext \(x\in M\) under the secret key dk.

  • \(\text {HS.Eval}(pk,C,c_{1},c_{2},\ldots ,c_{n})\rightarrow c_{y}\). Same as the FHE. Eval. Given the public key pk, a circuit C and a set of n ciphertexts \(c_{1},c_{2},\ldots ,c_{n}\) deterministically compute and outputs a new ciphertext \(c_{y}\).

Similar to FHE, a HS scheme should also satisfy four properties, which is encryption correctness, evaluation correctness, succinctness and semantic security.

As instantiation we use the Paillier public-key encryption scheme (Paillier 1999; Damgard and Jurik 2001) which has plaintext space \(Z_{N}\) and ciphertext space \(Z_{N^{2}}\), where N is a T-bit RSA modulus, while we use the FHE scheme over the integers (Dijk et al. 2010). In Erkin et al. (2009), the privacy-preserving face recognition protocol uses the homomorphic cryptosystem of Damgard, Geisler and Kroigard (DGK) other than the Paillier public-key encryption scheme. The DGK homomorphic encryption scheme can reduce the ciphertext space to \(Z_{N}^{*}\). In Sadeghi et al. (2010), the privacy-preserving face recognition protocol additionally uses Yao’s Garbled Circuit other than the Paillier public-key encryption scheme. Both protocols in Erkin et al. (2009) and Sadeghi et al. (2010) do not use FHE.

In this paper, in an additively homomorphic Paillier encryption scheme, given encryptions \([a]_\mathrm{PE}\) and \([b]_\mathrm{PE}\), an encryption \([a + b]_\mathrm{PE}\) can be computed by \([a + b]_\mathrm{PE}=[a]_\mathrm{PE}\cdot [b]_\mathrm{PE}\), where all operations are performed in the algebra of the message or ciphertext space. Furthermore, in a FHE scheme, given encryptions \([a]_\mathrm{FHE}\) and \([b]_\mathrm{FHE}\), an encryption \([a + b]_\mathrm{FHE}\) can be computed by \([a + b]_\mathrm{FHE}=[a]_\mathrm{FHE}+[b]_\mathrm{FHE}\) and \([ab]_\mathrm{FHE}\) can be computed by \([ab]_\mathrm{FHE}=[a]_\mathrm{FHE}[b]_\mathrm{FHE}\).

3 Face recognition algorithm using Eigenfaces

In the following we briefly summarize the recognition process of the Eigenfaces algorithmm (Turk and Pentland 1991; Erkin et al. 2009; Sadeghi et al. 2010). The algorithm obtains as input the query face image \(\varGamma \) represented as a pixel image with N pixels. Additionally, the algorithm obtains the parameters determined in the enrollment phase as inputs: the average face \(\varPsi \) which is the mean of all training images, the Eigenfaces \(u_{1}, \ldots \), \(u_{K}\) which span the K-dimensional face space, the projected faces \(\varOmega _{1}, \ldots , \varOmega _{M}\) being the projections of the M faces in the database into the face space, and the threshold value \(\tau \). The output r of the recognition algorithm is the index of that face in the database which is closest to the query face \(\varGamma \) or the special symbol \(\perp \) if no match was found, i.e., all faces have a larger distance than the threshold \(\tau \). Specifically, the recognition algorithm consists of three phases, which are described as follows.

  1. 1.

    Projection The average face \(\varPsi \) is subtracted from the face \(\varGamma \) and the result is projected into the K-dimensional face space using the Eigenfaces \(u_{1},\ldots \), \(u_{K}\). The result is the projected K-dimensional face \(\bar{\varOmega }\).

  2. 2.

    Distance The square of the Euclidean distance \(D_{i}\) between the projected K-dimensional face \(\bar{\varOmega }\) and all projected K-dimensional faces in the database \(\varOmega _{i}(i=1,2,\ldots ,M)\) is computed.

  3. 3.

    Minimum The minimum distance \(D_\mathrm{min}\) is selected. If \(D_\mathrm{min}\) is smaller than the threshold \(\tau \), the index of the minimum value, i.e., the identifier \(i_\mathrm{min}\) of the match found, is returned to the client and as a result \(r=i_\mathrm{min}\). Otherwise, the image was not found and the special symbol \(r=\perp \) is returned.

4 Privacy-preserving face recognition with outsourced computation

In this section, we present a privacy-preserving face recognition protocol with outsourced computation. The protocol operates on encrypted images. Three parties are involved in our schemes, that is, a client C, a database owner DB of face images and an untrusted cloud server CS. We work in the semi-honest attacker model. Informally, this assumes that the client C and the database owner DB follow the protocol but try to learn additional information from them. In addition, any outsourcer can verify the correctness of the untrusted cloud server output. It is also assumed that the parties communicate over an authenticated channel (this can be achieved by standard mechanisms and is thus outside the scope of this paper). We assume that a database owner has already set up the face recognition system by running the enrollment process (in the clear) on all available training images \(\{\theta _{1},\ldots ,\theta _{M}\}\) to obtain the basis \(u_{1}, \ldots , u_{K}\) of the face space and feature vectors \(\varOmega _{i}(i=1,2,\ldots ,M)\) of faces to be recognized.

Furthermore, we assume that all coordinates of the eigenfaces and feature vectors are represented as integers. Each feature vector in the database is further accompanied by a string \(id_{i}\) that contains the identity of the person the feature vector belongs to; we assume that the identity is encoded as a non-zero element of the message space of the chosen encryption scheme.

Figure 2 shows an outline of our protocol, which is described as follows.

Fig. 2
figure 2

Outline of our protocol

Full size image

Projection The input image \(\varGamma \) has to be projected onto the low-dimensional face space spanned by the eigenfaces \(u_{1}, \ldots , u_{K}\). the client C runs \(\text {HS.Gen}\) to obtain \((pk,dk,pk',sk,\kappa )\), where (pk, dk) is the public/secret key pair of the FHE and \((pk',sk)\) is the public/secret key pair of the Paillier homomorphic encryption scheme. In addition, \(\kappa \) is the encryption of sk under FHE. Let \(\kappa \) be \([sk]_{FHE}\). The client C encrypts the face \(\varGamma \) as \([\varGamma ]_\mathrm{PE}=([\varGamma _{1}]_\mathrm{PE},\cdots ,[\varGamma _{N}]_\mathrm{PE})\). Meanwhile, the client randomly chooses three elements a,b and c, and encrypts them as \([a]_\mathrm{PE}\), \([b]_\mathrm{PE}\) and \([c]_\mathrm{PE}\).

The client sends \(\{[\varGamma ]_\mathrm{PE},[a]_{E},[b]_\mathrm{PE},[c]_\mathrm{PE},[sk]_\mathrm{FHE}\}\) along with \((pk,pk')\) to the database owner DB. Using the homomorphic properties and outsourced computation, DB projects the encrypted face into the low-dimensional face space and obtains the encryption of the projected face \([\bar{\varOmega }]_\mathrm{PE}=([\bar{\omega _{1}}]_\mathrm{PE},\cdots ,[\bar{\omega _{K}}]_\mathrm{PE})\) as follows.

  1. 1.

    For \(i=1,\ldots ,K\), the database owner DB computes \(p_{i}=-\sum _{j=1}^{N}u_{i,j}\varPsi _{j}\), where \(\varPsi _{j}\) is the component of the vector \(\varPsi =\frac{1}{M}\sum _{i=1}^{M}\theta _{i}\). This step can be completed in the pre-computation phase (offline phase).

  2. 2.

    The database owner DB encrypts \(p_{i}\) under the public key \(pk'\) to obtain \([p_{i}]_\mathrm{PE}=[-\sum _{j=1}^{N}u_{i,j}\varPsi _{j}]_\mathrm{PE}\). This step is completed in the online phase.

  3. 3.

    DB computes \(q_{i}=\prod _{j=1}^{N}[\varGamma _{j}]_\mathrm{PE}^{u_{i,j}}\) using outsourcing exponentiation algorithm (such as (Wang et al. 2014)) which can reduce the database owner DB ’s computation cost.

  4. 4.

    For \(i=1,\ldots ,K\), the database owner computes \([\bar{\omega _{i}}]_\mathrm{PE}=[p_{i}]_\mathrm{PE}\cdot q_{i}\).

Distance After projection, the database owner DB needs to compute the Paillier encryption of the Euclidean distances between the projected face \(\bar{\varOmega }\) and all projected faces \(\varOmega _{1},\ldots ,\varOmega _{M}\) in the database held by the database owner in Erkin et al. (2009) and Sadeghi et al. (2010). In addition, DB also needs interaction with the client. In our protocol, DB does not need interaction with the client. Because the computation cost is very large for DB, who may no capacity to complete the computation task by himself. Thus, the database owner DB requires assistance from a third party (e.g., cloud server). In this paper, we use outsourced computation which can enable the database owner to outsource all or partly computation to the cloud server who has lager computing powering. For \(i=1,2,\ldots ,M\), the encryption of the square Euclidean distances \([D_{i}]_\mathrm{PE}=[\Vert \varOmega _{i}-\bar{\varOmega }\Vert ^{2}]_\mathrm{PE}=[S_{1,i}+S_{2,i}+S_{3}]_\mathrm{PE}=[S_{1,i}]_\mathrm{PE}\cdot [S_{2,i}]_\mathrm{PE}\cdot [S_{3}]_\mathrm{PE}\), where \([S_{1,i}]_\mathrm{PE}=[\sum _{j=1}^{K}\omega _{i,j}^{2}]_\mathrm{PE}\), \([S_{2,i}]_\mathrm{PE}=[\sum _{j=1}^{K}(-2\omega _{i,j}\bar{\omega _{j}})]_\mathrm{PE}= \prod _{j=1}^{K}\) \([\bar{\omega _{j}}]_\mathrm{PE}^{-2\omega _{i,j}}\) and \([S_{3}]_\mathrm{PE}=[\sum _{j=1}^{K}\bar{\omega _{j}}^{2}]_\mathrm{PE}\). We notice that \(S_{3}\) is a fixed value once the input mage \(\varGamma \) and the face database are fixed. Hence, DB only needs to compute \([D_{i}']_\mathrm{PE}=[S_{1,i}+S_{2,i}]_\mathrm{PE}=[S_{1,i}]_\mathrm{PE}\cdot [S_{2,i}]_\mathrm{PE}\). These cannot effect the next step (See. Match finding). Specifically, \([D_{i}']_\mathrm{PE}\) can be computed as follows.

  1. 1.

    To obtain \([S_{1,i}]_\mathrm{PE}\), the database owner DB needs to complete two steps below.

    • DB computes \(\sum _{j=1}^{K}\omega _{i,j}^{2}\) which can be pre-computed in the offline stage.

    • DB encrypts \(\sum _{j=1}^{K}\omega _{i,j}^{2}\) under the public key \(pk'\) to obtain \([S_{1,i}]_\mathrm{PE}=[\sum _{j=1}^{K}\omega _{i,j}^{2}]_\mathrm{PE}\). This step is completed by the database owner DB in the online phase.

  2. 2.

    For computing \([S_{2,i}]_\mathrm{PE}\), the database owner DB firstly outsources exponentiation \([\bar{\omega _{j}}]_\mathrm{PE}^{-2\omega _{i,j}}\) to the cloud server CS by outsourcing exponentiation algorithm, and then multiply those exponentiation together to obtain \([S_{2,i}]_\mathrm{PE}\).

  3. 3.

    For \(i=1,2,\ldots ,M\), DB computes \([D_{i}']_\mathrm{PE}=[S_{1,i}]_\mathrm{PE}\cdot [S_{2,i}]_\mathrm{PE}\)

Thus, DB can finish this phase without interacting with the client.

Minimum (Match finding) In the last step of the recognition algorithm, the goal is to find the minimum value D from \(\{D_{i}\}_{i=1}^{M}\) and its index \(Id_\mathrm{min}\). If the minimum value D is smaller than the threshold value \(\tau \) known by the database owner, then a match is reported and an encryption of the identity \(Id_\mathrm{min}\) which corresponds to the best matching feature vector is returned to the client. Because \(S_{3}\) is a fixed value, we only need to find the minimum value \(D'\) from \(\{D_{i}'\}_{i=1}^{M}\) and its index \(Id_\mathrm{min}\). If the minimum value \(D'\) is smaller than the value \(\tau '=\tau -S_{3}\), then a match is reported and an encryption of the identity \(Id_\mathrm{min}\) which corresponds to the best matching feature vector is returned to the client.

As we need to return the identity of the best matching feature vector, we also have to keep track of the IDs during the minimum computation. This is done by working with pairs \(([D_{i}']_\mathrm{PE}, [Id_{i}]_\mathrm{PE})\) of distances and their corresponding identities. To check if the minimum distance is smaller than \(\tau '\), we can treat the value \(\tau '\) as one additional distance that has the special identity 0. Together with the distances \(D_{1}'.\ldots , D_{M}'\), the client, the database owner, and the cloud server jointly carry out the protocol with verifiable outsourced computation to find minimum distance and the corresponding identity \(([D']_\mathrm{FHE}, [Id]_\mathrm{FHE})\), where \(D'\in \{\tau ',D_{1}',\ldots ,D_{M}'\}\) and \(Id\in \{0, Id_{1}, \ldots , Id_{M}\}\). Thus, if a face image could be recognized the value Id contains the corresponding identity. If no match could be found Id is equal to 0. Some encrypted values are finally sent to the client as the result of the private face recognition protocol. Then, the client can obtain the recognition result Id by some computations and can verify the correctness of the result. To achieve this, the client C, the database owner DB, and the cloud server CS jointly run the following match finding protocol (MFP) with verifiable outsourced computation (VOC).

  1. 1.

    The database owner DB constructs a circuit \(C_\mathrm{circuit}\) with multi-input, which is shown in Fig. 3. This can be completed by the database owner in the offline stage.

  2. 2.

    DB sends the circuit \(C_\mathrm{circuit}\), \([sk]_\mathrm{FHE}\) and \(\sigma =\{[\tau ]_\mathrm{PE},\) \([\bar{\omega _{1}}]_\mathrm{PE},\ldots , [\bar{\omega _{K}}]_\mathrm{PE}, [D_{1}']_\mathrm{PE}, \ldots , [D_{M}']_\mathrm{PE}, [a]_\mathrm{PE}, [b]_\mathrm{PE},\) \([c]_\mathrm{PE}\}\) to the cloud server CS.

  3. 3.

    For each element in the set \(\sigma \), CS runs the algorithm \(\mathrm{HS.Enc_{2}}\) to get \(\sigma '=\{[\tau ]_\mathrm{FHE},[\bar{\omega _{1}}]_\mathrm{FHE}, \cdots ,[\bar{\omega _{K}}]_\mathrm{FHE},\) \([D_{1}']_\mathrm{FHE},\ldots ,[D_{M}']_\mathrm{FHE},[a]_\mathrm{FHE},[b]_\mathrm{FHE},[c]_\mathrm{FHE}\}\).

  4. 4.

    CS computes \(\mathrm{FHE.Eval}(pk,C_\mathrm{circuit},\sigma ')\) to obtain \([\varDelta _{1}]_\mathrm{FHE}\) and \([\varDelta _{2}]_\mathrm{FHE}\), then sends them to the client.

  5. 5.

    The client decrypts \([\varDelta _{1}]_\mathrm{FHE}\) and \([\varDelta _{2}]_\mathrm{FHE}\) under the secret key dk to obtain \(\varDelta _{1}\) and \(\varDelta _{2}\). If \(\varDelta _{1}-a=c(\varDelta _{2}-b)\), then the client accepts the match result \(\mathrm{Id}=\varDelta _{2}-b\), otherwise rejects. If \(\mathrm{Id}=0\), it shows that no match could be found in the database held by the database owner.

In our minimum (Match) finding protocol, the online computation and round complexity have been substantially improved for the client C and the database owner DB, we have given the comparison of three minimum protocols from two aspects, i.e., the online round complexity and the asymptotic computation complexity (ACC1), which is shown as in Table 2 with parameter \(m \approx \frac{l'M}{T-\kappa '}\), where T is the asymmettric security parameter and \(\kappa '\) is the statistical correctness parameter in Sadeghi et al. (2010).

Fig. 3
figure 3

Circuit \(C_\mathrm{circuit}\) for match finding with VOC

Full size image
Table 2 Comparison of three minimum protocols
Full size table

5 Security and efficiency analysis

The security of our protocol is based on the security of four schemes, i.e. the privacy-preserving face recognition scheme in Sadeghi et al. (2010), HS scheme in Li and Lai (2012) and the verifiable outsourced computation schemes for simultaneous exponentiations in Wang et al. (2014) and arbitrary functions in Tang and Chen (2014). This four schemes are secure which have been proved Sadeghi et al. (2010); Wang et al. 2014); Li and Lai 2012); Tang and Chen 2014). Thus, our protocol is secure.

In order to illustrative the efficiency of our protocol, we will give detailed analysis from three respects, i.e., the round, the communication and computation complexity.

5.1 Round complexity

The round complexity of our protocol is very low. Firstly, sending the encrypted face image takes one move. Secondly, for outsourced computation, it needs 5 moves between the database owner and the cloud server. In the last step of FMP, sending the result of FMP takes one move between the client and the cloud server. Hence the overall round cost is 7 moves. In addition, we note that it has only 3 moves if the database owner completes exponentiations by himself rather than the cloud server in both projection and calculation distance phases. Therefore, the round complexity of our protocol is O(1). Furthermore, our protocol does not require the database owner interaction with the client for calculation distance, but the database owner needs interactions with the cloud server if partly computation task is outsourced to the cloud server, in which it can reduce the computation cost of the database owner.

5.2 Online communication complexity

For communication complexity, the communication complexity highly depends on the size of Paillier encryption, FHE, and outsourcing algorithm. In the offline phase, the circuit \(C_\mathrm{circuit}\) with VOC can be transmitted to the cloud server. In the following, we only analyze the online communication complexity.

  • \({\varvec{C}}\rightarrow {\varvec{DB}}\). In the projection stage, the client requires transmission of 1 FHE encrypted value \([\mathrm sk]_\mathrm{FHE}, (N+3)\) Paillier encrypted values \(\{[\varGamma _{1}]_\mathrm{PE},\cdots ,[\varGamma _{N}]_\mathrm{PE},~[a]_\mathrm{PE}\),  \([b]_\mathrm{PE}\), \([c]_\mathrm{PE}\}\).

  • \({{\mathbf {DB}}}\rightleftharpoons {{\mathbf {CS}}}\). In the distance calculation phase, for \(i=1,\ldots ,K\), to obtain \([\bar{\omega _{i}}]_\mathrm{PE}=[p_{i}]_\mathrm{PE}\cdot q_{i}\), the database owner outsources the computation \(q_{i}=\prod _{j=1}^{N}[\varGamma _{j}]_\mathrm{PE}^{u_{i,j}}\) to CS using outsourced computation algorithm for simultaneous exponentiation (Sexp) in Wang et al. (2014) in the projection stage. Therefore, it needs \(K\cdot \lceil N/2\rceil \) operations of Sexp, which means that the communication overhead is \(K\cdot \lceil N/2\rceil \cdot (6\mathrm{log}p+12Len_{[\varGamma _{j}]_\mathrm{PE}})\), where p is the bit length of \(u_{i,j}\) and \(Len_{[\varGamma _{j}]_\mathrm{PE}}\) is the bit length of \([\varGamma _{j}]_\mathrm{PE}\). In the distance computation stage, it needs \(K\cdot \lceil N/2\rceil \) operations of Sexp for computing \([S_{2,i}]_\mathrm{PE}\), which means that the communication overhead is \(K\cdot \lceil N/2\rceil \cdot (6\mathrm{log}p'+12Len_{[\bar{\omega _{j}}]_\mathrm{PE}})\) bits, where \(p'\) is the bit length of \(-2\omega _{i,j}\) and \(Len_{[\bar{\omega _{j}}]_\mathrm{PE}}\) is the bit length of \([\bar{\omega _{j}}]_\mathrm{PE}\).

  • \({\varvec{DB}}\rightarrow {\varvec{CS}}\). In the minimum (match) finding stage, the circuit \(C_\mathrm{circuit}\) can be transmitted in the offline stage. It requires transmission of 1 FHE encrypted value and \((K+2M+4)\) PE encrypted values in the online stage. Similar to Erkin et al. (2009) and Sadeghi et al. (2010), we only require transmission of \((K+M+4)\) PE encrypted values if we omit the statistic for the transmission of \([id]_\mathrm{PE}\).

  • \({\varvec{CS}}\rightarrow {\varvec{C}}\). In the minimum (Match) finding stage, it requires transmission of 2 FHE encrypted value \([\varDelta _{1}]_\mathrm{FHE}\) and \([\varDelta _{2}]_\mathrm{FHE}\).

Similar to Erkin et al. (2009) and Sadeghi et al. (2010), we omit the statistic for the transmission of \([id_{i}]_\mathrm{PE}\). Let k be the number of the packed ciphertexts in (Sadeghi et al. 2010). Suppose that the size of FHE-ciphertexts is \(\gamma \) bits. We now compare our protocol with the previous works (Erkin et al. 2009; Sadeghi et al. 2010) as shown in Table 3. Unfortunately, the online communication cost of our protocol is larger than the precious works because we use outsourced computation algorithms which means that the outsourcer requires some interactions with the cloud server.

Table 3 Comparison of round and asymptotic communication complexity (ACC)
Full size table

5.3 Online computation complexity

The overall online computation complexity of our protocol is substantially lower. We denote by \(\text {Enc}_\text {PE}\) an invocation of the Paillier homomorphic encryption algorithm, by \(\text {Dec}_\text {PE}\) an invocation of the Paillier homomorphic decryption algorithm, by \(\text {Enc}_\text {FHE}\) an invocation of the FHE algorithm, by \(\text {Dec}_\text {FHE}\) an invocation of the fully homomorphic decryption algorithm, by MM a modular multiplication, by MInv a modular inverse, by Exp a modular exponentiation, by \(\text {Sexp}_\text {VOC}\) an invocation of the verifiable outsourced computation algorithm for simultaneous exponentiation. We omit other operations such as modular additions. More precisely, the online computation cost of the client and the database owner is given as follows.

  • In the projection phase, the client needs (N+3) \(\text {Enc}_\text {PE}\) and 1 \(\text {Enc}_\text {FHE}\), and the database owner requires K \(\text {Enc}_\text {PE}\), \(K\cdot \lceil N/2\rceil \) \(\text {Sexp}_\text {VOC}\) and \((K\lceil N/2\rceil )\) MM.

  • In the distance computation phase, the database owner needs M \(\text {Enc}_\text {PE}\), \((M\cdot \lceil K/2\rceil ) \text {Sexp}_\text {VOC}\) and \((M\cdot \lceil K/2\rceil )\) \(\text {MM}\).

  • In the minimum distance (or match) finding phase, the client needs \(2\text {Dec}_\text {FHE}\). Because the database owner needs to encrypt \(\{\tau ,id_{0},id_{1},\ldots ,id_{M}\}\) under PE, the database owner needs \((M+2)\text {Enc}_\text {PE}\) in the online phase.

Compared with the previous algorithms in Erkin et al. (2009), Sadeghi et al. (2010), our protocol is superior in efficiency due to the reduction of the computation cost of the client and the database owner. Similar to Erkin et al. (2009), Sadeghi et al. (2010), we omit the statistic for the computation cost of the encryption \(\{id_{i}\}_{i=0}^{M}\) under PE. Table 4 presents the comparison of the online computation cost of the client and the database owner in the three algorithms. In particular, beyond the encryption operations, we note that the overall computation cost of the client and the database owner in our protocol is at most 1/2 of the corresponding protocol in the state-of-the-art algorithms (Erkin et al. 2009; Sadeghi et al. 2010).

Table 4 Comparison of asymptotic computation complexity (online)
Full size table

6 Conclusion

In this paper, we present a privacy-preserving face recognition scheme with outsourced computation, which allows to match an encrypted image showing a face against a database of facial templates in such a way that the biometric itself and the detection result is hidden from the server that performs the matching. In particular, our protocol allows the database owner to securely outsource some computation task to an untrusted cloud server, and the database owner can detect the dishonest behavior of the untrusted cloud server. Furthermore, the client can verify the correctness of the recognition result. Compared with the state-of-the-art algorithms (Erkin et al. 2009; Sadeghi et al. 2010), beyond the same operations for encryption, the overall online computation cost of the database owner and the client is greatly reduced. However, the online communication cost cannot reduce due to using outsourced computation. Thus, the key problem of our protocol is that how to further reduce the online communication cost and the client’s computation cost on the future work.