# Identity-Based Proxy Signcryption Protocol with Universal Composability

Authors: Huifang Yu; Zhicang Wang; Jianmin Li; Xinzhe Gao
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Proxy signcryption means that the proxy signcrypter obtains the delegate authorization from the original signcrypter and then signcrypts the specified message on behalf of the original signcrypter. In this paper, we construct an identity-based proxy signcryption protocol (IBPSP) based on the universally composable (UC) framework. In the random oracle model, we prove that this protocol has the semantic security under the gap bilinear Diffie-Hellman and computational Diffie-Hellman assumptions. At the same time, an ideal functionality of the identity-based proxy signcryption protocol is defined in the UC security framework, and we also prove the equivalence between the universally composable identity-based proxy signcryption protocol and its IND-CCA2 and UF-CMA security. Analysis shows this IBPSP has both low computation complexity and semantic security together with UC security.


---

## Body

## 1. Introduction

Proxy signature [1] has the authenticity of signature but cannot guarantee the confidentiality of message. Gamage et al. [2] proposed the first proxy signcryption scheme, which can simultaneously realize two functions of public key encryption and proxy signature. Later, Li and Chen [3] constructed an identity-based proxy signcryption scheme by integrating identity-based cryptosystem and proxy signcryption, but this scheme does not meet the unforgeability and forward security. Chen et al. [4] devised a provably secure identity-based proxy signcryption scheme under the computational Diffie-Hellman and bilinear Diffie-Hellman assumptions. Ming et al. [5] constructed an identity-based proxy signcryption scheme without random oracles and proved its confidentiality and unforgeability. Zhou [6] devised secure identity-based generalized proxy signcryption without random oracles from bilinear pairings which has the properties of public verification in the proxy signcryption mode.The UC security framework [7] can meet the requirement of modular design of protocols. The salient property of UC definitions of security is that they guarantee security even when a secure protocol is composed of an arbitrary set of protocols, or when the protocol is used as a component of an arbitrary system. It is an essential property in a complex and unpredictable environment. Moreover, UC definitions can guarantee security even when an unbounded number of protocol instances are carried out concurrently in an adversarially controlled manner; furthermore, they can guarantee nonmalleability with respect to arbitrary protocols. In the UC framework, a protocol is abstracted as an ideal functionality which is considered as a trusted third party (TTP) for specific tasks. Every player can deliver a command to the ideal functionality in a secure and authentic manner, and the ideal functionality executes the command according to its specification. Informally, one protocol can securely carry out a given ideal functionality if no adversary can obtain more advantages from an attack on an instance of real execution of the protocol than from an attack on an ideal process where the parties only submit their inputs to a TTP with appropriate functionality. In other words, it is required that an instance of real execution can be simulated in the ideal process. A protocol is said to securely realize ideal functionality if any effect caused by an adversary attacking the protocol can be achieved by an adversary attacking the ideal functionality. i.e., when devising the complex protocols, one can allow the involved parties to have secure access to ideal functionalities; when implementing the protocol, each ideal functionality is replaced by one protocol securely realizing the ideal functionality. Any ideal functionality can be UC realized as long as a majority of parties are supposed to be honest.Canetti [8] corrected the ideal functionality definition of digital signature in 2001. Wang et al. [9] defined the ideal functionality of the identity-based signature protocol and simultaneously proved the equivalence between identity-based signature with UC security and classical identity-based signature with EUF-CMA security in an adaptive adversary model. Tian et al. [10] devised composable group communication and solved the composable security problem of multicast group communication. Tian et al. [11] devised secure multiparty computation with the universal composability and realized a fair and secure two-party computation protocol. Thus, they solved the fair and secure two-party computation problem, although Katz deemed that this problem could not be realized. Zhang et al. [12] devised a key exchange protocol and proved its security in the UC security framework. Yuan and Liu [13] devised a universally composable group ownership transfer protocol for RFID tags. Zhao et al. [14, 15] proposed a universally composable group signature protocol and group blind protocol. Li et al. [16] devised self-certified blind signcryption with UC security. Hu et al. [17] proposed a gateway-oriented password-authenticated key exchange protocol with universal composability.Identity-based proxy signcryption is appropriate for applications in electronic governments and electronic commerce [18], such as online proxy auctions or contract signing by an authorized proxy signer. Consider an application such as a bank account owned by a busy boss. So as to withdraw money from their saving account, the boss must sign a withdrawal slip which can only be verified by the bank teller. In this case, when the boss is unable to sign personally, they can delegate their signing power to a proxy signer who can legitimately conduct transactions on their behalf. It is an interesting research problem of how to construct a secure identity-based proxy signcryption protocol applying to a more complex network environment. In this paper, we construct a novel identity-based proxy signcryption protocol (IBPSP) with universal composability, whose semantic security is based on the intractability of the gap bilinear Diffie-Hellman (gap BDH) and computational Diffie-Hellman (CDH) problems. In the random oracle model, we prove its indistinguishability against adaptive chosen-ciphertext attacks (IND-CCA2) and existential unforgeability against adaptive chosen-message attacks (UF-CMA). At the same time, we define the ideal functionality of IBPSP and illustrate the equivalence between the universally composable IBPSP and its IND-CCA2 and UF-CMA security.


## 2. Preliminaries

In this section, we briefly introduce bilinear pairings and several computational problems together with the universally composable (UC) framework.


### 2.1. Bilinear Pairings

LetG
1 denote one cyclic addition group with prime orderq and letG
2 denote one cyclic multiplication group with the same prime order. In addition,P is a generator of additive groupG
1 and e
:
G
1
×
G
1
→
G
2 is a bilinear map with the properties as below:Bilinearity:e
a
U
,
b
V
=
e
U
,
V
a
b for any U
,
V
∈
G
1 and a
,
b
∈
Z
q
∗Nondegeneracy: there existsU
,
V
∈
G
1 such that e
U
,
V
≠
1
G
2, where 1
G
2 is the identity element ofG
2Computability: there is an efficient algorithm to calculatee
U
,
V for any U
,
V
∈
G
1


#### 2.1.1. BDH Problem

Given<
P
,
a
P
,
b
P
,
c
P
> for any a
,
b
,
c
∈
Z
q
∗, the bilinear Diffie-Hellman (BDH) problem is that it is computationally infeasible to determine the value of e
(
P
,
P
)
a
b
c
∈
G
2.


#### 2.1.2. CDH Problem

Given<
P
,
a
P
,
b
P
> for any a
,
b
∈
Z
q
∗, the computational Diffie-Hellman (CDH) problem is that it is computationally infeasible to determine the value of a
b
P
∈
G
1.


#### 2.1.3. DBDH Problem

Given<
P
,
a
P
,
b
P
,
c
P
> for any a
,
b
,
c
∈
Z
q
∗ and X
∈
G
2, the decisional bilinear Diffie-Hellman (DBDH) problem is to decide whether e
(
P
,
P
)
a
b
c
=
X. If it holds, the DBDH oracle O
D
B
D
H returns 1; else, O
D
B
D
H returns 0.


#### 2.1.4. Gap BDH Problem

Given<
P
,
a
P
,
b
P
,
c
P
> for any a
,
b
,
c
∈
Z
q
∗, the gap bilinear Diffie-Hellman (gap BDH) problem is to determine the value of e
(
P
,
P
)
a
b
c
∈
G
2 with the help of O
D
B
D
H.


### 2.2. UC Framework

The UC framework [8] consists of a real-life model, ideal model, and hybrid model. In the UC framework, Z represents the external environment that consists of arbitrary protocols running concurrently with the given protocol. Z generates the inputs to all parties, reads all outputs, and interacts with the adversary in an arbitrary way throughout the computation. A protocol π is said to securely realize an ideal functionality F if, for any real-life adversary A interacting with the protocol, there exists a simulator S such that no Z can distinguish with nonnegligible probability whether it interacts with A and parties running the protocol π or with S and parties interacting with F in the ideal process.Letr
e
a
l
π
,
A
,
Z
k
,
z
,
r denote the output of Z when interacting with the adversary A and parties P
1
,
.
.
.
,
P
n running protocol π on security parameterk, inputz, and random input r
=
r
Z
,
r
A
,
r
1
,
.
.
.
,
r
n (z and r
Z for Z, r
A for A, and r
i for party P
i). Let r
e
a
l
π
,
A
,
Z
k
,
z be the random variable describing r
e
a
l
π
,
A
,
Z
k
,
z
,
r whenr is uniformly chosen. Here r
e
a
l
π
,
A
,
Z is the ensemble(1)
r
e
a
l
π
,
A
,
Z
k
,
z
k
∈
N
,
z
∈
0,1
∗
.Leti
d
e
a
l
F
,
S
,
Z
k
,
z
,
r denote the output of Z after interacting with the adversary S and ideal functionality F on security parameterk, inputz, and random input r
=
r
Z
,
r
S
,
r
F (z and r
Z for Z, r
S for S, and r
F for F). Let i
d
e
a
l
F
,
S
,
Z
k
,
z be the random variable describing i
d
e
a
l
F
,
S
,
Z
k
,
z
,
r whenr is uniformly chosen. Here i
d
e
a
l
F
,
S
,
Z is the ensemble (2)
i
d
e
a
l
F
,
S
,
Z
k
,
z
k
∈
N
,
z
∈
0,1
∗
.Definition 1 (indistinguishability).
Two binary distribution ensembles X and Y are indistinguishable (written X≈Y), if, for anyc
∈
N, there exists k
0
∈
N such that, for all k
>
k
0 and for alla, we have(3)
Pr
⁡
X
k
,
a
=
1
-
Pr
⁡
Y
k
,
a
=
1
<
k
-
c
.Definition 2 (UC simulation).
LetF denote an ideal functionality and let π denote a probabilistic polynomial time protocol. We say that π securely realizes F if, for any adversary A, there exists an ideal-process adversary S such that, for any environment Z, we have (4)
i
d
e
a
l
F
,
S
,
Z
≈
r
e
a
l
π
,
A
,
Z
.Theorem 3 (universal composition).
LetF and G be ideal functionalities. Let π be a protocol in the F-hybrid model and let ρ be a protocol which securely realizes F in the G-hybrid model. Then for any adversary A in the G-hybrid model, there exists an adversary S in the F-hybrid model such that, for any environment Z, we have(5)
r
e
a
l
π
,
S
,
Z
F
≈
r
e
a
l
π
ρ
,
A
,
Z
G
.


## 2.1. Bilinear Pairings

LetG
1 denote one cyclic addition group with prime orderq and letG
2 denote one cyclic multiplication group with the same prime order. In addition,P is a generator of additive groupG
1 and e
:
G
1
×
G
1
→
G
2 is a bilinear map with the properties as below:Bilinearity:e
a
U
,
b
V
=
e
U
,
V
a
b for any U
,
V
∈
G
1 and a
,
b
∈
Z
q
∗Nondegeneracy: there existsU
,
V
∈
G
1 such that e
U
,
V
≠
1
G
2, where 1
G
2 is the identity element ofG
2Computability: there is an efficient algorithm to calculatee
U
,
V for any U
,
V
∈
G
1


### 2.1.1. BDH Problem

Given<
P
,
a
P
,
b
P
,
c
P
> for any a
,
b
,
c
∈
Z
q
∗, the bilinear Diffie-Hellman (BDH) problem is that it is computationally infeasible to determine the value of e
(
P
,
P
)
a
b
c
∈
G
2.


### 2.1.2. CDH Problem

Given<
P
,
a
P
,
b
P
> for any a
,
b
∈
Z
q
∗, the computational Diffie-Hellman (CDH) problem is that it is computationally infeasible to determine the value of a
b
P
∈
G
1.


### 2.1.3. DBDH Problem

Given<
P
,
a
P
,
b
P
,
c
P
> for any a
,
b
,
c
∈
Z
q
∗ and X
∈
G
2, the decisional bilinear Diffie-Hellman (DBDH) problem is to decide whether e
(
P
,
P
)
a
b
c
=
X. If it holds, the DBDH oracle O
D
B
D
H returns 1; else, O
D
B
D
H returns 0.


### 2.1.4. Gap BDH Problem

Given<
P
,
a
P
,
b
P
,
c
P
> for any a
,
b
,
c
∈
Z
q
∗, the gap bilinear Diffie-Hellman (gap BDH) problem is to determine the value of e
(
P
,
P
)
a
b
c
∈
G
2 with the help of O
D
B
D
H.


## 2.1.1. BDH Problem

Given<
P
,
a
P
,
b
P
,
c
P
> for any a
,
b
,
c
∈
Z
q
∗, the bilinear Diffie-Hellman (BDH) problem is that it is computationally infeasible to determine the value of e
(
P
,
P
)
a
b
c
∈
G
2.


## 2.1.2. CDH Problem

Given<
P
,
a
P
,
b
P
> for any a
,
b
∈
Z
q
∗, the computational Diffie-Hellman (CDH) problem is that it is computationally infeasible to determine the value of a
b
P
∈
G
1.


## 2.1.3. DBDH Problem

Given<
P
,
a
P
,
b
P
,
c
P
> for any a
,
b
,
c
∈
Z
q
∗ and X
∈
G
2, the decisional bilinear Diffie-Hellman (DBDH) problem is to decide whether e
(
P
,
P
)
a
b
c
=
X. If it holds, the DBDH oracle O
D
B
D
H returns 1; else, O
D
B
D
H returns 0.


## 2.1.4. Gap BDH Problem

Given<
P
,
a
P
,
b
P
,
c
P
> for any a
,
b
,
c
∈
Z
q
∗, the gap bilinear Diffie-Hellman (gap BDH) problem is to determine the value of e
(
P
,
P
)
a
b
c
∈
G
2 with the help of O
D
B
D
H.


## 2.2. UC Framework

The UC framework [8] consists of a real-life model, ideal model, and hybrid model. In the UC framework, Z represents the external environment that consists of arbitrary protocols running concurrently with the given protocol. Z generates the inputs to all parties, reads all outputs, and interacts with the adversary in an arbitrary way throughout the computation. A protocol π is said to securely realize an ideal functionality F if, for any real-life adversary A interacting with the protocol, there exists a simulator S such that no Z can distinguish with nonnegligible probability whether it interacts with A and parties running the protocol π or with S and parties interacting with F in the ideal process.Letr
e
a
l
π
,
A
,
Z
k
,
z
,
r denote the output of Z when interacting with the adversary A and parties P
1
,
.
.
.
,
P
n running protocol π on security parameterk, inputz, and random input r
=
r
Z
,
r
A
,
r
1
,
.
.
.
,
r
n (z and r
Z for Z, r
A for A, and r
i for party P
i). Let r
e
a
l
π
,
A
,
Z
k
,
z be the random variable describing r
e
a
l
π
,
A
,
Z
k
,
z
,
r whenr is uniformly chosen. Here r
e
a
l
π
,
A
,
Z is the ensemble(1)
r
e
a
l
π
,
A
,
Z
k
,
z
k
∈
N
,
z
∈
0,1
∗
.Leti
d
e
a
l
F
,
S
,
Z
k
,
z
,
r denote the output of Z after interacting with the adversary S and ideal functionality F on security parameterk, inputz, and random input r
=
r
Z
,
r
S
,
r
F (z and r
Z for Z, r
S for S, and r
F for F). Let i
d
e
a
l
F
,
S
,
Z
k
,
z be the random variable describing i
d
e
a
l
F
,
S
,
Z
k
,
z
,
r whenr is uniformly chosen. Here i
d
e
a
l
F
,
S
,
Z is the ensemble (2)
i
d
e
a
l
F
,
S
,
Z
k
,
z
k
∈
N
,
z
∈
0,1
∗
.Definition 1 (indistinguishability).
Two binary distribution ensembles X and Y are indistinguishable (written X≈Y), if, for anyc
∈
N, there exists k
0
∈
N such that, for all k
>
k
0 and for alla, we have(3)
Pr
⁡
X
k
,
a
=
1
-
Pr
⁡
Y
k
,
a
=
1
<
k
-
c
.Definition 2 (UC simulation).
LetF denote an ideal functionality and let π denote a probabilistic polynomial time protocol. We say that π securely realizes F if, for any adversary A, there exists an ideal-process adversary S such that, for any environment Z, we have (4)
i
d
e
a
l
F
,
S
,
Z
≈
r
e
a
l
π
,
A
,
Z
.Theorem 3 (universal composition).
LetF and G be ideal functionalities. Let π be a protocol in the F-hybrid model and let ρ be a protocol which securely realizes F in the G-hybrid model. Then for any adversary A in the G-hybrid model, there exists an adversary S in the F-hybrid model such that, for any environment Z, we have(5)
r
e
a
l
π
,
S
,
Z
F
≈
r
e
a
l
π
ρ
,
A
,
Z
G
.


## 3. Formal Definition of IBPSP

### 3.1. Algorithm Model

A universally composable IBPSP consists of five probabilistic polynomial time algorithms:Setup,Extract,PKeyGen,ProxyS, andUns. Moreover, it involves four parties: a private key generator (PKG), an original signcrypter with identityI
a, a proxy signcrypter with identityI
p, and a receiver with identityI
b.Setup is an initialization algorithm that takes a security parameterk as input. The PKG runs this algorithm and outputs the master keys along with a set of system parameters β.Extract is an extraction algorithm that takes β and an identityI
i (i isa,p,b) of some user as input. The PKG runs this algorithm and outputs the public key Y
i and private key S
i of this user. Keep in mind thatI
a is the identity of the original signcrypter,I
p is the identity of the proxy signcrypter, andI
b is the identity of the receiver.Apparently, the public and private key pair of the original signcrypter, proxy signcrypter, and receiver is<
Y
a
,
S
a
>, <
Y
p
,
S
p
>, and <
Y
b
,
S
b
>, respectively.PKeyGen is a proxy key generation algorithm that takes <
β
,
I
a
,
I
p
> as input. The original signcrypter with identityI
a generates an authorization certificate m
w and then interacts with the proxy signcrypter with identityI
p. Finally, this algorithm outputs a proxy signcryption keyS
ap for the proxy signcrypter.ProxyS is a proxy signcryption algorithm that takes <
β
,
m
,
m
w
,
I
a
,
I
b
,
I
p
,
Y
p
,
Y
b
,
S
a
p
> as input. The proxy signcrypter with identityI
p runs this algorithm and outputs a ciphertext σ on messagem to the receiver with identityI
b.Uns is an unsigncryption algorithm that takes <
β
,
σ
,
m
w
,
I
a
,
I
b
,
I
p
,
Y
a
,
Y
p
,
Y
b
,
S
b
> as input. The receiver with identityI
b runs this unsigncryption algorithm and outputs a plaintextm or a symbol ⊥.


### 3.2. Security Model

In this section, we describe the formal security model of the universally composable IBPSP. A universally composable IBPSP must satisfy the confidentiality (IND-CCA2 security) and unforgeability (UF-CMA security). Keep in mind that we do not allow the queries when the identities of the original signcrypter, proxy signcrypter, or receiver are the same.For the confidentiality of the universally composable IBPSP, we adopt the IND-CCA2 security model. Now, we describe the interactive gameIND-IBPS-CCA2 played between an adversary A and a challengerC.IND-IBPS-CCA2: First of all,C runs the initialization algorithm to obtain a set of system parameters β and the master keys. ThenC keeps the secrecy ofs but returns β to A.Phase 1.
A makes a sequence of a polynomial bounded number of queries in an adaptive fashion.Extraction queries:A submits a query of identityI
i to the extraction oracle.C returns the private keyS
i and public keyY
i by a call to the extraction algorithm.Proxy key queries:A submits a query of the trituple <
I
a
,
I
p
,
m
w
> to the proxy key generation oracle.C returns the proxy keyS
ap by a call to the proxy key generation algorithm.Proxy signcryption queries:A submits a query of the quaternion <
I
a
,
I
b
,
I
p
,
m
> to the proxy signcryption oracle.C returns the ciphertext σ on messagem by a call to the proxy signcryption algorithm.Unsigncryption queries:A submits a query of the quaternion <
I
a
,
I
b
,
I
p
,
σ
> to the unsigncryption oracle.C returns a plaintextm or a symbol ⊥ by a call to the unsigncryption algorithm.Challenge. At the end of P
h
a
s
e
1, the adversary outputs two messages <
m
0
,
m
1
>
∈
{
0,1
}
l and quaternion <
I
a
∗
,
I
b
∗
,
I
p
∗
,
m
w
∗
> on which it wishes to be challenged. In P
h
a
s
e
1, the adversary cannot query the private key of identity I
b
∗.C selects a random δ
∈
{
0,1
} and obtains a challenge ciphertext σ
∗ on message m
δ by a call to the proxy signcryption algorithm. Finally,C returns σ
∗ as the answer.Phase 2.
A makes another sequence of queries in an adaptive fashion as in the first phase.C answers these queries as in the first phase. However, the adversary cannot extract the private key of identity I
b
∗ and cannot make the unsigncryption query on σ
∗.At the end of the game, the adversary outputs a guessδ
′
∈
{
0,1
}. If δ
=
δ
′, this shows that the adversary winsIND-IBPS-CCA2 above.Definition 4 (confidentiality).
A universally composable IBPSP is said to have the IND-CCA2 security if no probabilistic polynomial time adversaryA winsIND-IBPS-CCA2 with nonnegligible advantage.For the unforgeability of the universally composable IBPPSP, we adopt the UF-CMA security model. Keep in mind that, in the security models,A
p is in possession of the private key of the proxy signcrypter and A
o owns the private key of the original signcrypter.UF-IBPS-CMA-I:This is an interactive game performed between an adversary A
p and a challengerC.First of all,C generates a set of system parameters β and the master keys by a call toSetup(1k). It then keeps the secrecy ofs but delivers β to the adversary.Queries.
A
p makes a series of a polynomial bounded number of queries in an adaptive manner as in the first phase inIND-IBPS-CCA2. Moreover,C answers these queries as in the first phase inIND-IBPS-CCA2.Forgery. At the end of queries, A
p outputs a forged ciphertext <
I
a
∗
,
I
b
∗
,
I
p
∗
,
σ
∗
> toC. In queries, A
p cannot issue the private key query of identity I
p
∗. If the unsigncryption verification equality holds, this indicates that A
p winsUF-IBPS-CMA-I.UF-IBPS-CMA-II:This is an interactive game performed between an adversary A
o and a challengerC.First of all,C obtains the master keys and a set of system parameters β by a call toSetup(1k). It then returns β to the adversary but keeps the secrecy ofs.Queries.
A
o adaptively makes a series of a polynomial bounded number of queries as in P
h
a
s
e
1 inIND-IBPS-CCA2.C answers these queries as in P
h
a
s
e
1 inIND-IBPS-CCA2.Forgery. At the end of queries, A
o outputs a forged ciphertext <
I
a
∗
,
I
b
∗
,
I
p
∗
,
σ
∗
> toC. In queries, A
o cannot extract the private key of identity I
a
∗. If the verification equality holds, this shows that A
o winsUF-IBPS-CMA-II.Definition 5 (unforgeability).
A universally composable IBPSP is said to have UF-CMA-I security if no probabilistic polynomial time adversaryA
p winsUF-IBPS-CMA-I with nonnegligible advantage. In a similar manner, a universally composable IBPSP is said to have the UF-CMA-II security if probabilistic polynomial time adversary A
o winsUF-IBPS-CMA-II with nonnegligible advantage. Hence, a universally composable IBPSP is UF-CMA secure if it is both UF-CMA-I and UF-CMA-II secure.


## 3.1. Algorithm Model

A universally composable IBPSP consists of five probabilistic polynomial time algorithms:Setup,Extract,PKeyGen,ProxyS, andUns. Moreover, it involves four parties: a private key generator (PKG), an original signcrypter with identityI
a, a proxy signcrypter with identityI
p, and a receiver with identityI
b.Setup is an initialization algorithm that takes a security parameterk as input. The PKG runs this algorithm and outputs the master keys along with a set of system parameters β.Extract is an extraction algorithm that takes β and an identityI
i (i isa,p,b) of some user as input. The PKG runs this algorithm and outputs the public key Y
i and private key S
i of this user. Keep in mind thatI
a is the identity of the original signcrypter,I
p is the identity of the proxy signcrypter, andI
b is the identity of the receiver.Apparently, the public and private key pair of the original signcrypter, proxy signcrypter, and receiver is<
Y
a
,
S
a
>, <
Y
p
,
S
p
>, and <
Y
b
,
S
b
>, respectively.PKeyGen is a proxy key generation algorithm that takes <
β
,
I
a
,
I
p
> as input. The original signcrypter with identityI
a generates an authorization certificate m
w and then interacts with the proxy signcrypter with identityI
p. Finally, this algorithm outputs a proxy signcryption keyS
ap for the proxy signcrypter.ProxyS is a proxy signcryption algorithm that takes <
β
,
m
,
m
w
,
I
a
,
I
b
,
I
p
,
Y
p
,
Y
b
,
S
a
p
> as input. The proxy signcrypter with identityI
p runs this algorithm and outputs a ciphertext σ on messagem to the receiver with identityI
b.Uns is an unsigncryption algorithm that takes <
β
,
σ
,
m
w
,
I
a
,
I
b
,
I
p
,
Y
a
,
Y
p
,
Y
b
,
S
b
> as input. The receiver with identityI
b runs this unsigncryption algorithm and outputs a plaintextm or a symbol ⊥.


## 3.2. Security Model

In this section, we describe the formal security model of the universally composable IBPSP. A universally composable IBPSP must satisfy the confidentiality (IND-CCA2 security) and unforgeability (UF-CMA security). Keep in mind that we do not allow the queries when the identities of the original signcrypter, proxy signcrypter, or receiver are the same.For the confidentiality of the universally composable IBPSP, we adopt the IND-CCA2 security model. Now, we describe the interactive gameIND-IBPS-CCA2 played between an adversary A and a challengerC.IND-IBPS-CCA2: First of all,C runs the initialization algorithm to obtain a set of system parameters β and the master keys. ThenC keeps the secrecy ofs but returns β to A.Phase 1.
A makes a sequence of a polynomial bounded number of queries in an adaptive fashion.Extraction queries:A submits a query of identityI
i to the extraction oracle.C returns the private keyS
i and public keyY
i by a call to the extraction algorithm.Proxy key queries:A submits a query of the trituple <
I
a
,
I
p
,
m
w
> to the proxy key generation oracle.C returns the proxy keyS
ap by a call to the proxy key generation algorithm.Proxy signcryption queries:A submits a query of the quaternion <
I
a
,
I
b
,
I
p
,
m
> to the proxy signcryption oracle.C returns the ciphertext σ on messagem by a call to the proxy signcryption algorithm.Unsigncryption queries:A submits a query of the quaternion <
I
a
,
I
b
,
I
p
,
σ
> to the unsigncryption oracle.C returns a plaintextm or a symbol ⊥ by a call to the unsigncryption algorithm.Challenge. At the end of P
h
a
s
e
1, the adversary outputs two messages <
m
0
,
m
1
>
∈
{
0,1
}
l and quaternion <
I
a
∗
,
I
b
∗
,
I
p
∗
,
m
w
∗
> on which it wishes to be challenged. In P
h
a
s
e
1, the adversary cannot query the private key of identity I
b
∗.C selects a random δ
∈
{
0,1
} and obtains a challenge ciphertext σ
∗ on message m
δ by a call to the proxy signcryption algorithm. Finally,C returns σ
∗ as the answer.Phase 2.
A makes another sequence of queries in an adaptive fashion as in the first phase.C answers these queries as in the first phase. However, the adversary cannot extract the private key of identity I
b
∗ and cannot make the unsigncryption query on σ
∗.At the end of the game, the adversary outputs a guessδ
′
∈
{
0,1
}. If δ
=
δ
′, this shows that the adversary winsIND-IBPS-CCA2 above.Definition 4 (confidentiality).
A universally composable IBPSP is said to have the IND-CCA2 security if no probabilistic polynomial time adversaryA winsIND-IBPS-CCA2 with nonnegligible advantage.For the unforgeability of the universally composable IBPPSP, we adopt the UF-CMA security model. Keep in mind that, in the security models,A
p is in possession of the private key of the proxy signcrypter and A
o owns the private key of the original signcrypter.UF-IBPS-CMA-I:This is an interactive game performed between an adversary A
p and a challengerC.First of all,C generates a set of system parameters β and the master keys by a call toSetup(1k). It then keeps the secrecy ofs but delivers β to the adversary.Queries.
A
p makes a series of a polynomial bounded number of queries in an adaptive manner as in the first phase inIND-IBPS-CCA2. Moreover,C answers these queries as in the first phase inIND-IBPS-CCA2.Forgery. At the end of queries, A
p outputs a forged ciphertext <
I
a
∗
,
I
b
∗
,
I
p
∗
,
σ
∗
> toC. In queries, A
p cannot issue the private key query of identity I
p
∗. If the unsigncryption verification equality holds, this indicates that A
p winsUF-IBPS-CMA-I.UF-IBPS-CMA-II:This is an interactive game performed between an adversary A
o and a challengerC.First of all,C obtains the master keys and a set of system parameters β by a call toSetup(1k). It then returns β to the adversary but keeps the secrecy ofs.Queries.
A
o adaptively makes a series of a polynomial bounded number of queries as in P
h
a
s
e
1 inIND-IBPS-CCA2.C answers these queries as in P
h
a
s
e
1 inIND-IBPS-CCA2.Forgery. At the end of queries, A
o outputs a forged ciphertext <
I
a
∗
,
I
b
∗
,
I
p
∗
,
σ
∗
> toC. In queries, A
o cannot extract the private key of identity I
a
∗. If the verification equality holds, this shows that A
o winsUF-IBPS-CMA-II.Definition 5 (unforgeability).
A universally composable IBPSP is said to have UF-CMA-I security if no probabilistic polynomial time adversaryA
p winsUF-IBPS-CMA-I with nonnegligible advantage. In a similar manner, a universally composable IBPSP is said to have the UF-CMA-II security if probabilistic polynomial time adversary A
o winsUF-IBPS-CMA-II with nonnegligible advantage. Hence, a universally composable IBPSP is UF-CMA secure if it is both UF-CMA-I and UF-CMA-II secure.


## 4. Concrete Protocol

In this section, we devise a concrete example of the universally composable IBPSP; its algorithm details are described as follows.


### 4.1. Setup

In this system initialization algorithm with the input 1k, the PKG obtains the master keys and a set of system parameters β by carrying out the steps as below.LetG
1 denote a cyclic addition group with prime orderq and letG
2 denote a cyclic multiplication group with the same prime order. Moreover,P is a generator of addition groupG
1 and e
:
G
1
×
G
1
→
G
2 is a bilinear map. The PKG chooses four cryptography hash functions:(6)
h
1
:
0,1
∗
→
G
1
h
2
:
0,1
t
×
G
1
→
Z
q
∗
h
3
:
0,1
t
×
G
1
×
G
2
→
0,1
l
h
4
:
0,1
l
×
0,1
t
3
×
G
1
×
G
2
→
Z
q
∗
.Then the PKG selects a randoms
∈
Z
q
∗ as the system master key and calculates the system public key y
=
s
P. Finally, the PKG keeps the secrecy of master keys but publishes a set of the system parameters(7)
β
=
G
1
,
G
2
,
q
,
e
,
t
,
l
,
P
,
y
,
h
1
~
h
4
.


### 4.2. Extract

In this extraction algorithm with the inputβ and an identityI
i (i isa,b,p) of some user, the PKG carries out the following calculations to achieve this user’s public key and private key. Concretely speaking, the PKG calculates the public and private key for the original signcrypter with identityI
a as follows: (8)
Y
a
=
h
1
I
a
,
S
a
=
s
Y
a
.In the same manner, the PKG calculates the public and private key for the proxy signcrypter with identityI
p as follows:(9)
Y
p
=
h
1
I
p
,
S
p
=
s
Y
p
.We also readily obtain the public and private key for the receiver with identityI
b as follows:(10)
Y
b
=
h
1
I
b
,
S
b
=
s
Y
b
.


### 4.3. PKeyGen

In this proxy key generation algorithm with the input<
β
,
I
a
,
I
p
>, the original signcrypter with identityI
a generates an authorization certificate m
w which includes the identity information of the original signcrypter and proxy signcrypter together with other restriction contents. The original signcrypter selects a random k
a
∈
Z
q
∗ and calculates(11)
U
a
=
k
a
Y
a
V
=
h
2
m
w
,
U
a
S
a
.After that, the original signcrypter delivers the trituple<
U
a
,
V
,
m
w
> to the proxy signcrypter with identityI
p. Upon receiving <
U
a
,
V
,
m
w
>, the proxy signcrypter verifies whether the equality holds as below:(12)
e
P
,
V
=
e
y
,
Y
a
h
2
m
w
,
U
a
.If the verification is true, the proxy signcrypter calculates the proxy signcryption key(13)
S
a
p
=
S
p
+
V
.


### 4.4. ProxyS

In this proxy signcryption algorithm with the input<
β
,
m
,
m
w
,
I
a
,
I
p
,
I
b
,
Y
p
,
Y
b
,
S
a
p
>, the proxy signcrypter with identityI
p obtains a ciphertext σ on messagem and delivers it to the receiver with identityI
b.Concretely speaking, the proxy signcrypter selects a randomk
p
∈
Z
q
∗ to set U
p
=
k
p
P and then continues to calculate(14)
R
=
e
y
,
Y
b
k
p
c
=
m
⊕
h
3
m
w
,
U
p
,
R
μ
=
h
4
m
,
I
a
,
I
p
,
I
b
,
U
p
,
R
S
=
μ
S
a
p
+
k
p
Y
p
.Finally, the ciphertextσ
=
<
c
,
m
w
,
S
,
U
a
,
U
p
> is sent to the receiver.


### 4.5. Uns

In this unsigncryption algorithm with the input<
β
,
σ
,
m
w
,
I
a
,
I
b
,
I
p
,
Y
a
,
Y
p
,
Y
b
,
S
b
>, the receiver with identityI
b recoversm using two equalities as follows:(15)
R
=
e
U
p
,
S
b
m
=
c
⊕
h
3
m
w
,
U
p
,
R
.After that, the receiver continues to calculate(16)
μ
=
h
4
m
,
I
a
,
I
p
,
I
b
,
U
p
,
R
.Finally, this receiver checks whether the verification equality holds as follows:(17)
e
P
,
S
=
e
y
,
h
2
m
w
,
U
a
Y
a
+
Y
p
μ
e
U
p
,
Y
p
.If the above verification is true, this illustrates thatσ is valid; otherwise, it is invalid.It is easy for us to verify the correctness of our concrete protocol instance using three equalities as follows:(18)
e
P
,
V
=
e
P
,
h
2
m
w
,
U
a
S
a
=
e
P
,
s
Y
a
h
2
m
w
,
U
a
=
e
y
,
Y
a
h
2
m
w
,
U
a
R
=
e
y
,
Y
b
k
p
=
e
U
p
,
s
Y
b
=
e
U
p
,
S
b
e
P
,
S
=
e
P
,
μ
S
a
p
+
k
p
Y
p
=
e
P
,
S
p
+
V
μ
e
P
,
k
p
Y
p
=
e
P
,
s
Y
p
+
h
2
m
w
,
U
a
S
a
μ
e
U
p
,
Y
p
=
e
y
,
h
2
m
w
,
U
a
Y
a
+
Y
p
μ
e
U
p
,
Y
p
.


## 4.1. Setup

In this system initialization algorithm with the input 1k, the PKG obtains the master keys and a set of system parameters β by carrying out the steps as below.LetG
1 denote a cyclic addition group with prime orderq and letG
2 denote a cyclic multiplication group with the same prime order. Moreover,P is a generator of addition groupG
1 and e
:
G
1
×
G
1
→
G
2 is a bilinear map. The PKG chooses four cryptography hash functions:(6)
h
1
:
0,1
∗
→
G
1
h
2
:
0,1
t
×
G
1
→
Z
q
∗
h
3
:
0,1
t
×
G
1
×
G
2
→
0,1
l
h
4
:
0,1
l
×
0,1
t
3
×
G
1
×
G
2
→
Z
q
∗
.Then the PKG selects a randoms
∈
Z
q
∗ as the system master key and calculates the system public key y
=
s
P. Finally, the PKG keeps the secrecy of master keys but publishes a set of the system parameters(7)
β
=
G
1
,
G
2
,
q
,
e
,
t
,
l
,
P
,
y
,
h
1
~
h
4
.


## 4.2. Extract

In this extraction algorithm with the inputβ and an identityI
i (i isa,b,p) of some user, the PKG carries out the following calculations to achieve this user’s public key and private key. Concretely speaking, the PKG calculates the public and private key for the original signcrypter with identityI
a as follows: (8)
Y
a
=
h
1
I
a
,
S
a
=
s
Y
a
.In the same manner, the PKG calculates the public and private key for the proxy signcrypter with identityI
p as follows:(9)
Y
p
=
h
1
I
p
,
S
p
=
s
Y
p
.We also readily obtain the public and private key for the receiver with identityI
b as follows:(10)
Y
b
=
h
1
I
b
,
S
b
=
s
Y
b
.


## 4.3. PKeyGen

In this proxy key generation algorithm with the input<
β
,
I
a
,
I
p
>, the original signcrypter with identityI
a generates an authorization certificate m
w which includes the identity information of the original signcrypter and proxy signcrypter together with other restriction contents. The original signcrypter selects a random k
a
∈
Z
q
∗ and calculates(11)
U
a
=
k
a
Y
a
V
=
h
2
m
w
,
U
a
S
a
.After that, the original signcrypter delivers the trituple<
U
a
,
V
,
m
w
> to the proxy signcrypter with identityI
p. Upon receiving <
U
a
,
V
,
m
w
>, the proxy signcrypter verifies whether the equality holds as below:(12)
e
P
,
V
=
e
y
,
Y
a
h
2
m
w
,
U
a
.If the verification is true, the proxy signcrypter calculates the proxy signcryption key(13)
S
a
p
=
S
p
+
V
.


## 4.4. ProxyS

In this proxy signcryption algorithm with the input<
β
,
m
,
m
w
,
I
a
,
I
p
,
I
b
,
Y
p
,
Y
b
,
S
a
p
>, the proxy signcrypter with identityI
p obtains a ciphertext σ on messagem and delivers it to the receiver with identityI
b.Concretely speaking, the proxy signcrypter selects a randomk
p
∈
Z
q
∗ to set U
p
=
k
p
P and then continues to calculate(14)
R
=
e
y
,
Y
b
k
p
c
=
m
⊕
h
3
m
w
,
U
p
,
R
μ
=
h
4
m
,
I
a
,
I
p
,
I
b
,
U
p
,
R
S
=
μ
S
a
p
+
k
p
Y
p
.Finally, the ciphertextσ
=
<
c
,
m
w
,
S
,
U
a
,
U
p
> is sent to the receiver.


## 4.5. Uns

In this unsigncryption algorithm with the input<
β
,
σ
,
m
w
,
I
a
,
I
b
,
I
p
,
Y
a
,
Y
p
,
Y
b
,
S
b
>, the receiver with identityI
b recoversm using two equalities as follows:(15)
R
=
e
U
p
,
S
b
m
=
c
⊕
h
3
m
w
,
U
p
,
R
.After that, the receiver continues to calculate(16)
μ
=
h
4
m
,
I
a
,
I
p
,
I
b
,
U
p
,
R
.Finally, this receiver checks whether the verification equality holds as follows:(17)
e
P
,
S
=
e
y
,
h
2
m
w
,
U
a
Y
a
+
Y
p
μ
e
U
p
,
Y
p
.If the above verification is true, this illustrates thatσ is valid; otherwise, it is invalid.It is easy for us to verify the correctness of our concrete protocol instance using three equalities as follows:(18)
e
P
,
V
=
e
P
,
h
2
m
w
,
U
a
S
a
=
e
P
,
s
Y
a
h
2
m
w
,
U
a
=
e
y
,
Y
a
h
2
m
w
,
U
a
R
=
e
y
,
Y
b
k
p
=
e
U
p
,
s
Y
b
=
e
U
p
,
S
b
e
P
,
S
=
e
P
,
μ
S
a
p
+
k
p
Y
p
=
e
P
,
S
p
+
V
μ
e
P
,
k
p
Y
p
=
e
P
,
s
Y
p
+
h
2
m
w
,
U
a
S
a
μ
e
U
p
,
Y
p
=
e
y
,
h
2
m
w
,
U
a
Y
a
+
Y
p
μ
e
U
p
,
Y
p
.


## 5. Analysis of Semantic Security

In this section, we describe the proof process of the confidentiality and unforgeability of our protocol instance in the random oracle model.


### 5.1. Confidentiality

Theorem 6.
If no probabilistic polynomial time adversaryA winsIND-IBPS-CCA2 inDefinition4 with nonnegligible advantage ε by askingl
i queries to theh
i (i=1,2,3,4) oracle,l
e queries to the extraction oracle, andl
ap queries to the proxy key generation oracle, then there exists an algorithmC that can solve the gap BDH problem with the advantage ε
′ (e is the base of natural logarithm), where(19)
ε
′
≥
ε
e
l
3
l
e
+
l
a
p
.Proof.
Assume the algorithmC obtains a random instance <
P
,
a
P
,
b
P
,
c
P
> of the gap BDH problem, and the purpose ofC is to determine R
=
P
,
P
a
b
c
∈
G
2. For this purpose,C runs the adversary A as a subroutine and acts as the role of its challenger in the following interactive game.At the start of the game,C runs the system initialization algorithm with the security parameterk and obtains a set of system parameters β with y
=
a
P. ThenC delivers β to the adversary. In the whole game,C maintains five lists L
1
~
L
4 andL
ap which are empty in the beginning; L
1
~
L
4 are used to trace theh
i (i=1,2,3,4) oracle andL
ap is used to trace the extraction oracle and proxy key generation oracle.Phase 1.
A submits a series of a polynomial bounded number of queries in an adaptive fashion.h
1 queries:C first selects an identity I
λ
1
≤
λ
≤
l
1 as the target identity in the challenge phase. Bear in mind thatl
1 is the query time to theh
1 oracle. Let γ be the probability of I
i
=
I
λ, and the value of γ will be determined later. A submits a query of identityI
i to theh
1 oracle. If there is a matching tuple in the listL
1,C returns the public keyY
i as the answer; otherwise,C considers two cases as the response to this query.Case 1.
If it is theλ
t
h query,C sets Y
i
=
h
1
I
i
=
b
P. It then delivers public keyY
i to the adversary and records <
I
i
,
Y
i
,
-
,
-
> to the listL
1.Case 2.
If it is not theλ
t
h query,C uses a random x
i
∈
Z
q
∗ of its choice to calculate Y
i
=
h
1
(
I
i
)
=
x
i
P. It then returns Y
i as the answer and records <
I
i
,
Y
i
,
x
i
,
-
> to the listL
1.h
2 queries: A submits a query to theh
2 oracle. If there is a matching tuple in the listL
2,C returnsf as the answer; otherwise,C returns a random f
∈
Z
q
∗ of its choice and records <
m
w
,
U
a
,
f
> to the listL
2.h
3 queries: A submits a query to theh
3 oracle. If there exists a matching tuple in the listL
3,C returns ϕ as the answer; otherwise,C returns a random ϕ
∈
{
0,1
}
l of its choice and records <
m
w
,
R
,
U
p
,
ϕ
> to the listL
3.h
4 queries: A submits a query to theh
4 oracle. If there is a matching tuple in the listL
4,C delivers μ to the adversary; otherwise,C returns a random μ
∈
Z
q
∗ of its choice and stores <
m
,
I
a
,
I
p
,
I
b
,
U
p
,
R
,
μ
> to the listL
4.Extraction queries:A submits a query of identity I
i to the extraction oracle.C terminates this simulation if I
i
=
I
λ; otherwise,C calculates S
i
=
x
i
a
P
=
x
i
y and then returns <
Y
i
,
S
i
> and stores <
I
i
,
Y
i
,
x
i
,
S
i
> into the listL
1.Proxy key queries:A submits a proxy key query of the trituple <
I
a
,
I
p
,
m
w
>. Let us assume the adversary has made theh
1 andh
2 oracle queries along with key extraction queries before the proxy key query. If I
a
=
I
λ,C terminates this simulation; otherwise,C makes use of a random k
a
∈
Z
q
∗ of its choice to calculate (20)
U
a
=
k
a
Y
a
,
V
=
f
x
a
y
.If the verification equalitye
P
,
V
=
e
y
,
Y
a
f holds,C calculates the proxy keyS
ap using the equality as below(21)
S
a
p
=
x
p
y
+
Vand deliversS
ap to the adversary. Eventually,C stores <
m
w
,
S
a
p
,
U
a
,
V
> into the listL
ap.Proxy signcryption queries: Assume the adversary has made various hash oracle queries together with the extraction and proxy key generation query before a proxy signcryption query.A requests a query of <
I
a
,
I
b
,
I
p
,
m
w
,
m
> to the proxy signcryption oracle.C considers two cases as the response to this proxy signcryption query.Case 1.
IfI
p
≠
I
λ,C returns obtains a ciphertext σ by a call to the actual proxy signcryption algorithm and delivers this ciphertext to the adversary.Case 2.
IfI
p
=
I
λ,C selects two randoms υ
,
k
p
∈
Z
q
∗ and calculates(22)
U
p
=
k
p
P
-
υ
y
R
=
e
U
p
,
S
b
.
C continues to calculate c
=
m
⊕
ϕ and stores <
m
w
,
U
p
,
R
,
ϕ
> into the listL
3. ThenC sets μ
=
υ and adds <
m
,
I
a
,
I
p
,
I
b
,
U
p
,
R
,
μ
> into the listL
4. Finally,C calculates (23)
S
=
μ
f
x
a
y
+
k
p
Y
pand returns σ
=
<
c
,
m
w
,
S
,
U
a
,
U
p
> as the answer.It is very effortless for the adversary to verify the validity of the ciphertextσ using the equality as below.(24)
e
y
,
h
2
m
w
,
U
a
Y
a
+
Y
p
μ
e
U
p
,
Y
p
=
e
y
,
f
Y
a
+
Y
p
μ
e
k
p
P
-
υ
y
,
Y
p
=
e
y
,
μ
f
x
a
P
e
y
,
υ
Y
p
e
P
,
k
p
Y
p
e
y
,
Y
p
-
υ
=
e
P
,
μ
f
x
a
y
e
P
,
k
p
Y
p
=
e
P
,
μ
f
x
a
y
+
k
p
Y
p
=
e
P
,
S
.Unsigncryption queries: AssumeA has queried various hash oracles together with the extraction oracle and proxy key generation oracle before an unsigncryption query. A requests an unsigncryption query of the quaternion <
I
a
,
I
b
,
I
p
,
m
w
,
σ
>.C considers two cases as the response to this unsigncryption query.Case 1.
IfI
b
≠
I
λ,C returns a result by a call to the actual unsigncryption algorithm.Case 2.
IfI
b
=
I
λ,C goes over the listL
3 to seek the tuple <
m
w
,
U
p
,
R
,
ϕ
> for differentR such that O
D
B
D
H returns 1 when the adversary made a query on <
y
,
Y
b
,
U
b
,
R
>. If there exists this case,C calculates(25)
m
=
c
⊕
ϕ
μ
=
h
4
m
,
I
a
,
I
p
,
I
b
,
U
p
,
R
.
Finally,C checks whether the verification equality holds as below:(26)
e
P
,
S
=
e
y
,
h
2
m
w
,
U
a
Y
a
+
Y
p
μ
e
U
p
,
Y
p
.
If the verification is true,C returnsm; otherwise,C returns ⊥.Challenge. As the adversary decides to end the first phase, it outputsm
0 andm
1 with the same length along with the quaternion <
I
a
∗
,
I
b
∗
,
I
p
∗
,
m
w
∗
> on which it wishes to be challenged. Assume the adversary has queried various hash oracles together with the extraction and proxy key generation oracle before a challenge query. In the first phase, the private key of identity I
b
∗ cannot be extracted. Upon receiving a challenge query,C deals with this query by considering two cases as follows.Case 1.
IfI
p
∗
=
I
λ,C terminates this simulation.Case 2.
IfI
p
∗
≠
I
λ,C selects a random δ
∈
{
0,1
} and R
∗
∈
G
2. ThenC sets U
p
∗
=
c
P and calculates (27)
c
∗
=
m
δ
⊕
ϕ
∗
μ
∗
=
h
4
m
δ
,
I
a
∗
,
I
p
∗
,
I
b
∗
,
U
p
∗
,
R
∗
.
C stores <
m
w
∗
,
U
p
∗
,
R
∗
,
ϕ
∗
> into the list L3 and records <
m
δ
,
I
a
∗
,
I
p
∗
,
I
b
∗
,
U
p
∗
,
R
∗
,
μ
∗
> to the list L4. Finally, C continues to calculate(28)
S
∗
=
μ
∗
S
a
p
∗
+
x
p
∗
U
p
∗and returns σ
∗
=
<
c
∗
,
m
w
∗
,
S
∗
,
U
a
∗
,
U
p
∗
> as challenge ciphertext.Phase 2.
A issues another sequence of oracle queries in an adaptive fashion as the first phase. In addition,C answers these oracle queries as in the first phase. However, A cannot extract the private key of identity I
b
∗ and cannot make use of σ
∗ to query the unsigncryption oracle.At the end of the game, the adversary outputs a guessδ
′
∈
{
0,1
} of δ. If δ
=
δ
′,C outputs the solution of the gap BDH problem instance:(29)
R
∗
=
e
U
p
∗
,
S
b
∗
=
e
c
P
,
a
Y
b
∗
=
e
P
,
P
a
b
cAnalysis of probability. In the following, we analyze the success probability ofC in solving the gap BDH problem.According to the detailed description in the interactive game, we have that the probability ofC not terminating the simulation in the first phase or second phase is γ
l
e
+
l
a
p. And the probability ofC not terminating the simulation in the challenge phase is 1
-
γ. Thus, the probability ofC not terminating the simulation is γ
l
e
+
l
a
p
1
-
γ whose value is maximized at (30)
γ
=
1
-
1
1
+
l
e
+
l
a
p
.Referring to the method of the probability analysis in [20], we obtain that the probability ofC not terminating the simulation is at least(31)
1
e
l
e
+
l
a
p
.At the same time, the probability of the adversary querying theh
3 oracle is 1/l
3. Hence, the probability ofC in solving the gap BDH problem is at least(32)
ε
e
l
3
l
e
+
l
a
p
.If the adversary succeeds with probabilityε,C can solve the gap BDH problem with probability ε
′. It contracts with the initial gap BDH assumption. Therefore, ε must be negligible if the gap BDH problem is hard.


### 5.2. Unforgeability

Theorem 7.
If no probabilistic polynomial time adversaryA
p (or A
o) winsUF-IBPS-CMA-I (orUF-IBPS-CMA-II) with nonnegligible advantage ε by makingl
i queries to theh
i (i=1,2,3,4) oracle,l
e queries to the extraction oracle,l
ap queries to the proxy key generation oracle, andl
usc queries to the unsigncryption oracle, then there exist two cases. (1) InUF-IBPS-CMA-I, there exists an algorithmC which can solve the CDH problem with the advantage ε
1, where(33)
ε
1
≥
ε
e
l
u
s
c
l
e
+
l
a
p
.
(2) InUF-IBPS-CMA-II, there is an algorithmC which can solve the CDH problem with the advantage ε
2, where(34)
ε
2
≥
ε
e
l
e
l
u
s
c
.Proof.
Give a random instance<
P
,
a
P
,
b
P
> of the CDH problem, and the aim ofC is to determine the value of a
b
P
∈
G
1. In order to achieve this aim, the algorithmC runs the adversary A
p or A
o as a subroutine and acts as the role of the challenger of A
p or A
o in the interactive game.Initial.
C obtains a set of system parameters β with y
=
a
P by a call to the initialization algorithm and delivers β to A
p or A
o. In the interactive game,C needs to maintain five lists L
1
~
L
4 andL
ap which are empty in the beginning, and these lists make use of tracing the relevant random oracles.Queries. These are the same as those inP
h
a
s
e
1 inTheorem6.Forgery. At the end of these queries, the response to the forgery is described as follows.(1) As the queries are over,A
p outputs a forged ciphertext σ
∗
=
<
c
∗
,
m
w
∗
,
S
∗
,
U
a
∗
,
U
p
∗
> toC. In queries, A
p cannot extract the private key of identity I
p
∗ and σ
∗ should not be the response of any proxy signcryption oracle query made by A
p.C considers two cases as the response to this queryCase 1.
IfI
p
∗
=
I
λ and I
a
∗
=
I
λ,C terminates this simulation.Case 2.
IfI
p
∗
≠
I
λ and I
a
∗
=
I
λ,C queries various hash oracles to obtain <
x
p
∗
,
f
∗
,
μ
∗
> and Y
a
∗
=
b
P from the listL
1. ThenC outputs the solution of the CDH problem instance(35)
a
b
P
=
S
∗
-
μ
∗
S
p
∗
-
x
p
∗
U
p
∗
μ
∗
f
∗
.IfC wins in the interactive game above, this shows that the verification equality must hold:(36)
e
P
,
S
∗
=
e
y
,
h
2
m
w
∗
,
U
a
∗
Y
a
∗
+
Y
p
∗
μ
∗
e
U
p
∗
,
Y
p
∗
=
e
y
,
μ
∗
f
∗
Y
a
∗
e
y
,
μ
∗
Y
p
∗
e
P
,
x
p
∗
U
p
∗
=
e
P
,
μ
∗
f
∗
a
b
P
e
P
,
μ
∗
S
p
∗
e
P
,
x
p
∗
U
p
∗
.Analysis of probability. Now, we analyze the success probability thatC obtains the solution of the CDH problem instance.From the interactive game, we know that the probability ofC not aborting the game in the first phase or second phase is γ
l
e
+
l
a
p. And the probability ofC not aborting the execution of game in the challenge phase is 1
-
γ. Thus, the probability ofC not aborting the execution of game is γ
l
e
+
l
a
p
1
-
γ. Referring to the probability analysis inTheorem6, we can obtain that the probability ofC not aborting the execution of game is at least(37)
1
e
l
e
+
l
a
p
.Furthermore, the probability thatσ
∗ passes the unsigncryption verification is 1/l
usc. Therefore, the probability ofC in solving the CDH problem is at least(38)
ε
e
l
u
s
c
l
e
+
l
a
p
.(2) At the end of the queries,A
o outputs a forged ciphertext σ
∗
=
<
c
∗
,
m
w
∗
,
S
∗
,
U
a
∗
,
U
p
∗
> toC, where U
p
∗
=
y. In queries, A
o cannot issue the private key query of identity I
a
∗ and σ
∗ should not be the response of any proxy signcryption oracle query made by A
o. It is needful forC to deal with this query by considering two cases as belowCase 1.
IfI
a
∗
=
I
λ and I
p
∗
=
I
λ,C terminates this simulation.Case 2.
IfI
a
∗
≠
I
λ and I
p
∗
=
I
λ,C calls various hash oracles to achieve <
x
p
∗
,
f
∗
,
μ
∗
> and Y
p
∗
=
b
P from the listL
1. ThenC outputs the solution of the CDH problem instance: (39)
a
b
P
=
S
∗
-
μ
∗
f
∗
x
p
∗
y
μ
∗
+
1
.IfC wins in the interactive game above, this indicates that the verification equality must hold:(40)
e
P
,
S
∗
=
e
y
,
h
2
m
w
∗
,
U
a
∗
Y
a
∗
+
Y
p
∗
μ
∗
e
U
p
∗
,
Y
p
∗
=
e
y
,
μ
∗
f
∗
Y
a
∗
e
y
,
μ
∗
Y
p
∗
e
y
,
b
P
=
e
P
,
μ
∗
f
∗
x
a
∗
y
e
P
,
μ
∗
a
b
P
e
P
,
a
b
P
.Analysis of probability. Now, Let us analyze the success probability ofC in solving the CDH problem.From the interactive game above, we obtain that the probability ofC not aborting the game in the first phase or second phase is γ
l
e and the probability ofC not aborting the game in the challenge phase is 1
-
γ. Thus, the probability ofC not aborting the game is γ
l
e
1
-
γ. Referring to the probability analysis inTheorem6, we have that the probability ofC not aborting the game is at least 1/el
e.In addition, the probability thatσ
∗ passes the unsigncryption verification is 1/l
usc. Therefore, the probability ofC in solving the CDH problem is at least(41)
ε
e
l
e
l
u
s
c
.IfA
1 or A
o succeeds with probability ε,C can solve the CDH problem with probability ε
1 or ε
2. It contracts with the initial CDH assumption. Hence, ε must be negligible if the CDH problem is hard.


## 5.1. Confidentiality

Theorem 6.
If no probabilistic polynomial time adversaryA winsIND-IBPS-CCA2 inDefinition4 with nonnegligible advantage ε by askingl
i queries to theh
i (i=1,2,3,4) oracle,l
e queries to the extraction oracle, andl
ap queries to the proxy key generation oracle, then there exists an algorithmC that can solve the gap BDH problem with the advantage ε
′ (e is the base of natural logarithm), where(19)
ε
′
≥
ε
e
l
3
l
e
+
l
a
p
.Proof.
Assume the algorithmC obtains a random instance <
P
,
a
P
,
b
P
,
c
P
> of the gap BDH problem, and the purpose ofC is to determine R
=
P
,
P
a
b
c
∈
G
2. For this purpose,C runs the adversary A as a subroutine and acts as the role of its challenger in the following interactive game.At the start of the game,C runs the system initialization algorithm with the security parameterk and obtains a set of system parameters β with y
=
a
P. ThenC delivers β to the adversary. In the whole game,C maintains five lists L
1
~
L
4 andL
ap which are empty in the beginning; L
1
~
L
4 are used to trace theh
i (i=1,2,3,4) oracle andL
ap is used to trace the extraction oracle and proxy key generation oracle.Phase 1.
A submits a series of a polynomial bounded number of queries in an adaptive fashion.h
1 queries:C first selects an identity I
λ
1
≤
λ
≤
l
1 as the target identity in the challenge phase. Bear in mind thatl
1 is the query time to theh
1 oracle. Let γ be the probability of I
i
=
I
λ, and the value of γ will be determined later. A submits a query of identityI
i to theh
1 oracle. If there is a matching tuple in the listL
1,C returns the public keyY
i as the answer; otherwise,C considers two cases as the response to this query.Case 1.
If it is theλ
t
h query,C sets Y
i
=
h
1
I
i
=
b
P. It then delivers public keyY
i to the adversary and records <
I
i
,
Y
i
,
-
,
-
> to the listL
1.Case 2.
If it is not theλ
t
h query,C uses a random x
i
∈
Z
q
∗ of its choice to calculate Y
i
=
h
1
(
I
i
)
=
x
i
P. It then returns Y
i as the answer and records <
I
i
,
Y
i
,
x
i
,
-
> to the listL
1.h
2 queries: A submits a query to theh
2 oracle. If there is a matching tuple in the listL
2,C returnsf as the answer; otherwise,C returns a random f
∈
Z
q
∗ of its choice and records <
m
w
,
U
a
,
f
> to the listL
2.h
3 queries: A submits a query to theh
3 oracle. If there exists a matching tuple in the listL
3,C returns ϕ as the answer; otherwise,C returns a random ϕ
∈
{
0,1
}
l of its choice and records <
m
w
,
R
,
U
p
,
ϕ
> to the listL
3.h
4 queries: A submits a query to theh
4 oracle. If there is a matching tuple in the listL
4,C delivers μ to the adversary; otherwise,C returns a random μ
∈
Z
q
∗ of its choice and stores <
m
,
I
a
,
I
p
,
I
b
,
U
p
,
R
,
μ
> to the listL
4.Extraction queries:A submits a query of identity I
i to the extraction oracle.C terminates this simulation if I
i
=
I
λ; otherwise,C calculates S
i
=
x
i
a
P
=
x
i
y and then returns <
Y
i
,
S
i
> and stores <
I
i
,
Y
i
,
x
i
,
S
i
> into the listL
1.Proxy key queries:A submits a proxy key query of the trituple <
I
a
,
I
p
,
m
w
>. Let us assume the adversary has made theh
1 andh
2 oracle queries along with key extraction queries before the proxy key query. If I
a
=
I
λ,C terminates this simulation; otherwise,C makes use of a random k
a
∈
Z
q
∗ of its choice to calculate (20)
U
a
=
k
a
Y
a
,
V
=
f
x
a
y
.If the verification equalitye
P
,
V
=
e
y
,
Y
a
f holds,C calculates the proxy keyS
ap using the equality as below(21)
S
a
p
=
x
p
y
+
Vand deliversS
ap to the adversary. Eventually,C stores <
m
w
,
S
a
p
,
U
a
,
V
> into the listL
ap.Proxy signcryption queries: Assume the adversary has made various hash oracle queries together with the extraction and proxy key generation query before a proxy signcryption query.A requests a query of <
I
a
,
I
b
,
I
p
,
m
w
,
m
> to the proxy signcryption oracle.C considers two cases as the response to this proxy signcryption query.Case 1.
IfI
p
≠
I
λ,C returns obtains a ciphertext σ by a call to the actual proxy signcryption algorithm and delivers this ciphertext to the adversary.Case 2.
IfI
p
=
I
λ,C selects two randoms υ
,
k
p
∈
Z
q
∗ and calculates(22)
U
p
=
k
p
P
-
υ
y
R
=
e
U
p
,
S
b
.
C continues to calculate c
=
m
⊕
ϕ and stores <
m
w
,
U
p
,
R
,
ϕ
> into the listL
3. ThenC sets μ
=
υ and adds <
m
,
I
a
,
I
p
,
I
b
,
U
p
,
R
,
μ
> into the listL
4. Finally,C calculates (23)
S
=
μ
f
x
a
y
+
k
p
Y
pand returns σ
=
<
c
,
m
w
,
S
,
U
a
,
U
p
> as the answer.It is very effortless for the adversary to verify the validity of the ciphertextσ using the equality as below.(24)
e
y
,
h
2
m
w
,
U
a
Y
a
+
Y
p
μ
e
U
p
,
Y
p
=
e
y
,
f
Y
a
+
Y
p
μ
e
k
p
P
-
υ
y
,
Y
p
=
e
y
,
μ
f
x
a
P
e
y
,
υ
Y
p
e
P
,
k
p
Y
p
e
y
,
Y
p
-
υ
=
e
P
,
μ
f
x
a
y
e
P
,
k
p
Y
p
=
e
P
,
μ
f
x
a
y
+
k
p
Y
p
=
e
P
,
S
.Unsigncryption queries: AssumeA has queried various hash oracles together with the extraction oracle and proxy key generation oracle before an unsigncryption query. A requests an unsigncryption query of the quaternion <
I
a
,
I
b
,
I
p
,
m
w
,
σ
>.C considers two cases as the response to this unsigncryption query.Case 1.
IfI
b
≠
I
λ,C returns a result by a call to the actual unsigncryption algorithm.Case 2.
IfI
b
=
I
λ,C goes over the listL
3 to seek the tuple <
m
w
,
U
p
,
R
,
ϕ
> for differentR such that O
D
B
D
H returns 1 when the adversary made a query on <
y
,
Y
b
,
U
b
,
R
>. If there exists this case,C calculates(25)
m
=
c
⊕
ϕ
μ
=
h
4
m
,
I
a
,
I
p
,
I
b
,
U
p
,
R
.
Finally,C checks whether the verification equality holds as below:(26)
e
P
,
S
=
e
y
,
h
2
m
w
,
U
a
Y
a
+
Y
p
μ
e
U
p
,
Y
p
.
If the verification is true,C returnsm; otherwise,C returns ⊥.Challenge. As the adversary decides to end the first phase, it outputsm
0 andm
1 with the same length along with the quaternion <
I
a
∗
,
I
b
∗
,
I
p
∗
,
m
w
∗
> on which it wishes to be challenged. Assume the adversary has queried various hash oracles together with the extraction and proxy key generation oracle before a challenge query. In the first phase, the private key of identity I
b
∗ cannot be extracted. Upon receiving a challenge query,C deals with this query by considering two cases as follows.Case 1.
IfI
p
∗
=
I
λ,C terminates this simulation.Case 2.
IfI
p
∗
≠
I
λ,C selects a random δ
∈
{
0,1
} and R
∗
∈
G
2. ThenC sets U
p
∗
=
c
P and calculates (27)
c
∗
=
m
δ
⊕
ϕ
∗
μ
∗
=
h
4
m
δ
,
I
a
∗
,
I
p
∗
,
I
b
∗
,
U
p
∗
,
R
∗
.
C stores <
m
w
∗
,
U
p
∗
,
R
∗
,
ϕ
∗
> into the list L3 and records <
m
δ
,
I
a
∗
,
I
p
∗
,
I
b
∗
,
U
p
∗
,
R
∗
,
μ
∗
> to the list L4. Finally, C continues to calculate(28)
S
∗
=
μ
∗
S
a
p
∗
+
x
p
∗
U
p
∗and returns σ
∗
=
<
c
∗
,
m
w
∗
,
S
∗
,
U
a
∗
,
U
p
∗
> as challenge ciphertext.Phase 2.
A issues another sequence of oracle queries in an adaptive fashion as the first phase. In addition,C answers these oracle queries as in the first phase. However, A cannot extract the private key of identity I
b
∗ and cannot make use of σ
∗ to query the unsigncryption oracle.At the end of the game, the adversary outputs a guessδ
′
∈
{
0,1
} of δ. If δ
=
δ
′,C outputs the solution of the gap BDH problem instance:(29)
R
∗
=
e
U
p
∗
,
S
b
∗
=
e
c
P
,
a
Y
b
∗
=
e
P
,
P
a
b
cAnalysis of probability. In the following, we analyze the success probability ofC in solving the gap BDH problem.According to the detailed description in the interactive game, we have that the probability ofC not terminating the simulation in the first phase or second phase is γ
l
e
+
l
a
p. And the probability ofC not terminating the simulation in the challenge phase is 1
-
γ. Thus, the probability ofC not terminating the simulation is γ
l
e
+
l
a
p
1
-
γ whose value is maximized at (30)
γ
=
1
-
1
1
+
l
e
+
l
a
p
.Referring to the method of the probability analysis in [20], we obtain that the probability ofC not terminating the simulation is at least(31)
1
e
l
e
+
l
a
p
.At the same time, the probability of the adversary querying theh
3 oracle is 1/l
3. Hence, the probability ofC in solving the gap BDH problem is at least(32)
ε
e
l
3
l
e
+
l
a
p
.If the adversary succeeds with probabilityε,C can solve the gap BDH problem with probability ε
′. It contracts with the initial gap BDH assumption. Therefore, ε must be negligible if the gap BDH problem is hard.


## 5.2. Unforgeability

Theorem 7.
If no probabilistic polynomial time adversaryA
p (or A
o) winsUF-IBPS-CMA-I (orUF-IBPS-CMA-II) with nonnegligible advantage ε by makingl
i queries to theh
i (i=1,2,3,4) oracle,l
e queries to the extraction oracle,l
ap queries to the proxy key generation oracle, andl
usc queries to the unsigncryption oracle, then there exist two cases. (1) InUF-IBPS-CMA-I, there exists an algorithmC which can solve the CDH problem with the advantage ε
1, where(33)
ε
1
≥
ε
e
l
u
s
c
l
e
+
l
a
p
.
(2) InUF-IBPS-CMA-II, there is an algorithmC which can solve the CDH problem with the advantage ε
2, where(34)
ε
2
≥
ε
e
l
e
l
u
s
c
.Proof.
Give a random instance<
P
,
a
P
,
b
P
> of the CDH problem, and the aim ofC is to determine the value of a
b
P
∈
G
1. In order to achieve this aim, the algorithmC runs the adversary A
p or A
o as a subroutine and acts as the role of the challenger of A
p or A
o in the interactive game.Initial.
C obtains a set of system parameters β with y
=
a
P by a call to the initialization algorithm and delivers β to A
p or A
o. In the interactive game,C needs to maintain five lists L
1
~
L
4 andL
ap which are empty in the beginning, and these lists make use of tracing the relevant random oracles.Queries. These are the same as those inP
h
a
s
e
1 inTheorem6.Forgery. At the end of these queries, the response to the forgery is described as follows.(1) As the queries are over,A
p outputs a forged ciphertext σ
∗
=
<
c
∗
,
m
w
∗
,
S
∗
,
U
a
∗
,
U
p
∗
> toC. In queries, A
p cannot extract the private key of identity I
p
∗ and σ
∗ should not be the response of any proxy signcryption oracle query made by A
p.C considers two cases as the response to this queryCase 1.
IfI
p
∗
=
I
λ and I
a
∗
=
I
λ,C terminates this simulation.Case 2.
IfI
p
∗
≠
I
λ and I
a
∗
=
I
λ,C queries various hash oracles to obtain <
x
p
∗
,
f
∗
,
μ
∗
> and Y
a
∗
=
b
P from the listL
1. ThenC outputs the solution of the CDH problem instance(35)
a
b
P
=
S
∗
-
μ
∗
S
p
∗
-
x
p
∗
U
p
∗
μ
∗
f
∗
.IfC wins in the interactive game above, this shows that the verification equality must hold:(36)
e
P
,
S
∗
=
e
y
,
h
2
m
w
∗
,
U
a
∗
Y
a
∗
+
Y
p
∗
μ
∗
e
U
p
∗
,
Y
p
∗
=
e
y
,
μ
∗
f
∗
Y
a
∗
e
y
,
μ
∗
Y
p
∗
e
P
,
x
p
∗
U
p
∗
=
e
P
,
μ
∗
f
∗
a
b
P
e
P
,
μ
∗
S
p
∗
e
P
,
x
p
∗
U
p
∗
.Analysis of probability. Now, we analyze the success probability thatC obtains the solution of the CDH problem instance.From the interactive game, we know that the probability ofC not aborting the game in the first phase or second phase is γ
l
e
+
l
a
p. And the probability ofC not aborting the execution of game in the challenge phase is 1
-
γ. Thus, the probability ofC not aborting the execution of game is γ
l
e
+
l
a
p
1
-
γ. Referring to the probability analysis inTheorem6, we can obtain that the probability ofC not aborting the execution of game is at least(37)
1
e
l
e
+
l
a
p
.Furthermore, the probability thatσ
∗ passes the unsigncryption verification is 1/l
usc. Therefore, the probability ofC in solving the CDH problem is at least(38)
ε
e
l
u
s
c
l
e
+
l
a
p
.(2) At the end of the queries,A
o outputs a forged ciphertext σ
∗
=
<
c
∗
,
m
w
∗
,
S
∗
,
U
a
∗
,
U
p
∗
> toC, where U
p
∗
=
y. In queries, A
o cannot issue the private key query of identity I
a
∗ and σ
∗ should not be the response of any proxy signcryption oracle query made by A
o. It is needful forC to deal with this query by considering two cases as belowCase 1.
IfI
a
∗
=
I
λ and I
p
∗
=
I
λ,C terminates this simulation.Case 2.
IfI
a
∗
≠
I
λ and I
p
∗
=
I
λ,C calls various hash oracles to achieve <
x
p
∗
,
f
∗
,
μ
∗
> and Y
p
∗
=
b
P from the listL
1. ThenC outputs the solution of the CDH problem instance: (39)
a
b
P
=
S
∗
-
μ
∗
f
∗
x
p
∗
y
μ
∗
+
1
.IfC wins in the interactive game above, this indicates that the verification equality must hold:(40)
e
P
,
S
∗
=
e
y
,
h
2
m
w
∗
,
U
a
∗
Y
a
∗
+
Y
p
∗
μ
∗
e
U
p
∗
,
Y
p
∗
=
e
y
,
μ
∗
f
∗
Y
a
∗
e
y
,
μ
∗
Y
p
∗
e
y
,
b
P
=
e
P
,
μ
∗
f
∗
x
a
∗
y
e
P
,
μ
∗
a
b
P
e
P
,
a
b
P
.Analysis of probability. Now, Let us analyze the success probability ofC in solving the CDH problem.From the interactive game above, we obtain that the probability ofC not aborting the game in the first phase or second phase is γ
l
e and the probability ofC not aborting the game in the challenge phase is 1
-
γ. Thus, the probability ofC not aborting the game is γ
l
e
1
-
γ. Referring to the probability analysis inTheorem6, we have that the probability ofC not aborting the game is at least 1/el
e.In addition, the probability thatσ
∗ passes the unsigncryption verification is 1/l
usc. Therefore, the probability ofC in solving the CDH problem is at least(41)
ε
e
l
e
l
u
s
c
.IfA
1 or A
o succeeds with probability ε,C can solve the CDH problem with probability ε
1 or ε
2. It contracts with the initial CDH assumption. Hence, ε must be negligible if the CDH problem is hard.


## 6. Analysis of UC Security

### 6.1. Protocolπ
I
B
P
S
P

A concreteπ
I
B
P
S
P usually makes use of the PKG to control two algorithms:Setup andExtract. π
I
B
P
S
P in the UC framework proceeds as below, with parties P
1
,
.
.
.
,
P
n and an adversary A.(1) Upon input<
P
K
G
,
S
e
t
u
p
,
s
i
d
> from A, the PKG verifies whether s
i
d
=
<
P
K
G
,
s
i
d
′
>. If not, the PKG ignores this request; else, the PKG obtains <
s
,
β
> by a call toSetup(1
k
) and returns β(2) Upon input<
E
x
t
r
a
c
t
,
s
i
d
> from A, P
i obtains <
Y
i
,
S
i
> by a call to E
x
t
r
a
c
t
β
,
s
,
I
i and returns <
Y
i
,
S
i
>(3) Upon input<
P
K
e
y
G
e
n
,
s
i
d
> from A, P
i obtains S
a
p by a call to P
K
e
y
G
e
n
β
,
I
a
,
I
p and returns S
a
p(4) Upon input<
P
r
o
x
y
S
,
s
i
d
,
m
> from A, P
i obtains a ciphertext σ by a call to the algorithm P
r
o
x
y
S
β
,
m
,
m
w
,
I
a
,
I
b
,
I
p
,
Y
b
,
Y
p
,
S
a
p and returns σ(5) Upon input<
U
s
c
,
s
i
d
,
σ
> from A, P
i obtains m
←
U
n
s
β
,
σ
,
m
w
,
I
a
,
I
b
,
I
p
,
Y
a
,
Y
p
,
S
b and then returns f
←
υ
β
,
σ
,
m
,
s
i
d


### 6.2. Ideal FunctionalityF
I
B
P
S
P

In this section, we introduce the definition of an ideal functionalityF
I
B
P
S
P for the IBPSP, based on the security definitions in Section 2.2. F
I
B
P
S
P and π
I
B
P
S
P have the exact same interface; that is to say, F
I
B
P
S
P can be realized by π
I
B
P
S
P under certain condition. F
I
B
P
S
P proceeds as follows, with parties P
1
,
.
.
.
,
P
n and an ideal adversary S. υ is a deterministic verification algorithm.(1) Given<
S
e
t
u
p
,
s
i
d
> from the PKG, verify whether s
i
d
=
<
P
K
G
,
s
i
d
′
> for some s
i
d
′. If not, then ignore this request; else, forward <
S
e
t
u
p
,
s
i
d
> to S. Then, on receiving <
S
e
t
u
p
,
s
i
d
,
υ
> from S, record <
s
i
d
,
υ
> and output <
s
i
d
,
υ
> to S(2) On receiving<
E
x
t
r
a
c
t
,
s
i
d
> from some party P
i, verify whether s
i
d
=
<
P
i
,
s
i
d
′
>. If not, then ignore this request; else, forward <
E
x
t
r
a
c
t
,
s
i
d
> to S. Then, on receiving <
Y
i
,
S
i
,
υ
> from S, record <
Y
i
,
S
i
,
υ
> and output <
Y
i
,
S
i
> to P
i(3) On receiving<
P
K
e
y
G
e
n
,
s
i
d
> from P
p, verify whether s
i
d
=
<
P
p
,
s
i
d
′
>. If not, then ignore this; else, forward <
P
K
e
y
G
e
n
,
s
i
d
> to S. Then, on receiving <
S
a
p
,
υ
> from S, record <
S
a
p
,
υ
> and outputS
ap to P
p(4) On receiving<
P
r
o
x
y
S
,
s
i
d
,
υ
′
,
m
> for somem from P
p, verify whether s
i
d
=
<
P
p
,
s
i
d
′
>. If not, then ignore this. Else, do the following:① IfP
p is not corrupt and υ
=
υ
′, deliver <
P
r
o
x
y
S
,
s
i
d
,
|
m
|
> to S, where |m| is the length of messagem; else, deliver <
P
r
o
x
y
S
,
s
i
d
,
υ
′
,
m
> to S② On receiving the replayσ from S, deliver <
P
r
o
x
y
S
,
s
i
d
,
υ
′
,
m
,
σ
> to the party P
b and record <
m
,
σ
>(5) On input<
U
n
s
,
s
i
d
,
σ
> from P
b, verify whether s
i
d
=
<
P
b
,
s
i
d
′
>. If not, then ignore this. Else, do the following:① If<
m
,
σ
> has been recorded, then achieve f
←
υ
β
,
σ
,
m
,
s
i
d and send <
m
,
f
=
1
> to P
b② Else, return<
U
n
s
,
s
i
d
,
σ
> to S and obtainm from S, and then send <
m
,
f
=
0
> to P
b


### 6.3. Proof of UC Security

Theorem 8.
Ifπ
I
B
P
S
P satisfies the IND-CCA2 security, then π
I
B
P
S
P can securely realize F
I
B
P
S
P in the UC framework.Proof.
Assume the protocolπ
I
B
P
S
P satisfies the IND-CCA2 security; then π
I
B
P
S
P can securely realize F
I
B
P
S in the UC framework. i.e., if no probabilistic polynomial time A winsIND-IBPS-CCA2 with nonnegligible advantage, then any environment Z cannot distinguish whether it is interacting with π
I
B
P
S
P and A in the real-life model or with F
I
B
P
S
P and S in the ideal model.EnvironmentZ proceeds as follows.(1)Z delivers a request onSetup. On receiving <
S
e
t
u
p
,
s
i
d
>, Z inputs β and activates A(2) On receiving a request on<
E
x
t
r
a
c
t
,
s
i
d
> from A, Z activates some party P
i with input <
E
x
t
r
a
c
t
,
s
i
d
> and outputs <
Y
i
,
S
i
> to A(3) On receiving<
P
K
e
y
G
e
n
,
s
i
d
> from A, Z activates P
a and P
p with <
P
K
e
y
G
e
n
,
s
i
d
> and outputsS
ap to A(4) On receiving<
P
r
o
x
y
S
,
s
i
d
,
m
> from A, Z activates P
p with input <
P
r
o
x
y
S
,
s
i
d
,
m
> and outputs σ to A(5) On receiving a request on<
U
n
s
,
s
i
d
,
σ
> from A, Z activates P
b with input <
U
n
s
,
s
i
d
,
σ
> and outputs the valuef of υ
σ
,
m
,
s
i
dIfA winsIND-IBPS-CCA2, Z outputs f
=
1. In addition, the probability that Z outputs 1 is 0 in the ideal model. Obviously, if π
I
B
P
S
P satisfies the IND-CCA2 security, π
I
B
P
S
P can securely realize F
I
B
P
S
P in the UC framework.Theorem 9.
Ifπ
I
B
P
S
P can securely realize F
I
B
P
S
P in the UC framework, then π
I
B
P
S
P satisfies the IND-CCA2 security.Proof.
Here we construct an ideal adversaryS such that no environment Z can tell with nonnegligible advantage whether it interacts with F
I
B
P
S
P and S in the ideal model or with π
I
B
P
S
P and A in the real-life model.S runs a copy of A and sends the input from Z to A, and simultaneously any output from A is considered as the output of S.(1) On receiving<
S
e
t
u
p
,
s
i
d
> from F
I
B
P
S
P, it runs the Setup algorithm and obtains <
β
,
s
>, and then returns <
S
e
t
u
p
,
s
i
d
,
υ
,
β
>(2) On receiving<
E
x
t
r
a
c
t
,
s
i
d
> from F
I
B
P
S
P, it invokes the extraction algorithm to achieve <
Y
i
,
S
i
> and then returns <
Y
i
,
S
i
>(3) On receiving<
P
K
e
y
G
e
n
,
s
i
d
> from F
I
B
P
S
P, it invokes the proxy key generation algorithm to obtainS
ap and then returnsS
ap(4) On receiving<
P
r
o
x
y
S
,
s
i
d
,
m
> from F
I
B
P
S
P, it runs the proxy signcryption algorithm to obtain σ and then returns σ(5) On receiving<
U
n
s
,
s
i
d
,
σ
> from F
I
B
P
S
P, it runs the unsigncryption algorithm to obtainm and then returnsm. Then it returns f
←
υ
σ
,
m
,
s
i
d. If P
b is corrupted, then deliver <
m
,
f
=
0
> to all parties; else, deliver <
m
,
f
=
1
> to P
bIn the following, we prove that the ideal adversaryS simulates the real-life adversary A.(1) On receivingβ from the challengerC, Z is invoked. On receiving <
S
e
t
u
p
,
s
i
d
> from Z, it issues a request toC that returns η
=
s
i
d
,
β as the answer(2) On receiving<
E
x
t
r
a
c
t
,
s
i
d
> from Z, it issues a request toC that returns <
Y
i
,
S
i
> as the answer(3) On receiving<
P
K
e
y
G
e
n
,
s
i
d
> from Z, it issues a request toC that returnsS
ap as the answer(4) On receiving<
P
r
o
x
y
S
,
s
i
d
,
m
> from Z, it issues a request toC that responds as follows:① IfP
p is uncorrupt, send <
P
r
o
x
y
S
,
s
i
d
,
|
m
|
> toC that returns σ
′ as the answer② IfP
p is corrupt, deliver <
P
r
o
x
y
S
,
s
i
d
,
m
> toC that returns σ as the answer(5) On input<
U
n
s
,
s
i
d
,
σ
> from Z, it issues a request toC that responds as follows:① If bothP
p and P
b are not corrupt, then send <
U
n
s
,
s
i
d
,
σ
′
> toC that returns m
′ as the answer② IfP
p is corrupt and P
b is not corrupt, then send <
U
n
s
,
s
i
d
,
σ
> toC that returns m
′ as the answer③ IfP
p is not corrupt and P
b is corrupt, then send <
U
n
s
,
s
i
d
,
σ
′
> toC that returns m
′ as the answer④ If bothP
p and P
b are corrupt, then deliver <
U
n
s
,
s
i
d
,
σ
> toC that returnsm as the answerThen,Z obtains f
←
υ
β
,
σ
,
m
,
s
i
d and returnsf. If f
=
1, this shows that the ciphertext is valid; else, it is invalid.According to the running process, we define four events: forZ, the occurrence of each event means that it cannot tell whether it interacts with π
I
B
P
S
P and A in the real-life model or with F
I
B
P
S
P and S in the ideal model.Event 1:P
p and P
b are both uncorrupt. In the real-life process, P
p obtains σ ofm by the proxy signcryption algorithm and sends σ to P
b. And P
b can unsigncrypt σ to obtainm and verifies the validity of σ. In the ideal process, S simulates P
b to obtain σ
′ of m
′ of its choice and sends σ
′ to P
b. S answers with m
′ when P
b unsigncrypts σ
′; the unsigncryption succeeds if f
=
1.Event 2:P
p is not corrupt and P
b is corrupt. In the real-life process, Z cannot determine which message is signcrypted by P
p. In the ideal process, S simulates P
p with m
′ of its choice to obtain σ
′ and forwards σ
′ to A. It follows that Z cannot distinguish <
m
,
σ
> and <
m
′
,
σ
′
>.Event 3:P
p is corrupt and P
b is not corrupt. If P
p is corrupt, this shows A obtains the process of proxy signcryption. On the other hand, S can invoke a copy of A; therefore, S can obtain the same information with A. That is to say, when S makes the proxy signcryption, S can perfectly simulate P
p that is corrupt.Event 4:P
p and P
b are both corrupt. In this case, S can obtain all their input information; i.e., S can generate real data to simulate the execution of protocol.In the four events defined above, ifZ can tell whether it interacts with <
π
I
B
P
S
P
,
A
> or with <
F
I
B
P
S
P
,
S
> with probability |
Pr
⁡
Z
π
I
B
P
S
P
,
A
→
1
-
Pr
⁡
Z
F
I
B
P
S
P
,
S
→
1
|, then A winsIND-IBPS-CCA2 with probability |
Pr
⁡
Z
π
I
B
P
S
P
,
A
→
1
-
Pr
⁡
Z
F
I
B
P
S
P
,
S
→
1
|. In the real world, Pr
⁡
Z
π
I
B
P
S
P
,
A
→
1 is a negligible probability; in addition, Pr
⁡
Z
F
I
B
P
S
P
,
S
→
1 is always equal to zero in the ideal world. Therefore, we readily obtain that |
Pr
⁡
Z
π
I
B
P
S
P
,
A
→
1
-
Pr
⁡
Z
F
I
B
P
S
P
,
S
→
1
| is negligible.Theorem 10.
In the UC framework,π
I
B
P
S
P satisfies the existential unforgeability against adaptive chosen-message attacks.Proof.
Assume there exists a forger. Here we construct an environmentZ and an adversary A such that, for any adversary A, Z cannot tell with nonnegligible probability whether it interacts with π
I
B
P
S
P and A in the real-life model or with F
I
B
P
S
P and S in the ideal model.Z proceeds as below. On receiving a request on proxy signcryption of A, Z activates P
p and outputs the ciphertext σ to A. On receiving a request on unsigncryption of A, Z activates P
b and outputs <
m
,
f
> to A.A proceeds as follows. A first invokes the forger. As the forger requests to signcrypt a messagem, A requests Z to signcrypt a messagem and outputs the ciphertext σ
′ to the forger. On receiving a request on unsigncryption of the forger, A requests Z to unsigncrypt σ
′ and outputs <
m
′
,
f
> to A and simultaneously delivers σ
′ to the forger. Once the forger receives m
′ and f
=
1, then the forgery σ
′ is valid and at this time Z outputs f
=
1. Clearly, if the forger winsUF-IBPS-CMA-I orUF-IBPS-CMA-Iwith probability ε, then the forger can succeed in forging valid proxy signcryption. Assume that such a forger exists with nonnegligible probability ε; then the probability that Z outputs f
=
1 is nonnegligible. However, the probability that Z outputs f
=
1 is always equal to zero in the ideal model. In other words, if such a forger exists, Z can always tell with nonnegligible probability whether it interacts with π
I
B
P
S
P and A or with F
I
B
P
S
P and S. It contracts with the initial assumption inTheorem10. As mentioned above, such a forger cannot exist; that is to say, π
I
B
P
S
P satisfies the existential unforgeability against adaptive chosen-message attacks in the UC framework.


## 6.1. Protocolπ
I
B
P
S
P

A concreteπ
I
B
P
S
P usually makes use of the PKG to control two algorithms:Setup andExtract. π
I
B
P
S
P in the UC framework proceeds as below, with parties P
1
,
.
.
.
,
P
n and an adversary A.(1) Upon input<
P
K
G
,
S
e
t
u
p
,
s
i
d
> from A, the PKG verifies whether s
i
d
=
<
P
K
G
,
s
i
d
′
>. If not, the PKG ignores this request; else, the PKG obtains <
s
,
β
> by a call toSetup(1
k
) and returns β(2) Upon input<
E
x
t
r
a
c
t
,
s
i
d
> from A, P
i obtains <
Y
i
,
S
i
> by a call to E
x
t
r
a
c
t
β
,
s
,
I
i and returns <
Y
i
,
S
i
>(3) Upon input<
P
K
e
y
G
e
n
,
s
i
d
> from A, P
i obtains S
a
p by a call to P
K
e
y
G
e
n
β
,
I
a
,
I
p and returns S
a
p(4) Upon input<
P
r
o
x
y
S
,
s
i
d
,
m
> from A, P
i obtains a ciphertext σ by a call to the algorithm P
r
o
x
y
S
β
,
m
,
m
w
,
I
a
,
I
b
,
I
p
,
Y
b
,
Y
p
,
S
a
p and returns σ(5) Upon input<
U
s
c
,
s
i
d
,
σ
> from A, P
i obtains m
←
U
n
s
β
,
σ
,
m
w
,
I
a
,
I
b
,
I
p
,
Y
a
,
Y
p
,
S
b and then returns f
←
υ
β
,
σ
,
m
,
s
i
d


## 6.2. Ideal FunctionalityF
I
B
P
S
P

In this section, we introduce the definition of an ideal functionalityF
I
B
P
S
P for the IBPSP, based on the security definitions in Section 2.2. F
I
B
P
S
P and π
I
B
P
S
P have the exact same interface; that is to say, F
I
B
P
S
P can be realized by π
I
B
P
S
P under certain condition. F
I
B
P
S
P proceeds as follows, with parties P
1
,
.
.
.
,
P
n and an ideal adversary S. υ is a deterministic verification algorithm.(1) Given<
S
e
t
u
p
,
s
i
d
> from the PKG, verify whether s
i
d
=
<
P
K
G
,
s
i
d
′
> for some s
i
d
′. If not, then ignore this request; else, forward <
S
e
t
u
p
,
s
i
d
> to S. Then, on receiving <
S
e
t
u
p
,
s
i
d
,
υ
> from S, record <
s
i
d
,
υ
> and output <
s
i
d
,
υ
> to S(2) On receiving<
E
x
t
r
a
c
t
,
s
i
d
> from some party P
i, verify whether s
i
d
=
<
P
i
,
s
i
d
′
>. If not, then ignore this request; else, forward <
E
x
t
r
a
c
t
,
s
i
d
> to S. Then, on receiving <
Y
i
,
S
i
,
υ
> from S, record <
Y
i
,
S
i
,
υ
> and output <
Y
i
,
S
i
> to P
i(3) On receiving<
P
K
e
y
G
e
n
,
s
i
d
> from P
p, verify whether s
i
d
=
<
P
p
,
s
i
d
′
>. If not, then ignore this; else, forward <
P
K
e
y
G
e
n
,
s
i
d
> to S. Then, on receiving <
S
a
p
,
υ
> from S, record <
S
a
p
,
υ
> and outputS
ap to P
p(4) On receiving<
P
r
o
x
y
S
,
s
i
d
,
υ
′
,
m
> for somem from P
p, verify whether s
i
d
=
<
P
p
,
s
i
d
′
>. If not, then ignore this. Else, do the following:① IfP
p is not corrupt and υ
=
υ
′, deliver <
P
r
o
x
y
S
,
s
i
d
,
|
m
|
> to S, where |m| is the length of messagem; else, deliver <
P
r
o
x
y
S
,
s
i
d
,
υ
′
,
m
> to S② On receiving the replayσ from S, deliver <
P
r
o
x
y
S
,
s
i
d
,
υ
′
,
m
,
σ
> to the party P
b and record <
m
,
σ
>(5) On input<
U
n
s
,
s
i
d
,
σ
> from P
b, verify whether s
i
d
=
<
P
b
,
s
i
d
′
>. If not, then ignore this. Else, do the following:① If<
m
,
σ
> has been recorded, then achieve f
←
υ
β
,
σ
,
m
,
s
i
d and send <
m
,
f
=
1
> to P
b② Else, return<
U
n
s
,
s
i
d
,
σ
> to S and obtainm from S, and then send <
m
,
f
=
0
> to P
b


## 6.3. Proof of UC Security

Theorem 8.
Ifπ
I
B
P
S
P satisfies the IND-CCA2 security, then π
I
B
P
S
P can securely realize F
I
B
P
S
P in the UC framework.Proof.
Assume the protocolπ
I
B
P
S
P satisfies the IND-CCA2 security; then π
I
B
P
S
P can securely realize F
I
B
P
S in the UC framework. i.e., if no probabilistic polynomial time A winsIND-IBPS-CCA2 with nonnegligible advantage, then any environment Z cannot distinguish whether it is interacting with π
I
B
P
S
P and A in the real-life model or with F
I
B
P
S
P and S in the ideal model.EnvironmentZ proceeds as follows.(1)Z delivers a request onSetup. On receiving <
S
e
t
u
p
,
s
i
d
>, Z inputs β and activates A(2) On receiving a request on<
E
x
t
r
a
c
t
,
s
i
d
> from A, Z activates some party P
i with input <
E
x
t
r
a
c
t
,
s
i
d
> and outputs <
Y
i
,
S
i
> to A(3) On receiving<
P
K
e
y
G
e
n
,
s
i
d
> from A, Z activates P
a and P
p with <
P
K
e
y
G
e
n
,
s
i
d
> and outputsS
ap to A(4) On receiving<
P
r
o
x
y
S
,
s
i
d
,
m
> from A, Z activates P
p with input <
P
r
o
x
y
S
,
s
i
d
,
m
> and outputs σ to A(5) On receiving a request on<
U
n
s
,
s
i
d
,
σ
> from A, Z activates P
b with input <
U
n
s
,
s
i
d
,
σ
> and outputs the valuef of υ
σ
,
m
,
s
i
dIfA winsIND-IBPS-CCA2, Z outputs f
=
1. In addition, the probability that Z outputs 1 is 0 in the ideal model. Obviously, if π
I
B
P
S
P satisfies the IND-CCA2 security, π
I
B
P
S
P can securely realize F
I
B
P
S
P in the UC framework.Theorem 9.
Ifπ
I
B
P
S
P can securely realize F
I
B
P
S
P in the UC framework, then π
I
B
P
S
P satisfies the IND-CCA2 security.Proof.
Here we construct an ideal adversaryS such that no environment Z can tell with nonnegligible advantage whether it interacts with F
I
B
P
S
P and S in the ideal model or with π
I
B
P
S
P and A in the real-life model.S runs a copy of A and sends the input from Z to A, and simultaneously any output from A is considered as the output of S.(1) On receiving<
S
e
t
u
p
,
s
i
d
> from F
I
B
P
S
P, it runs the Setup algorithm and obtains <
β
,
s
>, and then returns <
S
e
t
u
p
,
s
i
d
,
υ
,
β
>(2) On receiving<
E
x
t
r
a
c
t
,
s
i
d
> from F
I
B
P
S
P, it invokes the extraction algorithm to achieve <
Y
i
,
S
i
> and then returns <
Y
i
,
S
i
>(3) On receiving<
P
K
e
y
G
e
n
,
s
i
d
> from F
I
B
P
S
P, it invokes the proxy key generation algorithm to obtainS
ap and then returnsS
ap(4) On receiving<
P
r
o
x
y
S
,
s
i
d
,
m
> from F
I
B
P
S
P, it runs the proxy signcryption algorithm to obtain σ and then returns σ(5) On receiving<
U
n
s
,
s
i
d
,
σ
> from F
I
B
P
S
P, it runs the unsigncryption algorithm to obtainm and then returnsm. Then it returns f
←
υ
σ
,
m
,
s
i
d. If P
b is corrupted, then deliver <
m
,
f
=
0
> to all parties; else, deliver <
m
,
f
=
1
> to P
bIn the following, we prove that the ideal adversaryS simulates the real-life adversary A.(1) On receivingβ from the challengerC, Z is invoked. On receiving <
S
e
t
u
p
,
s
i
d
> from Z, it issues a request toC that returns η
=
s
i
d
,
β as the answer(2) On receiving<
E
x
t
r
a
c
t
,
s
i
d
> from Z, it issues a request toC that returns <
Y
i
,
S
i
> as the answer(3) On receiving<
P
K
e
y
G
e
n
,
s
i
d
> from Z, it issues a request toC that returnsS
ap as the answer(4) On receiving<
P
r
o
x
y
S
,
s
i
d
,
m
> from Z, it issues a request toC that responds as follows:① IfP
p is uncorrupt, send <
P
r
o
x
y
S
,
s
i
d
,
|
m
|
> toC that returns σ
′ as the answer② IfP
p is corrupt, deliver <
P
r
o
x
y
S
,
s
i
d
,
m
> toC that returns σ as the answer(5) On input<
U
n
s
,
s
i
d
,
σ
> from Z, it issues a request toC that responds as follows:① If bothP
p and P
b are not corrupt, then send <
U
n
s
,
s
i
d
,
σ
′
> toC that returns m
′ as the answer② IfP
p is corrupt and P
b is not corrupt, then send <
U
n
s
,
s
i
d
,
σ
> toC that returns m
′ as the answer③ IfP
p is not corrupt and P
b is corrupt, then send <
U
n
s
,
s
i
d
,
σ
′
> toC that returns m
′ as the answer④ If bothP
p and P
b are corrupt, then deliver <
U
n
s
,
s
i
d
,
σ
> toC that returnsm as the answerThen,Z obtains f
←
υ
β
,
σ
,
m
,
s
i
d and returnsf. If f
=
1, this shows that the ciphertext is valid; else, it is invalid.According to the running process, we define four events: forZ, the occurrence of each event means that it cannot tell whether it interacts with π
I
B
P
S
P and A in the real-life model or with F
I
B
P
S
P and S in the ideal model.Event 1:P
p and P
b are both uncorrupt. In the real-life process, P
p obtains σ ofm by the proxy signcryption algorithm and sends σ to P
b. And P
b can unsigncrypt σ to obtainm and verifies the validity of σ. In the ideal process, S simulates P
b to obtain σ
′ of m
′ of its choice and sends σ
′ to P
b. S answers with m
′ when P
b unsigncrypts σ
′; the unsigncryption succeeds if f
=
1.Event 2:P
p is not corrupt and P
b is corrupt. In the real-life process, Z cannot determine which message is signcrypted by P
p. In the ideal process, S simulates P
p with m
′ of its choice to obtain σ
′ and forwards σ
′ to A. It follows that Z cannot distinguish <
m
,
σ
> and <
m
′
,
σ
′
>.Event 3:P
p is corrupt and P
b is not corrupt. If P
p is corrupt, this shows A obtains the process of proxy signcryption. On the other hand, S can invoke a copy of A; therefore, S can obtain the same information with A. That is to say, when S makes the proxy signcryption, S can perfectly simulate P
p that is corrupt.Event 4:P
p and P
b are both corrupt. In this case, S can obtain all their input information; i.e., S can generate real data to simulate the execution of protocol.In the four events defined above, ifZ can tell whether it interacts with <
π
I
B
P
S
P
,
A
> or with <
F
I
B
P
S
P
,
S
> with probability |
Pr
⁡
Z
π
I
B
P
S
P
,
A
→
1
-
Pr
⁡
Z
F
I
B
P
S
P
,
S
→
1
|, then A winsIND-IBPS-CCA2 with probability |
Pr
⁡
Z
π
I
B
P
S
P
,
A
→
1
-
Pr
⁡
Z
F
I
B
P
S
P
,
S
→
1
|. In the real world, Pr
⁡
Z
π
I
B
P
S
P
,
A
→
1 is a negligible probability; in addition, Pr
⁡
Z
F
I
B
P
S
P
,
S
→
1 is always equal to zero in the ideal world. Therefore, we readily obtain that |
Pr
⁡
Z
π
I
B
P
S
P
,
A
→
1
-
Pr
⁡
Z
F
I
B
P
S
P
,
S
→
1
| is negligible.Theorem 10.
In the UC framework,π
I
B
P
S
P satisfies the existential unforgeability against adaptive chosen-message attacks.Proof.
Assume there exists a forger. Here we construct an environmentZ and an adversary A such that, for any adversary A, Z cannot tell with nonnegligible probability whether it interacts with π
I
B
P
S
P and A in the real-life model or with F
I
B
P
S
P and S in the ideal model.Z proceeds as below. On receiving a request on proxy signcryption of A, Z activates P
p and outputs the ciphertext σ to A. On receiving a request on unsigncryption of A, Z activates P
b and outputs <
m
,
f
> to A.A proceeds as follows. A first invokes the forger. As the forger requests to signcrypt a messagem, A requests Z to signcrypt a messagem and outputs the ciphertext σ
′ to the forger. On receiving a request on unsigncryption of the forger, A requests Z to unsigncrypt σ
′ and outputs <
m
′
,
f
> to A and simultaneously delivers σ
′ to the forger. Once the forger receives m
′ and f
=
1, then the forgery σ
′ is valid and at this time Z outputs f
=
1. Clearly, if the forger winsUF-IBPS-CMA-I orUF-IBPS-CMA-Iwith probability ε, then the forger can succeed in forging valid proxy signcryption. Assume that such a forger exists with nonnegligible probability ε; then the probability that Z outputs f
=
1 is nonnegligible. However, the probability that Z outputs f
=
1 is always equal to zero in the ideal model. In other words, if such a forger exists, Z can always tell with nonnegligible probability whether it interacts with π
I
B
P
S
P and A or with F
I
B
P
S
P and S. It contracts with the initial assumption inTheorem10. As mentioned above, such a forger cannot exist; that is to say, π
I
B
P
S
P satisfies the existential unforgeability against adaptive chosen-message attacks in the UC framework.


## 7. Efficiency Analysis

In this section, we compare our protocol with similar protocols in terms of computational complexity together with UC security and semantic security (see Table1). In Table 1, E is one exponent operation, P is one pairing operation inG
2, M is one scalar multiplication operation inG
1, and H is one hash operation. Moreover, "√" means that one cryptography protocol satisfies the relevant security and "×" means that one cryptography protocol does not satisfy the relevant security.Table 1
Comparison of computational efficiency and security.
Protocols
PKeyGen
ProxyS
Uns
Total
UC security
Semantic security
Protocol [4]
1H+1E+3M+2P
2H+2E+3M+2P
3H+1E+1M+5P
6H+4E+7M+9P
×
√
Protocol [19]
1H+1E+2M+2P
3H+2E+1M+2P
2H+4E+6P
6H+7E+3M+10P
×
√
IBPSP
1H+1E+2M+2P
2H+1E+3M+1P
3H+1E+1M+4P
6H+3E+6M+7P
√
√Lett
H denote the time cost of one hash operation. According to the literature [21], we can summarize and deduce the time cost of all operations as follows: P
≈
1440
t
H, E
≈
21
t
H, M
≈
29
t
H, and H
≈
t
H. We can readily obtain that the time cost of our protocol is 10323 t
H. Following the comparison analysis, there are 13253 t
H and 14640 t
H in protocols [4, 19], respectively.From the comparison in Table1, we obtain that the computation cost of our IBPSP is lower than those of other protocols. It is known from Table 1 that our IBPSP has both semantic security and UC security, but other protocols cannot guarantee the security in the UC framework. All the protocols in Table 1 satisfy the semantic security in the random oracle model.


## 8. Summary

The UC security framework provides the theory basis for the design of protocols in a complex and unpredictable environment. In this paper, we construct an IBPSP with universal composability and prove its semantic security in the random oracle model. We also define the ideal functionality of the IBPSP and prove the equivalence between IBPSP with universal composability and its IND-CCA2 and UF-CMA security. Our IBPSP can guarantee security even when it is composed of an arbitrary set of protocols, or when it is used as a component of an arbitrary system. What is more, our IBPSP can guarantee security even when it concurrently runs with an unbounded number of protocol instances.



---

*Source: 9531784-2018-12-02.xml*