# Optimistic Fair Exchange in Cloud-Assisted Cyber-Physical Systems

Authors: Jun Wang; Feixiang Luo; Zequan Zhou; Xiling Luo; Zhen Wang
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Recently, optimistic fair exchange in electronic commerce (e-commerce) or mobile commerce (m-commerce) has made great progress. However, new technologies create large amounts of data and it is difficult to handle them. Fortunately, with the assistance of cloud computing and big data, optimistic fair exchange of digital items in cyber-physical systems (CPSes) can be efficiently managed. Optimistic fair exchange in cloud-assisted CPSes mainly focuses on online data exchange in e-commerce or online contracts signing. However, there exist new forms of risks in the uncertain network environment. To solve the above problems, we use a new technique called verifiably encrypted identity-based signature (VEIS) to construct optimistic fair exchange in cloud-assisted CPSes. VEIS is an encrypted signature, and we can check the validity of the underlying signature without decrypting it. We introduce a robust arbitration mechanism to guarantee fairness of the exchange, and even the trusted third party (TTP) cannot get the original signatures of the exchange parties. And the TTP in our protocol is offline, which greatly improves the efficiency. Besides, we show that our protocol is secure, fair, and practical.


---

## Body

## 1. Introduction

### 1.1. Background

In recent years, optimistic fair exchange in e-commerce and m-commerce has grown fast and information technology has been widely utilized. However, with the development of the information systems, the data are rapidly and continuously created from varieties of devices in the transaction, leaving big challenges for data storage and management. The new cloud-assisted cyber-physical systems (CPSes), which combine the big data, cloud computing, internet of things, and even artificial intelligence with industrial automation, can be used to deal with huge files and complex structures in the fair exchange.The model of optimistic fair exchange in cloud-assisted CPSes is shown in Figure1. In such systems, users can purchase the service or store their data in the cloud data service. Besides, they can also use their data to trade with others or sign contracts on digital files. For example, if Alice attempts to exchange her digital content with Bob in another cloud, she needs to perform optimistic fair exchange of signatures in her physical devices (e.g., desktop, laptop, or smartphone).Figure 1
Optimistic fair exchange in cloud-assisted CPSes.Although optimistic fair exchange in cloud-assisted CPSes plays a significant role in e-commerce or m-commerce with new capabilities, there still exist risks. Security and privacy issues continue to be a barrier for optimistic fair exchange due to the uncertain network environment. For uncertain environment of fair exchange, we consider two aspects: uncertain contents of the exchange and uncertain activities of the exchange [1, 2]. On the one hand, the exchange parties may not know what will be received before the exchange. On the other hand, no one can make sure the other party does honestly in the transaction. To solve the above problems, we proposed optimistic fair exchange, which is secure and practical in cloud-assisted CPSes.


### 1.2. Rated Works

Optimistic fair exchange is a common method in e-commerce or m-commerce, in which two parties (e.g., individuals, companies, or systems) exchange their signatures of digital goods fairly. In optimistic fair exchange protocols [3, 4], we usually consider three parties, two exchange parties and a trusted third party (TTP, also called arbiter). Suppose Alice and Bob are parties involved in the protocol, and they need to exchange their signatures of contracts. In the protocol, Alice first sends a partial signature to Bob, and Bob then checks the validity of the partial signature. If it is invalid, Bob stops the protocol. Otherwise, Bob sends his full signature to Alice. Alice then checks whether Bob’s full signature is valid. If it is valid, then Alice sends her full signature to Bob. If Bob does not receive Alice’s full signature or receives an invalid signature, then Bob submits his full signature and Alice’s partial signature to the TTP, the TTP first checks whether Bob’s signature is valid. If it is valid, then the TTP converts the partial signature to the full signature and returns it to Bob. At the same time, the TTP returns Bob’s full signature to Alice as well. Otherwise, the TTP does nothing.There are other fair exchange protocols which use different technologies. In [5], the authors proposed a fair document exchange, which protected the anonymity of signers. Their another work [6] offered the protection of the private information and provided offline signature recovery. Fan et al. [7] used watermarking technology to construct fair content exchange in cloud computing; however, they did not give the full security proof. In [8], they showed optimistic fair exchange protocols which can be used in file sharing system with a high volume of data exchanged. However, all the above schemes have weaknesses. We compare these schemes with ours in the following aspects. The results are shown in Table 1.(i)
Identity-based cryptosystem: it does not need to exchange public and private keys and does not need key directories; thus, it has better efficiency than PKI-based cryptosystem.(ii)
Semitrusted third party (TTP): since malicious TTP may leak the information of the users, we need to use semi-TTP to replace fully trusted arbiter.(iii)
Strong security: security is important for optimistic fair exchange; however, we find some schemes do not satisfy strong security since they do not give the attack model and security proof.Table 1
Summary of fair exchange schemes.
Identity-based cryptosystem
Semitrusted third party
Strong security
Zhang et al. [5]
No
No
No
Zhang et al. [6]
No
Yes
Yes
Fan et al. [7]
No
No
No
Kp and Lysyanskaya [8]
No
No
Yes
Gu et al. [9]
Yes
No
No
Zhang et al. [10]
Yes
No
No
Ours
Yes
Yes
YesA kind of technique called verifiably encrypted signature (VES) can be used to construct optimistic fair exchange in cloud-assisted CPSes. VES is an encrypted signature, and we can check the validity without extracting the original signature. Some optimistic fair exchange protocols based on VES [9–13] have been proposed. However, most of them are based on Public Key Infrastructure (PKI), thus leading to the high cost in authenticating and managing the public keys. Fortunately, several identity-based VES schemes [9, 10, 12] have been proposed since identity-based cryptosystems can be used to reduce the cost in public key distribution and management. Most identity-based schemes are more efficient. With regard to security, most schemes consider only if an adversary cannot forge a valid original signature and a valid VES. However, they do not consider stronger security attributes: Can anyone forge a valid VES while the underlying signature is invalid? Meanwhile, many schemes do not give the attack model and security proof. Therefore, even though the schemes [9, 10, 12] are highly efficient, they are not very secure. We compare our scheme with the above schemes in four aspects in Table 2:(i)
Identity-based cryptosystem: it greatly reduces the cost in management of the public keys because it does not need to exchange public and private keys and does not need key directories.(ii)
Standard model: the security proof of a scheme does not use random oracle model.(iii)
Strong security: it means that the scheme satisfies three different security properties at the same time. The properties include opacity, unforgeability, and extractability. Meanwhile, there should be the attack model and security proof.(iv)
High efficiency: the lower the computational overhead involved in a scheme, the higher the efficiency. Therefore, high efficiency means less use of complex mathematical operations, including exponential, hash, and bilinear operations, while maintaining strong security properties. For a detailed computational overhead, refer to Table3.Table 2
Summary of VES schemes.
Identity-based cryptosystem
Standard model
Strong security
High efficiency
Boneh et al. [11]
No
Yes
No
Yes
Gu [9]
Yes
No
No
Yes
Zhang et al. [10]
Yes
Yes
No
No
Lu et al. [12]
Yes
Yes
No
Yes
Nishimaki and Xagawa [13]
No
Yes
Yes
No
Shao and Gao [14]
No
No
Yes
No
Seo et al. [15]
No
Yes
Yes
No
Ours
Yes
Yes
Yes
YesTable 3
The efficiency of VES schemes.
SKG
VESign
VEVerify
Adj
Ver
Boneh et al. [11]
1E
3E + 1H
3e + 1H
1E
2e + 1H
Gu et al. [9]
1H
2E + 2H
3e + 1H
1e + 1H
2e + 2H + 1E
Zhang et al. [10]
2E
6E
5e
5E
4e
Shao and Gao [14]
2E
6E + 2H
8E + 2H
3E + 1H
4E + 2H
Seo et al. [15]
2E
6E + 1H
4e + 1H + 1E
4E
3e
Ours
2E
6E
5e
1E
4eMotivated by the above works, we construct an optimistic fair exchange protocol with a new kind of VES scheme which combines an identity-based signature scheme and a PKI-based encryption scheme. In this way, we can achieve secure and efficient fair exchange in cloud-assisted CPSes.


### 1.3. Our Contributions

Technically, we use a new cryptographic technique called verifiably identity-based signature (VEIS) to construct the optimistic fair exchange protocol. The VEIS scheme which combines an identity-based signature scheme [16] and the ElGamal encryption scheme [17] allows us to exchange signatures in the cloud-assisted CPSes easily. Besides, we define the security properties according to the major requirements of optimistic fair exchange in cloud-assisted CPSes. The properties include opacity, unforgeability, and extractability. Opacity guarantees that no one can extract a valid signature from a VEIS without the private key. Unforgeability means that no one can forge a VEIS without the signing key of his identity. And extractability means that if a VEIS is valid, then a valid signature can be pulled out from it.Then, we construct optimistic fair exchange in cloud-assisted CPSes with our VEIS scheme. In our protocol, two parties (Alice and Bob) may exchange their digital signatures in cloud with their physical devices. Then, Alice first generates her VEIS and sends it to Bob. Next, Bob sends his identity-based signature to Alice if Alice’s VEIS is valid. Finally, Alice sends her identity-based signature to Bob. If cheating occurs during the exchange, the trusted third party (TTP) will get involved and ensure the fairness. Our protocol protects the privacy of the exchange parties since TTP will not get the original signatures of them. Besides, TTP only involves in the exchange when cheating occurs and it reduces the communication cost. The arbitration mechanism guarantees the fairness of the exchange, which means both parties obtain the other’s signature or neither does when the protocol ends. Finally, we report the results of the simulation, which show that our protocol is efficient.


### 1.4. Outline

We organize the rest of this paper as follows. In Section2, we give some relevant notions and show the building blocks of our scheme. In Section 3, we present the verifiably encrypted identity-based signature (VEIS) scheme which is used to construct our optimistic fair exchange in cloud-assisted CPSes. In Section 4, we construct the optimistic fair exchange protocol with offline TTP. Then, we discuss the security and fairness of our protocol. In Section 5, we show the results of the simulation. Finally, we conclude in Section 6.


## 1.1. Background

In recent years, optimistic fair exchange in e-commerce and m-commerce has grown fast and information technology has been widely utilized. However, with the development of the information systems, the data are rapidly and continuously created from varieties of devices in the transaction, leaving big challenges for data storage and management. The new cloud-assisted cyber-physical systems (CPSes), which combine the big data, cloud computing, internet of things, and even artificial intelligence with industrial automation, can be used to deal with huge files and complex structures in the fair exchange.The model of optimistic fair exchange in cloud-assisted CPSes is shown in Figure1. In such systems, users can purchase the service or store their data in the cloud data service. Besides, they can also use their data to trade with others or sign contracts on digital files. For example, if Alice attempts to exchange her digital content with Bob in another cloud, she needs to perform optimistic fair exchange of signatures in her physical devices (e.g., desktop, laptop, or smartphone).Figure 1
Optimistic fair exchange in cloud-assisted CPSes.Although optimistic fair exchange in cloud-assisted CPSes plays a significant role in e-commerce or m-commerce with new capabilities, there still exist risks. Security and privacy issues continue to be a barrier for optimistic fair exchange due to the uncertain network environment. For uncertain environment of fair exchange, we consider two aspects: uncertain contents of the exchange and uncertain activities of the exchange [1, 2]. On the one hand, the exchange parties may not know what will be received before the exchange. On the other hand, no one can make sure the other party does honestly in the transaction. To solve the above problems, we proposed optimistic fair exchange, which is secure and practical in cloud-assisted CPSes.


## 1.2. Rated Works

Optimistic fair exchange is a common method in e-commerce or m-commerce, in which two parties (e.g., individuals, companies, or systems) exchange their signatures of digital goods fairly. In optimistic fair exchange protocols [3, 4], we usually consider three parties, two exchange parties and a trusted third party (TTP, also called arbiter). Suppose Alice and Bob are parties involved in the protocol, and they need to exchange their signatures of contracts. In the protocol, Alice first sends a partial signature to Bob, and Bob then checks the validity of the partial signature. If it is invalid, Bob stops the protocol. Otherwise, Bob sends his full signature to Alice. Alice then checks whether Bob’s full signature is valid. If it is valid, then Alice sends her full signature to Bob. If Bob does not receive Alice’s full signature or receives an invalid signature, then Bob submits his full signature and Alice’s partial signature to the TTP, the TTP first checks whether Bob’s signature is valid. If it is valid, then the TTP converts the partial signature to the full signature and returns it to Bob. At the same time, the TTP returns Bob’s full signature to Alice as well. Otherwise, the TTP does nothing.There are other fair exchange protocols which use different technologies. In [5], the authors proposed a fair document exchange, which protected the anonymity of signers. Their another work [6] offered the protection of the private information and provided offline signature recovery. Fan et al. [7] used watermarking technology to construct fair content exchange in cloud computing; however, they did not give the full security proof. In [8], they showed optimistic fair exchange protocols which can be used in file sharing system with a high volume of data exchanged. However, all the above schemes have weaknesses. We compare these schemes with ours in the following aspects. The results are shown in Table 1.(i)
Identity-based cryptosystem: it does not need to exchange public and private keys and does not need key directories; thus, it has better efficiency than PKI-based cryptosystem.(ii)
Semitrusted third party (TTP): since malicious TTP may leak the information of the users, we need to use semi-TTP to replace fully trusted arbiter.(iii)
Strong security: security is important for optimistic fair exchange; however, we find some schemes do not satisfy strong security since they do not give the attack model and security proof.Table 1
Summary of fair exchange schemes.
Identity-based cryptosystem
Semitrusted third party
Strong security
Zhang et al. [5]
No
No
No
Zhang et al. [6]
No
Yes
Yes
Fan et al. [7]
No
No
No
Kp and Lysyanskaya [8]
No
No
Yes
Gu et al. [9]
Yes
No
No
Zhang et al. [10]
Yes
No
No
Ours
Yes
Yes
YesA kind of technique called verifiably encrypted signature (VES) can be used to construct optimistic fair exchange in cloud-assisted CPSes. VES is an encrypted signature, and we can check the validity without extracting the original signature. Some optimistic fair exchange protocols based on VES [9–13] have been proposed. However, most of them are based on Public Key Infrastructure (PKI), thus leading to the high cost in authenticating and managing the public keys. Fortunately, several identity-based VES schemes [9, 10, 12] have been proposed since identity-based cryptosystems can be used to reduce the cost in public key distribution and management. Most identity-based schemes are more efficient. With regard to security, most schemes consider only if an adversary cannot forge a valid original signature and a valid VES. However, they do not consider stronger security attributes: Can anyone forge a valid VES while the underlying signature is invalid? Meanwhile, many schemes do not give the attack model and security proof. Therefore, even though the schemes [9, 10, 12] are highly efficient, they are not very secure. We compare our scheme with the above schemes in four aspects in Table 2:(i)
Identity-based cryptosystem: it greatly reduces the cost in management of the public keys because it does not need to exchange public and private keys and does not need key directories.(ii)
Standard model: the security proof of a scheme does not use random oracle model.(iii)
Strong security: it means that the scheme satisfies three different security properties at the same time. The properties include opacity, unforgeability, and extractability. Meanwhile, there should be the attack model and security proof.(iv)
High efficiency: the lower the computational overhead involved in a scheme, the higher the efficiency. Therefore, high efficiency means less use of complex mathematical operations, including exponential, hash, and bilinear operations, while maintaining strong security properties. For a detailed computational overhead, refer to Table3.Table 2
Summary of VES schemes.
Identity-based cryptosystem
Standard model
Strong security
High efficiency
Boneh et al. [11]
No
Yes
No
Yes
Gu [9]
Yes
No
No
Yes
Zhang et al. [10]
Yes
Yes
No
No
Lu et al. [12]
Yes
Yes
No
Yes
Nishimaki and Xagawa [13]
No
Yes
Yes
No
Shao and Gao [14]
No
No
Yes
No
Seo et al. [15]
No
Yes
Yes
No
Ours
Yes
Yes
Yes
YesTable 3
The efficiency of VES schemes.
SKG
VESign
VEVerify
Adj
Ver
Boneh et al. [11]
1E
3E + 1H
3e + 1H
1E
2e + 1H
Gu et al. [9]
1H
2E + 2H
3e + 1H
1e + 1H
2e + 2H + 1E
Zhang et al. [10]
2E
6E
5e
5E
4e
Shao and Gao [14]
2E
6E + 2H
8E + 2H
3E + 1H
4E + 2H
Seo et al. [15]
2E
6E + 1H
4e + 1H + 1E
4E
3e
Ours
2E
6E
5e
1E
4eMotivated by the above works, we construct an optimistic fair exchange protocol with a new kind of VES scheme which combines an identity-based signature scheme and a PKI-based encryption scheme. In this way, we can achieve secure and efficient fair exchange in cloud-assisted CPSes.


## 1.3. Our Contributions

Technically, we use a new cryptographic technique called verifiably identity-based signature (VEIS) to construct the optimistic fair exchange protocol. The VEIS scheme which combines an identity-based signature scheme [16] and the ElGamal encryption scheme [17] allows us to exchange signatures in the cloud-assisted CPSes easily. Besides, we define the security properties according to the major requirements of optimistic fair exchange in cloud-assisted CPSes. The properties include opacity, unforgeability, and extractability. Opacity guarantees that no one can extract a valid signature from a VEIS without the private key. Unforgeability means that no one can forge a VEIS without the signing key of his identity. And extractability means that if a VEIS is valid, then a valid signature can be pulled out from it.Then, we construct optimistic fair exchange in cloud-assisted CPSes with our VEIS scheme. In our protocol, two parties (Alice and Bob) may exchange their digital signatures in cloud with their physical devices. Then, Alice first generates her VEIS and sends it to Bob. Next, Bob sends his identity-based signature to Alice if Alice’s VEIS is valid. Finally, Alice sends her identity-based signature to Bob. If cheating occurs during the exchange, the trusted third party (TTP) will get involved and ensure the fairness. Our protocol protects the privacy of the exchange parties since TTP will not get the original signatures of them. Besides, TTP only involves in the exchange when cheating occurs and it reduces the communication cost. The arbitration mechanism guarantees the fairness of the exchange, which means both parties obtain the other’s signature or neither does when the protocol ends. Finally, we report the results of the simulation, which show that our protocol is efficient.


## 1.4. Outline

We organize the rest of this paper as follows. In Section2, we give some relevant notions and show the building blocks of our scheme. In Section 3, we present the verifiably encrypted identity-based signature (VEIS) scheme which is used to construct our optimistic fair exchange in cloud-assisted CPSes. In Section 4, we construct the optimistic fair exchange protocol with offline TTP. Then, we discuss the security and fairness of our protocol. In Section 5, we show the results of the simulation. Finally, we conclude in Section 6.


## 2. The Main Text

### 2.1. Bilinear Maps and Complexity Assumption

We first briefly review the bilinear maps and complexity assumptions below.


#### 2.1.1. Bilinear Maps

LetG and GT be groups of prime order p and g be a generator of G, then we say that e:G×G⟶GT is an efficient and computable bilinear map if it satisfies the following properties, i.e., (1) Bilinear: ∀a,b∈ℤp, we have ega,gb=eg,gab. (2) Nondegenerate: eg,g≠1: clearly, the bilinearity implies that ∀g1,g2,g3∈G, we have eg1,g3eg2,g3=eg1g2,g3.


#### 2.1.2. Complexity Assumptions

CDH problem: giveng, ga, and gb, compute gab.If the probability that adversaryB solves the CDH problem is at least ϵ, we have(1)PrBg,ga,gb=gab≥ε.Then, CDH assumption is as follows.Definition 1.
Thet,ε-CDH assumption holds if no adversary runs at most t times and has at least ϵ advantage in solving the CDH problem on G.
The aggregate extraction problem: giveng, ga, gb, gβ, gδ, and gab+βδ, compute gab.
If the probability that adversaryB solves the aggregate extraction problem is at least ϵ, we have(2)PrBg,ga,gb,gβ,gδ,gab+βδ=gab≥ε.
Then, aggregate extraction assumption is as follows.Definition 2.
Thet,ϵ-aggregate extraction assumption holds if no adversary runs at most t times and has at least ϵ advantage in solving the aggregate extraction problem on G.


### 2.2. Building Blocks

Our optimistic fair exchange protocol is mainly based on Paterson’s identity-based signature (IBS) scheme [16] and ElGamal encryption scheme [17], which are described as follows.


#### 2.2.1. Paterson’s IBS Scheme

LetG and GT be groups of prime order p and g be a generator of G. There exists an efficient and computable bilinear map e:G×G⟶GT. All identities and messages will be assumed to be bit strings of length nu and nm, respectively. We can also let identities be bit strings of arbitrary length and nu and nm be the output length of collision-resistant hash functions, Hu:0,1⟶0,1nu and Hm:0,1⟶0,1nm. The signature scheme is defined by the following algorithms.Setup: a secretα∈ℤp and generator g of G are chosen at random. Then, set the value g1=gα and choose g2 randomly in G. Additionally, pick elements u′, m′∈G randomly and vectors U=ui, M=mi of length nu and nm, where ui and mi are randomly chosen from G. The public parameters are MPK=G,GT,e,g,g1,g2,u′,U,m′,M and the master secret key is MSK=g2α.Extract: letU be a bit string of length nu representing an identity and let Ui be the ith bit of U. Define U¯⊂1,…,nu to be the set of indices i such that Ui=1. A private key for identity U is generated as follows. First, choose a random ru∈ℤp. Then, compute(3)skU=dU=d1,d2=g2αu′∏i∈U¯uiru,gru.Sign: letm be a bit string of length nm representing a message. Furthermore, let M¯⊂1,…,nm be a set of indices j such that mj=1.A signature ofU on m is constructed as follows: First, pick a random rm∈ℤp. Then, compute(4)σ=σ0,σ1,σ2=g2αu′∏i∈U¯uirum′∏j∈M¯mjrm,gru,grm.Verify: suppose we wish to check ifσ=σ0,σ1,σ2 is a valid signature of an identity U on m. The signature is accepted if it holds that(5)eσ0,g=eg2,g1eu′∏i∈U¯ui,σ1⋅em′∏j∈M¯mj,σ2.


#### 2.2.2. The Modified Signature Scheme

In Paterson’s IBS scheme, we find one element of the signature (σ1) is a part of the private key (d2) and it is not allowed in the strictest sense. Thus, we randomize the first two elements, including the secret key part of the original signature. Let Σ=Setup,Extract,Sign,Verify be Paterson’s IBS scheme, and the new IBS scheme Σ′=Setup′,Extract′,Sign′,Verify′ is as follows:Setup′ and Extract′ are the same as Setup and Extract, respectively.Sign′: choose random ru′,rm∈ℤp and compute(6)σ=σ0,σ1,σ2=σ0⋅u′∏i∈U¯uiru′,σ1⋅gru′,σ2.Verify′: we can check the validity of the signature by the following equation:(7)eσ0,g=?eg2,g1eu′∏i∈U¯ui,σ1⋅em′∏j∈M¯mj,σ2.If the equation holds, then the signature is valid. Otherwise, it is invalid.The modified signature scheme is existentially unforgeable and the security proof is almost the same as stated in [16], we will not prove it again. We use the following theorem to show that.Theorem 1.
The modified identity-based signature scheme is existentially unforgeable if the CDH assumption holds.


#### 2.2.3. The Encryption Scheme

In the ElGamal encryption scheme, KeyGen generates a pair of keysSK,PK=α,gα, where g is a generator of G. Enc takes as input PK, a message m, and outputs ciphertext C=C1,C2=mPKt,gt, where t is randomly chosen from G. Dec takes as input C, the secret key SK, and outputs the message m=C1/C2α=m.


## 2.1. Bilinear Maps and Complexity Assumption

We first briefly review the bilinear maps and complexity assumptions below.


### 2.1.1. Bilinear Maps

LetG and GT be groups of prime order p and g be a generator of G, then we say that e:G×G⟶GT is an efficient and computable bilinear map if it satisfies the following properties, i.e., (1) Bilinear: ∀a,b∈ℤp, we have ega,gb=eg,gab. (2) Nondegenerate: eg,g≠1: clearly, the bilinearity implies that ∀g1,g2,g3∈G, we have eg1,g3eg2,g3=eg1g2,g3.


### 2.1.2. Complexity Assumptions

CDH problem: giveng, ga, and gb, compute gab.If the probability that adversaryB solves the CDH problem is at least ϵ, we have(1)PrBg,ga,gb=gab≥ε.Then, CDH assumption is as follows.Definition 1.
Thet,ε-CDH assumption holds if no adversary runs at most t times and has at least ϵ advantage in solving the CDH problem on G.
The aggregate extraction problem: giveng, ga, gb, gβ, gδ, and gab+βδ, compute gab.
If the probability that adversaryB solves the aggregate extraction problem is at least ϵ, we have(2)PrBg,ga,gb,gβ,gδ,gab+βδ=gab≥ε.
Then, aggregate extraction assumption is as follows.Definition 2.
Thet,ϵ-aggregate extraction assumption holds if no adversary runs at most t times and has at least ϵ advantage in solving the aggregate extraction problem on G.


## 2.1.1. Bilinear Maps

LetG and GT be groups of prime order p and g be a generator of G, then we say that e:G×G⟶GT is an efficient and computable bilinear map if it satisfies the following properties, i.e., (1) Bilinear: ∀a,b∈ℤp, we have ega,gb=eg,gab. (2) Nondegenerate: eg,g≠1: clearly, the bilinearity implies that ∀g1,g2,g3∈G, we have eg1,g3eg2,g3=eg1g2,g3.


## 2.1.2. Complexity Assumptions

CDH problem: giveng, ga, and gb, compute gab.If the probability that adversaryB solves the CDH problem is at least ϵ, we have(1)PrBg,ga,gb=gab≥ε.Then, CDH assumption is as follows.Definition 1.
Thet,ε-CDH assumption holds if no adversary runs at most t times and has at least ϵ advantage in solving the CDH problem on G.
The aggregate extraction problem: giveng, ga, gb, gβ, gδ, and gab+βδ, compute gab.
If the probability that adversaryB solves the aggregate extraction problem is at least ϵ, we have(2)PrBg,ga,gb,gβ,gδ,gab+βδ=gab≥ε.
Then, aggregate extraction assumption is as follows.Definition 2.
Thet,ϵ-aggregate extraction assumption holds if no adversary runs at most t times and has at least ϵ advantage in solving the aggregate extraction problem on G.


## 2.2. Building Blocks

Our optimistic fair exchange protocol is mainly based on Paterson’s identity-based signature (IBS) scheme [16] and ElGamal encryption scheme [17], which are described as follows.


### 2.2.1. Paterson’s IBS Scheme

LetG and GT be groups of prime order p and g be a generator of G. There exists an efficient and computable bilinear map e:G×G⟶GT. All identities and messages will be assumed to be bit strings of length nu and nm, respectively. We can also let identities be bit strings of arbitrary length and nu and nm be the output length of collision-resistant hash functions, Hu:0,1⟶0,1nu and Hm:0,1⟶0,1nm. The signature scheme is defined by the following algorithms.Setup: a secretα∈ℤp and generator g of G are chosen at random. Then, set the value g1=gα and choose g2 randomly in G. Additionally, pick elements u′, m′∈G randomly and vectors U=ui, M=mi of length nu and nm, where ui and mi are randomly chosen from G. The public parameters are MPK=G,GT,e,g,g1,g2,u′,U,m′,M and the master secret key is MSK=g2α.Extract: letU be a bit string of length nu representing an identity and let Ui be the ith bit of U. Define U¯⊂1,…,nu to be the set of indices i such that Ui=1. A private key for identity U is generated as follows. First, choose a random ru∈ℤp. Then, compute(3)skU=dU=d1,d2=g2αu′∏i∈U¯uiru,gru.Sign: letm be a bit string of length nm representing a message. Furthermore, let M¯⊂1,…,nm be a set of indices j such that mj=1.A signature ofU on m is constructed as follows: First, pick a random rm∈ℤp. Then, compute(4)σ=σ0,σ1,σ2=g2αu′∏i∈U¯uirum′∏j∈M¯mjrm,gru,grm.Verify: suppose we wish to check ifσ=σ0,σ1,σ2 is a valid signature of an identity U on m. The signature is accepted if it holds that(5)eσ0,g=eg2,g1eu′∏i∈U¯ui,σ1⋅em′∏j∈M¯mj,σ2.


### 2.2.2. The Modified Signature Scheme

In Paterson’s IBS scheme, we find one element of the signature (σ1) is a part of the private key (d2) and it is not allowed in the strictest sense. Thus, we randomize the first two elements, including the secret key part of the original signature. Let Σ=Setup,Extract,Sign,Verify be Paterson’s IBS scheme, and the new IBS scheme Σ′=Setup′,Extract′,Sign′,Verify′ is as follows:Setup′ and Extract′ are the same as Setup and Extract, respectively.Sign′: choose random ru′,rm∈ℤp and compute(6)σ=σ0,σ1,σ2=σ0⋅u′∏i∈U¯uiru′,σ1⋅gru′,σ2.Verify′: we can check the validity of the signature by the following equation:(7)eσ0,g=?eg2,g1eu′∏i∈U¯ui,σ1⋅em′∏j∈M¯mj,σ2.If the equation holds, then the signature is valid. Otherwise, it is invalid.The modified signature scheme is existentially unforgeable and the security proof is almost the same as stated in [16], we will not prove it again. We use the following theorem to show that.Theorem 1.
The modified identity-based signature scheme is existentially unforgeable if the CDH assumption holds.


### 2.2.3. The Encryption Scheme

In the ElGamal encryption scheme, KeyGen generates a pair of keysSK,PK=α,gα, where g is a generator of G. Enc takes as input PK, a message m, and outputs ciphertext C=C1,C2=mPKt,gt, where t is randomly chosen from G. Dec takes as input C, the secret key SK, and outputs the message m=C1/C2α=m.


## 2.2.1. Paterson’s IBS Scheme

LetG and GT be groups of prime order p and g be a generator of G. There exists an efficient and computable bilinear map e:G×G⟶GT. All identities and messages will be assumed to be bit strings of length nu and nm, respectively. We can also let identities be bit strings of arbitrary length and nu and nm be the output length of collision-resistant hash functions, Hu:0,1⟶0,1nu and Hm:0,1⟶0,1nm. The signature scheme is defined by the following algorithms.Setup: a secretα∈ℤp and generator g of G are chosen at random. Then, set the value g1=gα and choose g2 randomly in G. Additionally, pick elements u′, m′∈G randomly and vectors U=ui, M=mi of length nu and nm, where ui and mi are randomly chosen from G. The public parameters are MPK=G,GT,e,g,g1,g2,u′,U,m′,M and the master secret key is MSK=g2α.Extract: letU be a bit string of length nu representing an identity and let Ui be the ith bit of U. Define U¯⊂1,…,nu to be the set of indices i such that Ui=1. A private key for identity U is generated as follows. First, choose a random ru∈ℤp. Then, compute(3)skU=dU=d1,d2=g2αu′∏i∈U¯uiru,gru.Sign: letm be a bit string of length nm representing a message. Furthermore, let M¯⊂1,…,nm be a set of indices j such that mj=1.A signature ofU on m is constructed as follows: First, pick a random rm∈ℤp. Then, compute(4)σ=σ0,σ1,σ2=g2αu′∏i∈U¯uirum′∏j∈M¯mjrm,gru,grm.Verify: suppose we wish to check ifσ=σ0,σ1,σ2 is a valid signature of an identity U on m. The signature is accepted if it holds that(5)eσ0,g=eg2,g1eu′∏i∈U¯ui,σ1⋅em′∏j∈M¯mj,σ2.


## 2.2.2. The Modified Signature Scheme

In Paterson’s IBS scheme, we find one element of the signature (σ1) is a part of the private key (d2) and it is not allowed in the strictest sense. Thus, we randomize the first two elements, including the secret key part of the original signature. Let Σ=Setup,Extract,Sign,Verify be Paterson’s IBS scheme, and the new IBS scheme Σ′=Setup′,Extract′,Sign′,Verify′ is as follows:Setup′ and Extract′ are the same as Setup and Extract, respectively.Sign′: choose random ru′,rm∈ℤp and compute(6)σ=σ0,σ1,σ2=σ0⋅u′∏i∈U¯uiru′,σ1⋅gru′,σ2.Verify′: we can check the validity of the signature by the following equation:(7)eσ0,g=?eg2,g1eu′∏i∈U¯ui,σ1⋅em′∏j∈M¯mj,σ2.If the equation holds, then the signature is valid. Otherwise, it is invalid.The modified signature scheme is existentially unforgeable and the security proof is almost the same as stated in [16], we will not prove it again. We use the following theorem to show that.Theorem 1.
The modified identity-based signature scheme is existentially unforgeable if the CDH assumption holds.


## 2.2.3. The Encryption Scheme

In the ElGamal encryption scheme, KeyGen generates a pair of keysSK,PK=α,gα, where g is a generator of G. Enc takes as input PK, a message m, and outputs ciphertext C=C1,C2=mPKt,gt, where t is randomly chosen from G. Dec takes as input C, the secret key SK, and outputs the message m=C1/C2α=m.


## 3. Verifiably Encrypted Identity-Based Signature

Verifiable encrypted identity-based signature (VEIS) is an encrypted identity-based signature, allowing its validity to be checked without decryption. We encrypt the identity-based signature with the public key encryption scheme. In fact, our scheme is a weak version of the identity-based verifiably encrypted signature scheme as stated in [18]; thus, we call it verifiably encrypted identity-based signature (VEIS). Informally, the VEIS system works as follows. A private key generator (PKG) generates private keys for the signers, and a key generator (KG) generates keys pairs for the adjudicator. A signer generates a signature on a message with a signing key associated with his identity, then encrypts it with the adjudicator’s public key, and obtains a VEIS. A verifier can publicly check whether the VEIS is valid. The adjudicator can decrypt VEIS with his private key and get the original signature. We now present our definition of VEIS, as well as several properties.


### 3.1. Modelling VEIS

Formally, a VEIS schemeVEIS=Setup,SKG,VESign,VEVer,Adj,Ver is defined as follows.Setup: it takes as input a security parameter1λ and then outputs two pairs of keys, MSK,MPK for PKG and SKT,PKT for the adjudicator.SKG: PKG inputs1λ, a master secret key MSK, and a signer’s identity U and outputs a private key skU⟵SKG1λ,MSK,U for the signer.VESign: it takes as input a signing keyskU of identity U and a message m; a signer first generates a signature σ and then he encrypts it with the public key PKT and outputs a VEIS ω⟵VESignm,skU,PKT.VEVer: deterministic algorithm VEVer takes as input a messagem, a VEIS ω, and verification keys U, PKT, and MPK and then outputs a bit b⟵VEVerm,ω,MPK,PKT,U, where b∈0,1. If b=1, then VEIS is valid. Otherwise, it is invalid.Adj: the adjudicator takes as inputω and SKT, decrypts VEIS, and then obtains a signature σ⟵Adjω,SKT.Ver: a verifier can check whether the signature is valid. That is,Verm,σ,MPK,U=b, where b∈0,1. If b=1, the signature is valid. Otherwise, the signature is invalid.


### 3.2. Security Definitions

In [11], Boneh et al. proposed two security definitions of verifiably encrypted signature (VES), i.e., unforgeability and opacity. Unforgeability means that no one can forge a VES without the signing key. Opacity guarantees that no one can extract a valid signature from a VES without the adjudicator’s private key. In fact, we find that the VES scheme in [11] missed an important property, i.e., extractability. Extractability means that a valid signature can be extracted from a VES if it passes the check. And we require that extractability must hold even when the master public key and encrypted signatures are maliciously generated.We now formalize three security definitions of VEIS, i.e., unforgeability, opacity, and extractability. They are all defined in games which are played by a challenger and an adversary. Besides, we define the following oracles:(i)
Signing key oracle: the adversary can make a query for a private key associated with an identityU of a signer, the challenger first gets the master key, runs SKG, and then responds with the private key skU.(ii)
VEIS oracle: the adversary can make a query for a VEIS on messagem of an identity U; the challenger first gets a private key of U, runs VESign, and responds with a VEIS ω.(iii)
Adjudication oracle: the adversary can make a query for a signature by providing a messagem, a VEIS ω, and an identity U. The challenger first gets the decryption key, runs Adj, and responds with a signature σ.Then, the security definitions are as follows.Definition 3.
Unforgeability is defined by the gameGameForgeλ. The involved parties in the game are a challenger and an adversary A.(i)
Setup: the challenger sets up the system, generates the public parameters, and sends them toA.(ii)
Query:A submits an identity U to Signing Key Oracle and obtains a signing key skU. A can make at most q1 queries for signing keys. A submits an identity U, a message m to VEIS Oracle, and obtains a VEIS ω. A can make at most q2 queries for VEIS. A submits a message m, a VEIS ω, and an identity U to Adjudication Oracle and obtains a signature σ. A can make at most q3 queries for signatures.(iii)
Forge: finally,A submits a tuple m∗,ω∗,U∗ to the challenger, where the adversary never queried Signing Key Oracle at U∗, VEIS Oracle at m∗,U∗, or Adjudication Oracle at m∗,ω∗,U∗. If VEVerm∗,ω∗,MPK,PKT,U∗=1, A wins in the above game.
A VEIS scheme is unforgeable if for any probabilistic polynomial time (PPT) adversaryA, the probability that A wins in the above game is negligible.Definition 4.
pacity is defined by the gameGameOpacλ as follows. Similarly, a challenger and an adversary get involved in the game.(i)
Setup: the challenger sets up the system, generates the public parameters, and sends them toA.(ii)
Query:A submits an identity U to Signing Key Oracle and obtains a signing key skU. A can make at most q1 queries for signing keys. A submits an identity U, a message m to VEIS Oracle, and obtains a VEIS ω. A can make at most q2 queries for VEIS. A submits a message m, a VEIS ω, and an identity U to Adjudication Oracle and obtains a signature σ. A can make at most q3 queries for signatures.(iii)
Forge: finally,A submits a tuple m∗,σ∗,U∗ to the challenger, where the adversary never queried Signing Key Oracle at U∗, or Adjudication Oracle at m∗,ω∗,U∗, and A can get ω∗ from VEIS Oracle. If σ∗ is a valid signature on m∗ of identity U∗, A wins in the above game.
A VEIS scheme is opaque if for any PPT adversaryA, the probability that A wins in the above game is negligible.Definition 5.
Extractability is defined by the gameGameExtrλ, which involves a challenger and an adversary A.(i)
Setup: the challenger sets up the system, generates the public parameters, and sends them toA.(ii)
Query:A submits an identity U to Signing Key Oracle and obtains a signing key skU. A submits a message m, a VEIS ω, and an identity U to Adjudication Oracle and obtains a signature σ.(iii)
Forge:A submits a tuple m∗,ω∗,U∗,MPK∗ to the challenger.(iv)
Extract: the challenger runs Adj and getsσ∗. If we have VEVerm∗,ω∗,MPK∗,PKT,U∗=1 and Verσ∗,m∗,MPK∗,U∗=0, which means that the signature σ∗ is invalid, then A wins in the above game.
A VEIS scheme is extractable if for all PPT adversariesA, the probability that adversaries wins in the above game is negligible.
We require that if a VEIS scheme satisfies the unforgeability, opacity, and extractability, then it is secure.


### 3.3. The Proposed VEIS Scheme

We now present the concrete VEIS scheme. A VEIS scheme consists of following algorithms.Setup: it takes as input a security parameter1λ and generates the system parameters. Let G and GT be groups of prime order p, g be a generator of G, and e be a bilinear map; that is, e:G×G⟶GT. An identity for a signer is denoted by U. We assume that the length of the identity is nu. If it is not, then we use a hash function Hu:0,1⟶0,1nu to obtain nu-length identity. Then, choose nu-length vectors U=ui and nm-length vector M=mj at random, where ui, mj∈G. Besides, pick random u′, m′∈G. Choose random α1∈ℤp as the secret value. Compute g1=gα1. Choose g2∈G randomly. Then, set the master secret key MSK=g2α1 and the master public key MPK=G,GT,e,g,g1,g2,u′,U,m′,M. Besides, choose random αT∈ℤp and then set the private key for adjudication as SKT=αT, and the public key is PKT=gαT.SKG: it takes as input an identity of a signer,U, and the master secret key MSK and outputs a private key for signing as follows. First, let U¯⊂1,…,nu be the set of indices i such that Ui=1, where Ui is the ith bit of U. Then, choose a random ru∈ℤp and compute(8)skU=dU=g2α1u′∏i∈U¯uiru,gru.VESign: it takes as input a signing keydU and a message m and generates a signature as follows. Let M¯⊂1,…,nm be the set of indices j such that mj=1, where mj is the jth bit of m. Then, choose a random ru′,rm∈ℤp and construct a signature by computing(9)σ0=g2α1u′∏i∈U¯uiruu′∏i∈U¯uiru′⋅m′∏j∈M¯mjrm,σ1=grugru′,σ2=grm,σ=σ0,σ1,σ2.Then, we construct a VEIS as follows. In fact, sinceσ1 and σ2 are independent with the message and identity U1, we only need to encrypt σ0. Choose a random t∈ℤp and construct the VEIS by computing(10)ω1=PKTtσ0,=PKTtg2α1u′∏i∈U¯uiru+ru′m′∏j∈M¯mjrm,ω2=gt,ω3=σ1=gru+ru′,ω4=σ2=grm,ω=ω1,ω2,ω3,ω4.VEVer: if the following equation holds:(11)eω1,g=ePKT,ω2eg2,g1eu′∏i∈U¯ui,ω3em′∏j∈M¯mj,ω4,then, the VEIS is valid and the verifier outputs 1. Otherwise, he outputs 0.Adj: it takes as inputω and SKT=αT and outputs a signature by computing(12)σ0=ω1ω2αT,σ1=ω3,σ2=ω4,σ=σ0,σ1,σ2.Ver: it checks whetherσ=σ0,σ1,σ2 is valid. If the equation(13)eσ0,g=eg2,g1eu′∏i∈U¯ui,σ1em′∏j∈M¯mj,σ2,holds, then the signature is valid and Ver outputs 1. Otherwise, Ver outputs 0 to show σ is invalid.Our scheme is secure in the standard model, and the security proof will be shown in the next section.


## 3.1. Modelling VEIS

Formally, a VEIS schemeVEIS=Setup,SKG,VESign,VEVer,Adj,Ver is defined as follows.Setup: it takes as input a security parameter1λ and then outputs two pairs of keys, MSK,MPK for PKG and SKT,PKT for the adjudicator.SKG: PKG inputs1λ, a master secret key MSK, and a signer’s identity U and outputs a private key skU⟵SKG1λ,MSK,U for the signer.VESign: it takes as input a signing keyskU of identity U and a message m; a signer first generates a signature σ and then he encrypts it with the public key PKT and outputs a VEIS ω⟵VESignm,skU,PKT.VEVer: deterministic algorithm VEVer takes as input a messagem, a VEIS ω, and verification keys U, PKT, and MPK and then outputs a bit b⟵VEVerm,ω,MPK,PKT,U, where b∈0,1. If b=1, then VEIS is valid. Otherwise, it is invalid.Adj: the adjudicator takes as inputω and SKT, decrypts VEIS, and then obtains a signature σ⟵Adjω,SKT.Ver: a verifier can check whether the signature is valid. That is,Verm,σ,MPK,U=b, where b∈0,1. If b=1, the signature is valid. Otherwise, the signature is invalid.


## 3.2. Security Definitions

In [11], Boneh et al. proposed two security definitions of verifiably encrypted signature (VES), i.e., unforgeability and opacity. Unforgeability means that no one can forge a VES without the signing key. Opacity guarantees that no one can extract a valid signature from a VES without the adjudicator’s private key. In fact, we find that the VES scheme in [11] missed an important property, i.e., extractability. Extractability means that a valid signature can be extracted from a VES if it passes the check. And we require that extractability must hold even when the master public key and encrypted signatures are maliciously generated.We now formalize three security definitions of VEIS, i.e., unforgeability, opacity, and extractability. They are all defined in games which are played by a challenger and an adversary. Besides, we define the following oracles:(i)
Signing key oracle: the adversary can make a query for a private key associated with an identityU of a signer, the challenger first gets the master key, runs SKG, and then responds with the private key skU.(ii)
VEIS oracle: the adversary can make a query for a VEIS on messagem of an identity U; the challenger first gets a private key of U, runs VESign, and responds with a VEIS ω.(iii)
Adjudication oracle: the adversary can make a query for a signature by providing a messagem, a VEIS ω, and an identity U. The challenger first gets the decryption key, runs Adj, and responds with a signature σ.Then, the security definitions are as follows.Definition 3.
Unforgeability is defined by the gameGameForgeλ. The involved parties in the game are a challenger and an adversary A.(i)
Setup: the challenger sets up the system, generates the public parameters, and sends them toA.(ii)
Query:A submits an identity U to Signing Key Oracle and obtains a signing key skU. A can make at most q1 queries for signing keys. A submits an identity U, a message m to VEIS Oracle, and obtains a VEIS ω. A can make at most q2 queries for VEIS. A submits a message m, a VEIS ω, and an identity U to Adjudication Oracle and obtains a signature σ. A can make at most q3 queries for signatures.(iii)
Forge: finally,A submits a tuple m∗,ω∗,U∗ to the challenger, where the adversary never queried Signing Key Oracle at U∗, VEIS Oracle at m∗,U∗, or Adjudication Oracle at m∗,ω∗,U∗. If VEVerm∗,ω∗,MPK,PKT,U∗=1, A wins in the above game.
A VEIS scheme is unforgeable if for any probabilistic polynomial time (PPT) adversaryA, the probability that A wins in the above game is negligible.Definition 4.
pacity is defined by the gameGameOpacλ as follows. Similarly, a challenger and an adversary get involved in the game.(i)
Setup: the challenger sets up the system, generates the public parameters, and sends them toA.(ii)
Query:A submits an identity U to Signing Key Oracle and obtains a signing key skU. A can make at most q1 queries for signing keys. A submits an identity U, a message m to VEIS Oracle, and obtains a VEIS ω. A can make at most q2 queries for VEIS. A submits a message m, a VEIS ω, and an identity U to Adjudication Oracle and obtains a signature σ. A can make at most q3 queries for signatures.(iii)
Forge: finally,A submits a tuple m∗,σ∗,U∗ to the challenger, where the adversary never queried Signing Key Oracle at U∗, or Adjudication Oracle at m∗,ω∗,U∗, and A can get ω∗ from VEIS Oracle. If σ∗ is a valid signature on m∗ of identity U∗, A wins in the above game.
A VEIS scheme is opaque if for any PPT adversaryA, the probability that A wins in the above game is negligible.Definition 5.
Extractability is defined by the gameGameExtrλ, which involves a challenger and an adversary A.(i)
Setup: the challenger sets up the system, generates the public parameters, and sends them toA.(ii)
Query:A submits an identity U to Signing Key Oracle and obtains a signing key skU. A submits a message m, a VEIS ω, and an identity U to Adjudication Oracle and obtains a signature σ.(iii)
Forge:A submits a tuple m∗,ω∗,U∗,MPK∗ to the challenger.(iv)
Extract: the challenger runs Adj and getsσ∗. If we have VEVerm∗,ω∗,MPK∗,PKT,U∗=1 and Verσ∗,m∗,MPK∗,U∗=0, which means that the signature σ∗ is invalid, then A wins in the above game.
A VEIS scheme is extractable if for all PPT adversariesA, the probability that adversaries wins in the above game is negligible.
We require that if a VEIS scheme satisfies the unforgeability, opacity, and extractability, then it is secure.


## 3.3. The Proposed VEIS Scheme

We now present the concrete VEIS scheme. A VEIS scheme consists of following algorithms.Setup: it takes as input a security parameter1λ and generates the system parameters. Let G and GT be groups of prime order p, g be a generator of G, and e be a bilinear map; that is, e:G×G⟶GT. An identity for a signer is denoted by U. We assume that the length of the identity is nu. If it is not, then we use a hash function Hu:0,1⟶0,1nu to obtain nu-length identity. Then, choose nu-length vectors U=ui and nm-length vector M=mj at random, where ui, mj∈G. Besides, pick random u′, m′∈G. Choose random α1∈ℤp as the secret value. Compute g1=gα1. Choose g2∈G randomly. Then, set the master secret key MSK=g2α1 and the master public key MPK=G,GT,e,g,g1,g2,u′,U,m′,M. Besides, choose random αT∈ℤp and then set the private key for adjudication as SKT=αT, and the public key is PKT=gαT.SKG: it takes as input an identity of a signer,U, and the master secret key MSK and outputs a private key for signing as follows. First, let U¯⊂1,…,nu be the set of indices i such that Ui=1, where Ui is the ith bit of U. Then, choose a random ru∈ℤp and compute(8)skU=dU=g2α1u′∏i∈U¯uiru,gru.VESign: it takes as input a signing keydU and a message m and generates a signature as follows. Let M¯⊂1,…,nm be the set of indices j such that mj=1, where mj is the jth bit of m. Then, choose a random ru′,rm∈ℤp and construct a signature by computing(9)σ0=g2α1u′∏i∈U¯uiruu′∏i∈U¯uiru′⋅m′∏j∈M¯mjrm,σ1=grugru′,σ2=grm,σ=σ0,σ1,σ2.Then, we construct a VEIS as follows. In fact, sinceσ1 and σ2 are independent with the message and identity U1, we only need to encrypt σ0. Choose a random t∈ℤp and construct the VEIS by computing(10)ω1=PKTtσ0,=PKTtg2α1u′∏i∈U¯uiru+ru′m′∏j∈M¯mjrm,ω2=gt,ω3=σ1=gru+ru′,ω4=σ2=grm,ω=ω1,ω2,ω3,ω4.VEVer: if the following equation holds:(11)eω1,g=ePKT,ω2eg2,g1eu′∏i∈U¯ui,ω3em′∏j∈M¯mj,ω4,then, the VEIS is valid and the verifier outputs 1. Otherwise, he outputs 0.Adj: it takes as inputω and SKT=αT and outputs a signature by computing(12)σ0=ω1ω2αT,σ1=ω3,σ2=ω4,σ=σ0,σ1,σ2.Ver: it checks whetherσ=σ0,σ1,σ2 is valid. If the equation(13)eσ0,g=eg2,g1eu′∏i∈U¯ui,σ1em′∏j∈M¯mj,σ2,holds, then the signature is valid and Ver outputs 1. Otherwise, Ver outputs 0 to show σ is invalid.Our scheme is secure in the standard model, and the security proof will be shown in the next section.


## 4. Optimistic Fair Exchange in Cloud-Assisted CPSes

In this section, we construct optimistic fair exchange in cloud-assisted CPSes based on the proposed VEIS scheme. The system model is shown in Figure2. Two parties (known as Alice and Bob) may want to exchange their signatures on digital goods in cloud. They first get their private keys from a private key generator. Then, they perform our optimistic fair exchange protocol and get the signature of each other fairly. If there exist disputes, they can ask the TTP for arbitration.Figure 2
System model.


### 4.1. Optimistic Fair Exchange Protocol

It is more straightforward to design the fair exchange protocol with online TTP than optimistic fair exchange (fair exchange protocol with offline TTP). However, optimistic fair exchange is more efficient since it greatly reduces the workload on the TTP. In the optimistic fair exchange protocol, the TTP only involves in the exchange when someone attempts to cheat. And TTP in our protocol will not get the original signature of the parties in the exchange. Without loss of generality, we assume Alice and Bob have agreed on two filesmA and mB, and Alice is the protocol initiator. The concrete protocol is as follows:(i)
Initialization: take as input security parameter1λ, run Setup1λ, and output master public key MPK=G,GT,e,g,g1,g2,u′,U,m′,M and the master secret key MSK=g2α1. Besides, the TTP chooses random αT∈ℤp, and then he sets a key pair for adjudication as SKT,PKT=αT,gαT. Similarly, A and B choose random αA,αB∈ℤp, and then set their key pairs as SKA,PKA=αA,gαA and SKB,PKB=αB,gαB, respectively.(ii)
Registration: a user can register with his identityu and obtain a signing key. Let u be a bit string of length nu and let ui be the ith bit of u. Define U¯⊂1,…,nu to be the set of indices i such that ui=1. The signing key for identity u is computed as follows:(14)skU=dU=d1,d2=g2α1u′∏i∈U¯uiru,gru.(iii)
Exchange: letuA and uB be identities of A and B, respectively. Then Alice and Bob will obtain their signing keys duA=dA,1,dA,2 and duB=dB,1,dB,2, respectively. The time t1 denotes the maximum time Alice can wait, and the time t2 denotes the longest the Bob can wait. Then, the optimistic fair exchange of identity-based signatures is as follows:(1) Alice first generates her identity-based signature (onmA) as(15)σA=σA,0,σA,1,σA,2=g2α1u′∏i∈U¯Auiru1+ru1′m′∏j∈M¯Amjrm1,gru1+ru1′,grm1.Then, she encrypts it with the new public keyPK=PKT⋅PKB=gαT+αB and obtains(16)ωA,1=PKtσA,0,ωA,2=gt,ωA,3=σA,1=gru1+ru1′,ωA,4=σA,2=grm1,ωA=ωA,1,ωA,2,ωA,3,ωA,4.Then, she sendsωAmB to Bob.(2) Bob quits if he waited more thant2. Otherwise, after receiving ωA∥mB from Alice, Bob checks whether the following equation holds:(17)eωA,1,g=?ePK,ωA,2eg2,g1eu′∏i∈U¯Aui,ωA,3em′∏j∈M¯Amj,ωA,4.If the equation holds, thenωA is valid and it implies that the identity-based signature σA is valid as well. Bob generates his identity-based signature (on mB), encrypts it with the new public key PK=PKT⋅PKA=gαT+αA, and obtains(18)ωB,1=PKtσB,0,ωB,2=gt,ωB,3=σB,1=gru1+ru1′,ωB,4=σB,2=grm1,ωB=ωB,1,ωB,2,ωB,3,ωB,4.Then Bob sendsωBmA to Alice.(3)
Alice invokes ProtocolAbort and then quits if she waited more than t1. Otherwise, within the time t1, Alice receives ωBmA from Bob and checks whether it is valid by the following equation:(19)eωB,1,g=?ePK,ωB,2eg2,g1eu′∏i∈U¯Bui,ωB,3em′∏j∈M¯Bmj,ωB,4.If the equation holds, Bob’s signature is valid and Alice sends her identity-based signatureσA to Bob. Otherwise, Alice invokes Protocol Abort and then quits.(4)
Bob invokes ProtocolResolve if he waited more than t2. Otherwise, within the time t2, Bob receives σA from Alice and checks it. If it is valid, Bob sends his identity-based signature σB to Alice. Otherwise, Bob invokes Protocol Resolve and then quits.(5)
Alice invokes ProtocolResolve if she waited more than t1. Otherwise, within the time t1, Alice receives σB from Bob and checks whether it is valid. If Bob’s signature is valid, the protocol ends successfully. Otherwise, Alice invokes Protocol Resolve and then quits.(i)
Abort protocol:(a)
Alice sends an abort commandAlice,Bob,abort to TTP.(b)
The TTP checks the record if there have a command of resolve from Bob.(c)
If not, the TTP sends acceptation message to Alice and stores the abort command into record. Otherwise, the TTP sends Bob’s signatureωB′.(ii)
Resolve protocol: Alice and Bob can use the sameResolve protocol. For convenience, we use Bob as an example to describe the protocol.(a)
Bob encryptsσB with the public key PKA=gαA and obtains(20)ωB,1′=PKAt′σB,0,ωB,2′=gt′,ωB,3′=σB,1=gru2+ru2′,ωB,4′=σB,2=grm2,ωB′=ωB,1′,ωB,2′,ωB,3′,ωB,4′.Then he submits a resolve commandAlice,Bob,ωA∥mB,ωB′,resolve to TTP.(b)
The TTP checks the record if there is a command from Alice to ask abort the exchange. If it exists, the TTP sends a rejection message.(c)
If not, the TTP first checks whetherωA=ωA,1,ωA,2,ωA,3,ωA,4 and ωB′=ωB,1′,ωB,2′,ωB,3′,ωB,4′ are valid by the following equations:(21)eωA,1,g=?eg2,g1eu′∏i∈U¯Aui,ωA,3ePK,ωA,2em′∏j∈M¯Amj,ωA,4,eωB,1′,g=?eg2,g1eu′∏i∈U¯Bui,ωB,3′ePKA,ωB,2′em′∏j∈M¯Bmj,ωB,4′.If either of the equations does not hold, then the TTP refuses the request from Bob. Otherwise, the TTP decryptsωA with its private key and obtains a new VEIS by computing(22)ωA,1′=ωA,1ωA,2αT=PKBtg2α1u′∏i∈U¯Auiru1+ru1′m′∏j∈M¯Amjrm1,ωA,2′=ωA,2=gt,ωA,3=ωA,3=gru1+ru1′,ωA,4′=ωA,4=grm1.Next TTP returnsωA′=ωA,1′,ωA,2′,ωA,3′,ωA,4′ to Bob and sends ωB′ to Alice. Meanwhile, the TTP stores this command into record.(d)
Bob can decryptωA′ with his private key and obtains Alice’s signature σA by computing(23)σA,0=ωA,1′ωA,2′αB=g2α1u′∏i∈U¯Auiru1+ru1′m′∏j∈M¯Amjrm1,σA,1=ωA,3′=gru1+ru1′,σA,2=ωA,3′=grm1,σA=σA,0,σA,1,σA,2.


### 4.2. Security

In fact, the security of our protocol can be reduced to the security of the VEIS scheme as stated in [9]. Therefore, we mainly consider the following questions. Can anyone forge a valid original signature? Can anyone forge a valid VEIS? Given a VEIS, can anyone extract a valid signature from it? And there is an extra question which is missed in [9, 10]: Can anyone forge a valid VEIS while the underlying signature is invalid? The above questions are the basis of the security properties. Therefore, we will show that our scheme satisfies unforgeability, opacity, and extractability by the following theorems.Theorem 2.
Our VEIS scheme is unforgeable.Proof.
In fact, ifA forges a valid VEIS ω∗ (on m∗) of identity U∗, he breaks the unforgeability of our VEIS scheme, and we can construct an adversary B that breaks the existential unforgeability of the underlying signature scheme. Therefore, the unforgeability of our VEIS scheme can be reduced to the underlying IBS scheme, which is slightly different from Paterson’s IBS scheme. We now prove Theorem 2 by the following two lemmas.Lemma 1.
Our VEIS scheme is unforgeable if the underlying signature scheme is existentially unforgeable.Proof.
If there exists an adversaryA that forges a tuple m∗,ω∗,U∗ with a nonnegligible probability ϵ and it holds that VEVerm∗,ω∗,MPK,PKT,U∗=1, then A breaks the unforgeability of the VEIS scheme. And we can construct an adversary B that breaks the existential unforgeability of the underlying signature scheme.
We assume thatA and B play the game GameForgeλ, and B simulates the challenger and tries to break the underlying signature scheme. We now show how to construct B.Setup:B runs algorithm Setup and gets the master secret key MSK=g2α1, the master public key MPK=G,GT,e,g,g1,g2,u′,U,m′,M, the adjudicator’s public key PKT=gαT, and adjudicator’s private key SKT=αT. Then he sends MPK and PKT to A, which are indistinguishable from the real ones.Query:B simulates oracles as follows:(a)
Simulation of signing key oracle: whenA submits an identity U of a signer and requests a private key, B chooses ru at random and computes(24)skU=dU=g2α1u′∏i∈U¯uiru,gru,
and then he sends it toA.
(b)
Simulation of VEIS oracle: whenA submits a message m and an identity U and requests a VEIS, B first gets a private key of U as he does in Simulation of Signing Key Oracle, and he generates the signature as follows:(25)σ0=g2α1u′∏i∈U¯uiruu′∏i∈U¯uiru′m′∏j∈M¯mjrm,σ1=grugru′,σ2=grm,σ=σ0,σ1,σ2.
Then, he encrypts the signature withPKT by(26)ω1=PKTtσ0=PKTtg2α1u′∏i∈U¯uiru+ru′m′∏j∈M¯mjrm,ω2=gt,ω3=σ1=gru+ru′,ω4=σ2=grm.
Finally, he sendsω=ω1,ω2,ω3,ω4 to A.
(c)
Simulation of adjudication oracle: whenA submits a message m, a VEIS ω=ω1,ω2,ω3,ω4, and an identity U and requests a signature, B decrypts the VEIS as follows:(27)σ0=ω1ω2αT,σ1=ω3,σ2=ω4.
Then, he sends the signatureσ=σ0,σ1,σ2 to A.
The simulation above is perfect sinceB does it honestly.
Forge: finally,A submits a tuple m∗,ω∗,U∗ to B, where the adversary has never queried Signing Key Oracle at U∗, VEIS Oracle at m∗,U∗, or Adjudication Oracle at m∗,ω∗,U∗. If VEVerm∗,ω∗,MPK,PKT,U∗=1, then we have Verm∗,σ∗,MPK,U∗=1 (it implies the extractability of VEIS and we will prove this later), and B can decrypt the VEIS and obtain a valid signature as follows:(28)σ0∗=ω1∗ω2∗αT,σ1∗=ω3∗,σ2∗=ω4∗,σ∗=σ0∗,σ1∗,σ2∗.
Thus,B forges a valid signature σ∗=σ0∗,σ1∗,σ2∗ with a nonnegligible probability ϵ. This completes the proof.Lemma 2.
The modified signature scheme is existentially unforgeable.
The proof is almost the same as stated in [14], and we use Theorem 1 to show that.Theorem 3.
Our VEIS scheme is opaque if the aggregate extraction assumption holds, and the underlying signature scheme is existentially unforgeable.Proof.
Suppose adversaryA breaks the opacity of the VEIS scheme with nonnegligible probability ϵ, then we can construct an adversary B that solves the aggregate extraction problem. A and B play the game GameOpacλ, and B simulates the challenger.
The aggregate extraction problem: giveng, ga, gb, gβ, gδ, and gab+βδ, compute gab.
We now constructB as follows:Setup.B chooses nu-length vectors U=ui, and nm-length vector M=mj at random, where ui, mj∈G. Besides, pick random u′, m′∈G. Then he sets g1=ga, g2=gb, and the master public key MPK=G,GT,e,g,g1,g2,u′,U,m′,M, and public key PKT=gβ. Then he sends MPK and PKT to A, which are indistinguishable from the real ones. Although B does not know MSK=g2a and SKT=β, we can still complete the simulation by playing some tricks.B sets lu=2q1+q2 and lm=2q2 (A can query at most q1 times for private keys and q2 times for VEISs). Then, B chooses x′, z′, nu-length vector X=xi, and nm-length vector Z=zj at random, where x′ and xi are random values in 0,…,lu and z′ and zj are random values in 0,…,lm. Besides, B picks y′, w′, nu-length vector Y=yi, and nm-length vector W=wj, where y′, yi, w′, and wj are random elements in ℤp. Then, B sets u′=g2−luk1+x′gy′, ui=g2xigyi, m′=g2−lmk2+z′gw′, and mj=g2zjgwj, where 0≤k1≤nu and 0≤k2≤nm.Then, define the following functions for easy analysis:(29)F1U=−luk1+x′+∑i∈U¯xi,K1U=y′+∑i∈U¯yi,F2m=−lmk2+z′+∑j∈M¯zj,K2m=w′+∑j∈M¯wj.Query.B simulates oracles as follows:(a)
Simulation of signing key oracle: whenA submits an identity U of a signer and requests a private key, B constructs it as follows:(30)dU=d1,d2=g1−K1U/F1Uu′∏i∈U¯uiru,g1−1/F1Ugru.
Writingr˜u=ru−a/F1U, the private key can be simplified as(31)d1=g1−K1U/F1Uu′∏i∈U¯uiru=g1−K1U/F1Ug2F1UgK1Uru=g2ag2F1UgK1U−a/F1Ug2F1UgK1Uru=g2au′∏i∈U¯uiru−a/F1U=g2au′∏i∈U¯uir˜u,d2=g1−1/F1Ugru=gru−a/F1U=gr˜u.
Therefore, the private keys generated byB are indistinguishable from the real ones. Then, B sends the signing key dU=d1,d2 to A.
(b)
Simulation of VEIS oracle: whenA submits a message mℓ and an identity Uℓ and requests a VEIS, B can use a list Query List≔=∅ to respond. B initializes the list Query List≔=∅ and chooses the random index ℓ∗∈1,…,q2 to guess from which VEIS A extracts a signature in the list. And A has not queried for a signing key at Uℓ∗. If ℓ≠ℓ∗, then B chooses random ru, ru′, and rm in ℤp and constructs VEIS as follows. First, B computes(32)σ0,ℓ=g1−K2mℓ/F2mℓu′∏i∈U¯uiruu′∏i∈U¯uiru′⋅m′∏j∈M¯mjrm=g2au′∏i∈U¯uiru+ru′m′∏j∈M¯mjr˜m,σ1,ℓ=grugru′=gru+ru′,σ2,ℓ=g1−1/F2mgrm=gr˜m,σℓ=σ0,ℓ,σ1,ℓ,σ2,ℓ,
wherer˜m=rm−a/F2mℓ. Then, he chooses random t and encrypts the signature with PKT as follows:(33)ω1,ℓ=PKTtσ0=PKTtg2au′∏i∈U¯uiru+ru′m′∏j∈M¯mjr˜m,ω2,ℓ=gt,ω3,ℓ=σ1,ℓ=gru+ru′,ω4,ℓ=σ2,ℓ=gr˜m.
Ifℓ=ℓ∗, then B chooses random ru, ru′, rm and sets(34)ω1,ℓ∗=gab+βδu′∏i∈U¯uiru+ru′m′∏j∈M¯mjrm=gβδg2au′∏i∈U¯uiru+ru′m′∏j∈M¯mjrm,ω2,ℓ∗=gδ,ω3,ℓ∗=gru+ru′,ω4,ℓ∗=grm.
Finally, he sends the VEISωℓ=ω1,ℓ,ω2,ℓ,ω3,ℓ,ω4,ℓ and ωℓ∗=ω1,ℓ∗,ω2,ℓ∗,ω3,ℓ∗,ω4,ℓ∗ to A and stores the tuple mℓ,σℓ,ωℓ,Uℓ, mℓ∗,σℓ∗,ωℓ∗,Uℓ∗ in QueryList. If one of F1Uℓ=0, F2mℓ=0, F1Uℓ∗≠0, and F2mℓ∗≠0 holds, B stops the game (if one of them holds, B cannot solve his problem). We denote this event by S1. Otherwise, the simulation is perfect.
(c)
Simulation of adjudication oracle: in this phase,A is not allowed to make a query on mℓ∗,ωℓ∗. When A submits a message mℓ′, a VEIS ωℓ′=ω1,ℓ′,ω2,ℓ′,ω3,ℓ′,ω4,ℓ′, and an identity Uℓ′ and requests a signature, B first checks whether the tuple mℓ′,ωℓ′,Uℓ′ is in the list QueryList; if it is not in QueryList, then the VEIS is invalid and B returns ⊥ (if the VEIS is valid, then A forges a valid VEIS, and this contradicts the unforgeability of our VEIS scheme). If the tuple is in the list QueryList and ℓ′=ℓ, then B finds out the tuple Uℓ,mℓ,σℓ,ωℓ and returns σℓ to A. The simulation above is perfect if B has not aborted.
Forge: finally,A outputs a valid signature extracted from the VEIS; that is, σℓ∗=σ0,ℓ∗,σ1,ℓ∗,σ2,ℓ∗ (on message mℓ∗) of identity Uℓ∗ with a nonnegligible probability ϵ. That means B correctly guesses from which VEIS A extracts the identity-based signature, and we denote this event by S2. Then, B solves his problem by computing(35)gab=σ0,ℓ∗σ1,ℓ∗K1Uℓ∗σ2,ℓ∗K2mℓ∗.
Then, the probability thatB has not aborted in the above game is as follows:(36)PrS1∧S2=PrS1PrS2.
The probability thatB correctly guesses the index ℓ∗ is 1/q2, and we deduce PrS1≥1/16q2q1+q2nu+1nm+1 since we use proof skills in [16]. Thus, we have(37)PrS1∧S2≥1q2⋅116q2q1+q2nu+1nm+1=116q22q1+q2nu+1nm+1.
And the probability thatB solves the aggregate extraction problem is at least ε/16q22q1+q2nu+1nm+1, which is nonnegligible.
This completes the proof of opacity.Theorem 4.
Our VEIS scheme is extractable.Proof.
The challenger plays the gameGameExtrλ with an adversary A as follows:Setup: the challenger sets up the system, generates key pairsMSK,MPK, PKT,SKT, and sends the public keys MPK=G,GT,e,g,g1,g2,u′,U,m′,M and PKT=gαT to A.Query: whenA makes queries, the challenger answers as follows:(a)
Signing key oracle:A submits an identity U, then the challenger chooses random rU∈ℤp and computes(38)skU=dU=g2α1u′∏i∈U¯uiru,gru.
Then, he returns it toA.
(b)
Adjudication oracle:A submits a message m, a VEIS ω=ω1,ω2,ω3,ω4, and an identity U, then the challenger first decrypts the VEIS and obtains(39)σ0=ω1ω2αT=g2α1u′∏i∈U¯uiru+ru′m′∏j∈M¯mjrm,σ1=ω3=gru+ru′,σ2=ω4=grm,σ=σ0,σ1,σ2.
Then, he returnsσ=σ0,σ1,σ2 to A.
Forge: finally,A outputs a VEIS ω∗=ω1∗,ω2∗,ω3∗,ω4∗ of the challenge identity U∗ and sends m∗,ω∗,U∗,MPK∗ to the challenger.
Extract: if the given VEISω∗=ω1∗,ω2∗,ω3∗,ω4∗ passes the check, then we have(40)eω1∗,g=ePKT,ω2∗eg2,g1eu′∏i∈U¯ui,ω3∗em′∏j∈M¯mj,ω4∗.
Then, a signature can be extracted by(41)σ0∗=ω1∗ω2∗αT,σ1∗=ω3∗,σ2∗=ω4∗,σ∗=σ0∗,σ1∗,σ2∗.
And we have(42)eσ0∗,g=eω1∗ω2∗αT,g=eω1∗,geω2∗αT,g−1=ePKT,ω2∗eg2,g1eu′∏i∈U¯ui,ω3∗em′∏j∈M¯mj,ω4∗eω2∗,gαT−1=eg2,g1em′∏j∈M¯mj,σ2∗eu′∏i∈U¯ui,σ1∗.
It implies that ifVEVerm∗,ω∗,MPK∗,PKT,U∗=1 holds, then Verm∗,σ∗,MPK∗,U∗=1 always holds as well. Thus, our VEIS scheme is extractable.


### 4.3. Fairness

To show our protocol satisfies fairness, we consider the cases where Alice or Bob cheats in the protocol.(i)
Case 1: Alice has two chances to perform the optimistic fair exchange protocol dishonestly. In step 1, if Alice sends an invalid VEISωA to Bob, then Bob will check whether the verification equation holds. Since ωA is invalid, the equation does not hold. Bob detects that ωA is invalid and stops the protocol. In step 3, after receiving Bob’s signature, Alice does not send her signature σA to Bob or sends an invalid signature to Bob. However, Bob can submit ωA and ωB to the TTP and ask for arbitration. If both ωA and ωB are valid, the TTP decrypts ωA and returns ωA′ to Bob. Then, Bob decrypts ωA′ with his private key and obtains Alice’s signature σA. Therefore, Alice gets no benefits if she cheats in the protocol.(ii)
Case 2: Bob also has two chances to perform the optimistic fair exchange protocol dishonestly. In step 1, after receiving the valid signatureωA from Alice, Bob stops the protocol and asks for arbitration without providing his VEIS ωB or providing an invalid VEIS. However, TTP will detect this and return nothing to Bob. In step 2, after receiving the valid signature σA from Alice, Bob sends an invalid signature to Alice. However, Alice will detect this and refuse to send σA to Bob. Therefore, Bob also gets no benefits if he cheats in the protocol.Besides, the TTP will not get useful information of the exchange parties.


## 4.1. Optimistic Fair Exchange Protocol

It is more straightforward to design the fair exchange protocol with online TTP than optimistic fair exchange (fair exchange protocol with offline TTP). However, optimistic fair exchange is more efficient since it greatly reduces the workload on the TTP. In the optimistic fair exchange protocol, the TTP only involves in the exchange when someone attempts to cheat. And TTP in our protocol will not get the original signature of the parties in the exchange. Without loss of generality, we assume Alice and Bob have agreed on two filesmA and mB, and Alice is the protocol initiator. The concrete protocol is as follows:(i)
Initialization: take as input security parameter1λ, run Setup1λ, and output master public key MPK=G,GT,e,g,g1,g2,u′,U,m′,M and the master secret key MSK=g2α1. Besides, the TTP chooses random αT∈ℤp, and then he sets a key pair for adjudication as SKT,PKT=αT,gαT. Similarly, A and B choose random αA,αB∈ℤp, and then set their key pairs as SKA,PKA=αA,gαA and SKB,PKB=αB,gαB, respectively.(ii)
Registration: a user can register with his identityu and obtain a signing key. Let u be a bit string of length nu and let ui be the ith bit of u. Define U¯⊂1,…,nu to be the set of indices i such that ui=1. The signing key for identity u is computed as follows:(14)skU=dU=d1,d2=g2α1u′∏i∈U¯uiru,gru.(iii)
Exchange: letuA and uB be identities of A and B, respectively. Then Alice and Bob will obtain their signing keys duA=dA,1,dA,2 and duB=dB,1,dB,2, respectively. The time t1 denotes the maximum time Alice can wait, and the time t2 denotes the longest the Bob can wait. Then, the optimistic fair exchange of identity-based signatures is as follows:(1) Alice first generates her identity-based signature (onmA) as(15)σA=σA,0,σA,1,σA,2=g2α1u′∏i∈U¯Auiru1+ru1′m′∏j∈M¯Amjrm1,gru1+ru1′,grm1.Then, she encrypts it with the new public keyPK=PKT⋅PKB=gαT+αB and obtains(16)ωA,1=PKtσA,0,ωA,2=gt,ωA,3=σA,1=gru1+ru1′,ωA,4=σA,2=grm1,ωA=ωA,1,ωA,2,ωA,3,ωA,4.Then, she sendsωAmB to Bob.(2) Bob quits if he waited more thant2. Otherwise, after receiving ωA∥mB from Alice, Bob checks whether the following equation holds:(17)eωA,1,g=?ePK,ωA,2eg2,g1eu′∏i∈U¯Aui,ωA,3em′∏j∈M¯Amj,ωA,4.If the equation holds, thenωA is valid and it implies that the identity-based signature σA is valid as well. Bob generates his identity-based signature (on mB), encrypts it with the new public key PK=PKT⋅PKA=gαT+αA, and obtains(18)ωB,1=PKtσB,0,ωB,2=gt,ωB,3=σB,1=gru1+ru1′,ωB,4=σB,2=grm1,ωB=ωB,1,ωB,2,ωB,3,ωB,4.Then Bob sendsωBmA to Alice.(3)
Alice invokes ProtocolAbort and then quits if she waited more than t1. Otherwise, within the time t1, Alice receives ωBmA from Bob and checks whether it is valid by the following equation:(19)eωB,1,g=?ePK,ωB,2eg2,g1eu′∏i∈U¯Bui,ωB,3em′∏j∈M¯Bmj,ωB,4.If the equation holds, Bob’s signature is valid and Alice sends her identity-based signatureσA to Bob. Otherwise, Alice invokes Protocol Abort and then quits.(4)
Bob invokes ProtocolResolve if he waited more than t2. Otherwise, within the time t2, Bob receives σA from Alice and checks it. If it is valid, Bob sends his identity-based signature σB to Alice. Otherwise, Bob invokes Protocol Resolve and then quits.(5)
Alice invokes ProtocolResolve if she waited more than t1. Otherwise, within the time t1, Alice receives σB from Bob and checks whether it is valid. If Bob’s signature is valid, the protocol ends successfully. Otherwise, Alice invokes Protocol Resolve and then quits.(i)
Abort protocol:(a)
Alice sends an abort commandAlice,Bob,abort to TTP.(b)
The TTP checks the record if there have a command of resolve from Bob.(c)
If not, the TTP sends acceptation message to Alice and stores the abort command into record. Otherwise, the TTP sends Bob’s signatureωB′.(ii)
Resolve protocol: Alice and Bob can use the sameResolve protocol. For convenience, we use Bob as an example to describe the protocol.(a)
Bob encryptsσB with the public key PKA=gαA and obtains(20)ωB,1′=PKAt′σB,0,ωB,2′=gt′,ωB,3′=σB,1=gru2+ru2′,ωB,4′=σB,2=grm2,ωB′=ωB,1′,ωB,2′,ωB,3′,ωB,4′.Then he submits a resolve commandAlice,Bob,ωA∥mB,ωB′,resolve to TTP.(b)
The TTP checks the record if there is a command from Alice to ask abort the exchange. If it exists, the TTP sends a rejection message.(c)
If not, the TTP first checks whetherωA=ωA,1,ωA,2,ωA,3,ωA,4 and ωB′=ωB,1′,ωB,2′,ωB,3′,ωB,4′ are valid by the following equations:(21)eωA,1,g=?eg2,g1eu′∏i∈U¯Aui,ωA,3ePK,ωA,2em′∏j∈M¯Amj,ωA,4,eωB,1′,g=?eg2,g1eu′∏i∈U¯Bui,ωB,3′ePKA,ωB,2′em′∏j∈M¯Bmj,ωB,4′.If either of the equations does not hold, then the TTP refuses the request from Bob. Otherwise, the TTP decryptsωA with its private key and obtains a new VEIS by computing(22)ωA,1′=ωA,1ωA,2αT=PKBtg2α1u′∏i∈U¯Auiru1+ru1′m′∏j∈M¯Amjrm1,ωA,2′=ωA,2=gt,ωA,3=ωA,3=gru1+ru1′,ωA,4′=ωA,4=grm1.Next TTP returnsωA′=ωA,1′,ωA,2′,ωA,3′,ωA,4′ to Bob and sends ωB′ to Alice. Meanwhile, the TTP stores this command into record.(d)
Bob can decryptωA′ with his private key and obtains Alice’s signature σA by computing(23)σA,0=ωA,1′ωA,2′αB=g2α1u′∏i∈U¯Auiru1+ru1′m′∏j∈M¯Amjrm1,σA,1=ωA,3′=gru1+ru1′,σA,2=ωA,3′=grm1,σA=σA,0,σA,1,σA,2.


## 4.2. Security

In fact, the security of our protocol can be reduced to the security of the VEIS scheme as stated in [9]. Therefore, we mainly consider the following questions. Can anyone forge a valid original signature? Can anyone forge a valid VEIS? Given a VEIS, can anyone extract a valid signature from it? And there is an extra question which is missed in [9, 10]: Can anyone forge a valid VEIS while the underlying signature is invalid? The above questions are the basis of the security properties. Therefore, we will show that our scheme satisfies unforgeability, opacity, and extractability by the following theorems.Theorem 2.
Our VEIS scheme is unforgeable.Proof.
In fact, ifA forges a valid VEIS ω∗ (on m∗) of identity U∗, he breaks the unforgeability of our VEIS scheme, and we can construct an adversary B that breaks the existential unforgeability of the underlying signature scheme. Therefore, the unforgeability of our VEIS scheme can be reduced to the underlying IBS scheme, which is slightly different from Paterson’s IBS scheme. We now prove Theorem 2 by the following two lemmas.Lemma 1.
Our VEIS scheme is unforgeable if the underlying signature scheme is existentially unforgeable.Proof.
If there exists an adversaryA that forges a tuple m∗,ω∗,U∗ with a nonnegligible probability ϵ and it holds that VEVerm∗,ω∗,MPK,PKT,U∗=1, then A breaks the unforgeability of the VEIS scheme. And we can construct an adversary B that breaks the existential unforgeability of the underlying signature scheme.
We assume thatA and B play the game GameForgeλ, and B simulates the challenger and tries to break the underlying signature scheme. We now show how to construct B.Setup:B runs algorithm Setup and gets the master secret key MSK=g2α1, the master public key MPK=G,GT,e,g,g1,g2,u′,U,m′,M, the adjudicator’s public key PKT=gαT, and adjudicator’s private key SKT=αT. Then he sends MPK and PKT to A, which are indistinguishable from the real ones.Query:B simulates oracles as follows:(a)
Simulation of signing key oracle: whenA submits an identity U of a signer and requests a private key, B chooses ru at random and computes(24)skU=dU=g2α1u′∏i∈U¯uiru,gru,
and then he sends it toA.
(b)
Simulation of VEIS oracle: whenA submits a message m and an identity U and requests a VEIS, B first gets a private key of U as he does in Simulation of Signing Key Oracle, and he generates the signature as follows:(25)σ0=g2α1u′∏i∈U¯uiruu′∏i∈U¯uiru′m′∏j∈M¯mjrm,σ1=grugru′,σ2=grm,σ=σ0,σ1,σ2.
Then, he encrypts the signature withPKT by(26)ω1=PKTtσ0=PKTtg2α1u′∏i∈U¯uiru+ru′m′∏j∈M¯mjrm,ω2=gt,ω3=σ1=gru+ru′,ω4=σ2=grm.
Finally, he sendsω=ω1,ω2,ω3,ω4 to A.
(c)
Simulation of adjudication oracle: whenA submits a message m, a VEIS ω=ω1,ω2,ω3,ω4, and an identity U and requests a signature, B decrypts the VEIS as follows:(27)σ0=ω1ω2αT,σ1=ω3,σ2=ω4.
Then, he sends the signatureσ=σ0,σ1,σ2 to A.
The simulation above is perfect sinceB does it honestly.
Forge: finally,A submits a tuple m∗,ω∗,U∗ to B, where the adversary has never queried Signing Key Oracle at U∗, VEIS Oracle at m∗,U∗, or Adjudication Oracle at m∗,ω∗,U∗. If VEVerm∗,ω∗,MPK,PKT,U∗=1, then we have Verm∗,σ∗,MPK,U∗=1 (it implies the extractability of VEIS and we will prove this later), and B can decrypt the VEIS and obtain a valid signature as follows:(28)σ0∗=ω1∗ω2∗αT,σ1∗=ω3∗,σ2∗=ω4∗,σ∗=σ0∗,σ1∗,σ2∗.
Thus,B forges a valid signature σ∗=σ0∗,σ1∗,σ2∗ with a nonnegligible probability ϵ. This completes the proof.Lemma 2.
The modified signature scheme is existentially unforgeable.
The proof is almost the same as stated in [14], and we use Theorem 1 to show that.Theorem 3.
Our VEIS scheme is opaque if the aggregate extraction assumption holds, and the underlying signature scheme is existentially unforgeable.Proof.
Suppose adversaryA breaks the opacity of the VEIS scheme with nonnegligible probability ϵ, then we can construct an adversary B that solves the aggregate extraction problem. A and B play the game GameOpacλ, and B simulates the challenger.
The aggregate extraction problem: giveng, ga, gb, gβ, gδ, and gab+βδ, compute gab.
We now constructB as follows:Setup.B chooses nu-length vectors U=ui, and nm-length vector M=mj at random, where ui, mj∈G. Besides, pick random u′, m′∈G. Then he sets g1=ga, g2=gb, and the master public key MPK=G,GT,e,g,g1,g2,u′,U,m′,M, and public key PKT=gβ. Then he sends MPK and PKT to A, which are indistinguishable from the real ones. Although B does not know MSK=g2a and SKT=β, we can still complete the simulation by playing some tricks.B sets lu=2q1+q2 and lm=2q2 (A can query at most q1 times for private keys and q2 times for VEISs). Then, B chooses x′, z′, nu-length vector X=xi, and nm-length vector Z=zj at random, where x′ and xi are random values in 0,…,lu and z′ and zj are random values in 0,…,lm. Besides, B picks y′, w′, nu-length vector Y=yi, and nm-length vector W=wj, where y′, yi, w′, and wj are random elements in ℤp. Then, B sets u′=g2−luk1+x′gy′, ui=g2xigyi, m′=g2−lmk2+z′gw′, and mj=g2zjgwj, where 0≤k1≤nu and 0≤k2≤nm.Then, define the following functions for easy analysis:(29)F1U=−luk1+x′+∑i∈U¯xi,K1U=y′+∑i∈U¯yi,F2m=−lmk2+z′+∑j∈M¯zj,K2m=w′+∑j∈M¯wj.Query.B simulates oracles as follows:(a)
Simulation of signing key oracle: whenA submits an identity U of a signer and requests a private key, B constructs it as follows:(30)dU=d1,d2=g1−K1U/F1Uu′∏i∈U¯uiru,g1−1/F1Ugru.
Writingr˜u=ru−a/F1U, the private key can be simplified as(31)d1=g1−K1U/F1Uu′∏i∈U¯uiru=g1−K1U/F1Ug2F1UgK1Uru=g2ag2F1UgK1U−a/F1Ug2F1UgK1Uru=g2au′∏i∈U¯uiru−a/F1U=g2au′∏i∈U¯uir˜u,d2=g1−1/F1Ugru=gru−a/F1U=gr˜u.
Therefore, the private keys generated byB are indistinguishable from the real ones. Then, B sends the signing key dU=d1,d2 to A.
(b)
Simulation of VEIS oracle: whenA submits a message mℓ and an identity Uℓ and requests a VEIS, B can use a list Query List≔=∅ to respond. B initializes the list Query List≔=∅ and chooses the random index ℓ∗∈1,…,q2 to guess from which VEIS A extracts a signature in the list. And A has not queried for a signing key at Uℓ∗. If ℓ≠ℓ∗, then B chooses random ru, ru′, and rm in ℤp and constructs VEIS as follows. First, B computes(32)σ0,ℓ=g1−K2mℓ/F2mℓu′∏i∈U¯uiruu′∏i∈U¯uiru′⋅m′∏j∈M¯mjrm=g2au′∏i∈U¯uiru+ru′m′∏j∈M¯mjr˜m,σ1,ℓ=grugru′=gru+ru′,σ2,ℓ=g1−1/F2mgrm=gr˜m,σℓ=σ0,ℓ,σ1,ℓ,σ2,ℓ,
wherer˜m=rm−a/F2mℓ. Then, he chooses random t and encrypts the signature with PKT as follows:(33)ω1,ℓ=PKTtσ0=PKTtg2au′∏i∈U¯uiru+ru′m′∏j∈M¯mjr˜m,ω2,ℓ=gt,ω3,ℓ=σ1,ℓ=gru+ru′,ω4,ℓ=σ2,ℓ=gr˜m.
Ifℓ=ℓ∗, then B chooses random ru, ru′, rm and sets(34)ω1,ℓ∗=gab+βδu′∏i∈U¯uiru+ru′m′∏j∈M¯mjrm=gβδg2au′∏i∈U¯uiru+ru′m′∏j∈M¯mjrm,ω2,ℓ∗=gδ,ω3,ℓ∗=gru+ru′,ω4,ℓ∗=grm.
Finally, he sends the VEISωℓ=ω1,ℓ,ω2,ℓ,ω3,ℓ,ω4,ℓ and ωℓ∗=ω1,ℓ∗,ω2,ℓ∗,ω3,ℓ∗,ω4,ℓ∗ to A and stores the tuple mℓ,σℓ,ωℓ,Uℓ, mℓ∗,σℓ∗,ωℓ∗,Uℓ∗ in QueryList. If one of F1Uℓ=0, F2mℓ=0, F1Uℓ∗≠0, and F2mℓ∗≠0 holds, B stops the game (if one of them holds, B cannot solve his problem). We denote this event by S1. Otherwise, the simulation is perfect.
(c)
Simulation of adjudication oracle: in this phase,A is not allowed to make a query on mℓ∗,ωℓ∗. When A submits a message mℓ′, a VEIS ωℓ′=ω1,ℓ′,ω2,ℓ′,ω3,ℓ′,ω4,ℓ′, and an identity Uℓ′ and requests a signature, B first checks whether the tuple mℓ′,ωℓ′,Uℓ′ is in the list QueryList; if it is not in QueryList, then the VEIS is invalid and B returns ⊥ (if the VEIS is valid, then A forges a valid VEIS, and this contradicts the unforgeability of our VEIS scheme). If the tuple is in the list QueryList and ℓ′=ℓ, then B finds out the tuple Uℓ,mℓ,σℓ,ωℓ and returns σℓ to A. The simulation above is perfect if B has not aborted.
Forge: finally,A outputs a valid signature extracted from the VEIS; that is, σℓ∗=σ0,ℓ∗,σ1,ℓ∗,σ2,ℓ∗ (on message mℓ∗) of identity Uℓ∗ with a nonnegligible probability ϵ. That means B correctly guesses from which VEIS A extracts the identity-based signature, and we denote this event by S2. Then, B solves his problem by computing(35)gab=σ0,ℓ∗σ1,ℓ∗K1Uℓ∗σ2,ℓ∗K2mℓ∗.
Then, the probability thatB has not aborted in the above game is as follows:(36)PrS1∧S2=PrS1PrS2.
The probability thatB correctly guesses the index ℓ∗ is 1/q2, and we deduce PrS1≥1/16q2q1+q2nu+1nm+1 since we use proof skills in [16]. Thus, we have(37)PrS1∧S2≥1q2⋅116q2q1+q2nu+1nm+1=116q22q1+q2nu+1nm+1.
And the probability thatB solves the aggregate extraction problem is at least ε/16q22q1+q2nu+1nm+1, which is nonnegligible.
This completes the proof of opacity.Theorem 4.
Our VEIS scheme is extractable.Proof.
The challenger plays the gameGameExtrλ with an adversary A as follows:Setup: the challenger sets up the system, generates key pairsMSK,MPK, PKT,SKT, and sends the public keys MPK=G,GT,e,g,g1,g2,u′,U,m′,M and PKT=gαT to A.Query: whenA makes queries, the challenger answers as follows:(a)
Signing key oracle:A submits an identity U, then the challenger chooses random rU∈ℤp and computes(38)skU=dU=g2α1u′∏i∈U¯uiru,gru.
Then, he returns it toA.
(b)
Adjudication oracle:A submits a message m, a VEIS ω=ω1,ω2,ω3,ω4, and an identity U, then the challenger first decrypts the VEIS and obtains(39)σ0=ω1ω2αT=g2α1u′∏i∈U¯uiru+ru′m′∏j∈M¯mjrm,σ1=ω3=gru+ru′,σ2=ω4=grm,σ=σ0,σ1,σ2.
Then, he returnsσ=σ0,σ1,σ2 to A.
Forge: finally,A outputs a VEIS ω∗=ω1∗,ω2∗,ω3∗,ω4∗ of the challenge identity U∗ and sends m∗,ω∗,U∗,MPK∗ to the challenger.
Extract: if the given VEISω∗=ω1∗,ω2∗,ω3∗,ω4∗ passes the check, then we have(40)eω1∗,g=ePKT,ω2∗eg2,g1eu′∏i∈U¯ui,ω3∗em′∏j∈M¯mj,ω4∗.
Then, a signature can be extracted by(41)σ0∗=ω1∗ω2∗αT,σ1∗=ω3∗,σ2∗=ω4∗,σ∗=σ0∗,σ1∗,σ2∗.
And we have(42)eσ0∗,g=eω1∗ω2∗αT,g=eω1∗,geω2∗αT,g−1=ePKT,ω2∗eg2,g1eu′∏i∈U¯ui,ω3∗em′∏j∈M¯mj,ω4∗eω2∗,gαT−1=eg2,g1em′∏j∈M¯mj,σ2∗eu′∏i∈U¯ui,σ1∗.
It implies that ifVEVerm∗,ω∗,MPK∗,PKT,U∗=1 holds, then Verm∗,σ∗,MPK∗,U∗=1 always holds as well. Thus, our VEIS scheme is extractable.


## 4.3. Fairness

To show our protocol satisfies fairness, we consider the cases where Alice or Bob cheats in the protocol.(i)
Case 1: Alice has two chances to perform the optimistic fair exchange protocol dishonestly. In step 1, if Alice sends an invalid VEISωA to Bob, then Bob will check whether the verification equation holds. Since ωA is invalid, the equation does not hold. Bob detects that ωA is invalid and stops the protocol. In step 3, after receiving Bob’s signature, Alice does not send her signature σA to Bob or sends an invalid signature to Bob. However, Bob can submit ωA and ωB to the TTP and ask for arbitration. If both ωA and ωB are valid, the TTP decrypts ωA and returns ωA′ to Bob. Then, Bob decrypts ωA′ with his private key and obtains Alice’s signature σA. Therefore, Alice gets no benefits if she cheats in the protocol.(ii)
Case 2: Bob also has two chances to perform the optimistic fair exchange protocol dishonestly. In step 1, after receiving the valid signatureωA from Alice, Bob stops the protocol and asks for arbitration without providing his VEIS ωB or providing an invalid VEIS. However, TTP will detect this and return nothing to Bob. In step 2, after receiving the valid signature σA from Alice, Bob sends an invalid signature to Alice. However, Alice will detect this and refuse to send σA to Bob. Therefore, Bob also gets no benefits if he cheats in the protocol.Besides, the TTP will not get useful information of the exchange parties.


## 5. Simulation

In this section, we report several simulations and the results show that our VEIS scheme and optimistic fair exchange protocol are practical. We conducted experiments with Pairing Based Cryptography (PBC,http://crypto.stanford.edu/pbc/) library. The experiments were compiled in C programming language and carried out on Inter(R) Core(TM) Quad CPU Core i7-6700K @ 4.00 GHz. The security parameter was set to be 160, and the length of an element in group G, GT was 512 bits. The efficiency of our VEIS scheme mainly depends on the length of users’ identities, which was chosen from 32 bits to 240 bits to evaluate the performance of our VEIS scheme and optimistic fair exchange protocol.Before performing our experiments, we first compare several VES schemes by theoretical analysis. The results are shown in Table3.LetE, H, and e denote exponent operation time, operation time of hash function, and pairing operation time, and all the other light-weight operations such as additions and multiplications are omitted. We can find the efficiency of our scheme is comparable with other efficient schemes. The VES schemes in [9, 11] are more efficient; however, Boneh’s scheme is PKI-based and Gu’s scheme is not quite secure. Although VES schemes in [14, 15] are more secure, too many hash operations still reduce the efficiency of the schemes. Our VEIS scheme overcomes their weaknesses and is still efficient. The simulation results are shown in the following papers.In Figure3, we show the running time of our VEIS scheme with different length of identities (nu). We do not consider the length of files (nm) since we have the similar results when only changing nm. The length of identities is chosen from 32 bits to 240 bits; that is, nu=32,64,80,160,240. And the full time ranges from 120 ms to 688 ms. The algorithm Setup takes roughly the same processing time, which is the biggest part of full operation time. To the contrary, SKG costs about 3 ms, and the rest algorithms costs about 16 ms for different length of identities. Therefore, once the system is set up, it is very efficient for users to generate their VEISs in cloud. Since the private key generator must distribute all users’ keys, we have to evaluate whether it is suitable for a large number of users who take activities in cloud-assisted CPSes. The length of identity is set to be 160 bits, and Figure 4 shows the results. For cloud data services which have 100000 users, our scheme only takes about 350 seconds to generate their signing keys.Figure 3
Running time of VEIS.Figure 4
SKG time for different users.In Figure5, we show the running time of optimistic fair exchange with different length of identities. In the experiments, we do not consider the communication time which is hard to evaluate due to some subjective factors. The full protocol takes less than 1 second when the length of the identity is set to be 240 bits, and it is quite acceptable. Initialization takes a little more time than other phases; however, we only need to perform it once in the system. When two users exchange their signatures of digital files in cloud, they only need to take 50 or 60 ms to finish the transaction. The above results show that our protocol is efficient and practical in cloud-assisted CPSes.Figure 5
Running time of optimistic fair exchange.


## 6. Conclusion

Optimistic fair exchange in cloud-assisted CPSes is a kind of protocol in which two parties can exchange their signatures of digital content in cloud. In this paper, we constructed such a protocol with a new cryptographic technique, i.e., verifiably encrypted identity-based signature (VEIS), which is based on Paterson’s IBS scheme and ElGamal encryption scheme. Then, we showed that our protocol is secure with the strictest security proof. Additionally, we discussed fairness of our protocol, and the results showed that both two parties obtain each other’s signature or neither of them get anything useful in the protocol. Finally, the results of the simulation showed that our protocol is practical.



---

*Source: 5175076-2019-10-30.xml*