# An efficient biometric identity based signature scheme.

1. IntroductionBiometric technology has been used to ensure a higher level of security. It is adopted in important areas of the national infrastructure, such as electronic passports, visa application and immigration control systems. Biometric keys have many advantages over common cryptographic credentials. They are unforgettable, difficult to copy or share, un-transferable and do not need to be stored, while typical keys can be forgotten, lost, stolen and can not provide non-repudiation [1]. Cryptosystems based on biometric characteristics of persons inherently provide solutions to these problems [2].

Identity based scheme (IBE) [3] is a public key cryptosystem that allows the user to choose his email address or telephone number as public key, instead of generating a random pair of public/private keys. A private key generator (PKG) computes private keys from master secret key and distributes these to the entities participating in the scheme. IBE system has its strengths and weaknesses. The chief disadvantage of such schemes is that they did not allow human biometric characteristics to be used as identities. Since the value of a biometric sample is often disturbed by many noises and has distortion when sampled, we could not utilize available identity based schemes.

In 2005, Sahai and Waters [4] proposed a new concept "fuzzy identity based encryption" in which identities are regarded as a set of descriptive attributes instead of a string of social characters in previous identity based encryption systems [5, 6]. In 2007, Burnett, Duffy and Dowling [7] presented the concept of biometric identity based signature(Bio-IBS), where they used the biometric information to construct the key yet has no concrete scheme. In 2008, Liu et al. [8] proposed a new special Bio-IBS scheme. However, it focuses on the algorithm to generate key string from a biometric measurement of signer rather than the construction of Bio-IBS. A toy Bio-IBS scheme is presented in [8] without any security proof. Up to now, the existing Bio-IBS scheme is very few.

In this paper, we present a new Bio-IBS scheme which possesses low communication overhead and high security simultaneously. In our case, biometric measurements such as fingerprints [9], eye retinas and irises [10], voice patterns [11] and facial patterns [12] are utilized to construct the key. Using biometrics in cryptosystem however arouse a question that how to turn biometric data into key and reproduce the key from noisy biometric information. There are three steps to overcome this problem. First, extract biometric feature from raw biometric information with reader equipment. Second, transform the data into identity utilizing an encoding function of error correcting code [13]. Then, decoding function is used to reproduce the key string from biometric information which may be disturbed by many noises and distortion when is sampled. Thus, our construction has features of strong error tolerance and flexibility. We also present the concrete scheme model and security model of Bio-IBS. Furthermore, under the Computational Diffie-Hellman (CDH) assumption, our scheme is provably secure against existential unforgeable chosen message attack (EU-CMA). This assumption is more natural than the hardness assumptions which have been recently introduced to other schemes. Hence, the proposed scheme is secure.

The rest of the paper is organized as follows. In section 2, we briefly outline the concept of bilinear map, the harness assumption, threshold secret sharing and fuzzy extractor. In section 3, we formally define a Bio-IBS scheme including the security model. A description of our construction is followed in section 4 and in section 5 we discuss the security and efficiency issues. Finally, our conclusion is drawn in section 6.

2. Preliminaries

2.1 Bilinear Map

Let G and [G.sub.1] be two (multiplicative) cyclic groups of prime order p and g be a generator of G. A bilinear map e is a map e: G x G [right arrow] [G.sub.1] with the following properties:

* Bilinearity: for all u, v [member of] G, a, b [member of] [Z.sub.p], we have e([u.sup.a], [v.sup.b]) = e[(u, v).sup.ab];

* Non-degeneracy: e(g, g)[not equal to]1;

* Computability: there is an efficient algorithm to compute e([u.sup.a], [v.sup.b]) for all u, v [member of] G.

The modified Weil pairing and the Tate pairing are admissible maps of this kind. The security of our scheme described here relies on the hardness of the following problems.

2.2 Computational Diffie-Hellman Assumption

Security of our Bio-IBS scheme will be reduced to the hardness of the CDH problem in the group in which the scheme is constructed. We briefly recall the definition of the CDH problem:

Definition 1 Given a group G of prime order p with generator g and elements [g.sup.a], [g.sup.b] [member of] G for some uniformly chosen a, b[member of][Z.sub.p] as input, the CDH problem is to compute [g.sup.ab].

Definition 2 We say that (t, [epsilon]) CDH assumption holds in group G if there is no adversary running in time at most t can solve the CDH problem in G with an advantage at least [epsilon].

2.3 Shamir's Threshold Secret Sharing

In Shamir's (n, t) threshold secret sharing scheme, a secret s [member of] GF(p) is partitioned into several parts [s.sup.i] as a share of the secret which are distributed among a set of participants {[P.sub.1], ..., [P.sub.n]}. The secret s could be reconstructed by subsets with at least t participants. Shamir's solution utlizes polynomial interpolation to achieve threshold secret sharing. The dealer confidentially selects a polynomial f(x) of degree t - 1 with f(0) = s, i.e.

f(x) = s + [t-1.summation over (i=1)] [a.sub.i][x.sup.i] (mod p).

If each participant [P.sub.i] is assigned a unique element [[alpha].sub.i], the dealer sends [P.sub.i] the secret share [s.sub.i] = f ([[alpha].sub.i]). A participants' group S with [absolute value of S] [greater than or equal to] t can recover the secret s by computing:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

On the other hand, a group T of the less than t participants could not obtain the secret s.

2.4 Generating Key Data from Biometrics

Extract cryptographic keys from biometric data is problematic since biometric information is not perfectly reproducible. Recently, Dodis [14] demonstrates how such data can be used to generate strong keys for any kind of cryptographic application. They propose the notion of fuzzy extractor to describe the process of extracting a random string U from a biometric input b. The extraction is error-tolerant in the sense that if the input changes slightly to b' then the extracted U will be the same. Dodis [14] describes three metrics to measure the variation of input data: Hamming Distance, Set Distance and Edit Distance. Hamming Distance is defined to be the number of bit positions that differ between b and b' and is proved to be the most natural and straightforward metric.

(1) Biometric Fuzzy Extraction

The fuzzy extractor construction using the Hamming distance metric is based on previous work on the fuzzy commitment scheme in [15]. A comprehensive description appears in [14,15]. Formally, a fuzzy extractor is defined as follows:

Let M be a finite dimensional metric space consisting of biometric data points with a distance function d's: M x M [right arrow] [Z.sup.+] which calculates the distance between two points based on the chosen metric. Let n be the number of bits of the extracted output string U and d be the error tolerant parameter. An (M, n, d) fuzzy extractor is constructed with two functions Gen and Rep. Gen is a generation procedure. On input b[member of] M, the function outputs an "extracted" string U[member of][{0,J}.sup.n] and public string V. Rep is a reproduction procedure allows recovery of U from the corresponding public string V and any b' that satisfying d's(b,b')[less than or equal to] d, i.e. [for all] b, b'[member of] M with dis(b,b) [less than or equal to] d, if Gen(b)[right arrow](U,V), then Rep(b',V)[right arrow] U.

(2) Error-correcting Codes

Error-correcting code is an important part of the extraction process which will be mentioned in the next subsection. A code is a subset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] which is referred to as codebook and the elements [c.sub.i] in codebook are called codeword. Given a codebook C, we define a pair of functions <[C.sub.e], [C.sub.d]>. The encoding function [C.sub.e]: M [right arrow] C represents a one-to-one mapping of messages to codewords. The decoding function [C.sub.d]: [{0,J}.sup.n][right arrow] C is used to map the received arbitrary n-bit string to codeword. For instance, the decoding function of [n, k, 2d + J] BCH error-correcting code maps a given n -bit string x to the nearest codeword in C with an error tolerant threshold of d. More details about BCH code and other error-correcting codes can be found in [13].

(3) The Process of Extraction

We now describe the construction of a fuzzy extractor for the space M = [{0,1}.sup.N] under the Hamming Distance metric.

* Gen function takes the biometrics b as input, then returns [omega] and public parameter V = b [direct sum][C.sub.e] ([omega]), in which a represents the identity of user corresponding to biometrics b. Identity [omega] is used for private key extraction and V is used to recover a when any other b' is given.

* Rep function takes the biometrics b' and V as input and computes: [omega]' = [C.sub.d](b'[direct sum] V) = [C.sub.d](b'[direct sum] b[direct sum][C.sub.e]([omega]) = [C.sub.d] (e' [direct sum] [C.sub.e] ([omega]))

where e' = b [direct sum] b'. Identity [omega]' = [omega] if and only if dis (b,b') [less than or equal to] d.

(4) Fuzzy Extractor from Sketches

A fuzzy extractor [14] extracts nearly uniform randomness R from its biometric input; the extraction is error-tolerant in the sense that R will be the same even if the input changes, as long as it remains reasonably close to the original.

Assume SS is a (M,m,m', t) -secure sketch with recovery procedure Rec, and let Ext be the (n,m',l, [epsilon]) -strong extractor based on pairwise-independent hashing (in particular, l = m' - 2 log(1/[epsilon])). Then for uniformly distributed randomization strings [X.sub.1], [X.sub.2] the following algorithms (Gen, Rep) is a (M, m, m', t) -fuzzy extractor:

--Gen(W; [X.sub.1], [X.sub.2]) : set P = <SS(W; [X.sub.1]),[X.sub.2]>, R = Ext(W;[X.sub.2]), output <R, P>.

--Rep(W',<V, [X.sub.2]>): recover W = Rec(W', V)and output R = Ext(W;[X.sub.2]).

Theorem 1. [21] Let [M.sub.l], ..., [M.sub.m] be n x n -matrices over GF(2) such that for every non-empty subset I [subset] [m] the matrix [summation over (i[member of] l)[M.sub.i] is invertible. Then the function Ext: [([{0,1}.sup.n).sup.N]] [right arrow] [{0,1}.sup.m] defined by

Ext( [x.sub.1], ..., [x.sub.n]) = ([summation over (s<1)]<[x.sub.s], [M.sub.l][x.sub.t]), [summation over (s<1)]<[x.sub.s], [M.sub.m][x.sub.t]>)

is a [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] -strong extractor, where log (1/[epsilon]) = k - n/2 -m + 1.

Note: The efficient construction of suitable matrices [M.sub.1], ..., [M.sub.m] in the theorem is discussed in [22].

Comment: The construction of a secure fuzzy extractor to resist various kinds of attacks is an important research topic in biometric information and cryptography. For different biometric characteristics and metrics, there are distinct designs of fuzzy extractors [23-34] to be chosen according to the practical usage.

2.5 Formal Definition of Bio-IBS

2.5.1 Bio-IBS Scheme

A biometric identity based signature scheme consists of the following four algorithms Setup, Extract, Sign and Verify. They are specified as follows:

* Setup: Given a security parameter k and error tolerant parameter d, the algorithm generates the master secret key MK and the public parameters PK of the system.

* Extract: Given a biometric string b (identity [omega] is obtained using a fuzzy extractor) and master secret key MK, the algorithm returns the corresponding private key [K.sub.[omega]].

* Sign: Given the public parameters PK, private key [K.sub.[omega]] corresponding to identity [omega] and a message M, the algorithm outputs signature [sigma].

* Verify : Given the public parameters PK, a biometric string b', the message M and corresponding signature [sigma], the algorithm accepts [sigma] if it is valid and outputs [perpendicular to] otherwise.

2.5.2 Security Model

Definition 3: A Bio-IBS is existentially unforgeable against chosen message attack (EU-sID-CMA) if no attacker has a non-negligible advantage in the following game.

* Init: Adversary A outputs a challenge biometric data b*. Challenger C extract the challenge identity [omega]* (corresponding to b*) through fuzzy extractor.

* Setup: Challenger C runs the setup algorithm and sends adversary A the public parameters PK.

* Query Phase: Adversary A issues private key extract queries and signature queries.

a) Extract queries: A issues private key extract queries for biometric string b, where b [not equal to] b*. In response, C obtains the corresponding identity [gamma] using fuzzy extraction algorithm and then runs Extract algorithm to get the private key [K.sub.[gamma]] and sends it to A.

b) Signing queries: A issues signature queries of identity [omega]* and any message M. In response, C runs the Extract algorithm to obtain the private key [K.sub.[omega]*] and then runs Sign algorithm to obtain a signature [sigma], which is forwarded to A.

* Challenge: Adversary A outputs [sigma]* tuple ([omega]*, M*, [sigma]*) where M* [not equal to] M for all M got from signing query phase. If [sigma]* is a valid signature of ([omega]*,M*), then A wins.

Definition 4: We say that a Bio-IBS is (t, [epsilon], [q.sub.E], [q.sub.S]) -EU-sID-CMA secure if all t time adversaries making at most [q.sub.E] private key extract queries, [q.sub.S] signing queries have advantage at most [epsilon] in winning the above game.

Note: The extract and sign algorithms in security model are identical to those in Bio-IBS scheme. The extract and sign queries are used to simulate that the adversary has the ability to obtain signature of any message that he wants, i.e., the process to choose message. Then, adversary's probability [epsilon] to win the game means the probability that an adversary could forge a new signature in a chosen message attack (CMA). When [epsilon] is negligible, the adversary could not succeed in CMA attack. Then, the signature is existentially unforgeable (EU) against chosen message attack (CMA).

3. An Efficient Bio-IBS Scheme

In this section, we define some notations for this paper and propose a secure and efficient biometric identity based signature scheme. The proposed scheme involves three roles: a system authority (AU), signer (SG) and a verifier (VF). We assume that AU is responsible for a private key generation center. Due to the noisy nature of biometrics, the proposed Bio-IBS allows for error tolerant in the verification phase, where a signature signed with the identity [omega] (extracted from biometric data b) could be verified by the identity [omega]' that is extracted from biometric data b, provided that [omega] and [omega]' are within a certain distance of each other.

3.1 Notations

* [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]: a supersingular elliptic curve E: [y.sup.2] = [x.sup.3] - x +1 (mod[3.sup.k])

* G: a multiplicative group of the elliptic curve E whose order is a large prime p

* g: a generator of G whose order is p

* [G.sub.1]: a multiplicative group of the elliptic curve E whose order is p

* e: a bilinear pair map, e: G x G [right arrow] [G.sub.1]

* M: the content of a message

* [C.sub.e]: encoding function of error-correcting code

* [C.sub.d]: decoding function of error-correcting code

* d: the error tolerant parameter, which represents the distance that is allowed between two identities for successful verification

* H: a one-way hash function, H: {0,1}* [right arrow] G

3.2 Proposed Scheme

3.2.1 Setup phase

AU selects a random [g.sub.1][member of] G. Next, AU chooses a master-key s[member of][Z.sup.*.sub.p] and computes [g.sub.2] = [g.sup.s], A = e([g.sub.l],[g.sub.2]). Randomly choose [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and compute [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], Then SG publishes the system's public parameters

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

the master key MSK = s is kept secret.

3.2.2 Extract phase

In this phase, signer SG performs the following steps to register to AU and obtain his private key.

* SG sends his biometric b to AU.

* AU extracts identity [omega] = ([[mu].sub.1], ..., [[mu].sub.n]), [[mu].sub.i] [member of] {0,1} from b through fuzzy extractor.

* AU generates SG's private key as follows:

a) Choose a random d - 1 degree polynomial p(x) = [a.sub.0] + [a.sub.1] x + ... + [a.sub.d-1] [x.sup.d-1] such that P(0) = [a.sub.o] = s.

b) For each [[mu].sub.i][member of][omega], compute [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

c) AU sends [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to SG confidentially.

Thus, SG obtains his private key [K.sub.[omega]] that is corresponding to his biometric b.

3.2.3 Signature phase

To sign a message represented as a bit string [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for identity [omega] using private key [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], SG calculates V = b[direct sum][C.sub.e]([omega]) as fuzzy commitment [15] used for verification. Then, SG selects a random [s.sub.i][member][Z.sub.p] for each [[mu].sub.i][member of][omega] and outputs signature

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3.2.4 Verification phase

Given a signature [sigma] on a message M for identity [omega], VF performs the following steps:

* Obtain user's biometric information b' and calculate [omega]' = [C.sub.d](b'[direct sum] V) in order to obtain [omega]' = ([[mu].sub.1]', ..., [[mu].sub.b]').

* If |[omega][intersection][omega]'|< d, PF rejects the signature; if |[omega][intersection][omega]'|[greater than or equal to] d, go to the next step.

* VF chooses an arbitrary set S ?? [omega][intersection][omega]' such that [absolute value of S]= d. VF accepts the signature if and only if the following equation holds, otherwise rejects it.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

* If there is a dispute between SG and VF, VF can passes (M, [sigma], [omega], [omega]') to a third party (the message M has no need to be secret). The third party can verify the validity of the signature by Eq.(1).

3.3 Correctness

For all [[mu].sub.i][member of S, we have [[mu].sub.i] = [[mu].sub.i]'. Then, correctness of the scheme is justified as follow.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3.4 Efficiency Analysis

The number of group elements in the public parameters grows linearly with the length of message, i.e. [n.sub.m] + 4 elements from group G and one element from group [G.sub.1]. The number of group elements that compose a signer's private key and resulting signature [sigma] grows linearly with the number of identities associated with the signer.

The number of scalar multiplications in group G for a signer to sign a message will be linear with the length of signer's identity. The procedure of signing does not need any bilinear pairing computations. The cost of verification is dominated by 3d bilinear pairing operations.

4. Comparison of Existing Schemes

4.1 Notations

We first define some notations for the comparison.

* size of PP: size of public parameters

* n: length of identity

* [n.sub.m]: length of message

* [absolute value of G]: bit-length of an element in G

* [absolute value of [G.sub.1]]: bit-length of an element in [G.sub.1]

* [absolute value of [Z.sub.p]]: bit-length of an element in [Z.sub.p]

* [rho]: time of one exponentiation in [G.sub.1]

* [tau]: time of one scalar multiplication in G

* [t.sub.Pair]: time of one pairing operation in G

* (k +1)-EP: (k +1) Exponential Problem

4.2 Comparison

(1) By comparing the features of our scheme with other signature schemes [7, 8, 16-20] in Table 1, we can see that our scheme not only satisfies the security properties for signature scheme but also eliminates the certificate problem. Furthermore, biometric data is utilized to derive user's public key and private key.

(2) Table 2 shows the performance comparison between the Burnett et al.'s Bio-IBS scheme [7], Liu et al.'s Bio-IBS scheme [8] and ours in terms of system parameter size, private key size, signature size, private key extraction cost, signing cost, verification cost, hardness assumption and security proof.

a) In [7], Burnett's scheme has no concrete construction of Bio-IBS, let alone security proof.

b) Liu's scheme [8] focuses on how to extract identity from biometric data and presents a toy scheme without any security proof.

c) To the author's knowledge, our scheme is the first Bio-IBS scheme with concrete construction and detailed security proof.

(3) Since fuzzy IBS possesses similar error-tolerance property as Bio-IBS, we compare the classical fuzzy IBS schemes [16, 17] and our Bio-IBS scheme in Table 3. We can see that our scheme achieves higher efficiency and stronger security.

a) The security of our Bio-IBS scheme is reduced to computational Diffie-Hellman(CDH) assumption, as well as the scheme in [16]. While in [17], the scheme is secure if (k +i) -EP assumption holds. Since the hardness of CDH problem is stronger than (k + i) -EP problem, the security of [16] and ours are stronger than [17].

b) Compared with [16], our scheme has shorter sizes of public parameters. Hence, communication overhead is decreased in our scheme. Moreover, [16] requires more computation in the private key extraction. Thus, our scheme has better performance than [16].

c) The chief drawback of [17] is that large amount of bilinear pairing operation is required in the private key extraction process. As well known, pairing operation is the most time consuming operation in group G. It means that a user has to spend long time to get a valid private key. Moreover, high security could not be achieved in [17] which is mentioned in (a).

To sum up, our scheme achieves higher efficiency and stronger security compared with the existing schemes. As a result, the communication overhead of the network is decreased and the computation at the users and system authority is reduced.

5. Security Analysis

5.1 Non-repudiation

Any third party can be convinced of the message's origin by step 4 in Section 3.2.

5.2 Unforgeability

Theorem 2. Suppose the (t', [epsilon]') CDH assumption holds in G, then the constructed Bio-IBS scheme is (t, [epsilon], [q.sub.E], [q.sub.S]) UF-slD-CMA secure, where

[epsilon]' = [epsilon]/([q.sub.E] + [q.sub.s),] t' = t + O(d([rho] + [tau])[q.sub.E] + ([rho] + [tau])[q.sub.s]))

[rho] is the time for an exponentiation, [tau] is the time for a multiplication and d is the error tolerant parameter.

Proof: Suppose there exists a (t, [epsilon], [q.sub.E], [q.sub.S]) adversary A against our scheme, then we construct an algorithm C that solves the CDH problem with probability at least [epsilon]' and in time at most [tau]'. The challenger C is given a tuple (g, [g.sup.a], [g.sup.b]) of the CDH problem. The game between A and C proceeds as follows.

* Init. Adversary A outputs a challenge biometric data b*, C can extract the challenge identity [omega]* = ([[mu].sup.*.sub.i], ..., [[mu].sup.*.sub.n]) through fuzzy extractor.

* Setup.

1) Challenger C sets [l.sub.m] = [q.sub.E] + [q.sub.S] and randomly chooses integer k[member of][Z.sub.p]. Select at random [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

2) Define functions for message M as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3) Then challenger C calculates a set of public parameters as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where 1 [less than or equal to] j [less than or equal to] [n.sub.m].

4) We can also obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

5) Challenger C outputs the public parameters [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

* Hash Queries. Adversary A is allowed to issue hash query in any phase. Upon receiving a query on [[omega].sub.i], if there exists [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in H-list, return [h.sub.i]. Otherwise, do the following.

1) If [[omega].sub.i] = [omega]*, choose l* [member of] [Z.sub.p] at random and compute [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

2) Else, randomly select [l.sub.i] [member of] [Z.sub.p] and compute [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

3) Add ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) to H-list and return [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as answer.

* Phase 1.

Extract queries. Upon receiving a biometric b for private key extract query, challenger C do the following to simulate the private key.

1. Challenger C extracts identity y of b with fuzzy extractor, where [gamma] = ([[mu].sub.i], ..., [[mu].sub.n]).

2. C judges the relationship between [gamma] and [omega]*:

- If |[gamma] [intersection] [omega]* |< d, challenger C sets [GAMMA] = [gamma] [intersection] [omega]* and let [GAMMA]' be any set such that [GAMMA] ?? [GAMMA]' ?? [gamma], [absolute value of [GAMMA]'] = d-1 Then, let S = [GAMMA]' [union] {0}.

refer, |r'|=J-l.Then, let S = T'U{0}.

- If |[gamma][intersection][omega]*| [greater than or equal to] d, challenger C sets [GAMMA] = [gamma] [intersection] [omega]* and let [GAMMA]' be any set such that [GAMMA]' ?? [GAMMA] ?? [gamma], [absolute value of [GAMMA]'] = d-l. Then, let S = [GAMMA]' [union]{0}.

3. Challenger C constructs the private key.

- For every [[mu].sub.i][member of] [GAMMA]', run the above hash query to get ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) in H-list. Then, pick [[lambda].sub.i] [member of [Z.sub.p] at random and compute [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Now define [[lambda].sub.i] = p([[mu].sub.i]) for a random polynomial p(.) of degree d-1 such that p(0) = b. Thus challenger C has successfully constructed [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

--For every [[mu].sub.i][member of][lambda]\[GAMMA]', run the above hash query to get [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in H-list and compute:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Note that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, challenger C has successfully simulated the private key [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Signing queries. To answer the signing query on [omega]* for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], if F(M) [equivalent to] 0 (mod [l.sub.m]), the challenger C aborts. Otherwise,

1. C selects a random set [GAMMA] such that [GAMMA][member of][omega]* and [absolute value of [GAMMA]] = d-1. Let S = [GAMMA][union]{0}.

--For [[mu].sub.i][member of][GAMMA], randomly pick [r.sub.i][member][Z.sub.p] and define q(i) = [r.sub.i] for a random polynomial q(.) of degree d-1 over [Z.sub.p] such that q(0) = b.

--For [[mu].sub.i][member of][omega]*\[GAMMA], challenger C computes:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

2. Challenger C chooses random [s.sub.i][member of][Z.sub.p] for every [[mu].sub.i][member of][omega]* and calculates:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3. Set ?? = [s.sub.i] - q(i)/F(M). Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for identity [omega]*, we have that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It shows that [[sigma].sup.(i).sub.1], [[sigma].sup.(i).sub.2], [[sigma].sup.(i).sub.3] are correctly simulated.

Challenge. Adversary A generates a valid forgery [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for identity [omega]* on message [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where M*[not equal to] M for all M got from signing query phase.

1. Challenger C define:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

2. If F(M*) [not equal to] 0(mod p), challenger C aborts. Otherwise, the signature must be the following form:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

for some [s.sup.*.sub.i][member of][[Z.sub.p]. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3. Challenger C selects a random set [LAMBDA] such that [LAMBDA] ?? [omega]* and [absolute value of [LAMBDA]] = d and calculates:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where W = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

4. Challenger C could solve the CDH problem by computing

[[sigma].sup.*.sub.1] x_[[sigma].sup.*.sub.2] x ([[sigma].sup.*.sub.1]).sup.J(M*) = [g.sup.b.sub.1] = [g.sup.ab].

* Probability Analysis: Let abort be the event that the simulated game aborts.

1. We require F(M) [not equal to] 0(mod [l.sub.m]) in signing phase which means that K(M) = 1 (mod [l.sub.m]) and occurs with probability [(1-1/[l.sub.m]).sup.[q.sub.S]].

2. We require F(M*) = 0(mod [l.sub.m]) in challenge phase which means that K(M*) = 0 (mod [l.sub.m]) and occurs with probability 1/[l.sub.m].

3. Then:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

* Time Analysis: The running time of the simulation is dominated by the multiplication and exponent operation in the query phase. Then we have

t' = t + O(d ([rho] + [tau])[q.sub.E] + ([rho] + [tau])[q.sub.s])

5. Conclusion

Biometric technology has been attracting considerable attention in recent years and mainly been for highly secretive environments. In this paper, we have proposed an efficient biometric identity based signature scheme. With the adoption of Shamir's threshold secret sharing and error correction code, the suggested scheme is error tolerant and flexible. Moreover, this scheme is proved unforgeable against adaptive chosen message attack. Compared with the previous works, the proposed scheme is more secure and efficient. Meanwhile, the scheme will decrease the computational costs and improve communication efficiency of the system. An open problem is to construct efficient biometric identity based signature scheme in standard model.

This work is partially supported by the "973" program of China under Grant 2007CB311201 and the National Natural Science Foundation of China under Grants 60970119, 61072067, 61103175, 61100231, 61202350. This work was also supported by the Technology Innovation Platform Project of Fujian Province (No.2009J1007) and Natural Science Basic Research Plan in Shaanxi Province (No.2012JQ8044).

http://dx.doi.org/10.3837/tiis.2013.08.015

References

[1] Tang Q, Bringer J, Chabanne H, and Pointcheval D, "A formal study of the privacy concerns in biometric-based remote authentication schemes," in Proc. of 4th Int. Conf. on Information Security Practice and Experience, vol. 4991, pp. 56-70, April 21-23, 2008. Article (CrossRef Link)

[2] Uludag U, "Biometric cryptosystems: issues and challenges," Proceedings of the IEEE, vol. 92, no. 6, pp. 948-960, 2004. Article (CrossRef Link)

[3] Boneh D, and Boyen X, "Secure identity based encryption without random oracles," in Proc. of 24th Annual Int. Cryptology Conf., vol. 3152, pp. 443-459, August 15-19, 2004. Article (CrossRef Link)

[4] Sahai A, and Waters B, "Fuzzy identity-based encryption," in Proc. of 24th Annual Int. Conf. on the Theory and Applications of Cryptographic Techniques, vol. 3494, pp.457-473, May 22-26, 2005. Article (CrossRef Link)

[5] Kancharla PK, Gummadidala S, and Saxena A, "Identity based strong designated verifier signature scheme," Informatica, vol. 18, no. 2, pp. 239-252, 2007. Article (CrossRef Link)

[6] Sun X, Li J, Yin H, and Chen G, "Delegatability of an identity based strong designated verifier signature scheme," Informatica, vol. 21, no. 1, pp. 117-122, 2010. Article (CrossRef Link)

[7] Burnett A, Byrne F, Dowling T, and Duffy A, "A biometric identity based signature scheme," International Journal of Network Security, vol. 5, no. 3, pp. 317-326, 2007. Article (CrossRef Link)

[8] Liu X, Miao Q, and Li D, "A new special biometric identity based signature scheme," International Journal of Security and its Applications, vol. 2, no.1, pp. 13-18, 2008. Article (CrossRef Link)

[9] Maltoni D, Maio D, Jain AK, and Prabhakar S, Handhook of Fingerprint Recognition, Springer Publishing Company, New York, 2009. Article (CrossRef Link)

[10] Sanjay K, Dijana P, and Bernadette D, "Obtaining cryptographic keys using feature level fusion of iris and face biometrics for secure user authentication," in Proc. of IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops, pp. 138-145, June 13-18, 2010. Article (CrossRef Link)

[11] Rashid RA, Mahalin NH, Sarijari MA, "Security system using biometric technology: design and implementation of voice recognition systems," in Proc. of Int. Conf. on Computer and Communication Engineering, pp. 898-902, May 13-15, 2008. Article (CrossRef Link)

[12] Koelstra S, Pantic M, Dynamic A, "A dynamic texture-based approach to recognition of facial actions and their temporal models," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 32, no. 11, pp. 1-15, 2010. Article (CrossRef Link)

[13] Huffman WC, Pless V, Fundamentals of error-correcting codes, Cambridge University Press, 2003. Article (CrossRef Link)

[14] Y. Dodis, L. Reyzin, A. Smith. "Fuzzy extractors: how to generate strong keys from biometrics and other noisy data," SIAM Journal on Computing, vol. 38, no. 1, pp. 97-139, 2008. Article (CrossRef Link)

[15] Juels A, Wattenberg M, "A fuzzy commitment scheme," in Proc. of the 6th ACM Conf. on Computer and Communications Security, pp. 28-36, November 1-4, 1999. Article (CrossRef Link)

[16] Yang P, Cao Z, and Dong X. "Fuzzy identity based signature." Available in Cryptology ePrint Archive. Article (CrossRef Link)

[17] Wang C, Wei C, Yang L. "A fuzzy identity based signature scheme," in Proc. of Int. Conf. on E-Business and Information System Security, pp. 1-5, October 17-19, 2009. Article (CrossRef Link)

[18] Wang C, Kim JH, "Two constructions of fuzzy identity based signature," in Proc. of 2nd Int. Conf. on Biomedical Engineering and Informatics, pp. 1-5, October 17-19, 2009. Article (CrossRef Link)

[19] Li J, Huang X, Mu Y, Susilo W, Wu Q, "Certificate-based signature: security model and efficient construction." in Proc. of European Public Key Infrastructure Workshop, vol. 4582, pp. 110-125, June 28-30, 2007. Article (CrossRef Link)

[20] Liu J, Baek J, Susilo W, Zhou J, "Certificate-based signature schemes without pairings or random oracles," in Proc. of Information Security Conf., pp. 285-297, September 15-18, 2008. Article (CrossRef Link)

[21] Konig R, and Maurer U, "Generalized strong extractors and deterministic privacy amplification," in Proc. of Int. Workshop on Cryptography and Coding, vol. 3796, pp. 322-339, March 14-18, 2005. Article (CrossRef Link)

[22] Dodis Y, Elbaz A, Oliveira R, and Raz R, "Improved randomness extraction from two independent sources," in Proc. of Int. Workshop on Randomization and Approximation Techniques in Computer Science, pp 334-344, August 22-24, 2004. Article (CrossRef Link)

[23] Kanukurthi B, L. Reyzin, "An improved robust fuzzy extractor," in Proc. of 6th Conf. on Security and Cryptography for Networks, vol. 5229, pp. 156-171, September 10-12, 2008. Article (CrossRef Link)

[24] Yang B, Sun A, and Zhang W, "A Fuzzy Extractor Based on Smooth Entropy," in Proc. of2ndInt. Conf. on Computer Science and its Applications, pp. 1-6, December 10-12, 2009. Article (CrossRef Link)

[25] Skoric B, Tuyls P, Guajardo J, and Preneel B, "An efficient fuzzy extractor for limited noise," Available in Cryptology ePrint Archive. Article (CrossRef Link)

[26] Yang B, Sun A, and Zhang W, "A fully robust fuzzy extractor," in Proc. of IEEE Int. Conf. on Network Infrastructure and Digital Content, pp. 552-556, October 10-11, 2009. Article (CrossRef Link)

[27] Buhan I, Doumen J, Hartel P, and Veldhuis R, "Constructing practical fuzzy extractors using QIM," Tech. Rep. TR-CTIT-07-52, Centre for Telematics and Information Technology, University of Twente, 2007. Article (CrossRef Link)

[28] Skoric B, "Security with Noisy Data I," in Proc. of Int. Conf. on Information Hiding, pp. 79-99, May 15-18, 2007. Article (CrossRef Link)

[29] Skoric B, "Security with Noisy Data II," in Proc. of Int. Conf. on Information Hiding, pp. 101-112, May 15-18, 2007. Article (CrossRef Link)

[30] Ong TS, "Fuzzy key extraction from fingerprint biometrics based on dynamic quantization mechanism," in Proc. of Third Int. Symposium on Information Assurance and Security, pp. 71-76, August 29-31, 2007. Article (CrossRef Link)

[31] Alvarez FH, and Encinas LH, "Biometric fuzzy extractor scheme for iris templates," in Proc. of the 2009 World Congress in Computer Science, Computer Engineering, and Applied Computing, pp. 563-569, July 13-16, 2009. Article (CrossRef Link)

[32] Arakala A, Jeffers J, and Horadam K, "Fuzzy extractors for minutiae-based fingerprint authentication," in Proc. of Advances in Biometrics, vol. 4642, pp. 760-769, August 27-29, 2007. Article (CrossRef Link)

[33] Li Q, Guo M, and Chang E, "Fuzzy extractors for asymmetric biometric representations," in Proc. of IEEE Conf. on Computer Vision and Pattern Recognition Workshops, pp. 1-6, June 23-28, 2008. Article (CrossRef Link)

[34] Sutcu Y, Li Q, and Memon N, "Design and analysis of fuzzy extractors for faces," in Proc. of the SPIE Optics and Photonics in Global Homeland Security V and Biometric Technology for Human Identification VI, vol. 7306, pp. 71-76, April 13-16, 2009. Article (CrossRef Link)

Yang Yang received the Ph.D degree in school of communication engineering from Xidian University of China in 2011. Now she is a faculty in School of Math. & Computer Science of Fuzhou University. Her main research interests include network security and security protocol.

Yupu Hu received the Ph.D degrees in school of communication engineering from Xidian University of China in 2008. Now he is a professor in School of Telecommunication Engineering of Xidian University. His main research interests include information security and cryptography.

Leyou Zhang received the Ph.D degrees in applied mathematics from Xidian University of China in 2009. Now he is an associate professor in Department of Mathematical Sciences of Xidian University. His main research interests include security protocol and public key cryptography.

Yang Yang (1,2), Yupu Hu(3) and Leyou Zhang (3)

(1) College of Mathematics and Computer Science, Fuzhou University, Fuzhou, 350108--China [e-mail: yang.yang.research@gmail.com]

(2) Key Lab of Information Security of Network Systems (Fujian Province Universities), Fuzhou University, Fuzhou, 350108--China

(3) Key Laboratory of Computer Networks and Information Security, Xidian University, Xi'an, 710071--China

[e-mail: xidianzly@163.com]

* Corresponding author: Yang Yang

Received April 23, 2012; revised September 6, 2013; revised October 14, 2013; accepted December 2, 2012; published August 30, 2013

Table 1. Features comparison of different signature schemes [7] [8] [16] [17] [18] [19] [20] Ours Unforgeability X X o o X o o o Non-repudiatioin o o o o o o o o Biometric identity o o X X X X X o Without certificate o o o o o X X o Security proof X X o o X o o o Table 2. Comparison of existing Bio-IBS schemes [7] [8] Security proof No No Size of PP -- 2[absolute value of [Z.sub.p]] Size of Private Key -- [absolute value of [Z.sub.p]] Size of Signature -- 2[absolute value of [Z.sub.p]] Cost of Extract -- [rho] Cost of Sign -- 2[rho] + [tau] Cost of Verify -- 2[rho] + [tau] Hardness Assumption -- -- Ours Security proof Yes Size of PP ([n.sub.m]+4)[absolute value of G] +[absolute value of [G.sub.1]] Size of Private Key 2n[absolute value of G] Size of Signature 3n[absolute value of G] Cost of Extract n(2[rho] p + [tau]) Cost of Sign [n.sub.m](2[rho] p + [tau]) Cost of Verify 3d x [t.sub.pair] + d x [rho] Hardness Assumption CDH Table 3. Comparison of our scheme with different fuzzy IBS schemes [16] Biometric identity No Hardness Assumption CDH Size of PP ([n.sub.m]+n+4)[absolute value of G] +[absolute value of [G.sub.1]] Size of Private Key 2n[absolute value of G] Size of Signature 3n[absolute value of G] Cost of Extract n(3[rho] + 2[tau]) Cost of Sign n(2[rho] + [tau]) Cost of Verify 3d x [t.sub.pair] + d x [rho] [17] Biometric identity No Hardness Assumption (k+1)-EP Size of PP (2n+2)+[absolute value of G] Size of Private Key n+[absolute value of G] Size of Signature (n+1)+[absolute value of G] Cost of Extract n([t.sub.pair] + [rho] + [tau]) Cost of Sign 2n x [tau] Cost of Verify d x [t.sub.Pair] + d x [rho] Ours Biometric identity Yes Hardness Assumption CDH Size of PP ([n.sub.m]+4)+[absolute value of G] + [absolute value of [G.sub.1]] Size of Private Key 2n[absolute value of G] Size of Signature 3n[absolute value of G] Cost of Extract n(2 [rho] + [tau]) Cost of Sign n(2 [rho] + [tau]) Cost of Verify 3d x [t.sub.Pair] + d x [rho]

Printer friendly Cite/link Email Feedback | |

Author: | Yang, Yang; Hu, Yupu; Zhang, Leyou |
---|---|

Publication: | KSII Transactions on Internet and Information Systems |

Article Type: | Report |

Date: | Aug 1, 2013 |

Words: | 6856 |

Previous Article: | RPFuzzer: a framework for discovering router protocols vulnerabilities based on fuzzing. |

Next Article: | A novel reversible data hiding scheme for VQ-compressed images using index set construction strategy. |

Topics: |