# Identity-Based Identification Scheme without Trusted Party against Concurrent Attacks

Authors: Fei Tang; Jiali Bao; Yonghong Huang; Dong Huang; Fuqun Wang
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Identification schemes support that a prover who holding a secret key to prove itself to any verifier who holding the corresponding public key. In traditional identity-based identification schemes, there is a key generation center to generate all users’ secret keys. This means that the key generation center knows all users’ secret key, which brings the key escrow problem. To resolve this problem, in this work, we define the model of identity-based identification without a trusted party. Then, we propose a multi-authority identity-based identification scheme based on bilinear pairing. Furthermore, we prove the security of the proposed scheme in the random oracle model against impersonation under passive and concurrent attacks. Finally, we give an application of the proposed identity-based identification scheme to blockchain.


---

## Body

## 1. Introduction

In identification schemes, the user, playing the role of a prover, can identity itself to any verifier in a protocol in which the verifier begins by holding only the corresponding public key. One of the purposes of identification is to promote access control to resources, when an access privilege is linked to a particular identity.There are a lot of research studies on identification schemes. The fundamental work of identification scheme [1] was proposed by Fiat and Shamir, named FS scheme. The authors described an identification scheme in which any user can prove its identity to other users. They combined zero-knowledge interactive proofs with identity-based schemes. The key of FS scheme is to assume that there is a trusted center, such as computer center, government, and credit card company. This center gives smart cards to users after checking their physical identities. The FS scheme is based on the factorization problem. Feige et al. [2] proposed another identification scheme, named FFS scheme, which is also based on the factorization problem. Okamoto [3] presented a three-move interactive identification scheme and proved that the scheme has the same security as the discrete logarithm problem. Schnorr’s scheme [4] is one of the famous identification schemes. The GQ scheme which was proposed by Guillou and Quisquater [5] is based on the RSA-inversion problem. The formal proof of security for GQ and Schnorr schemes was realized by Bellare and Palacio [6]. They provided a proof for GQ scheme based on RSA-inversion assumption and a proof for Schnorr scheme based on one more discrete logarithm (OMDL) assumption. These two schemes are provably secure against impersonation under active and concurrent attacks. Girault [7] gave a modification of Schnorr’s identification scheme, in which each user can select his own secret key but the center can not get it from the public key. Kim and Kim [8] proposed a new identification scheme based on bilinear Diffie-Hellman problem, which is secure against passive and active attacks.In traditional identification schemes, we need a certificate authority (CA) to authenticate prover’s public key in the setting of public key infrastructure (PKI). Shamir [9] introduced the notion of identity-based cryptography (IBC). The purpose of IBC is to simplify the management of certificates in PKI. Shamir pointed out that the key generation center (KGC) generates the corresponding secret key with the public identity and sends it to the user when he first joins in the system. Each user has a unique and meaningful identity as the public key and thus avoids the complicated certificate management problem. Then, Boneh and Franklin proposed an identity-based encryption (IBE) scheme [10], which is based on bilinear pairing. Since then, a large number of identity-based identification schemes have been proposed by using bilinear pairings.The formal definition of identity-based identification (IBI) scheme was introduced by Kurosawa and Heng [11]. They constructed a transformation from any standard digital signature scheme to an IBI scheme. Then, in [12], they proposed two IBI schemes, one of which is provably secure against impersonation passive attacks, and the other is provably secure against impersonation active and concurrent attacks. The security model of IBI [11, 13] can be divided into three types, called security against impersonation under passive attacks, active attacks, and concurrent attacks, respectively. Then, Chin et al. [14] presented a provably secure IBI scheme in the standard model. The scheme of [14] is secure against impersonation under active and concurrent attacks based on one more computational Diffie-Hellman assumption. Barapatre and Rangan [15] proposed a general framework of IBI based on the identity-based key encapsulation mechanism. The scheme of [15] is secure against impersonation under active and concurrent attacks based on the q-bilinear Diffie-Hellman inversion assumption.It is well known that, the IBI schemes suffer the key escrow problem, which means that we need a trusted KGC to generate all users’ key. In order to solve this problem, in this work, we consider the IBI scheme without a trusted party. The main contributions of this work can be summarized as follows:(1)
We give the formal definition of IBI scheme in the multi-authority setting. In our definition, there aren authorities. The generation of users’ secret key needs at least t authorities.(2)
We construct an IBI scheme with multiple authorities based on the BLS signature scheme [16]. The security of the proposed scheme is provably against impersonation under passive and concurrent attacks in the random oracle model.(3)
We consider the applications of the proposed multi-authority IBI scheme. We show that the scheme can be used to identification in blockchain.The rest of this paper is organized as follows. In Section2, we give the definitions of bilinear pairing and complexity assumptions. We also present the definition and security models of the IBI scheme in Section 2. Section 3 presents the details of IBI scheme. In Section 4, we prove the security of the proposed scheme. In Section 5, we describe the applications of the multi-authority IBI scheme in blockchain. Finally, we make a conclusion about this paper in section 6.


## 2. Preliminaries

In this section, we describe the relevant definitions and security models.


### 2.1. Bilinear Map and Complexity Assumptions

In the construction of our identity-based identification scheme, we use bilinear pairing as the basic tool. Therefore, we briefly introduce the concept of bilinear pairing.LetG and GT be two cyclic multiplicative groups, where G is generated by an element g, i.e., G=g. Groups G and GT have same prime order p. We say that e:G×G⟶GT is an admissible bilinear pairing if it satisfies the following properties:(1)
Bilinearity:ega,gb=eg,gab for all a,b∈ℤp.(2)
Nondegeneracy: there existsgc,gd∈G, for c,d∈ℤp, such that egc,gd≠1GT, where 1GT represents the identity element of the group GT.(3)
Computability: there is an efficient algorithm to computeega,gb for all a,b∈ℤp.The security of our scheme relies on the following two difficult problems: Computational Diffie-Hellman (CDH) Problem and One More Discrete Logarithm (OMDL) Problem.Definition 1 (CDH).
Giveng,ga,gb for some a,b∈ℤp, it is hard to compute gab.Definition 2 (OMDL) (see [17]).
The definition of the OMDL problem is defined by the following experimentExpomdlk.(i)
Training: A polynomial-time adversaryA makes n queries to the challenge oracle ℬ⋅ and m queries to the Discrete-Logarithm (DL) oracle Dℒp,g⋅. Let s1,s2,…,sn⟵Aℬ⋅,Dℒp,g⋅p,g,e,G,GT.(ii)
Output: Ifgs1=h1∧⋯∧gsn=hn, where h1,…,hn are random points in G output by the challenge oracle C⋅, and n<m, where n denotes the number of queries to the DL oracle, then return 1. Otherwise, return 0.
We define the advantage of adversaryA as AdvAomdlk=PrExpomdlk=1. We say that OMDL problem is hard if AdvAomdlk is negligible in k for any polynomial-time adversary.


### 2.2. Definition of Multi-authority IBI

An identity-based identification (IBI) schemeℐℬℐ=S,K,P,V is specified by four probabilistic polynomial-time algorithms, called Setup, Key-generation, Proving, and Verification, respectively. On input security parameter k, S returns system public parameters and the master secret key. K is executed by the key generation center to generate a secret key corresponding to a given public identity. P and V are interactive algorithms that implement the prover and verifier. We call P,V an identification protocol.As far as we know, there is no IBI scheme in the setting of multiple authorities. The standard IBI schemes have a key generation center to produce all users’ secret key. Therefore, it is well known that identity-based cryptographic schemes have the key escrow problem. This work defines the notion of IBI scheme with multiple authorities. In our scheme, there has one more algorithm, Authority Setup, to generate all authorities’ master secret keys. The notion of IBI scheme with multiple authorities is consists of the following algorithms:(i)
System-setup: This algorithm takes as input the security parameterk and outputs the system public parameter params.(ii)
Authority-setup: The authority setup algorithm is interactively executed by all authorities. On input the system public parameterparams and identities P1,…,Pn, output their master secret keys SK1,…,SKn.(iii)
Key-generation: Userid makes queries to at least t authorities, Pi1,…,Pit, where ij∈1,n for key generation. Each authority Pij takes as inputs the system public parameter params, master secret key SKij, and user’s identity id and outputs user its partial key pskid,ij. Finally, user id can compute the secret key skid by itself.(iv)
Identification:P receives as inputs params, id, and skid and V receives as inputs params, and id), where skid is the secret key corresponding to the public identity id. After an interactive execution of P,V, V outputs 1 (accept) or 0 (reject).(v)
Correctness: A legitimateP should always be accepted, i.e., PKmsk,id,Vparams,id⟶1.


### 2.3. Security Models

The accepted framework of security concepts for identification schemes was proposed by Feige et al. [2]. Then, the security definition for IBI scheme was presented in [11, 13]. This is an extension of the framework of [2]; that is, the three concepts of security for standard identification schemes are extended to IBI. Usually, we consider adversary goals, adversary capabilities or attacks. The adversary goal is impersonation that if the adversary interacts with the verifier playing the role of prover with identity id∗ and can persuade the verifier to accept with a nonnegligible probability. To achieve this goal, the adversary can carry out various attacks. We consider three kinds of attacks, namely, passive attacks [2], active attacks [2], and concurrent attacks [6]. These attacks should take place and complete before the impersonation attempt.Passive attacks are the weakest one of the above three kinds of attacks for IBI schemes. In passive attacks, the adversary does not interact with the prover. The adversary just eavesdrops and obtains a transcript of a conversation between the prover and verifier. The definition of passive attacks of IBI schemes is defined by the following game which is executed by an adversaryA=V^,P^ and a challenger C.Definition 3 (Security against Impersonation under Passive Attacks).
LetA=V^,P^ be an impersonation adversary with passive attacks (imp-pa).(i)
System-setup: The challengerC runs the system setup algorithm on input a security parameter k to generate system public parameters params. Then, C returns params to A.(ii)
Authority-setup: The challengerC runs the authority setup algorithm to generate master secret keys SK1,SK2,…,SKn for all authorities P1,P2,…,Pn.(iii)
Queries:A can issues some queries as follows:(1)
Master secret key queries:A issues a request for some authorities Pi for their master secret key. For such a request, C transmits SKi to A.(2)
Key generation queries:A issues some key generation queries idi. C then returns the corresponding private key skidi as the answer.(3)
Transcript queries:A can issue some transcript queries on id. In passive attacks, C returns the transcripts T which denotes the conversations between the valid prover id and other verifiers.(iv)
Challenge:A chooses a challenge identity id∗. Then, A plays the role of a cheating prover, trying to convince any verifier.
We define that adversaryA succeeds in impersonating if it can make the verifier accepts. The advantage of an imp-pa adversary A denoted by ADVℐℬℐ,Aimp−pak. We say that IBI scheme is secure against impersonation under passive attacks if Advℐℬℐ,Aimp−pak is negligible in k for any imp-pa adversary.
Different from passive attacks, in the active and concurrent attacks, the adversary first plays the role of the cheating verifier, interacting with the honest prover multiple times, trying to extract some useful information. Then it plays role of cheating prover, interacting with the honest verifier, trying to persuade the honest verifier to accept. It is easy to see that the security notions of active and concurrent attacks are stronger than the notion of passive attacks. Generally, we pursue stronger security notion for crytographic schemes, such as [18, 19].
Active attacks are a special case of concurrent attacks. In the active attacks, the next round of attack is carried out after one attack is completed, that is, the interaction is one by one. In the concurrent attacks, however, the adversary can interact with multiple different prover “replicas” concurrently. The replicas all have the same secret key but are initialized with independent coins and maintain their own state. Apparently, security against impersonation under concurrent attack implies security against impersonation under active attack.Difinition 4 (Security against Impersonation under Concurrent Attacks).
An impersonation under concurrent attacks (imp-ca) adversaryA=V^,P^ is a pair of randomized polynomial-time algorithms, which denotes the cheating verifier and the cheating prover, respectively. The definition of the concurrent attacks of IBI schemes is defined by the following game which is played by a concurrent adversary and challenger C.(i)
System-setup: The challengerC runs the system setup algorithm on input k to generate system public parameters params. Then, C sends params to different replicas of prover P and adversary A=V^,P^.(ii)
Authority-setup: The challengerC runs the authority setup algorithm to generate master secret keys SK1,SK2,…,SKn for all authorities P1,P2,…,Pn.(iii)
Queries:A can issues some queries as follows:(1)
Master secret key queries:A issues a request for some authorities Pi for their master secret key. For such a request, C transmits SKi to A.(2)
Key generation queries:A issues some key generation queries idi. C then returns the corresponding private key skidi as the answer.(3)
Identification training:A first plays the role of a cheating verifier to execute the identification protocols with the honest prover id. In concurrent attacks, the adversary A can issue the identification protocol at any time regardless of whether the last protocol is end or not. The difference between concurrent attack and active attack is that the active adversary only can issue a new identification protocol after the end of the last protocol. We denote the transcript of i-th protocol as Ti.(iv)
Challenge: Finally, adversary plays the role of a cheating proverP^ to execute the identification protocol with a valid verifier V to try to convince that he is the valid prover.
We define that adversaryA succeeds in impersonating if it can make the verifier accepts. The advantage of an imp-ca adversary A denoted by Advℐℬℐ,Aimp−cak. We say that IBI scheme is secure against impersonation under concurrent attacks if Advℐℬℐ,Aimp−cak is negligible in k for any imp-ca adversary.


## 2.1. Bilinear Map and Complexity Assumptions

In the construction of our identity-based identification scheme, we use bilinear pairing as the basic tool. Therefore, we briefly introduce the concept of bilinear pairing.LetG and GT be two cyclic multiplicative groups, where G is generated by an element g, i.e., G=g. Groups G and GT have same prime order p. We say that e:G×G⟶GT is an admissible bilinear pairing if it satisfies the following properties:(1)
Bilinearity:ega,gb=eg,gab for all a,b∈ℤp.(2)
Nondegeneracy: there existsgc,gd∈G, for c,d∈ℤp, such that egc,gd≠1GT, where 1GT represents the identity element of the group GT.(3)
Computability: there is an efficient algorithm to computeega,gb for all a,b∈ℤp.The security of our scheme relies on the following two difficult problems: Computational Diffie-Hellman (CDH) Problem and One More Discrete Logarithm (OMDL) Problem.Definition 1 (CDH).
Giveng,ga,gb for some a,b∈ℤp, it is hard to compute gab.Definition 2 (OMDL) (see [17]).
The definition of the OMDL problem is defined by the following experimentExpomdlk.(i)
Training: A polynomial-time adversaryA makes n queries to the challenge oracle ℬ⋅ and m queries to the Discrete-Logarithm (DL) oracle Dℒp,g⋅. Let s1,s2,…,sn⟵Aℬ⋅,Dℒp,g⋅p,g,e,G,GT.(ii)
Output: Ifgs1=h1∧⋯∧gsn=hn, where h1,…,hn are random points in G output by the challenge oracle C⋅, and n<m, where n denotes the number of queries to the DL oracle, then return 1. Otherwise, return 0.
We define the advantage of adversaryA as AdvAomdlk=PrExpomdlk=1. We say that OMDL problem is hard if AdvAomdlk is negligible in k for any polynomial-time adversary.


## 2.2. Definition of Multi-authority IBI

An identity-based identification (IBI) schemeℐℬℐ=S,K,P,V is specified by four probabilistic polynomial-time algorithms, called Setup, Key-generation, Proving, and Verification, respectively. On input security parameter k, S returns system public parameters and the master secret key. K is executed by the key generation center to generate a secret key corresponding to a given public identity. P and V are interactive algorithms that implement the prover and verifier. We call P,V an identification protocol.As far as we know, there is no IBI scheme in the setting of multiple authorities. The standard IBI schemes have a key generation center to produce all users’ secret key. Therefore, it is well known that identity-based cryptographic schemes have the key escrow problem. This work defines the notion of IBI scheme with multiple authorities. In our scheme, there has one more algorithm, Authority Setup, to generate all authorities’ master secret keys. The notion of IBI scheme with multiple authorities is consists of the following algorithms:(i)
System-setup: This algorithm takes as input the security parameterk and outputs the system public parameter params.(ii)
Authority-setup: The authority setup algorithm is interactively executed by all authorities. On input the system public parameterparams and identities P1,…,Pn, output their master secret keys SK1,…,SKn.(iii)
Key-generation: Userid makes queries to at least t authorities, Pi1,…,Pit, where ij∈1,n for key generation. Each authority Pij takes as inputs the system public parameter params, master secret key SKij, and user’s identity id and outputs user its partial key pskid,ij. Finally, user id can compute the secret key skid by itself.(iv)
Identification:P receives as inputs params, id, and skid and V receives as inputs params, and id), where skid is the secret key corresponding to the public identity id. After an interactive execution of P,V, V outputs 1 (accept) or 0 (reject).(v)
Correctness: A legitimateP should always be accepted, i.e., PKmsk,id,Vparams,id⟶1.


## 2.3. Security Models

The accepted framework of security concepts for identification schemes was proposed by Feige et al. [2]. Then, the security definition for IBI scheme was presented in [11, 13]. This is an extension of the framework of [2]; that is, the three concepts of security for standard identification schemes are extended to IBI. Usually, we consider adversary goals, adversary capabilities or attacks. The adversary goal is impersonation that if the adversary interacts with the verifier playing the role of prover with identity id∗ and can persuade the verifier to accept with a nonnegligible probability. To achieve this goal, the adversary can carry out various attacks. We consider three kinds of attacks, namely, passive attacks [2], active attacks [2], and concurrent attacks [6]. These attacks should take place and complete before the impersonation attempt.Passive attacks are the weakest one of the above three kinds of attacks for IBI schemes. In passive attacks, the adversary does not interact with the prover. The adversary just eavesdrops and obtains a transcript of a conversation between the prover and verifier. The definition of passive attacks of IBI schemes is defined by the following game which is executed by an adversaryA=V^,P^ and a challenger C.Definition 3 (Security against Impersonation under Passive Attacks).
LetA=V^,P^ be an impersonation adversary with passive attacks (imp-pa).(i)
System-setup: The challengerC runs the system setup algorithm on input a security parameter k to generate system public parameters params. Then, C returns params to A.(ii)
Authority-setup: The challengerC runs the authority setup algorithm to generate master secret keys SK1,SK2,…,SKn for all authorities P1,P2,…,Pn.(iii)
Queries:A can issues some queries as follows:(1)
Master secret key queries:A issues a request for some authorities Pi for their master secret key. For such a request, C transmits SKi to A.(2)
Key generation queries:A issues some key generation queries idi. C then returns the corresponding private key skidi as the answer.(3)
Transcript queries:A can issue some transcript queries on id. In passive attacks, C returns the transcripts T which denotes the conversations between the valid prover id and other verifiers.(iv)
Challenge:A chooses a challenge identity id∗. Then, A plays the role of a cheating prover, trying to convince any verifier.
We define that adversaryA succeeds in impersonating if it can make the verifier accepts. The advantage of an imp-pa adversary A denoted by ADVℐℬℐ,Aimp−pak. We say that IBI scheme is secure against impersonation under passive attacks if Advℐℬℐ,Aimp−pak is negligible in k for any imp-pa adversary.
Different from passive attacks, in the active and concurrent attacks, the adversary first plays the role of the cheating verifier, interacting with the honest prover multiple times, trying to extract some useful information. Then it plays role of cheating prover, interacting with the honest verifier, trying to persuade the honest verifier to accept. It is easy to see that the security notions of active and concurrent attacks are stronger than the notion of passive attacks. Generally, we pursue stronger security notion for crytographic schemes, such as [18, 19].
Active attacks are a special case of concurrent attacks. In the active attacks, the next round of attack is carried out after one attack is completed, that is, the interaction is one by one. In the concurrent attacks, however, the adversary can interact with multiple different prover “replicas” concurrently. The replicas all have the same secret key but are initialized with independent coins and maintain their own state. Apparently, security against impersonation under concurrent attack implies security against impersonation under active attack.Difinition 4 (Security against Impersonation under Concurrent Attacks).
An impersonation under concurrent attacks (imp-ca) adversaryA=V^,P^ is a pair of randomized polynomial-time algorithms, which denotes the cheating verifier and the cheating prover, respectively. The definition of the concurrent attacks of IBI schemes is defined by the following game which is played by a concurrent adversary and challenger C.(i)
System-setup: The challengerC runs the system setup algorithm on input k to generate system public parameters params. Then, C sends params to different replicas of prover P and adversary A=V^,P^.(ii)
Authority-setup: The challengerC runs the authority setup algorithm to generate master secret keys SK1,SK2,…,SKn for all authorities P1,P2,…,Pn.(iii)
Queries:A can issues some queries as follows:(1)
Master secret key queries:A issues a request for some authorities Pi for their master secret key. For such a request, C transmits SKi to A.(2)
Key generation queries:A issues some key generation queries idi. C then returns the corresponding private key skidi as the answer.(3)
Identification training:A first plays the role of a cheating verifier to execute the identification protocols with the honest prover id. In concurrent attacks, the adversary A can issue the identification protocol at any time regardless of whether the last protocol is end or not. The difference between concurrent attack and active attack is that the active adversary only can issue a new identification protocol after the end of the last protocol. We denote the transcript of i-th protocol as Ti.(iv)
Challenge: Finally, adversary plays the role of a cheating proverP^ to execute the identification protocol with a valid verifier V to try to convince that he is the valid prover.
We define that adversaryA succeeds in impersonating if it can make the verifier accepts. The advantage of an imp-ca adversary A denoted by Advℐℬℐ,Aimp−cak. We say that IBI scheme is secure against impersonation under concurrent attacks if Advℐℬℐ,Aimp−cak is negligible in k for any imp-ca adversary.


## 3. The Proposed Scheme

In this section, we give our multi-authority IBI scheme without a trusted party. Generally speaking, in traditional IBI schemes, there is a trusted party for the generation and distribution of user secret keys. To address the problem of no trusted party, we utilize distributed key generation (DKG) protocol to generate user secret keys. DKG was proposed by Gennaro et al. [20]. The core idea of DKG is t,n threshold secret sharing. The concept of secret sharing was introduced by Shamir [21]. Secret sharing is used to share a secret among a group of participants, each of whom has partial information about secret. t,n threshold secret sharing means that at least t participate among n participants can reconstructed the secret value.In the DKG protocol, the participants jointly choose and generate a random secret shares. Each participant Pi chooses a random share si, and then a random secret share s can be recovered by at least t participants. At the end of the protocol, the public key can be defined as y=gs. There is no trusted party, who owns the secret value s in the secret sharing scheme. The secret value s can only be reconstructed by the cooperation of at least t participants.The construction of our scheme refers to two article by Lin et al. [22] and Tang et al. [23]. Lin et al. proposed a threshold multi-authority attribute-based encryption scheme. In their scheme, they use t,n threshold secret sharing to get the system secret key a0. Each authority only has the share ai0 about secret a0. Therefore, the system secret key a0 is unknown to any authority. Tang et al. proposed an efficient multi-authority authentication scheme for electronic health records system based on blockchain.


### 3.1. Construction

The construction of the scheme is outlined below:(i)
System-setup: Given the security parameterk as input, generates prime p randomly to establish the system parameters. First of all, it chooses two multiplication cycles G and GT with some prime order p, and a bilinear map e:G×G⟶GT. Let g be a generator of the group G. Next, it chooses a cryptographic hash function H:0,1∗⟶G. The system parameters are params=p,g,e,G,GT,H,n,t, where n is the number of authorities in the system, and t is the threshold value which denotes the number of authorities to generate secret key for users.(ii)
Authority-setup: In this algorithm, all authorities take public parametersparams and their identities P1,…,Pn as inputs and establish their master secret keys SK1,…,SKn. It consists of the following two phases:(a)
Phase 1 (generation of the master secret key): Each authority generates the public key and private key, as well as the master public key of the system.(1)
Each authorityPi selects at random a polynomial ℱix∈ℤp∗ of degree t−1:(1)ℱix=∑j=0t−1aijxj.(2)
Pi calculates Aik=gaik for k=0,1,…,t−1 and then broadcasts Aik.(3)
Pi computes secret value yij=ℱiPj for j=1,2,…,n, and then sends yij secretly to authority Pj for j≠i.(4)
Pj verifies the equation gyij=∏k=0t−1AikPjk holds or not. If it holds, the secret sharing from Pi is valid. Otherwise, Pj broadcasts a complaint against Pi.(5)
If authorityPi is complained, then it needs to broadcast values yij that satisfy the equation. If the disclosed yij still does not match, Pi has to keep proving itself to be honest until the equation is true.(6)
Pj computes its own private key SKj=∑i=1nyij and calculates its own public key PKj=gSKj. The master secret key s can be recovered by any t values in PK1,…,PKn.(b)
Phase 2 (generation of master public key): According to the above phase, each authority has broadcasted valuesPKi=gSKi for i=1,2,…,n which can verified publicly. Therefore, the master public key can be computed as(2)y=∏i=1nPKi∏j=1,j≠itPj/Pj−Pi.After the above two phases, each authority adds parametersy and Pi,PKii=1n to the parameters params:=p,g,e,G,GT,H,y,n,t,Pi,PKii=1n.(iii)
Key-generation: Useridi makes key-generation request to at least t authorities. Then, the authority generates the corresponding partial secret key and sends it to the user. After receiving the partial secret key, the user can verify its correctness using the public key of the corresponding authority. Finally, user idi computes his secret key skidi by himself.(1)
Phase 1 (generation of partial secret key): Each authorityPj computes a value pskidi,j=HidiSKj and secretly transmits it to user idi.(2)
Phase 2 (verification of partial secret key): After receiving the partial secret keypskidi,j from authority Pj, the user idi verifies the equation epskidi,j,g=eHidi,PKj holds or not. If it holds, then the partial secret key is correct. Otherwise, the user exposes the partial secret key and requests other authorities to authenticate it. The authority Pj needs to retransmit the correct value to satisfies the equation.(3)
Phase 3 (generation of secret key): After receiving all partial secret keys, the useridi computes his own secret key as(3)skidi=Hidis=∏j=1tpskidi,j∏k=1,k≠jtPk/Pk−Pj.(iv)
Identification: We consider two types of identification protocols which corresponding to the passive attack and concurrent (or active) attack, respectively.(a)
Identification protocol against passive attacks:(1)
The proveridi selects r∈ℤp∗ randomly, computes U=Hidir∈G, and sends U to verifier.(2)
The verifier choosesc∈ℤp∗ randomly and sends it to prover idi.(3)
The proveridi computes V=skidir+c∈G and returns it to verifier.(4)
The verifier checkseV,g=eU,y⋅eHidic,y holds or not. If it holds, outputs accept; otherwise, outputs reject.(b)
Identification protocol against active and concurrent attacks:(1)
The proveridi blinds the secret key skidi. Let sk˜idi=skidiz, where z∈ℤp∗ is the blinding factor.(2)
The proveridi randomly selects an integer r∈ℤp∗, computes X=eHidi,yr, and sends X and sk˜idi to verifier.(3)
The verifier chooses a random integerc∈ℤp∗ and sends it to prover idi.(4)
The proveridi computes t=r+czmodp and sends t to verifier.(5)
The verifier checkseHidi,yt=X⋅esk˜idi,gc holds or not. If it holds, outputs accept; otherwise, outputs reject.


### 3.2. Correctness

The correctness of the identification protocol against passive attacks can be verified by the following equation:(4)eV,g=eskidir+c,g=eHidis⋅r+c,g=eHidir+c,gs=eHidir,y⋅eHidic,y=eU,y⋅eHidic,y.The correctness of the identification protocol against concurrent attacks can be verified by the following equation:(5)eHidi,yt=eHidi,yr+cz=eHidi,yr⋅eHidi,ycz=X⋅eHidiz,gsc=X⋅eHidizs,gc=X⋅esk˜idi,gc.


## 3.1. Construction

The construction of the scheme is outlined below:(i)
System-setup: Given the security parameterk as input, generates prime p randomly to establish the system parameters. First of all, it chooses two multiplication cycles G and GT with some prime order p, and a bilinear map e:G×G⟶GT. Let g be a generator of the group G. Next, it chooses a cryptographic hash function H:0,1∗⟶G. The system parameters are params=p,g,e,G,GT,H,n,t, where n is the number of authorities in the system, and t is the threshold value which denotes the number of authorities to generate secret key for users.(ii)
Authority-setup: In this algorithm, all authorities take public parametersparams and their identities P1,…,Pn as inputs and establish their master secret keys SK1,…,SKn. It consists of the following two phases:(a)
Phase 1 (generation of the master secret key): Each authority generates the public key and private key, as well as the master public key of the system.(1)
Each authorityPi selects at random a polynomial ℱix∈ℤp∗ of degree t−1:(1)ℱix=∑j=0t−1aijxj.(2)
Pi calculates Aik=gaik for k=0,1,…,t−1 and then broadcasts Aik.(3)
Pi computes secret value yij=ℱiPj for j=1,2,…,n, and then sends yij secretly to authority Pj for j≠i.(4)
Pj verifies the equation gyij=∏k=0t−1AikPjk holds or not. If it holds, the secret sharing from Pi is valid. Otherwise, Pj broadcasts a complaint against Pi.(5)
If authorityPi is complained, then it needs to broadcast values yij that satisfy the equation. If the disclosed yij still does not match, Pi has to keep proving itself to be honest until the equation is true.(6)
Pj computes its own private key SKj=∑i=1nyij and calculates its own public key PKj=gSKj. The master secret key s can be recovered by any t values in PK1,…,PKn.(b)
Phase 2 (generation of master public key): According to the above phase, each authority has broadcasted valuesPKi=gSKi for i=1,2,…,n which can verified publicly. Therefore, the master public key can be computed as(2)y=∏i=1nPKi∏j=1,j≠itPj/Pj−Pi.After the above two phases, each authority adds parametersy and Pi,PKii=1n to the parameters params:=p,g,e,G,GT,H,y,n,t,Pi,PKii=1n.(iii)
Key-generation: Useridi makes key-generation request to at least t authorities. Then, the authority generates the corresponding partial secret key and sends it to the user. After receiving the partial secret key, the user can verify its correctness using the public key of the corresponding authority. Finally, user idi computes his secret key skidi by himself.(1)
Phase 1 (generation of partial secret key): Each authorityPj computes a value pskidi,j=HidiSKj and secretly transmits it to user idi.(2)
Phase 2 (verification of partial secret key): After receiving the partial secret keypskidi,j from authority Pj, the user idi verifies the equation epskidi,j,g=eHidi,PKj holds or not. If it holds, then the partial secret key is correct. Otherwise, the user exposes the partial secret key and requests other authorities to authenticate it. The authority Pj needs to retransmit the correct value to satisfies the equation.(3)
Phase 3 (generation of secret key): After receiving all partial secret keys, the useridi computes his own secret key as(3)skidi=Hidis=∏j=1tpskidi,j∏k=1,k≠jtPk/Pk−Pj.(iv)
Identification: We consider two types of identification protocols which corresponding to the passive attack and concurrent (or active) attack, respectively.(a)
Identification protocol against passive attacks:(1)
The proveridi selects r∈ℤp∗ randomly, computes U=Hidir∈G, and sends U to verifier.(2)
The verifier choosesc∈ℤp∗ randomly and sends it to prover idi.(3)
The proveridi computes V=skidir+c∈G and returns it to verifier.(4)
The verifier checkseV,g=eU,y⋅eHidic,y holds or not. If it holds, outputs accept; otherwise, outputs reject.(b)
Identification protocol against active and concurrent attacks:(1)
The proveridi blinds the secret key skidi. Let sk˜idi=skidiz, where z∈ℤp∗ is the blinding factor.(2)
The proveridi randomly selects an integer r∈ℤp∗, computes X=eHidi,yr, and sends X and sk˜idi to verifier.(3)
The verifier chooses a random integerc∈ℤp∗ and sends it to prover idi.(4)
The proveridi computes t=r+czmodp and sends t to verifier.(5)
The verifier checkseHidi,yt=X⋅esk˜idi,gc holds or not. If it holds, outputs accept; otherwise, outputs reject.


## 3.2. Correctness

The correctness of the identification protocol against passive attacks can be verified by the following equation:(4)eV,g=eskidir+c,g=eHidis⋅r+c,g=eHidir+c,gs=eHidir,y⋅eHidic,y=eU,y⋅eHidic,y.The correctness of the identification protocol against concurrent attacks can be verified by the following equation:(5)eHidi,yt=eHidi,yr+cz=eHidi,yr⋅eHidi,ycz=X⋅eHidiz,gsc=X⋅eHidizs,gc=X⋅esk˜idi,gc.


## 4. Security Proofs

In this section, we prove the security of the proposed multi-authority IBI scheme.As said above, the proposed scheme is based on the distributed key generation technique [20] and a centralized IBI scheme. It seems that the security of the scheme directly holds based on the securities of the two schemes. It is not true because in the security proof of IBI scheme we need to embed the challenge instance to a fixed element y which is one of the public parameters. However, the value y which is generated by the distributed key generation technique [20] is randomly in the beginning.To resolve this problem, we use the proof framework of [23] which introduced the approach of hybrid games for this kind of schemes. The core technique of [23] is that define three games. The first game corresponds to the honest execution of the security proof. Then, in the second game, we set the master key as y:=gas where a is the exponent of the CDH or OMDL instance and s is the master secret key randomly generated by all authorities, respectively. No one knows a and s. In the last game, the challenger plays the role of all authorities, and thus it knows the value s. Then, we can prove that the advantage of any probabilistic polynomial time (PPT) adversary in the first game is close to the another two games. Hence, if we can prove the advantage of any PPT adversary in the last game which corresponds to the proof of centralized IBI scheme is negligible, then we can obtain the security result that the advantage of any PPT adversary of the multi-authority IBI scheme is also negligible. Therefore, in this work, we only prove the security of the centralized IBI scheme. Please refer to [23] for details of the proof technique which describes the security from centralized scheme to the multi-authority setting.Theorem 1.
The proposed multi-authority IBI scheme is secure against impersonation under passive attack in the random oracle model assuming that the CDH problem is hard.Proof.
LetA=V^,P^ be a polynomial-time imp-pa impersonator that tries to break the IBI scheme. Let C be a challenger that tries to break the BLS signature scheme under chosen message attack. C takes as input k, generates public parameters p,g,e,G,GT,H, where H:0,1∗⟶G is a hash function modeled as a random oracle. C chooses x∈ℤp⋆, computes y=gx∈G, and then gives system public parameters params=p,g,e,G,GT,H,y to adversary A.
IfA makes a key generation query on idi. C then returns the corresponding private key skidi as the answer. If A makes a transcript query on idj. Then C chooses cj∈ℤp∗, Vj∈G randomly and computes Uj such that eVj,g=eUj,y⋅eHidjcj,y. C then gives Uj,cj,Vj to A as the transcript. Finally, A chooses a challenge identity id∗.
Now,A plays the role as the cheating prover and interacts with challenger C. A can still issues some key generation queries and transcript queries in this phase, with the restriction that the query on the challenge identity id∗ is not allowed. C runs A to get the response U. After receiving U, C selects c∈ℤp∗ randomly, runs A to get its response V and verifies the equation eV,g=eU,y⋅eHid∗c,y holds or not. If the equation holds, C runs A again with the same state but with different challenge value c′∈ℤp∗, obtains its response V′, and verifies the equation eV′,g=eU,y⋅eHid∗c′,y hold or not. If the equation holds, C outputs V/V′c−c′−1 as a forgery. Since we have V=skid∗r+c and V′=skid∗r+c′. Thus, skid∗=V/V′c−c′−1 is a valid signature on id∗.Theorem 2.
The proposed multi-authority IBI scheme is secure against impersonation under concurrent attack in random oracle model assuming that the OMDL problem is hard.Proof.
LetA=V^,P^ be a polynomial-time imp-ca impersonator that tries to break the identity-based identification scheme. Let C be an OMDL challenger. We assume that V^ never repeats a request. C takes as input k and generates public parameters p,g,e,G,GT. C chooses x∈ℤp∗ and computes y=gx∈G and then outputs params=p,g,e,G,GT,y as system public parameters. C returns params to adversary A.
IfA makes a key generation query on idi. C then returns the corresponding private key skidi as the answer.
Now,A makes a identification training. First, challenger C queries its challenge oracle ℬ⋅ to obtain a challenge point W0=gr0∈G, where r0∈ℤp∗. C now chooses an arbitrary identity id∈0,1∗. H:0,1∗⟶G is hash function viewed as a random oracle. We set it as follows. C chooses a random l∈ℤp∗ and sets Hid=gl∈G. If id′≠id, C chooses a random l′∈ℤp∗ and sets Hid′=gl′∈G. C next computes sk˜id=W0lx and sends it to adversary A. Since W0=gr0 for random r0∈ℤp∗, sk˜id=W0lx=gr0lx=Hidxr0 for random l,x∈ℤp∗. Now, C simulates an interaction between V^ and the prover replicas as follows. A random tape Ri is chosen for prover replicas i. C then initializes prover replicas i with params,Ri. C first queries its challenge oracle B⋅ to get the response Wi. C computes Xi=eWilx,g and sends this to V^. Since Wi=gri for random ri∈ℤp∗, we have Xi=eWilx,g=egrilx,g=egril,gx=egl,gxri=eHid,yri. V^ chooses random ci∈ℤp∗ and returns to C. C makes the query WiW0ci to its discrete log oracle DLp,g⋅ and get the response ti. C sends ti to V^. V^ verifies the equation eHid,yti=Xi⋅esk˜id,gci hold or not. The correctness of the equation is as follows:(6)eHid,yti=egl,gxri+cir0=egl,gxri⋅+egl,gxcir0=Xi⋅eglxr0,gci=Xi⋅esk˜id,gci.
After performing the above simulations,V^ outputs some state information and stops interaction. Now, C attempts to extract the discrete logarithm r0 of challenge point W0. Then using this value, C can further compute the discrete logarithm r1,r2,…,rn of other challenge points W1,W2,…,Wn. To do so, C runs P^ in state St obtaining X, selects a random c∈ℤp∗, and runs P^ to get its response t. C then verifies the equation eHid,yt=X⋅esk˜id,gc holds or not. If the equation holds, C runs P^ again with the same state St but with different challenge value c′∈ℤp∗, obtains its response t′ and verifies the equation eHid,yt′=X⋅esk˜id,gc′ hold or not. If the equation holds, C computes t−t′/c−c′modp. We show that t−t′/c−c′modp is the discrete logarithm of W0. Observing that(7)eglxt−t′/c−c′,g=eglxt−t′,g1/c−c′=egl,gxtegl,gx−t′1/c−c′=eHid,yteHid,y−t′c−c′=X⋅esk˜id,gcX⋅esk˜id,gc′−1c−c′=esk˜id,gc−c′1/c−c′=eW0lx,g=egr0lx,g.
From the above equation, we obtainr0=t−t′/c−c′modp. We now can further compute ri=ti−cir0modp for i=1,2,…,n. Finally, C outputs r1,r2,…,rn.


## 5. Applications

The proposed IBI scheme provides a good solution for scenarios where there is no trusted center, such as blockchain. Hence, in this section, we consider the application of the multi-authority IBI scheme in blockchain.Blockchain technology was introduced by Nakamoto [24] in Bitcoin. Blockchain as the underlying technology of Bitcoin is essentially a type of distributed ledger. It can avoid the single point of failure. The advantages of blockchain are decentralization, anonymity, trustworthiness, and so on. According to different application scenarios and participants, blockchain can be divided into three categories, including public blockchain, consortium blockchain, and private blockchain [25]. In public blockchain, everyone can read and send transactions and everyone could join in the consensus process. For private blockchain, the node coming from a specific organization can be allowed to enter into the consensus process. The consortium blockchain is between public blockchain and private blockchain. It is a specific blockchain with authorized nodes. The consensus process is controlled by authorized nodes. The consortium blockchain is a community composed of n member organizations, and each member runs a node. Only with the confirmation of 2/3 of the member organizations can each block take effect. At present, many researchers are trying to utilize blockchain in different fields, such as healthcare [26, 27], Internet of things (IoT) [28], and so on. This will make data freedom from ideal to reality, and these data providers will become the buliders and users of blockchain. In order to achieve the security of data sharing and privacy protection and confirm that data usage is legitimate, it is necessary to reach a consensus on the identification to ensure the authenticity of the identity on the chain.Traditional IBI schemes are centralized which have a trusted party to generate and distribute users’ key. However, the main feature of blockcahin is decentralization. Traditional IBI schemes are suitable for single authority instead of multiple authorities. There is no trusted party in blockchain. At the same time, we cannot build a trusted party in blockchain. Distrbuted identification is a way to address this problem. In distributed identification, we do not need to rely on the trusted third party for secret key generation and distribution and identity management.Our multi-authority IBI scheme can provide a good solution for consortium blockchain. We describe the application of our IBI scheme in consortium blockchain. In the consortium blockchain, we can divide nodes into two types, authority and user. The member of consortium blockchain plays the role of the authority, and the user is assumed by other nodes that join the consortium blockchain. The identification protocol for blockchain based on multi-authority IBI scheme is as shown in Figure1.Figure 1
The identification protocol of blockchain based on multi-authority IBI scheme.(1)
System-setup: In the beginning, alln authorities are cooperating to initialize the consortium blockchain system. In this phase, they generate the public parameters according to the security parameters. Meanwhile, all master secret keys can be generated by themselves. Finally, public parameters are published to all users in this system, and the master secret keys are secretly kept by all authorities.(2)
User-registration: When a user wants to join the system, he submits his enrollment request to at leastt authorities. Then, the system assign an unique recognizable identity id and corresponding partial secret key pskid,j. Eventually, user verifies the validity of the partial secret key and computes its own secret key skid.(3)
Identification: Finally, in some cases, the user needs to prove that he is a legitimate user of this system. Then he can use the identification protocol of the IBI scheme.


## 6. Conclusion

In this paper, we propose an identity-based identification scheme without trusted party, which is provably secure in the random oracle model. Our scheme takes advantage of distributed key generation to generate the user’s secret key. By interacting with at leastt authorities, a legal user can generate his/her secret key. Thus, it avoids any one authority being a single-point bottleneck on security. The security analysis results show that our identity-based identification scheme is secure against impersonation under passive and concurrent attacks. Finally, we apply the proposed scheme to the blockchain.



---

*Source: 8820271-2020-10-17.xml*