# Efficient and Provable Secure Pairing-Free Security-Mediated Identity-Based Identification Schemes

Authors: Ji-Jian Chin; Syh-Yuan Tan; Swee-Huay Heng; Raphael C.-W. Phan
Journal: The Scientific World Journal
 (2014)

---

## Abstract

Security-mediated cryptography was first introduced by Boneh et al. in 2001. The main motivation behind security-mediated cryptography was the capability to allow instant revocation of a user’s secret key by necessitating the cooperation of a security mediator in any given transaction. Subsequently in 2003, Boneh et al. showed how to convert a RSA-based security-mediated encryption scheme from a traditional public key setting to an identity-based one, where certificates would no longer be required. Following these two pioneering papers, other cryptographic primitives that utilize a security-mediated approach began to surface. However, the security-mediated identity-based identification scheme (SM-IBI) was not introduced until Chin et al. in 2013 with a scheme built on bilinear pairings. In this paper, we improve on the efficiency results for SM-IBI schemes by proposing two schemes that are pairing-free and are based on well-studied complexity assumptions: the RSA and discrete logarithm assumptions.


---

## Body

## 1. Introduction

### 1.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 may be 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 [8–10], 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 (SM-IBI) 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 Section2. 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.


## 1.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 may be 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 [8–10], 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 (SM-IBI) 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 Section2. 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

LetG 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=ga in group G, output a.Definition 1.
The discrete logarithm assumption states that there exists no polynomial-time algorithmM that is able to (tDL,εDL)-solve the discrete logarithm problem with nonnegligible probability such that
(1)Pr[M(G,q,g,A)=a]≥εDL.


### 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].LetG 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 Wi∈G when queried and a discrete log oracle DLOG, which provides the discrete log wi∈Zq corresponding to the query Wi where gwi=Wi. M wins if after making i queries to CHALLDL, 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.
TheOMDL assumption states that there exists no polynomial-time algorithm M that is able to (tOMDL,qOMDL,εOMDL)-solve the OMDL problem with nonnegligible probability where
(2)Pr⁡[EDL(M(1k,G,g,CHALLDL,DLOG)=1]≥εOMDL.


### 2.3. RSA Inversion (RSAI) Assumption

Given(N,e,X)←$kRSA(1k) compute Y such that Y=Xdmod⁡N where ed=1mod⁡ϕ(N).Definition 3.
TheRSAI assumption states that there exists no polynomial-time algorithm M that is able to (tRSAI,εRSAI)-solve the RSAI problem with nonnegligible probability such that
(3)Pr[M(1k,N,e,X)=Y:Y=Xdanded=1mod⁡ϕ(N)]000≥εRSAI.


### 2.4. One-More RSA Inversion (OMRSAI) Assumption

This is the interactive variant of theRSAI 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 experimentERSAI where an adversary M is given (N,e)←$kRSA(1k) as input and access to two oracles CHALL and RSA. CHALL on any input returns a random point Wi, while RSA on any input h will return hd where ed=1mod⁡N. M is required to compute the RSAI solutions to all the target points W0,…,Wn while using strictly less queries to the RSA oracle. In other words, M is required to find W0d,…,Wnd while using the RSA oracle only i<n times. ERSAI returns 1 if M is successful and 0 otherwise.Definition 4.
TheOMRSAI assumption states that there exists no polynomial-time algorithm M that is able to (tOMRSAI,qOMRSAI,εOMRSAI)-win the OMRSAI problem with nonnegligible probability where
(4)Pr[ERSAI(M(1k,N,e,CHALLRSA,RSA))=1]≥εRSAI.


### 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 1k as input and outputs the system parametersparams  along with the master secret keyMSK.(ii)
Extract. Upon receiving a user’s request for a key, it takes inparamsMSK and a user’s identityID. Once the secret key is created, the PKG separates the key into two portions, one for the user, USKuser, and one for the security mediator, USKsem, 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 andSEM-prover on the prover side trying to authenticate himself to theVerifier. 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 toID to theSEM-prover.SEM-prover checks whether ID’s keys have been revoked and stops with an error code if true. IfID is legitimate then it generates and sendsSEM-COMMIT toUser-Prover who then combinesSEM-COMMIT with his ownUSER-COMMIT to formFULL-COMMIT to send toVerifier.(2)
Verifier selects a randomCHALLENGE and sends it to theUser-Prover.(3)
User-Prover relaysCHALLENGE toSEM-Prover and receivesSEM-RESPONSE fromSEM-Prover which it then combines with his ownUSER-RESPONSE to formFULL-RESPONSE and sends to theVerifier. TheVerifier 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 adversaryI against a challenger C as follows.(i)
Setup.C runsSetup, creates the system parametersparams, and passes them to I while keeping the master secret keyMSK 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 runExtract but returns only the user’s portion of the secret key to I.(b)
SEM-Extract (ID). C will runExtract but returns only the security mediator’s portion of the secret key to I.(c)
Full-Extract(ID). C will runExtract 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)
Phase 2.I will eventually output ID* 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Π is (tSMIBI,qSMIBI,εSMIBI)-secure under passive or active/concurrent attacks if for any passive or active/concurrent Type-1 impersonator I who runs in time tSMIBI, Pr[Icanimpersonate]<εSMIBI, where I can make at most qSMIBI 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.


## 2.1. Discrete Logarithm Assumption

LetG 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=ga in group G, output a.Definition 1.
The discrete logarithm assumption states that there exists no polynomial-time algorithmM that is able to (tDL,εDL)-solve the discrete logarithm problem with nonnegligible probability such that
(1)Pr[M(G,q,g,A)=a]≥εDL.


## 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].LetG 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 Wi∈G when queried and a discrete log oracle DLOG, which provides the discrete log wi∈Zq corresponding to the query Wi where gwi=Wi. M wins if after making i queries to CHALLDL, 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.
TheOMDL assumption states that there exists no polynomial-time algorithm M that is able to (tOMDL,qOMDL,εOMDL)-solve the OMDL problem with nonnegligible probability where
(2)Pr⁡[EDL(M(1k,G,g,CHALLDL,DLOG)=1]≥εOMDL.


## 2.3. RSA Inversion (RSAI) Assumption

Given(N,e,X)←$kRSA(1k) compute Y such that Y=Xdmod⁡N where ed=1mod⁡ϕ(N).Definition 3.
TheRSAI assumption states that there exists no polynomial-time algorithm M that is able to (tRSAI,εRSAI)-solve the RSAI problem with nonnegligible probability such that
(3)Pr[M(1k,N,e,X)=Y:Y=Xdanded=1mod⁡ϕ(N)]000≥εRSAI.


## 2.4. One-More RSA Inversion (OMRSAI) Assumption

This is the interactive variant of theRSAI 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 experimentERSAI where an adversary M is given (N,e)←$kRSA(1k) as input and access to two oracles CHALL and RSA. CHALL on any input returns a random point Wi, while RSA on any input h will return hd where ed=1mod⁡N. M is required to compute the RSAI solutions to all the target points W0,…,Wn while using strictly less queries to the RSA oracle. In other words, M is required to find W0d,…,Wnd while using the RSA oracle only i<n times. ERSAI returns 1 if M is successful and 0 otherwise.Definition 4.
TheOMRSAI assumption states that there exists no polynomial-time algorithm M that is able to (tOMRSAI,qOMRSAI,εOMRSAI)-win the OMRSAI problem with nonnegligible probability where
(4)Pr[ERSAI(M(1k,N,e,CHALLRSA,RSA))=1]≥εRSAI.


## 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 1k as input and outputs the system parametersparams  along with the master secret keyMSK.(ii)
Extract. Upon receiving a user’s request for a key, it takes inparamsMSK and a user’s identityID. Once the secret key is created, the PKG separates the key into two portions, one for the user, USKuser, and one for the security mediator, USKsem, 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 andSEM-prover on the prover side trying to authenticate himself to theVerifier. 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 toID to theSEM-prover.SEM-prover checks whether ID’s keys have been revoked and stops with an error code if true. IfID is legitimate then it generates and sendsSEM-COMMIT toUser-Prover who then combinesSEM-COMMIT with his ownUSER-COMMIT to formFULL-COMMIT to send toVerifier.(2)
Verifier selects a randomCHALLENGE and sends it to theUser-Prover.(3)
User-Prover relaysCHALLENGE toSEM-Prover and receivesSEM-RESPONSE fromSEM-Prover which it then combines with his ownUSER-RESPONSE to formFULL-RESPONSE and sends to theVerifier. TheVerifier 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 adversaryI against a challenger C as follows.(i)
Setup.C runsSetup, creates the system parametersparams, and passes them to I while keeping the master secret keyMSK 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 runExtract but returns only the user’s portion of the secret key to I.(b)
SEM-Extract (ID). C will runExtract but returns only the security mediator’s portion of the secret key to I.(c)
Full-Extract(ID). C will runExtract 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)
Phase 2.I will eventually output ID* 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Π is (tSMIBI,qSMIBI,εSMIBI)-secure under passive or active/concurrent attacks if for any passive or active/concurrent Type-1 impersonator I who runs in time tSMIBI, Pr[Icanimpersonate]<εSMIBI, where I can make at most qSMIBI 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 (1k). It takes in the security parameter 1k, runs the key generation algorithm for RSA, and obtains an RSA instance, (N,e,d)←$kRSA(1k). It chooses a hash function H:{0,1}*→ZN* 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 XFULL=H(ID)d. It further chooses dSEM←$Zϕ(N)*, sets dUSER=d-dSEM, and calculates XUSER=H(ID)dUSER and XSEM=H(ID)dSEM. It gives XUSER to the user as its partial secret key and XSEM to the security mediator as its partial private key and keeps XFULL secret.(3)
Identification Protocol. It is run by theUser-Prover andSEM-Prover withVerifier as such.
(a)
User-Prover sends its ID toSem-Prover and chooses yUSER←$ZN* and sets YUSER=yUSERe.SEM-Prover upon receiving ID checks if it is still valid and returns error if it is revoked. Otherwise,SEM-Prover chooses ySEM←$ZN* and sends YSEM=ySEMe toUser-Prover.User-Prover combines YFULL=YSEM×YUSER and sends YFULL toVerifier.(b)
Verifier chooses a random challenge c←$Z2l(k) where l(·) is a super-logarithmic challenge length such that 2l(k)<e.Verifier then sends it toUser-Prover.User-Prover relays c toSEM-Prover.(c)
SEM-Prover calculates its half of the response zSEM=ySEMXSEMc and sends it toUser-Prover.User-Prover combines it with his response zUSER=yUSERXUSERc to create zFULL=zSEM×zUSER and sends it as a response toVerifier.Verifier checks ifzFULLe=YFULLH(ID)c and accepts if yes; otherwise it outputs reject.To check for completeness,(5)ZFULLe=[(ySEMXSEMc)(yUSERXUSERc)]e=[ySEMyUSER(XSEMXUSER)c]e=ySEMeyUSERe(H(ID)(dSEM+dUSER)ec)=YSEMYUSER(H(ID)dec)=YFULL(H(ID)c).


### 3.1. Security Analysis: Impersonation under Passive Attack

Theorem 5.
The GQ-SM-IBI scheme is(tSMIBI,qSMIBI,εSMIBI)-secure against impersonation under passive attacks in the random oracle if the RSA Inversion Problem is (tRSAI,εRSAI)-hard where
(6)εSMIBI≤εRSAIe(qSMIBI+1)+12l(k).Proof.
Assume the GQ-SM-IBI scheme is(tSMIBI,qSMIBI,εSMIBI)-breakable; then a simulator M that (tRSAI,ε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 anySEM-Extract, User-Extract, SEM-Identification, User-Identification, andFull-Identification queries are preceded by aCreate-User query. To avoid collision and consistently respond to these queries, M maintains a list LH=〈IDi,QIDi,fIDi,XFULLIDi,XSEMIDi,XUSERIDi,dSEMIDi,dUSERIDi〉 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}*→ZN* and sets the system parameters as mpk=〈N,e,H〉. It sends mpk to I.(2)
Create-User(IDi). M chooses l∈{1,…,qH} randomly and lets IDl=ID* at this point. Whenever I makes a H query on IDi, consider the following.
(a)
Ifi=l, M will choose fID*←$ZN* sets QID*=yfID*e and will return QID* to I. It adds 〈IDl,QID*,fID*,XFULLID*=⊥,XUSERID*=⊥,XSEMID*=⊥,dSEMID*=⊥,dUSERID*=bot〉 to LH.(b)
Otherwise, fori≠l, M chooses fIDi←$Zq*, sets QIDi=fIDie, and returns QIDi to I. M also sets XFULLIDi=fIDi, chooses dUSERID*←$Zϕ(N)*, and sets XSEMIDi=QIDidSEMIDi as the SEM portion of the user private key and XUSERIDi=fIDiQIDi-dUSERIDi as the user portion of the user private key. It can be seen that
(7)XSEMIDi×XUSERIDi=QIDidSEMIDi×fIDiQIDi-dSEMIDi=fIDi=XFULLIDi.M adds 〈IDi, QIDi, fIDi, XFULLIDi, XUSERIDi, XSEMIDi, dSEMIDi, dUSERIDi〉 to LH. M returns QIDi to I.(3)
SEM-Extract (IDi). If IDi=ID* andUSER-Extract (ID*) has been queried before, M aborts. If IDi=ID*, butUSER-Extract (ID*) has not been queried before, M chooses dSEMID*←$Zϕ(N)* and sets XSEMID*=QID*dSEMID* as the SEM portion of the user private key, saves it in LH, and returns it to I. Otherwise for all other IDi≠ID*, M just retrieves XSEMIDi in LH and returns it to I.(4)
USER-Extract (IDi). If IDi=ID* andUSER-Extract (ID*) has been queried before, M aborts. If IDi=ID*, butSEM-Extract (ID*) has not been queried before, M chooses dUSERID*←$Zϕ(N)* and sets XUSERID*=QID*dUSERID* as the USER portion of the user private key, saves it in LH, and returns it to I. Otherwise for all other IDi≠ID*, M just retrieves XUSERIDi in LH and returns it to I.(5)
Identification (IDj, session). I will act as the cheating verifier to learn information from valid conversation transcripts from M. If IDi≠ID*M just retrieves IDi’s entry in LH and runs the identification protocol for either the SEM’s interactions, the user’s interactions, or both combined as in the protocol.Otherwise, forIDj=ID*, M then creates a full valid transcript for each mth query by picking zm,USERID*,zm,SEMID*←$Zq*, and cm,ID*←$Zq* and sets Zm,FULLID*=zm,USERID*×zm,SEMID*. M also sets Ym,USERID*=zm,USERID*eQID*-(cm,ID*/2), Ym,SEMID*=zm,SEMID*eQID*-(cm,ID*/2), and Ym,FULLID*=zm,FULLID*eQID*-cm,ID*. M tags the session with session=m. If I queries
(i)
SEM-Identification (ID*, m), M will return 〈Ym,SEMID*,cm,ID*,zm,SEMID*〉;(ii)
User-Identification (ID*, m), M will return 〈Ym,USERID*,cm,ID*,zm,USERID*〉;(iii)
Full-Identification (ID*, m), M will return 〈Ym,FULLID*,cm,ID*,zm,FULLID*〉.If no session is specified for the query,M just returns the next session in sequence. One can see thatSEM-Identification (ID*, m) andUser-Identification (ID*, m) can be combined to create a full and valid transcript on session m:
(8)Ym,FULLID*H(ID*)cm,ID*=Ym,SEMID*Ym,USERID*QID*cm,ID*=zm,SEMID*eQID*-(cm,ID*/2)zm,USERID*eQID*-(cm,ID*/2)QID*cm,ID*=[zm,SEMID*zm,USERID*]eQID*-cm,ID*QID*cm,ID*=zm,SEMID*ezm,USERID*e=zm,FULLID*e.Eventually, I stops Phase 1 and outputs the challenge ID, ID* on which it wishes to be challenged on. M checks if ID*=IDl from LH and aborts if not. Otherwise, M runs I now as a cheating prover on ID* by obtaining its commitment, YFULLID*, selecting a challenge c1←$Zq* and obtaining the response zFULLID*,1 from I.M then resets I to the step whereby I just sent YFULLID*, selects a second challenge c2←$Zq*, and receives zFULLID*,2 as response. It should hold that zFULLID*,1e=YFULLID*H(ID)c1 and zFULLID*,2e=YFULLID*H(ID)c2. One can then obtain (zFULLID*,1/zFULLID*,2)e=H(ID)c1-c2. Since e is a prime and -e<c1-c2<e, GCD(e,c1-c2)=1. Use the extended Euclidean algorithm to obtain integers S and T such that eS+(c1-c2)T=1. It follows that
(9)H(ID*)=QID*eS+(c1-c2)Tmod⁡N=(yfID*e)eS+(c1-c2)Tmod⁡N=(yfID*e2S)(yfID*e(c1-c2)T)mod⁡N=(yfID*e2S)(zFULLID*,1zFULLID*,2)eTmod⁡N=[(yfID*eS)(zFULLID*,1zFULLID*,2)T]emod⁡N.M then calculates the solution to the RSAI problem as follows:
(10)yfID*e=[(yfID*eS)(zFULLID*,1zFULLID*,2)T]emod⁡N,ydfID*=(yfID*eS)(zFULLID*,1zFULLID*,2)Tmod⁡N,yd=(yfID*eS)(zFULLID*,1/zFULLID*,2)TfID*mod⁡N,yd=(yfID*eS-1)(zFULLID*,1zFULLID*,2)Tmod⁡N.
It remains to calculate the probability ofM solving the RSAI problem and winning the game. The probability of M successfully extracting two valid conversation transcripts from I is bounded by (εIBI-(1/2l(k)))2 as given by the reset lemma [20]:
(11)Pr[MwinsRSAI]=Pr[Mcomputesgab⋀¬abort]=Pr[Mcomputesgab∣¬abort]Pr[¬abort]εRSAI≥(εSMIBI-12l(k))2Pr[¬abort].
Finally calculate Pr[¬abort]. Let δ be the probability that I issues both aSEM-Extract and aUSER-Extract query on ID* and that I makes a total of qSMIBI of such queries. The probability of M answering all the extraction queries is δSMIBIq. In Phase 2, the probability of M not aborting is if I outputs the challenge identity ID* that was not queried before. This is given by the probability 1-δ. Compiling them, the probability of M not aborting is δqSMIBI(1-δ). This probability is maximised at δopt=1-(1/(qSMIBI+1)). Using δopt, the probability that M does not abort is at least 1/(2l(k)(qSMIBI+1)) because the value (1-(1/(qSMIBI+1)))qSMIBI approaches 1/e for large qSMIBI. Therefore, the advantage of M, εRSAI, and the bound of the simulation are given as follows:(12)εRSAI≥(εSMIBI-12l(k))21(qSMIBI+1)εRSAI(qSMIBI+1)≥(εSMIBI-12l(k))2εSMIBI≤εRSAI(qSMIBI+1)+12l(k).


### 3.2. Security Analysis: Impersonation under Active/Concurrent Attack

Theorem 6.
The GQ-SM-IBI scheme is(tSMIBI,qSMIBI,εSMIBI)-secure against impersonation under active/concurrent attacks in the random oracle if the OMCDH Problem is (tOMRSAI,qOMRSAI,εOMRSAI)-hard where
(13)εSMIBI≤εOMRSAIe(qSMIBI+1)+12l(k).Proof.
Assume the GQ-SM-IBI scheme is(tSMIBI,qSMIBI,εSMIBI)-breakable; then a simulator M that (tOMRSAI,qOMRSAI,ε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. AnySEM-Extract, User-Extract, SEM-Identification, User-Identification, andFull-Identification queries are preceded by aCreate-User query. M maintains a list LH=〈IDi,QIDi,fIDi,XFULLIDi,XSEMIDi,XUSERIDi,dSEMIDi,dUSERIDi〉 which is initially empty. The following shows how M simulates the environment and oracle queries for I. (1)
Create-User (IDi). M chooses l∈{1,…,qH} randomly and lets IDl=ID* at this point. Whenever I makes a H query on IDi, consider the following.
(i)
Ifi=l, M will choose fID*←$ZN*, queries CHALL for w0, and sets QID*=w0fID*e and will return QID* to I. It adds 〈IDl, QID*, fID*, XFULLID*=⊥, XUSERID*=⊥, XSEMID*=⊥, dSEMID*=⊥, dUSERID*=⊥〉 to LH.(ii)
Otherwise, fori≠l, M chooses fIDi←$Zq*, sets QIDi=fIDie, and returns QIDi to I. M also sets XFULLIDi=fIDi, chooses dUSERID*←$Zϕ(N)*, and sets XSEMIDi=QIDidSEMIDi as the SEM portion of the user private key and XUSERIDi=fIDiQIDi-dUSERIDi as the user portion of the user private key. It can be seen that
(14)XSEMIDi×XUSERIDi=QIDidSEMIDi×fIDiQIDi-dSEMIDi=fIDi=XFULLIDi.M adds 〈IDi,QIDi, fIDi, XFULLIDi, XUSERIDi, XSEMIDi, dSEMIDi, dUSERIDi〉 to LH. M returns QIDi to I.(2)
SEM-Extract (IDi). If IDi=ID* andUSER-Extract (ID*) has been queried before, M aborts. If IDi=ID*, butUSER-Extract (ID*) has not been queried before, M chooses dSEMID*←$Zϕ(N)* and sets XSEMID*=QID*dSEMID* as the SEM portion of the user private key, saves it in LH, and returns it to I. Otherwise for all other IDi≠ID*, M just retrieves XSEMIDi in LH and returns it to I.(3)
USER-Extract (IDi). If IDi=ID* andSEM-Extract (ID*) has been queried before, M aborts. If IDi=ID*, butSEM-Extract (ID*) has not been queried before, M chooses dUSERID*←$Zϕ(N)* and sets XUSERID*=QID*dUSERID* as the USER portion of the user private key, saves it in LH, and returns it to I. Otherwise for all other IDi≠ID*, M just retrieves XUSERIDi in LH and returns it to I.(4)
Identification (IDi, session). I will act as the cheating verifier to learn information from valid conversation interactions from M. If IDi≠ID*M just retrieves IDi’s entry in LH and runs the identification protocol for either the SEM’s interactions, the user’s interactions, or both combined as in the protocol.
Otherwise, forID*=ID*, M then creates a full valid conversation for each mth query by querying CHALL for Wm and setting YFULLID*=Wm. Additionally, M chooses Ym,SEMID*←$ZN* and sets Ym,UserID*=Wm/Ym,SEMID*. Upon receiving cm,ID* from I, M will query RSA(Wm(W0fID*e)cm,ID*) to receive Vm=(Wm(W0fID*e)cm,ID*)d and sets zFULLID*=Vm. M then chooses zm,SEMID*←$ZN* and then sets zm,USERID*=Vm/zm,SEMID*. M tags the session with session=m.
(i)
IfI queriesSEM-Identification (ID*, m), M will commit Ym,SEMID* and respond with zm,SEMID* upon receiving cm,ID*.
(ii)
IfI queriesUser-Identification (ID*, m), M will commit Ym,USERID* and respond with zm,USERID* upon receiving cm,ID*.
(iii)
IfI queriesFull-Identification (ID*, m), M will commit Ym,FULLID* and respond with zm,FULLID* upon receiving cm,ID*.
If no session is specified for the query,M just returns the next session in sequence. One can see thatSEM-Identification   (ID*, m) andUser-Identification   (ID*, m) can be combined to create a full and valid conversation on session m:
(15)Ym,FULLID*H(ID*)cm,ID*=Ym,SEMID*Ym,USERID*QID*cm,ID*=Ym,SEMID*WmYm,SEMID*(W0fID*e)cm,ID*=Wm(W0fID*e)cm,ID*=[Wm(W0fID*e)cm,ID*]de=[[Wm(W0fID*e)cm,ID*]d]e=[Vm]e=(Vmzm,SEMID*)e(zm,SEMID*)e=zm,SEMID*ezm,USERID*e=zm,FULLID*e.
Eventually,I stops Phase 1 and outputs the challenge ID, ID* on which it wishes to be challenged on. M checks if ID*=IDl from LH and aborts if not. Otherwise, M runs I now as a cheating prover on ID*. M runs by obtaining its commitment, YFULLID*, selects a challenge c1←$Zq*, and obtains the response zFULLID*,1 from I. M then resets I to the step whereby I just sent YFULLID*, selects a second challenge c2←$Zq*, and receives zFULLID*,2 as response. It should hold that zFULLID*,1e=YFULLID*H(ID)c1 and zFULLID*,2e=YFULLID*H(ID)c2. One can then obtain (zFULLID*,1/zFULLID*,2)e=H(ID)c1-c2. Since e is a prime and -e<c1-c2<e, GCD(e,c1-c2)=1. Use the extended Euclidean algorithm to obtain integers S and T such that eS+(c1-c2)T=1. It follows that
(16)H(ID*)=QID*eS+(c1-c2)Tmod⁡N=(w0fID*e)eS+(c1-c2)Tmod⁡N=(w0fID*e2S)(w0fID*e(c1-c2)T)mod⁡N=(w0fID*e2S)(zFULLID*,1zFULLID*,2)eTmod⁡N=[(w0fID*eS)(zFULLID*,1zFULLID*,2)T]emod⁡N.
M then calculates the solution to the RSAI problem as follows:
(17)w0fID*e=[(w0fID*eS)(zFULLID*,1zFULLID*,2)T]emod⁡N,w0dfID*=(w0fID*eS)(zFULLID*,1zFULLID*,2)Tmod⁡N,w0d=(w0fID*eS)(zFULLID*,1/zFULLID*,2)TfID*mod⁡N,w0d=(w0fID*eS-1)(zFULLID*,1zFULLID*,2)Tmod⁡N.
M proceeds to calculate the solutions to the other challenges as follows:
(18)wj=Vj(w0fID*)-cm,ID*.
The probability study for the simulation above is similar to that of the impersonation under passive attack game and is therefore omitted.


## 3.1. Security Analysis: Impersonation under Passive Attack

Theorem 5.
The GQ-SM-IBI scheme is(tSMIBI,qSMIBI,εSMIBI)-secure against impersonation under passive attacks in the random oracle if the RSA Inversion Problem is (tRSAI,εRSAI)-hard where
(6)εSMIBI≤εRSAIe(qSMIBI+1)+12l(k).Proof.
Assume the GQ-SM-IBI scheme is(tSMIBI,qSMIBI,εSMIBI)-breakable; then a simulator M that (tRSAI,ε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 anySEM-Extract, User-Extract, SEM-Identification, User-Identification, andFull-Identification queries are preceded by aCreate-User query. To avoid collision and consistently respond to these queries, M maintains a list LH=〈IDi,QIDi,fIDi,XFULLIDi,XSEMIDi,XUSERIDi,dSEMIDi,dUSERIDi〉 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}*→ZN* and sets the system parameters as mpk=〈N,e,H〉. It sends mpk to I.(2)
Create-User(IDi). M chooses l∈{1,…,qH} randomly and lets IDl=ID* at this point. Whenever I makes a H query on IDi, consider the following.
(a)
Ifi=l, M will choose fID*←$ZN* sets QID*=yfID*e and will return QID* to I. It adds 〈IDl,QID*,fID*,XFULLID*=⊥,XUSERID*=⊥,XSEMID*=⊥,dSEMID*=⊥,dUSERID*=bot〉 to LH.(b)
Otherwise, fori≠l, M chooses fIDi←$Zq*, sets QIDi=fIDie, and returns QIDi to I. M also sets XFULLIDi=fIDi, chooses dUSERID*←$Zϕ(N)*, and sets XSEMIDi=QIDidSEMIDi as the SEM portion of the user private key and XUSERIDi=fIDiQIDi-dUSERIDi as the user portion of the user private key. It can be seen that
(7)XSEMIDi×XUSERIDi=QIDidSEMIDi×fIDiQIDi-dSEMIDi=fIDi=XFULLIDi.M adds 〈IDi, QIDi, fIDi, XFULLIDi, XUSERIDi, XSEMIDi, dSEMIDi, dUSERIDi〉 to LH. M returns QIDi to I.(3)
SEM-Extract (IDi). If IDi=ID* andUSER-Extract (ID*) has been queried before, M aborts. If IDi=ID*, butUSER-Extract (ID*) has not been queried before, M chooses dSEMID*←$Zϕ(N)* and sets XSEMID*=QID*dSEMID* as the SEM portion of the user private key, saves it in LH, and returns it to I. Otherwise for all other IDi≠ID*, M just retrieves XSEMIDi in LH and returns it to I.(4)
USER-Extract (IDi). If IDi=ID* andUSER-Extract (ID*) has been queried before, M aborts. If IDi=ID*, butSEM-Extract (ID*) has not been queried before, M chooses dUSERID*←$Zϕ(N)* and sets XUSERID*=QID*dUSERID* as the USER portion of the user private key, saves it in LH, and returns it to I. Otherwise for all other IDi≠ID*, M just retrieves XUSERIDi in LH and returns it to I.(5)
Identification (IDj, session). I will act as the cheating verifier to learn information from valid conversation transcripts from M. If IDi≠ID*M just retrieves IDi’s entry in LH and runs the identification protocol for either the SEM’s interactions, the user’s interactions, or both combined as in the protocol.Otherwise, forIDj=ID*, M then creates a full valid transcript for each mth query by picking zm,USERID*,zm,SEMID*←$Zq*, and cm,ID*←$Zq* and sets Zm,FULLID*=zm,USERID*×zm,SEMID*. M also sets Ym,USERID*=zm,USERID*eQID*-(cm,ID*/2), Ym,SEMID*=zm,SEMID*eQID*-(cm,ID*/2), and Ym,FULLID*=zm,FULLID*eQID*-cm,ID*. M tags the session with session=m. If I queries
(i)
SEM-Identification (ID*, m), M will return 〈Ym,SEMID*,cm,ID*,zm,SEMID*〉;(ii)
User-Identification (ID*, m), M will return 〈Ym,USERID*,cm,ID*,zm,USERID*〉;(iii)
Full-Identification (ID*, m), M will return 〈Ym,FULLID*,cm,ID*,zm,FULLID*〉.If no session is specified for the query,M just returns the next session in sequence. One can see thatSEM-Identification (ID*, m) andUser-Identification (ID*, m) can be combined to create a full and valid transcript on session m:
(8)Ym,FULLID*H(ID*)cm,ID*=Ym,SEMID*Ym,USERID*QID*cm,ID*=zm,SEMID*eQID*-(cm,ID*/2)zm,USERID*eQID*-(cm,ID*/2)QID*cm,ID*=[zm,SEMID*zm,USERID*]eQID*-cm,ID*QID*cm,ID*=zm,SEMID*ezm,USERID*e=zm,FULLID*e.Eventually, I stops Phase 1 and outputs the challenge ID, ID* on which it wishes to be challenged on. M checks if ID*=IDl from LH and aborts if not. Otherwise, M runs I now as a cheating prover on ID* by obtaining its commitment, YFULLID*, selecting a challenge c1←$Zq* and obtaining the response zFULLID*,1 from I.M then resets I to the step whereby I just sent YFULLID*, selects a second challenge c2←$Zq*, and receives zFULLID*,2 as response. It should hold that zFULLID*,1e=YFULLID*H(ID)c1 and zFULLID*,2e=YFULLID*H(ID)c2. One can then obtain (zFULLID*,1/zFULLID*,2)e=H(ID)c1-c2. Since e is a prime and -e<c1-c2<e, GCD(e,c1-c2)=1. Use the extended Euclidean algorithm to obtain integers S and T such that eS+(c1-c2)T=1. It follows that
(9)H(ID*)=QID*eS+(c1-c2)Tmod⁡N=(yfID*e)eS+(c1-c2)Tmod⁡N=(yfID*e2S)(yfID*e(c1-c2)T)mod⁡N=(yfID*e2S)(zFULLID*,1zFULLID*,2)eTmod⁡N=[(yfID*eS)(zFULLID*,1zFULLID*,2)T]emod⁡N.M then calculates the solution to the RSAI problem as follows:
(10)yfID*e=[(yfID*eS)(zFULLID*,1zFULLID*,2)T]emod⁡N,ydfID*=(yfID*eS)(zFULLID*,1zFULLID*,2)Tmod⁡N,yd=(yfID*eS)(zFULLID*,1/zFULLID*,2)TfID*mod⁡N,yd=(yfID*eS-1)(zFULLID*,1zFULLID*,2)Tmod⁡N.
It remains to calculate the probability ofM solving the RSAI problem and winning the game. The probability of M successfully extracting two valid conversation transcripts from I is bounded by (εIBI-(1/2l(k)))2 as given by the reset lemma [20]:
(11)Pr[MwinsRSAI]=Pr[Mcomputesgab⋀¬abort]=Pr[Mcomputesgab∣¬abort]Pr[¬abort]εRSAI≥(εSMIBI-12l(k))2Pr[¬abort].
Finally calculate Pr[¬abort]. Let δ be the probability that I issues both aSEM-Extract and aUSER-Extract query on ID* and that I makes a total of qSMIBI of such queries. The probability of M answering all the extraction queries is δSMIBIq. In Phase 2, the probability of M not aborting is if I outputs the challenge identity ID* that was not queried before. This is given by the probability 1-δ. Compiling them, the probability of M not aborting is δqSMIBI(1-δ). This probability is maximised at δopt=1-(1/(qSMIBI+1)). Using δopt, the probability that M does not abort is at least 1/(2l(k)(qSMIBI+1)) because the value (1-(1/(qSMIBI+1)))qSMIBI approaches 1/e for large qSMIBI. Therefore, the advantage of M, εRSAI, and the bound of the simulation are given as follows:(12)εRSAI≥(εSMIBI-12l(k))21(qSMIBI+1)εRSAI(qSMIBI+1)≥(εSMIBI-12l(k))2εSMIBI≤εRSAI(qSMIBI+1)+12l(k).


## 3.2. Security Analysis: Impersonation under Active/Concurrent Attack

Theorem 6.
The GQ-SM-IBI scheme is(tSMIBI,qSMIBI,εSMIBI)-secure against impersonation under active/concurrent attacks in the random oracle if the OMCDH Problem is (tOMRSAI,qOMRSAI,εOMRSAI)-hard where
(13)εSMIBI≤εOMRSAIe(qSMIBI+1)+12l(k).Proof.
Assume the GQ-SM-IBI scheme is(tSMIBI,qSMIBI,εSMIBI)-breakable; then a simulator M that (tOMRSAI,qOMRSAI,ε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. AnySEM-Extract, User-Extract, SEM-Identification, User-Identification, andFull-Identification queries are preceded by aCreate-User query. M maintains a list LH=〈IDi,QIDi,fIDi,XFULLIDi,XSEMIDi,XUSERIDi,dSEMIDi,dUSERIDi〉 which is initially empty. The following shows how M simulates the environment and oracle queries for I. (1)
Create-User (IDi). M chooses l∈{1,…,qH} randomly and lets IDl=ID* at this point. Whenever I makes a H query on IDi, consider the following.
(i)
Ifi=l, M will choose fID*←$ZN*, queries CHALL for w0, and sets QID*=w0fID*e and will return QID* to I. It adds 〈IDl, QID*, fID*, XFULLID*=⊥, XUSERID*=⊥, XSEMID*=⊥, dSEMID*=⊥, dUSERID*=⊥〉 to LH.(ii)
Otherwise, fori≠l, M chooses fIDi←$Zq*, sets QIDi=fIDie, and returns QIDi to I. M also sets XFULLIDi=fIDi, chooses dUSERID*←$Zϕ(N)*, and sets XSEMIDi=QIDidSEMIDi as the SEM portion of the user private key and XUSERIDi=fIDiQIDi-dUSERIDi as the user portion of the user private key. It can be seen that
(14)XSEMIDi×XUSERIDi=QIDidSEMIDi×fIDiQIDi-dSEMIDi=fIDi=XFULLIDi.M adds 〈IDi,QIDi, fIDi, XFULLIDi, XUSERIDi, XSEMIDi, dSEMIDi, dUSERIDi〉 to LH. M returns QIDi to I.(2)
SEM-Extract (IDi). If IDi=ID* andUSER-Extract (ID*) has been queried before, M aborts. If IDi=ID*, butUSER-Extract (ID*) has not been queried before, M chooses dSEMID*←$Zϕ(N)* and sets XSEMID*=QID*dSEMID* as the SEM portion of the user private key, saves it in LH, and returns it to I. Otherwise for all other IDi≠ID*, M just retrieves XSEMIDi in LH and returns it to I.(3)
USER-Extract (IDi). If IDi=ID* andSEM-Extract (ID*) has been queried before, M aborts. If IDi=ID*, butSEM-Extract (ID*) has not been queried before, M chooses dUSERID*←$Zϕ(N)* and sets XUSERID*=QID*dUSERID* as the USER portion of the user private key, saves it in LH, and returns it to I. Otherwise for all other IDi≠ID*, M just retrieves XUSERIDi in LH and returns it to I.(4)
Identification (IDi, session). I will act as the cheating verifier to learn information from valid conversation interactions from M. If IDi≠ID*M just retrieves IDi’s entry in LH and runs the identification protocol for either the SEM’s interactions, the user’s interactions, or both combined as in the protocol.
Otherwise, forID*=ID*, M then creates a full valid conversation for each mth query by querying CHALL for Wm and setting YFULLID*=Wm. Additionally, M chooses Ym,SEMID*←$ZN* and sets Ym,UserID*=Wm/Ym,SEMID*. Upon receiving cm,ID* from I, M will query RSA(Wm(W0fID*e)cm,ID*) to receive Vm=(Wm(W0fID*e)cm,ID*)d and sets zFULLID*=Vm. M then chooses zm,SEMID*←$ZN* and then sets zm,USERID*=Vm/zm,SEMID*. M tags the session with session=m.
(i)
IfI queriesSEM-Identification (ID*, m), M will commit Ym,SEMID* and respond with zm,SEMID* upon receiving cm,ID*.
(ii)
IfI queriesUser-Identification (ID*, m), M will commit Ym,USERID* and respond with zm,USERID* upon receiving cm,ID*.
(iii)
IfI queriesFull-Identification (ID*, m), M will commit Ym,FULLID* and respond with zm,FULLID* upon receiving cm,ID*.
If no session is specified for the query,M just returns the next session in sequence. One can see thatSEM-Identification   (ID*, m) andUser-Identification   (ID*, m) can be combined to create a full and valid conversation on session m:
(15)Ym,FULLID*H(ID*)cm,ID*=Ym,SEMID*Ym,USERID*QID*cm,ID*=Ym,SEMID*WmYm,SEMID*(W0fID*e)cm,ID*=Wm(W0fID*e)cm,ID*=[Wm(W0fID*e)cm,ID*]de=[[Wm(W0fID*e)cm,ID*]d]e=[Vm]e=(Vmzm,SEMID*)e(zm,SEMID*)e=zm,SEMID*ezm,USERID*e=zm,FULLID*e.
Eventually,I stops Phase 1 and outputs the challenge ID, ID* on which it wishes to be challenged on. M checks if ID*=IDl from LH and aborts if not. Otherwise, M runs I now as a cheating prover on ID*. M runs by obtaining its commitment, YFULLID*, selects a challenge c1←$Zq*, and obtains the response zFULLID*,1 from I. M then resets I to the step whereby I just sent YFULLID*, selects a second challenge c2←$Zq*, and receives zFULLID*,2 as response. It should hold that zFULLID*,1e=YFULLID*H(ID)c1 and zFULLID*,2e=YFULLID*H(ID)c2. One can then obtain (zFULLID*,1/zFULLID*,2)e=H(ID)c1-c2. Since e is a prime and -e<c1-c2<e, GCD(e,c1-c2)=1. Use the extended Euclidean algorithm to obtain integers S and T such that eS+(c1-c2)T=1. It follows that
(16)H(ID*)=QID*eS+(c1-c2)Tmod⁡N=(w0fID*e)eS+(c1-c2)Tmod⁡N=(w0fID*e2S)(w0fID*e(c1-c2)T)mod⁡N=(w0fID*e2S)(zFULLID*,1zFULLID*,2)eTmod⁡N=[(w0fID*eS)(zFULLID*,1zFULLID*,2)T]emod⁡N.
M then calculates the solution to the RSAI problem as follows:
(17)w0fID*e=[(w0fID*eS)(zFULLID*,1zFULLID*,2)T]emod⁡N,w0dfID*=(w0fID*eS)(zFULLID*,1zFULLID*,2)Tmod⁡N,w0d=(w0fID*eS)(zFULLID*,1/zFULLID*,2)TfID*mod⁡N,w0d=(w0fID*eS-1)(zFULLID*,1zFULLID*,2)Tmod⁡N.
M proceeds to calculate the solutions to the other challenges as follows:
(18)wj=Vj(w0fID*)-cm,ID*.
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 (1k). It takes in the security parameter 1k. It randomly selects x←$Zq, a generator g←$G and computes X=gx. Setup also chooses H:{0,1}*→Zq 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 rFULL,rSEM,sSEM←$Zq, calculates sFULL=rFULL+xH(ID) and RFULL=grFULL, and sets the full user private key as uskFULL=〈sFULL,RFULL〉. Additionally, it sets sUSER=sFULL-sSEM, rUSER=rFULL-rSEM, RUSER=grUSER, RSEM=grSEM. It then sets uskUSER=〈sUSER,RUSER〉 and uskSEM=〈sSEM,RSEM〉. It gives uskUSER to the user as its partial private key and uskSEM to the security mediator as its partial private key and keeps uskFULL secret.(3)
Identification Protocol.It is run by theUser-Prover andSEM-Prover withVerifier as such.
(a)
User-Prover sends its ID toSem-Prover, chooses yUSER←$Zq, and sets YUSER=gyUSER and SUser=gsUSER.SEM-Prover upon receiving ID checks if it is still valid and returns error if it is revoked. Otherwise,SEM-Prover chooses ySEM←$Zq and sends YSEM=gySEM, SSEM=gsSEM, and RSEM toUser-Prover.User-Prover combines YFULL=YSEM×YUSER, SFULL=SSEM×SUSER, RFULL=RSEM×RUSER and sends YFULL,SFULL, and RFULL toVerifier.(b)
Verifier chooses a random challenge c←$Zq and sends it toUser-Prover.User-Prover relays c toSEM-Prover.(c)
SEM-Prover calculates its half of the response zSEM=ySEM+csSEM and sends it toUser-Prover.User-Prover combines it with his response zUSER=yUSER+csUSER to create zFULL=zSEM+zUSER and sends it as a response toVerifier.Verifier checks if gzFULL=YFULLRFULLcXH(ID)c and accepts if yes; otherwise it outputs reject.To check for completeness,(19)gzFULL=gzSEM+zUSER=gySEM+csSEM+yUSER+csUSER=gySEM+yUSER+c(sSEM+sUSER)=gyFULL+c(sFULL)=gyFULL+c(rFULL+xH(ID))=gyFULLgrFULLcgxH(ID)c=YFULLRFULLcXH(ID)c.


### 4.1. Security Analysis: Impersonation under Passive Attack

Theorem 7.
The BNN-SM-IBI scheme is(tSMIBI,qSMIBI,εSMIBI)-secure against impersonation under passive attacks in the random oracle if the DL problem is (tDL,εDL)-hard where
(20)εSMIBI≤εDLe(qSMIBI+1)+1q.Proof.
Assume the BNN-SM-IBI scheme is(tSMIBI,qSMIBI,εSMIBI)-breakable; then a simulator M that (tDL,εDL)-breaks the DL problem can be shown. M takes in input (g,A=ga) and runs the impersonator I as a subroutine. Without loss of generality, it can be assumed that anySEM-Extract,User-Extract,SEM-Identification,User-Identification, andFull-Identification queries are preceded by aCreate-User query. To avoid collision and consistently respond to these queries, M maintains a list LH=〈IDi,QIDi, SFULLIDi, SSEMIDi, SUSERIDi, sFULLIDi, sSEMIDi, sUSERIDi, rFULLIDi, rSEMIDi, rUSERIDi, RFULLIDi, RSEMIDi, RUSERIDi〉 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=gx,H〉 and keeps master private key x secret. It sends mpk to I.(2)
Create-User(IDi). M chooses l∈{1,…,qH} randomly and lets IDl=ID* at this point. Whenever I makes a H query on IDi, consider the following.
(i)
Ifi=l, M chooses QID*←$Zq and sets SFULLID*=A and RFULLID*=AXQID* and returns QID* to I. M adds 〈IDl, QID*, SFULLID*, SSEMID*=⊥, SUSERID*, sFULLID*=⊥, sSEMID*, sUSERID*=⊥, rFULLID*=⊥, rSEMID*=⊥, rUSERID*=⊥, RFULLID*, RSEMID*=⊥, RUSERID*=⊥〉 to LH.(ii)
Otherwise, fori≠l, M chooses QIDi←$Zq* and returns QIDi. It then chooses rFULLIDi,rSEMIDi,sSEMIDi←$Zq*, calculates sFULLIDi=rFULLIDi+xQ, and sets rUSERIDi=rFULLIDi-rSEMIDi and sUSERIDi=sFULLIDi-sSEMIDi. M adds 〈IDi, QIDi, SFULLIDi, SSEMIDi, SUSERIDi, sFULLIDi, sSEMIDi, sUSERIDi, rFULLIDi, rSEMIDi, rUSERIDi, RFULLIDi, RSEMIDi, RUSERIDi〉 to LH.(3)
SEM-Extract (IDi). If IDi=ID* andUSER-Extract (ID*) has been queried before, M aborts. If IDi=ID*, butUSER-Extract (ID*) has not been queried before, M will choose rSEMID*,sSEMID*←$Zq and sets RSEMID*=grSEMID* and SSEMID*=gsSEMID*. M also sets SUSERID*=SFULLID*/SSEMID* and RUSERID*=RFULLID*/RSEMID*, saves these values in LH, and returns them to I. These values will be used in the event of anIdentification query later on. Otherwise for all other IDi≠ID*, M just retrieves 〈sSEMIDi,RSEMIDi〉 in LH and returns it to I.(4)
USER-Extract (IDi). If IDi=ID* andSEM-Extract (ID*) has been queried before, M aborts. If IDi=ID*, butSEM-Extract (ID*) has not been queried before, M will choose rUSERID*,sUSERID*←$Zq and sets RUSERID*=grUSERID* and SUSERID*=gsUSERID*. M also sets SSEMID*=SFULLID*/SUSERID* and RSEMID*=RFULLID*/RUSERID*, saves these values in LH, and returns them to I. These values will be used in the event of anIdentification query later on. Otherwise for all other IDi≠ID*, M just retrieves 〈sUSERIDi,RUSERIDi〉 in LH and returns it to I.(5)
Identification (IDj, session). I will act as the cheating verifier to learn information from valid conversation transcripts from M. If IDj≠ID*, M just retrieves IDj’s entry in LH and runs the identification protocol for either the SEM’s interactions, the user’s interactions, or both combined as in the protocol.Otherwise, forIDj=ID*, M then creates a full valid transcript for each mth query by picking zm,FULLID*,zm,SEMID*,cm,ID*←$Zq. M retrieves SFULLID*, RFULLID* and sets Ym,FULLID*=gzm,FULLID*SFULLID*-cm,ID*. Additionally, M chooses zm,SEMID*←$Zq, calculates zm,USERID*=zm,FULLID*-zm,SEMID*, and retrieves SSEMID*, RSEMID* and SUSERID*, RUSERID* from LH as well. M then sets Ym,SEMID*=gzm,SEMID*SSEMID*cm,ID* and Ym,USERID*=gzm,USERID*SUSERID*cm,ID*. M tags the session with session=m. If I queries
(i)
SEM-Identification (ID*, m), M will return 〈Ym,SEMID*,SSEMID*,RSEMID*,cm,ID*,zm,SEMID*〉;(ii)
User-Identification (ID*, m), M will return 〈Ym,USERID*, SUSERID*, RUSERID*, cm,ID*zm,USERID*〉;(iii)
Full-Identification (ID*, m), M will return 〈Ym,FULLID*, SFULLID*, RFULLID*, cm,ID*zm,FULLID*〉.If no session is specified for the query,M just returns the next session in sequence. One can see thatSEM-Identification  (ID*, m) andUser-Identification  (ID*,m) can be combined to create a full and valid transcript on session m:
(21)Ym,FULLID*RFULLID*cm,ID*XH(ID*)cm,ID*=Ym,USERID*Ym,SEMID*RUSERID*cm,ID*RSEMID*cm,ID*×XH(ID*)cm,ID*=(gzm,USERID*SUSERID*-cm,ID*gzm,SEMID*)SSEMID*-cm,ID*×(RUSERID*RSEMID*)cm,ID*XH(ID*)cm,ID*=gzm,USERID*gzm,SEMID*(SUSERID*SSEMID*)-cm,ID*×(RUSERID*RSEMID*)cm,ID*XH(ID*)cm,ID*=gzm,USERID*gzm,SEMID*(SFULLID*SSEMID*SSEMID*)-cm,ID*×(RFULLID*RSEMID*RSEMID*)cm,ID*XH(ID*)cm,ID*=gzm,FULLID*A-cm,ID*Acm,ID*X-H(ID*)cm,ID*×XH(ID*)cm,ID*=gzm,FULLID*.Eventually, I stops Phase 1 and outputs the challenge ID, ID* on which it wishes to be challenged on. M checks if ID=IDl from LH and aborts if not. Otherwise, M runs I now as a cheating prover on ID* by obtaining its commitment, YFULLID*, SFULLID*, RFULLID* selecting a challenge c1←$Zq* and obtaining the response zFULLID*,1 from I. M then resets I to the step whereby I just sent YFULLID*, SFULLID*, RFULLID*, selects a second challenge c2←$Zq*, and receives zFULLID*,2 as response. M is then able to extract the full user private key as follows:
(22)zFULLID*,1-zFULLID*,2c1-c2=yFULLID*+c1a-yFULLID*+c2ac1-c2=(c1-c2)ac1-c2=a.M outputs a as the discrete log solution.
It remains to calculate the probability ofM solving the CDH problem and winning the game. The probability of M successfully extracting two valid conversation transcripts from I is bounded by (εSMIBI-(1/q))2 as given by the reset lemma [20]:
(23)Pr[MwinsDL]=Pr[Mcomputesa⋀¬abort]=Pr[Mcomputesa∣¬abort]Pr[¬abort]εDL≥(εSMIBI-1q)2Pr[¬abort].
Finally, let δ be the probability that I issues aSEM-Extract and aUSER-Extract query on ID* and that I makes a total of qSMIBI of such queries. The probability of M answering all the extraction queries is δIq. In Phase 2, the probability of M not aborting is if I outputs the challenge identity ID* that was not queried before. This is given by the probability 1-δ. Compiling them, the probability of M not aborting is δqSMIBI(1-δ). This value is maximised at δopt=1-(1/(qSMIBI+1)). Using δopt, The probability that M does not abort is at least 1/e(qSMIBI+1) because the value (1-(1/(qSMIBI+1)))qSMIBI approaches 1/e for large qSMIBI. Therefore, the advantage of M, εDL, and the bound of the simulation is given as follows:
(24)εDL≥(εSMIBI-1q)21e(qSMIBI+1)εDLe(qSMIBI+1)≥(εSMIBI-1q)2εSMIBI≤εDLe(qSMIBI+1)+1q.


### 4.2. Security Analysis: Impersonation under Active/Concurrent Attack

Theorem 8.
The BNN-SM-IBI scheme is(tSMIBI,qSMIBI,εSMIBI)-secure against impersonation under active/concurrent attacks in the random oracle if the OMCDH Problem is (tOMCDH,qOMCDH,εOMCDH)-hard where
(25)εSMIBI≤εOMCDHe(qSMIBI+1)+1q.Proof.
Assume the BNN-SM-IBI scheme is(tSMIBI,qSMIBI,εSMIBI)-breakable; then a simulator M that (tOMCDH,qOMCDH,εOMCDH)-breaks the OMCDH Problem can be shown. M takes in input (g,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 anySEM-Extract,User-Extract,SEM-Identification,User-Identification, andFull-Identification queries are preceded by aCreate-User query. To avoid collision and consistently respond to these queries, M maintains a list LH=〈IDi,QIDi, SFULLIDi, SSEMIDi, SUSERIDi, sFULLIDi, sSEMIDi, sUSERIDi, rFULLIDi, rSEMIDi, rUSERIDi, RFULLIDi, RSEMIDi,RUSERIDi〉 which is initially empty. The following shows how M simulates the environment and oracle queries for I. (1)
Setup. M sets the system parameters asmpk=〈G,q,g,X=gx,H〉 and keeps master private key x secret. It sendsmpk to I.(2)
Create-User (IDi). M chooses l∈{1,…,qH} randomly and lets IDl=ID* at this point. Whenever I makes a H query on IDi, consider the following.
(i)
Ifi=l, M chooses QID*←$Zq, queries CHALL for W0, and sets SFULLID*=W0 and RFULLID*=W0XQID*. M returns QID* to I. M adds LH=〈IDl, QID*, SFULLID*, SSEMID*=⊥, SUSERID*=⊥, sFULLID*=⊥, sSEMID*=⊥, sUSERID*=⊥, rFULLID*=⊥, rSEMID*=⊥, rUSERID*=⊥, RFULLID*, RSEMID*=⊥, RUSERID*=⊥〉 to LH.(ii)
Otherwise, fori≠l, M chooses QIDi←$Zq* and returns QIDi. It then chooses rFULLIDi,rSEMIDi,sSEMIDi←$Zq*, calculates sFULLIDi=rFULLIDi+xQ, and sets rUSERIDi=rFULLIDi-rSEMIDi and sUSERIDi=sFULLIDi-sSEMIDi. M adds LH=〈IDi,QIDi, SFULLIDi, SSEMIDi, SUSERIDi, sFULLIDi, sSEMIDi, sUSERIDi, rFULLIDi, rSEMIDi, rUSERIDi, RFULLIDi, RSEMIDi, RUSERIDi〉 to LH.(3)
SEM-Extract (IDi). If IDi=ID* andUSER-Extract (ID*) has been queried before, M aborts. If IDi=ID*, butUSER-Extract (ID*) has not been queried before, M will choose rSEMID*,sSEMID*←$Zq and sets RSEMID*=grSEMID* and SSEMID*=gsSEMID*. M also sets SUSERID*=SFULLID*/SSEMID* and RUSERID*=RFULLID*/RSEMID*, saves these values in LH, and returns them to I. These values will be used in the event of anIdentification query later on. Otherwise for all other IDi≠ID*, M just retrieves 〈sSEMIDi,RSEMIDi〉 in LH and returns it to I.(4)
USER-Extract (IDi). If IDi=ID* andSEM-Extract (ID*) has been queried before, M aborts. If IDi=ID*, butSEM-Extract (ID*) has not been queried before, M will choose rUSERID*,sUSERID*←$Zq and sets RUSERID*=grUSERID* and SUSERID*=gsUSERID*. M also sets SSEMID*=SFULLID*/SUSERID* and RSEMID*=RFULLID*/RUSERID*, saves these values in LH, and returns them to I. These values will be used in the event of an Identification query later on. Otherwise for all other IDi≠ID*, M just retrieves 〈sUSERIDi,RUSERIDi〉 in LH and returns it to I.(5)
Identification (IDj, session). I will act as the cheating verifier to learn information from valid conversations from M. If IDj≠ID*, M just retrieves IDj’s entry in LH and runs the identification protocol for either the SEM’s interactions, the user’s interactions, or both combined as in the protocol.
Otherwise, forIDi=ID*, M then creates a full valid conversation for each mth query by querying CHALL for Wm and setting Ym,FULLID*=Wm. M also retrieves. Additionally, M chooses Ym,SEMIDj←$G and sets Ym,UserIDj=Wm/Ym,SEMIDj. M also retrieves Sm,FULLIDj, Sm,SEMIDj, Sm,USERIDj, Rm,FULLIDj, Rm,SEMIDj, and Rm,USERIDj from LH. Upon receiving cm,IDj from I, M will query zm,FULLIDj=DLOG(WmW0cm,IDj), selects zm,SEMIDj←$Zq, and sets zm,USERIDj=zm,FULLIDj-zm,SEMIDj. M tags the session with session=m.
(a)
IfI queriesSEM-Identification (IDj, m), M will commit Ym,SEMIDj, SSEMIDj, RSEMIDj and respond with zm,SEMIDj upon receiving cm,IDj.
(b)
IfI queriesUser-Identification (IDj, m), M will commit Ym,USERIDj, SUSERIDj, RUSERIDj and respond with zm,USERIDj upon receiving cm,IDj.
(c)
IfI queriesFull-Identification (IDj,m), M will commit Ym,FULLIDj, SFULLIDj, RFULLIDj and respond with zm,FULLIDj upon receiving cm,IDj.
If no session is specified for the query,M just returns the next session in sequence. One can see thatSEM-Identification (IDj, m) andUser-Identification (ID*, m) can be combined to create a full and valid conversation on session m:
(26)Ym,FULLIDjRFULLIDjcm,IDjXH(IDj)cm,IDj=Ym,USERIDjYm,SEMIDjRUSERIDjcm,IDjRSEMIDjcm,IDjXH(IDj)cm,IDj=WmYm,SEMIDjYm,SEMIDj(W0X-H(ID)RSEMIDj)cm,IDj×RSEMIDjcm,IDjXH(IDj)cm,IDj=Wm(W0cm,IDj)X-H(ID)cm,IDjXH(IDj)cm,IDj=Wm(W0cm,IDj)=gDLOG(Wm(W0cm,IDj)=gzm,FULLIDj.Eventually, I stops Phase 1 and outputs the challenge ID, ID* on which it wishes to be challenged on. M checks if ID*=IDl from LH and aborts if not. Otherwise, M runs I now as a cheating prover on ID*. M runs by obtaining its commitment, YFULLID*, SFULLID*, RFULLID*, selects a challenge c1←$Zq*, and obtains the response zFULLID*,1 from I. M then resets I to the step whereby I just sent YFULLID*, SFULLID*, RFULLID*, selects a second challenge c2←$Zq*, and receives zFULLID*,2 as response. M is then able to extract the full user private key as follows:
(27)zFULLID*,1-zFULLID*,2c1-c2=yFULLID*+c1w0-yFULLID*+c2w0c1-c2=(c1-c2)w0c1-c2=w0.M outputs w0 as the initial discrete log challenge solution.
M proceeds to calculate the solutions to the other challenges as follows:
(28)zm,FULLIDj-w0cm,IDj=DLOG(WmW0cm,IDj)-w0cm,IDj=[wm+w0cm,IDj]-w0cm,IDj=wm.
The probability study for the simulation above is similar to that of the impersonation under passive attack game and is therefore omitted.


## 4.1. Security Analysis: Impersonation under Passive Attack

Theorem 7.
The BNN-SM-IBI scheme is(tSMIBI,qSMIBI,εSMIBI)-secure against impersonation under passive attacks in the random oracle if the DL problem is (tDL,εDL)-hard where
(20)εSMIBI≤εDLe(qSMIBI+1)+1q.Proof.
Assume the BNN-SM-IBI scheme is(tSMIBI,qSMIBI,εSMIBI)-breakable; then a simulator M that (tDL,εDL)-breaks the DL problem can be shown. M takes in input (g,A=ga) and runs the impersonator I as a subroutine. Without loss of generality, it can be assumed that anySEM-Extract,User-Extract,SEM-Identification,User-Identification, andFull-Identification queries are preceded by aCreate-User query. To avoid collision and consistently respond to these queries, M maintains a list LH=〈IDi,QIDi, SFULLIDi, SSEMIDi, SUSERIDi, sFULLIDi, sSEMIDi, sUSERIDi, rFULLIDi, rSEMIDi, rUSERIDi, RFULLIDi, RSEMIDi, RUSERIDi〉 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=gx,H〉 and keeps master private key x secret. It sends mpk to I.(2)
Create-User(IDi). M chooses l∈{1,…,qH} randomly and lets IDl=ID* at this point. Whenever I makes a H query on IDi, consider the following.
(i)
Ifi=l, M chooses QID*←$Zq and sets SFULLID*=A and RFULLID*=AXQID* and returns QID* to I. M adds 〈IDl, QID*, SFULLID*, SSEMID*=⊥, SUSERID*, sFULLID*=⊥, sSEMID*, sUSERID*=⊥, rFULLID*=⊥, rSEMID*=⊥, rUSERID*=⊥, RFULLID*, RSEMID*=⊥, RUSERID*=⊥〉 to LH.(ii)
Otherwise, fori≠l, M chooses QIDi←$Zq* and returns QIDi. It then chooses rFULLIDi,rSEMIDi,sSEMIDi←$Zq*, calculates sFULLIDi=rFULLIDi+xQ, and sets rUSERIDi=rFULLIDi-rSEMIDi and sUSERIDi=sFULLIDi-sSEMIDi. M adds 〈IDi, QIDi, SFULLIDi, SSEMIDi, SUSERIDi, sFULLIDi, sSEMIDi, sUSERIDi, rFULLIDi, rSEMIDi, rUSERIDi, RFULLIDi, RSEMIDi, RUSERIDi〉 to LH.(3)
SEM-Extract (IDi). If IDi=ID* andUSER-Extract (ID*) has been queried before, M aborts. If IDi=ID*, butUSER-Extract (ID*) has not been queried before, M will choose rSEMID*,sSEMID*←$Zq and sets RSEMID*=grSEMID* and SSEMID*=gsSEMID*. M also sets SUSERID*=SFULLID*/SSEMID* and RUSERID*=RFULLID*/RSEMID*, saves these values in LH, and returns them to I. These values will be used in the event of anIdentification query later on. Otherwise for all other IDi≠ID*, M just retrieves 〈sSEMIDi,RSEMIDi〉 in LH and returns it to I.(4)
USER-Extract (IDi). If IDi=ID* andSEM-Extract (ID*) has been queried before, M aborts. If IDi=ID*, butSEM-Extract (ID*) has not been queried before, M will choose rUSERID*,sUSERID*←$Zq and sets RUSERID*=grUSERID* and SUSERID*=gsUSERID*. M also sets SSEMID*=SFULLID*/SUSERID* and RSEMID*=RFULLID*/RUSERID*, saves these values in LH, and returns them to I. These values will be used in the event of anIdentification query later on. Otherwise for all other IDi≠ID*, M just retrieves 〈sUSERIDi,RUSERIDi〉 in LH and returns it to I.(5)
Identification (IDj, session). I will act as the cheating verifier to learn information from valid conversation transcripts from M. If IDj≠ID*, M just retrieves IDj’s entry in LH and runs the identification protocol for either the SEM’s interactions, the user’s interactions, or both combined as in the protocol.Otherwise, forIDj=ID*, M then creates a full valid transcript for each mth query by picking zm,FULLID*,zm,SEMID*,cm,ID*←$Zq. M retrieves SFULLID*, RFULLID* and sets Ym,FULLID*=gzm,FULLID*SFULLID*-cm,ID*. Additionally, M chooses zm,SEMID*←$Zq, calculates zm,USERID*=zm,FULLID*-zm,SEMID*, and retrieves SSEMID*, RSEMID* and SUSERID*, RUSERID* from LH as well. M then sets Ym,SEMID*=gzm,SEMID*SSEMID*cm,ID* and Ym,USERID*=gzm,USERID*SUSERID*cm,ID*. M tags the session with session=m. If I queries
(i)
SEM-Identification (ID*, m), M will return 〈Ym,SEMID*,SSEMID*,RSEMID*,cm,ID*,zm,SEMID*〉;(ii)
User-Identification (ID*, m), M will return 〈Ym,USERID*, SUSERID*, RUSERID*, cm,ID*zm,USERID*〉;(iii)
Full-Identification (ID*, m), M will return 〈Ym,FULLID*, SFULLID*, RFULLID*, cm,ID*zm,FULLID*〉.If no session is specified for the query,M just returns the next session in sequence. One can see thatSEM-Identification  (ID*, m) andUser-Identification  (ID*,m) can be combined to create a full and valid transcript on session m:
(21)Ym,FULLID*RFULLID*cm,ID*XH(ID*)cm,ID*=Ym,USERID*Ym,SEMID*RUSERID*cm,ID*RSEMID*cm,ID*×XH(ID*)cm,ID*=(gzm,USERID*SUSERID*-cm,ID*gzm,SEMID*)SSEMID*-cm,ID*×(RUSERID*RSEMID*)cm,ID*XH(ID*)cm,ID*=gzm,USERID*gzm,SEMID*(SUSERID*SSEMID*)-cm,ID*×(RUSERID*RSEMID*)cm,ID*XH(ID*)cm,ID*=gzm,USERID*gzm,SEMID*(SFULLID*SSEMID*SSEMID*)-cm,ID*×(RFULLID*RSEMID*RSEMID*)cm,ID*XH(ID*)cm,ID*=gzm,FULLID*A-cm,ID*Acm,ID*X-H(ID*)cm,ID*×XH(ID*)cm,ID*=gzm,FULLID*.Eventually, I stops Phase 1 and outputs the challenge ID, ID* on which it wishes to be challenged on. M checks if ID=IDl from LH and aborts if not. Otherwise, M runs I now as a cheating prover on ID* by obtaining its commitment, YFULLID*, SFULLID*, RFULLID* selecting a challenge c1←$Zq* and obtaining the response zFULLID*,1 from I. M then resets I to the step whereby I just sent YFULLID*, SFULLID*, RFULLID*, selects a second challenge c2←$Zq*, and receives zFULLID*,2 as response. M is then able to extract the full user private key as follows:
(22)zFULLID*,1-zFULLID*,2c1-c2=yFULLID*+c1a-yFULLID*+c2ac1-c2=(c1-c2)ac1-c2=a.M outputs a as the discrete log solution.
It remains to calculate the probability ofM solving the CDH problem and winning the game. The probability of M successfully extracting two valid conversation transcripts from I is bounded by (εSMIBI-(1/q))2 as given by the reset lemma [20]:
(23)Pr[MwinsDL]=Pr[Mcomputesa⋀¬abort]=Pr[Mcomputesa∣¬abort]Pr[¬abort]εDL≥(εSMIBI-1q)2Pr[¬abort].
Finally, let δ be the probability that I issues aSEM-Extract and aUSER-Extract query on ID* and that I makes a total of qSMIBI of such queries. The probability of M answering all the extraction queries is δIq. In Phase 2, the probability of M not aborting is if I outputs the challenge identity ID* that was not queried before. This is given by the probability 1-δ. Compiling them, the probability of M not aborting is δqSMIBI(1-δ). This value is maximised at δopt=1-(1/(qSMIBI+1)). Using δopt, The probability that M does not abort is at least 1/e(qSMIBI+1) because the value (1-(1/(qSMIBI+1)))qSMIBI approaches 1/e for large qSMIBI. Therefore, the advantage of M, εDL, and the bound of the simulation is given as follows:
(24)εDL≥(εSMIBI-1q)21e(qSMIBI+1)εDLe(qSMIBI+1)≥(εSMIBI-1q)2εSMIBI≤εDLe(qSMIBI+1)+1q.


## 4.2. Security Analysis: Impersonation under Active/Concurrent Attack

Theorem 8.
The BNN-SM-IBI scheme is(tSMIBI,qSMIBI,εSMIBI)-secure against impersonation under active/concurrent attacks in the random oracle if the OMCDH Problem is (tOMCDH,qOMCDH,εOMCDH)-hard where
(25)εSMIBI≤εOMCDHe(qSMIBI+1)+1q.Proof.
Assume the BNN-SM-IBI scheme is(tSMIBI,qSMIBI,εSMIBI)-breakable; then a simulator M that (tOMCDH,qOMCDH,εOMCDH)-breaks the OMCDH Problem can be shown. M takes in input (g,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 anySEM-Extract,User-Extract,SEM-Identification,User-Identification, andFull-Identification queries are preceded by aCreate-User query. To avoid collision and consistently respond to these queries, M maintains a list LH=〈IDi,QIDi, SFULLIDi, SSEMIDi, SUSERIDi, sFULLIDi, sSEMIDi, sUSERIDi, rFULLIDi, rSEMIDi, rUSERIDi, RFULLIDi, RSEMIDi,RUSERIDi〉 which is initially empty. The following shows how M simulates the environment and oracle queries for I. (1)
Setup. M sets the system parameters asmpk=〈G,q,g,X=gx,H〉 and keeps master private key x secret. It sendsmpk to I.(2)
Create-User (IDi). M chooses l∈{1,…,qH} randomly and lets IDl=ID* at this point. Whenever I makes a H query on IDi, consider the following.
(i)
Ifi=l, M chooses QID*←$Zq, queries CHALL for W0, and sets SFULLID*=W0 and RFULLID*=W0XQID*. M returns QID* to I. M adds LH=〈IDl, QID*, SFULLID*, SSEMID*=⊥, SUSERID*=⊥, sFULLID*=⊥, sSEMID*=⊥, sUSERID*=⊥, rFULLID*=⊥, rSEMID*=⊥, rUSERID*=⊥, RFULLID*, RSEMID*=⊥, RUSERID*=⊥〉 to LH.(ii)
Otherwise, fori≠l, M chooses QIDi←$Zq* and returns QIDi. It then chooses rFULLIDi,rSEMIDi,sSEMIDi←$Zq*, calculates sFULLIDi=rFULLIDi+xQ, and sets rUSERIDi=rFULLIDi-rSEMIDi and sUSERIDi=sFULLIDi-sSEMIDi. M adds LH=〈IDi,QIDi, SFULLIDi, SSEMIDi, SUSERIDi, sFULLIDi, sSEMIDi, sUSERIDi, rFULLIDi, rSEMIDi, rUSERIDi, RFULLIDi, RSEMIDi, RUSERIDi〉 to LH.(3)
SEM-Extract (IDi). If IDi=ID* andUSER-Extract (ID*) has been queried before, M aborts. If IDi=ID*, butUSER-Extract (ID*) has not been queried before, M will choose rSEMID*,sSEMID*←$Zq and sets RSEMID*=grSEMID* and SSEMID*=gsSEMID*. M also sets SUSERID*=SFULLID*/SSEMID* and RUSERID*=RFULLID*/RSEMID*, saves these values in LH, and returns them to I. These values will be used in the event of anIdentification query later on. Otherwise for all other IDi≠ID*, M just retrieves 〈sSEMIDi,RSEMIDi〉 in LH and returns it to I.(4)
USER-Extract (IDi). If IDi=ID* andSEM-Extract (ID*) has been queried before, M aborts. If IDi=ID*, butSEM-Extract (ID*) has not been queried before, M will choose rUSERID*,sUSERID*←$Zq and sets RUSERID*=grUSERID* and SUSERID*=gsUSERID*. M also sets SSEMID*=SFULLID*/SUSERID* and RSEMID*=RFULLID*/RUSERID*, saves these values in LH, and returns them to I. These values will be used in the event of an Identification query later on. Otherwise for all other IDi≠ID*, M just retrieves 〈sUSERIDi,RUSERIDi〉 in LH and returns it to I.(5)
Identification (IDj, session). I will act as the cheating verifier to learn information from valid conversations from M. If IDj≠ID*, M just retrieves IDj’s entry in LH and runs the identification protocol for either the SEM’s interactions, the user’s interactions, or both combined as in the protocol.
Otherwise, forIDi=ID*, M then creates a full valid conversation for each mth query by querying CHALL for Wm and setting Ym,FULLID*=Wm. M also retrieves. Additionally, M chooses Ym,SEMIDj←$G and sets Ym,UserIDj=Wm/Ym,SEMIDj. M also retrieves Sm,FULLIDj, Sm,SEMIDj, Sm,USERIDj, Rm,FULLIDj, Rm,SEMIDj, and Rm,USERIDj from LH. Upon receiving cm,IDj from I, M will query zm,FULLIDj=DLOG(WmW0cm,IDj), selects zm,SEMIDj←$Zq, and sets zm,USERIDj=zm,FULLIDj-zm,SEMIDj. M tags the session with session=m.
(a)
IfI queriesSEM-Identification (IDj, m), M will commit Ym,SEMIDj, SSEMIDj, RSEMIDj and respond with zm,SEMIDj upon receiving cm,IDj.
(b)
IfI queriesUser-Identification (IDj, m), M will commit Ym,USERIDj, SUSERIDj, RUSERIDj and respond with zm,USERIDj upon receiving cm,IDj.
(c)
IfI queriesFull-Identification (IDj,m), M will commit Ym,FULLIDj, SFULLIDj, RFULLIDj and respond with zm,FULLIDj upon receiving cm,IDj.
If no session is specified for the query,M just returns the next session in sequence. One can see thatSEM-Identification (IDj, m) andUser-Identification (ID*, m) can be combined to create a full and valid conversation on session m:
(26)Ym,FULLIDjRFULLIDjcm,IDjXH(IDj)cm,IDj=Ym,USERIDjYm,SEMIDjRUSERIDjcm,IDjRSEMIDjcm,IDjXH(IDj)cm,IDj=WmYm,SEMIDjYm,SEMIDj(W0X-H(ID)RSEMIDj)cm,IDj×RSEMIDjcm,IDjXH(IDj)cm,IDj=Wm(W0cm,IDj)X-H(ID)cm,IDjXH(IDj)cm,IDj=Wm(W0cm,IDj)=gDLOG(Wm(W0cm,IDj)=gzm,FULLIDj.Eventually, I stops Phase 1 and outputs the challenge ID, ID* on which it wishes to be challenged on. M checks if ID*=IDl from LH and aborts if not. Otherwise, M runs I now as a cheating prover on ID*. M runs by obtaining its commitment, YFULLID*, SFULLID*, RFULLID*, selects a challenge c1←$Zq*, and obtains the response zFULLID*,1 from I. M then resets I to the step whereby I just sent YFULLID*, SFULLID*, RFULLID*, selects a second challenge c2←$Zq*, and receives zFULLID*,2 as response. M is then able to extract the full user private key as follows:
(27)zFULLID*,1-zFULLID*,2c1-c2=yFULLID*+c1w0-yFULLID*+c2w0c1-c2=(c1-c2)w0c1-c2=w0.M outputs w0 as the initial discrete log challenge solution.
M proceeds to calculate the solutions to the other challenges as follows:
(28)zm,FULLIDj-w0cm,IDj=DLOG(WmW0cm,IDj)-w0cm,IDj=[wm+w0cm,IDj]-w0cm,IDj=wm.
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 inZϕ(N), multiplication operations in Zϕ(N) and ZN*, and exponentiation operations in ZN*. Overall, the operational costs of the GQ-SM-IBI scheme are given in Table 1.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ϕ(N), M1: multiplication in Zϕ(N), M2: multiplication in ZN*, and E: exponentiation in ZN*.We also provide the communication costs of the GQ-SM-IBI scheme in Table2.Table 2
Communication costs between algorithms for the GQ-SM-IBI scheme.
Algorithms
Bitstring|ID|
Elements of|e-1|
Elements inZN*
TA-User (Extract)
1
0
1
TA-SEM (Extract)
1
0
1
SEM-User (Identification)
1
1
2
User-Verifier (Identification)
1
1
2As for the BNN-SM-IBI scheme, we measure the operational costs in terms of group operational costs of addition moduloq, 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.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.We also provide the communication costs of the BNN-SM-IBI scheme in Table4.Table 4
Communication costs between algorithms for the BNN-SM-IBI scheme.
Algorithms
Bitstring
Elements inG1
Elements inZq
TA-User (Extract)
1
1
1
TA-SEM (Extract)
1
1
1
SEM-User (Identification)
1
3
2
User-Verifier (Identification)
1
3
2However, 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-SM-IBI 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 Table5.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,987From 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.



---

*Source: 170906-2014-05-26.xml*