Lattice-based remote user authentication from reusable fuzzy signature

Abstract

In this paper, we introduce a new construction of reusable fuzzy signature based remote user authentication that is secure against quantum computers. We investigate the reusability of fuzzy signature, and we prove that the fuzzy signature schemes provide biometrics reusability (aka. reusable fuzzy signature). We define formal security models for the proposed construction, and we prove that it achieves user authenticity and user privacy. The proposed construction ensures: 1) a user’s biometrics can be securely reused in remote user authentication; 2) a third party having access to the communication channel between a user and the authentication server cannot identify the user.

Keywords

Lattice-based cryptography fuzzy signature biometrics reusability user privacy

1. Introduction

Fuzzy signature (FS), also known as signature with fuzzy secret key [22,28], is a new type of digital signature that allows a signature to be generated using biometrics as a signing key, without relying on any additional data (e.g., the helper data as used in fuzzy extractor [9]). FS can further be explored in a reusable setting: reusable fuzzy signature (RFS), which deals with biometrics reuse. This is because a user may generate multiple message-signature pairs under various signing keys, but with noisy versions of the same biometrics. Reusability allows the security of the generated signature used in an application to remain secure even if some of the generated signatures used in other applications are compromised (e.g., in case the signing keys are leaked to attackers). Therefore, biometrics reusability is an essential security property required in RFS, but there is no such security guarantee in [22,28].

The RFS is significantly useful in many real-world applications, such as biometric-based remote user authentication [3,6,7,20,30]. We consider a setting where user Alice wishes to authenticate herself to server Bob using her biometrics remotely. A traditional method is to use digital signature with fuzzy extractor [6,7,20,30]. That is, Alice relies on her enrolled helper data stored somewhere (e.g., server, smart card, and USB token) to derive a signing key for generating a signature on a nonce message, then Bob verifies the message-signature pair under Alice’s enrolled verification key. In RFS, Alice’s signature additionally includes a new verification key (her signature is generated by a new signing key), and a new helper data, in which the new helper data is derived from the new signing key and her noisy biometrics. Bob verifies the message-signature pair under Alice’s new verification key and checks whether the new verification key is linked to Alice’s enrolled verification key. This checking process relies on Alice’s new and enrolled helper data, and the successful checking requires that Alice’s noisy biometrics and her enrolled biometrics are close enough. A crucial point to stress is that Alice’s signature generation does not depend on her enrolled helper data, which is the key difference between digital signature with fuzzy extractor [6,7,20,30] and RFS.

The security and privacy of RFS used in remote user authentication are also essential. First, lattice-based cryptography resistance to quantum computers has been extensively studied in the literature [14,23–25]. We note that remote user authentication that exploits prior fuzzy signatures [22,28] is not secure, as a quantum computer can efficiently solve some hard mathematical problems such as discrete logarithm (DL) problem [27]. So, the DL-based fuzzy signature schemes proposed in [22,28] are not desired in the post-quantum era. Second, user’s privacy is compromised if we apply fuzzy signatures [22,28] to remote user authentication. Specifically, multiple message-signature pairs from a same user Alice can be easily linked by a third party eavesdropping the communication channel, since the fuzzy signatures [22,28] are publicly verifiable (i.e., anyone has Alice’s enrolled verification key can verify Alice’s message-signature pairs). Therefore, the main goal of this work is to design reusable fuzzy signature based remote user authentication (RFS-RUA) that satisfies resistance to quantum computers, biometrics reusability, and privacy guarantee against eavesdroppers.

Technical Challenges. It is a non-trivial task to design a lattice-based RFS for RUA that is secure against quantum computers. We use the lattice-based digital signatures without trapdoors [11,21], because this line of research supports a simple and efficient signing process [21] compared to lattice-based trapdoor signatures [14]. However, in the design of lattice-based signatures without trapdoors, the signature generation is independent of the signing key. This mechanism may contradict to the homomorphic property required in RFS, which means that the difference (“shift”) between two signatures is identical to the difference between two signing/verification key pairs [22,28]. Such homomorphic property allows Bob to find the correct difference between Alice’s new verification key and her enrolled verification key. Alice’s message-signature pair can be confirmed as valid because she is the only party who can produce the correct difference between her new signing key and her enrolled signing key.

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

New Construction. We propose a new construction of remote user authentication that is built on top of lattice-based digital signatures [11,21], reusable fuzzy extractors from learning with errors (LWE) [2,32], a family of universal hash functions, and lattice-based public key encryptions.

Quantum Resistant. The proposed construction can withstand quantum computers due to the lattice-based cryptographic primitives we used. Its provable security relies on the worst-case intractability of standard lattice problems.

Biometrics Reusability. We formulate the security definition of RFS. We prove that the lattice-based RFS achieves biometrics reusability since the underlying LWE-based fuzzy extractors are reusable. In particular, the construction of RFS is the first cryptographic primitive that supports Hamming distance.

Privacy Protection. We show a user privacy model to prevent the eavesdroppers from identifying any authorized user or linking any authorized user’s multiple sessions. We prove that the proposed construction achieves user privacy under standard assumptions.

Overview of Techniques. We now explain our key technical insights. First, we characterize the homomorphic property of lattice signatures without trapdoors [11,21]. We discover that these lattice signatures have the desired homomorphic property, such that the “shift” between two lattice signatures is identical to the “shift” between two signing/verification key pairs. Second, putting all building blocks together, which include lattice signatures [11,21], reusable fuzzy signatures [2,32], and a family of universal hash functions, we can construct a lattice-based RFS that achieves biometrics reusability. Third, we use the lattice-based public-key encryptions to ensure privacy guarantee, where the validity of lattice-based RFS is verified by the authentication server only. Specifically, Alice’s identity is encrypted under the public key of Bob. After extracting Alice’s encrypted identity, Bob can identify her enrolled verification key and helper data. Then, he verifies Alice’s lattice-based RFS under a new verification key, which is derived from the enrolled verification key, the enrolled and new helper data.

1.1. Related work

Fuzzy Signatures. The concept of fuzzy signature was firstly introduced by Takahashi et al. [28], which is a signature scheme that inputs fuzzy data such as biometrics as a signing key. Specifically, the generation of a signature does not rely on additional data such as helper data (or sketch). The proposed generic construction is built on top of a signature scheme with homomorphic (see Section 2.4) properties regarding keys and signatures, and a linear sketch. It is proven secure in the standard model. To relax some requirements on the building blocks used in the generic construction of [22], Matsuda et al. proposed a new generic construction using some relaxed building blocks. For example, Waters signature scheme [31] is replaced by Schnorr signature scheme [26].

The input biometrics of linear sketch in [28] is assumed to be uniformly distributed over metric space. To relax such strong assumption on fuzzy data, Matsuda et al. [22] require only high min-entropy on the distribution of biometrics. Specifically, they consider linear sketches as real numbers that include integer and decimal (i.e., secret key and biometrics) parts. If the difference between two linear sketches is less than a threshold t (a positive real number), then a difference algorithm (i.e., DiffRec) can extract the correct difference (may include noise) between two linear sketches.

Yasuda et al. [34] introduced the “recovering attacks” to recover both the secret key and biometrics from linear sketch. They claim that the “integer plus decimal” format is vulnerable to such attacks. In addition, they provided a trivial countermeasure (add small noisy data to the sketch) with informal security analysis. Meanwhile, Takahashi et al. [29] (merged version of [22,28]) also provided the treatment to avoid the “recovering attacks”. The remedy is to add a “rounding-down” operation (or truncation) on the decimal part of the real numbers. However, such extra truncation would bring a correctness loss to the proposed constructions in [22,28].

Instead of using real numbers (with “integer plus decimal” format) to represent and process fuzzy data. In this work, we take binary strings over Hamming distance as fuzzy data input such as Iriscode [16]. We notice that constructing fuzzy signatures from Hamming distance is an open problem, which is pointed out by prior works [22,29].

Lattice Signatures. A lattice-based signature scheme with provable security was first constructed by Gentry et al. [14]. Their construction is based on “hash-and-sign” paradigm, and its security relies on the worst-case hardness of standard lattice problems such as small integer solution (SIS). To achieve more practical and efficient constructions, another line of research on lattice-based digital signatures relies on the Fiat–Shamir heuristic [12] such as [11,21]. Their constructions are Schnorr-like identification protocols whose security is based on SIS or LWE, and the efficiency relies on a rejection sampling (see Section 2.4) rather than the pre-image sampling used in [14]. In this work, we use lattice-based signature schemes [11,21] as our building blocks.

Reusable Fuzzy Extractor. Fuzzy extractor (FE) is one of the promising approaches to construct a biometric-based remote user authentication [6,7,20,30]. Juels and Wattenberg [18] introduced a cryptography primitive called “fuzzy commitment”. It is particularly useful for biometric-based remote authentication systems, because its error-correcting technique can correct certain errors within a suitable metric (Hamming distance). Dodis et al. [9] formally introduced the notions of “secure sketches” and “fuzzy extractors”. In particular, they provided concrete constructions of secure sketches and fuzzy extractors in three metrics (Hamming distance, set difference, and edit distance), and the constructions are information-theoretically secure.

Boyen [6] introduced an important notion: reusable fuzzy extractor. It states that a user can produce multiple secret/public string pairs using the same biometrics w, i.e., ${(R_{i}, P_{i})} \leftarrow Gen (w)$ . Later, Canetti et al. [8] proposed the first reusable FE from some low-entropy distributions. They particularly refined the security of strongly reusable FE, such that each $R_{i}$ remains secure even if all other secret strings $R_{j}$ ( $j \neq i$ ) are revealed.

Canetti et al. [8] proposed the first computational and information-theoretic secure FEs, Fuller et al. [13] constructed them from LWE [25]. In Fuller et al.’s construction, the entropy of the derived cryptographic key is the same as the entropy of the fuzzy biometrics from which the key is derived. However, their computational FE is not reusable. To achieve reusable FE from LWE, Apon et al. [2] provided a generic transformation to convert non-reusable (resp. weak reusable) fuzzy extractors to weak reusable (resp. strong reusable) ones. According to the definition of reusability [6,8], Apon et al. formalized both weak and strong reusability. Recently, Wen and Liu [32] proposed a new reusable and robust FE. Its reusability also follows the strong reusability defined in [2]. In this work, we follow the strong reusability defined in [2,32], where the “shifts” between many runs of $Gen (w)$ are controlled by the adversary (i.e., the perturbation attacks defined in [6]).

To highlight our distinction, we show the function (feature) difference between our proposed new construction and some existing works in Table 1: it shows that our proposed construction has quantum resistance, biometrics reusability, and user privacy. The new construction is proven secure in the random oracle model. We stress that the proposed RFS can be regarded as a step forward from fuzzy signatures [22,28] and fuzzy extractors [2,32] in the lattice-based setting. Besides, we present the commonly used notations in Table 2.

Table 1
The comparison between different functionalities of lattice-based signature (Sig), fuzzy extractor (FE), and fuzzy signature (FS) schemes. Reusability shows whether the biometrics reuse is formally addressed or not. User privacy means user’s privacy concern with respect to the eavesdroppers (see Appendix A). N/A means that the scheme did not consider this functionality

Functionality/Scheme [21] [13] [28] [22] [2] [32] Ours

Sig/FS/FE Sig FE FS FS FE FE FS

Reusability N/A × N/A N/A ✓ ✓ ✓

User Privacy × N/A × × N/A N/A ✓

Lattice Based ✓ ✓ × × ✓ ✓ ✓

Standard Model × ✓ ✓ × ✓ ✓ ×

Functionality/Scheme	[21]	[13]	[28]	[22]	[2]	[32]	Ours
Sig/FS/FE	Sig	FE	FS	FS	FE	FE	FS
Reusability	N/A	×	N/A	N/A	✓	✓	✓
User Privacy	×	N/A	×	×	N/A	N/A	✓
Lattice Based	✓	✓	×	×	✓	✓	✓
Standard Model	×	✓	✓	×	✓	✓	×

Table 2

Summary of notations

Notation	Meaning
$({s k}_{i}, {p k}_{i})$	User i’s key pair
$(w, w^{'})$	Enrolled biometrics/near-by biometrics
$dist (w, w^{'})$	Distance between biometrics w and $w^{'}$
$t \in R^{+}$	Threshold value (a positive real number)
$(R, P)$	Secret string/public string (helper data)
$SS (w, s k)$	Sketch (part of helper data P) with a secret key

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 the notion of RFS and prove its reusability. In Section 4, we first present the formal security models to capture the security requirements of the RFS-based remote user authentication, then we show the proposed construction. We present the security analysis in Section 5, and the paper is concluded in Section 6.

2. Preliminaries

In this section, we present the complexity assumptions and the underlying techniques, which will be used in our proposed reusable fuzzy signatures RFS.

2.1. Complexity assumptions

Definition 2.1 ( ${SIS}_{q, n, m, d}$ Distribution).

Given a random matrix $A \in Z_{q}^{n \times m}$ and a vector $X \in {- d, \dots, 0, \dots, d}^{m}$ , output $(A, A \cdot X)$ , where d denotes the absolute value of random integers.

Definition 2.2 (Decisional SIS [21]).

Given a pair $(A, t)$ such that $t = A \cdot X$ , a probabilistic polynomial-time (PPT) adversary aims to decide whether the pair is generated from real ${SIS}_{q, n, m, d}$ distribution, or whether it is uniformly generated from random distribution $Z_{q}^{n \times m} \times Z_{q}^{n}$ .

If $d ≫ q^{n / m}$ (high-density), then real ${SIS}_{q, n, m, d}$ distribution is statistically close to uniform distribution over $Z_{q}^{n \times m} \times Z_{q}^{n}$ , and there are many solutions X such that $A \cdot X = t$ . If $d ≪ q^{n / m}$ (low-density), then there is only one solution X.

Definition 2.3 (Decisional LWE [25]).

Given a matrix $A \in Z_{q}^{m \times n}$ , a vector $X \in Z_{q}^{n}$ , and an arbitrary distribution $χ \in Z_{q}^{m}$ , a PPT adversary aims to distinguish real distribution $(A, A \cdot X + χ)$ from random distribution over $(Z_{q}^{m \times n}, Z_{q}^{m})$ . The ${DLWE}_{q, n, m, χ}$ is ( $ϵ, s_{\sec}$ )-secure if no PPT adversary $D_{s_{\sec}}$ of size $s_{\sec}$ can distinguish the LWE instances from random ones except with probability ϵ, where $s_{\sec} = p o l y (λ)$ , and ϵ is a negligible function of the security parameter λ.

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

Lemma 2.1.
If ${DLWE}_{q, n - k, m, χ}$ 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}$ , $X_{1, \dots, k}$ denotes the first k coordinates of X, and $s_{\sec}^{'} \approx s_{\sec} - n^{3}$ .

2.2. Universal hash function

Let $H$ be a universal hash function family whose domain is $Z_{q^{n}}$ and whose range is $Z_{q}$ . Let $Z_{q^{n}}$ be a vector space, which consists of n dimensional of finite ring with prime order q. We define an isomorphism $ψ : {(Z_{q})}^{n} \to Z_{q^{n}}$ ( $ψ^{- 1}$ is its inverse), and $n \in N$ . Note that ${(Z_{q})}^{n} = Z_{q}^{n}$ . A family of universal hash functions is defined as $H = {H_{z} : Z_{q}^{n} \to Z_{q} | z \in Z_{q^{n}}}$ . Specifically, for each invertible element $z \in Z$ in the seed space $Z \in Z_{q^{n}}$ , define the hash function $H_{z}$ as follows: on input $x \in {(Z_{q})}^{n}$ , $H_{z} (x)$ computes $y \leftarrow ψ (x) \cdot z$ , where $“ \cdot^{″}$ denotes the multiplication in the extension field $Z_{q^{n}}$ . Let $(y_{1}, \dots, y_{n}) \leftarrow ψ^{- 1} (y)$ , and the output of $H_{z} (x)$ is $y_{1} \in Z_{q}$ . Since the isomorphism ψ between $Z_{q}^{n}$ and $Z_{q}^{n}$ 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} 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} \to Z_{q}}_{z \in Z}$ is universal, for any random variable W taking values in $Z_{q}^{n}$ 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}}$ 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 [ 9 ].

2.3. Computational fuzzy extractors

Let $m ⩾ n$ , and q be a prime number. The computational FE [13] consists of the following algorithms:

Gen: The algorithm takes $w \leftarrow M$ , and $A \in Z_{q}^{m \times n}$ , $x \in Z_{q}^{n}$ as input, outputs $(R, P)$ , where $M$ is a uniform distribution over $Z_{q}^{m}$ , and $(R, P) = [x_{1, \dots, n / 2}, (A, A \cdot x + w)]$ .

Rep: The algorithm takes as $(w^{'}, P)$ input, outputs $R = x_{1, \dots, n / 2}$ , where $P = (A, c)$ , $b = c - w^{'}$ , $x = {Decode}_{t} (A, b)$ , and $dist (w, w^{'}) ⩽ t$ .

The correctness of computational FE relies on the ${Decode}_{t} (A, b)$ algorithm, which is explicitly shown as follows.

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

Select $2 n$ distinct indices $i_{1}, \dots, i_{2 n} \leftarrow [1, \dots, m]$ .

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

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

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

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

Recall that $A \in Z_{q}^{m \times n}, b \in Z_{q}^{m}$ , and ${Decode}_{t}$ algorithm can correct at most $t = O (log n)$ errors (of Hamming distance) in a random linear code. Note that with probability at least $1 / p o l y (λ)$ , none of the $2 n$ rows selected in step 2 have errors (i.e., 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 is in the form of $SS (w, x) = A \cdot x + w$ , and satisfies the linearity defined in [22,28]. 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 [13], which takes $w \leftarrow M$ and a value $x \in Z_{q}^{n}$ as input, output a distribution over $Z_{q}^{m}$ . The detailed description of fuzzy extractor and secure sketch is referred to Appendix B.

The computational fuzzy extractors (FE) from LWE has an inherent property: “indistinguishability” (IND). Informally, given two sketches (part of helper string P), which are the “encryption” of 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 public sketches only). In addition, we discover that both computational FE [13] and its variant reusable FEs [2,32] have such inherent property.

Definition 2.4.
The IND experiment between an adversary $A$ and a simulator $S$ is defined below. $\begin{matrix} Experiment {Exp}_{F E}^{IND} (λ) \\ b \in {0, 1}, w_{b} \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 $S$ . We define the advantage of $A$ as $\begin{matrix} {Adv}_{A}^{IND} (λ) = | Pr [S \to 1] - 1 / 2 | . \end{matrix}$ A computational FE from LWE is IND secure if ${Adv}_{A}^{IND} (λ)$ is negligible in λ.
Lemma 2.3.
The computational fuzzy extractors from LWE achieves the IND security if the* ${DLWE}_{q, n, m, χ}$ assumption is $(ϵ, s_{\sec})$ secure.

Informally, we can think of the sketch $A \cdot x + w$ (part of helper string p) as an “encryption” of x that where decryption works from any close $w^{'}$ (i.e., decryption key). We can also think of any two “encryptions” $A_{0} \cdot x_{0} + w_{0}$ and $A_{1} \cdot x_{1} + w_{1}$ are indistinguishable by any third party without having decryption keys $(w_{0}^{'}, w_{1}^{'})$ .
Proof.

Fig. 1.
Description of adversary $S$ for the 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 $S$ to break the decisional LWE ( ${DLWE}_{q, n, m, χ}$ ) assumption. The algorithm $S$ has almost the same time complexity with $A$ . We first consider the shared public parameter by all users, i.e., $A_{0} = A_{1}$ . Then, we show the simulation differences when $A_{0} \neq A_{1}$ .

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

We then analyze the behaviour of $S$ on ${Exp}_{S}^{LWE-REAL}$ and ${Exp}_{S}^{LWE-RAND}$ respectively. In the ${Exp}_{S}^{LWE-REAL}$ , the input ( $A, A \cdot X + χ + w$ ) satisfies the Rep algorithm of FE described in Section 2.3, where w is uniformly distributed over a small interval. Notice that the computed distribution ( $A, A \cdot (X + u) + χ + w$ ) are valid and they are uniformly and independently distributed over $(Z_{q}^{m \times n}, 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}$ . Thus, $S$ 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} P_{0} \leftarrow A \cdot X + χ + w_{0} . ⊳ if b = 0 \\ P_{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}{l} Pr [{Exp}_{S}^{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}_{S}^{LWE-RAND}$ , the input distributions to $S$ in Fig. 1 are all uniformly distributed over $(Z_{q}^{m \times n}, Z_{q}^{m})$ . Therefore, the corresponding computed distribution above are also uniformly and independently distributed over $(Z_{q}^{m \times n}, Z_{q}^{m})$ . In particular, the challenge ciphertext is a random distribution over $(Z_{q}^{m \times n}, Z_{q}^{m})$ , and independent of bit b. Hence we have $\begin{array}{l} Pr [{Exp}_{S}^{LWE-RAND} (λ) = 1] ⩽ 1 / 2 + 1 / 2^{λ - 1} . \end{array}$

The last term indicates that the random distribution to $S$ 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}{l} {Adv}_{S}^{LWE} (λ) & = Pr [{Exp}_{S}^{LWE-REAL} (λ) = 1] + Pr [{Exp}_{S}^{LWE-RAND} (λ) = 1] \\ ⩾ 1 / 2 \cdot Pr [{Exp}_{A}^{IND} (λ) - 1 / 2^{λ - 1} . \end{array}$

Finally, we analyze the case of $A_{0} \neq A_{1}$ . $S$ performs the simulation using the same method described above, except that $A$ simulates $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 \times n}$ . □
2.4. Lattice-based signatures

Definition 2.5.
The continuous Gaussian distribution over $R^{m}$ centred at v with standard deviation σ is defined by the function $ρ_{v, σ}^{m} (x) = {(\frac{1}{\sqrt{2 π σ^{2}}})}^{m} e^{\frac{- ‖ x - v ‖^{2}}{2 σ^{2}}}$ .

When the center $v = 0$ we write $ρ_{σ}^{m} (x)$ , and the $‖ \cdot ‖$ denotes the Euclidean norm. The discrete Gaussian distribution over $Z^{m}$ is defined as follows.
Definition 2.6.
The discrete Gaussian distribution over $Z^{m}$ centered at some $v \in Z^{m}$ with standard deviation σ is defined as $D_{v, σ}^{m} (x) = ρ_{v, σ}^{m} (x) / ρ_{σ}^{m} (Z^{m})$ .

A lattice-based digital signature scheme $Σ = (Setup, KG, Sign, Verify)$ has homomorphic property, if the following conditions are held. Besides, we provide the description of the standard digital signature in Appendix C.

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

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

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

Linearity of Verifications. We require that $Verify (p p, M_{p k} (p p, p k, Δ (s k)), msg, M_{Σ} (p p, p k, msg, σ, Δ (s k))) = “ 1^{″}$ , and $Verify (p p, p k, msg, σ) = “ 1^{″}$ .

We show that the lattice-based Schnorr-like signature schemes [11,21] have the homomorphic properties regarding keys and signatures. We first present the simplest version of the lattice-based signature scheme based on SIS [21], then, we show Lemma 2.4 aterwards.

the singer’s signing key is $s k \leftarrow Z_{q}^{m \times k}$ , and its verification key is $p k \leftarrow A \cdot s k mod q$ . These exists a hash function $H : {0, 1}^{} \to {- d, 0, d}^{k}$ and $A \in Z_{q}^{n \times m}$ .

the signer generates a potential message-signature pair $(msg, σ) = (msg, c, z)$ , where σ includes $c \leftarrow H (A \cdot y mod q, msg)$ and $z \leftarrow s k \cdot c + y$ (for $y \in D_{σ}^{m}$ ).

the verifier accepts the signature iff $‖ z ‖ ⩽ 2 σ \sqrt{m}$ and $c = H (A \cdot z - p k \cdot c mod q, msg)$ .
Lemma 2.4.
The lattice-based Schnorr-like signature schemes satisfy the homomorphic property.*
Proof.
The key pair is a pair of integer matrixes such that $(s k, p k) = (s k, A \cdot s k mod q)$ , where $s k \in Z_{q}^{m \times k}$ and $A \in Z_{q}^{n \times m}$ is a public parameter generated by a trusted party. The “shifted” ${p k}^{'} = p k + A \cdot Δ (s k) = {KG}^{'} (A, s k + Δ (s k))$ . Therefore, the condition 1 and 2 are immediate held. As for the condition 3, by definition, $σ = (c, z) = (c \leftarrow H (A \cdot y mod q, msg), z \leftarrow s k \cdot c + y)$ . If $σ^{'} = \underline{(c^{'}, z^{'})}$ is output by $M_{Σ} (p p, p k, msg, σ, Δ (s k))$ , then it holds that $\begin{matrix} z^{'} \leftarrow s k \cdot c + y + \underline{Δ (s k) \cdot c}, c^{'} = c \leftarrow H (A \cdot y mod q, msg) . \end{matrix}$

The output of z (resp. $z^{'}$ ) depends on the vector $v = s k \cdot c$ (resp. $v^{'} = (s k + Δ (s k)) \cdot c^{'}$ ) as well as the secret key $s k$ (resp. $s k + Δ (s k)$ ). To ensure that the signatures do not leak the secret key, the rejection sampling (Theorem 3.4 [21]) aims to remove such dependence. Informally, rejection sampling is to “re-center” the distribution of z to be a discrete Gaussian distribution centered at “zero” rather than at $v = s k \cdot c$ . To show the condition 3 is held such that two distributions are identical in the case of “shifted” Gaussian distributions (i.e., $D_{v^{'}, σ}^{m}$ where $v^{'} = (s k + Δ (s k)) \cdot c$ ), we present Fig. 2 in a two-dimensional space for correctness check.

Fig. 2.
Rejection sampling with “shifted” Gaussian distribution. In blue is the distribution of z, with $v = s k \cdot c$ (left figure) and “shifted” $v^{'} = (s k + Δ (s k)) \cdot c$ (middle and right figures) over the spaces of all y before rejection sampling. In dashed red is the common target distribution $D_{σ}^{m}$ .

When applying the rejection sampling (with same parameters $p p$ , message $msg$ and randomness $y \in D_{σ}^{m}$ ), we have $z = z^{'} \leftarrow Σ . Sign (p p, s k + Δ (s k), msg; y) \in D_{σ}^{m}$ . That is, the target distribution $D_{σ}^{m}$ is independent of the “shifted” Gaussian distributions. It is easy to check that the two distributions we considered are identical, which shows that the condition 3 holds. Furthermore, the randomness $y \in D_{σ}^{m}$ ensures that the discrete Gaussian distributions centered at “zero” and $v / v^{'}$ have sufficient common overlap, hence the condition 4 regarding $Σ . Verify$ is also held. Combing the above conditions together, the lemma is complete. □
3. Reusable fuzzy signature

In this section, we first introduce the construction of reusable fuzzy signature (RFS). Then, we show the formal reusability model of the RFS and its reusability analysis.

3.1. Construction

The RFS is built on top of a family of universal hash functions $H$ , fuzzy extractor $FE = (Gen, Rep)$ , and digital signature $Σ = (KG, Sign, Verify)$ . In particular, both FE and Σ have linearities so that the correctness of RFS is held. A RFS consists of the following algorithms.

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

Fuz-KG: The algorithm takes public parameter $p p$ and biometrics w as input, outputs a key pair $(s k, p k) \leftarrow Σ . KG$ , and a sketch $P \leftarrow FE . Gen (s k, w)$ . Let $(p k, P)$ be a reference.

Fuz-Sign: The randomized algorithm takes public parameter $p p$ , a message $msg$ and a nearby biometrics $w^{'}$ as inputs, outputs a tuple ( ${p k}^{'}, msg, σ, P^{'}$ ), where $({s k}^{'}, {p k}^{'}) \leftarrow Σ . KG, σ \leftarrow Σ . Sign ({s k}^{'}, msg)$ , $P^{'} \leftarrow FE . Gen ({s k}^{'}, w^{'})$ .

Fuz-Verify: The deterministic algorithm takes public parameter $p p$ , message-signature pair $(msg, σ)$ , sketch $P^{'}$ and reference $(p k, P)$ as input, outputs “1” if $1 = Σ . Verify ({p k}^{'}, σ, msg)$ and ${p k}^{'} \leftarrow M_{p k} (p p, p k, Δ (s k))$ , where $Δ (s k) \leftarrow H (Δ (P))$ and $Δ (P) = P^{'} - P$ ; Otherwise, it outputs “0”.

Correctness. The equation ${p k}^{'} \leftarrow M_{p k} (p p, p k, Δ (s k))$ holds if: 1) both the public keys $(p k, {p k}^{'})$ and the sketches $(P, P^{'})$ are linear; and 2) $dist (w, w^{'}) ⩽ t$ . First, linearity of keys means that ${p k}^{'} = M_{p k} (p p, p k, Δ (s k))$ , where $M_{p k}$ is a deterministic algorithm (see Section 2.4). Linearity of sketches means that $P^{'} = P + Δ (P)$ . Second, $Δ (s k) \leftarrow H (Δ (P))$ when $dist (w, w^{'}) ⩽ t$ . Specifically, if the biometrics involved in sketches $(P, P^{'})$ satisfy $dist (w, w^{'}) ⩽ t$ , the difference between two sketches (i.e., $Δ (P) = P^{'} - P$ ) equals to the difference between two secret keys (i.e., $Δ (s k) = {s k}^{'} - s k$ ). Note that $H$ is a universal hash function that maps each (uniformly chosen) key pair used in a digital signature to a secret string used in a public sketch.

3.2. Reusability analysis

First, we present the reusability model of the RFS. Informally, a reusable fuzzy signature requires that an adversary $A$ cannot distinguish an extracted secret string $R^{*}$ used to generate a fuzzy signature from a uniform string. Note that the secret string $R^{*}$ is extracted from a biometrics $w^{*}$ . The goal of reusability is to ensure that a biometrics $w^{*}$ remains secure even if an attacker sees the fuzzy signatures generated by independent executions of Fuz-Sign on a series of inputs related to the biometrics $w^{*}$ . The formal reusability game between an adversary $A$ and a simulator $S$ is defined as follows.

Setup: $S$ samples a biometrics $w^{*} \in M$ , generates a key pair $(s k, p k)$ , a secret string and public sketch pair $(R, P)$ by running the key generation algorithm Fuz-KG $(p p, w^{*})$ . Then, $S$ sends a reference $(p k, P)$ to $A$ . $S$ also tosses a random coin b which will be used later in the game.

Training: $A$ may choose a message ${msg}_{i}$ and a shift $δ_{i} \in M$ with $dist (δ_{i}, 0) ⩽ t$ , and issue Fuz-Sign queries to $S$ , while $S$ performs the following operations.

sample a new key pair $({s k}_{i}, {p k}_{i})$ .

obtain $(R_{i}, P_{i})$ by running Fuz-KG $(p p, w^{*} + δ_{i})$ , where $R_{i} \leftarrow H ({s k}_{i})$ .

generate a message-signature pair $({msg}_{i}, σ_{i})$ using the secret key ${s k}_{i}$ (i.e., $σ_{i} \leftarrow Sign ({s k}_{i}, {msg}_{i})$ ).

return a fuzzy signature $({p k}_{i}, {msg}_{i}, σ_{i}, P_{i})$ to $A$ .

Challenge: $S$ chooses a shift $δ^{*}$ and obtains $(R^{*}, P^{*})$ by running Fuz-KG $(p p, w^{*} + δ^{*})$ , where $δ^{*} \in M$ and $dist (δ^{*}, 0) ⩽ t$ . If $b = 0$ , $S$ gives $R^{*}$ to $A$ ; Otherwise, $S$ chooses $U \overset{R}{\leftarrow} {0, 1}^{| R^{*} |}$ and gives U to $A$ . Eventually, $A$ outputs a bit $b^{'}$ , and $A$ wins if $b^{'} = b$ . We define the advantage of an adversary $A$ in the above game as $\begin{matrix} {Adv}_{A}^{RFS} (λ) = | Pr [S \to 1] - 1 / 2 | . \end{matrix}$

Second, we review the strong reusability of fuzzy extractors (FE) [2,32]. Informally, an adversary, who is given ${(R_{i}, P_{i})}$ generated by independent executions of $Gen (w^{*} + δ_{i})$ on a series of inputs related to the biometrics $w^{*}$ , aims to distinguish an extracted secret string $R^{*}$ from a random string.

Definition 3.1.
Let $FE = (Gen, Rep)$ be an $(M, λ, t, ϵ)$ -fuzzy extractor for class of distributions $M$ . The $FE$ is ϵ-strongly reusable if for any $w \in M$ , any PPT adversary succeeds with probability at most $1 / 2 + ϵ$ in the following experiment between an adversary $A$ and a simulator $S$ .
$S$ samples $w^{} \in M$ , and obtains $(R^{}, P^{})$ by running algorithm $Gen (w^{})$ . The value $P^{}$ is given to $A$ .

$A$ may adaptively make queries of the following form:

$A$ outputs a shift $δ_{i} \in M$ with $dist (δ_{i}, 0) ⩽ t$ .

$S$ obtains $(R_{i}, P_{i})$ by running $Gen (w^{} + δ_{i})$ , and returns them to $A$ .

$S$ tosses a random coin b. If $b = 0$ , $S$ gives $R^{}$ to $A$ ; Otherwise, $S$ chooses $U \overset{R}{\leftarrow} {0, 1}^{| R^{} |}$ and gives U to $A$ .

$A$ outputs a bit $b^{'}$ , and $A$ wins if $b^{'} = b$ .

Third, we reduce the reusability of RFS to the strong reusability of FE as follows. Theorem 3.1.
The fuzzy signature scheme is reusable if the underlying fuzzy extractor is strongly reusable.
Proof.
Let $S$ denote an adversary against the strongly reusability as defined above, who is given a public sketch $P^{}$ and a FE generation oracle $O^{Gen (w^{})}$ , aims to distinguish a real secret string $R^{}$ from a random string U. $S$ simulates the reusability game for $A$ as follows.
$S$ obtains a string pair $(R, P)$ by invoking his oracle $O^{Gen (w^{})}$ . $A$ is given a reference $(p k, P)$ , where $p k \leftarrow KG (p p, s k), s k \leftarrow H (R)$ .

If $A$ issues a Fuz-Sign query in the form of $({msg}_{i}, δ_{i})$ to $S$ , where $δ_{i} \in M$ and $dist (δ_{i}, 0) ⩽ t$ , then $S$ performs the following operations.

obtain the values $(R_{i}, P_{i})$ by invoking his oracle $O^{Gen (w^{})}$ on input $δ_{i}$ (i.e., $Gen (w^{} + δ_{i})$ );

compute a secret key ${s k}_{i} \leftarrow H (R_{i})$ , and generate its corresponding public key ${p k}_{i} \leftarrow KG (p p, {s k}_{i})$ ;

generate a message-signature pair $({msg}_{i}, σ_{i})$ using the secret key ${s k}_{i}$ (i.e., $σ_{i} \leftarrow Sign ({s k}_{i}, {msg}_{i})$ );

return a fuzzy signature $({p k}_{i}, {msg}_{i}, σ_{i}, P_{i})$ to $A$ .

$S$ obtains a secret string $R_{b}^{}$ from his challenger, and sends $(R_{b}^{}, P^{*})$ to $A$ . Finally, $S$ outputs whatever $A$ outputs. If $A$ guesses the random bit correctly, then $S$ breaks the strong reusability of FE. □

4. Proposed construction

In this section, we first present the security models (user authenticity and user privacy) for our proposed remote user authentication construction based on RFS (RFS-RUA). Then, we show the proposed construction and its security analysis.

States. We define a system entity set $U$ with N users and M servers. We say an instance oracle $Π_{ID}^{l}$ (e.g., session l of user $ID$ ) may be used or unused, and a user $ID$ has unlimited number of instances called oracles. The oracle is considered as unused if it has never been initialized. Each unused oracle $Π_{ID}^{l}$ can be initialized with a secret key $s k$ . The oracle is initialized as soon as it becomes part of a protocol execution. 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 $Π_{ID}^{l}$ learns its partner id ${pid}_{ID}^{l}$ 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}_{ID}^{l}$ is maintained by the oracle. The oracle $Π_{ID}^{l}$ remains in the processing state until it collects enough information to finalize the user authentication procedure. As soon as the user authentication is accomplished, $Π_{ID}^{l}$ accepts and terminates the protocol execution in the sense that it would not send or receive further messages. If the protocol execution fails, then $Π_{ID}^{l}$ terminates without having accepted.

We denote the l-th session established by a server as $Π_{S}^{l}$ and identities of all the users recognized by $Π_{S}^{l}$ during the execution of that session by partner identifier ${pid}_{S}^{l}$ . We define ${sid}_{S}^{l}$ as the unique session identifier belonging to the session l established by a server $S$ . Specifically, we have ${sid}_{S}^{l} = {{msg}_{i}}_{i = 1}^{n}$ , where ${msg}_{i} \in {0, 1}^{*}$ is the message transcript transmitted between users and servers.

4.1. Definition

A RFS-RUA consists of the following algorithms:

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

KeyGen: The algorithm takes public parameter $p p$ as input, outputs key pairs ${(s k, p k)}$ for users, and key pairs ${(s s k, s p k)}$ for authentication servers.

Enrollment. This is a non-interactive protocol between a user and an authentication server over a secure channel. The user enrolls her identity $ID$ , public key $p k$ , and sketch $SS (w, s k)$ to the authentication server. The enrolled users become authorized ones after enrollment, and the sketch $SS (w, s k)$ means that it derives from biometrics w and secret key $s k$ . We assume a uniform1

¹
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 [19]) while the security of FE is held. We use a uniform source here for presentation simplicity, the case of non-uniform source is discussed in [13,32,33].

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. The protocol takes public parameter $p p$ , an authorized user’s identity $ID$ and biometrics $w^{'}$ , and an authentication server’s public key $s p k$ as input, outputs a new key pair $({s k}^{'}, {p k}^{'})$ , a new sketch $SS (w^{'}, {s k}^{'})$ and a message-signature pair $(msg, σ)$ . The authentication server accepts the user if: 1) the message-signature pair $(msg, σ)$ is verified as valid under her new public key ${p k}^{'}$ ; and 2) the new public key ${p k}^{'}$ is linked to new sketch $SS (w^{'}, {s k}^{'})$ , and her enrolled public key $p k$ and sketch $SS (w, s k)$ . The message $msg$ denotes the transmitted ephemeral data, and the biometrics satisfies $dist (w^{'}, w) ⩽ t$ .

4.2. Security models

User Authenticity. We define Δ as the set of functions $f : M \to M$ satisfies: for any $w \in M$ , $f (w)$ is “close” to w (i.e., $dist (w, f (w)) ⩽ t$ ). The perturbations $δ \in Δ$ are specified by the adversary and applied by the simulator (i.e., challenger). Furthermore, the simulator specifies a class of functions $Φ = {ϕ}^{| s k |}$ whose domain and range are the secret key space of RFS-RUA. In the user authenticity game, 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 simulator $S$ as follows.

Setup. $S$ first generates identities ${S_{j}}$ and key pairs ${(s s k_{j}, s s p k_{j})}$ ( $j \in [1, M]$ ) for M servers, and identities ${{ID}_{i}}$ ( $i \in [1, N]$ ) for N users in the system. $S$ also generates user’s biometrics information ${w_{i}}$ ( $w_{i} \in M$ ), generates a set of public/secret key pairs ${{p k}_{i}^{j}, {s k}_{i}^{j}}_{j = 1}^{M}$ and their corresponding sketches $SS (w_{i}, {s k}_{i}^{j})$ for each user i with respect to M servers. Eventually, $S$ sends all identities, public keys and sketches to $A$ . Let $KG$ be a key generation algorithm which takes public parameter $p p$ and a secret key $s k$ as input, outputs a public key $p k$ .

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

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

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

Secret Key Reveal: If $A$ issues a secret key reveal query to user i with respect to server $S_{j}$ , then $S$ returns the enrolled secret key ${s k}_{i}^{j}$ to $A$ .

Biometrics Shift: If $A$ issues a biometrics shift query with δ to user i, then $S$ returns user i’s shifted biometric information $SS (w_{i} + δ, {s k}_{i}^{j})$ to $A$ .

Secret Key Shift: If $A$ issues a secret key shift query with ϕ to user i, then $S$ returns user i’s shifted public key ${p k}_{i}^{'} \leftarrow KG (p p, ϕ ({s k}_{i}^{j}))$ to $A$ .

Server Secret Key Reveal: If $A$ issues a server secret key reveal query to server $S_{j}$ , then $S$ will return server $S_{j}$ ’s secret key $s s k_{j}$ to $A$ .

Challenge. $A$ outputs a message $msg$ and wins the game if all of the following conditions hold.

$S_{j}$ accepts user i. It implies ${pid}_{S_{j}}^{s}$ and ${sid}_{S_{j}}^{s}$ exist.

$A$ did not issue Biometrics Reveal query to user i.

$A$ did not issue Secret Key Reveal query to user i with respect to $S_{j}$ .

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

A

is allowed to reveal user i’s secret keys associate with M-1 servers. We also allow

A

to adaptively issue Biometrics Shift queries to challenge user i. We define the advantage of an adversary

A

in the above game as

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

Definition 4.1.
A RFS-RUA has user authenticity if for any PPT $A$ , ${Adv}_{A}^{RFS-RUA} (λ)$ is a negligible function of the security parameter λ.

Remark. The perturbation $δ \in Δ$ from adversary is used to capture the adaptive chosen perturbation attacks [6]. For example, an adversary may query an oracle to perform extractions and re-generations based on the chosen perturbations of biometrics. The function $Φ = {ϕ}^{| s k |}$ from simulator is used to capture the related key attacks, such that an adversary may “modify” the secret keys [4]. In particular, the simulator should “update” the simulated signatures under the new public keys [22].

User Privacy. Informally, an adversary attempts to identify the authenticated users involved in a RFS-RUA. We define a formal user privacy game between an adversary $A$ and a simulator $S$ as follows:
Setup: $S$ first generates identities ${S_{j}}$ and key pairs ${(s s k_{j}, s p k_{j})}$ ( $j \in [1, M]$ ) for M servers, and identities ${{ID}_{i}}$ ( $i \in [1, N]$ ) for N users in the system. $S$ also generates biometrics information ${w_{i}}$ for N users, generates a set of public/secret key pairs ${{p k}_{i}^{j}, {s k}_{i}^{j}}_{j = 1}^{M}$ and their corresponding sketches $SS (w_{i}, {s k}_{i}^{j})$ with respect to M servers. Eventually, $S$ sends all identities, public keys and sketches to $A$ . $S$ also tosses a random coin b which will be used later in the game.

Training: $A$ is allowed to issue Execute queries to $S$ . In addition, $A$ can issue at most N-2 Biometrics Reveal, N-2 Secret Key Reveal queries, and M-1 Server Secret Key Reveal queries to $S$ . We denote the honest (i.e., uncorrupted) user and server set as $(U_{0}^{'}, U_{1}^{'})$ , respectively. The honest user requires that her biometrics as well as her secret key are not corrupted.

The Execute query [5] allows $A$ to invoke an honest execution of the protocol and returns a transcript of exchanged messages to $A$ .

Challenge: $S$ randomly selects two users ${ID}_{i}, {ID}_{j} \in U_{0}^{'}$ as challenge candidates. $S$ removes them from $U_{0}^{'}$ and simulates ${ID}_{b}^{}$ by either ${ID}_{b}^{} = {ID}_{i}$ if $b = 1$ or ${ID}_{b}^{} = {ID}_{j}$ if $b = 0$ . $S$ also selects a server ${ID}_{S} \in U_{1}^{'}$ at random, and let ${ID}_{S}$ interact with the challenge user ${ID}_{b}^{}$ . $A$ can access all the communication transcripts among them. $\begin{matrix} {ID}_{S} \leftrightarrow {ID}_{b}^{*} = \{\begin{matrix} {ID}_{i} & b = 1 \\ {ID}_{j} & b = 0 \end{matrix} \end{matrix}$

$A$ is allowed to issue Secret Key Shift queries to challenge candidates. Finally, $A$ outputs $b^{'}$ as its guess for b. If $b^{'} = b$ , then $S$ outputs 1; Otherwise, $S$ outputs 0. We define the advantage of an adversary $A$ in the above game as $\begin{matrix} {Adv}_{A}^{RFS-RUA} (λ) = | Pr [S \to 1] - 1 / 2 | . \end{matrix}$
Definition 4.2.
A RFS-RUA has user privacy if for any PPT $A$ , ${Adv}_{A}^{RFS-RUA} (λ)$ is a negligible function of the security parameter λ.

4.3. Proposed construction

The proposed construction consists of the following building blocks.

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

An existential unforgeability under chosen message attack EUF-CMA secure digital signature scheme $Σ = (KG, Sign, Verify)$ .

An indistinguishability under chosen plaintext attack IND-CPA secure public key encryption scheme $PKE = (KG, Enc, Dec)$ .

A universal hash function family $H$ .

We use user i and server j to present our proposed construction.

Setup. Let λ be the security parameter, and let universal hash function family be $H : {y = H_{A} (x)}$ , which involves a public matrix $A$ .

KeyGen. User i obtains a key pair $({s k}_{i}, {p k}_{i}) \leftarrow Σ . KG$ by running the key generation algorithm of Σ. The server j obtains a key pair $(s s k_{j}, s p k_{j}) \leftarrow PKE . KG$ by running the key generation algorithm of $PKE$ .

Enrollment. A user i wants to enroll herself to an authentication server j performs the following steps

compute a secret string $s_{i} \overset{R}{\leftarrow} H_{A}^{- 1} ({s k}_{i})$ from the secret key ${s k}_{i}$ , and derive a sketch $SS (w_{i}, {s k}_{i}) \leftarrow FE . Gen (A, w_{i}, s_{i})$ .

send a reference tuple ( ${ID}_{i}, V K_{i}$ ) to server j (note that server j maintains a database DB of all enrolled users, which includes verification keys ${V K_{i}} = {({p k}_{i}, SS (w_{i}, {s k}_{i}))}$ ).

Authentication. The authentication between user i and server j is shown in Fig. 3.

Fig. 3.

Description of Authentication.

User i generates a ciphertext $C_{i} \leftarrow PKE . Enc (s p k_{j}, {ID}_{i})$ on her identity ${ID}_{i}$ under the public key $s p k_{j}$ of server j, and sends it to server j.

Server j obtains the identity ${ID}_{i} \leftarrow PKE . Dec (s s k_{j}, C_{i})$ by running the decryption algorithm of PKE, and sends a challenge nonce $n_{j}$ to user i.

User i performs the following steps

obtain a new key pair $({s k}_{i}^{'}, {p k}_{i}^{'}) \leftarrow Σ . KG$ and derive a new secret string $s_{i}^{'} \overset{R}{\leftarrow} H_{A}^{- 1} ({s k}_{i}^{'})$ from the new secret key ${s k}_{i}^{'}$ .

choose a response nonce $n_{i}$ and generate a message-signature pair $({msg}_{(i, j)}, σ_{i}) \leftarrow Σ . Sign ({s k}_{i}^{'}, {msg}_{(i, j)})$ , where ${msg}_{(i, j)} = (n_{i}, n_{j})$ .

derive a new sketch $SS (w_{i}^{'}, {s k}_{i}^{'}) \leftarrow FE . Gen (A, w_{i}^{'}, s_{i}^{'})$ , and send $({msg}_{(i, j)}, σ_{i}, SS (w_{i}^{'}, {s k}_{i}^{'}))$ to server j.

Server j performs the following steps

compute a “shift” secret between enrolled sketch and new sketch, where $Δ (s) \leftarrow SS (w_{i}, {s k}_{i}) - SS (w_{i}^{'}, {s k}_{i}^{'})$ (see correctness below).

compute a “shift” secret key $Δ (s k) = H_{A} (Δ (s))$ , and derive a new public key ${p k}_{i}^{'}$ from the enrolled public key ${p k}_{i}$ and the “shift” secret key $Δ (s k)$ (i.e., $M_{{p k}_{i}} (p p, {p k}_{i}, Δ (s k))$ ).

verify the message-signature pair $({msg}_{(i, j)}, σ_{i})$ under the new public key ${p k}_{i}^{'}$ . If the signature passes the verification, it accepts; Otherwise, it aborts.

Instantiations and Correctness. We hereby try to instantiate the underlying cryptographic building blocks which are able to resist quantum computers. First, to instantiate the computational fuzzy extractors from LWE, we rely on the reusable fuzzy extractors proposed by Apon et al. [2] (or the one called robustly reusable fuzzy extractor [32] with a non-uniform source). Second, we can implement the lattice-based digital signatures [11,21] as described in Section 2.4. Third, we could use the passively secure (i.e., IND-CPA) encryptions such as Regev’s LWE-based cryptosystem [25] to instantiate the underlying public key encryptions. We notice that the passively secure encryptions will suffice for our defined user privacy model, and we refer to [24] for passively and actively secure cryptosystems which might be alternatively applicable to instantiate our proposed construction.

The public matrix includes $A = (A_{1} \in Z_{q^{m k}}, A_{2} \in Z_{q}^{m k \times n}, A_{3} \in Z_{q}^{m \times n})$ (the transpose of $A_{3}$ is $A_{3}^{⊤} \in Z_{q}^{n \times m}$ ). We set $m ⩾ c \cdot n$ , where c is a positive constant, $n = n (λ)$ and $q = q (λ) ⩾ 2$ are two integers. Let the universal hash function be ${H_{(A_{1}, A_{2})} : Z_{q}^{n} \to Z_{q}^{m \times k}}_{A_{1} \in Z_{1}, A_{2} \in Z_{2}}$ . For each seed pair $(A_{1}, A_{2}) \in (Z_{q^{m k}}, \in Z_{q}^{m k \times n})$ and $y \in Z_{q}^{m \times k}$ , we define “ $H_{(A_{1}, A_{2})}^{- 1} (y)$ ” as the set of pre-images of y under $H_{(A_{1}, A_{2})}$ . That is, $H_{(A_{1}, A_{2})}^{- 1} (y) = {x \in Z_{q}^{n} : H_{A_{1}, A_{2}} (x) = y}$ . In particular, $x \overset{R}{\leftarrow} H_{(A_{1}, A_{2})}^{- 1} (y)$ means that we choose a vector x uniformly at random from set $H_{(A_{1}, A_{2})}^{- 1} (y)$ , and its size is $c \cdot k$ .

The sketch $SS (w_{i}, {s k}_{i})$ is instantiated with a random linear code over a finite field $Z_{q}$ . That is, $SS (w_{i}, {s k}_{i}) \leftarrow A_{3} \cdot s_{i} + w_{i}$ , where biometrics $w_{i} \in Z_{q}^{m}$ and secret $s_{i} \in Z_{q}^{n}$ . The correctness of $Δ (s)$ relies on an algorithm ${Decode}_{t} (A_{3}, b)$ [13]. According to the ${Decode}_{t}$ algorithm, we have the following equation with respect to the “shift” secret $Δ (s) = s_{i} - s_{i}^{'}$ . $\begin{array}{l} SS (w_{i}, {s k}_{i}) - SS (w_{i}^{'}, {s k}_{i}^{'}) & = A_{3} \cdot s_{i} + w_{i} - (A_{3} \cdot s_{i}^{'} + w_{i}^{'}) = A_{3} \cdot (s_{i} - s_{i}^{'}) + (w_{i} - w_{i}^{'}) \\ = A_{3} \cdot Δ (s) + δ . \end{array}$

We assume that δ has at most t non-zero coordinates (i.e., at most t of non-zero coordinates can be zeroed out by $w_{i} - w_{i}^{'}$ ), and notice that $A_{3} \cdot Δ (s)$ is a linear system with m equations and $2 n$ unknowns. If $m ⩾ 6 n$ (we set $c = 6$ as suggested by [2] in order to ensure the ${Decode}_{t}$ works with expected running time), then one can recover $Δ (s)$ using the ${Decode}_{t}$ algorithm with high probability (we refer to [13] for success probability and time complexity of ${Decode}_{t}$ ). Furthermore, we emphasize that the biometrics $w_{i}, w_{i}^{'}$ are computationally secure, because the server j is allowed to learn the “shift” secret $Δ (s) = s_{i} - s_{i}^{'}$ only.

5. Security analysis

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

Theorem 5.1.
The proposed RFS-RUA achieves user authenticity in the random oracle model if the family of universal hash functions $H = {H_{(z_{1}, z_{2})} : Z_{q}^{n} \to Z_{q}^{m \times k}}_{z_{1} \in Z_{1}, z_{2} \in Z_{2}}$ is ϵ-statistically secure, the ${DLWE}_{q, n - k, m, χ}$ assumption is $(ϵ, s_{\sec}^{'})$ secure and the digital signature scheme Σ is EUF-CMA secure.
Proof.
We define a sequence of games ${G_{i}}$ and let ${Adv}_{i}^{RFS-RUA}$ 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.
$G_{0}$ : This is the original game for user authenticity security.

$G_{1}$ : This game is identical to game $G_{0}$ except that the simulator $S$ will output a random bit if server j accepts user i, but ${sid}_{{ID}_{i}}^{l} \neq {sid}_{S_{j}}^{l}$ . Since N users involved in this game, we have: $\begin{matrix} (1) & | {Adv}_{0}^{RFS-RUA} - {Adv}_{1}^{RFS-RUA} | ⩽ N \cdot m {(λ)}^{2} / 2^{λ} . \end{matrix}$

$G_{2}$ : This game is identical to game $G_{1}$ except the following difference: $S$ randomly chooses $g \in [1, m (λ)]$ as a guess for the index of the Challenge session. $S$ 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}^{RFS-RUA} = m (λ) \cdot {Adv}_{2}^{RFS-RUA} . \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 encrypted secret in the sketch $SS (w_{i}, {s k}_{i}^{'})$ of user i w.r.t. server j is replaced by a random value. Below we show that the difference between $G_{2}$ and $G_{3}$ is negligible under the ${DLWE}_{q, n - k, m, χ}$ assumption.

Let $S$ denote a distinguisher against the ${DLWE}_{q, n - k, m, χ}$ 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_{R} Z_{q}^{k}$ . $S$ simulates the game for $A$ as follows.
Setup. $S$ sets up the game for $A$ by creating N users and M servers with the corresponding identities. $S$ randomly selects indexes $(i, j)$ and guesses that the g-th session will happen with regard to user i at server j. $S$ sets the sketch of user i w.r.t. server j as $SS (w_{i}, {s k}_{b})$ such that $SS (w_{i}, {s k}_{b}) = A \cdot \underline{X_{b}} + χ$ , where ${s k}_{b} = H_{(A_{1}, A_{2})} (\underline{X_{b}})$ and $X_{b} = \underline{X_{1, \dots, k}}$ . $S$ generates user i’s enrolled public/secret key pair $({p k}_{i}^{l}, {s k}_{i}^{l})$ w.r.t. l servers ( $l \neq j$ ), and their corresponding sketches ${SS (w_{i}, {s k}_{b} + {s k}_{l})}$ . In addition, $S$ honestly generates biometrics for N-1 users, and generates enrolled public/secret key pairs and sketches as Enrollment specified for N-1 users w.r.t. M servers. Eventually, $S$ sends all enrolled public keys and references to $A$ . $S$ sets $A_{3} = A$ , and generates rest public parameters (including matrixes $A_{1}, A_{2}$ ) for the system. $S$ also chooses a random vector from $Z_{q}^{n - k}$ to construct $X_{b} \in Z_{q}^{n}$ , we omit it in the following proof for simplicity.

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

If $A$ issues a Send query in the form of $n_{j}$ to $S$ , $S$ chooses a response nonce $n_{i}$ first, then $S$ honestly generates the protocol transcript $T_{i}$ using user i’s enrolled secret key ${s k}_{b}$ and sketch $SS (w_{i}, {s k}_{b})$ . Specifically, $T_{i} = ({msg}_{(i, j)}, σ_{i}, SS (w_{i}, {s k}_{i}^{'}))$ , where $σ_{i} \leftarrow M_{Σ} (p p, {p k}_{b}, Sign ({s k}_{b}, {msg}_{(i, j)}), Δ (s_{i}))$ , $SS (w_{i}, {s k}_{i}^{'}) \leftarrow A \cdot X_{b} + χ + A \cdot Δ (s_{i})$ , where ${s k}_{i}^{'} \leftarrow H_{(A_{1}, A_{2})} (s_{b} + Δ (s_{i})), s_{b} \overset{R}{\leftarrow} H_{(A_{1}, A_{2})}^{- 1} ({s k}_{b})$ and $Δ (s_{i}) \in_{R} Z_{q}^{n}$ is chosen by $S$ .

As for user i’s g-th session w.r.t. server j, $S$ first generates $SS (w_{i}, {s k}_{b}^{'}) \leftarrow A \cdot X_{b} + χ + A \cdot Δ (s)$ , and denotes $X_{b}^{'} = X_{b} + Δ (s)$ and $X_{b} = \underline{U}$ ; $S$ then generates a key pair $({s k}_{b}^{'}, {p k}_{b}^{'})$ from $X_{b}^{'}$ , where ${s k}_{b}^{'} = H_{(A_{1}, A_{2})} (X_{b}^{'})$ and ${p k}_{b}^{'} = A^{⊤} \cdot {s k}_{b}^{'}$ ; eventually, $S$ honestly generates the message-signature pair according to the protocol specification, and returns the protocol transcript to $A$ .

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

If $A$ issues a Secret Key Reveal query to an instance oracle $Π_{{ID}_{i}}^{g}$ (g-th session of user i w.r.t. server j), then $S$ returns new secret key ${s k}_{b}^{'}$ to $A$ .

If $A$ issues Biometrics Shift query in the form of δ to $S$ , then $S$ returns $SS (w_{i} + δ, s k) = A \cdot \underline{X_{b}} + χ + δ$ by the linearity of the sketch, where $s k$ can be either enrolled secret key ${s k}_{b}$ or new secret key ${s k}_{b}^{'}$ that involves at g-th session.

If $A$ issues Secret Key Shift query in the form of ϕ to $S$ , then $S$ returns new public key ${p k}_{b}^{'} \leftarrow KG (p p, ϕ ({s k}_{b}))$ . Notice that $A$ is not allowed to obtain user i’s enrolled secret key ${s k}_{b}$ .
Note that in the Challenge session of user i w.r.t. server j, if the challenge of $S$ 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 $S$ can break the ${DLWE}_{q, n - k, m, χ}$ . Since at most N users involved in the system, hence we have $\begin{matrix} (3) & | {Adv}_{2}^{RFS-RUA} - {Adv}_{3}^{RFS-RUA} | ⩽ N \cdot {Adv}_{S}^{{DLWE}_{q, n - k, m, χ}} (λ) . \end{matrix}$

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

Let $S$ 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 w.r.t. server j is $\underline{{s k}_{i}^{j}}$ . In the g-th session of user i w.r.t server j, to answer the Send query from $A$ , $S$ will simulate the protocol transcript $T_{i}^{'}$ as follows. $S$ first simulates the sketch as $SS (w_{i}, {s k}_{i}^{'}) \leftarrow A_{3} \cdot (s_{i} + Δ (s)) + w_{i}$ , where ${s k}_{i}^{'} \leftarrow H_{(A_{1}, A_{2})} (s_{i} + Δ (s)), s_{i} \overset{R}{\leftarrow} H_{(A_{1}, A_{2})}^{- 1} (\underline{u}), u \in_{R} Z_{q}^{m \times k}$ , and $Δ (s)$ is randomly chosen by $S$ ; $S$ then generates a key pair $({s k}_{i}^{'}, {p k}_{i}^{'})$ from $s_{i} + Δ (s)$ ; eventually, $S$ honestly generates the message-signature pair using the same method described in previous game $G_{3}$ .

We then analyze the statistical distance between two distributions $T_{i}^{'} = ({msg}_{(i, j)}, σ_{i}, SS (w_{i}, {s k}_{i}^{'}))$ and $T_{i}$ (of previous game $G_{3}$ ). We notice that the only difference is the simulated value $s_{i} \overset{R}{\leftarrow} H_{(A_{1}, A_{2})}^{- 1} (\underline{u})$ instead of taking the real enrolled secret key ${s k}_{i}^{j}$ as input, and according to Lemma 2.2, we have the statistically distance between ${s k}_{i}^{j} \leftarrow H_{(A_{1}, A_{2})} (s_{i})$ and $u \in_{R} Z_{q}^{m \times k}$ with probability no greater than ϵ. Since at most M servers involved in the system, hence we have $\begin{matrix} (4) & | {Adv}_{3}^{RFS-RUA} - {Adv}_{4}^{RFS-RUA} | ⩽ M \cdot {Adv}_{S}^{H} (λ) . \end{matrix}$

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

Let $F$ denote a forger against a (lattice-based) signature scheme Σ with EUF-CMA security, who is given a verification key ${p k}^{}$ and a signing oracle $O$ , and aims to find a forgery $σ^{}$ . $S$ simulates the game for $A$ as follows.
Setup. $F$ sets up the game for $A$ by creating N users and M servers with the corresponding identities and biometrics. $F$ sets up the verification key of user i w.r.t. server j as $V K_{i}^{j} = ({p k}^{}, SS (w_{i}, {s k}_{i}^{j}))$ , where $SS (w_{i}, {s k}_{i}^{j}) = A_{3} \cdot s_{i} + w_{i}, s_{i} \in_{R} Z_{q}^{n}$ . $F$ also honestly generates public/secret key pairs and sketches as Enrollment specified for N-1 users and M servers. Eventually, $F$ sends all enrolled public keys and references to $A$ . Note that $F$ honestly generates all the public parameters (including matrixes $A_{1}, A_{2}, A_{3}$ ) in the system. Also note that $A$ cannot link the simulated sketch $SS (w_{i}, {s k}_{i}^{j})$ and public key ${p k}^{}$ since $A$ is not allowed to access biometrics $w_{i}$ .

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

If $A$ issues a Send query in the form of $n_{j}$ to $F$ , $F$ chooses a response nonce $n_{i}$ first, then $F$ simulates the protocol transcript $T_{i} = (σ_{i}^{'}, SS (w_{i}, {s k}_{i}^{'}))$ as follows.

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

generate a sketch $SS (w_{i}, {s k}_{i}^{'}) \leftarrow SS (w_{i}, {s k}_{i}^{j}) + A_{3} \cdot Δ (s_{i})$ , where $Δ (s_{i})$ is randomly chosen by $F$ ;

generate a signature $σ_{i}^{'} \leftarrow M_{Σ} (p p, {p k}^{}, σ_{i}, Δ (s_{i}))$ by using the deterministic algorithm $M_{Σ}$ described in Section 3;

returen $(m_{(i, j)}, σ_{i}^{'}, SS (w_{i}, {s k}_{i}^{'}))$ to $A$ .

If $A$ issues a Secret Key Reveal query to an instance oracle $Π_{{ID}_{i}}^{i}$ , then $F$ returns new secret key ${s k}_{i}^{'} \in_{R} Z_{q}^{m \times k}$ to $A$ . Since $A$ is not allowed to reveal the enrolled secret key $D l o g ({p k}^{})$ (of user i w.r.t. server j), the simulation is perfect.

If $A$ issues Biometrics Shift query in the form of δ to $F$ , then $F$ returns $SS (w_{i} + δ, {s k}_{i}^{'})$ to $A$ . Notice that $A$ is not allowed to obtain user i’s biometrics $w_{i}$ .

If $A$ issues Secret Key Shift query in the form of ϕ to $F$ , then $F$ returns new public key ${p k}^{^{'}} \leftarrow KG (p p, D l o g ({p k}^{}), ϕ (Δ (s k)))$ , where $Δ (s k)$ is chosen by $A$ .

When $Forge$ event occurs (i.e., $A$ outputs $({msg}^{}, σ^{^{'}}, SS (w_{i}, {s k}^{^{'}}))$ ), $F$ checks whether:
the Forge event happens at g-th session;

the message-signature pair $({msg}^{}, σ^{^{'}})$ is not previously simulated by $S$ ;

verifies $Σ . Verify ({p k}^{^{'}}, {msg}^{}, σ^{^{'}}) \overset{?}{=} 1$ , where ${p k}^{^{'}} \leftarrow {p k}^{} + A_{3}^{⊤} \cdot \underline{Δ ({s k}^{})}, \underline{Δ ({s k}^{})} = H_{(A_{1}, A_{2})} (Δ (s^{})), Δ (s^{}) \leftarrow SS (w_{i}, {s k}^{^{'}}) - SS (w_{i}, {s k}_{i}^{j})$ . Note that $\underline{Δ ({s k}^{})}$ is the correct “shift” between $D l o g ({p k}^{^{'}})$ and ${s k}_{i}^{j}$ .
If all the above conditions hold, $F$ confirms that it as a successful forgery from $A$ , then $F$ extracts the forgery via $σ^{} \leftarrow M_{Σ} (p p, {p k}^{}, σ^{^{'}}, \underline{Δ ({s k}^{})})$ by using the homomorphic property of Σ (Lemma 3). To this end, $F$ outputs $σ^{}$ as its own forgery; Otherwise, $F$ aborts the game. Therefore, we have $\begin{matrix} (6) & | Pr [Forge] | ⩽ {Adv}_{F}^{EUF-CMA} (λ) . \end{matrix}$
Combining the above results together, we have $\begin{array}{l} {Adv}_{A}^{RFS-RUA} (λ) \\ ⩽ N \cdot m {(λ)}^{2} / 2^{λ} + m (λ) [N \cdot {Adv}_{S}^{{DLWE}_{q, n - k, m, χ}} (λ) + M \cdot {Adv}_{S}^{H} (λ) + {Adv}_{F}^{EUF-CMA} (λ)] . \end{array}$
□
Theorem 5.2.
The proposed RFS-RUA achieves user privacy in the random oracle model if the decisional* ${SIS}_{q, n, m, d}$ assumption is ( $ϵ, s_{\sec}$ ) secure, the public key encryption is IND-CPA secure and the computational fuzzy extractor is IND secure.
Proof.
We define a sequence of games ${G_{i}}$ and let ${Adv}_{i}^{RFS-RUA}$ denote the advantage of the adversary $A$ in game $G_{i}$ . We also highlight the differences between adjacent games by underline.
$G_{0}$ : This is the original game for user privacy.

$G_{1}$ : This game is identical to game $G_{0}$ except that at challenge stage, $S$ replaces the real identity (message of ciphertext $C_{i}$ ) by random string R. Below we show that the difference between $G_{0}$ and $G_{1}$ is negligible under the assumption that the public key encryption scheme is IND-CPA secure.

Let $S$ denote an attacker who is given a public key ${p k}^{}$ , aims to break the IND-CPA security of the public key encryption scheme. $S$ simulates the game for $A$ as follows.
Setup. $S$ sets up the game for $A$ by creating N users and M servers. $S$ honestly generates biometrics for N users, generates key pairs with respect to M servers and their corresponding sketches. $S$ randomly selects index j and guesses the challenge will happen with regard to server j. $S$ sets the public key of server j as ${p k}^{}$ , and honestly generates key pairs for M-1 servers. It is obvious that $S$ can easily simulate the protocol execution of N users and M-1 servers except server j. Below we mainly focus on the simulation of server j.

Training. If $A$ issues an Execute query between user i and server j, then $S$ randomly chooses nonces $(n_{i}, n_{j})$ and new key pairs, and performs the session execution honestly according to the protocol specification.

Challenge. Upon receiving challenge candidates $({ID}_{0}, {ID}_{1}) \in U_{0}^{'}$ from $A$ , $S$ follows the security game to select ${ID}_{b}^{}$ . Then $S$ executes the RFS-RUA protocol to generate the protocol transcript. After that, $S$ generates another random string $\underline{R}$ and sends ${ID}_{b}$ and $\underline{R}$ as the challenge messages to its own oracle. After receiving the challenge ciphertext $\underline{C^{}}$ from his own challenger, $S$ replaces the ciphertext generated by ${ID}_{b}$ in the first message of the transcript by $\underline{C^{}}$ . Eventually, $S$ sends the complete transcript to $A$ .
Finally, $S$ outputs whatever $A$ outputs. If $A$ guesses the random bit correctly, then $S$ can break the IND-CPA security of public key encryption scheme. Since at most M servers in the system, and at most $K = {0, 1}^{| ID |}$ encryptions are executed (because each ciphertext encrypts a single bit of real identity), we have $\begin{array}{l} (7) & | {Adv}_{0}^{RFS-RUA} - {Adv}_{1}^{RFS-RUA} | ⩽ M \cdot K \cdot {Adv}_{S}^{IND-CPA} (λ) . \end{array}$

$G_{2}$ : This game is identical to game $G_{1}$ except that at challenge stage, $S$ replaces the sketch $SS (w_{i}^{'}, {s k}_{i}^{'})$ by a random distribution over $Z_{q}^{m}$ . Below we show that the difference between $G_{1}$ and $G_{2}$ is negligible under the assumption that computational fuzzy extractor is IND secure.

Let $S$ denote an attacker who is given a challenge sketch (assuming a common public matrix $A$ here, and $p \leftarrow A \cdot X + χ$ ), aims to break the IND security of the computational fuzzy extractor. $S$ simulates the game for $A$ as follows.
Setup. $S$ sets up the game for $A$ by creating N users and M servers. $S$ honestly generates key pairs for M servers. $S$ randomly selects indexes $(i, j)$ and guesses the challenge will happen with regard to user i and server j. $S$ sets the enrolled sketch of user i with respect to server j as $p_{0}$ , and generates the enrolled key pair at random (which is a matrix pair over distribution $(Z_{q}^{m \times k}, Z_{q}^{n \times k})$ ). Additionally, $S$ honestly generates biometrics, key pairs (w.r.t. M servers) and sketches for N-1 users. It is obvious that $S$ can easily simulate all protocol executions except user i w.r.t server j. Below we mainly focus on the simulation between user i and server j. Note that $A_{3}^{⊤} = \underline{A^{⊤}}$ .

Training. If $A$ issues an Execute query, then $S$ simulates the session execution as follows

generate a ciphertext $C_{i}$ on the identity of user i;

choose nonces $n_{i}, n_{j}$ and form a message ${msg}_{i} = (n_{i}, n_{j})$ ;

choose a new key pair $({s k}_{i}^{'}, {p k}_{i}^{'})$ and generate message-signature pair using the secret key ${s k}_{i}^{'}$ ;

compute “shift” $Δ ({s k}_{i})$ from (enrolled public key) ${p k}_{i}^{j}$ and ${p k}_{i}^{'}$ ;

simulate a new sketch $SS (w_{i}, {s k}_{i}^{'}) = {p k}_{0} + A^{⊤} \cdot Δ ({s k}_{i})$ ;

sends the complete transcript to $A$ .

Challenge. Upon receiving challenge candidates $({ID}_{0}, {ID}_{1}) \in U_{0}^{'}$ from $A$ , $S$ follows the security game to select ${ID}_{b}^{}$ and server j (from honest set $U_{1}^{'}$ ). Then $S$ executes the RFS-RUA protocol to generate the protocol transcript. After that, $S$ replaces the simulated sketch associated with ${ID}_{b}^{}$ in the third message of the transcript by $\underline{C^{}}$ . Eventually, $S$ sends the complete transcript to $A$ .
Finally, $S$ outputs whatever $A$ outputs. If $A$ guesses the random bit correctly, then $S$ can break the IND security of the computational fuzzy extractors. Since at most N users and M servers in the system, we have $\begin{array}{l} (8) & | {Adv}_{1}^{RFS-RUA} - {Adv}_{2}^{RFS-RUA} | ⩽ N \cdot M \cdot {Adv}_{S}^{IND} (λ) . \end{array}$

$G_{3}$ : This game is identical to game $G_{2}$ except that at challenge stage, $S$ replace the real verification key of digital signature $σ_{i}$ by a random key over $Z_{q}^{n \times k}$ . Below we show that the difference between $G_{2}$ and $G_{3}$ is negligible under the assumption that the decisional ${SIS}_{q, n, m, d}$ is hard.

Let $S$ denote a decisional SIS problem distinguisher, who is given a pair $(A^{}, t^{})$ , aims to decide it whether from a ${SIS}_{q, n, m, d}$ distribution or from a random distribution over $Z_{q}^{n \times m} \times Z_{q}^{n}$ . $S$ simulates the game for $A$ as follows.
Setup: $S$ sets up the game for $A$ by creating N users and M servers with the corresponding identities and biometrics. $S$ generates enrolled public/secret key pairs $({p k}_{i}^{j}, {s k}_{i}^{j})$ and sketches $SS (w_{i}, {s k}_{i}^{j})$ for N users and M servers. Eventually, $S$ sends all identities, public keys and sketches to $A$ . In particular, $S$ sets $A_{3}^{⊤} = \underline{A^{* ⊤}}$ and honestly generates other public parameters (such as matrixes $A_{1}, A_{2}$ ) for the system. Note that ${p k}_{i}^{j} = A^{* ⊤} \cdot {s k}_{i}^{j}$ .

Training: $S$ honestly simulates the session execution (using user’s secret keys and biometrics) according to the protocol specification.

Challenge: Upon receiving challenge candidates $({ID}_{0}, {ID}_{1}) \in U_{0}^{'}$ from the $A$ , $S$ follows the security game to select ${ID}_{b}^{}$ and server j. $S$ simulates the the transcript as follows.
generate a ciphertext $C_{i}$ on the identity of user i;

choose $s^{'} \in_{R} Z_{q}^{n}$ and compute a new sketch $SS (w_{b}, {s k}_{b}^{'}) \leftarrow A^{} \cdot s^{'} + w_{b}$ ;

choose nonces $n_{i}, n_{j}$ and form a message ${msg}_{(i, j)} = (n_{i}, n_{j})$ ;

generate a message-signature pair $({msg}_{(i, j)}, σ_{b}^{})$ (by design, $σ_{b}^{} = (z_{b}^{}, c_{b}^{})$ ) using the same method described in the security proof of [21]; Note that the corresponding public (verification) key is ${p k}_{b}^{^{'}} = \underline{U^{}} + A_{3}^{⊤} \cdot Δ (s k)$ , where $Δ (s k)$ derives from public sketches.

return $(C_{i}, {msg}_{(i, j)}, \underline{σ_{b}^{}}, SS (w_{b}, {s k}_{b}^{'}))$ as the complete transcript.
Finally, $S$ outputs whatever $A$ outputs. Notice that the enrolled public key ${p k}_{b}$ is replaced by the given instance $\underline{U^{}}$ in the Challenge stage. Moreover, the simulated message-signature pair $({msg}_{(i, j)}, σ_{b}^{})$ can be successfully verified under verification key ${p k}_{b}^{^{'}}$ (by programming random oracle such that $H (A^{} \cdot z_{b}^{} - {p k}_{b}^{^{'}} \cdot c_{b}^{}, {msg}_{(i, j)}) = c_{b}^{}$ ). As for the matrix pair $(A^{}, U^{})$ , according to the hybrid argument, distinguishing the real public key from a uniform distribution $(A^{}, U^{}) \in Z_{q}^{n \times m} \times Z_{q}^{n \times k}$ is as hard as the ${SIS}_{q, n, m, d}$ decisional problem (but with a loss of factor k in the advantage). Therefore, the two verification keys ${p k}_{b}^{^{'}}$ ( $b = [0, 1]$ ) are statistically indistinguishable w.r.t. high-density SIS or computational indistinguishable w.r.t. low-density SIS. Since at most N users and M servers in the system, we have $\begin{array}{l} (9) & | {Adv}_{2}^{RFS-RUA} - {Adv}_{3}^{RFS-RUA} | ⩽ N \cdot M \cdot k \cdot {Adv}_{S}^{{SIS}_{q, n, m, d}} (λ) . \end{array}$
Combining the above results together, we have $\begin{array}{l} {Adv}_{A}^{RFS-RUA} (λ) ⩽ M \cdot K \cdot {Adv}_{S}^{IND-CPA} (λ) + N \cdot M \cdot ({Adv}_{S}^{IND} (λ) + k \cdot {Adv}_{S}^{{SIS}_{q, n, m, d}} (λ)) . \end{array}$
□

6. Conclusion

In this work, we have proposed a lattice-based construction for remote user authentication from reusable fuzzy signature RFS. First, the RFS-based remote user authentication had biometrics reusability, such that the user’s biometrics can be reused multiple times to secure user authentication. Second, the RFS-based remote user authentication had a privacy guarantee against the eavesdroppers. Third, the RFS-based remote user authentication had proven secure in the random oracle model under our defined security models (user authenticity and user privacy). As our future work, we leave the construction of RFS based on efficient ring-SIS or ring-LWE [15,24].

Footnotes

Acknowledgments

This work is partially supported by enPiT(Education Network for Practical Information Technologies) at MEXT, and Innovation Platform for Society 5.0 at MEXT. Yingjiu Li was supported in part by the Ripple University Blockchain Research Initiative. Robert Deng was supported in part by the AXA Research Fund.

Privacy concerns on [ 22,28,29 ]

We assume the Enrollment stage is also executed in a secure channel, which means the attackers cannot access user’s enrolled public keys. According to the generic construction in [22] (also applicable to [28]), we assume an authorized user Alice wants to authenticate herself to an authentication server, and produces a transcript $\underline{({p k}_{A}^{'}, SS (w_{A}^{'}, {s k}_{A}^{'}), σ_{A}^{'})}$ in one session, where the new public key is ${p k}_{A}^{'} = g^{{s k}_{A}^{'}}$ . In another session, suppose a challenge identity ${ID}_{b}^{*}$ generates a transcript $({p k}_{{ID}_{b}}^{*}, SS (w_{{ID}_{b}}^{*}, {s k}_{{ID}_{b}}^{*}), σ_{{ID}_{b}}^{*})$ , where the new public key is ${p k}_{{ID}_{b}}^{*} = g^{{s k}_{{ID}_{b}}^{*}}$ . Then attacker can link the challenge identity ${ID}_{b}^{*}$ to user Alice. Specifically, an attacker will verify the signature $σ_{{ID}_{b}}^{*}$ using the new public key ${p k}_{{ID}_{b}}^{*}$ first; then compute the “difference” $Δ ({s k}_{{ID}_{b}}^{*}) \leftarrow SS (w_{{ID}_{b}}^{*}, {s k}_{{ID}_{b}}^{*}) - SS (w_{A}^{'}, {s k}_{A}^{'})$ ; eventually, attachers can verify the relationship between new public keys ${p k}_{{ID}_{b}}^{*}$ and ${p k}_{A}^{'}$ via a “difference reconstruction” algorithm $M_{{p k}_{A}^{'}} (p p, {p k}_{A}^{'}, Δ ({s k}_{{ID}_{b}}^{*})) \overset{?}{=} {p k}_{{ID}_{b}}^{*}$ . Notice that if algorithm $M_{{p k}_{A}^{'}}$ outputs 1, then attacker can conclude that the challenge user ${ID}_{b}$ is user Alice. The key point here is that the new public key of user Alice ${p k}_{A}^{'}$ in one session actually acts as an enrolled public key, and can be easily linked with the new public key ${p k}_{{ID}_{b}}^{'}$ in another session of the same user, assuming user Alice (with biometrics $w_{A}^{'}$ and $dist (w_{A}^{'}, w_{{ID}_{b}}^{*}) ⩽ t$ ) is successfully authenticated by an authentication server.

Our Treatment. We modify the verification process, in which the verification of signature requires the enrolled public key of user Alice ${p k}_{A}$ . We follow the example above, user Alice first generates her new secret key ${s k}_{A}^{'}$ for signing a message, then computes a new sketch $SS (w_{A}^{'}, {s k}_{A}^{'})$ . The user Alice sends the transcript $\underline{(SS (w_{A}^{'}, {s k}_{A}^{'}), σ_{A}^{'})}$ to an authentication server. The authentication server first obtains the “difference” value $Δ ({s k}_{A})$ from enrolled and new sketches, then computes her new public key ${p k}_{A}^{'} \leftarrow M_{{p k}_{A}} (p p, {p k}_{A}, Δ ({s k}_{A}))$ and verifies the message-signature pair $(m, σ_{A}^{'})$ using the corresponding new public key ${p k}_{A}^{'}$ . Notice that the major difference between two transcripts (underline parts) is: our treatment does not transmit new public key in the public channel. In fact, the verification of message-signature pair is based on the designated verifier concept [17] such that the authentication server who holds the enrolled public key can verify it. We stress that the publicly verifiable of message-signature pair is the main privacy concern in [22,28,29].

Fuzzy extractor

A fuzzy extractor converts a non-uniform data to uniformly random strings, which can be used in cryptographic applications. A typical application of fuzzy extractor is to extract reproducible string from biometric information. Then, the extracted string is considered as a secret for user authentication.

Secure sketch and fuzzy extractor. Secure sketch is a building block of fuzzy extractors. A secure sketch scheme takes noisy information w as input, outputs a sketch $SS$ which is an auxiliary string. Secure sketch schemes normally use error correcting techniques to recover w given $SS$ and $w^{'}$ , if the given input $w^{'}$ is statistically close to w. The sketch $SS$ can be published since it does not reveal any information about w. Let $M$ be a metric space on N points with distance function $dist : M \times M \to R^{+} = [0, \infty)$ , where $N = | M |$ . A secure sketch is defined below.

Fuzzy extractor extracts a non-uniform string from a noisy input $w \in M$ . The difference is that fuzzy extractor returns a uniform string, but secure sketch returns a non-uniform string.

Since sketch reconstructs the original input from noisy data, it can be used to construct fuzzy extractor. So, the helper data P contains sketch $SS$ .

Digital signature

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.

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,

Cash and

Miller, Cryptography secure against related-key attacks and tampering, in: ASIACRYPT, 2011, pp. 486–503.

Bellare,

Pointcheval and

Rogaway, Authenticated key exchange secure against dictionary attacks, in: EUROCRYPT, 2000, pp. 139–155.

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, Vol. 3494, 2005, pp. 147–163.

Canetti,

Fuller,

Paneth,

Reyzin and

A.D.

Smith, Reusable fuzzy extractors for low-entropy distributions, in: EUROCRYPT, 2016, pp. 117–146.

Dodis,

Reyzin and

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

10.

Döttling and

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

11.

Ducas,

Durmus,

Lepoint and

Lyubashevsky, Lattice signatures and bimodal Gaussians, in: CRYPTO, 2013, pp. 40–56.

12.

Fiat and

Shamir, How to prove yourself: Practical solutions to identification and signature problems, in: CRYPTO, 1986, pp. 186–194.

13.

Fuller,

Meng and

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

14.

Gentry,

Peikert and

Vaikuntanathan, Trapdoors for hard lattices and new cryptographic constructions, in: STOC, 2008, pp. 197–206.

15.

Güneysu,

Lyubashevsky and

Pöppelmann, Practical lattice-based cryptography: A signature scheme for embedded systems, in: CHES, 2012, pp. 530–547.

16.

A.K.

Jain,

Prabhakar,

Hong and

Pankanti, FingerCode: A filterbank for fingerprint representation and matching, in: Computer Vision and Pattern Recognition, IEEE Computer Society Conference on., Vol. 2, 1999, pp. 187–193.

17.

Jakobsson,

Sako and

Impagliazzo, Designated verifier proofs and their applications, in: EUROCRYPT, 1996, pp. 143–154.

18.

Juels and

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

19.

Kamp and

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

20.

Li,

Guo,

Mu,

Susilo and

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

21.

Lyubashevsky, Lattice signatures without trapdoors, in: EUROCRYPT, 2012, pp. 738–755.

22.

Matsuda,

Takahashi,

Murakami and

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

23.

Micciancio, Lattice-based cryptography, in: Encyclopedia of Cryptography and Security, 2011, pp. 713–715. doi:10.1007/978-1-4419-5906-5_417.

24.

Peikert, A decade of lattice cryptography, Foundations and Trends ^® in Theoretical Computer Science 10(4) (2016), 283–424. doi:10.1561/0400000074.

25.

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

26.

C.-P.

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

27.

P.W.

Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Review 41(2) (1999), 303–332. doi:10.1137/S0036144598347011.

28.

Takahashi,

Matsuda,

Murakami,

Hanaoka and

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

29.

Takahashi,

Matsuda,

Murakami,

Hanaoka and

Nishigaki, Signature schemes with a fuzzy private key, IACR Cryptology ePrint Archive 2017 (2017), 1188.

30.

Tian,

Li,

R.H.

Deng,

Li,

Wu and

Liu, A new framework for privacy-preserving biometric-based remote user authentication, Journal of Computer Security (2020), 1–30.

31.

Waters, Efficient identity-based encryption without random oracles, in: EUROCRYPT, 2005, pp. 114–127.

32.

Wen and

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

33.

Wen,

Liu and

Han, Reusable fuzzy extractor from the decisional Diffie–Hellman assumption, Designs, Codes and Cryptography 86(11) (2018), 2495–2512. doi:10.1007/s10623-018-0459-4.

34.

Yasuda,

Shimoyama,

Takenaka,

Abe,

Yamada and

Yamaguchi, Recovering attacks against linear sketch in fuzzy signature schemes of ACNS 2015 and 2016, in: ISPEC, 2017, pp. 409–421.

Lattice-based remote user authentication from reusable fuzzy signature

Abstract

Keywords

1. Introduction

1.1. Related work

2. Preliminaries

2.1. Complexity assumptions

Definition 2.1 ( SIS q , n , m , d Distribution).

Definition 2.2 (Decisional SIS [21]).

Definition 2.3 (Decisional LWE [25]).

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

3.1. Construction

3.2. Reusability analysis

4.1. Definition

Footnotes

Acknowledgments

Privacy concerns on [ 22,28,29 ]

Fuzzy extractor

Digital signature

References

Definition 2.1 ( ${SIS}_{q, n, m, d}$ Distribution).