A new framework for privacy-preserving biometric-based remote user authentication

Abstract

In this paper, we introduce the first general framework for strong privacy-preserving biometric-based remote user authentication based on oblivious RAM (ORAM) protocol and computational fuzzy extractors. We define formal security models for the general framework, and we prove that it can achieve user authenticity and strong privacy. In particular, the general framework ensures that: (1) a strong privacy and a log-linear time-complexity are achieved by using a new tree-based ORAM protocol; (2) a constant bandwidth cost is achieved by exploiting computational fuzzy extractors in the challenge-response phase of remote user authentications.

Keywords

Remote user authentication oblivious RAM computational fuzzy extractors strong privacy constant bandwidth

1. Introduction

Privacy-Preserving Biometric-based Remote User Authentication (BRUA) allows an authorized user to anonymously authenticate herself to a remote authentication server using her biometrics. In the literature, BRUA with biometrics privacy has been intensively studied [4,8,9,20,23,28]. Biometrics privacy means that no biometrics should be stored in plaintext at server side, this is because a user may lose its security forever if her secret biometrics is leaked to the authentication server or any outsiders. However, we discover that none of existing schemes ever consider non-biometrics privacy, including identity privacy and access privacy.

Identity privacy and access privacy are essential in the remote user authentication setting. A remote user authentication, that does not achieve identity privacy and access privacy, may leak sensitive information about a user to the authentication server or any outsiders. Let us consider a real-world application: mobile health (mHealth), where patients wish to obtain healthcare information after being authenticated by an authentication server through mobile devices. We assume an authentication server maintains a database of records and each record contains a patient’s “encrypted” biometrics. We also assume that the authentication server must access a patient’s record to authenticate the patient. Identity privacy can ensure that a patient logs in to mHealth system without disclosing her real identity to the authentication server.

We note that the previously mentioned login does not guarantee access privacy. Access privacy means that the authentication server cannot determine which record is being accessed at any time. If the same record is accessed twice, then the authentication server can easily link two accesses made by the same anonymous patient [25,30]. As a result, the authentication server can learn a patient’s sensitive information such as interaction history and login behaviour, and disclose it to third parties afterwards [24]. In contrast, access privacy aims to prevent the authentication server from obtaining such sensitive information.

The practicality of a remote user authentication system (e.g., mHealth) is evaluated by time-complexity and bandwidth cost. First, the time-complexity means that the amount of time it takes for the authentication server to authenticate a user. Second, the bandwidth cost means the number of records transferred between the authentication server and a user in order to authenticate the user. To analyze the bandwidth cost in detail, we assume a remote user authentication includes three phases: early-reshuffle, challenge-response and post-reshuffle. Both early-reshuffle and post-reshuffle allow a patient to reshuffle and re-randomize a set of records in the database, so multiple logins by the same anonymous patient are unlinkable by the authentication server. In the challenge-response phase, a patient proves her authenticity to the authentication server by generating digital signatures based on any messages (e.g., nonces) and transferred records.

In this work, we present the first general framework of biometrics-based remote user authentication that satisfies strong privacy, including biometrics privacy, identity privacy and access privacy, while the time-complexity is log-linear in the number of enrolled users, and the communication bandwidth in the challenge-response phase is constant. We call our framework pBRUA for convenience.

Overview of Techniques. We now explain our key technical insights. First, biometrics privacy and identity privacy can be achieved using the existing techniques such as computational fuzzy extractors [2,21,43] (note that fuzzy extractors are used to convert repeated noisy readings of a secret into the same key of uniform distribution [16]) and anonymous digital signatures [10,44]. Second, for achieving access privacy, to the best of our knowledge, there is no existing solution that can be directly applied to construct pBRUA.1

¹
It is possible to use other alternative solutions to achieve access privacy such as private information retrieval [11] and shuffle index [14], while the ORAM based solution may achieve lower bandwidth complexity.

We shall show that some existing tree-based ORAM protocols can be used to construct BRUA with log-linear time-complexity (see Appendix). However, they cannot achieve constant bandwidth cost in the challenge-response phase. Therefore, we propose a new tree-based ORAM (uORAM) protocol (see Fig. 1). The uORAM not only supports a log-linear time-complexity in the number of records (including all enrolled users’ real records and many dummy records) due to the structure of a binary tree, but also achieves a constant bandwidth in the challenge-response phase.

Fig. 1.

uORAM in a multiple-user and single-server setting. The individual user stores a small amount of local data in a stash. The server-side storage is treated as a binary tree where each node is a bucket that can hold up to a fixed number of records. If the black record is mapped to the shaded path, then the record must reside in any slot along the path or in the stash.

Our Novel Technique. In pBRUA, a user first reshuffles and re-randomizes a set of records in a tree path in the early-reshuffle phase, which includes a real record (which contains the user’s “encrypted” biometrics) and many dummy records (which contains “encrypted” zeros). The user is required to replace the “encrypted” zeros in the dummy records with secret randomness chosen by the user. In the challenge-response phase, the authentication server “aggregates” the records in the tree path specified by the user and sends the “aggregated” record to the user. Then, the user obtains a cryptographic key from the “aggregated” record using her biometrics and the chosen secret randomness. Such cryptographic key is used to generate a signing/verification key pair to prove her authenticity. In particular, we use the Schnorr signature scheme [36]. This is because the cryptographic key is re-randomized by the user in the early-reshuffles phase. As a result, the Schnorr signature generated by the derived signing key in the challenge-response phase can achieve both user authenticity and constant bandwidth. We stress that we do not use the previously mentioned anonymous digital signatures, which essentially compromise the constant bandwidth, because the number of verification keys transferred between user and server for verifying anonymous signatures has the log-linear time-complexity in the number of records.

Our Contributions. The major contributions of this work are summarized as follows.

General Framework. We propose the first general framework pBRUA using learning with errors (LWE) computational fuzzy extractors [2,21,43], digital signatures [31,41] and a uORAM protocol. The proposed pBRUA achieves the strong privacy, log-linear time-complexity and constant bandwidth in the challenge-response phase. We prove that the proposed pBRUA can achieve user authenticity and strong privacy under standard assumptions.

New ORAM. We propose a new tree-based ORAM (uORAM) for remote user authentications in a multi-user setting, which is built on top of Path ORAM [40] and Ring ORAM [34] (a variant of Path ORAM). The proposed uORAM is proven secure under a variant of standard ORAM security definition [22].

Constant Bandwidth. We show the proposed uORAM (and pBRUA as well) can achieve the constant bandwidth. Constant bandwidth in this work means that the authentication server transfers a single record to an authorized user in the challenge-response phase.

We highlight our contributions in Table 1. We can see that the pBRUA is achieved by proposing a uORAM and exploiting the LWE-based fuzzy extractor (FE) altogether. We remark that the new uORAM protocol can be regarded as an independent cryptographic primitive, if one does not consider the constant bandwidth in the challenge-response (CR) phase.

Table 1

N is the total number of records, Z (e.g., $Z = 4$ ) is the number of real records per bucket (more details are referred to Section 3) and $Z^{*}$ (e.g., $Z^{*} = 3$ ) is a smaller number than Z which means an improved overall bandwidth in Ring ORAM

Criteria/Construction	Path	Ring	uORAM	uORAM + FE
Overall bandwidth	$2 Z \cdot log N$	$Z^{*} \cdot log N$	$2 Z \cdot log N$	$2 Z \cdot log N$
CR bandwidth	$Z \cdot log N$	$log N$	$log N$	$1$

1.1. Related work

ORAM. Oblivious RAM was introduced by Goldreich and Ostrovsky [22] (GO-ORAM), that allows a client to conceal her access pattern as seen by the untrusted storage server. They have proposed two ORAMs: Square-root ORAM and Hierarchical ORAM. The main drawback is: the worst-case cost on bandwidth is linear in the total number of records (or blocks) N. The bandwidth is to measure the amount of communication cost between client and server to serve a client request. For example, the Hierarchical ORAM is with $O (N \cdot {log}^{2} N)$ (i.e., poly-logarithmic) complexity, so it hinders its practicality in realistic settings. To reduce the worst-case cost, Shi et al. [37] proposed the tree-based ORAM which manages the ORAM storage into a binary tree, so that achieving the worst-case bandwidth with $O ({log}^{3} N)$ complexity.

To further reduce the bandwidth cost while keeping a small client storage, Stefanov et al [40] proposed the Path ORAM with $O (log N)$ bandwidth complexity. The Path ORAM is extremely simple – just 16 lines of pseudocode. Each access can be expressed a fetching and storing a path in the tree stored remotely on the server. However, the overall bandwidth is too high because the server has to pass all blocks in a tree path to client, and the overall bandwidth of Path ORAM depends on the bucket size. To remove such dependence, Ren et al. proposed the Ring ORAM [34] such that fetching one block per bucket in a tree path. Moreover, the Ring ORAM can achieve the $O (1)$ on-line bandwidth efficiency by applying the XOR technique [13], which means that returning a single block back to serve a user request. This is important because the on-line bandwidth determines the response time to serve a user request. We note that the Evict operation (see Section 3) in the Ring ORAM is NOT suitable for user authentications because it does not execute on every user request. By contrast, the requested user should push blocks back to ORAM tree after a valid authentication because multiple users share the same ORAM tree.

For achieving the $O (1)$ on-line bandwidth efficiency, the untrusted server is allowed to perform matrix multiplication on some blocks (e.g., SSS ORAM [39]) or XOR operation (e.g., Burst ORAM [13] and Ring ORAM [34]). In particular, the Onion ORAM [15] can achieve a constant worst-case bandwidth blowup by allowing the untrusted server to perform the (additive/somewhat) homomorphic encryption on the involved blocks. The bandwidth blowup means the number of blocks transmitted between client and server to serve a client request. For example, Circuit ORAM [42] incurs a $O (log N)$ lower bound in bandwidth blowup, while Onion ORAM has a $O (1)$ bandwidth blowup.

A separate line of research on ORAM is to handle the asynchronous user requests at multi-user setting [6,38], Sahin et al. [35] introduced a new ORAM: Taostore, which relies on a trusted proxy who acts as a middle layer between multiple users and an untrusted server (i.e., “hybrid cloud” model [38]). Meanwhile, many practical ORAMs have been implemented for real-world applications, like secure processors [29,40], secure storage systems [13,38,39] and secure multi-party computations [17,42].

Comparison with Existing ORAMs. First, we notice that some existing tree-based ORAMs can be directly used to construct BRUA with log-linear time-complexity (e.g., the Path ORAM described in Appendix). Then, we compare our uORAM with some existing tree-based ORAMs in Table 2. Our uORAM protocol is unique in design: (1) the authentication server generates certain number of dummy records for padding each bucket during enrollment, in which the dummy records are common resources shared by all enrolled users; (2) an enrolled user maintains her access privacy during authentication, which is usually executed in a short time period; (3) multiple users store their individual key materials securely and maintain stash independently. Our designed uORAM works at non-standard model, secures against an honest-but-curious (or semi-honest) server. It has two round trips in total, and a single server coordinates the authentication requests from multiple users in sequence. We note that the proposed uORAM can store a generic data as required in the existing ORAMs. In this work, we use the LWE-based fuzzy extractor to store biometrics with a specific format, so as to achieve a constant bandwidth for user authentication. If the constant bandwidth is not required in the design goal, then many fuzzy extractors in the literature could be suitable for uORAM which can handle various types of biometrics.

Table 2
The overall comparison between our uORAM and some tree-based ORAMs. Bandwidth means on-line bandwidth complexity. Standard means no server computation, non-standard means server can perform certain computation such as XOR. “1” round trip means the $O (log N)$ bandwidth complexity when processing the buckets in parallel. Multi-user means that whether a single ORAM contains the blocks from multiple clients. Asynchronicity means whether server handles multiple client requests asynchronously. Security means whether the untrusted server is semi-honest (SH) or malicious (M). In Ring [34], it achieves $O (1)$ on-line bandwidth complexity using the XOR technique. In Taostore [35], the total number of round-trips depends on the number of asynchronous client requests (here we denote it as N/A). In uORAM, the on-line bandwidth complexity $O (1)$ covers the challenge-response phase of user authentications

Criteria/ORAM Tree [37] Path [40] Ring [34] Onion [15] Taostore [35] Ours

Bandwidth $O ({log}^{3} N)$ $O (log N)$ $O (1)$ $O (1)$ $O (log N)$ $O (1)$

Standard ✓ ✓ × × ✓ ×

Roundtrips 1 1 2 1 N/A 2

Multi-user × × × × ✓ ✓

Asynchronicity × × × × ✓ ×

Security N/A N/A SH SH/M SH SH

Criteria/ORAM	Tree [37]	Path [40]	Ring [34]	Onion [15]	Taostore [35]	Ours
Bandwidth	$O ({log}^{3} N)$	$O (log N)$	$O (1)$	$O (1)$	$O (log N)$	$O (1)$
Standard	✓	✓	×	×	✓	×
Roundtrips	1	1	2	1	N/A	2
Multi-user	×	×	×	×	✓	✓
Asynchronicity	×	×	×	×	✓	×
Security	N/A	N/A	SH	SH/M	SH	SH

Fuzzy Extractor. Fuzzy extractor (FE) is one of the promising approaches to construct a biometric-based user authentication [8,9,28]. Juels and Wattenberg [26] introduced a cryptography primitive called “fuzzy commitment”. It can be used in the biometric-based authentication systems, because its error-correcting technique can correct certain errors within a suitable metric (e.g., Hamming distance). Dodis et al. [16] formally introduced the notions of “secure sketches” (the sketches are used to recover the original biometrics from a nearby biometrics) and “fuzzy extractors”. In particular, they provided concrete constructions of secure sketches and FEs in three metrics (Hamming distance, set difference and edit distance), and the constructions are information-theoretically secure.

Fuller et al. [21] introduced the first computationally-secure FE from LWE [33] such that the derived cryptographic key equals to the entropy2

To obtain sufficient entropy at one time, a sensor that captures multiple biometrics (e.g., fingerprint and fingervein) has been developed [32], but we do not survey on this research direction since it is beyond the scope of this work.

of the fuzzy biometrics. However, their computational FE is not reusable. Reusability [8] means that a user can produce multiple key and sketch pairs using the same biometrics w (i.e.,

{(s_{i}, p_{i})} \leftarrow Gen (w)

). To achieve a reusable FE from LWE, Apon et al. [2] provided a general method to convert non-reusable (resp. weakly reusable) computational fuzzy extractors to weakly reusable (resp. strongly reusable) ones. The strongly reusable FE allows an attacker to obtain the secret key string

s_{i}

, in addition to the public sketch

p_{i}

. We notice that the weakly reusable FE will suffice for privacy-preserving remote user authentications in this work, and we can achieve the strongly reusability by using the general method proposed in [2] when considering multiple authentication servers. In addition, we present the commonly used notations in Table 3.

Table 3

Summary of notations

Notation	Meaning
$n / N$	Total number of users/records (blocks)
$L = log N$	Height of the binary tree $T$
$ID / {leaf}_{ID}$	Block/leaf identifier
$Z / S / S$	Real block/dummy block/Stash
${pk}_{i} / {sk}_{i}$	User i public/secret key pair
$dist (x, y)$	Distance between vector x and vector y
$t \in R^{+}$	Threshold value (positive real number)
$w / w^{'}$	Enrolled biometrics/noised biometrics
$SS (s, w)$	Secure sketch with a secret string s
$P ({leaf}_{ID})$	Tree path from leaf node ${leaf}_{ID}$ to the root
$P ({leaf}_{ID}, ℓ)$	The bucket at level ℓ along the tree path $P ({leaf}_{ID})$
$position$	User’s local position map
${leaf}_{ID} = position (ID)$	Block $ID$ resides somewhere along the path $P ({leaf}_{ID})$

1.2. Paper organization

In the next section, we present some preliminaries which will be used in our proposed construction. In Section 3, we present our uORAM protocol and its security analysis. We then present our general framework of pBRUA in Section 4 and formally prove its security in Section 5. The paper is concluded in Section 6.

2. Preliminaries

In this section, we present the digital signatures with homomorphic property, a family of universal hash functions and fuzzy extractors from LWE, which will be used in our proposed general framework.

2.1. Complexity assumptions

Definition 2.1 (Decisional LWE [33]).

Given a random matrix $A \in Z_{q}^{m_{0} \times n_{0}}$ , $X \in Z_{q}^{n_{0}}$ and χ be an arbitrary distribution on $Z_{q}^{m_{0}}$ , the decisional LWE ( ${D-LWE}_{q, n_{0}, m_{0}, χ}$ ) problem is to distinguish the distribution $(A, A \cdot X + χ)$ from a random distribution over $(Z_{q}^{m_{0} \times n_{0}}, Z_{q}^{m_{0}})$ . We say that ${D-LWE}_{q, n_{0}, m_{0}, χ}$ is ( $ϵ, s_{\sec}$ ) secure if no PPT distinguisher $D_{s_{\sec}}$ of size $s_{\sec}$ can distinguish the LWE instances from uniform except with probability ϵ, where $s_{\sec} = poly (λ)$ and ϵ is a negligible function of the security parameter λ.

Dottling and Muller-Quade [18] showed that one can encode biometrics w as the error term in a LWE problem by splitting it into $m_{0}$ blocks. Furthermore, to extract the pseudorandom bits, we rely on the result from Akavia et al. [1] such that $X \in Z_{q}^{n_{0}}$ has simultaneously many hardcore bits.

Lemma 2.1.
If ${D-LWE}_{q, n_{0} - k, m_{0}, χ}$ is ( $ϵ, s_{\sec}$ ) secure, then $\begin{matrix} δ^{D_{s_{\sec}^{'}}} ((X_{1, \dots, k}, A, A \cdot X + χ), (U, A, A \cdot X + χ)) ⩽ ϵ, \end{matrix}$ where $U \in Z_{q}^{k}$ and $X_{1, \dots, k}$ denotes the first k coordinates of x and $s_{\sec}^{'} \approx s_{\sec} - n_{0}^{3}$ .

2.2. Digital signatures

We say a digital signature scheme $Σ = (Setup, KG, Sign, Verify)$ is homomorphic, if the following conditions are held.

Simple Key Generation. $(sk, pk) \leftarrow Σ . KG (p p)$ and $p p \leftarrow Σ . Setup (λ)$ , where $pk$ is derived from $sk$ via a deterministic algorithm $pk \leftarrow {KG}^{'} (p p, sk)$ .

Linearity of Keys. ${KG}^{'} (p p, sk + Δ (sk)) = M_{pk} (p p, {KG}^{'} (p p, sk), Δ (sk))$ , where $M_{pk}$ denotes a deterministic algorithm which takes $p p$ , a public key $pk$ and a “shifted” value $Δ (sk)$ , outputs the “shifted” public key ${pk}^{'}$ .

Linearity of Signatures. Two distributions are identical: ${σ^{'} \leftarrow Σ . Sign (p p, sk + Δ (sk), m)}$ and ${σ^{'} \leftarrow M_{Σ} (p p, pk, m, σ, Δ (sk))}$ , where $σ \leftarrow Σ . Sign (p p, sk, m)$ and $M_{Σ}$ denotes a deterministic algorithm which takes $p p$ , a public key $pk$ , a message-signature pair $(m, σ)$ and a “shifted” value $Δ (sk)$ , outputs the “shifted” signature $σ^{'}$ .

Linearity of Verifications. We require that $Σ . Verify (p p, M_{pk} (p p, pk, Δ (sk)), m, M_{Σ} (p p, pk, m, σ, Δ (sk))) = “1”$ , and $Σ . Verify (p p, pk, m, σ) = “1”$ .

Matsuda et al. [31] showed that the Schnorr signature scheme [36] satisfies the homomorphic properties regarding keys and signatures (see Lemma 2 in [31]).

2.3. Universal hash function

Let $H$ be a universal hash function family whose domain is $Z_{q^{n_{0}}}$ and whose range is $Z_{q}$ . Let $Z_{q^{n_{0}}}$ be a vector space, which consists of $n_{0}$ dimensional of finite ring with prime order q. We define an isomorphism $ψ : {(Z_{q})}^{n_{0}} \to Z_{q^{n_{0}}}$ ( $ψ^{- 1}$ is its inverse), and $n_{0} \in N$ . Note that ${(Z_{q})}^{n_{0}} = Z_{q}^{n_{0}}$ . A family of universal hash functions is defined as $H = {H_{z} : Z_{q}^{n_{0}} \to Z_{q} | z \in Z_{q^{n_{0}}}}$ . Specifically, for each invertible element $z \in Z$ in the seed space $Z \in Z_{q^{n_{0}}}$ , define the hash function $H_{z}$ as follows: on input $x \in {(Z_{q})}^{n_{0}}$ , $H_{z} (x)$ computes $y \leftarrow ψ (x) \cdot z$ , where “·” denotes the multiplication in the extension field $Z_{q^{n_{0}}}$ . Let $(y_{1}, \dots, y_{n_{0}}) \leftarrow ψ^{- 1} (y)$ , and the output of $H_{z} (x)$ is $y_{1} \in Z_{q}$ . Since the isomorphism ψ between $Z_{q}^{n_{0}}$ and $Z_{q}^{n_{0}}$ is applied to the universal hash function family, we can easily get the desired linearity below $\begin{matrix} \forall x, x^{'} \in {(Z_{q})}^{n_{0}} and y_{1}, y_{2} \in Z_{q} : y_{1} \cdot H_{z} (x) + y_{2} \cdot H_{z} (x^{'}) = H_{z} (y_{1} \cdot x + y_{2} \cdot x^{'}) . \end{matrix}$

Lemma 2.2.
Assume a family of functions ${H_{z} : Z_{q}^{n_{0}} \to Z_{q}}_{z \in Z}$ is universal, for any random variable W taking values in $Z_{q}^{n_{0}}$ and any random variable Y, $\begin{matrix} SD ((U_{Z}, \underline{H_{z} (W)}, Y), (U_{Z}, \underline{U}, Y)) ⩽ \frac{1}{2} \sqrt{2^{- {\tilde{H}}_{\infty} (W | Y)} \cdot | Z_{q} |}, \end{matrix}$ where $U_{Z}$ and U are uniformly distributed over $Z_{q^{n_{0}}}$ and $Z_{q}$ respectively. In particular, such universal hash functions are (average-case, strong) extractors with ϵ-statistically close to uniform. The detailed description of (average) mini-entropy ${\tilde{H}}_{\infty}$ and statistical distance $SD$ can be found in [ 16 ].

2.4. Fuzzy extractors

Let $m_{0} ⩾ n_{0}$ and q be a prime number, define two algorithms Gen, Rep of computational FE [21] below.

Input: $w \leftarrow M$ . ⊳ suppose $M$ is a uniform distribution over $Z_{q}^{m_{0}}$ .

Sample $A \in Z_{q}^{m_{0} \times n_{0}}$ , $x \in Z_{q}^{n_{0}}$ uniformly.

Compute $p = (A, A \cdot x + w), s = x_{1, \dots, n_{0} / 2}$ .

Output: $(s, p)$ .

Input: $w^{'}, p$ . ⊳ where Hamming distance between $w^{'}$ and w is at most t.

Parse p as ( $A, c$ ); let $b = c - w^{'}$ .

Let $x = {Decode}_{t} (A, b)$ .

Output: $s = x_{1, \dots, n_{0} / 2}$ .

Note that p denotes the public helper string, and s denotes the secret string. The correctness of computational FE relies on the

{Decode}_{t} (A, b)

algorithm [21], which is explicitly shown as follows.

Input: $(A, b = A \cdot x + w - w^{'})$ .

Select $2 n_{0}$ distinct indices $i_{1}, \dots, i_{2 n_{0}} \leftarrow {1, \dots, m_{0}}$ .

Restrict $A, b$ to rows $i_{1}, \dots, i_{2 n_{0}}$ ; Denote these by $A_{i_{1}}, \dots, A_{i_{2 n_{0}}}, b_{1}, \dots, b_{i_{2 n_{0}}}$ .

Find $n_{0}$ linearly independent rows of $A_{i_{1}}, \dots, A_{i_{2 n_{0}}}$ (if no such rows exist, output abort and stop), and restrict $A_{i_{1}}, \dots, A_{i_{2 n_{0}}}, b_{i_{1}}, \dots, b_{i_{2 n_{0}}}$ to $n_{0}$ rows. Denote the result by $A^{'}, b^{'}$ .

Compute $x^{'} = A^{^{'} - 1} \cdot b^{'}$ .

If $b - A \cdot x^{'}$ has at most t non-zero coordinates, then outputs $x^{'}$ ; Otherwise, it returns to step 2.

Recall that $A \in Z_{q}^{m_{0} \times n_{0}}, b \in Z_{q}^{m_{0}}$ , and ${Decode}_{t}$ algorithm can correct at most $t = O (log n_{0})$ errors (of Hamming distance) in a random linear code. Also note that with probability at least $1 / poly (λ)$ , none of the $2 n_{0}$ rows selected in step 2 have errors (i.e., nearby biometrics w and $w^{'}$ agree on these rows), thus $x^{'}$ is a solution to the linear system. Furthermore, we notice that the sketch from LWE satisfies the linearity defined in [31,41]. That is, $\begin{matrix} SS (w, x + Δ (x)) = A \cdot (x + Δ (x)) + w = (A \cdot x + w) + A \cdot Δ (x), \end{matrix}$ where $SS$ denotes a secure sketch procedure [21], which takes $w \leftarrow M$ and a value $x \in Z_{q}^{n_{0}}$ as input, output a distribution over $Z_{q}^{m_{0}}$ . The sketch from LWE is in the form of $SS (w, x) = A \cdot x + w$ .

The computational fuzzy extractors (FE) from LWE has an inherent property: “indistinguishability”. Informally, given two sketches (part of helper data) with respect to two independent biometrics, adversary cannot distinguish them without having decryption keys. We formally prove that the computational FE from LWE is secure in the IND model (note that the adversary here is allowed to access the sketch only). In addition, we discover that both computational FE [21] and its variant reusable FEs [2,43] have such inherent property.

Definition 2.2.
The IND experiment between an adversary $A$ and a challenger $C$ is defined below. $\begin{matrix} Experiment {Exp}_{F E}^{IND} (λ) \\ b \in {0, 1}, w \leftarrow M, Q = \emptyset \\ (r_{i}, p_{i}) \leftarrow Gen (w_{b}) \\ Q \leftarrow Q \cup p_{i} \\ return p_{i} \\ b^{'} = A (guess, c^{}), c^{} \leftarrow p_{b} \\ Return 1, i f b^{'} = b \land p_{b} \notin Q; else, return 0 . \end{matrix}$ In the guess stage, $A$ is given a challenge sketch $c^{}$ , which was not previously simulated by $C$ . We define the advantage of $A$ as $\begin{matrix} {Adv}_{A}^{IND} (λ) = | \Pr [C \to 1] - 1 / 2 | . \end{matrix}$ A computational FE from LWE is said to be IND secure if ${Adv}_{A}^{IND} (λ)$ is negligible in λ for any PPT $A$ .
Lemma 2.3.
The computational fuzzy extractors from LWE achieves the IND security if the* ${D-LWE}_{q, n_{0}, m_{0}, χ}$ assumption is $(ϵ, s_{\sec})$ secure.

Informally, we can think of the sketch $A \cdot x + w$ (part of helper data p) as an “encryption” of x that where decryption works from any close $w^{'}$ (i.e., decryption key). Furthermore, we can also think of any two sketches $A_{0} \cdot x_{0} + w_{0}$ and $A_{1} \cdot x_{1} + w_{1}$ (in a multi-user setting, we set $A_{0} = A_{1}$ which is shared among all users) are indistinguishable by any third parties without having decryption keys $(w_{0}^{'}, w_{1}^{'})$ .
Proof.
Assume that there exists a PPT $A$ breaking the IND security of the computational fuzzy extractors from LWE, then we can construct an algorithm $C$ to break the decisional LWE ( ${D-LWE}_{q, n_{0}, m_{0}, χ}$ ) assumption. The algorithm $C$ has almost the same time complexity with $A$ . For simplicity, we consider the shared public parameter by all users such that $A_{0} = A_{1}$ .

Fig. 2.
Description of adversary $C$ for the proof.

The algorithm $C$ uses $A$ as a subroutine (see Fig. 2, note that v can be either $A \cdot X + χ$ or a random distribution). $C$ first generates another distribution which has the same property and distribution as its own challenge distribution. That is, computed distribution ( $A, A \cdot (X + u) + χ + w$ ), where u and w are randomly chosen by $C$ . If $C$ ’s challenge is a real distribution, then it is the computed distribution; Otherwise, it is a random distribution over $(Z_{q}^{m_{0} \times n_{0}}, Z_{q}^{m_{0}})$ . By using its challenge and computed distribution, $C$ can simulate two sketches $(p_{0}, p_{1})$ for $A$ . At guess stage, $C$ returns a challenge ciphertext $c^{}$ to $A$ according to the bit b.

We then analyze the behaviour of $C$ on ${Exp}_{C}^{LWE-REAL}$ and ${Exp}_{C}^{LWE-RAND}$ respectively. In the ${Exp}_{C}^{LWE-REAL}$ , the input ( $A, A \cdot X + χ + w$ ) satisfies the Rep algorithm of FE described in Section 2.4. Notice that the computed distribution ( $A, A \cdot (X + u) + χ + w$ ) is also valid and they are uniformly and independently distributed over $(Z_{q}^{m_{0} \times n_{0}}, Z_{q}^{m})$ , because $A \cdot (X + u) + χ + w = A \cdot X + χ + A \cdot u + w$ and u is a randomly element in $Z_{q}^{n_{0}}$ . Thus, $C$ can simulate the proper distribution of two challenge sketches (i.e., $p_{0} \leftarrow A \cdot X + χ + w_{0}$ and $p_{1} \leftarrow A \cdot (X + u) + χ + w_{1}$ ), and the challenge ciphertext $c^{}$ is distributed exactly like a real sketch which associates with $w_{b}$ . $\begin{array}{l} c_{0} \leftarrow A \cdot X + χ + w_{0} . ⊳ if b = 0, \\ c_{1} \leftarrow A \cdot (X + u) + χ + w_{1} . ⊳ otherwise . \end{array}$

Therefore, we have ${Exp}_{C}^{LWE-REAL}$ below, which includes the experiment with respect to $b = 1$ (i.e., IND-1) and $b = 0$ (i.e., IND-0). $\begin{array}{rcl} \Pr [{Exp}_{C}^{LWE-REAL} (λ) = 1] & = & 1 / 2 \cdot \Pr [{Exp}_{A}^{IND-1} (λ) = 1] + 1 / 2 \cdot (1 - \Pr [{Exp}_{A}^{IND-1} (λ) = 1]) \\ = & 1 / 2 + 1 / 2 \cdot {Adv}_{A}^{IND} (λ) . \end{array}$

As for ${Exp}_{C}^{LWE-RAND}$ , the input distributions to $C$ in Fig. 2 are all uniformly distributed over $(Z_{q}^{m_{0} \times n_{0}}, Z_{q}^{m_{0}})$ . Therefore, the corresponding computed distribution above are also uniformly and independently distributed over $(Z_{q}^{m_{0} \times n_{0}}, Z_{q}^{m_{0}})$ . In particular, the challenge ciphertext is a random distribution over $(Z_{q}^{m_{0} \times n_{0}}, Z_{q}^{m_{0}})$ , and independent of bit b. Hence we have $\begin{array}{rcl} \Pr [{Exp}_{C}^{LWE-RAND} (λ) = 1] & ⩽ & 1 / 2 + 1 / 2^{λ - 1} . \end{array}$

The last term indicates that the random distribution to $C$ happen to have the distribution of a real distribution, which is bounded by $1 / 2^{λ - 1}$ since $2^{λ - 1} < q < 2^{λ}$ . By combing all equations above, we have $\begin{array}{rcl} {Adv}_{C}^{LWE} (λ) & = & \Pr [{Exp}_{C}^{LWE-REAL} (λ) = 1] + \Pr [{Exp}_{C}^{LWE-RAND} (λ) = 1] \\ ⩾ & 1 / 2 \cdot \Pr [{Exp}_{A}^{IND} (λ) - 1 / 2^{λ - 1} . \end{array}$

We can also show that $A_{0} \neq A_{1}$ when public parameter is chosen at random over $Z_{q}^{m_{0} \times n_{0}}$ , while $C$ will slightly change to $p_{0} \leftarrow (A_{0} = A, A_{0} \cdot X + χ + w_{0}); p_{1} \leftarrow (A_{1} = A_{0} \cdot A^{}, A_{1} \cdot (X + u) + χ + w_{1})$ , where $A^{} \overset{R}{\leftarrow} Z_{q}^{m_{0} \times n_{0}}$ . □
3. A new oblivious RAM

In this section, we present our proposed tree-based ORAM (uORAM). The uORAM protocol is comprised of some novel techniques from Path ORAM [40] and Ring ORAM [34].

Binary Tree $T$ . We assume a binary tree of height $L = log N$ and $2^{L}$ leaves. Levels in the tree are numbered from 0 (the root) to L.

Bucket. Each node in the tree is called a bucket with a fixed number (e.g., 4 or 5) of blocks. We guarantee that each bucket has exactly Z real blocks, and we allow the server to pad real blocks if a bucket has less than Z real blocks. We assume S dummy blocks are generated and padded for each bucket by the server. If the client tries to access her real blocks and maintain her access privacy, then she needs to update at least one dummy block in each bucket, which is similar to Path or Ring ORAM. Consequently, the server does not learn any information about the accessed blocks.

Path. Let ${leaf}_{ID} \in {0, 1, \dots, 2^{L} - 1}$ denote the leaf node in the tree. We define $P ({leaf}_{ID})$ as a set of buckets along the path from leaf ${leaf}_{ID}$ to the root, and $P ({leaf}_{ID}, ℓ)$ denotes the bucket in $P ({leaf}_{ID})$ at level ℓ in $T$ .

Stash. During the course of the data access, a small number of blocks might overflow from the tree buckets on the server. The client can locally store these overflowing blocks in a local data structure S called stash.

Position Map. The client also locally maintains a position map (see Fig. 1), which stores a public leaf identifier ${leaf}_{ID}$ and a secret block identifier $ID$ such that ${leaf}_{ID} \leftarrow position [ID]$ (i.e., a block $ID$ is currently mapped to a leaf node with identifier ${leaf}_{ID}$ ). The block $ID$ either resides in some buckets in path $P ({leaf}_{ID})$ , or in the stash S. The position map changes over time as blocks are accessed and remapped.

Operations. uORAM includes the following key operations: EarlyReshuffles, ReadPath and Evict. Here we provide a high-level of these operations.

ReadPath (from Ring ORAM). This operation reads one block from each bucket – the block of interest if found or a dummy block otherwise. Specifically, the ReadPath operation is to select a single block to read from that bucket. The index of the block to read (either real or random) is returned by the GetBlockOffset function. According to the random offset $offset$ per bucket and the leaf identifier ${leaf}_{ID}$ , the server fetches these blocks and passes them to the client. Specifically, the client relies on a small-size Bucket Metadata, which is used to store the $offset$ per bucket. We stress that the $offset$ is chosen at random by client. The client must read through all the buckets in a tree path $ℓ \in {0, 1, \dots, L}$ , and each bucket returns either the interested block or a randomly-chosen dummy block.

$ReadPath ({leaf}_{ID}, ID)$

$data \leftarrow ⊥$ , for $ℓ \in {0, 1, \dots, L}$ :

$offset \leftarrow GetBlockOffset (P ({leaf}_{ID}, ℓ), ID)$

${data}^{'} \leftarrow P ({leaf}_{ID}, ℓ, offset)$

if ${data}^{'} \neq ⊥$ then $data \leftarrow {data}^{'}$ , return $data$ .

EarlyReshuffles (from Ring ORAM). To ensure the ReadPath operation securely read one block per bucket, it requires a maintenance task called EarlyReshuffles on $P ({leaf}_{ID})$ , the path accessed by ReadPath. That is, the client reshuffles the bucket in the path ${leaf}_{ID}$ .

$EarlyReshuffles ({leaf}_{ID})$

for $ℓ \in {0, 1, \dots, L}$ :

$S \leftarrow S \cup ReadBucket (P ({leaf}_{ID}, ℓ))$

$WriteBucket (P ({leaf}_{ID}, ℓ), S)$ .

Evict (from Path ORAM). This operation is to push blocks back from the stash $S$ to the ORAM tree and keep the stash $S$ occupancy low. First, it reads all the buckets along the lookup path, all the (remaining) real blocks are added to the stash $S$ (i.e., $ReadBucket$ ). Meanwhile, the Evict operation writes as many blocks as possible from the stash $S$ back to the lookup path, and the evicted blocks from the stash get pushed down as far as they can go (i.e., $WriteBucket$ ). This operation terminates after writing all real blocks from the stash $S$ back to the lookup path, and each bucket is guaranteed to have Z real blocks. We denote the $ReadBucket$ and $WriteBucket$ functions as $Evict ({leaf}_{ID})$ operation, and the pseudocode is also shown in $EarlyReshuffles ({leaf}_{ID})$ (Line 2–4).

We briefly show the GetBlockOffset, ReadBucket, WriteBucket functions below, we refer reader to [34] for detailed descriptions.

GetBlockOffset is to find the block of interest $ID$ and return the permuted location of that block, or to return the permuted location of a random dummy block.

ReadBucket is to read exactly Z real blocks in a bucket into the stash $S$ . If the bucket contains less than Z real blocks, then the remaining blocks read out are updated dummy blocks (see Main Invariants below).

WriteBucket is to evict up to Z blocks from stash $S$ to a bucket. In particular, the location of $Z + S$ blocks are randomly reshuffled based on pseudo-random permutation or a truly random permutation. Eventually, the permuted data and its $offset$ are encrypted and written into the bucket.

Main Invariants. uORAM has three invariants, and we maintain these invariants at any time since they will determine the security of uORAM.

Invariant 1. Every block is mapped to a leaf chosen uniformly at random in the ORAM tree $T$ . If a block $ID$ is mapped to leaf ${leaf}_{ID}$ , block $ID$ is contained either in the stash S or in a bucket along the path from the root to leaf ${leaf}_{ID}$ .

Invariant 2. For every bucket in the tree $T$ , the physical position of the $Z + S$ real and dummy blocks in each bucket are randomly permuted with respect to all past and future writes to that bucket.

Invariant 3. For every bucket along the path from the root to leaf ${leaf}_{ID}$ , at least one dummy block in each bucket is randomly updated.

Data Access. uORAM takes ( $op, ID, {data}^{*}, time$ ) as input, outputs $data$ .

$EarlyReshuffles ({leaf}_{ID})$ ⊳ from Ring ORAM

${leaf}_{ID} \leftarrow position [ID]$

$position [ID] \leftarrow UniformRandom (0, 2^{L} - 1)$

$data \leftarrow ReadPath ({leaf}_{ID}, ID)$ ⊳ from Ring ORAM

$data \leftarrow$ read block $ID$ from $S$

if $op = read$ then return $data$ to client end if

if $op = write$ then $S \leftarrow (S - {(ID, data)}) \cup {(ID, {data}^{*})}$ end if

$Evict ({leaf}_{ID}, time)$ . ⊳ from Path ORAM

To access a block

ID

, the client first invokes an operation

EarlyReshuffles ({leaf}_{ID})

to read and write the real and dummy blocks on the path with leaf identifier

{leaf}_{ID}

(Line 1). As a result, the client can determine the physical positions of a block of interest

ID

and dummy blocks per bucket. Second, the block of interest is remapped to a new random path and the position map is updated accordingly (Line 2 to 3). Third, the client invokes a read path operation

ReadPath ({leaf}_{ID}, ID)

to read one block per bucket on that path, and then read that block into stash

S

(Line 4). If block

ID

is not found on path ℓ, it must be in Stash

S

(Line 5). Forth, if the access is read/write, then the client updates the content of block

ID

(Line 6 to 7). Last, the protocol invokes an eviction operation

Evict ({leaf}_{ID}, time)

that reads all remaining real blocks on that path into stash

S

and writes the same path we just read from, percolating blocks down that path (Line 8). We remark that the dummy blocks in the read/write path can be updated using either randomness (w.r.t. EarlyReshuffles operation) or timestamp (w.r.t. Evict operation), both randomness and timestamp are chosen at random by client. We note that timestamp is linked to “time-locked” dummy block, which means we embed a time-lock in a dummy block using a timestamp

time

during Evict operation. In other words, the “time-locked” dummy block can be updated again once the specified timestamp

time

is reached (or “unlocked”). For example, another client may update the “unlocked” dummy block using a new randomness during his EarlyReshuffles operation.

3.1. Security definition

We modify the standard ORAM security definition [22]. That is, adding a designated timestamp to the operation of an access pattern. Informally, two access patterns in a specific time-window (i.e., a time period that is considered best from starting to finishing some tasks such as user authentications) should be computationally indistinguishable. A crucial point is, the client makes data requests within an allowable time-window does not leak any useful information about the access pattern.

Definition 3.1 (Security Definition).

Let $\begin{matrix} \overset{\leftarrow}{y} = (({op}_{M}, {ID}_{M}, {data}_{M}, {time}_{M}), \dots, ({op}_{1}, {ID}_{1}, {data}_{1}, {time}_{1})) \end{matrix}$ denote a data sequence of M, where ${op}_{i}$ denotes the i-th operation is a read or a write, ${ID}_{i}$ denotes the address for that access, ${data}_{i}$ denotes the data being written, and ${time}_{i}$ denotes the designated timestamp such that ${time}_{i} \in ϱ$ , where ϱ denotes an allowable time-window. Let uORAM( $\overset{\leftarrow}{y}$ ) be the resulting sequence of operations between client and server under an uORAM protocol. The uORAM protocol guarantees that: (1) for any $\overset{\leftarrow}{y}$ and $\overset{\leftarrow}{y^{'}}$ , uORAM( $\overset{\leftarrow}{y}$ ) and uORAM( $\overset{\leftarrow}{y^{'}}$ ) are computationally indistinguishable (by anyone except the client) if $| \overset{\leftarrow}{y} | = | \overset{\leftarrow}{y^{'}} |$ ; (2) for any $\overset{\leftarrow}{y}$ the data returned to the client using uORAM is consistent with $\overset{\leftarrow}{y}$ (i.e., the uORAM behaves like a valid RAM) with overwhelming probability.

Security Analysis. We prove the security of uORAM using the similar approach described in [34].

Lemma 3.1.
EarlyReshuffles operation leaks no information.
Proof.
We let ReadBucket function read exactly $Z^{'} = Z + “1”$ real blocks from random slots. If the bucket contains less than $Z^{'}$ real blocks, the remaining blocks read out are updated dummy blocks. The number $“1”$ means that at least one dummy block in each bucket is updated by the client when reading. Meanwhile, the number of dummy blocks per bucket becomes $S^{'} = S - ‘ “1”$ . Similarly, WriteBucket function writes $Z^{'} + S^{'}$ (i.e., $Z + S$ ) encrypted blocks in a data-independent fashion. If there are $z^{'} ⩽ Z^{'}$ real blocks to be evicted to that bucket, then $Z^{'} - z^{'}$ updated dummy blocks are added. In particular, the $Z^{'} + S^{'}$ real and dummy blocks are randomly shuffled by the client. Overall, $A$ learns nothing during EarlyReshuffles operation. □
Lemma 3.2.
ReadPath operation leaks no information.
Proof.
The path selected for reading will look random to $A$ due to Invariant 1 such that leaves are chosen uniformly at random. From Invariant 2, we know that every bucket is randomly reshuffled. In particular, the real and updated dummy blocks we read are indistinguishable to $A$ due to Invariant 3 (the Lemma 2.3 confirms such fact). Therefore, $A$ learns nothing during ReadPath operation. □
Lemma 3.3.
Evict operation leaks no information.
Proof.
The path selected for eviction is chosen uniformly and is public. $ReadBucket$ function reads all remaining real and updated dummy blocks from the bucket stored on the server. The real and updated dummy blocks on the lookup path are stored into stash $S$ after $ReadBucket$ . $WriteBucket$ function writes the real and updated dummy blocks from the stash $S$ into the specified bucket on the server. In particular, the client writes back all updated dummy blocks to their original format. Meanwhile, the client erases her random permutation in the Bucket Metadata. If there is $z ⩽ Z$ real blocks to be evicted to that bucket, then $Z - z$ “time-locked” blocks are added. The “time-locked” blocks are the blocks that cannot be updated until a designated timestamp is reached. We remark that the real and “time-locked” blocks we write back are indistinguishable to $A$ because the specified timestamp $time$ is randomly chosen by the client (otherwise, the server may keep a history of the updated dummy blocks if a client updates them multiple times within a time-window ϱ, thus break the unlinkability of uORAM). Therefore, $A$ learns nothing during Evict operation within ϱ. □

3.2. Stash and bandwidth analysis

Since a small number of blocks might overflow from the tree bucket on the server after Evict operation, the client locally stores these overflowing blocks in the stash $S$ . To analyze the stash usage (i.e., measuring the number of real blocks that remain in the stash after Evict operation), we rely on the theoretical result of Path ORAM [40]. The Theorem 1 in [40] has shown that the probability (i.e., the number of real blocks in the stash exceeds R) decreased exponentially in R (i.e., the stash size).

Now, we analyze the overall bandwidth of proposed uORAM, including EarlyReshuffles, ReadPath and Evict operations. The EarlyReshuffles operation reads exactly $Z + “1”$ real blocks and writes back $Z + S$ real and dummy blocks per bucket, so the bandwidth is $(2 Z + S + “1”) (L + 1)$ ( $L = log N$ ). The number $“1”$ means that at least one dummy block per bucket is updated by the client due to Invariant 3. We observe that the ReadPath operation first transfers $L + 1$ blocks – one from each bucket. Then, the client reads the remaining real and updated dummy blocks into the stash and writes back $Z + S$ real and dummy blocks per bucket during Evict operation. So, the overall bandwidth is $2 (2 Z + S + “1”) (L + 1)$ . We notice that the overall bandwidth of uORAM is higher than a Path or Ring ORAM. However, neither Path ORAM nor Ring ORAM can achieve our design goal (see Appendix).

4. The proposed general framework

In this section, we first present the security models (user authenticity and strong privacy) for our proposed pBRUA. Then, we show the proposed general framework of pBRUA.

States. We define a system user set $U$ with n users, i.e. $| U | = n$ . We say an instance oracle $Π_{pk}^{i}$ (i.e., session i of user $pk$ ) may be used or unused, and a user $pk$ has an unlimited number of instances called oracles. The oracle is considered as unused if it has never been initialized. Each unused oracle $Π_{pk}^{i}$ can be initialized with a secret key $sk$ . The oracle is initialized as soon as it becomes part of a group. After the initialization the oracle is marked as used and turns into the stand-by state where it waits for an invocation to execute a protocol operation. Upon receiving such invocation, the oracle $Π_{pk}^{i}$ learns its partner id ${pid}_{pk}^{i}$ (i.e., a collection of recognized users by the instance oracle $Π_{pk}^{i}$ ) and turns into a processing state where it sends, receives and processes messages according to the description of the protocol. During that stage, the internal state information ${state}_{pk}^{i}$ is maintained by the oracle. The oracle $Π_{pk}^{i}$ remains in the processing state until it collects enough information to finalize the user authentications. As soon as the user authentication is accomplished, $Π_{pk}^{i}$ accepts and terminates the protocol execution meaning that it would not send or receive further messages. If the protocol execution fails then $Π_{pk}^{i}$ terminates without having accepted. We define ${sid}_{pk}^{i}$ as the unique session identifier belonging to user $pk$ of session i. Specifically, ${sid}_{pk}^{i} = {m_{j}}_{j = 1}^{n}$ , where $m_{j} \in {0, 1}^{*}$ is the message transcript among users in ${pid}_{pk}^{i}$ . The session identifier means that the session which $Π_{pk}^{i}$ participates in is defined by a unique session id ${sid}_{pk}^{i}$ , and this value is known to all oracles participating in the same session.

4.1. Definition

A pBRUA framework consists of the following algorithms:

Setup: The algorithm takes a security parameter λ as input, outputs a public parameter $p p$ .

Enrollment: This is a non-interactive protocol between a user and an authentication server in a secure channel. The user first generates a secret/public key pair $(sk, pk)$ using public parameter $p p$ , derives a sketch $SS (s, w)$ from her biometrics w and a secret string s. Then, she enrolls her identity $ID$ , public key $pk$ and sketch $SS (s, w)$ to the authentication server. The enrolled users become authorized ones after enrollment. We assume a uniform3

³
One may question a uniform source is not practical, we stress that the uniform source can be replaced by a non-uniform source (e.g., symbol-fixing source [27]) while the security of FE is held. We use a uniform source here just for simplicity, and the case of the non-uniform source was explicitly discussed in [21,43].

biometrics source

M

and

w \in M

Authentication: This is an interactive protocol between an authorized user and an authentication server over a public channel. An authorized user takes public parameter $p p$ , her nearby biometrics $w^{'}$ and her enrolled sketch $SS (s, w)$ as input, outputs a message-signature pair $(m, σ)$ . The authentication server accepts the user if the message-signature pair $(m, σ)$ is verified as valid under her enrolled public key $pk$ . The message m contains the ephemeral data transmitted during user authentication, and the nearby biometrics satisfies $dist (w^{'}, w) ⩽ t$ .

4.2. Security models

A secure pBRUA framework should achieve several security goals: user authenticity and user privacy. Below we present corresponding security models to capture these requirements.

Authenticity. Informally, an adversary attempts to impersonate an authorized user and authenticate herself to an authentication server. We define a formal authenticity game between a probabilistic polynomial-time (PPT) adversary $A$ and a challenger $C$ below.

Setup. $C$ first generates public/secret key pairs ${({pk}_{i} {sk}_{i})}_{i = 1}^{n}$ ( $i \in {1, n}$ ) for n users and an authentication server $S$ in the system. $C$ also generates biometrics information $w_{i}$ and its corresponding sketch $SS (s_{i}, w_{i})$ for individual users. Eventually, $C$ sends all users’ public keys and sketches to $A$ .

Training. $A$ can make the following queries in an arbitrary sequence to $C$ .

Send: If $A$ issues a send query in the form of ( $pk, i, m$ ) to simulate a network message for the i-th session of user $pk$ , then $C$ would simulate the reaction of instance oracle $Π_{pk}^{i}$ upon receiving message m, and return to $A$ the response that $Π_{pk}^{i}$ would generate; If $A$ issues a send query in the form of ( ${pk}^{'}$ , $‘ start ’$ ), then $C$ creates a new instance oracle $Π_{{pk}^{'}}^{i}$ and returns to $A$ the first protocol message.

Biometrics Reveal: If $A$ issues a biometrics reveal query to user i, then $C$ returns user i’s biometrics information $w_{i}$ to $A$ .

Secret Key Reveal: If $A$ issues a secret key reveal query to user i, then $C$ returns user i’s enrolled secret key ${sk}_{i}$ to $A$ .

Challenge. $A$ wins the game if all of the following conditions hold.

$S$ accepts user ${pk}_{i}$ . It implies ${sid}_{S}^{s}$ (i.e., session s of server $S$ ) exist.

$A$ issued neither Biometrics Reveal nor Secret Key Reveal query to user ${pk}_{i}$ .

$m \in {sid}_{S}^{s}$ , but there exists no instance oracle $Π_{{pk}_{i}}^{s}$ which has sent m (m denotes the message transcript from user ${pk}_{i}$ ).

We define the advantage of an adversary

A

in the above game as

\begin{matrix} {Adv}_{A} (λ) = | \Pr [A wins] | . \end{matrix}

Definition 4.1.
We say a pBRUA protocol has user authenticity if for any PPT $A$ , ${Adv}_{A} (λ)$ is a negligible function of the security parameter λ.

Strong Privacy. Informally, an authentication server $S$ is not allowed to identify who are the authorized users in a certain time-window. We define a game between an adversary $A$ and a challenger $C$ as follows:
Setup: $C$ generates public/secret key pairs ${({pk}_{i} {sk}_{i})}_{i = 1}^{n}$ for n users and an authentication server $S$ in the system. In addition, $C$ generates biometrics information $w_{i}$ and its corresponding sketch $SS (s_{i}, w_{i})$ for individual users. Eventually, $C$ sends all public information to $A$ , and the authentication server $S$ is completely controlled by $A$ . $C$ tosses a random coin b which will be used later in the game. We denote the original n users set as $U$ .

Training: $A$ is allowed to issue Send query and at most $n - 2$ Secret Key Reveal and Biometrics Reveal queries to $C$ . We denote $U^{'}$ as the set of honest users whose biometrics as well as secrets keys are not corrupted.

Challenge: $A$ randomly selects two users ${pk}_{i}, {pk}_{j} \in U^{'}$ as challenge candidates, then $C$ removes them from $U^{'}$ and simulates ${pk}_{b}^{}$ to $A$ by either ${pk}_{b}^{} = {pk}_{i}$ if $b = 1$ or ${pk}_{b}^{} = {pk}_{j}$ if $b = 0$ . $C$ chooses a time-window ϱ, lets $A$ interact with challenge user ${pk}_{b}^{}$ in the time-window ϱ. $\begin{matrix} A \Leftrightarrow {pk}_{b}^{*} = \{\begin{matrix} {pk}_{i}, & b = 1, \\ {pk}_{j}, & b = 0 . \end{matrix} \end{matrix}$

Finally, $A$ outputs $b^{'}$ as its guess for b. If $b^{'} = b$ , then $C$ outputs 1; Otherwise, $C$ outputs 0. We define the advantage of $A$ in the above game as $\begin{matrix} {Adv}_{A} (λ) = \Pr [C \to 1] - 1 / 2 . \end{matrix}$
Definition 4.2.
We say a pBRUA protocol has strong privacy if for any PPT $A$ , ${Adv}_{A} (λ)$ is a negligible function of the security parameter λ.

4.3. Proposed construction

Fig. 3.

High-level user authentication via uORAM.

High-level Description. Suppose at most n users enroll themselves to an authentication server, and the authentication server built a binary tree to store all users’ enrolled information. Next, an uORAM protocol is executed between an authorized user and the authentication server for user authentications (including early-reshuffle phase, challenge-response phase, and post-reshuffle phase), which is described in Fig. 3. Specifically, in the early-reshuffle phase, an authorized user randomizes and permutes either her real block or a dummy block in each bucket along a tree path (i.e., EarlyReshuffles operation, and the tree path must include her real block). In the challenge-response phase, the authorized user first obtains the permutation of either her real block or a dummy block in each bucket by performing the ReadPath operation. Then, the authorized user derives a message-signature pair based on her real block and the randomized dummy blocks for proving her authenticity. In the post-reshuffle phase, the authorized user re-randomizes all blocks in the tree path (i.e., Evict operation). The proposed pBRUA framework is mainly used to achieve strong privacy for valid user authentications. The proposed pBRUA framework consists of the following building blocks. Meanwhile, we note that a blind signature scheme [7] could be used to prevent an unauthorized user with NO enrolled biometrics from performing a valid user authentication in the pBRUA framework (the detailed explanation is referred to Remark 2).

A LWE-based computational fuzzy extractor $FE = (Gen, Rep)$ .

An Existential Unforgeability under Chosen Message Attack EUF-CMA secure digital signature $Σ = (Setup, KG, Sign, Verify)$ .

An Indistinguishability of Keys under Chosen Plaintext Attack IK-CPA secure public key encryption $PKE = (KG, Enc, Dec)$ .

The uORAM protocol.

Block Structures. The real block consists of two parts: user i’s public key and sketch $({pk}_{2}, SS (s_{2}, w_{2}))$ . The dummy block is of the form $({pk}_{1}, SS (s_{1}, empty))$ , where ${pk}_{1}$ denotes a random public key, the data in sketch $SS$ is $empty$ (i.e., “0”) and the secret string $s_{1}$ is chosen at random. We stress that the dummy block is a public resource during Enrollment, it becomes a private one during Authentication. The status of real block $({pk}_{2}, SS (s_{2}, w_{2}))$ and dummy block $({pk}_{1}, SS (s_{1}, 0))$ at different phases are shown in Fig. 4, respectively.

Fig. 4.

The status of real or dummy block in a bucket. The physical position of real or dummy block in the bucket will be permuted at random under EarlyReshuffles operation and Evict operation, respectively. Meanwhile, the hidden message (r₁ denotes the randomness and T₁ denotes the timestamp) in dummy sketch will be updated accordingly.

Our Construction. Let ${H_{z} : Z_{q}^{n_{0}} \to Z_{q}}$ be a universal hash function with linearity that we reviewed in Section 2.3. For each seed $z \in Z_{q^{n_{0}}}$ and $y \in Z_{q}$ , we define “ $H_{z}^{- 1} (y)$ ” as the set of pre-images of y under $H_{z}$ . That is, $H_{z}^{- 1} (y) = {x \in Z_{q}^{n_{0}} : H_{z} (x) = y}$ . In particular, $x \overset{R}{\leftarrow} H_{z}^{- 1} (y)$ means that we choose an element x uniformly from the set $H_{z}^{- 1} (y)$ , and its dimension is $n_{0}$ . We run the Setup algorithm first to generate the public parameter $p p$ in the system. Then, we use a user i and an authentication server $S$ to illustrate our general framework.

Enrollment. A user i enroll herself to an authentication server $S$ will perform the following

generate a secret/public key pair $({sk}_{i}, {pk}_{i}) \leftarrow Σ . KG (p p)$ .

obtain a secret/public string pair $(s_{i}, p_{i}) \leftarrow FE.Gen (p p, w_{i})$ , where $s_{i} \overset{R}{\leftarrow} H_{z}^{- 1} ({sk}_{i})$ , $w_{i} \leftarrow M$ (the biometrics distribution $M$ is referred to Section 2.4), and public string $p_{i} = SS (s_{i}, w_{i})$ .

send public values $({pk}_{i}, SS (s_{i}, w_{i}))$ to $S$ .

According to the uORAM protocol,

S

regards user i’s public information

({pk}_{i}, SS (s_{i}, w_{i}))

as an enrolled record, stores into a bucket and returns the leaf identifier

{leaf}_{i d_{i}}

of that tree path to user i. The user i can identify her block of interest in a bucket of the lookup path using leaf identifier

{leaf}_{i d_{i}}

and block identifier

{ID}_{i}

, where

{leaf}_{i d_{i}} \leftarrow position [{ID}_{i}]

and

{ID}_{i}

is the secret block identifier.

Fig. 5.

The Authentication includes early-reshuffle, challenge-response, and post-reshuffle phases. The bandwidth of early-reshuffle phase and post-reshuffle phase are $Z \cdot log N$ , respectively. In the challenge-response phase, server $S$ returns a ciphertext $C_{i, 2}^{*}$ (i.e., aggregated “sketch”) only.

Authentication. The detailed interaction between a user i and authentication server $S$ is described in Fig. 5. We use the previously mentioned three phases to present the general framework.

Early-reshuffle Phase: User i performs the $EarlyReshuffles ({leaf}_{{id}_{i}})$ operation to update the ${offset}_{j}$ ( $j \in {0, L}$ ) for all buckets along the lookup path. Specifically, user i: (1) updates a dummy block as $({pk}_{j}, SS (s_{j}, r_{j}))$ in a bucket, where the randomness $r_{j} \leftarrow M$ is chosen at random by user i (see remark below for detailed description); (2) writes $offset$ into ${Bucket Metadata}_{j} \leftarrow PKE.Enc ({pk}_{i}, {offset}_{j})$ per bucket along the lookup path.

Challenge-response Phase: User i performs the $ReadPath ({leaf}_{{id}_{i}}, {ID}_{i})$ operation to obtain the random ${offset}_{j} \leftarrow PKE.Dec ({sk}_{i}, {Bucket Metadata}_{j})$ per bucket in the lookup path. Upon receiving an authentication request (i.e., a set of offset ${{offset}_{j}}_{j = 0}^{L}$ and leaf identifier ${leaf}_{{id}_{i}}$ ) from user i, $S$ computes an “aggregated” version of requested blocks, which consists of a ( $L + 1$ size) set of public keys and sketches: $C_{(i, 1)}^{*} \leftarrow \prod_{i = 0}^{L} {pk}_{i}, C_{(i, 2)}^{*} \leftarrow \sum_{i = 0}^{L} (SS (s_{i}, w_{i}))$ (see correctness below), and returns a single ciphertext $C_{(i, 2)}^{*}$ and a challenge randomness $n_{j}$ to user i.

Challenge-response Phase: User i performs the following

choose a response randomness $n_{i}$ and generate the message $m_{(i, j)} = (n_{i}, n_{j}, Request)$ .

extract the secret string by running algorithm $s_{i}^{*} \leftarrow FE.Rep (C_{(i, 2)}^{*}, w_{i}^{'})$ iff $dist (w_{i}^{'}, w_{i}) ⩽ t$ , and obtain the “aggregated” secret key ${sk}_{i}^{*} \leftarrow H_{z} (s_{i}^{*})$ .

generate a message-signature pair $(m_{(i, j)}, σ_{i}) \leftarrow Σ . Sign ({sk}_{i}^{*}, m_{(i, j)})$ and send it to $S$ .

Challenge-response Phase: $S$ verifies $1 \overset{?}{=} Σ . Verify (C_{(i, 1)}^{*}, m_{(i, j)}, σ_{i})$ under the “aggregated” public key $C_{(i, 1)}^{*}$ . If the signature passes the verification, it accepts; Otherwise, it aborts.

Post-reshuffle Phase: User i performs the $Evict ({leaf}_{{id}_{i}})$ operation. Specifically, $Evict ({leaf}_{{id}_{i}})$ operation reads all remaining real blocks along the lookup path into the local stash S, writes real and updated dummy blocks back to the lookup path.

Instantiations. We hereby try to instantiate the underlying cryptographic building blocks. First, to instantiate the LWE-based computational fuzzy extractors, we could use the fuzzy extractor scheme in [2,21,43]. In particular, we require that all enrolled users share the common public parameters, just like the first reusable fuzzy extractor scheme in [2]. Second, we use the Schnorr signature scheme with homomorphic property to instantiate the underlying digital signatures. Meanwhile, the Waters signature scheme described in [41] should be also suitable for our general framework. Last, the public key encryption scheme (which was used in Bucket Metadata) can be instantiated to ElGamal cryptosystem [19] for achieving IK-CPA security, and we refer readers to [5] for Cramer-Shoup cryptosystem [12] with IK-CCA security which might be alternatively applicable to instantiate our general framework.

Correctness. In the challenge-response phase of user authentication, the returned block is either a block of interest or an updated dummy block in a bucket. Specifically, ReadPath opreation will request $L + 1$ blocks in a tree path – one from each bucket. That is, $({pk}_{0}, SS (s_{0}, r_{0})), ({pk}_{i}, SS (s_{i}, w_{i})), \dots, ({pk}_{L}, SS (s_{L}, r_{L}))$ , where ${pk}_{i} = g^{{sk}_{i}}$ and $SS (s_{i}, w_{i}) = A \cdot s_{i} + w_{i}$ ( $g, A \in p p$ ). We notice that a dummy block after EarlyReshuffles operation will be updated as $({pk}_{0}, SS (s_{0}, r_{0})) = (g^{{sk}_{0}}, A \cdot s_{0} + r_{0})$ , where randomness $r_{0}$ is independently chosen and stored by user i (see remark below). To achieve a constant bandwidth, the authentication server $S$ returns a single “aggregated” ciphertext (underline part) to user i: $(C_{(i, 1)}^{*}, \underline{C_{(i, 2)}^{*}})$ , where $C_{(i, 1)}^{*} = {pk}_{0} \cdot {pk}_{1} \dots {pk}_{L}$ , $\underline{C_{(i, 2)}^{*}} = SS (s_{0}, r_{0}) + SS (s_{i}, w_{i}) + \dots + SS (s_{L}, w_{L})$ and · denotes the multiplication. More specifically, $\begin{array}{l} C_{(i, 1)}^{*} = {pk}_{0} \cdot {pk}_{1} \dots {pk}_{L} = g^{\sum_{i = 0}^{L} ({sk}_{i})}, \\ \underline{C_{(i, 2)}^{*}} = SS (s_{0}, r_{0}) + SS (s_{i}, w_{i}) + \dots + SS (s_{L}, r_{L}) = A (\sum_{i = 0}^{L} (s_{i})) + \sum_{i = 0}^{L - 1} (r_{i}) + w_{i}, \end{array}$ where $\sum_{i = 0}^{L} ({sk}_{i}) = H_{z} (\sum_{i = 0}^{L} (s_{i}))$ . The user i can obtain the “aggregated” sketch (includes her interested sketch $SS (s_{i}, w_{i})$ ) by removing the randomness ${r_{i}}_{i = 0}^{L - 1}$ , and the challenge-response of user authentications proceeds as the protocol specified.

Remark 1.

The ReadPath operation relies on a metadata: Bucket Metadata. We use an example to illustrate its workflow, and we assume a bucket includes 4 blocks. We also assume the bucket includes a block interested by user i $({pk}_{i}, SS (s_{i}, w_{i}))$ , a block interested by another user j $({pk}_{j}, SS (s_{j}, w_{j}))$ and two dummy blocks $({pk}_{0}, SS (s_{0}, 0)), ({pk}_{1}, SS (s_{1}, 0))$ , where $s_{0}, s_{1}$ are chosen at random by server $S$ .

The EarlyReshuffles operation includes ReadBucket and WriteBucket functions. The ReadBucket function will read all real blocks from the bucket into the local stash. Specifically, a user i finds her block of interest (interest) and one dummy block (dummy) per bucket in a “compute and compare” manner. In particular, user i updates one dummy block (updated). More concretely, $\begin{array}{l} {pk}_{i} = g^{{sk}_{i}}, {sk}_{i} \leftarrow FE.Rep (SS (s_{i}, w_{i}), w_{i}^{'}) . ⊳ interest, \\ {pk}_{0} = g^{{sk}_{0}}, {sk}_{0} \leftarrow FE.Rep (SS (s_{0}, 0), 0) . ⊳ dummy, \\ {pk}_{0}^{'} = g^{{sk}_{0}^{'}}, {sk}_{0}^{'} \leftarrow FE.Rep (SS (s_{0}, r_{0}), r_{0}) . ⊳ updated, \end{array}$ where randomness $r_{0} \leftarrow M$ is chosen by user i and the updated dummy block can be decrypted by user i only. Afterwards, use i writes back 3 blocks (i.e., one updated dummy block ${pk}_{0}^{'}$ and two real blocks ${pk}_{i}$ and ${pk}_{j}$ ) and writes the permuted $offset$ into the Bucket Metadata (i.e., WriteBucket function). Specifically, user i chooses the $offset \in {0, \dots, 3}$ at random and encrypts the random $offset$ by running $C_{i} \leftarrow PKE.Enc ({pk}_{i}, offset)$ . Later, if user i performs the ReadPath operation, then she can obtain the random $offset \leftarrow PKE.Dec ({sk}_{i}, C_{i})$ .

The $Evict$ operation requires that the block of interest ${ID}_{i}$ must be re-randomized as $({pk}_{i}^{'}, SS (s_{i}^{'}, data)) = (g^{{sk}_{i}^{'}}, A \cdot s_{i}^{'} + data)$ , where ${sk}_{i}^{'}$ is chosen at random and $s_{i}^{'} = H_{z}^{- 1} ({sk}_{i}^{'})$ . Other blocks (include dummy blocks) in the same bucket should also be re-randomized accordingly. For example, a block $({pk}_{j}, SS (s_{j}, w_{j}))$ is re-randomized as $({pk}_{j}^{'}, SS (s_{j}^{'}, w_{j})) = ({pk}_{j} \cdot g^{Δ ({sk}_{j})}, SS (s_{j}, w_{j}) + A \cdot Δ (s_{j}))$ , where $Δ (s_{j}) \leftarrow H_{z}^{- 1} (Δ ({sk}_{j}))$ , and $Δ ({sk}_{j})$ is chosen at random. Note that the $data$ can be a new biometrics such as $\overline{w_{i}} \neq w_{i}$ . According to the design of uORAM protocol, the dummy block is a common resource shared by all enrolled users, user i should remove her randomness $r_{0}$ in sketch $SS (s_{0}, r_{0})$ . To maintain the security of Definition 3.1, user i updates the dummy block to a “time-locked” format: $SS (s_{0}, {time}_{0}) = A \cdot s_{0} + {time}_{0}$ , where ${time}_{0} \leftarrow M$ denotes a designated timestamp. Once the designated timestamp is reached, the “time-locked” dummy block becomes a public one. We note that an extra (mapping) mechanism could be used to transform a timestamp with the standard format into a distribution over $Z_{q}^{m_{0}}$ .

Since multiple users share an uORAM protocol and each user has an individual stash, the user should push all real blocks back to the uORAM tree during Evict operation. This is because if real blocks reside in the local stash S, then user authentication may fail. We leave it as a future work to ensure a policy such that the user must push real blocks back to the uORAM tree, or to ensure a valid user authentication even when real blocks are resided in the stash S.

Remark 2.

One may notice that an unauthorized (or unenrolled) user with NO biometrics data can be successfully authenticated by the authentication server. This is because the dummy blocks in the tree are common resources, any third parties can distinguish them from real blocks (as described previously). In this way, the unauthorized user updates at least one dummy block in each bucket in a tree path, and utilizes them for generating a valid message-signature pair and authenticating herself to the authentication server. We stress that such security threat is independent from the security concern in our proposed user authenticity model (an adversary tries to impersonate an authorized user). In particular, the unauthorized user authentication will NOT help the adversary (e.g., impersonator) to win the user authenticity game.

To tackle such security threat, we rely on an extra cryptographic tool: signatures on randomizable ciphertexts [7], such that given a signature on a ciphertext, any third parties (know neither the signing key nor the encrypted message) can randomize the ciphertext and adapt the signature to the re-randomized ciphertext. A pair of ciphertext and its signature can be randomized simultaneously and consistently. In particular, a given signature can be transformed into a new one on the same message, which in turn yields a blind signature scheme.

The modified pBRUA framework is described as follows: an authorized user runs the interactive blind signature scheme proposed in [7], to derive a publicly verifiable ciphertext-signature pair $(C, σ)$ during Enrollment. Let the encrypted message be denoted as ${ID}_{i}$ (i.e., user i’s secret block identifier). In the challenge-response phase of Authentication, an authorized user sends the derived ciphertext-signature pair to the authentication server as the authentication request. The authentication executes the pBRUA protocol if the ciphertext-signature pair is valid (i.e., the anonymous authorized user is an enrolled one). We stress that, the authentication server still cannot link the anonymous authorized user across different authentication sessions, because the ciphertext-signature pair has the blindness, and it can be randomized by the authorized user with the same encrypted message ${ID}_{i}$ .

5. Security analysis

In this section, we show the security result of our proposed pBRUA framework.

Theorem 5.1.
The proposed pBRUA achieves user authenticity if the ${D-LWE}_{q, n_{0} - k, m_{0}, χ}$ assumption is $(ϵ, s_{\sec}^{'})$ secure, the family of universal hash functions $H \leftarrow {H_{z} : Z_{q}^{n_{0}} \to Z_{q}}_{z \in Z}$ is ϵ-statistically secure and the digital signature scheme Σ is EUF-CMA secure.
Proof.
We define a sequence of games ${G_{i}}$ and let ${Adv}_{i}^{pBRUA}$ denote the advantage of the adversary $A$ in game $G_{i}$ . Assume that $A$ activates at most m sessions in each game. We highlight the differences between adjacent games by underline. For simplicity, we ignore the technique for constant bandwidth in the following and subsequent proofs.
$G_{0}$ : This is the original game for user authenticity security.

$G_{1}$ : This game is identical to game $G_{0}$ except that the challenger $C$ will output a random bit if the authentication server $S$ accepts a user i, but ${sid}_{i}^{s} \neq {sid}_{S}^{s}$ (i.e., a session s between user i and server $S$ ). Since n users involved in this game, we have: $\begin{matrix} (1) & | {Adv}_{0}^{pBRUA} - {Adv}_{1}^{pBRUA} | ⩽ n \cdot m^{2} / 2^{λ} . \end{matrix}$

$G_{2}$ : This game is identical to game $G_{1}$ except the following difference: $C$ randomly chooses $g \in {1, m}$ as a guess for the index of the Challenge session. $C$ will output a random bit if $A$ ’s challenge query does not occur in the g-th session. Therefore we have $\begin{matrix} (2) & {Adv}_{1}^{pBRUA} = m \cdot {Adv}_{2}^{pBRUA} . \end{matrix}$

$G_{3}$ : This game is identical to game $G_{2}$ except that in the g-th session, the k-size pseudorandom bit of hidden secret in the sketch $SS (s_{i}, w_{i})$ of user i is replaced by a random value U. Below we show that the difference between $G_{2}$ and $G_{3}$ is negligible under the ${D-LWE}_{q, n_{0} - k, m_{0}, χ}$ assumption.

Let $C$ denote a distinguisher against the ${D-LWE}_{q, n_{0} - k, m_{0}, χ}$ assumption, who is given a tuple $(\underline{X_{1, \dots, k}}, A, A \cdot X + χ)$ , aims to distinguish the real LWE tuple from a random tuple $(\underline{U}, A, A \cdot X + χ)$ where $U \in Z_{q}^{k}$ . $C$ simulates the game for $A$ as follows.
Setup. $C$ sets up the game for $A$ by creating n users with the corresponding block identifiers ${{ID}_{i}}$ . $C$ randomly selects index i and guesses that the g-th session will happen with regard to user i. $C$ sets the sketch of user i as $SS (s_{b}, w_{i})$ such that $SS (s_{b}, w_{i}) = A \cdot \underline{X_{b}} + χ$ , where $X_{b} = \underline{X_{1, \dots, k}}$ . $C$ sets user i’s enrolled secret key as ${sk}_{b} \leftarrow H_{z} (\underline{X_{b}})$ (its public key is ${pk}_{b} \leftarrow Σ . KG (p p, {sk}_{b})$ ). $C$ honestly generates biometrics, public/secret key pairs and sketches as Enrollment specified for n-1 users. In addition, $C$ generates certain dummy public keys and sketches in the system. Eventually, $C$ sends all real/dummy enrolled public keys and references to $A$ . Note that we choose a random vector from $Z_{q}^{n_{0} - k}$ to generate $X_{b} \in Z_{q}^{n_{0}}$ , we omit it in the following proof.

Training. $C$ answers $A$ ’s queries as follows.

If $A$ issues a Send query in the form of $(n_{j}, C_{(i, 2)}^{})$ to $C$ , where $C_{(i, 2)}^{}$ includes a re-randomized real sketch $SS (s_{b}^{'}, w_{i})$ and L dummy sketches ${SS (s_{j}, r_{j})}$ . $C$ chooses a response randomness $n_{i}$ first, then $C$ honestly generates the protocol transcript $T_{i}$ using user i’s enrolled secret key ${sk}_{b}$ . Specifically, $T_{i} = (m_{(i, j)}, σ_{i})$ , where $σ_{i} \leftarrow M_{Σ} (p p, {pk}_{b}, Sign ({sk}_{b}, m_{(i, j)}), Δ (s_{i}))$ , and the correct offset $Δ (s_{i})$ derives from $C_{(i, 2)}^{}$ . More specifically, $C$ first obtains the randomness ${r_{j}}$ from updated dummy sketches, in which the dummy sketch is $SS (s_{j}, r_{j}) = A \cdot s_{j} + r_{j}$ . Next, $C$ can obtain the correct offset $Δ (s_{i})$ from a real sketch $SS (s_{b}^{'}, w_{i}) = A \cdot \underline{X_{b}} + χ + A \cdot Δ (s)$ and L dummy sketches, where the offset $Δ (s)$ and the randomness ${r_{j}}$ are chosen at random by $A$ .

In the g-th session of user i, upon receiving a Send query from $A$ , $C$ first obtains $X_{b}^{'} = X_{b} + Δ (s_{i})$ , where $X_{b} = \underline{U}$ and the computation of correct offset $Δ (s_{i})$ using the same method described above; $C$ then generates the re-randomized secret key ${sk}_{b}^{'}$ from $X_{b}^{'}$ (i.e., ${sk}_{b}^{'} \leftarrow H_{z} (X_{b}^{'})$ ) for producing message-signature pair while $A$ verifies it using the corresponding public key ${pk}_{b}^{'}$ .

If $A$ issues a Biometrics Reveal query to user i, then $C$ aborts.

If $A$ issues a Secret Key Reveal query to an instance oracle $Π_{{pk}_{i}}^{g}$ (g-th session of user i), then $C$ returns a (re-randomized) secret key ${sk}_{b}^{'}$ to $A$ . Notice that $A$ is not allowed to obtain user i’s enrolled secret key ${sk}_{b}$ .
In the Challenge session of user i, if the challenge of $C$ is $\underline{X_{1, \dots, k}}$ , then the simulation is consistent with $G_{2}$ ; Otherwise, the simulation is consistent with $G_{3}$ . If the advantage of $A$ is significantly different in $G_{2}$ and $G_{3}$ , then $C$ can break the ${D-LWE}_{q, n_{0} - k, m_{0}, χ}$ . Since at most n users involved in the system, hence we have $\begin{matrix} (3) & | {Adv}_{2}^{pBRUA} - {Adv}_{3}^{pBRUA} | ⩽ n \cdot {Adv}_{C}^{{D-LWE}_{q, n_{0} - k, m_{0}, χ}} (λ) . \end{matrix}$

$G_{4}$ : This game is identical to game $G_{3}$ except that in the g-th session, the enrolled secret key ${sk}_{i}$ is replaced by a random value u. Below we show that the difference between $G_{3}$ and $G_{4}$ is bounded by a negligible probability.

Let $C$ simulate the whole environment honestly according to the protocol specification, and it is easy to see that all the queries made to a user can be simulated perfectly using the user’s secret keys and biometrics. In particular, the enrolled secret key of user i is ${sk}_{i}$ . In the g-th session of user i, to answer the Send query from $A$ , $C$ will simulate the protocol transcript $T_{i} = (n_{j}, C_{(i, 2)}^{})$ as follows. $C$ first simulates the real sketch as $SS (s_{i}^{'}, w_{i}) \leftarrow A \cdot (\underline{s_{i}} + Δ (s)) + w_{i}$ , where $s_{i}^{'} = \underline{s_{i}} + Δ (s), \underline{s_{i}} \overset{R}{\leftarrow} H_{z}^{- 1} (\underline{u}), u \in Z_{q}$ , and $Δ (s)$ is randomly chosen by $C$ ; $C$ then generates a secret/public key pair $({sk}_{i}^{'}, {pk}_{i}^{'})$ from a real sketch (with hidden secret $s_{i}^{'}$ ) and L dummy sketches for producing the message-signature pair, where ${sk}_{i}^{'} \leftarrow H_{z} (s_{i}^{'})$ .

We then analyze the statistical distance between distribution $T_{i} = (n_{j}, C_{(i, 2)}^{})$ at game $G_{4}$ and distribution $T_{i}$ at previous game $G_{3}$ . We notice that the only difference is the simulated value $s_{i} \overset{R}{\leftarrow} H_{z}^{- 1} (u)$ instead of taking the real enrolled secret key ${sk}_{i}$ as input, and according to Lemma 2.2, we have the statistically distance between ${sk}_{i} \leftarrow H_{z} (s_{i})$ and $u \in Z_{q}$ with probability no greater than ϵ. Hence we have $\begin{matrix} (4) & | {Adv}_{3}^{pBRUA} - {Adv}_{4}^{pBRUA} | ⩽ {Adv}_{C}^{H} (λ) . \end{matrix}$

$G_{5}$ : This game is identical to game $G_{4}$ except that in the g-th session, $C$ outputs a random bit if Forge event happens where $A$ ’s Send query includes a valid forgery $σ^{}$ while user i’s enrolled secret key is not corrupted. Then we have $\begin{matrix} (5) & | {Adv}_{4}^{pBRUA} - {Adv}_{5}^{pBRUA} | ⩽ \Pr [Forge] . \end{matrix}$

Let $F$ denote a forger against a signature scheme Σ with EUF-CMA security, who is given a public key ${pk}^{}$ and a signing oracle $O$ , aims to find a forgery $σ^{}$ . $C$ simulates the game for $A$ as follows.
Setup. $F$ sets up the game for $A$ by creating n users with the corresponding block identifiers and biometrics. $F$ sets up user i’s enrolled block as $({pk}^{}, SS (s_{i}, w_{i}))$ , where sketch is $SS (w_{i}, {sk}_{i}) = A \cdot s_{i} + w_{i}, s_{i} \in Z_{q}^{n}$ . $F$ also honestly generates public/secret key pairs and sketches as Enrollment specified for n-1 users. Eventually, $F$ sends all enrolled real/dummy public keys and sketches to $A$ . Note that $A$ cannot link the simulated sketch $SS (s_{i}, w_{i})$ to the public key ${pk}^{}$ since $A$ is not allowed to access user i’s biometrics $w_{i}$ .

Training. $F$ answers $A$ ’s queries as follows.

If $A$ issues a Send query in the form of $(n_{j}, C_{(i, 2)}^{})$ to $F$ , $F$ chooses a response randomness $n_{i}$ first, then $F$ simulates the protocol transcript $T_{i} = (m_{(i, j)}, σ_{i}^{'})$ as follows

invoke the signing oracle $O$ to obtain a message-signature pair $(m_{(i, j)}, σ_{i})$ , where $m_{(i, j)} = (n_{i}, n_{j}, Request)$ ;

obtain the correct offset $Δ (s_{i})$ from $C_{(i, 2)}^{}$ , where $C_{(i, 2)}^{}$ includes a ( $L + 1$ size) set of (re-randomized) real and dummy sketches. Note that the real sketch is $SS (s_{i}^{'}, w_{i}) \leftarrow SS (s_{i}, w_{i}) + A \cdot Δ (s_{i})$ ;

generate a signature $σ_{i}^{'} \leftarrow M_{Σ} (p p, {pk}^{}, σ_{i}, Δ (s_{i}))$ by using the deterministic algorithm $M_{Σ}$ described in Section 2.2; Note that ${sk}_{i}^{'} \leftarrow H (s_{i}^{'})$ .

return $(m_{(i, j)}, σ_{i}^{'})$ to $A$ .

If $A$ issues a Secret Key Reveal query to an instance oracle $Π_{{pk}^{}}^{i}$ , then $F$ returns a re-randomized secret key ${sk}_{i}^{'}$ to $A$ . Since $A$ is not allowed to reveal the enrolled secret key $Dlog ({pk}^{})$ , the simulation is perfect.

When $Forge$ event occurs (i.e., $A$ outputs $(m^{}, \underline{σ^{^{'}}}, C_{(i, 2)}^{^{'}})$ , where $C_{(i, 2)}^{^{'}} = {SS (s_{i}^{^{'}}, w_{i})}$ ), $F$ checks whether:
the Forge event happens at g-th session;

the message-signature pair $(m^{}, \underline{σ^{^{'}}})$ was not previously simulated by $C$ , where $m^{} = (n_{i}, n_{j}, Request)$ ;

verifies $Σ . Verify ({pk}^{^{'}}, m^{}, \underline{σ^{^{'}}}) = 1$ , where ${pk}^{^{'}} \leftarrow {pk}^{} \cdot KG’ (p p, Δ ({sk}^{}))$ and $Δ ({sk}^{})$ derives from $C_{(i, 2)}^{^{'}}$ that includes a (L+1 size) set of (re-randomized) real/dummy sketches. Note that $Δ ({sk}^{})$ is the correct “offset” between $Dlog ({pk}^{^{'}})$ and $Dlog ({pk}^{})$ .
If all the above conditions hold, $F$ confirms that it as a successful forgery from $A$ , then $F$ extracts the forgery via $\underline{σ^{}} \leftarrow M_{Σ} (p p, {pk}^{}, \underline{σ^{^{'}}}, Δ ({sk}^{}))$ using the homomorphic property of Σ. To this end, $F$ outputs $\underline{σ^{}}$ as its own forgery; Otherwise, $F$ aborts the game. Therefore, we have $\begin{matrix} (6) & | \Pr [Forge] | ⩽ {Adv}_{F}^{EUF-CMA} (λ) . \end{matrix}$
It is easy to see that in game $G_{5}$ , $A$ has no advantage, i.e., $\begin{matrix} (7) & {Adv}_{5}^{pBRUA} = 0 . \end{matrix}$

Combining the above results together, we have $\begin{array}{rcl} {Adv}_{A}^{pBRUA} (λ) & ⩽ & n \cdot m^{2} / 2^{λ} + m [n \cdot {Adv}_{C}^{{D-LWE}_{q, n_{0} - k, m_{0}, χ}} (λ) + {Adv}_{C}^{H} (λ) + {Adv}_{F}^{EUF-CMA} (λ)] . □ \end{array}$

Theorem 5.2.
The proposed pBRUA achieves strong privacy if the family of universal hash functions $H \leftarrow {H_{z} : Z_{q}^{n_{0}} \to Z_{q}}_{z \in Z}$ is ϵ-statistically secure, the underlying computational fuzzy extractor is IND secure, public key encryption scheme is IK-CPA secure, and the access pattern under uORAM protocol is computationally IND secure.
Proof.
We define a sequence of games ${G_{i}}$ and let ${Adv}_{i}^{pBRUA}$ denote the advantage of the adversary $A$ in game $G_{i}$ . We also highlight the differences between adjacent games by underline. We assume the Challenge stage between adversary $A$ and challenger $C$ is executed in a specific time-window.
$G_{0}$ : This is the original game for user anonymity security.

$G_{1}$ : This game is identical to game $G_{1}$ except that at the Challenge stage, we replace the real sketch $SS (s_{i}, w_{i})$ (i.e., $p_{i}$ ) by a random vector $r \in Z_{q}^{m_{0}}$ . Below we show the difference between $G_{0}$ and $G_{1}$ is negligible under the assumption that the computational fuzzy extractor (FE) is IND secure.

Let $C$ denote an attacker, who is given a common public matrix $A$ and two sketches $({pk}_{0}, {pk}_{1})$ ( $pk \leftarrow A \cdot X + χ$ ), aims to break the IND security of the computational FE. $C$ simulates the game for $A$ as follows.
Setup. $C$ sets up the game for $A$ by creating n users with corresponding block identifiers ${{ID}_{i}}$ and leaf identifiers ${{leaf}_{{ID}_{i}}}$ . $C$ sets the common public matrix in the system as $A$ . $C$ randomly chooses users $i, j$ from user set $U$ and sets the enrolled sketches as $p_{i} = {pk}_{0}, p_{j} = {pk}_{1}$ , and generates biometrics and sketches for other users. In addition, $C$ honestly generates enrolled public/secret key pairs ${{pk}_{i}, {sk}_{i}}$ for n users.

Training. If $A$ issues a Send query in the form of ${{pk}_{i}, p_{i}}$ (assuming the bucket includes a real block) to user i during EarlyReshuffles, then $C$ performs the following steps
re-randomize the received real/dummy blocks to ${{pk}_{i}^{'}, p_{i}^{'}}$ by using the homomorphic property of public key and computational FE respectively; Note that $p_{i}^{'}$ is derived from $p_{i}$ .

reshuffle the updated blocks according to the random offset which is based on PRP;

encrypt the ${ID}_{i}$ , random offset and leaf identifier ${leaf}_{{ID}_{i}}$ under enrolled public key ${pk}_{i}$ , and generate the Bucket MetaData;

write back to the specified bucket as EarlyReshuffles operation specified.
If $A$ issues a Send query in the form of $({p_{i}^{'}}, n_{j})$ (the set ${p_{i}^{'}}$ includes one real sketch and the involving dummy sketches) to user i, then $C$ performs the simulation as follows.
choose the randomness $n_{i}$ as response;

simulate the message-signature pair $(m_{(i, j)}, σ_{i}^{})$ using user i’s enrolled secret key and correct offset which derives from two re-randomized sketches ${p_{i}}$ and ${p_{i}^{'}}$ .

perform the Evict operation.
Note that $C$ can easily identify the real block by the enrolled public key ${pk}_{i}$ , and meanwhile, $C$ records the re-randomized real public key ${pk}_{i}^{'}$ . Similarly, $C$ simulates the response of user j using the same method as above.

Challenge. If $A$ issues a Send query in the form of ${{pk}_{i}, p_{i}}$ (include a re-randomized block of user i) to challenge user ${pk}_{b}$ during EarlyReshuffles, then $C$ updates (re-randomizes) the received real/dummy blocks to ${\underline{({pk}_{i}^{'}, c^{^{'}})}, ({pk}_{l}, p_{l})}$ ( $l \neq i$ ), where the re-randomized ciphertext $c^{^{'}}$ derives from a challenge ciphertext $\underline{c^{}}$ due to the linearity property of computational FE. Note that $\underline{c^{}}$ is the challenge ciphertext on message $m^{}$ (the message is the offset between two re-randomized sketches). $C$ performs the simulation of ${pk}_{b}$ during Evict operation using the same method described above. Similarly, $C$ simulates the response of ${pk}_{b}$ using the same method when $A$ issues a Send query that includes a real block of user j.
Finally, $C$ outputs whatever $A$ outputs. If $A$ guesses the random bit correctly, then $C$ can break the IND security of computational FE. Since at most n users involved in the system, hence we have $\begin{matrix} (8) & | {Adv}_{0}^{pBRUA} - {Adv}_{1}^{pBRUA} | ⩽ n \cdot {Adv}_{C}^{FE} (λ) . \end{matrix}$

$G_{2}$ : This game is identical to game $G_{1}$ except that at the Challenge stage, we replace the real secret key ${sk}_{i}$ by a random key $r \in Z_{q}$ . By following the same analysis as described in game $G_{4}$ of previous proof, we have $\begin{matrix} (9) & | {Adv}_{1}^{pBRUA} - {Adv}_{2}^{pBRUA} | ⩽ {Adv}_{C}^{H} (λ) . \end{matrix}$

$G_{3}$ : This game is identical to game $G_{2}$ except that at the Challenge stage, we replace the real public key ${pk}_{i}$ by a random key $r \in Z_{q}$ . Below we show the difference between $G_{2}$ and $G_{3}$ is negligible under the assumption that the public key encryption (PKE) scheme is IK-CPA secure.

Let $C$ denote an attacker, who is given two public key pair $({pk}_{0}, {pk}_{1})$ , aims to break the IK-CPA security of the PKE. $C$ simulates the game for $A$ as follows.
Setup. $C$ sets up the game for $A$ by creating n users with corresponding biometrics ${w_{i}}$ and sketches $p_{i}$ (i.e., ${SS (s_{i}, w_{i})}$ ). $C$ randomly chooses users $i, j$ from user set $U$ and sets ${pk}_{i} = {pk}_{0}, {pk}_{j} = {pk}_{1}$ , and generates public/secret key pair for other users honestly. In addition, $C$ honestly generates block identifiers ${{ID}_{i}}$ and leaf identifiers ${{leaf}_{{ID}_{i}}}$ for n users in the system.

Training. If $A$ issues a Send query in the form of either ${{pk}_{i}, p_{i}}$ or $({p_{i}^{'}}, n_{j})$ to user i, then $C$ performs the simulation by following the protocol specification honestly. In particular, $C$ simulates the message-signature pair $(m_{(i, j)}, σ_{i}^{})$ using the method as described in [36], where $m_{(i, j)} = (n_{i}, n_{j}, Request)$ . Note that $C$ can obtain the (one-time) public key ${pk}_{i}^{}$ ( ${pk}_{i}^{}$ is derived from ${pk}_{i}$ ) since the correct offset can be computed from the received real/dummy sketches. $C$ simulates the response of user j using the same method.

Challenge. If $A$ issues a Send query in the form of ${{pk}_{i}, p_{i}}$ to challenge user ${pk}_{b}$ during EarlyReshuffles, then $C$ simulates the ciphertext stored in the Bucket MetaData as $\underline{c^{}}$ , where the challenge ciphertext $\underline{c^{}}$ is on message $m^{}$ (e.g., $m^{} \leftarrow ({ID}_{i}, offset, {leaf}_{{ID}_{i}})$ ) obtained from his challenger. $C$ honestly performs the simulation of ${pk}_{b}$ during Evict operation according to the protocol specification. Similarly, $C$ can simulate the response of ${pk}_{b}$ when $A$ issues a Send query that includes a real block of user j.
Finally, $C$ outputs whatever $A$ outputs. If $A$ guesses the random bit correctly, then $C$ can break the IK-CPA security of PKE. Since at most $log N$ buckets involved during the EarlyReshuffles operation, we have $\begin{matrix} (10) & | {Adv}_{2}^{pBRUA} - {Adv}_{3}^{pBRUA} | ⩽ log N \cdot {Adv}_{C}^{PKE} (λ) . \end{matrix}$

$G_{4}$ : This game is identical to game $G_{3}$ except that at the Challenge stage, we replace the real block identifier ${ID}_{i}$ by a random string. Below we show the difference between $G_{3}$ and $G_{4}$ is negligible under the assumption that the access patten under uORAM protocol is computationally IND secure.

Let $C$ denote an attacker, who is given two access patterns $(\overset{\leftarrow}{y_{0}}, \overset{\leftarrow}{y_{1}})$ with equal length in the time-window ϱ such that $\overset{\leftarrow}{y_{0}} = {({op}_{i}, {ID}_{i}, {data}_{i}, {time}_{i})}$ , aims to break the IND security of uORAM protocol. $C$ simulates the game for $A$ as follows.
Setup. $C$ sets up the game for $A$ by creating n users with corresponding biometrics ${w_{i}}$ , sketches $p_{i}$ (i.e., ${SS (s_{i}, w_{i})}$ ) and public/secret key pairs ${({pk}_{i}, {sk}_{i})}$ . In addition, $C$ randomly chooses users $i, j$ from user set $U$ and sets user $i, j$ ’s access pattern as $(\overset{\leftarrow}{y_{0}}, \overset{\leftarrow}{y_{1}})$ respectively, and generates both block identifier and leaf identifier for other users honestly. Note that user i’s block identifier is implicitly sets as ${ID}_{i} = {ID}_{0}$ with respect to access pattern $\overset{\leftarrow}{y_{0}}$ (assuming a user has one unique block identifier ${ID}_{0}$ ). Also note that $C$ generates user $i, j$ ’s leaf identifiers.

Training. If $A$ issues a Send query in the form of either ${{pk}_{i}, p_{i}}$ or $({p_{i}^{'}}, n_{j})$ to user i, then $C$ simulates the response of user i by following the protocol execution honestly. In particular, $C$ perfectly simulates the message-signature pair using user i’s secret key and biometrics. $A$ faithfully follows the access pattern $\overset{\leftarrow}{y_{0}}$ w.r.t. user i, the same rule applies to user j.

Challenge. If $A$ issues a Send query in the form of either ${{pk}_{i}, p_{i}}$ or $({p_{i}^{'}}, n_{j})$ to challenge user ${pk}_{b}$ , then $C$ constructs an equal length access pattern $\underline{\overset{\leftarrow}{y_{0}^{}}}$ which includes a random block identifier $\underline{r}$ . Then $C$ sends two access patterns to his challenge oracle and obtains a challenge sequence of operations under uORAM protocol $uORAM (\overset{\leftarrow}{y_{b}})$ and returns it to $A$ . In addition, $C$ simulates the message-signature pair of ${pk}_{b}$ using user i’s secret key and correct offset which derives from a ( $L + 1$ size) set of real/dummy sketches that obtained from its challenger. Note that $C$ can also simulate the response of ${pk}_{b}$ when $A$ issues a Send query that includes a real block of user j.
Finally, $C$ outputs whatever $A$ outputs. If $A$ guesses the random bit correctly, then $C$ can break the computationally IND security of uORAM. Hence we have $\begin{matrix} (11) & | {Adv}_{3}^{pBRUA} - {Adv}_{4}^{pBRUA} | ⩽ {Adv}_{C}^{uORAM} (λ) . \end{matrix}$

It is easy to see that in game $G_{4}$ , $A$ has no advantage, i.e., $\begin{matrix} (12) & {Adv}_{4}^{pBRUA} = 0 . \end{matrix}$

Combining the above results together, we have $\begin{array}{rcl} {Adv}_{A}^{pBRUA} (λ) & ⩽ & n \cdot {Adv}_{C}^{FE} (λ) + {Adv}_{C}^{H} (λ) + log N \cdot {Adv}_{C}^{PKE} (λ) + {Adv}_{C}^{uORAM} (λ) . \end{array}$
□

6. Conclusion

In this work, we have proposed the first general framework of strong privacy-preserving remote user authentication based on a new uORAM protocol and computational fuzzy extractors. The proposed general framework achieves the strong privacy against an honest-but-curious authentication server. In particular, the general framework supports a constant bandwidth cost in the challenge-response phase of user authentications. We have proved the security of the proposed general framework under standard assumptions. As for the future work, we would try to design a strong privacy-preserving user authentication that (1) handles multiple user requests in a concurrent and asynchronous manner [6,38]; or (2) secures against malicious servers [3,35].

Footnotes

Trivial solution

Suppose that we use a single instance of Path ORAM as a black-box with N records of n users ( $N ⩾ n$ ), and we show that we can achieve strong privacy and log-linear time-complexity, not constant bandwidth. Specifically, we let the authentication server construct a binary tree, in which each leaf/non-leaf node is a bucket, each bucket contains a certain number of records and each record contains a user’s enrolled verification key and helper data (or sketch). Note that helper data and a cryptographic key are derived from a user’s biometrics, and the same key can be extracted by inputting a “nearby” biometrics and the helper data [16]. In particular, the cryptographic key is used to derive a signing/verification key pair. The idea is, upon an authentication request, the authentication server retrieves a set of records which reside in the same tree path from the database and returns them back to the user. The authorized user first obtains a cryptographic key from her “nearby” biometrics and her enrolled helper data that are included in the returned helper data set, and then generates an anonymous signature (e.g., group signature [10] or ring signature [44]) using a signing key derived from the cryptographic key. The authentication server verifies the anonymous signature under a number of verification keys that are involved in the returned records set. This solution naturally achieves the log-linear time-complexity due to the structure of a binary tree. However, the bandwidth overhead has the log-linear time-complexity in the number of records N.

To highlight the advantage of uORAM over Path/Ring ORAM in user authentications, we present the following points. First, Path ORAM protocol cannot support a constant bandwidth because the server simply returns all blocks in a tree path to the client. In uORAM (and Path ORAM), the server returns only one block from each bucket on the path, so that eliminating the dependence on the bucket size. Second, Path ORAM cannot support an EarlyReshuffles procedure. The uORAM utilizes an EarlyReshuffles procedure (same as Ring ORAM) to reshuffle the buckets, because the dummy blocks may have been updated too many times. In other words, the user must perform an EarlyReshuffles procedure before actual user authentication, in order to ensure the unlinkability across multiple authentications. Third, Ring ORAM is not suitable for user authentications, due to its Evict procedure (as discussed in the Related Work). Therefore, we must select the ideas from both Path ORAM and Ring ORAM to construct our uORAM, which should be particularly suitable for user authentications. We stress that the constant bandwidth in the challenge-response phase can be achieved if and only if we exploit the LWE-based fuzzy extractor. The benefit is to let the user authenticate herself to the server in a practical manner. In other words, the user can perform a fast login during challenge-response phase, while the early-reshuffle and post-reshuffle phases are used to maintain strong privacy. Lastly, the overall bandwidth in the whole user authentication can be summarized to read and write all real blocks (also includes some “updated” dummy blocks) in a tree path twice.

References

Akavia,

Goldwasser and

Vaikuntanathan, Simultaneous hardcore bits and cryptography against memory attacks, in: TCC, 2009, pp. 474–495.

Apon,

Cho,

Eldefrawy and

Katz, Efficient, reusable fuzzy extractors from LWE, in: International Conference on Cyber Security Cryptography and Machine Learning, 2017, pp. 1–18.

Backes,

Herzberg,

Kate and

Pryvalov, Anonymous RAM, in: ESORICS, 2016, pp. 344–362.

Barni,

Bianchi,

Catalano,

Di Raimondo,

Donida Labati,

Failla,

Fiore,

Lazzeretti,

Piuri,

Scotti et al., Privacy-preserving fingercode authentication, in: Proceedings of the 12th ACM Workshop on Multimedia and Security, 2010, pp. 231–240. doi:10.1145/1854229.1854270.

Bellare,

Boldyreva,

Desai and

Pointcheval, Key-privacy in public-key encryption, in: ASIACRYPT, 2001, pp. 566–582.

Bindschaedler,

Naveed,

Pan,

Wang and

Huang, Practicing oblivious access on cloud storage: The gap, the fallacy, and the new way forward, in: ACM CCS, 2015, pp. 837–849.

Blazy,

Fuchsbauer,

Pointcheval and

Vergnaud, Signatures on randomizable ciphertexts, in: PKC, 2011, pp. 403–422.

Boyen, Reusable cryptographic fuzzy extractors, in: ACM CCS, 2004, pp. 82–91.

Boyen,

Dodis,

Katz,

Ostrovsky and

A.D.

Smith, Secure remote authentication using biometric data, in: EUROCRYPT, Lecture Notes in Computer Science, Vol. 3494, 2005, pp. 147–163.

10.

Chaum and

Van Heyst, Group signatures, in: EUROCRYPT, 1991, pp. 257–265.

11.

Chor,

Goldreich,

Kushilevitz and

Sudan, Private information retrieval, in: Proceedings of IEEE 36th Annual Foundations of Computer Science, 1995, pp. 41–50. doi:10.1109/SFCS.1995.492461.

12.

Cramer and

Shoup, A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack, in: CRYPTO, 1998, pp. 13–25.

13.

J.L.

DautrichJr.,

Stefanov and

Shi, Burst ORAM: Minimizing ORAM response times for bursty access patterns, in: USENIX, 2014, pp. 749–764.

14.

De Capitani di Vimercati,

Foresti,

Paraboschi,

Pelosi and

Samarati, Shuffle index: Efficient and private access to outsourced data, ACM Transactions on Storage (TOS) 11(4) (2015), 19.

15.

Devadas,

van Dijk,

C.W.

Fletcher,

Ren,

Shi and

Wichs, Onion ORAM: A constant bandwidth blowup oblivious RAM, in: TCC, 2016, pp. 145–174.

16.

Dodis,

Reyzin and

Smith, Fuzzy extractors: How to generate strong keys from biometrics and other noisy data, in: EUROCRYPT, 2004, pp. 523–540.

17.

Doerner and

Shelat, Scaling ORAM for secure computation, in: ACM CCS, 2017, pp. 523–535.

18.

Döttling and

Müller-Quade, Lossy codes and a new variant of the learning-with-errors problem, in: EUROCRYPT, 2013, pp. 18–34.

19.

ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Transactions on Information Theory 31(4) (1985), 469–472. doi:10.1109/TIT.1985.1057074.

20.

Erkin,

Franz,

Guajardo,

Katzenbeisser,

Lagendijk and

Toft, Privacy-preserving face recognition, in: PET, 2009, pp. 235–253.

21.

Fuller,

Meng and

Reyzin, Computational fuzzy extractors, in: ASIACRYPT, 2013, pp. 174–193.

22.

Goldreich and

Ostrovsky, Software protection and simulation on oblivious RAMs, JACM 43(3) (1996), 431–473. doi:10.1145/233551.233553.

23.

Huang,

Malka,

Evans and

Katz, Efficient privacy-preserving biometric identification, in: NDSS, 2011.

24.

Is your information on mobile health apps safe?, https://www.cybrary.it/2018/05/information-mobile-health-apps-safe/.

25.

M.S.

Islam,

Kuzu and

Kantarcioglu, Access pattern disclosure on searchable encryption: Ramification, attack and mitigation, in: NDSS, 2012, p. 12.

26.

Juels and

Wattenberg, A fuzzy commitment scheme, in: ACM CCS, 1999, pp. 28–36.

27.

Kamp and

Zuckerman, Deterministic extractors for bit-fixing sources and exposure-resilient cryptography, SIAM Journal on Computing 36(5) (2006), 1231–1247. doi:10.1137/S0097539705446846.

28.

Li,

Guo,

Mu,

Susilo and

Nepal, Fuzzy extractors for biometric identification, in: ICDCS, 2017, pp. 667–677.

29.

Maas,

Love,

Stefanov,

Tiwari,

Shi,

Asanovic,

Kubiatowicz and

Song, Phantom: Practical oblivious computation in a secure processor, in: ACM CCS, 2013, pp. 311–324.

30.

Maffei,

Malavolta,

Reinert and

Schröder, Privacy and access control for outsourced personal records, in: Security and Privacy (SP), 2015, pp. 341–358.

31.

Matsuda,

Takahashi,

Murakami and

Hanaoka, Fuzzy signatures: Relaxing requirements and a new construction, in: ACNS, 2016, pp. 97–116.

32.

Murakami,

Ohki and

Takahashi, Optimal sequential fusion for multibiometric cryptosystems, Information Fusion 32 (2016), 93–108. doi:10.1016/j.inffus.2016.02.002.

33.

Regev, On lattices, learning with errors, random linear codes, and cryptography, JACM 56(6) (2009), 34. doi:10.1145/1568318.1568324.

34.

Ren,

C.W.

Fletcher,

Kwon,

Stefanov,

Shi,

Van Dijk and

Devadas, Constants count: Practical improvements to oblivious RAM, in: USENIX, 2015, pp. 415–430.

35.

Sahin,

Zakhary,

El Abbadi,

Lin and

Tessaro, Taostore: Overcoming asynchronicity in oblivious data storage, in: Security and Privacy (SP), 2016, pp. 198–217.

36.

C.-P.

Schnorr, Efficient identification and signatures for smart cards, in: CRYPTO, 1989, pp. 239–252.

37.

Shi,

T.H.

Chan,

Stefanov and

Li, Oblivious RAM with O((log N)3) worst-case cost, in: ASIACRYPT, 2011, pp. 197–214.

38.

Stefanov and

Shi, Oblivistore: High performance oblivious cloud storage, in: Security and Privacy (SP), 2013, pp. 253–267.

39.

Stefanov,

Shi and

D.X.

Song, Towards practical oblivious RAM, in: NDSS, 2012.

40.

Stefanov,

Van Dijk,

Shi,

Fletcher,

Ren,

Yu and

Devadas, Path ORAM: An extremely simple oblivious RAM protocol, in: ACM CCS, 2013, pp. 299–310.

41.

Takahashi,

Matsuda,

Murakami,

Hanaoka and

Nishigaki, A signature scheme with a fuzzy private key, in: ACNS, 2015, pp. 105–126.

42.

Wang,

Chan and

Shi, Circuit ORAM: On tightness of the Goldreich–Ostrovsky lower bound, in: ACM CCS, 2015, pp. 850–861.

43.

Wen and

Liu, Robustly reusable fuzzy extractor from standard assumptions, in: ASIACRYPT, 2018, pp. 459–489.

44.

Zhang and

Kim, ID-based blind signature and ring signature from pairings, in: ASIACRYPT, 2002, pp. 533–547.

A new framework for privacy-preserving biometric-based remote user authentication

Abstract

Keywords

1. Introduction

1 It is possible to use other alternative solutions to achieve access privacy such as private information retrieval [11] and shuffle index [14], while the ORAM based solution may achieve lower bandwidth complexity.

2. Preliminaries

2.1. Complexity assumptions

Definition 2.1 (Decisional LWE [33]).

Lemma 2.1. If D-LWE q , n 0 − k , m 0 , χ is ( ϵ , s sec ) secure, then δ D s sec ′ ( ( X 1 , … , k , A , A · X + χ ) , ( U , A , A · X + χ ) ) ⩽ ϵ , where U ∈ Z q k and X 1 , … , k denotes the first k coordinates of x and s sec ′ ≈ s sec − n 0 3 . 2.2. Digital signatures

2.3. Universal hash function

3.1. Security definition

Definition 3.1 (Security Definition).

4. The proposed general framework

4.1. Definition

Footnotes

Trivial solution

References

¹
It is possible to use other alternative solutions to achieve access privacy such as private information retrieval [11] and shuffle index [14], while the ORAM based solution may achieve lower bandwidth complexity.