Efficient Verifiable Computation of XOR for Biometric Authentication

Abstract

This work addresses the security and privacy issues in remote biometric authentication by proposing an efficient mechanism to verify the correctness of the outsourced computation in such protocols. In particular, we propose an efficient verifiable computation of XORing encrypted messages using an XOR linear message authentication code (MAC) and we employ the proposed scheme to build a biometric authentication protocol. The proposed authentication protocol is both secure and privacy-preserving against malicious (as opposed to honest-but-curious) adversaries. Specifically, the use of the verifiable computation scheme together with an homomorphic encryption protects the privacy of biometric templates against malicious adversaries. Furthermore, in order to achieve unlinkability of authentication attempts, while keeping a low communication overhead, we show how to apply Oblivious RAM and biohashing to our protocol. We also provide a proof of security for the proposed solution. Our simulation results show that the proposed authentication protocol is efficient.

1 Introduction

Following the rapid growth of mobile and cloud computing, outsourcing computations to the cloud has increasingly become more attractive. Many practical applications, however, require not only the privacy of the sensitive data in such computations, but also the verifiability of correctness of the outsourced computations. There has been a wealth of work on verifiable computations in recent years, see, e.g., [1–3] and the references therein. One type of outsourced computation, in biometric authentication with distributed entities, is the computation over encrypted bitstrings (e.g., encrypted biometric templates) to obtain the XOR of two bitstrings (e.g., the XOR of the fresh and reference biometric templates). Consider, for instance, the following biometric authentication protocol consisting of three entities, namely, a set $\mathcal {C}$ of clients $\mathcal {C}_i$, for $i=1,\cdots ,N$, one for each user $\mathcal {U}_i$, a cloud server $\mathcal {CS}$ with a database $\mathcal {DB}$, and an authentication server $\mathcal {SP}$. Each client $\mathcal {C}_i$ has a sensor that extracts biometric templates from its owner’s biometrics (e.g., fingerprints). The cloud server $\mathcal {CS}$ stores the reference biometric templates and performs calculations. The authentication server $\mathcal {SP}$ takes the final decision depending on whether there is a match between the fresh and the reference biometric templates. This is a reasonable model adopted in many research papers (cf. Related Work) and the industry (e.g., [4]) considering the fast rise of cloud computing and storage services, and also the widespread use of smartphones with embedded biometric sensors. However, the privacy of biometric features must be seriously taken into account in such architectures, since its disclosure may lead to breaches in security and traceability of users among services, besides the inherent private information disclosure.

Let us consider a simple example of a biometric authentication protocol using an homomorphic encryption scheme. Let $\textsf {HE}=(\textsf {KeyGen},\textsf {Enc},\textsf {Dec})$ be a hypothetical homomorphic encryption (HE) scheme and f a function such that $f\big (\textsf {Enc}(m),\textsf {Enc}(m')\big )=\textsf {Enc}\big (m\oplus m'\big )$, for $m,\,m'$ in the domain of $\textsf {Enc}$, where $\oplus$ is the XOR operation. Suppose that the encryption/decryption keys $\textsf {pk}/\textsf {sk}$ are generated by the authentication server $\mathcal {SP}$ and $\textsf {pk}$ is distributed to $\mathcal {CS}$ and all $\mathcal {C}_i$. Then, the protocol works as follows. During the enrollment phase, the client $\mathcal {C}_i$ provides an encrypted reference biometric template $\textsf {Enc}(b_i)$, along with the user $\textsf {ID}_i$ for storage in the database $\mathcal {DB}$ on the $\mathcal {CS}$ side. During the authentication phase, the client $\mathcal {C}_i$ provides an encrypted fresh biometric template $\textsf {Enc}(b'_i)$ and a claimed user $\textsf {ID}_i$ to $\mathcal {CS}$, which then retrieves $\textsf {Enc}(b_i)$ corresponding to $\textsf {ID}_i$ from its database, computes $\textsf {ct}_{b_i\oplus b_i'}=f\big (\textsf {Enc}(b_i),\textsf {Enc}(b'_i)\big )=\textsf {Enc}\big (b_i\oplus b'_i\big )$ and sends $\textsf {ct}_{b_i\oplus b_i'}$ to $\mathcal {SP}$. Finally, $\mathcal {SP}$ decrypts $\textsf {ct}_{b_i\oplus b_i'}$ and checks if the Hamming weight $\textsf {HW}(b_i\oplus b_i)\le \tau$, where $\tau$ is a predefined authentication threshold. If $\textsf {HW}(b_i\oplus b_i)\le \tau$, then the user is granted access; otherwise, he/she is rejected. Note that $\textsf {HW}(b_i\oplus b'_i)$ is equal to the Hamming distance $\textsf {HD}(b_i,b'_i)$.

At a first glance, the protocol may seem secure against a malicious $\mathcal {CS}$, with respect to both the fresh and the stored template privacy. However, this only holds under the assumption that $\mathcal {CS}$ honestly performs the intended calculation, since there is no mechanism in place to prevent or detect cheating. By computing a function, g, different than what the protocol specifies (or the intended function f but on different inputs than the legitimate ones), and using $\mathcal {SP}$ as an oracle, $\mathcal {CS}$ can learn information about either the stored reference biometric template $b_i$ or the fresh biometric template $b'_i$. As an example $\mathcal {CS}$ could compute $g(\textsf {Enc}(b_i),\textsf {Enc}(v))$, where v is a chosen vector by $\mathcal {CS}$, and subsequently send the result to $\mathcal {SP}$, which outputs $\textsf {Out}_\mathcal {SP}$. By mounting a variant of the hill climbing attack [5], performing multiple repeated attempts, each time carefully choosing v, the stored template $b_i$ can be retrieved. Such attacks against several protocols proposed in [6–8] are presented in [9–11]. Therefore, in similar applications it is important to verify the correctness of the outsourced computation, namely, the computation of XORing encrypted bitstrings. Moreover, verifiable computation of XOR is what we need in order to mitigate such an attack by a malicious $\mathcal {CS}$ on the above presented protocol. Here, we propose an efficient scheme for verifying the correctness of the outsourced XOR computation and apply it to biometric authentication. To our knowledge, the employment of verifiable computation in privacy-preserving biometric authentication has not been studied before, although the infeasibility of (fully) homomorphic encryption alone for privacy-preserving cloud computing is already known [12].

Contributions. In this work, we propose an efficient verifiable computation of XORing encrypted messages using an XOR linear message authentication code (MAC) and we build a biometric authentication protocol that is secure and privacy-preserving in the malicious (as opposed to the honest-but-curious) adversary model. In the proposed protocol, the use of homomorphic encryption (HE) and the XOR linear MAC scheme protects the privacy of biometric templates against the malicious cloud, while the secret identity to an index map provides anonymity. However, the authentication protocol does not hide access patterns from the cloud. This could be avoided using Private Information Retrieval, but at the expense of a large communication overhead. Hence we further propose an extension of the protocol using oblivious RAM (ORAM). Since $b_i\oplus b'_i$ is revealed to $\mathcal {SP}$ in the proposed protocol, we also discuss how to make it robust against leakage of information regarding the user’s biometric characteristics by employing biohashing techniques.

Related Work. Privacy-preserving biometric authentication has attracted considerable attention over the last decade. Multiple protocols for privacy-preserving biometric authentication are based on secure multi-party computation techniques including oblivious transfer [13] and homomorphic encryption [14, 15], as well as on private information retrieval [16, 17]. Bringer et al. [8] proposed a distributed biometric authentication protocol using the Goldwasser-Micali cryptosystem [15] to protect the privacy of the biometric templates against honest-but-curious (or passive) adversaries. Nevertheless, some attacks on this protocol were reported in [5, 11, 18]. In [11], the authors have also improved upon the Bringer et al. protocol to achieve security against malicious but non-colluding adversaries. Simoens et al. [5] also presented a framework for analysing the security and privacy-preserving properties of biometric authentication protocols. In particular, they showed how biometric authentication protocols designed to be secure against honest-but-curious adversaries can be broken in the presence of malicious insider adversaries. They described several attacks against protocols proposed in [8, 18, 19]. There are also other protocols for privacy-preserving biometric authentication that are based on additive HE [14, 20] such as [21] for face recognition and its subsequent improvement in [22], as well as the protocol in [23]. Yasuda et al. proposed two biometric authentication protocols using somewhat HEs based on ideal lattices [6] and ring learning with errors [7], and the security of these protocols is scrutinised in [9, 10]. In most of these schemes, biometric templates are extracted as bitstrings and the similarity of two biometric templates is measured by computing the Hamming distance between them. For this reason, in [24] the authors have proposed protocols for secure Hamming distance computation based on oblivious transfer. These have potential applications in privacy-preserving biometric authentication. Recently Bringer et al. [25] generalised their results for secure computation of other distances such as the Euclidean and the normalised Hamming distance. Oblivious transfer was also used in SCiFi [26].

Outline. The rest of the paper is organised as follows. Section 2 introduces the necessary background. Section 3 presents our adversary model. In Sect. 4, we present our protocol for biometric authentication employing the scheme for verifiable computation of XOR. Section 5 shows how ORAM can be applied to our protocol. Finally, Sect. 6 concludes the paper.

2 Preliminaries

Homomorphic Encryption. For our purposes, the employed HE scheme must be such that given $\textsf {Enc}(m)$ and $\textsf {Enc}(m')$, it is possible to homomorphically compute $\textsf {Enc}(\textsf {Dist}(m,m'))$, where $\textsf {Dist}$ is a distance metric. We require the HE scheme to have semantic security against chosen plaintext attacks. Consider the following game played between a probabilistic polynomial time (PPT) adversary and a challenger:

and define the adversary’s advantage in this game as $\textsf {Adv}_{\textsf {HE},\mathcal {A}}^\textsf {IND-CPA}(\lambda )=\big |2\Pr \big \{\textsf {Exp}_{\textsf {HE},\mathcal {A}}^\textsf {IND-CPA}(\lambda )=1\big \}-1\big |$.

Definition 1

We say that $\textsf {HE}$ is $\textsf {IND-CPA}$-secure if all $\textsf {PPT}$ adversaries have a negligible advantage in the above game: $\textsf {Adv}_{\textsf {HE},\mathcal {A}}^\textsf {IND-CPA}(\lambda )\le \textsf {negl}(\lambda ).$

Definition 2

A function $\textsf {negl}:\mathbb {N}\mapsto [0,1]$ is called negligible if for all positive polynomials $\textsf {poly}$ and sufficiently large $\lambda \in \mathbb {N}$: $\textsf {negl}(\lambda )<1/\textsf {poly}(\lambda )$.

Message Authentication Codes. A message authentication code (MAC) consists of $(\textsf {KeyGen},\textsf {TAG},\textsf {VRFY})$ (associated with a key space, a message space and a tag space). $\textsf {KeyGen}$, a key generation algorithm, takes a security parameter $\lambda$ as input and outputs a key $\textsf {k}$ (i.e., $\textsf {k}\leftarrow \textsf {KeyGen}(\lambda )$). $\textsf {TAG}$, a tag generation algorithm, takes a message m and a key $\textsf {k}$ as input, and outputs a tag (i.e., $t\leftarrow \textsf {TAG}(m,\textsf {k})$). $\textsf {VRFY}$, a verification algorithm, takes a message m, a tag t and a key $\textsf {k}$ as input, and outputs a decision $\textsf {Out}_\textsf {MAC}$ (i.e., $\textsf {Out}_\textsf {MAC}\leftarrow \textsf {VRFY}(m,t,\textsf {k})$), which is 1 if the message-tag pair (m, t) is valid, and 0 otherwise.

A typical construction of a MAC is via the use of Universal$_2$ (U$_2$) hash functions, see [27–29] for more on U$_2$ hash functions. There are constructions of U$_2$ hash functions that are $\oplus$-linear [30], from which one can construct an $\oplus$-linear MAC scheme. Note that a MAC scheme is called $\oplus$-linear if $\textsf {TAG}(m_1\oplus m_2,\textsf {k})=\textsf {TAG}(m_1,\textsf {k})\oplus \textsf {TAG}(m_2,\textsf {k})$.

Definition 3

A MAC is called $(Q_T,Q_V,t,\epsilon )$-secure (or simply $\epsilon$-secure) if no $\textsf {PPT}$ adversary $\mathcal {A}$ running in time at most t cannot generate a valid message-tag pair, even after making $Q_T$ tag generation queries to $\textsf {TAG}$ and $Q_V$ verification queries to $\textsf {VRFY}$, except with probability $\epsilon$.

Privacy-Preserving Biometric Authentication. A privacy-preserving biometric authentication (PPBA) protocol comprises:

• Setup: In this step, a trusted party runs the key generation algorithm $\textsf {KeyGen}$ for the employed cryptographic primitives (e.g., homomorphic encryption) using a security parameter $\lambda$ as input: $(\textsf {pk},\textsf {sk})\leftarrow \textsf {KeyGen}(\lambda )$. The keys are distributed to the relevant parties.

• $\textsf {Enroll}$: This process collects the encrypted reference biometric template $\textsf {Enc}(b_i)$ and stores it along with additional user information such as the user’s identity $\textsf {ID}_i$ in the database $\mathcal {DB}$, i.e., $\mathcal {DB}\leftarrow \textsf {Enroll}\big (\textsf {Enc}(b_i),\textsf {ID}_i\big )$.

• $\textsf {Authen}$: This process takes an encrypted fresh biometric template $\textsf {Enc}(b'_i)$ and a claimed identity $\textsf {ID}_i$, and involves actions from the protocol actors. This can be abstracted as $\textsf {Out}_\mathcal {SP}\leftarrow \textsf {Authen}(\textsf {Enc}(b'_i),\textsf {ID}_i)$.

The PPBA protocol is correct if the following definition is satisfied.

Definition 4

(Correctness). We say that a privacy-preserving biometric authentication protocol $\textsf {PPBA}$ is correct if, for all enrolled user identities $\textsf {ID}_i$ with the corresponding reference biometric templates $b_i$, and for all fresh biometric templates $b'_i$, $\textsf {Authen}(\textsf {Enc}(b'_i),\textsf {ID}_i)$ results in a successful authentication of the user with $\textsf {ID}_i$ if and only if $\textsf {Dist}(b_i,b'_i)\le \tau$.

We define the security of $\textsf {PPBA}$ against a malicious adversary $\mathcal {A}$ as follows. Consider the following game:

and define the adversary’s advantage in this game as $Adv_{\textsf {PPBA},\mathcal {A}}^\textsf {Priv}(\lambda )=\big |2\Pr \{\textsf {Exp}_{\textsf {PPBA},\mathcal {A}}^\textsf {Priv}(\lambda )=1\}-1\big |$.

Definition 5

(Security and privacy). We say that $\textsf {PPBA}$ is secure if, for all $\textsf {PPT}$ adversaries $\mathcal {A}$, $Adv_{\textsf {PPBA},\mathcal {A}}^\textsf {Priv}(\lambda )\le \textsf {negl}(\lambda ).$

We assume that the adversary is given an oracle access to $\textsf {Authen}$ and is allowed to query it polynomially many times, e.g., $\textsf {poly}(\lambda )$ times, where $\lambda$ may depend on the false acceptance rate. The adversary is also given $\textsf {Enc}(b'_{i_\beta })$. If the adversary cannot distinguish whether it is $(\textsf {ID}_i,b'_{i_0})$ or $(\textsf {ID}_i,b'_{i_1})$ that is being used by $\textsf {Authen}$, then we say that the protocol preserves privacy of the biometric templates.

3 Adversary Model

In this paper, we focus on malicious as opposed to honest-but-curious, adversaries and we consider a distributed setting, namely, each user $\mathcal {U}_i$ has his/her own client $\mathcal {C}_i$, a cloud computing server $\mathcal {CS}$ with its own database, and an authentication server $\mathcal {SP}$. The client $\mathcal {C}_i$ (e.g., a smartphone owned by the user $\mathcal {U}_i$) has a biometric sensor that extracts biometric templates from the user. By requiring that each user $\mathcal {U}_i$ has a client $\mathcal {C}_i$, potential damages can be minimised in case the client $\mathcal {C}_i$ is stolen or lost. We assume that each user trusts his/her own client device only to the extent that the biometric sensor and the extracted biometric template are only accessible by the authorised apps on the user device. This is the minimal reasonable assumption given the fact that most people nowadays have a smartphone with an embedded biometric sensor, and without such a trust, users cannot use their devices to remotely access services. This assumption has also to be made in any type of authentication using client devices, e.g., password- or token-based remote access. This assumption does not rule out the case where an adversary is using several clients $\mathcal {C}_i$, in collusion with the cloud server, to impersonate a user that is not the owner of compromised clients. However, we do note that if a client $\mathcal {C}_i$ is compromised, say, infected by malware, then the reference biometric template of the owner $\mathcal {U}_i$ can be recovered using the fresh biometric template provided by $\mathcal {U}_i$ by hill climbing attacks [31].

The authentication server $\mathcal {SP}$ handles the keys for the employed encryption scheme and is responsible for making the authentication decision based on the underlying matching process used. We also consider the authentication server $\mathcal {SP}$ as a trusted key managing entity which keeps the secret keys secure and performs its task honestly. However, we do not trust any biometric template to $\mathcal {SP}$. The malicious party that we want to have a full protection against is the cloud server $\mathcal {CS}$. In our case the cloud has a database that stores the encrypted reference biometric templates. Additionally, $\mathcal {CS}$ performs computations on the encrypted fresh and reference biometric templates. The results of the computation will allow the authentication server to make its decision. We consider a malicious cloud server as a $\textsf {PPT}$ adversary. We do not consider denial-of-service type of attacks, which are easy to mount by $\mathcal {CS}$, since it can always send a wrong response which would with high probability result in a false rejection.

Regarding communication among the protocol actors, we assume that the communication channel between the protocol entities is secure in order to avoid replay attacks. This can be achieved by using TLS or IPsec. We also only consider the case of a single client for each user, a single cloud server, and a single authentication server.

4 The Scheme and the Protocol

The main idea behind the verifiable computation of XOR is that the client stores homomorphically encrypted message-tag pairs (e.g., $\textsf {Enc}(m),\,\textsf {Enc}(t)$, where $t=\textsf {TAG}(m,\textsf {k})$) in the cloud server. When the client provides a new homomorphically encrypted message-tag pair (e.g., $\textsf {Enc}(m'),\,\textsf {Enc}(t')$, where $t'=\textsf {TAG}(m',\textsf {k})$), the cloud server computes the designated function on the encrypted messages and tags separately (e.g., $\textsf {ct}_{m\oplus m'}=f(\textsf {Enc}(m),\textsf {Enc}(m'))$ and $\textsf {ct}_{t\oplus t'}=f(\textsf {Enc}(t),\textsf {Enc}(t'))$), and returns the results to the client. The client decrypts the results and checks if the tag is valid (i.e., $m\oplus m'\leftarrow \textsf {Dec}(\textsf {ct}_{m\oplus m'})$, $t\oplus t'\leftarrow \textsf {Dec}(\textsf {ct}_{t\oplus t'})$, and $\textsf {VRFY}(m\oplus m', t\oplus t', \textsf {k})$). If the MAC verification is successful, then the client can be sure (up to the security of the MAC scheme) that the cloud server has performed the correct computation.

Below, we apply this simple method to build a privacy-preserving biometric authentication protocol. In the description, $\textsf {HE}$ is an encryption scheme which allows the computation of XOR of encrypted messages, i.e., $f(\textsf {Enc}(m),\textsf {Enc}(m')) = \textsf {Enc}(m\oplus m')$, and $\textsf {MAC}$ is an XOR linear MAC. The enrollment procedure $\textsf {Enroll}$ involves the following interactions:

It is important for security that the user enrollment is performed in a secure and controlled environment.

The authentication $\textsf {Authen}$ involves the following interactions:

From now on, we denote this protocol by PPBA-HE-MAC. It is straightforward to see that PPBA-HE-MAC is correct, since a legitimate user with his/her own legitimate device can always successfully authenticate himself/herself as long as the fresh biometric template matches the reference biometric template.

Security and Privacy Analysis. Intuitively, PPBA-HE-MAC is secure as long as the employed HE scheme is $\textsf {IND-CPA}$-secure (cf. Definition 1) and the MAC scheme is $\epsilon$-secure (cf. Definition 3). In any biometric template recovery attack that makes use of the side channel information (i.e., $\textsf {Out}_\mathcal {SP}$), $\mathcal {CS}$ needs to be able to submit to $\mathcal {SP}$ a $\textsf {ct}_{b_i\oplus b'_i}$ and $\textsf {ct}_{t_i\oplus t'_i}$ that encrypt a valid message-tag pair. The $\epsilon$-security of the employed MAC scheme does not allow this to happen. Furthermore, if $\textsf {Out}_\mathcal {SP}==\bot$, $\mathcal {CS}$ does not know whether it is due to the MAC verification failure or the mismatch between the fresh and the reference biometric template. Hence, the protocol is secure against the malicious $\mathcal {CS}$. The following summarises the security of our protocol, and the proof is given in Appendix-6.

Theorem 1 (Security and privacy)

. The protocol PPBA-HE-MAC is secure and privacy-preserving against the malicious $\mathcal {CS}$ according to our Definition 5, if the employed $\textsf {HE}$ is IND-CPA-secure and $\textsf {MAC}$ $\epsilon$-secure.

Simulation. PPBA-HE-MAC is efficient because both the MAC scheme and the HE scheme can be implemented efficiently. The efficiency of the $\oplus$-linear MAC scheme in our case depends on the efficiency of the employed U$_2$ hash functions. One suitable family of U$_2$ hash functions for our instantiation is the construction by Krawczyk [30], which exploits a Linear Feedback Shift Register to allow efficient hardware implementations. This construction is also efficient on software. We refer the curious reader to [32] for more on the software performance of U$_2$ hash functions.

Note that our utilisation of a lightweight MAC scheme for verifying the correctness of the outsourced computation contrasts nicely with the existing verifiable computation schemes. More precisely, efficiency is the main issue with the existing verifiable computation schemes since they are very heavy computationally and have a large overhead [33]. On the other hand, our approach using a MAC scheme is very efficient regarding computation cost.

Regarding the HE scheme, we demonstrate its efficiency by simulating the Goldwasser-Micali encryption scheme [15] for various security levels and biometric template lengths. The Goldwasser-Micali encryption scheme supports homomorphic evaluation of the $\textsf {XOR}$ operation, and their primitives are the most heavy ones in our construction.

The simulations were performed on a Intel®Core$^\mathrm{TM}$2 Duo CPU E8400 @ 3.00 GHz x2 64 bit CentOS Linux 7 computer. The simulation software, written in C++, linked the NTL v9.4.0 (Number Theory Library [34]), GNU Multiple Precision Arithmetic Library v6.0.0 [35], for efficient multiprecision arithmetics support. The security level and the corresponding size of the prime factors are chosen according to the ECRYPT II recommendations and the length of the biometric binary templates is chosen following Daugman [36] and SCiFI [26]. The simulation setup and results are shown in Table 1, the source code can be provided upon request via anonymous channels.

Table 1. Simulation setup and results for the Goldwasser-Micali scheme.

We remark that since our aim is to show the feasibility of the HE scheme, the implementation is not optimised. Also, the simulations are run on single core, even though the Goldwasser-Micali encryption and decryption procedures can be done in parallel, since it is a bitwise encryption scheme. Therefore, the simulation results show that the HE scheme required for our instantiation is not only feasible, but also efficient.

5 Protocol Extensions

Oblivious RAM (ORAM) for Hiding Access Patterns. Our protocol can be easily extended to protect the access pattern of the client $\mathcal {C}_i$ towards the cloud server $\mathcal {CS}$. However, existing methods such as Private Information Retrieval (PIR) come at an elevated communication overhead. To reduce such costs, we suggest the use of ORAM instead, as a more suitable mechanism, and its use, as presented by this work, would not alter the underlying security properties of the main protocol. ORAM allows a client to hide the entry as well as the access pattern from the server at a significantly reduced communication vs PIR. Moreover, ORAM security is derived from the indistinguishability of any two access patterns A(y) and $A(y')$, for any two respective queries y and $y'$. The concept was initially presented by Goldreich and Ostrovsky [37] in 1996. Since then, the field has seen the introduction of various protocols with improved mechanisms and primitives, e.g., [38]. These advances on protocol efficiency have motivated the apparition of new applications such as, biometric identification [39]. Typically, ORAMs are designed and used to solve the problem of $\mathcal {DB}$ outsourcing [40]. This model would require the user to execute various ORAM primitives so that the remote database is correctly shuffled. To alleviate this processing task, and to make our protocol user agnostic, we propose to use a Secure Multiparty Computation (MPC) scheme. MPC schemes have been suggested in combination with ORAM constructions in recent works (e.g., [41]). Under this extended protocol, every time a new user data (e.g., $\textsf {Enc}(b_i)$ and $\textsf {Enc}(t_i)$) is added to the ORAM $\mathcal {DB}$. The index i is used to store the data mapping in a separate ORAM. The following are the additional parties, operations and the protocol extension:

These protocol extensions are oriented towards a task distribution. Hence, they do not have an impact on the security properties of the authentication scheme. It is worth noticing, however, that the security with respect to the access pattern will depend solely on the underlying ORAM and MPC protocols used by any implementation.

Biohashing for Avoiding Linkability of Error Patterns. The error pattern $b_i \oplus b'_i$ is disclosed to $\mathcal {SP}$ at the end of the authentication phase, as shown in Sect. 4. This can disclose some information about the binary biometric templates. For instance, the reliability of each bit can be different among different users, so the error patterns can be used for tracking users. In the ideal case, all the error patterns should be equiprobable for all the users. In this case, disclosing the error patterns would not provide any advantage to $\mathcal {SP}$. However, this is difficult to achieve in practice.

A practical solution to this problem is to use biohashing techniques [43]. The usual approach for obtaining binary templates $b_i$ from biometric features $f_i$ is by using a user-independent binarization transformation $b_i = B(f_i)$. Biohashing consists of using a user-specific random transformation $b_i = B_i(f_i)$ instead. The specific design of these transformations ensures a minimum distortion in the distances in the transformed domain with respect to the distances in the original domain, thus keeping the discrimination ability of the biometrics unaffected. And the dependency between the error patterns and the user-specific binary templates’ reliability is avoided, since changing $B_i$ leads to an independent error pattern.

The incorporation of biohashing into our system is straightforward. The user-specific random transformation $B_i$ is generated during the enrollment phase in the user client $\mathcal {C}_i$, where it is stored and used to obtain the enrollment binary template $b_i = B_i(f_i)$. During the authentication phase, this transformation is used by $\mathcal {C}_i$ to obtain $b'_i = B_i(f'_i)$. When the user enrolls again, a new random transformation would be generated, thus avoiding linkability between the previous and the new error patterns.

6 Conclusions

We proposed an efficient scheme for verifiable computation of XORing encrypted messages, and successfully applied it to the scenario of distributed biometric authentication, where the storage of the encrypted biometric templates and part of the computations are outsourced to a cloud server. The security and privacy of the proposed scheme has been proved in a challenging and reasonable malicious internal adversarial scenario, as opposed to the more usual and less realistic honest-but-curious scenario. Additionally, ORAM is employed instead of prevalent PIR schemes to reduce the communication overhead while keeping the access pattern hidden from the cloud. Moreover, Biohashing techniques are proposed to avoid the disclosure of linkable error patterns. The efficiency of the proposed scheme has been assessed by simulating the most computationally costly parts of the proposed scheme, i.e. the homomorphic encryption primitives, showing the feasibility and efficiency of the proposed solution.

A    Proof of Theorem 1

Proof

Let $\varPi$ be the PPBA-HE-MAC protocol. The security of $\varPi$ against a malicious adversary $\mathcal {A}$ (i.e., $\mathcal {CS}$) is defined via the following game.

where $\textsf {MAC}.K$ is the key space for the employed MAC. The adversary’s advantage is defined as $\textsf {Adv}_{\varPi ,\mathcal {A}}^{\textsf {Priv}} = \big |2\Pr \{\textsf {Exp}_{\varPi ,\mathcal {A}}^\textsf {Priv}(\lambda ,\textsf {ID}_i)=1\} - 1\big |.$ If the advantage is $\le \textsf {negl}(\lambda )$, we say that $\varPi$ is secure (and preserves the privacy of biometric templates) against $\mathcal {A}$.

The details of $\textsf {Authen}\big (\textsf {ID}_i,\textsf {Enc}(b'_{i_\beta }),\textsf {Enc}(t'_{i_\beta })\big )$ are given below.

The proof is based on the following two hybrid games.

$\mathbf{game}~0$ : This is the original game. Let $S_0$ be the event that $\beta '=\beta$.

$\mathbf{game}~1$ : This is the same as $\mathbf{game}~0$, except that now $\mathcal {CS}$ always performs the correct computation. Let $S_1$ be the event that $\beta '=\beta$ in $\mathbf{game}~1$.

Since providing a different index $i'$ than the correct one i always results in $\bot$ output, it does not help the adversary (i.e., the cloud) to win any of the games. So we assume that $\mathcal {CS}$ always provides the correct index i.

Claim 1: $|\Pr \{S_0\}-\Pr \{S_1\}|$ is negligible. This follows from the $\epsilon$-security of the MAC scheme. Precisely, the difference between the two games is that in game 0, $\textsf {VRFY}(b_i\oplus b'_{i_\beta }, t_i\oplus t'_{i_\beta },\textsf {k}_i)==0$ if $\mathcal {CS}$ does not perform the computation correctly, except for probability $\epsilon$, while in game 1, that does not happen as it performs the computation correctly. So the difference between the winning probabilities in game 0 and game 1 is negligible.

Claim 2: The adversary has negligible advantage in $\mathbf{game}~1$, i.e., $\big |2\Pr \{S_1\}-1\big |\le \textsf {negl}(\lambda )$. This follows from the $\textsf {IND-CPA}$-security of the employed HE scheme. Since otherwise, we can use the adversary $\mathcal {A}$ as a blackbox to construct another PPT adversary $\mathcal {A}'$ that can win the $\textsf {IND-CPA}$ game against the HE scheme with non-negligible probability in a straightforward fashion. More precisely, the adversary $\mathcal {A}'$ can use the challenge ciphertext in the $\textsf {IND-CPA}$ game to simulate the $\varPi$ for $\mathcal {A}$, and use $\mathcal {A}$’s guess to win the $\textsf {IND-CPA}$ game against the HE scheme. Hence, combining the two claims, we have that $\textsf {Adv}_{\varPi ,\mathcal {A}}^{\textsf {Priv}}$ is negligible.