# Efficient and provable secure pairing-free security-mediated identity-based identification schemes.

1. Introduction1.1. Background. Identification schemes allow one party, the prover, to prove itself to another party, the verifier, that it knows its secret key without revealing anything else about itself in the process. The main utilization of the identification primitive is to facilitate one-sided entity authentication and is conventionally deployed in access control mechanisms to facilitate resource control and distribution.

In traditional public key cryptography, certificates are used to ensure that a user's public key is legitimately bound to a particular user and cannot be replaced. This certificate is usually issued by a certificate authority. However, certificate management can become an issue when the number of users in a cryptosystem grows larger. One of the methods of mitigating this potentially costly problem is through the deployment of the cryptographic primitive in an identity-based setting introduced by Shamir [1].

Another issue that traditional public key cryptography faces is the revocation of user secret keys. This would necessarily involve the revocation of a user's certificate along with his public/secret key pair and is a costly operation.

Timeliness is also a factor, as the procedure to revoke a user's keys maybe a (relatively) long one and creates additional load on the certificate authority, turning the revocation procedure into a potentially costly process exercise. All these compound the certificate management issue mentioned earlier.

In the identity-based setting, where certificates are not used, key revocation is conventionally done by tagging validity periods onto the user's identity-string as an extension. This also creates an issue of timeliness since revocation is only possible at the end of those validity dates. Without checking certificates, it is also difficult to check if a user is still valid or if his user secret key has been revoked already.

In [2], Boneh et al. proposed the initial groundwork for instant revocation of user keys and privileges, including the public key and certificates by introducing the concept of security-mediated cryptography. The idea of security -mediated cryptography is to necessitate the cooperation of a security mediator, a trusted third party, in any form of transaction that a user needs to use. For example, in an encryption scheme, a security mediator needs to lend his cooperation to the user in order for the user to decrypt a particular ciphertext. And for signatures, a security mediator has to agree to cooperate with a signer in order to produce a valid signature.

Specifically, this is done by separating the user's secret key into two portions during the key generation. One portion of the key is given to the mediator while the other is given to the user. Therefore, the security mediator cooperates in the form of providing his portion of the secret key to be combined with the user's portion to create the full secret key for the transaction.

1.2. Related Work. Identification schemes were first introduced by Fiat and Shamir [3], while their identity-based counterparts, namely, identity-based identification schemes, were first formalized by Bellare et al. [4] and Kurosawa and Heng [5] independently. In recent years, there have been various advances in the area of identity-based identification, such as the introduction of identity-based identification schemes in the standard model [6,7], hierarchical model [810], and certificateless model [11].

Following Boneh et al.'s initial work, Ding and Tsudik expanded on security-mediated cryptography to cover identity-based encryption using the RSA assumption [12]. Shortly thereafter, Libert and Quisquater proposed the first pairing-based security-mediated identity-based encryption schemes [13]. On the signature front, Cheng et al. proposed the first security-mediated identity-based signature [14].

Chow et al. [15] and Yap et al. [16] both extended security-mediated cryptography into the certificateless setting, where the issue of key escrow was addressed. In certificateless cryptography, first proposed by Al-Riyami and Paterson [17], the key generation center only produces half of the user secret key. The user then produces the other half of the user secret key to be combined into the full user secret key, thus securing their key from even the key generation center. However, the cryptographic primitives in the certificateless setting introduce more operational cost to the scheme and are known to be difficult to be proven secure 18].

1.3. Motivations and Contribution. In 2013, Chin et al. first combined the notion of security-mediated cryptography with identifications in the identity-based setting to propose the first security-mediated identity-based identification (SMIBI) scheme [19]. In the paper, the authors provided the first formal definitions for SM-IBIs and also proposed a concrete construction. The motivation of the authors was to allow fast revocation of keys for identification schemes in the identity-based setting.

For SM-IBI schemes, a security mediator is required to participate in the identification protocol in order for a user to authenticate himself to a verifier. The security mediator can then hold a revocation list to identify which users' secret keys have been revoked and refuse participation for those users.

However the first concrete scheme that was proposed by the authors was built based on bilinear pairings. The pairing operation is widely known by cryptographers to be a costly operation; thus, it would be beneficial to construct pairing-free alternatives to facilitate more efficient running of the cryptographic primitive.

In this paper, we propose two pairing-free SM-IBI constructs as faster alternatives to the pairing-based scheme proposed by Chin et al. Our two schemes are constructed based on the RSA assumption and the discrete logarithm assumption, respectively. The RSA-based scheme, which we name as the GQ-SM-IBI, is constructed based on the Guillou Quisquater identification scheme constructed by Bellare and Palacio [20]. On the other hand, the discrete logarithm-based scheme, which we name as the BNN-SM-IBI, is constructed based on the BNN identity-based identification scheme proposed by Bellare et al. [4]. We provide security analysis for both schemes, proving them secure against impersonation under passive attacks if the RSA assumption and the discrete logarithm assumption hold and secure against impersonation under active and concurrent attacks if the one-more RSA inversion assumption and the one-more discrete logarithm assumption hold. Lastly, we provide an efficiency analysis, both theoretically and practically, and show that both schemes are significantly faster than Chin et al.'s pairing-based SM-IBI scheme.

The rest of the paper is organized as follows. We begin with some preliminaries and review the formal definitions and security model of SM-IBI schemes in Section 2. Then we show the construction and security analysis for the GQ-SM-IBI scheme in Section 3. This is followed by the construction and security analysis for the BNN-SM-IBI scheme in Section 4. In Section 5 we show the operational costs of both schemes as well as presenting our implementation results. Finally we conclude in Section 6.

2. Preliminaries

2.1. Discrete Logarithm Assumption. Let G be a cyclic group with prime order q and let g be a generator of G. The DL problem (DL) is defined as given a number A = [g.sup.a] in group G, output a.

Definition 1. The discrete logarithm assumption states that there exists no polynomial-time algorithm M that is able to ([t.sub.DL], [[epsilon].sub.DL])-solve the discrete logarithm problem with nonnegligible probability such that

Pr [M (G, q, g, A) = a] [greater than or equal to] [[epsilon].sub.DL]. (1)

2.2. The One-More Discrete Logarithm Assumption. The one-more discrete logarithm (OMDL) problem was first introduced by Bellare and Palacio [20] in their proof against impersonation under active and concurrent attacks for the standard Schnorr identification scheme. Later work that involves proving security of identification schemes based on discrete logarithms to be secure against active and concurrent attacks for discrete logarithm also makes use of this assumption such as [4, 21].

Let G be a finite cyclic group of order q and let g be a generator of G. Define an experiment EDL where an adversary M is given a challenge oracle CHALL that produces a random group element [W.sub.i] [member of] G when queried and a discrete log oracle DLOG, which provides the discrete log [w.sub.i] [member of] [Z.sub.q] corresponding to the query [W.sub.i] where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M wins if after making i queries to [CHALL.sub.DL], M is able to output solutions to all i challenges with only i - 1 queries to DLOG, meaning M has to solve at least one instance of the discrete logarithm problem without relying on the discrete log oracle. Edl returns 1 if M is successful and 0 otherwise.

Definition 2. The OMDL assumption states that there exists no polynomial-time algorithm M that is able to ([t.sub.OMDL], [Q.sub.OMDL], [[epsilon].sub.OMDL]) -solve the OMDL problem with nonnegligible probability where

Pr [[E.sub.DL] (M ([1.sup.k], G, g, [CHALL.sub.DL], DLOG) = l] [greater than or equal to] [[epsilon].sub.OMDL]. (2)

2.3. RSA Inversion (RSAI) Assumption. Given [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] compute Y such that Y = [X.sup.d] mod N where ed = 1 mod [phi](N).

Definition 3. The RSAI assumption states that there exists no polynomial-time algorithm M that is able to ([t.sub.RSAI], [[epsilon].sub.RSAI]) -solve the RSAI problem with nonnegligible probability such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3)

2.4. One-More RSA Inversion (OMRSAI) Assumption. This is the interactive variant of the RSAI problem first proposed by Bellare and Palacio [20] to prove security of the GQ identification scheme and is analogous to the OMDL assumption. This assumption is applied in the proof of security against active and concurrent attacks for RSA-based schemes.

Define an experiment [E.sub.RSAI] where an adversary M is given [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as input and access to two oracles CHALL and RSA. CHALL on any input returns a random point [W.sub.i], while RSA on any input h will return [h.sup.d] where ed = 1 mod N. M is required to compute the RSAI solutions to all the target points [W.sub.0], ..., [W.sub.n] while using strictly less queries to the RSA oracle. In other words, M is required to find [W.sup.d.sub.0], ..., [W.sup.d.sub.n] while using the RSA oracle only i < n times. [E.sub.RSAI] returns 1 if M is successful and 0 otherwise.

Definition 4. The OMRSAI assumption states that there exists no polynomial-time algorithm M that is able to ([t.sub.OMRSAI], [q.sub.OMRSAI], [[epsilon].sub.OMRSAI])-win the OMRSAI problem with nonnegligible probability where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (4)

2.5. Definition of Security-Mediated IBI Schemes. In this section, we review the definition of SM-IBI schemes as defined by [19]. The definition follows closely to that of conventional IBI schemes, with the difference being that the prover segment is extended to encompass obtaining tokens from the security mediator. The SM-IBI scheme is defined as five probabilistic polynomial-time algorithms.

(i) Setup. It takes in the security parameter [1.sup.k] as input and outputs the system parameters params along with the master secret key MSK.

(ii) Extract. Upon receiving a user's request for a key, it takes in params MSK and a user's identity ID. Once the secret key is created, the PKG separates the key into two portions, one for the user, [USK.sub.user], and one for the security mediator, [USK.sub.sem], and returns the portions to the respective parties.

(iii) Identification Protocol. The identification protocol is an interactive protocol run by the 3 algorithms: User-Prover and SEM-prover on the prover side trying to authenticate himself to the Verifier. Both provers are used cooperatively in the interactive three-step canonical honest verifier zero knowledge proof of knowledge protocol with the verifier as follows.

(1) User-Prover initiates by sending his identity to ID to the SEM-prover. SEM-prover checks whether ID's keys have been revoked and stops with an error code if true. If ID is legitimate then it generates and sends SEM-COMMIT to User-Prover who then combines SEM-COMMIT with his own USER-COMMIT to form FULL-COMMIT to send to Verifier.

(2) Verifier selects a random CHALLENGE and sends it to the User-Prover.

(3) User-Prover relays CHALLENGE to SEM-Prover and receives SEM-RESPONSE from SEM-Prover which it then combines with his own USER-RESPONSE to form FULL-RESPONSE and sends to the Verifier. The Verifier will choose to either accept or reject it.

2.6. Security Model for Security-Mediated IBI. Adversaries of SM-IBI follow the description of standard identification schemes: passive and active/concurrent attackers. However, the adversary for SM-IBI is able to query additionally partial conversation components, specifically the user's prover and the security mediator's prover besides the usual full prover query.

The security of SM-IBI schemes is modelled as a game played by an adversary I against a challenger C as follows.

(i) Setup. C runs Setup, creates the system parameters params and passes them to I while keeping the master secret key MSK to itself.

(ii) Phase 1. This is the training phase. I is allowed to adaptively make the following queries to C.

(a) User-Extract (ID). C will run Extract but returns only the user's portion of the secret key to I.

(b) SEM-Extract (ID). C will run Extract but returns only the security mediator's portion of the secret key to I.

(c) Full-Extract (ID). C will run Extract and returns both the user's portion of the secret key and the security mediator's portion of the secret key to I.

(d) Identification Queries (ID). For passive adversaries, C will generate transcripts of valid conversations for I. For active/concurrent adversaries, C will act as the cheating prover, engaging I as the cheating verifier in conversations. I is able to issue any one of the following identification queries.

(1) SEM-Identification (ID). C runs the security mediator's half of the prover session.

(2) User-Identification (ID). C runs the user's half of the prover session.

(3) Full-Identification (ID). C combines both security mediator's and user's session to generate a full and valid conversation.

(iii) Phase2.1 will eventually output [ID.sup.*] on which it wants to be challenged on and begins its role as the cheating prover for both security mediator and user prover sessions. C on the other hand assumes the role of the verifier. I wins the game if it manages to convince C to accept with nonnegligible probability.

We say a security-mediated IBI scheme n is ([t.sub.SMIBI], [q.sub.ISMIBI], [[epsilon].sub.SMIBI])-secure under passive or active /concurrent attacks if for any passive or active/concurrent Type-1 impersonator I who runs in time [t.sub.SMIBI], Pr[7 can impersonate] < [[epsilon].sub.SMIBI], where I can make at most [q.sub.SMIBI] full extract queries.

It is interesting to point out that extracting the security mediator's half of the secret key gives no information about the full user key and that neither security mediator's prover sessions nor user's prover sessions done alone will provide a valid conversation, but only the combined session will. This models the security requirement that any user cannot legitimately prove himself to a verifier without the security mediator's help.

3. GQ-SMIBI: RSA-Based

Security-Mediated IBI Scheme

The GQ-SM-IBI scheme is derived from the GQ identification scheme proposed in [20] and is provably secure against passive attackers assuming the RSAI assumption and against active/concurrent attackers assuming the OMRSAI assumption.

The GQ-SM-IBI scheme is constructed as follows.

(1) Setup ([1.sup.k]). It takes in the security parameter [1.sup.k], runs the key generation algorithm for RSA, and obtains an RSA instance, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It chooses a hash function H : [{0,1}.sup.*] [right arrow] [Z.sup.*.sub.N] and publishes the system parameters mpk = (N,e,H). The master secret key msk = d is kept secret.

(2) Extract (mpk, msk, ID). It takes in mpk, msk = s, and ID as input. It calculates H(ID) and sets [X.sub.FULL] = [H(ID).sup.d]. It further chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], sets [d.sub.USER] = d - [d.sub.SEM], and calculates [X.sub.USER] = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It gives [X.sub.USER] to the user as its partial secret key and [X.sub.SEM] to the security mediator as its partial private key and keeps [X.sub.FULL] secret.

(3) Identification Protocol. It is run by the User-Prover and SEM-Prover with Verifier as such.

(a) User-Prover sends its ID to Sem-Prover and chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets [Y.sup.e.sub.USER] = Fuser. SEM-Prover upon receiving ID checks if it is still valid and returns error if it is revoked. Otherwise, SEM-Prover chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sends [Y.sub.SEM] = [y.sup.e.sub.SEM] to User-Prover. User-Prover combines [Y.sub.FULL] = [Y.sub.SEM] x [Y.sub.USER] and sends [Y.sub.FULL] to Verifier.

(b) Verifier chooses a random challenge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where l(*) is a super-logarithmic challenge length such that [2.sup.l(k)] < e. Verifier then sends it to User-Prover. User-Prover relays c to SEM-Prover.

(c) SEM-Prover calculates its half of the response [z.sub.SEM] = [Y.sub.SEM][X.sup.c.sub.SEM] and sends it to User-Prover. User-Prover combines it with his response [z.sub.USER] = [y.sub.USER][X.sup.c.sub.USER] to create [z.sub.FULL] = [z.sub.SEM] x [z.sub.USER] and sends it as a response to Verifier.

Verifier checks if [z.sup.e.sub.FULL] = [Y.sup.FULL] [H(ID).sup.c] and accepts if yes; otherwise it outputs reject.

To check for completeness,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (5)

3.1. Security Analysis: Impersonation under Passive Attack

Theorem 5. The GQ-SM-IBI scheme is ([t.sub.SMIBI], [q.sub.SMIBI], [[epsilon].sub.SMIBI])-secure against impersonation under passive attacks in the random oracle if the RSA Inversion Problem is ([t.sub.RSAI], [[epsilon].sub.RSAI])-hard where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (6)

Proof. Assume the GQ-SM-IBI scheme is ([t.sub.SMIBI], [q.sub.SMIBI], [[epsilon].sub.SMIBI])-breakable; then a simulator M that ([t.sub.RSAI], [[epsilon].sub.RSAI])-breaks the RSAI problem can be shown. M takes in input (N, e, y) and runs the impersonator I as a subroutine.

Without loss of generality, it can be assumed that any SEM-Extract, User-Extract, SEM-Identification, User-Identification, and Full-Identification queries are preceded by a Create-User query. To avoid collision and consistently respond to these queries, M maintains a list [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] which is initially empty. The following shows how M simulates the environment and oracle queries for I.

(1) Setup. M selects a hash function H : [{0,1}.sup.*] [left arrow] [Z.sup.*.sub.N] and sets the system parameters as mpk = <N, e, H>. It sends mpk to I.

(2) Create-User ([ID.sub.i]). M chooses l [epsilon] {1, ..., [q.sub.H]} randomly and lets [ID.sub.i] = [ID.sub.*] at this point. Whenever I makes a H query on [ID.sub.i], consider the following.

(a) If i = l, M will choose [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and will return [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to I. It adds [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to [L.sub.H].

(b) Otherwise, for i [not equal to] l, M chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and returns [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M also sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as the SEM portion of the user private key and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as the user portion of the user private key. It can be seen that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (7)

M adds [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] M returns [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(3) SEM-Extract ([ID.sub.i]). If [ID.sub.i] = [ID.sub.*] and USER-Extract ([ID.sub.*]) has been queried before, M aborts. If [ID.sub.i] = [ID.sub.*], but USER-Extract ([ID.sub.*]) has not been queried before, M chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as the SEM portion of the user private key, saves it in [L.sub.H], and returns it to I. Otherwise for all other [ID.sub.i] = [ID.sub.*], M just retrieves [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [L.sub.H] and returns it to I.

(4) USER-Extract ([ID.sub.i]). If [ID.sub.i] = [ID.sub.*] and USER-Extract ([ID.sub.*]) has been queried before, M aborts. If [ID.sub.i] = [ID.sub.*], but SEM-Extract ([ID.sub.*]) has not been queried before, M chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as the USER portion of the user private key, saves it in [L.sub.H], and returns it to I. Otherwise for all other [ID.sub.i] = [ID.sub.*], M just retrieves [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [L.sub.H] and returns it to I.

(5) Identification ([ID.sub.i], session). I will act as the cheating verifier to learn information from valid conversation transcripts from M. If [ID.sub.i] = [ID.sub.*] M just retrieves [ID.sub.i]'s entry in [L.sub.H] and runs the identification protocol for either the SEM's interactions, the user's interactions, or both combined as in the protocol.

Otherwise, for [ID.sub.i] = [ID.sub.*], M then creates a full valid transcript for each mth query by picking [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M also sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M tags the session with session = m. If I queries

(i) SEM-Identification ([ID.sub.*], m), M will return [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII];

(ii) User-Identification ([ID.sub.*], m), M will return [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII];

(iii) Full-Identification ([ID.sub.*], m), M will return [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If no session is specified for the query, M just returns the next session in sequence. One can see that SEM-Identification ([ID.sub.*], m) and User-Identification ([ID.sub.*], m) can be combined to create a full and valid transcript on session m:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (8)

Eventually, I stops Phase 1 and outputs the challenge ID, [ID.sub.*] on which it wishes to be challenged on. M checks if [ID.sub.*] = [ID.sub.i] from [L.sub.H] and aborts if not. Otherwise, M runs I now as a cheating prover on [ID.sub.*] by obtaining its commitment, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], selecting a challenge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and obtaining the response [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from I. M then resets I to the step whereby I just sent [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], selects a second challenge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and receives [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as response. It should hold that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. One can then obtain [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since e is a prime and -e < [c.sub.1] - [c.sub.2] < e, GCD(e, [c.sub.1] - [c.sub.2]) = 1. Use the extended Euclidean algorithm to obtain integers S and T such that eS + ([c.sub.1] - [c.sub.2])T = 1. It follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (9)

M then calculates the solution to the RSAI problem as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (10)

It remains to calculate the probability of M solving the RSAI problem and winning the game. The probability of M successfully extracting two valid conversation transcripts from I is bounded by [([[epsilon].sub.IBI] - ([1/2.sup.l(k)])).sup.2] as given by the reset lemma [20]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (11)

Finally calculate Pr[[logical not]abort]. Let S be the probability that I issues both a SEM-Extract and a USER-Extract query on [ID.sub.*] and that I makes a total of [q.sub.SMIBI] of such queries. The probability of M answering all the extraction queries is [[delta].sup.q.sub.SMIBI] In Phase 2, the probability of M not aborting is if I outputs the challenge identity [ID.sub.*] that was not queried before. This is given by the probability 1 - [delta]. Compiling them, the probability of M not aborting is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This probability is maximised at [[delta].sub.opt] = 1 - (1/([q.sub.SMIB] + 1)). Using [[delta].sub.opt], the probability that M does not abort is at least 1/([2.sup.l(k)]([q.sub.SMIBI] + 1)) because the value [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] approaches 1/e for large [q.sub.SMIBI]. Therefore, the advantage of M, [[epsilon].sub.RSAI], and the bound of the simulation are given as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (12)

3.2. Security Analysis: Impersonation under Active/Concurrent Attack

Theorem 6. The GQ-SM-IBI scheme is ([t.sub.SMIBI], [q.sub.SMIBI], [[epsilon].sub.SMIBI])-secure against impersonation under active /concurrent attacks in the random oracle if the OMCDH Problem is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (13)

Proof. Assume the GQ-SM-IBI scheme is ([t.sub.SMIBI], [q.sub.SMIBI], [[epsilon].sub.SMIBI]/breakable; then a simulator M that ([t.sub.OMRSAI], [q.sub.OMRSAI], [[epsilon].sub.OMRSAI])-breaks the OMRSAI problem can be shown. M takes in input (N, e), is given access to CHALL and RSA oracles, and runs the impersonator I as a subroutine. Any SEM-Extract, User-Extract, SEM-Identification, User-Identification, and Full-Identification queries are preceded by a Create-User query. M maintains a list [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] which is initially empty. The following shows how M simulates the environment and oracle queries for I.

(1) Create-User ([ID.sub.i]). M chooses l [member of] [1, ..., [q.sub.H]] randomly and lets [ID.sub.l] = [ID.sub.*] at this point. Whenever I makes a H query on [ID.sub.i], consider the following.

(i) If i = l, M will choose /[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], queries CHALL for [w.sub.0], and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and will return [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It adds [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(ii) Otherwise, for i [not equal to] l, M chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and returns QID to I. M also sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as the SEM portion of the user private key and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as the user portion of the user private key. It can be seen that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (14)

M adds [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M returns [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(2) SEM-Extract ([ID.sub.i]). If [ID.sub.i] = [ID.sub.*] and USER-Extract ([ID.sub.*]) has been queried before, M aborts. If [ID.sub.i] = [ID.sub.*], but USER-Extract ([ID.sub.*]) has not been queried before, M chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as the SEM portion of the user private key, saves it in [L.sub.H], and returns it to I. Otherwise for all other [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], M just retrieves [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [L.sub.H] and returns it to I.

(3) USER-Extract ([ID.sub.i]). If [ID.sub.i] = [ID.sub.*] and SEM-Extract ([ID.sub.*]) has been queried before, M aborts. If [ID.sub.i] = [ID.sub.*], but SEM-Extract ([ID.sub.*]) has not been queried before, M chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as the USER portion of the user private key, saves it in [L.sub.H], and returns it to I. Otherwise for all other [ID.sub.i] [not equal to] [ID.sub.*], M just retrieves [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [L.sub.H] and returns it to I.

(4) Identification ([ID.sub.i], session). I will act as the cheating verifier to learn information from valid conversation interactions from M. If [ID.sub.i] _[ID.sub.*] M just retrieves [ID.sub.i]'s entry in [L.sub.H] and runs the identification protocol for either the SEM's interactions, the user's interactions, or both combined as in the protocol.

Otherwise, for [ID.sub.*] = [ID.sub.*], M then creates a full valid conversation for each mth query by querying CHALL for Wm and setting [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Additionally, M chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Upon receiving [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from I, M will query [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to receive [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M then chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and then sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M tags the session with session = m.

(i) If I queries SEM-Identification ([ID.sub.*], m), M will commit [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and respond with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], upon receiving [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(ii) If I queries User-Identification ([ID.sub.*], m), M will commit [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and respond with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] upon receiving [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(iii) If I queries Full-Identification ([ID.sub.*], m), M will commit [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and respond with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] upon receiving [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If no session is specified for the query, M just returns the next session in sequence. One can see that SEM-Identification ([ID.sub.*], m) and User-Identification ([ID.sub.*], m) can be combined to create a full and valid conversation on session m:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (15)

Eventually, I stops Phase 1 and outputs the challenge ID, [ID.sub.*] on which it wishes to be challenged on. M checks if [ID.sub.*] = [ID.sub.i] from [L.sub.H] and aborts if not. Otherwise, M runs I now as a cheating prover on [ID.sub.*]. M runs by obtaining its commitment, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], selects a challenge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and obtains the response [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from I. M then resets I to the step whereby I just sent [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], selects a second challenge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and receives [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as response. It should hold that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. One can then obtain [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Since e is a prime and -e < [c.sub.1] - [c.sub.2] < e, GCD(e, [c.sub.1] - [c.sub.2]) = 1. Use the extended Euclidean algorithm to obtain integers S and T such that eS + ([c.sub.1] - [c.sub.2])T = 1. It follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (16)

M then calculates the solution to the RSAI problem as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (17)

M proceeds to calculate the solutions to the other challenges as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (18)

The probability study for the simulation above is similar to that of the impersonation under passive attack game and is therefore omitted.

4. BNN-SM-IBI: An DL-Based Security-Mediated IBI Scheme

The BNN-SM-IBI scheme is derived from the BNN-IBI scheme proposed in the work of [4] and is provably secure against passive attackers assuming the DL assumption and against active/concurrent attackers assuming the OMDL assumption.

The BNN-SM-IBI scheme is constructed as follows.

(1) Setup ([1.sup.k]). It takes in the security parameter [1.sup.k]. It randomly selects [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], a generator [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and computes X = [g.sup.x]. Setup also chooses H : [{0,1}.sup.*] [right arrow] [Z.sub.q] and publishes the system parameters mpk = <G, q, g, X, H>. The master private key msk = x is kept secret.

(2) Extract (mpk, msk, ID). It takes in mpk, msk = s, and ID as input. It calculates H(ID), picks [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], calculates [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and sets the full user private key as [usk.sub.FULL] = <[s.sub.FULL], [R.sub.FULL]>. Additionally, it sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It then sets [usk.sub.USER] = <[s.sub.USER], [R.sub.USER]> and [usk.sub.SEM] = <[s.sub.SEM], [R.sub.SEM]>. It gives [usk.sub.USER] to the user as its partial private key and [usk.sub.SEM] to the security mediator as its partial private key and keeps [usk.sub.FULL] secret.

(3) Identification Protocol. It is run by the User-Prover and SEM-Prover with Verifier as such.

(a) User-Prover sends its ID to Sem-Prover, chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. SEM-Prover upon receiving ID checks if it is still valid and returns error if it is revoked. Otherwise, SEM-Prover chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sends [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to User-Prover. User-Prover combines [Y.sub.FULL] = [Y.sub.SEM] x [Y.sub.USER], [S.sub.FULL] = [S.sub.SEM] x [S.sub.USER], [R.sub.FULL] = [R.sub.SEM] x [R.sub.USER] and sends [Y.sub.FULL], [S.sub.FULL], and [R.sub.FULL] to Verifier.

(b) Verifier chooses a random challenge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sends it to User-Prover. User-Prover relays c to SEM-Prover.

(c) SEM-Prover calculates its half of the response [Z.sub.SEM] = [y.sub.SEM] + [cs.sub.SEM] and sends it to User-Prover. User-Prover combines it with his response [z.sub.USER] = [y.sub.USER] + [cs.sub.USER] to create [z.sub.FULL] = [z.sub.SEM] + [z.sub.USER] and sends it as a response to Verifier.

Verifier checks if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and accepts if yes; otherwise it outputs reject.

To check for completeness,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (19)

4.1. Security Analysis: Impersonation under Passive Attack

Theorem 7. The BNN-SM-IBI scheme is ([t.sub.SMIBI], [q.sub.SMIBI], [[epsilon].sub.SMIBI])-secure against impersonation under passive attacks in the random oracle if the DLproblem is ([t.sub.DL], [[epsilon].sub.DL])-hard where

[[epsilon].sub.SMIBI] [less than or equal to] [square root of ([[epsilon].sub.DL]e ([q.sub.SMIBI] + 1)] + 1/q. (20)

Proof. Assume the BNN-SM-IBI scheme is ([t.sub.SMIBI], [q.sub.SMIBi], [[epsilon].sub.SMIBI])-breakable; then a simulator M that ([t.sub.DL], [[epsilon].sub.DL])-breaks the DL problem can be shown. M takes in input (q, A = [g.sup.a]) and runs the impersonator I as a subroutine. Without loss of generality, it can be assumed that any SEM-Extract, User-Extract, SEM-Identification, User-Identification, and Full-Identification queries are preceded by a Create-User query. To avoid collision and consistently respond to these queries, M maintains a list [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] which is initially empty. The following shows how M simulates the environment and oracle queries for I.

(1) Setup. M sets the system parameters as mpk = (G, q, g, X = [g.sup.x], H> and keeps master private key x secret. It sends mpk to I.

(2) Create-User ([ID.sub.i]). M chooses l [member of] randomly and lets [ID.sub.i] = [ID.sub.*] at this point. Whenever 1 makes a H query on [ID.sub.i], consider the following.

(i) If i = l, M chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and returns [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to I. M adds [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to [L.sub.H].

(ii) Otherwise, for i [not equal to] l, M chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and returns [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It then chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], calculates [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M adds [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to [R.sub.H].

(3) SEM-Extract ([ID.sub.i]). If [ID.sub.i] = [ID.sub.*] and USER-Extract ([ID.sub.*]) has been queried before, M aborts. If [ID.sub.i] = [ID.sub.*], but USER-Extract ([ID.sub.*]) has not been queried before, M wih choose [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M also sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], saves these values in [L.sub.H], and returns them to I. These values will be used in the event of an Identification query later on. Otherwise for all other [ID.sub.i] = [ID.sub.*], M just retrieves [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [L.sub.H] and returns it to I.

(4) USER-Extract ([ID.sub.i]). If [ID.sub.i] = [ID.sub.*] and SEM-Extract ([ID.sub.*]) has been queried before, M aborts. II [ID.sub.i] = [ID.sub.*], but SEM-Extract ([ID.sub.*]) has not been queried before, M will choose [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [Z.sub.q] and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M also sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], saves these values in [L.sub.H], and returns them to I. These values will be used in the event of an Identification query later on. Otherwise for all other [ID.sub.i] [not equal to] [ID.sub.*], M just retrieves [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and returns it to I.

(5) Identification ([ID.sub.i], session). I will act as the cheating verifier to learn information from valid conversation transcripts from M. If [ID.sub.i] [not equal to] [ID.sub.*], M just retrieves [ID.sub.i]'s entry in [L.sub.H] and runs the identification protocol for either the SEM's interactions, the user's interactions, or both combined as in the protocol.

Otherwise, for [ID.sub.i] = [ID.sub.*], M then creates a full valid transcript for each mth query by picking [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M retrieves [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Additionally, M chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] calculates [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and retrieves [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from [L.sub.H] as well. M then sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M tags the session with session = m.Ifl queries

(i) SEM-Identification ([ID.sub.*], m), M will return [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII];

(ii) User-Identification ([ID.sub.*], m), M will return [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII];

(iii) Full-Identification ([ID.sub.*], m), M will return [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If no session is specified for the query, M just returns the next session in sequence. One can see that SEM-Identification ([ID.sub.*], m) and User-Identification ([ID.sub.*], m) can be combined to create a full and valid transcript on session m:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (21)

Eventually, I stops Phase 1 and outputs the challenge ID, [ID.sub.*] on which it wishes to be challenged on. M checks if ID = [ID.sub.i] from Lh and aborts if not. Otherwise, M runs I now as a cheating prover on [ID.sub.*] by obtaining its commitment, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] selecting a challenge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and obtaining the response [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from I. M then resets Ito the step whereby I just sent [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], selects a second challenge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and receives [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as response. M is then able to extract the full user private key as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (22)

M outputs a as the discrete log solution.

It remains to calculate the probability of M solving the CDH problem and winning the game. The probability of M successfully extracting two valid conversation transcripts from I is bounded by ([[epsilon].sub.SMIBI] - [(1/tq)).sub.2] as given by the reset lemma [20]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (23)

Finally, let [delta] be the probability that I issues a SEM-Extract and a USER-Extract query on [ID.sub.*] and that I makes a total of [q.sub.SMIBI] of such queries. The probability of M answering all the extraction queries is 8q. In Phase 2, the probability of M not aborting is if I outputs the challenge identity [ID.sub.*] that was not queried before. This is given by the probability 1 - [delta]. Compiling them, the probability of M not aborting is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. This value is maximised at [[delta].sub.opt] = 1-(1/([q.sub.SMIBI] + 1)). Using [[delta].sub.opt], The probability that M does not abort is at least 1/e([q.sub.SMIBI] + 1) because the value [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] approaches 1/e for large [q.sub.SMIBI]. Therefore, the advantage of M, [[epsilon].sub.DL], and the bound of the simulation is given as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (24)

4.2. Security Analysis: Impersonation under Active/Concurrent Attack

Theorem 8. The BNN-SM-IBI scheme is ([t.sub.SMIBI], qsMiBi, [[epsilon].sub.SMIBI])-secure against impersonation under active /concurrent ttacks in the random oracle if the OMCDH Problem is ([t.sub.OMCDH], [q.sub.OMCDH], [[epsilon].sub.OMCDH])-hard where

[[epsilon].sub.SMIBI] [less than or equal to] [square root of ([[epsilon].sub.OUCDH]e[[epsilon].sub.SMIBI] + 1))] + 1/q. (25)

Proof. Assume the BNN-SM-IBI scheme is ([t.sub.SMIBI], [q.sub.SMIBI], [[epsilon].sub.SMIBI])-breakable; then a simulator M that ([t.sub.OMCDH], [q.sub.OMCDH], [[epsilon].sub.OMCDH])-breaks the OMCDH Problem can be shown. M takes in input (q, ga), is given access to CHALL and DLOG oracles, and runs the impersonator I as a subroutine. Without loss of generality, it can be assumed that any SEM-Extract, User-Extract, SEM-Identification, User-Identification, and Full-Identification queries are preceded by a Create-User query. To avoid collision and consistently respond to these queries, M maintains a list [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] which is initially empty. The following shows how M simulates the environment and oracle queries for I.

(1) Setup. M sets the system parameters as mpk = <G, q, g, X = [g.sup.x], H> and keeps master private key x secret. It sends mpk to I.

(2) Create-User ([ID.sub.i]). M chooses l e [1, ..., [q.sub.H]] randomly and lets [ID.sub.i] = [ID.sub.*] at this point. Whenever I makes a H query on [ID.sub.i], consider the following.

(i) If i = l, M chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], queries CHALL for [W.sub.0], and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M returns [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to I. M adds [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to [L.sub.H].

(ii) Otherwise, for i [not equal to] l, M chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and returns [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It then chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], calculates [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to [L.sub.H].

(3) SEM-Extract ([ID.sub.i]). If [ID.sub.i] = [ID.sub.*] and USER-Extract ([ID.sub.*]) has been queried before, M aborts. If [ID.sub.i] = [ID.sub.*], but USER-Extract ([ID.sub.*]) has not been queried [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] choose [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] also sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] saves these values in [L.sub.H], and returns them to I. These values will be used in the event of an Identification query later on. Otherwise for all other [ID.sub.i] = [ID.sub.*], M just retrieves [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [L.sub.H] and returns it to I.

(4) USER-Extract ([ID.sub.i]). If [ID.sub.i] = [ID.sub.*] and SEM Extract ([ID.sub.*]) has been queried before, M aborts. If [ID.sub.i] = [ID.sub.*], but SEM-Extract ([ID.sub.*]) has not been queried before, M will choose [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M also sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], saves these values in [L.sub.H], and returns them to I. These values will be used in the event of an Identification query later on. Otherwise for all other [ID.sub.i] = [ID.sub.*], M just retrieves [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [L.sub.H] and returns it to I.

(5) Identification ([ID.sub.j], session). I will act as the cheating verifier to learn information from valid conversations from M. If [ID.sub.i] [not equal to] [ID.sub.*], M just retrieves [ID.sub.j]'s entry in [L.sub.H] and runs the identification protocol for either the SEM's interactions, the user's interactions, or both combined as in the protocol.

Otherwise, for [ID.sub.i] = [ID.sub.*], M then creates a full valid conversation for each mth query by querying CHALL for Wm and setting [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M also retrieves. Additionally, M chooses [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M also retrieves [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. from [L.sub.H]. Upon receiving [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from I, M will query [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], selects [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and sets [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. M tags the session with session = m.

(a) If I queries SEM-Identification ([ID.sub.j], m), M will commit [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and respond with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Upon receiving [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(b) If I queries User-Identification ([ID.sub.j], m), M will commit [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and respond with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] upon receiving [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(c) If I queries Full-Identification ([ID.sub.j], m), M will commit [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and respond with [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] upon receiving [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If no session is specified for the query, M just returns the next session in sequence. One can see that SEM-Identification ([ID.sub.j], m) and User-Identification ([ID.sub.*], m) can be combined to create a full and valid conversation on session m:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (26)

Eventually, I stops Phase 1 and outputs the challenge ID,

[ID.sub.*]

on which it wishes to be challenged on. M checks if [ID.sub.*] = [ID.sub.i] from [L.sub.H] and aborts if not. Otherwise, M runs I now as a cheating prover on [ID.sub.*]. M runs by obtaining its [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], selects a challenge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and obtains the response [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from I. M then resets I to the step whereby I just sent [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], selects a second challenge [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and receives [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as response. M is then able to extract the full user private key as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (27)

M outputs [w.sub.0] as the initial discrete log challenge solution.

M proceeds to calculate the solutions to the other challenges as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (28)

The probability study for the simulation above is similar to that of the impersonation under passive attack game and is therefore omitted.

5. Efficiency Analysis

In this section we provide the breakdown of operation costs for both the GQ-SM-IBI scheme and the BNN-SM-IBI scheme.

We measure the operation costs of the GQ-SM-IBI scheme in terms of addition operations in [Z.sub.[phi](N)], multi plication operations in [Z.sub.[phi](N)] and [Z.sup.[phi].sub.N], and exponentiation operations in [Z.sup.[phi].sub.N]. Overall, the operational costs of the GQ-SM-IBI scheme are given in Table 1.

We also provide the communication costs of the GQ-SM-IBI scheme in Table 2.

As for the BNN-SM-IBI scheme, we measure the operational costs in terms of group operational costs of addition modulo q, multiplication modulo q, multiplication in group G, and exponentiations modulo q. Overall, the operational costs of the BNN-SM-IBI scheme are given in Table 3.

We also provide the communication costs of the BNNSM-IBI scheme in Table 4.

However, it is difficult to compare all these operational costs since the schemes are using operations defined in different fields and groups. Therefore, we built a simulator to generate running time results using a common platform.

We compare the running time of only the identification protocol, since the protocol is invoked every time a prover wishes to perform an interaction with a verifier. We compare the running times of the GQ-SM-IBI scheme and BNN-SMIBI scheme as well as the original pairing-based scheme by [19]. We name the scheme from [19] as BLS-SM-IBI since its design follows the BLS signature scheme by Boneh et al. from [22]. For GQ-SM-IBI and BNN-SM-IBI the level of security used was 1024-bits, 2048-bits, and 3072-bits. We also compared the results with the equivalent level of security for BLS-SM-IBI pairing-based scheme of 512-bits, 1024-bits, and 1536-bits, respectively.

The simulation was run on a i7-2630QM platform with 4 GB RAM running 64-bit Windows 7 The library used was Java Cryptography Extension. We ran the simulation 100 iterations for each algorithm and took the average running time, measured in nanoseconds as presented in Table 5.

From the results, one can see that the GQ-SM-IBI scheme has the fastest identification protocol running time with the BNN-SM-IBI scheme trailing behind. However, both pairing-free schemes vastly outperform the BLS-SM-IBI that is pairing-based with at least an approximate factor of 6 to 7 for all three security levels. Therefore we obtain faster SM-IBI schemes from pairing-free alternatives.

6. Conclusion

We proposed two SM-IBI schemes that have an instant revocation feature and are very efficient. Our schemes outperform the only pairing-based SM-IBI currently known and are provably secure in the random oracle model against both passive and active/concurrent attackers.

http://dx.doi.org/10.1155/2014/170906

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgment

The authors would like to acknowledge the Ministry of Education, Malaysia, for financially aiding this research through the Fundamental Research Grant Scheme FRGS/2/2013/ ICT07/MMU/03/5.

References

[1] A. Shamir, "Identity-based cryptosystems and signature schemes," in Advances in Cryptology, G. R. Blakley and D. Chaum, Eds., vol. 196 of Lecture Notes in Computer Science, pp. 47-53, Springer, Berlin, Germany, 1984.

[2] D. Boneh, X. Ding, G. Tsudik, and C. M. Wong, "A method for fast revocation of public key certificates and security capabilities," in Proceedings of the 10th Conference on USENIX Security Symposium (SSYM '01), D. S. Wallach, Ed., vol. 10, p. 22, Berkeley, Calif, USA, 2001.

[3] A. Fiat and A. Shamir, "How to prove yourself: practical solutions to identification and signature problems," in Advances in Cryptology-CRYPTO '86, A. M. Odlyzko, Ed., vol. 263 of Lecture Notes in Computer Science, pp. 186-194, Springer, Berlin, Germany, 1986.

[4] M. Bellare, C. Namprempre, and G. Neven, "Security proofs for identity-based identification and signature schemes," in Advances in Cryptology-EUROCRYPT 2004, C. Cachin and J. Camenisch, Eds., vol. 3027 of Lecture Notes in Computer Science, pp. 268-286, Springer, Berlin, Germany, 2004.

[5] K. Kurosawa and S. H. Heng, "From digital signature to ID-based identification/signature," in Public Key CryptographyPKC 2004, F. Bao, R. H. Deng, and J. Zhou, Eds., vol. 2947 of Lecture Notes in Computer Science, pp. 248-261, Springer, Berlin, Germany, 2004.

[6] J. J. Chin, S. H. Heng, and B. M. Goi, "An efficient and provable secure identity-based identification scheme in the standard model," in Public Key Infrastructure, S. F. Mjolsne, S. Mauw, and S. K. Katsikas, Eds., vol. 5057 of Lecture Notes in Computer Science, pp. 60-73, Springer, Berlin, Germany, 2008.

[7] J. J. Chin and S. H. Heng, "An adaptive-secure k-resilient identity-based identification scheme in the standard model," in Proceedings of the FTRA-ACSA Summer, Vancouver, Canada, June 2012.

[8] J. J. Chin, S. H. Heng, and B. M. Goi, "Hierarchical identity-based identification schemes," in Security Technology, D. Slezak, T. H. Kim, W. C. Fang, and K. P. Arnett, Eds., vol. 58 of Communications in Computer and Information Science, pp. 9399, Springer, Berlin, Germany, 2009.

[9] A. Fujioka, T. Saito, and K. Xagawa, "Secure hierarchical identity-based identification without random oracles," in Information Security, D. Gollmann and F. C. Freiling, Eds., vol. 7483 of Lecture Notes in Computer Science, pp. 258-273, Springer, Berlin, Germany, 2012.

[10] A. Fujioka, T. Saito, and K. Xagawa, "Applicability of OR-proof techniques to hierarchical identity-based identification," in Cryptology and Network Security, J. Pieprzyk, A. R. Sadeghi, and M. Manulis, Eds., vol. 7712 of Lecture Notes in Computer Science, pp. 169-184, Springer, Berlin, Germany, 2012.

[11] J. J. Chin, R. C. W. Phan, R. Behnia, and S. H. Heng, "An efficient and provably secure certificateless identification scheme," in SECRYPT 2013, P. Samarati, Ed., pp. 371-378, SciTePress, 2013.

[12] X. Ding and G. Tsudik, "Simple identity-based cryptography with mediated RSA," in Topics in Cryptology-CT-RSA 2003, M. Joye, Ed., vol. 2612 of Lecture Notes in Computer Science, pp. 193-210, Springer, Berlin, Germany, 2003.

[13] B. Libert and J. J. Quisquater, "Efficient revocation and threshold pairing based cryptosystems," in Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing (PODC '03), E. Borowsky and S. Rajsbaum, Eds., pp. 163-171, ACM, Boston, Mass, USA, July 2003.

[14] X. Cheng, L. Guo, and X. Wang, "An identity-based mediated signature scheme from bilinear pairing," International Journal of Network Security, vol. 2, no. 1, pp. 29-33, 2006.

[15] S. S. M. Chow, C. Boyd, and J. M. G. Nieto, "Security-mediated certificateless cryptography," in Public Key Cryptography-PKC 2006, M. Yung, Y. Dodis, A. Kiayias, and T. Malkin, Eds., vol. 3958 of Lecture Notes in Computer Science, pp. 508-524, Springer, Berlin, Germany, 2006.

[16] W. S. Yap, S. S. M. Chow, S. H. Heng, and B. M. Goi, "Security mediated certificateless signatures," in Applied Cryptography and Network Security, J. Katz and M. Yung, Eds., vol. 4521 of Lecture Notes in Computer Science, pp. 459-477, Springer, Berlin, Germany, 2007.

[17] S. S. Al-Riyami and K. G. Paterson, "Certificateless public key cryptography," in Advances in Cryptology-ASIACRYPT2003, C.S. Laih, Ed., vol. 2894 of Lecture Notes in Computer Science, pp. 452-473, Springer, Berlin, Germany, 2003.

[18] J. J. Chin, R. Behnia, S. H. Heng, and R. C. W. Phan, "Cryptanalysis of a certificateless identification scheme," Security and Communication Networks, 2014.

[19] J. J. Chin, R. Behnia, S. H. Heng, and R. C. Phan, "An efficient and provable secure security-mediated identity-based identification scheme," in Proceedings of the 8th Asia Joint Conference on Information Security (Asia JCIS '13), pp. 27-32, IEEE, Seoul, South Korea, 2013.

[20] M. Bellare and A. Palacio, "GQ and Schnorr identification schemes: proofs of security against impersonation under active and concurrent attacks," in Advances in Cryptology-CRYPTO 2002, M. Yung, Ed., vol. 2442 of Lecture Notes in Computer Science, pp. 162-177, Springer, Berlin, Germany, 2002.

[21] S. Y. Tan, S. H. Heng, R. C. W. Phan, and B. M. Goi, "A variant of Schnorr identity-based identification scheme with tight reduction," in Future Generation Information Technology, T. H. Kim, H. Adeli, D. Slezak et al., Eds., vol. 7105 of Lecture Notes in Computer Science, pp. 361-370, Springer, Berlin, Germany, 2011.

[22] D. Boneh, B. Lynn, and H. Shacham, "Short signatures from the weil pairing," Journal of Cryptology, vol. 17, no. 4, pp. 297-319, 2004.

Ji-Jian Chin, (1) Syh-Yuan Tan, (2) Swee-Huay Heng, (2) and Raphael C.-W. Phan (1)

(1) Faculty of Engineering, Multimedia University, 63100 Cyberjaya, Selangor, Malaysia

(2) Faculty of Information Science and Technology, Multimedia University, Jalan Ayer Keroh Lama, 75450 Bukit Beruang, Melaka, Malaysia

Correspondence should be addressed to Ji-Jian Chin; jjchin@mmu.edu.my

Received 13 March 2014; Accepted 17 April 2014; Published 26 May 2014

Academic Editor: Mirjana Ivanovic

TABLE 1: Operation costs for the GQ-SM-IBI scheme. Algorithm A M1 M2 E Setup 0 0 0 0 Extract 1 0 0 3 SEM-Prove 0 0 1 2 User-Prove 0 0 3 2 Verify 0 0 1 2 A: addition in [Z.sub.[phi]N], M1: multiplication in [Z.sub.[phi]N], M2: multiplication in [Z.sup.*.sub.N], and E: exponentiation in [Z.sup.*.sub.N]. TABLE 2: Communication costs between algorithms for the GQ-SM-IBI scheme. Algorithms Bitstring Elements of [absolute value [absolute value of (ID)] of (e - l)] TA-User (Extract) 1 0 TA-SEM (Extract) 1 0 SEM-User 1 1 (Identification) User-Verifier 1 1 (Identification) Algorithms Elements in [Z.sup.*.sub.N] TA-User (Extract) 1 TA-SEM (Extract) 1 SEM-User 2 (Identification) User-Verifier 2 (Identification) TABLE 3: Operation costs for the BNN-SM-IBI scheme. Algorithm A M GM E Setup 0 0 0 1 Extract 3 1 0 3 SEM-Prover 1 1 0 2 User-Prover 2 1 3 2 Verifier 0 1 2 3 H: hash operation, A: addition mod q, M: multiplication mod q, GM: group multiplication, and E: exponentiation mod q. TABLE 4: Communication costs between algorithms for the BNN-SM-IBI scheme. Algorithms Bitstring Elements Elements in [G.sub.1] in [Z.sub.q] TA-User (Extract) 1 1 1 TA-SEM (Extract) 1 1 1 SEM-User 1 3 2 (Identification) User-Verifier 1 3 2 (Identification) TABLE 5: Comparison of average simulated runtimes for SM-IBI schemes. Identification (ns) GQ-SM-IBI (1024-bits) 2,158,747 BNN-SM-IBI (1024-bits) 14,064,652 BLS-SM-IBI (512-bits) 104,664,826 GQ-SM-IBI (2048-bits) 7,706,801 BNN-SM-IBI (2048-bits) 82,456,452 BLS-SM-IBI (1024-bits) 487,682,172 GQ-SM-IBI (3072-bits) 17,027,899 BNN-SM-IBI (3072-bits) 182,153,886 BLS-SM-IBI (1536-bits) 1,188,023,987

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Research Article |
---|---|

Author: | Chin, Ji-Jian; Tan, Syh-Yuan; Heng, Swee-Huay; Phan, Raphael C.-W. |

Publication: | The Scientific World Journal |

Article Type: | Report |

Date: | Jan 1, 2014 |

Words: | 9781 |

Previous Article: | Optical frequency upconversion technique for transmission of wireless MIMO-type signals over optical fiber. |

Next Article: | IgG, IgM, and IgA antinuclear antibodies in discoid and systemic lupus erythematosus patients. |

Topics: |