Certificatebased cryptography is a new cryptographic paradigm that provides an interesting balance between identitybased cryptography and traditional public key cryptography. It not only simplifies the complicated certificate management problem in traditional public key cryptography, but also eliminates the key escrow problem in identitybased cryptography. As an extension of the signcryption in certificatebased cryptography, certificatebased signcryption provides the functionalities of certificatebased encryption and certificatebased signature simultaneously. However, to the best of our knowledge, all constructions of certificatebased signcryption in the literature so far have to be based on the costly bilinear pairings. In this paper, we propose a certificatebased signcryption scheme that does not depend on the bilinear pairings. The proposed scheme is provably secure in the random oracle model. Due to avoiding the computationallyheavy paring operations, the proposed scheme significantly reduces the cost of computation and outperforms the previous certificatebased signcryption schemes.
1. Introduction
I
n publickey cryptography, each user has a public key and a private key. The public key is published and publicly accessible while the corresponding private key is kept secret by its owner. In traditional public key cryptography, each public key is generated with no connection to the identity of its owner. Therefore, a public key infrastructure (PKI) is employed for vouching the relationship between a user’s identity and a public key by certificates. However, the traditional PKI technology is faced with many challenges in practice, especially the complicated certificate management problem. In 1984, Shamir
[1]
introduced the concept of identitybased cryptography. In identitybased cryptography, a user’s public key could be an arbitrary string related to his identity and his private key is computed from his identity by a trusted authority called private key generator (PKG). The biggest merit of identitybased cryptography is that it eliminates the need for public key certificates. However, identitybased cryptography inevitably suffers from the key escrow problem since all the users’ private keys are known to the PKG.
In order to fill the gap between traditional public key cryptography and identitybased cryptography, AlRiyami and Paterson
[2]
proposed the notion of certificateless public key cryptography in Asiacrypt 2003. In certificateless public key cryptography, a trusted third party called key generation center (KGC) is employed for generating a partial private key for each user. Each user independently generates a pair of secret key and public key, and then combines his own secret key with the partial private key from the KGC to generate his full private key. Since KGC does not know any user’s private key, certificateless public key cryptography overcomes the key escrow problem. However, as partial private keys should be sent from KGC to users over secure channels, certificateless public key cryptography suffers from the key distribution problem.
In Eurocrypt 2003, Gentry
[3]
introduced another new paradigm called certificatebased cryptography that represents an interesting balance between identitybased cryptography and traditional public key cryptography. As in traditional public key cryptography, each user in certificatebased cryptography generates a pair of public key and private key, and then requests a certificate from a trusted third party called certifier. The difference is that certificatebased cryptography provides an effective implicit certificate mechanism so that a user needs both his private key and certificate to perform cryptographic operations (such as decryption and signing), while the other communication parties need not obtain the fresh information on this user’s certificate status. As a result, certificatebased cryptography eliminates the thirdparty queries for the certificate status and simplifies the certificate revocation problem in traditional PKI. Furthermore, since the certifier does not know any user’s private key and the certificates can be sent to their owners publicly, certificatebased cryptography overcomes both the key escrow and distribution problems.
Since its advent, certificatebased cryptography has attracted great interest in the research community and many schemes have been proposed, including many encryption schemes (
e.g.
[4

10]
) and signature schemes (
e.g.
[11

16]
). As an extension of the signcryption
[17]
in the certificatebased setting, Li
et al.
[18]
introduced the concept of certificatebased signcryption, which simultaneously provides the functionalities of certificatebased encryption and certificatebased signature. To the best of our knowledge, there exist three certificatebased signcryption schemes in the literature so far. All these schemes are based on the bilinear pairings. In
[18]
, Li
et al.
proposed the first certificatebased signcryption scheme based on Chen and MaloneLee’s identitybased signcryption scheme
[19]
. A subsequent paper by Luo
et al.
[20]
proposed a new certificatebased signcryption scheme alone with a security model. However, Luo
et al.
only partly proved the security of their scheme in the random oracle model
[21]
. Recently, Li
et al.
[22]
proposed a publicly verifiable certificatebased signcryption scheme which is provably secure in the random oracle model.
In this paper, we focus on the construction of certificatebased signcryption that does not depend on the costly bilinear pairings. As we know, compared with other common cryptographic operations such as prime modular exponentiations in finite fields, the bilinear pairings may be the most expensive ones. As pairing operations will greatly aggravate the computation load of a device, they are extremely disliked by the powerconstrained devices, such as wireless sensors, mobile intelligent terminals, etc. Therefore, it is interesting and worthwhile to construct cryptographic schemes without relying on bilinear parings. Based on the Schnorr signature scheme
[23
,
24]
and the enhanced ElGamal public key encryption scheme proposed by Fujisaki and Okamoto
[25]
, we develop a pairingfree certificatebased signcryption scheme. In the random oracle model, we prove that the proposed certificatebased signcryption scheme has chosenciphertext security under the gap DiffieHellman assumption and unforgeability security under the gap discrete logarithm assumption. Without pairings, our scheme significantly reduces the cost of computation and is more efficient than the previous pairingbased certificatebased signcryption schemes. This interesting property makes it be particularly suitable for the computationlimited environments, such as wireless sensor networks and mobile wireless networks.
In Section 2, we review some computational assumptions related to our paper. In Section 3, we present the definition and security model of certificatebased signcryption. The proposed certificatebased signcryption scheme is described in Section 4 and analyzed in Section 5 respectively. Finally, we draw our conclusion in Section 6.
2. Computational Assumptions
Let
k
be a security parameter and
p
be a
k
bit prime number. Let
G
denote a cyclic group of prime order
p
, and
g
a generator of the group
G
. Below, we review the computational assumptions that are used to prove the security of our proposed certificatebased signcryption scheme.
Definition 1
[26]
. The gap DiffieHellman (GDH) problem in
G
is, given a tuple (
g
,
g^{a}
,
g^{b}
) for unknown
a
,
b
∈
Z
^{*}
_{p}
and access to a decisional DiffieHellman (DDH) oracle
O^{DDH}
that takes (
g
,
g^{u}
,
g^{v}
,
z
) as input and outputs 1 if
z
=
g^{uv}
and 0 otherwise, to compute
g^{ab}
. The advantage of any probabilistic polynomialtime algorithm
A_{GDH}
in solving the GDH problem in
G
is defined as
The GDH assumption is that, for any probabilistic polynomialtime algorithm
A_{GDH}
, the advantage
Adv
(
A_{GDH}
) is negligible.
Definition 2
[27]
. The gap Discrete Logarithm (GDL) problem in
G
is, given a tuple (
g
,
g^{a}
) for unknown
a
∈
Z
^{*}
_{p}
and access to a restricted DDH oracle
O^{rDDH}
that takes (
g
,
g^{a}
,
g^{b}
,
z
) as input and outputs 1 if
z
=
g^{ab}
and 0 otherwise, to compute
a
. The advantage of any probabilistic polynomialtime algorithm
A_{GDL}
in solving the GDL problem in
G
is defined as
The GDL assumption is that, for any probabilistic polynomialtime algorithm
A_{GDL}
, the advantage
Adv
(
A_{GDL}
) is negligible.
3. Definition and Security Model of CertificateBased Signcryption
In this paper, a certificatebased signcryption scheme is composed of the following five algorithms: (1) System setup algorithm
Setup
, which is performed by a certifier to generate a master key and a list of public system parameters; (2) Keypair generation algorithm
KeyPairGen
, which is performed by the user to generate a pair of private key and partial public key; (3) Certification algorithm
Certify
, which is performed by a certifier to generate a certificate and public key for each user in the system; (4)
Signcrypt
ion algorithm
Signcrypt
, which is performed by a sender to signcrypt the messages; (5) Designcryption algorithm
Designcrypt
, which is performed by a receiver to designcrypt the ciphertext sent to him.
Fig. 1
gives the functional description of a certificatebased signcryption scheme.
Functional description of certificatebased signcryption
Definition 3.
A certificatebased signcryption scheme Π = (
Setup
,
KeyPairGen
,
Certify
,
Signcrypt
,
Designcrypt
) is said to be correct if for any message
m
,
m
=
Designcrypt
(
params
,
Signcrypt
(
params
,
m
,
id_{S}
,
PK_{S}
,
SK_{S}
,
Cert_{S}
,
id_{R}
,
PK_{R}
),
id_{R}
,
SK_{R}
,
Cert_{R}
,
id_{S}
,
PK_{S}
), where
params
are obtained from the system setup algorithm
Setup
, (
SK_{S}
,
PK_{S}
,
Cert_{S}
) and (
SK_{R}
,
PK_{R}
,
Cert_{R}
) are respectively generated according to the the specifications of the keypair generation algorithm
KeyPairGen
and the certification algorithm
Certify
.
As introduced in
[20
,
22]
, the security model for certificatebased signcryption includes two types of adversaries: TypeI and TypeII. A TypeI adversary (denoted by
A_{I}
) simulates a user who wants to gain some information about a message sent to him from its encryption without a certificate. A TypeII adversary (denoted by
A_{II}
) simulates a malicious certifier in possession of the master key who wants to attack a target user without the knowledge of this user’s private key.
To simulate potential attacking scenarios, we will use the following six oracles which can be accessed by the adversaries. We assume that the game simulator keeps a history of “queryanswer” while interacting with the adversaries. The six oracles are described as follows:
(1)
O^{CreateUserI}
(
id_{U}
): This oracle is only queried by the TypeI adversary
A_{I}
. On input an identity
id_{U}
, if
id_{U}
has already been created, the game simulator responds with the public key
PK_{U}
associated with the identity
id_{U}
. Otherwise, the game simulator generates a set of private key
SK_{U}
, public key
PK_{U}
and certificate
Cert_{U}
for the identity
id_{U}
, and then returns
PK_{U}
as the output. In this case,
id_{U}
is said to be created. For simplicity, we assume that other oracles only respond to an identity which has been created.
(2)
O^{CreateUserII}
(
id_{U}
): This oracle is only queried by the TypeII adversary
A_{II}
. On input an identity
id_{U}
, if
id_{U}
has already been created, the game simulator responds with the public key
PK_{U}
associated with the identity
id_{U}
. Otherwise, the game simulator first generates a private key
SK_{U}
and a partial public key
PPK_{U}
for the identity
id_{U}
, and then outputs
PPK_{U}
to
A_{II}
. Different from
O^{CreateUserI}
, this oracle requires
A_{II}
to help the game simulator to create a new user. As
A_{II}
simulates a malicious certifier who will generate a full public key and a certificate for any user by itself, it is possible that the game simulator is not aware of the secret(s) used by
A_{II}
to generate the public key and the certificate of a user. Therefore, when creating a new user,
A_{II}
should submit the secret(s) to the game simulator. Under the help of
A_{II}
, the game simulator generates a full public key
PK_{U}
and a certificate
Cert_{U}
for the identity
id_{U}
. In this case,
id_{U}
is said to be created. Similarly, we assume that other oracles only respond to an identity which has been created.
(3)
O^{RequestPrivateKey}
(
id_{U}
): On input an identity
id_{U}
, the game simulator outputs the private key
SK_{U}
associated with the identity
id_{U}
.
(4)
O^{RequestCertificate}
(
id_{U}
): On input an identity
id_{U}
, the game simulator outputs the certificate
Cert_{U}
associated with the identity
id_{U}
.
(5)
O^{Signcrypt}
(
m
,
id_{S}
,
id_{R}
): On input a message
m
, a sender’s identity
id_{S}
and a receiver’s identity
id_{R}
, the game simulator responds with the result of
Signcrypt
(
params
,
m
,
id_{S}
,
PK_{S}
,
SK_{S}
,
Cert_{S}
,
id_{R}
,
PK_{R}
). Note that we disallow queries where
id_{S}
=
id_{R}
.
(6)
O^{Designcrypt}
(
σ
,
id_{S}
,
id_{R}
): On input a ciphertext
σ
, a sender’s identity
id_{S}
and a receiver’s identity
id_{R}
, the challenger responds with the result of
Designcrypt
(
params
,
σ
,
id_{R}
,
SK_{R}
,
Cert_{R}
,
id_{S}
,
PK_{S}
). Again, we disallow queries where
id_{S}
=
id_{R}
.
A certificatebased signcryption scheme should satisfy both confidentiality (indistinguishability against adaptive chosenciphertext attacks (INDCBSCCCA2)) and unforgeability (existential unforgeability against adaptive chosenmessages attacks (EUFCBSCCMA)).
For the confidentiality, we consider the following two different adversarial games “INDCBSCCCA2 GameI” and “INDCBSCCCA2 GameII”. INDCBSCCCA2 GameI is the game played between the TypeI adversary
A_{I}
and a game simulator, in which
state
represents some state information,
OraclesI
means that the adversary
A_{I}
can adaptively query the oracles {
O^{CreateUserI}
,
O^{RequestPrivateKey}
,
O^{RequestCertificate}
,
O^{Signcrypt}
,
O^{Designcrypt}
} with the following constraints: (1) The identity
id
^{*}
_{R}
cannot be submitted to the oracle
O^{RequestCertificate}
; (2) (
σ
^{*}
,
id
^{*}
_{S}
,
id
^{*}
_{R}
) cannot be submitted to the oracle
O^{Designcrypt}
. INDCBSCCCA2 GameII is the game played between the TypeII adversary
A_{II}
and a game simulator, in which
state
represents some state information,
OraclesII
means that the adversary
A_{II}
can adaptively query the oracles {
O^{CreateUserII}
,
O^{RequestPrivateKey}
,
O^{Signcrypt}
,
O^{Designcrypt}
} with the following constraints: (1) The identity
id
^{*}
_{R}
cannot be submitted to the oracle
O^{RequestPrivateKey}
; (2) (
σ
^{*}
,
id
^{*}
_{S}
,
id
^{*}
_{R}
) cannot be submitted to the oracle
O^{Designcrypt}
.
In both two games, we say that an adversary wins the game if
b
=
b'
. The adversary’s advantage in winning the game is defined to be
Adv
(
A_{X}
) = 2Pr[
b
=
b'
]  1/2, where
X
is either I or II.
Definition 4.
A certificatebased signcryption scheme is said to be INDCBSCCCA2 secure if no probabilistic polynomialtime adversary has nonnegligible advantage in both the games INDCBSCCCA2 GameI and INDCBSCCCA2 GameII.
For the unforgeability, we consider the following two different adversarial games “EUFCBSCCMA GameI” and “EUFCBSCCMA GameII”. EUFCBSCCMA GameI is the game played between the TypeI adversary
A_{I}
and a game simulator, in which
OraclesIII
means that the adversary
A_{I}
can adaptively query the oracles {
O^{CreateUserI}
,
O^{RequestPrivateKey}
,
O^{RequestCertificate}
,
O^{Signcrypt}
,
O^{Designcrypt}
} with the following constraints: (1) The identity
id
^{*}
_{S}
cannot be submitted to the oracle
O^{RequestCertificate}
; (2) (
σ
^{*}
,
id
^{*}
_{S}
,
id
^{*}
_{R}
) is not produced by the oracle
O^{Signcrypt}
. EUFCBSCCMA GameII is the game played between the TypeII adversary
A_{II}
and a game simulator, in which
OraclesIV
means that the adversary
A_{II}
can adaptively query the oracles {
O^{CreateUserII}
,
O^{RequestPrivateKey}
,
O^{Signcrypt}
,
O^{Designcrypt}
} with the following constraints: (1) The identity
id
^{*}
_{S}
cannot be submitted to the oracle
O^{RequestPrivateKey}
; (2) (
σ
^{*}
,
id
^{*}
_{S}
,
id
^{*}
_{R}
) is not produced by the oracle
O^{Signcrypt}
.
In both two games, we say that an adversary wins the game if it outputs a valid forgery (
σ
^{*}
,
id
^{*}
_{S}
,
id
^{*}
_{R}
), namely that the result of
Designcrypt
(
params
,
σ
^{*}
,
id
^{*}
_{R}
,
SK
^{*}
_{R}
,
Cert
^{*}
_{R}
,
id
^{*}
_{S}
,
PK
^{*}
_{S}
) is not the symbol ⊥ . The adversary’s advantage is defined to be the probability that it wins the game.
Definition 5.
A certificatebased signcryption scheme is said to be EUFCBSCCMA secure if no probabilistic polynomialtime adversary has nonnegligible advantage in both the adversarial games EUFCBSCCMA GameI and EUFCBSCCMA GameII.
4. Description of the Proposed CertificateBased Signcryption Scheme
We now present the proposed certificatebased signcryption scheme. As mentioned previously, our scheme is based on the Schnorr signature scheme
[23
,
24]
and the enhanced ElGamal public key encryption scheme proposed by Fujisaki and Okamoto
[25]
. A formal description of the scheme is as follows:
(1)
Setup
(
k
): The certifier performs as follows: choose a group
G
of
k
bit prime order
p
and a random generator
g
∈
G
; choose a random value
α
∈
Z
^{*}
_{p}
and compute
g
_{1}
=
g^{a}
; choose three cryptographic hash functions
H
_{1}
: {0,1}
^{*}
×
G
×
G
→
Z
^{*}
_{p}
,
H
_{2}
:{0,1}
^{lm}
×
G
× {0,1}
^{*}
×
G
×
G
→
Z
^{*}
_{p}
and
H
_{3}
:
G
→{0,1}
^{lm}
, where
l_{m}
denotes the bitlength of a plaintext; output a list of public parameters
params
= {
G
,
p
,
g
,
g
_{1}
,
l_{m}
,
H
_{1}
,
H
_{2}
,
H
_{3}
} and a master key
msk
=
α
.
(2)
KeyPairGen
(
params
): A user with identity
id_{U}
chooses a random value
x
∈
Z
^{*}
_{p}
as his private key
SK_{U}
and computes his partial public key
PPK_{U}
=
g^{x}
.
(3)
Certify
(
params
,
msk
,
id_{U}
,
PPK_{U}
): The certifier performs as follows: set
PK_{U}
^{(1)}
=
PPK_{U}
; choose a random value
y
∈
Z
^{*}
_{p}
and compute
PK_{U}
^{(2)}
=
g^{y}
; compute
Cert_{U}
=
y
+
αH
_{1}
(
id_{U}
,
PK_{U}
^{(1)}
,
PK_{U}
^{(2)}
); output the user
id_{U}
’s public key
PK_{U}
= (
PK_{U}
^{(1)}
,
PK_{U}
^{(2)}
) and certificate
Cert_{U}
.
(4)
Signcrypt
(
params
,
m
,
id_{S}
,
PK_{S}
,
SK_{S}
,
Cert_{S}
,
id_{R}
,
PK_{R}
): To send a message
m
∈ {0,1}
^{lm}
to a user
id_{R}
, the sender
id_{S}
does the following: choose a random value
r
∈
Z
^{*}
_{p}
and compute
R
=
g^{r}
; compute
u
=
r
(
SK_{S}
+
Cert_{S}
+
h
)
^{1}
, where
h
=
H
_{2}
(
m
,
R
,
id_{S}
,
PK_{S}
^{(1)}
,
PK_{S}
^{(2)}
); compute
v
= (
PK_{R}
^{(1)}
⋅,
PK_{R}
^{(2)}
⋅
g
_{1}
^{H1(idR,PKR(1),PKR(2))}
)
^{r}
and then
c
=
m
⊕
H
_{3}
(
v
); output the ciphertext
σ
= (
h
,
u
,
c
).
(5)
Designcrypt
(
params
,
σ
,
id_{R}
,
SK_{R}
,
Cert_{R}
,
id_{S}
,
PK_{S}
): To designcrypt a ciphertext
σ
from the sender
id_{S}
, the receiver
id_{R}
does the following: parse the ciphertext
σ
as (
h
,
u
,
c
); compute
R'
= (
PK_{S}
^{(1)}
⋅,
PK_{S}
^{(2)}
⋅
g
_{1}
^{H1(idS,PKS(1),PKS(2))}
⋅
g^{h}
)
^{u}
and then
v'
= (
R'
)
^{SKR+CertR}
; compute
m'
=
c
⊕
H
_{3}
(
v'
); check whether
h
=
H
_{2}
(
m'
,
R'
,
id_{S}
,
PK_{S}
^{(1)}
,
PK_{S}
^{(2)}
). If it does, output the message
m'
, otherwise output an invalid symbol ⊥.
5. Analysis of the Proposed CertificateBased Signcryption Scheme
 5.1 Correctness
Theorem 1.
The proposed certificatebased signcryption scheme is correct.
Proof. This theorem can be proved by the following equations:
R'
= (
PK_{S}
^{(1)}
⋅
PK_{S}
^{(2)}
⋅
g
_{1}
^{H1(idS,PKS(1),PKS(2))}
⋅
g^{h}
)
^{u}
=
=
g^{r}
=
R
,
v'
= (
R'
)
^{SKR+CertR}
=
g
^{r(SKR+CertR)}
= (
PK_{R}
^{(1)}
⋅
PK_{R}
^{(2)}
⋅
g
_{1}
^{H1(idR,PKR(1),PKR(2))}
)
^{r}
=
v
.
 5.2 Security
We show that our scheme achieves the INDCBSCCCA2 security under the GDH assumption and the EUFCBSCCMA security under the GDL assumption in the random oracle model.
Theorem 2.
In the random oracle model, the proposed certificatebased signcryption scheme is INDCBSCCCA2 secure under the GDH assumption.
This theorem can be proved by combining the following two lemmas.
Lemma 1.
Suppose that
H
_{1}
~
H
_{3}
are random oracles and
A_{I}
is a TypeI adversary against the INDCBCSCCA2 security of the proposed scheme with advantage
ε
and running time
τ
. Assume also that
A_{I}
makes at most
q_{cu}
queries to the oracle
O^{CreateUserI}
,
q_{pri}
queries to the oracle
O^{RequestPrivateKey}
,
q_{cer}
queries to the oracle
O^{RequestCertificate}
,
q_{sc}
queries to the oracle
O^{Signcrypt}
,
q_{dsc}
queries to the oracle
O^{Designcrypt}
and
q_{i}
queries to the random oracles
H_{i}
(1 ≤
i
≤ 3) respectively. Then there exists an algorithm
A_{GDH}
to solve the GDH problem in the group
G
with advantage
and running time
τ'
≤
τ
+ (
q
_{1}
+
q
_{2}
+
q
_{3}
+
q_{cer}
+
q_{pri}
)
O
(1) +
q_{cu}
(3
τ_{exp}
+
O
(1)) +
q_{sc}
(4
τ_{exp}
+
O
(1)) +
q_{dsc}
(4
τ_{exp}
+
τ_{DDH}
+
O
(1)), where
τ_{exp}
and
τ_{DDH}
respectively denote thetime for computing an exponentiation in
G
and the one for a call to the DDH oracle.
Proof. Assume that the algorithm
A_{GDH}
is given a random GDH problem instance (
G
,
p
,
g
,
g^{a}
,
g^{b}
,
O^{DDH}
). Its goal is to compute
g^{ab}
by interacting with
A_{I}
as follows:
At the beginning of the game, the algorithm
A_{GDH}
randomly chooses an index
θ
∈ [1,
q_{cu}
] and sets
g
_{1}
=
g^{a}
. It then starts INDCBCSCCA2 GameI by supplying the adversary
A_{I}
with the public parameters
params
= {
G
,
p
,
g
,
g
_{1}
,
l_{m}
,
H
_{1}
,
H
_{2}
,
H
_{3}
}, where
H
_{1}
~
H
_{3}
are random oracles controlled by
A_{GDH}
. Note that the certifier’s master key is the value
a
which is unknown to the algorithm
A_{GDH}
.
During the queryanswer phase, the adversary
A_{I}
can adaptively make queries to the oracles
H
_{1}
,
H
_{2}
,
H
_{3}
,
O^{CreateUserI}
,
O^{RequestPrivateKey}
,
O^{RequestCertificate}
,
O^{Signcrypt}
and
O^{Designcrypt}
. The algorithm
A_{GDH}
responds as follows:
H
_{1}
queries
:
A_{GDH}
maintains a list H
_{1}
List of tuples 〈
id_{i}
,
PK_{i}
^{(1)}
,
PK_{i}
^{(2)}
,
h
_{1}
〉. On receiving such a query on (
id_{i}
,
PK_{i}
^{(1)}
,
PK_{i}
^{(2)}
),
A_{GDH}
first checks if H
_{1}
List contains a tuple 〈
id_{i}
,
PK_{i}
^{(1)}
,
PK_{i}
^{(2)}
,
h
_{1}
〉. If it does,
A_{GDH}
outputs
h
_{1}
to
A_{I}
directly. Otherwise, it outputs a random value
h
_{1}
∈
Z
^{*}
_{p}
to
A_{I}
and inserts a new tuple 〈
id_{i}
,
PK_{i}
^{(1)}
,
PK_{i}
^{(2)}
,
h
_{1}
〉 into H
_{1}
List.
H
_{2}
queries
:
A_{GDH}
maintains a list H
_{2}
List of tuples 〈
m
,
R
,
id_{i}
,
PK_{i}
^{(1)}
,
PK_{i}
^{(2)}
,
h
_{2}
〉. On receiving such a query on (
m
,
R
,
id_{i}
,
PK_{i}
^{(1)}
,
PK_{i}
^{(2)}
),
A_{GDH}
first checks if H
_{2}
List contains a tuple 〈
m
,
R
,
id_{i}
,
PK_{i}
^{(1)}
,
PK_{i}
^{(2)}
,
h
_{2}
〉. If it does,
A_{GDH}
outputs
h
_{2}
to
A_{I}
directly. Otherwise, it outputs a random value
h
_{2}
∈
Z
^{*}
_{p}
to
A_{I}
and inserts a new tuple 〈
m
,
R
,
id_{i}
,
PK_{i}
^{(1)}
,
PK_{i}
^{(2)}
,
h
_{2}
〉 into H
_{2}
List.
H
_{3}
queries
:
A_{GDH}
maintains a list H
_{3}
List of tuples 〈
v
,
h
_{3}
〉. On receiving such a query on
v
,
A_{GDH}
first checks if H
_{3}
List contains a tuple 〈
v
,
h
_{3}
〉. If it does,
A_{GDH}
outputs
h
_{3}
to
A_{I}
directly. Otherwise, it outputs a random value
v
∈ {0,1}
^{lm}
to
A_{I}
and inserts a new tuple 〈
v
,
h
_{3}
〉 into H
_{3}
List.
O^{CreateUserI}
queries
:
A_{GDH}
maintains a list UserList of tuples 〈
id_{i}
,
SK_{i}
,
PK_{i}
,
Cert_{i}
〉. On receiving such a query on
id_{i}
,
A_{GDH}
performs as follows: (1) If UserList contains a tuple 〈
id_{i}
,
SK_{i}
,
PK_{i}
,
Cert_{i}
〉, output
PK_{i}
to
A_{I}
directly; (2) Otherwise, if
id_{i}
is the
θ
th distinct identity submitted to this oracle, choose two random values
x_{θ}
,
y_{θ}
∈
Z
^{*}
_{p}
, set
SK_{θ}
=
x_{θ}
and compute
PK_{θ}
=(
g^{xθ}
,
g^{yθ}
), insert a new tuple 〈
id_{θ}
,
SK_{θ}
,
PK_{θ}
, ⊥〉 into UserList and output
PK_{θ}
to
A_{I}
; (3) Otherwise, randomly choose
x_{i}
,
t_{i}
,
e_{i}
∈
Z
^{*}
_{p}
, set
SK_{i}
=
x_{i}
and
Cert_{i}
=
t_{i}
, compute
PK_{i}
= (
PK_{i}
^{(1)}
,
PK_{i}
^{(2)}
) = (
g^{xi}
,
g^{ti}
,
g
_{1}
^{−ei}
), insert 〈
id_{i}
,
PK_{i}
^{(1)}
,
PK_{i}
^{(2)}
,
e_{i}
〉 and 〈
id_{i}
,
SK_{i}
,
PK_{i}
,
Cert_{i}
〉 into H
_{1}
List and UserList respectively, and output
PK_{i}
to
A_{I}
.
O^{RequestPrivateKey}
queries
: On receiving such a query on
id_{i}
,
A_{GDH}
retrieves a tuple of the form 〈
id_{i}
,
SK_{i}
,
PK_{i}
,
Cert_{i}
〉 from the list UserList and returns
SK_{i}
to
A_{I}
.
O^{RequestCertificate}
queries
: On receiving such a query on
id_{i}
,
A_{GDH}
aborts if
id_{i}
=
id_{θ}
. Otherwise, it retrieves a tuple of the form 〈
id_{i}
,
SK_{i}
,
PK_{i}
,
Cert_{i}
〉 from UserList and returns
Cert_{i}
to
A_{I}
.
O^{Signcrypt}
queries
: On receiving such a query on (
m
,
id_{S}
,
id_{R}
),
A_{GDH}
does the following: (1) If
id_{S}
=
id_{θ}
,
A_{GDH}
randomly chooses
u
,
h
_{2}
∈
Z
^{*}
_{p}
,
h
_{3}
∈{0,1}
^{lm}
, runs the simulation algorithm for the random oracle
H
_{1}
to get
h
_{1}
=
H
_{1}
(
id_{S}
,
PK_{S}
^{(1)}
,
PK_{S}
^{(2)}
), and computes
R
= (
⋅
g
_{1}
^{h1}
⋅
g
^{h2}
)
^{u}
,
v
=
R
^{SKR+CertR}
,
c
=
m
⊕
h
_{3}
. Then,
A_{GDH}
inserts 〈
m
,
R
,
id_{θ}
,
PK_{θ}
^{(1)}
,
PK_{θ}
^{(2)}
,
h
_{2}
〉 and 〈
v
,
h
_{3}
〉 into H
_{2}
List and H
_{3}
List respectively and returns
σ
= (
h
_{2}
,
u
,
c
) as the ciphertext to
A_{I}
. Note that
A_{GDH}
fails if H
_{2}
List or H
_{3}
List is already defined in the corresponding value but this only happens with probability smaller than (
q
_{2}
+
q
_{3}
+ 2
q_{sc}
)/2
^{k}
. (2) Otherwise,
A_{GDH}
can answer the query according to the specification of the algorithm
Signcrypt
since it knows the sender
id_{S}
’s private key and certificate.
O^{Designcrypt}
queries
: On receiving such a query on (
σ
= (
h
,
u
,
c
),
id_{S}
,
id_{R}
),
A_{GDH}
does the following: (1) If
id_{R}
=
id_{θ}
,
A_{GDH}
first runs the simulation algorithm for the random oracle
H
_{1}
to get
h
_{1}
=
H
_{1}
(
id_{R}
,
PK_{R}
^{(1)}
,
PK_{R}
^{(2)}
) and
h'
_{1}
=
H
_{1}
(
id_{S}
,
PK_{S}
^{(1)}
,
PK_{S}
^{(2)}
), and then checks if there exist a tuple 〈
m
,
R
,
id_{S}
,
PK_{S}
^{(1)}
,
PK_{S}
^{(2)}
,
h
〉 in H
_{2}
List and a tuple 〈
v
,
h
_{3}
〉 in H
_{3}
List such that
R
= (
PK_{S}
^{(1)}
⋅
PK_{S}
^{(2)}
⋅
g
_{1}
^{h'1}
⋅
g^{h}
)
^{u}
,
m
=
c
⊕
h
_{3}
and
O^{DDH}
(
g
,
R
,
PK_{R}
^{(1)}
⋅
PK_{R}
^{(2)}
⋅
g
_{1}
^{h1}
,
v
) = 1. If such two tuples exist,
A_{GDH}
returns
m
to
A_{I}
as the designcryption of
σ
; otherwise, it rejects
σ
. Note that a valid ciphertext is rejected with probability smaller than
q_{dsc}
/2
^{k}
across the whole game. (2) Otherwise,
A_{GDH}
designcrypts
σ
in the normal way since it knows the receiver
id_{R}
’s private key and certificate.
At the challenge phase,
A_{I}
outputs two distinct messages
m
_{0}
and
m
_{1}
of equal length, a sender identity
id
^{*}
_{S}
and a receiver identity
id
^{*}
_{R}
, on which it wants to be challenged. If
id
^{*}
_{R}
id_{θ}
≠, then
A_{GDH}
aborts. Otherwise,
A_{GDH}
randomly chooses
c
^{*}
∈ {0,1}
^{lm}
and
u
^{*}
,
h
^{*}
_{2}
, ∈
Z
^{*}
_{p}
, sets
R
^{*}
=
g^{b}
, and outputs
σ
^{*}
= (
h
^{*}
_{2}
,
u
^{*}
,
c
^{*}
) as the challenge ciphertext to
A_{I}
. Observe that the decryption of
c
^{*}
is
c
^{*}
⊕
H
_{3}
(
PK_{θ}
^{(1)}
⋅
PK_{θ}
^{(2)}
⋅
g
_{1}
^{H1(idθ, PKθ(1), PKθ(2))}
)
^{b}
).
At the guess phase,
A_{I}
outputs a bit which is ignored by
A_{GDH}
. Note that
A_{I}
cannot recognize that the challenge ciphertext
σ
^{*}
is an invalid ciphertext unless it queries
H
_{3}
(
PK_{θ}
^{(1)}
⋅
PK_{θ}
^{(2)}
⋅
g
_{1}
^{H1(idθ, PKθ(1), PKθ(2))}
)
^{b}
). It is clear that a successful
A_{I}
is very likely to query
H
_{3}
(
PK_{θ}
^{(1)}
⋅
PK_{θ}
^{(2)}
⋅
g
_{1}
^{H1(idθ, PKθ(1), PKθ(2))}
)
^{b}
) if the simulation is indistinguishable from a real attack environment. To produce a result,
A_{GDH}
randomly chooses a tuple 〈
v
,
h
_{3}
〉 from H
_{3}
List and outputs
as the solution to the given GDH problem. Obviously, if
v
= (
PK_{θ}
^{(1)}
⋅
PK_{θ}
^{(2)}
⋅
g
_{1}
^{H1(idθ, PKθ(1), PKθ(2))}
)
^{b}
, then we have
T
=
g^{ab}
.
This completes the simulation. We now estimate the advantage of
A_{GDH}
in solving the given GDH problem. From the above construction, the simulation fails if any of the following events occurs: (1)
E
_{1}
:
A_{I}
does not choose
id_{θ}
as the challenge receiver identity
id
^{*}
_{R}
; (2)
E
_{2}
:
A_{I}
queries
O^{RequestCertificate}
on the identity
id_{θ}
; (3)
E
_{3}
:
A_{GDH}
aborts in answer
A_{I}
’s query to
O^{Signcrypt}
because of a collision on
H
_{2}
or
H
_{3}
; (4)
E
_{4}
:
A_{GDH}
rejects a valid ciphertext at some point of the game. We clearly have that Pr[¬
E
_{1}
] = 1/
q_{cu}
and ¬
E
_{1}
implies ¬
E
_{2}
. We also already observed that Pr[
E
_{3}
] ≤
q_{sc}
(
q
_{2}
+
q
_{3}
+ 2
q_{sc}
)/2
^{k}
and Pr[
E
_{4}
] ≤
q_{dsc}
/2
^{k}
. Thus, we have that
Since
A_{GDH}
selects the correct tuple from H
_{3}
List with probability 1/(
q
_{3}
+
q_{sc}
), we have that the advantage of
A_{GDH}
in solving the GDH problem is
The time complexity of the algorithm
A_{GDH}
is dominated by the exponentiations and the calls to the DDH oracle in the oracle simulations. From the above description of
A_{GDH}
, it is easy to see that thetime complexity of
A_{GDH}
is bound by
τ'
≤
τ
+ (
q
_{1}
+
q
_{2}
+
q
_{3}
+
q_{cer}
+
q_{pri}
)
O
(1) +
q_{cu}
(3
τ_{exp}
+
O
(1)) +
q_{sc}
(4
τ_{exp}
+
O
(1)) +
q_{dsc}
(4
τ_{exp}
+
τ_{DDH}
+
O
(1)) , where
τ_{exp}
and
τ_{DDH}
respectively denote thetime for computing an exponentiation in
G
and the one for a call to the DDH oracle.
Lemma 2.
Suppose that
H
_{1}
~
H
_{3}
are random oracles and
A_{II}
is a TypeII adversary against the INDCBCSCCA2 security of the proposed scheme with advantage
ε
and running time
τ
. Assume also that
A_{II}
makes at most
q_{cu}
queries to the oracle
O^{CreateUserII}
,
q_{pri}
queries to the oracle
O^{RequesrPrivateKey}
,
q_{sc}
queries to the oracle
O^{Signcrypt}
,
q_{dsc}
queries to the oracle
O^{Designcrypt}
and
q_{i}
queries to the random oracles
H_{i}
(1 ≤
i
≤ 3). Then there exists an algorithm
A_{GDH}
to solve the GDH problem in the group
G
with advantage
and running time
τ'
≤
τ
+ (
q
_{1}
+
q
_{2}
+
q
_{3}
+
q_{pri}
)
O
(1) +
q_{cu}
(2
τ_{exp}
+
O
(1)) +
q_{sc}
(4
τ_{exp}
+
O
(1)) +
q_{dsc}
(4
τ_{exp}
+
τ_{DDH}
+
O
(1)), where
τ_{exp}
and
τ_{DDH}
respectively denote thetime for computing an exponentiation in
G
and the one for a call to the DDH oracle.
Proof. Assume that
A_{GDH}
is given a random GDH problem instance (
G
,
p
,
g
,
g^{a}
,
g^{b}
,
O^{DDH}
). Its goal is to compute
g^{ab}
by interacting with
A_{II}
as follows:
At the beginning of the game,
A_{GDH}
first randomly chooses
α
∈
Z
^{*}
_{p}
and an index
θ
∈ [1,
q_{cu}
]. It then computes
g
_{1}
=
g^{a}
and starts INDCBSCCCA2 GameII by supplying
A_{II}
with the master key
msk
=
α
and the public parameters
params
= {
G
,
p
,
g
,
g
_{1}
,
l_{m}
,
H
_{1}
,
H
_{2}
,
H
_{3}
}, where
H
_{1}
~
H
_{3}
are random oracles controlled by
A_{GDH}
.
During the questionanswer phase,
A_{II}
can adaptively make queries to the oracles
H
_{1}
,
H
_{2}
,
H
_{3}
,
O^{CreateUserII}
,
O^{RequestPrivateKey}
,
O^{Signcrypt}
and
O^{Designcrypt}
.
A_{GDH}
answers
A_{II}
’s queries to
H
_{1}
,
H
_{2}
,
H
_{3}
,
O^{Signcrypt}
and
O^{Designcrypt}
as in the proof of Lemma 1 and handles other queries as follows:
O^{CreateUserII}
queries
:
A_{GDH}
maintains a list UserList of tuples 〈
id_{i}
,
SK_{i}
,
PK_{i}
,
Cert_{i}
,
y_{i}
〉. On receiving such a query on
id_{i}
,
A_{GDH}
performs as follows: (1) If UserList contains a tuple 〈
id_{i}
,
SK_{i}
,
PK_{i}
,
Cert_{i}
,
y_{i}
〉, output
PK_{i}
to
A_{II}
directly. (2) Otherwise, if
id_{i}
is the
θ
th distinct identity submitted to this oracle, set
PK_{θ}
^{(1)}
=
g^{a}
and output
PK_{θ}
^{(1)}
to
A_{II}
. After receiving a value
y_{θ}
∈
Z
^{*}
_{p}
from
A_{II}
, compute
PK_{θ}
^{(2)}
=
g^{yθ}
, run the simulation algorithm for the random oracle
H
_{1}
to get a hash value
h
_{1}
=
H
_{1}
(
id_{θ}
,
PK_{θ}
^{(1)}
,
PK_{θ}
^{(2)}
), compute
Cert_{θ}
=
y_{θ}
+
αh
_{1}
and insert a new tuple 〈
id_{θ}
, ⊥,
PK_{θ}
,
Cert_{θ}
,
y_{θ}
〉 into UserList. (3) Otherwise, randomly choose
x_{i}
∈
Z
^{*}
_{p}
, set
SK_{i}
=
x_{i}
, compute
PK_{i}
^{(1)}
=
g^{xi}
and output
PK_{i}
^{(1)}
to
A_{II}
. After receiving a value
y_{i}
∈
Z
^{*}
_{p}
from
A_{II}
, compute
PK_{i}
^{(2)}
=
g^{yi}
, run the simulation algorithm for the random oracle
H
_{1}
to get a hash value
h
_{1}
=
H
_{1}
(
id_{i}
,
PK_{i}
^{(1)}
,
PK_{i}
^{(2)}
) , compute
Cert_{i}
=
y_{i}
+
αh
_{1}
and insert a new tuple 〈
id_{i}
,
SK_{i}
,
PK_{i}
,
Cert_{i}
,
y_{i}
〉 into UserList.
O^{RequestPrivateKey}
queries
: On receiving such a query on
id_{i}
,
A_{GDH}
aborts if
id_{i}
=
id_{θ}
. Otherwise, it retrieves a tuple of the form 〈
id_{i}
,
SK_{i}
,
PK_{i}
,
Cert_{i}
,
y_{i}
〉 from UserList and returns
SK_{i}
to
A_{II}
.
At the challenge phase,
A_{II}
outputs two distinct messages
m
_{0}
and
m
_{1}
of equal length, a sender identity
id
^{*}
_{S}
and a receiver identity
id
^{*}
_{R}
, on which it wants to be challenged. If
id
^{*}
_{R}
≠
id_{θ}
,
A_{GDH}
aborts. Otherwise,
A_{GDH}
randomly chooses
c
^{*}
∈ {0,1}
^{lm}
and
u
^{*}
,
h
^{*}
_{2}
, ∈
Z
^{*}
_{p}
, sets
R
^{*}
=
g^{b}
, and outputs
σ
^{*}
= (
h
^{*}
_{2}
,
u
^{*}
,
c
^{*}
) to
A_{II}
as the challenge ciphertext. Observe that the decryption of
c
^{*}
is
c
^{*}
⊕
H
_{3}
(
PK_{θ}
^{(1)}
⋅
PK_{θ}
^{(2)}
⋅
g
_{1}
^{H1(idθ,PKθ(1),PKθ(2))}
)
^{b}
).
At the guess phase,
A_{II}
outputs a bit which is ignored by
A_{GDH}
. Note that
A_{II}
cannot recognize that the challenge ciphertext
σ
^{*}
is not a valid ciphertext unless it queries
H
_{3}
(
PK_{θ}
^{(1)}
⋅
PK_{θ}
^{(2)}
⋅
g
_{1}
^{H1(idθ,PKθ(1),PKθ(2))}
)b). It is clear that a successful
A_{II}
is very likely to query
H
_{3}
(
PK_{θ}
^{(1)}
⋅
PK_{θ}
^{(2)}
⋅
g
_{1}
H
_{1}
(
id_{θ}
,
PK_{θ}
^{(1)}
,
PK_{θ}
^{(2)}
))
^{b}
). if the simulation is indistinguishable from a real attack environment. To produce a result,
A_{GDH}
randomly chooses a tuple 〈
v
,
h
_{3}
〉 from H
_{3}
List and outputs
as the solution to the given GDH problem. Obviously, if
v
= (
PK_{θ}
^{(1)}
⋅
PK_{θ}
^{(2)}
⋅
g
_{1}
^{H1(idθ,PKθ(1),PKθ(2))}
)
^{b}
, then we have
T
=
g^{ab}
.
We now estimate the advantage of
A_{GDH}
in solving the given GDH problem.
From the above construction, the simulation fails if any of the following events occurs: (1)
E
_{1}
:
A_{II}
does not choose
id_{θ}
as the challenge receiver identity
id
^{*}
_{R}
; (2)
E
_{2}
:
A_{II}
queries
O^{RequestPrivateKey}
on the identity
id_{θ}
; (3)
E
_{3}
:
A_{GDH}
aborts in answer
A_{II}
’s
O^{Signcrypt}
query because of a collision on
H
_{2}
or
H
_{3}
;(4)
E
_{4}
:
A_{GDH}
rejects a valid ciphertext at some point of the game. We clearly have that Pr[¬
E
_{1}
] = 1/
q_{cu}
and ¬
E
_{1}
implies ¬
E
_{2}
. We also already observed that Pr[
E
_{3}
] ≤
q_{sc}
(
q
_{2}
+
q
_{3}
+ 2
q_{sc}
)/2
^{k}
and Pr[
E
_{4}
] ≤
q_{dsc}
/2
^{k}
. Thus, we have that
Since
A_{GDH}
selects the correct tuple from H
_{3}
List with probability 1/(
q
_{3}
+
q_{sc}
), the advantage of
A_{GDH}
in solving the GDH problem is
The time complexity of the algorithm
A_{GDH}
is dominated by the exponentiations and the calls to the DDH oracle in the oracle simulations. From the above description of
A_{GDH}
, it is easy to see that thetime complexity of
A_{GDH}
is bound by
τ'
≤
τ
+ (
q
_{1}
+
q
_{2}
+
q
_{3}
+
q_{pri}
)
O
(1) +
q_{cu}
(2
τ_{exp}
+
O
(1)) +
q_{sc}
(4
τ_{exp}
+
O
(1)) +
q_{dsc}
(4
τ_{exp}
+
τ_{DDH}
+
O
(1)), where
τ_{exp}
and
τ_{DDH}
respectively denote thetime for computing an exponentiation in
G
and the one for a call to the DDH oracle.
Theorem 3.
In the random oracle model, the proposed certificatebased signcryption scheme is EUFCBSCCMA secure under the GDL assumption.
This theorem can be proved by combining the following two lemmas.
Lemma 3.
Suppose that
H
_{1}
~
H
_{3}
are random oracles and
A_{I}
is a TypeI adversary against the EUFCBSCCMA security of the proposed scheme who makes at most
q_{cu}
queries to the oracle
O^{CreateUserI}
,
q_{pri}
queries to the oracle
O^{RequestPrivateKey}
,
q_{cer}
queries to the oracle
O^{RequestCertificate}
,
q_{sc}
queries to the oracle
O^{Signcrypt}
,
q_{dsc}
queries to the oracle
O^{Designcrypt}
and
q_{i}
queries to the random oracles
H_{i}
(1 ≤
i
≤ 3). Assume also that
A_{I}
produces a forgery with probability
ε
≥ (
q_{sc}
+ 1)(
q_{sc}
+
q
_{2}
)/2
^{k}
within atime
τ
. Then there exists an algorithm
A_{GDL}
to solve the GDL problem in the group
G
with advantage
ε'
≥ 1/9 and running time
τ'
≤ 23
q_{cu}
q
_{2}
[
τ
+ (
q
_{1}
+
q
_{2}
+
q
_{3}
+
q_{cer}
+
q_{pri}
)
O
(1) +
q_{cu}
(2
τ_{exp}
+
O
(1)) +
q_{sc}
(4
τ_{exp}
+
O
(1)) +
q_{dsc}
(4
τ_{exp}
+
τ_{rDDH}
+
O
(1))][
ε
(1 
q_{dsc}
/2
^{k}
)(1 
q_{sc}
(
q
_{2}
+
q
_{3}
+ 2
q_{sc}
)/2
^{k}
)]
^{1}
, where
τ_{exp}
and
τ_{rDDH}
respectively denote thetime for computing an exponentiation in
G
and the one for a call to the restricted DDH oracle.
Proof. Assume that
A_{GDL}
is given a random GDL problem instance (
G
,
p
,
g
,
g^{a}
,
O^{rDDH}
). Its goal is to compute
a
by interacting with
A_{I}
as follows:
At the beginning of the game,
A_{GDL}
first randomly chooses
α
∈
Z
^{*}
_{p}
and an index
θ
∈ [1,
q_{cu}
]. It then computes
g
_{1}
=
g^{α}
and starts EUFCBSCCMA GameI by supplying
A_{I}
with the public parameters
params
= {
G
,
p
,
g
,
g
_{1}
,
l_{m}
,
H
_{1}
,
H
_{2}
,
H
_{3}
}, where
H
_{1}
~
H
_{3}
are random oracles controlled by
A_{GDL}
.
During the queryanswer phase,
A_{I}
can adaptively make queries to the oracles
H
_{1}
,
H
_{2}
,
H
_{3}
,
O^{CreateUserI}
,
O^{RequestPrivateKey}
,
O^{RequestCertificate}
,
O^{Signcrypt}
and
O^{Designcrypt}
.
A_{GDL}
answers
A_{I}
’s queries to
H
_{1}
,
H
_{2}
,
H
_{3}
,
O^{RequestPrivateKey}
,
O^{RequestCertificate}
and
O^{Signcrypt}
in the same way as the proof of Lemma 1 and handles other queries as follows:
O^{CreateUserI}
queries
:
A_{GDL}
maintains a list UserList of tuples 〈
id_{i}
,
SK_{i}
,
PK_{i}
,
Cert_{i}
〉. On receiving such a query on
id_{i}
,
A_{GDL}
performs as follows: (1) If UserList contains a tuple 〈
id_{i}
,
SK_{i}
,
PK_{i}
,
Cert_{i}
〉, output
PK_{i}
to
A_{I}
. (2) Otherwise, if
id_{i}
is the
θ
th distinct identity submitted to this oracle, randomly choose
x_{θ}
∈
Z
^{*}
_{p}
, set
SK_{θ}
=
x_{θ}
and
PK_{θ}
= (
g^{xθ}
,
g^{a}
), insert 〈
id_{θ}
,
SK_{θ}
,
PK_{θ}
, ⊥〉 into UserList and output
PK_{θ}
to
A_{I}
. (3) Otherwise, randomly choose
x_{i}
,
y_{i}
∈
Z
^{*}
_{p}
, set
SK_{i}
=
x_{i}
and
PK_{i}
= (
PK_{i}
^{(1)}
,
PK_{i}
^{(2)}
) = (
g^{xi}
,
g^{yi}
); run the simulation algorithm for the random oracle
H
_{1}
to get a hash value
h
_{1}
=
H
_{1}
(
id_{i}
,
PK_{i}
^{(1)}
,
PK_{i}
^{(2)}
) and compute
Cert_{i}
=
y_{i}
+
αh
_{1}
; insert 〈
id_{i}
,
SK_{i}
,
PK_{i}
,
Cert_{i}
〉 into UserList and output
PK_{i}
to
A_{I}
.
O^{Designcrypt}
queries
: On receiving such a query on (
σ
= (
h
,
u
,
c
),
id_{S}
,
id_{R}
),
A_{GDL}
does the following: (1) If
id_{R}
=
id_{θ}
,
A_{GDL}
first runs the simulation algorithm for the random oracle
H
_{1}
to get
h
_{1}
=
H
_{1}
(
id_{R}
,
PK_{R}
^{(1)}
,
PK_{R}
^{(2)}
) and
h'
_{1}
=
H
_{1}
(
id_{S}
,
PK_{S}
^{(1)}
,
PK_{S}
^{(2)}
), and then checks if there exist a tuple 〈
m
,
R
,
id_{S}
,
PK_{S}
^{(1)}
,
PK_{S}
^{(2)}
,
h
〉 in H
_{2}
List and a tuple 〈
v
,
h
_{3}
〉 in H
_{3}
List such that
R
= (
PK_{S}
^{(1)}
⋅
PK_{S}
^{(2)}
⋅
g
_{1}
^{h'1}
⋅
g^{h}
)
^{u}
,
m
=
c
⊕
h
_{3}
and
O^{rDDH}
(
g
,
g^{a}
,
R
,
v
⋅
R
^{−SKR−αh1}
) = 1. If such two tuples exist,
A_{GDL}
returns
m
to
A_{I}
as the designcryption of
σ
; otherwise, it rejects
σ
. Note that a valid ciphertext is rejected with probability smaller than
q_{dsc}
/2
^{k}
across the whole game. (2) Otherwise,
A_{GDL}
can answer the query according to the specification of the algorithm
Signcrypt
since it knows the sender
id_{R}
’s private key and certificate.
Finally,
A_{I}
outputs a valid ciphertext
σ
^{*}
= (
h
^{*}
,
u
^{*}
,
c
^{*}
) from
id
^{*}
_{S}
to
id
^{*}
_{R}
. If
id
^{*}
_{S}
≠
id_{θ}
, then
A_{GDL}
aborts. Otherwise, having the knowledge of
id
^{*}
_{R}
’s private key and certificate,
A_{GDL}
can designcrypt
σ
^{*}
to obtain
m
^{*}
and
R
^{*}
. Then,
A_{GDL}
uses the oracle replay technique
[28]
to generate one more valid ciphertext
σ
^{*′}
= (
h
^{*′}
,
u
^{*′}
,
c
^{*′}
) from
σ
^{*}
such that
h
^{*}
≠
h
^{*′}
and
u
^{*}
≠
u
^{*′}
. Since
σ
^{*}
and
σ
^{*′}
are both valid ciphertexts for the same message and randomness, we obtain the following relations:
where
h
_{1}
=
H
_{1}
(
id_{θ}
,
PK_{θ}
^{(1)}
,
PK_{θ}
^{(2)}
). Then, we have
Therefore,
A_{GDL}
can compute
as the solution to the given GDL problem.
From the Lemma 4 in
[28]
, if
A_{I}
produces a forgery with probability
ε
≥ 10(
q_{sc}
+ 1)(
q_{sc}
+
q
_{2}
)/2
^{k}
, then
A_{GDL}
can use the oracle replay technique to generate one more valid ciphertext with advantage
ε'
≥ 1/9. Since
A_{GDL}
can resolve the given GDL problem after it generates one more valid ciphertext from the valid ciphertext forged by
A_{I}
, we get that the advantage of
A_{GDL}
in solving the GDL problem is
ε'
≥ 1/9.
Also from the Lemma 4 in
[28]
, thetime complexity of
A_{GDL}
in solving the given GDL problem is bound by
τ'
≤ 23
q_{cu}q
_{2}
[
τ
+ (
q
_{1}
+
q
_{2}
+
q
_{3}
+
q_{cer}
+
q_{pri}
)
O
(1) +
q_{cu}
(2
τ_{exp}
+
O
(1)) +
q_{sc}
(4
τ_{exp}
+
O
(1)) +
q_{dsc}
(4
τ_{exp}
+
τ_{rDDH}
+
O
(1))][
ε
(1 
q_{dsc}
/2
^{k}
)(1 
q_{sc}
(
q
_{2}
+
q
_{3}
+ 2
q_{sc}
)/2
^{k}
)]
^{1}
, where
τ_{exp}
and
τ_{rDDH}
respectively denote thetime for computing an exponentiation in
G
and the one for a call to the restricted DDH oracle.
Lemma 4.
Suppose that
H
_{1}
~
H
_{3}
are random oracles and
A_{II}
is a TypeII adversary against the EUFCBSCCMA security of the proposed scheme that makes at most
q_{cu}
queries to the oracle
O^{CreateUserII}
,
q_{pri}
queries to the oracle
O^{RequestPrivateKey}
,
q_{sc}
queries to the oracle
O^{Signcrypt}
,
q_{dsc}
queries to the oracle
O^{Designcrypt}
and
q_{i}
queries to the random oracles
H_{i}
(1 ≤
i
≤ 3). Assume also that
A_{II}
produces a forgery with probability
ε
≥ 10(
q_{sc}
+ 1)(
q_{sc}
+
q
_{2}
)/2
^{k}
within atime
τ
. Then there exists an algorithm
A_{GDL}
to solve the GDL problem in the group
G
with advantage
ε'
≥ 1/9 and running time
τ'
≤ 23
q_{cu}q
_{2}
[
τ
+ (
q
_{1}
+
q
_{2}
+
q
_{3}
+
q_{pri}
)
O
(1) +
q_{cu}
(2
τ_{exp}
+
O
(1)) +
q_{sc}
(4
τ_{exp}
+
O
(1)) +
q_{dsc}
(4
τ_{exp}
+
τ_{rDDH}
+
O
(1))][
ε
(1 
q_{dsc}
/2
^{k}
)(1 
q_{sc}
(
q
_{2}
+
q
_{3}
+ 2
q_{sc}
)/2
^{k}
)]
^{1}
, where
τ_{exp}
and
τ_{rDDH}
respectively denote thetime for computing an exponentiation in
G
and the one for a call to the restricted DDH oracle.
Proof. Assume that
A_{GDL}
is given a random GDL problem instance (G,
p
,
g
,
g^{a}
,
O^{rDDH}
). Its goal is to compute
a
by interacting with
A_{II}
as follows:
At the beginning of the game,
A_{GDL}
first randomly chooses
α
∈
Z
^{*}
_{p}
and an index θ ∈ [1,
q_{cu}
]. It then computes
g
_{1}
=
g^{a}
and starts EUFCBSCCMA GameII by supplying
A_{II}
with the master key
msk
=
α
and the public parameters
params
= {
G
,
p
,
g
,
g
_{1}
,
l_{m}
,
H
_{1}
,
H
_{2}
,
H
_{3}
}, where
H
_{1}
~
H
_{3}
are random oracles controlled by
A_{GDL}
.
During the queryanswer phase,
A_{II}
can adaptively make queries to the oracles
H
_{1}
,
H
_{2}
,
H
_{3}
,
O^{CreateUserII}
,
O^{RequestPrivateKey}
,
O^{Signcrypt}
and
O^{Designcrypt}
.
A_{GDL}
answers
A_{II}
’s queries to
H
_{1}
,
H
_{2}
,
H
_{3}
,
O^{CreateUserII}
,
O^{RequestPrivateKey}
and
O^{Signcrypt}
in the same way as the proof of Lemma 2 and and handles other queries as follows:
O^{Designcrypt}
queries
: On receiving such a query on (
σ
= (
h
,
s
,
c
),
id_{S}
,
id_{R}
),
A_{GDL}
does the following: (1) If
id_{R}
=
id_{θ}
,
A_{GDL}
first runs the simulation algorithm for the random oracle
H
_{1}
to get
h
_{1}
=
H
_{1}
(
id_{R}
,
PK_{R}
^{(1)}
,
PK_{R}
^{(2)}
) and
h'
_{1}
=
H
_{1}
(
id_{S}
,
PK_{S}
^{(1)}
,
PK_{S}
^{(2)}
), and then checks if there exist a tuple 〈
m
,
R
,
id_{S}
,
PK_{S}
^{(1)}
,
PK_{S}
^{(2)}
,
h
〉 in H
_{2}
List and a tuple 〈
v
,
h
_{3}
〉 in H
_{3}
List such that
R
=
PK_{S}
^{(1)}
⋅
PK_{S}
^{(2)}
⋅
g
_{1}
h'
_{1}
⋅
g^{h}
)
^{u}
,
m
=
c
⊕
h
_{3}
and
O^{rDDH}
(
g
,
g^{a}
,
R
,
v
⋅
R^{−CertR}
) = 1. If such two tuples exist,
A_{GDL}
returns
m
to
A_{II}
as the designcryption of
σ
; otherwise, it rejects
σ
. Note that a valid ciphertext is rejected with probability smaller than
q_{dsc}
/2
^{k}
across the whole game. (2) Otherwise,
A_{GDL}
designcrypts
σ
in the normal way since it knows the receiver
id_{R}
’s private key and certificate.
Finally,
A_{II}
outputs a valid ciphertext
σ
^{*}
= (
h
^{*}
,
u
^{*}
,
c
^{*}
) from
id
^{*}
_{S}
to
id
^{*}
_{R}
. If
id
^{*}
_{S}
≠
id_{θ}
, then
A_{GDL}
aborts. Otherwise, having the knowledge of the user
id
^{*}
_{R}
’s private key and certificate,
A_{GDL}
can designcrypt
σ
^{*}
to obtain
m
^{*}
and
R
^{*}
. Then,
A_{GDL}
uses the oracle replay technique
[28]
to generate one more valid ciphertext
σ
^{*′}
= (
h
^{*′}
,
u
^{*′}
,
c
^{*′}
) from
σ
^{*}
such that
h
^{*}
≠
h
^{*′}
and
u
^{*}
≠
u
^{*′}
. Since
σ
^{*}
and
σ
^{*′}
are both valid ciphertexts for the same message and randomness, we obtain the following relations:
where
h
_{1}
=
H
_{1}
(
id_{θ}
,
PK_{θ}
^{(1)}
,
PK_{θ}
^{(2)}
). Then, we have
Therefore,
A_{GDL}
can compute
as the solution to the given GDL problem.
From the Lemma 4 in
[28]
, if
A_{II}
produces a forgery with probability
ε
≥ 10(
q_{sc}
+ 1)(
q_{sc}
+
q
_{2}
)/2
^{k}
, then
A_{GDL}
can use the oracle replay technique to generate one more valid ciphertext with advantage
ε'
≥ 1/9. Since
A_{GDL}
can resolve the given GDL problem after it generates one more valid ciphertext from the valid ciphertext forged by
A_{II}
, we get that the advantage of
A_{GDL}
in solving the GDL problem is
ε'
≥ 1/9.
Also from the Lemma 4 in
[28]
, thetime complexity of
A_{GDL}
in solving the given GDL problem is bound by
τ'
≤ 23
q_{cu}q
_{2}
[
τ
+ (
q
_{1}
+
q
_{2}
+
q
_{3}
+
q_{pri}
)
O
(1) +
q_{cu}
(2
τ_{exp}
+
O
(1)) +
q_{sc}
(4
τ_{exp}
+
O
(1)) +
q_{dsc}
(4
τ_{exp}
+
τ_{rDDH}
+
O
(1))][
ε
(1 
q_{dsc}
/2
^{k}
)(1 
q_{sc}
(
q
_{2}
+
q
_{3}
+ 2
q_{sc}
)/2
^{k}
)]
^{1}
, where
τ_{exp}
and
τ_{rDDH}
respectively denote thetime for computing an exponentiation in
G
and the one for a call to the restricted DDH oracle.
 5.3 Performance Comparison
We next make a comparison of our proposed scheme and the previous certificatebased signcryption schemes.
The details of the compared schemes are listed in
Table 1
, where we compare the schemes on computation complexity of signcryption and designcryption. We mainly consider four atomic operations: pairing, exponentiation in
G_{T}
, exponentiation in
G
and hash. Here
G
is an additive or multiplicative cyclic group,
G_{T}
is the target group in the setting of bilinear pairing,
i.e.
, the bilinear pairing is
e
:
G
×
G
→
G_{T}
. For simplicity, we denote these operations by
Pa
,
Exp_{GT}
,
Exp_{G}
and
Ha
respectively.
Comparison of the certificatebased signcryption schemes
Comparison of the certificatebased signcryption schemes
From
Table 1
, we can see that both the signcryption and designcryption algorithms in our scheme need computing four exponentiations and three hashes. In any other existing paringbased certificatebased signcryption scheme, the signcryption algorithm requires computing at least one bilinear pairing, five exponentiations and three hashes while the designcryption algorithm requires computing at least three pairings, two exponentiations and three hashes. Actually, the computation performance of our scheme can be further optimized when
g
_{1}
^{H1(idU,PKU(1), PKU(2))}
can be precomputed. Such a precomputation enables us to additionally reduce one exponentiation and one hash computation in both the signcryption algorithm and the designcryption algorithm.
To give a much clearer comparison and also show that our scheme is more suitable for the computationlimited devices, we make a concretetime analysis of the compared schemes. The results are given in
Table 2
. Here, we estimate the computationtime of the compared schemes on a standard MICA2 sensor node. According to the experiment results in
[29
,
30]
, for 80bit security, one pairing computation takes 1.90s and one exponentiation in the group
G
takes 0.32s on a MICA2 sensor node. However, the exponentiation in the target group
G_{T}
takes moretime than the exponentiation in the group
G
because of the fact that it is computed in a field much bigger than the field in which
G
is defined. In usual implementations of pairing, one exponentiation in
G_{T}
costs about equal to four exponentiations in
G
[31]
. Considering that the overheads of hash operations and arithmetic operations in
Z
^{*}
_{p}
are very small compared to the expensive pairing and exponentiation operations, we ignore these costs in thetime analysis.
Computationtime of the compared schemes on MICA2 sensors
Computationtime of the compared schemes on MICA2 sensors
From the comparison in
Table 2
, we can conclude that our scheme enjoys obvious advantage in the computationtime and is more suitable to be employed in the computationlimited environments.
6. Conclusion
In this paper, we presented a new certificatebased signcryption scheme and proved its security under the gap DiffieHellman assumption and the gap discrete logarithm assumption. As our proposed scheme does not require any costly pairing operation, it is more efficient than the previous certificatebased signcryption schemes which have to be based on the bilinear pairings. However, a limitation of our scheme is that its security can only be achieved in the random oracle model. So, it would be interesting to construct paringfree certificatebased signcryption in the standard model.
BIO
Yang Lu received the Ph.D. degree from PLA University of Science and Technology in 2009. He has been working in HoHai University from 2003. Currently, he is an Assistant Professor in College of Computer and Information Engineering. He has published more than 30 papers in international conferences and journals. His research interest includes information security and cryptography.
Jiguo Li received the Ph.D. degree from Harbin Institute of Technology in 2003. He has been working in HoHai University from 2003. Currently, he is a Professor in College of Computer and Information Engineering. His major research interests include information security and cryptography, network security, wireless security and trusted computing etc. He has published more than 70 scientific papers and two books. He has served as a PC member of several international conferences and the reviewer of some international journals and conferences.
Shamir A.
1984
“Identitybased cryptosystems and signature schemes”
in Proc. of Advances in Cryptology  Crypto 1984
August 1922
Article (CrossRef Link).
47 
53
AlRiyami S. S.
,
Paterson K. G.
2003
“Certificateless public key cryptography”
in Proc. of Advances in Cryptology  Asiacrypt 2003
November 30December 4
Article (CrossRef Link).
452 
473
Gentry C.
2003
“Certificatebased encryption and the certificate revocation problem”
in Proc. of Advances in Cryptology  Eurocrypt 2003
May 48
Article (CrossRef Link).
272 
293
Sur C.
,
Jung C. D.
,
Rhee K. H.
2007
“Multireceiver certificatebased encryption and application to public key broadcast encryption”
in Proc. of 2007 ECSIS Symposium on Bioinspired, Learning, and Intelligent Systems for Security
August 910
Article (CrossRef Link).
35 
40
Galindo D.
,
Morillo P.
,
Ràfols C.
2008
“Improved certificatebased encryption in the standard model”
Journal of Systems and Software
Article (CrossRef Link).
81
(7)
1218 
1226
DOI : 10.1016/j.jss.2007.09.009
Liu J. K.
,
Zhou J.
2008
“Efficient certificatebased encryption in the standard model”
in Proc. of 6th Int. Conf. on Security and Cryptography for Networks
September 1012
Article (CrossRef Link).
144 
155
Lu Y.
,
Li J.
,
Xiao J.
2009
“Constructing efficient certificatebased encryption with paring”
Journal of Computers
Article (CrossRef Link).
4
(1)
19 
26
DOI : 10.4304/jcp.4.1.1926
Lu Y.
,
Li J.
2013
“Constructing pairingfree certificatebased encryption”
International Journal of Innovative Computing, Information and Control
Article (CrossRef Link).
9
(11)
4509 
4518
Yao J.
,
Li J.
,
Zhang Y.
2013
“Certificatebased encryption scheme without pairing”
KSII Transactions on Internet and Information Systems
Article (CrossRef Link).
7
(6)
1480 
1491
DOI : 10.3837/tiis.2013.06.008
Kang B. G.
,
Park J. H.
,
Hahn S. G.
2004
“A certificatebased signature scheme”
in Proc. of Topics in Cryptology  CTRSA 2004
February 2327
Article (CrossRef Link).
99 
111
Au M. H.
,
Liu J. K.
,
Susilo W.
,
Yuen T. H.
2007
“Certificate based (linkable) ring signature”
in Proc. of 3rd Information Security Practice and Experience Conference
May 79
Article (CrossRef Link).
79 
92
Li J.
,
Huang X.
,
Mu Y.
,
Susilo W.
,
Wu Q.
2007
“Certificatebased signature: security model and efficient construction”
in Proc. of 4th European PKI Workshop Theory and Practice
June 2830
Article (CrossRef Link).
110 
125
Li J.
,
Huang X.
,
Mu Y.
,
Susilo W.
,
Wu Q.
2010
“Constructions of certificatebased signature secure against key replacement attacks”
Journal of Computer Security
Article (CrossRef Link).
18
(3)
421 
449
Liu J. K.
,
Baek J.
,
Susilo W.
,
Zhou J.
2008
“Certificate based signature schemes without pairings or random oracles”
in Proc. of 11th Information Security conference
September 1518
Article (CrossRef Link).
285 
297
Wu W.
,
Mu Y.
,
Susilo W.
,
Huang X.
2009
“Certificatebased signatures, revisited”
Journal of Universal Computer Science
Article (CrossRef Link).
15
(8)
1659 
1684
Zheng Y.
1997
“Digital signcryption or how to achieve cost (signature & encryption) << cost (signature) + cost (encryption)”
in Proc. of Advances in Cryptology  Crypto 1997
August 1721
Article (CrossRef Link).
165 
179
Li F.
,
Xin X.
,
Hu Y.
2008
“Efficient certificatebased signcryption scheme from bilinear pairings”
International Journal of Computers and Applications
Article (CrossRef Link).
30
(2)
129 
133
Chen L.
,
MaloneLee J.
2005
“Improved identitybased signcryption”
in Proc. of 8th Int. Workshop on Theory and Practice in Public Key Cryptography
January 2326
Article (CrossRef Link).
362 
379
Luo M.
,
Wen Y.
,
Zhao H.
2008
“A certificatebased signcryption scheme”
in Proc. of 2008 Int. Conf. on Computer Science and Information Technology
August 29  September 2
Article (CrossRef Link).
17 
23
Bellare M.
,
Rogaway P.
1993
“Random oracles are practical: a paradigm for designing efficient protocols”
in Proc. of 1st ACM Conf. on Communications and Computer Security
November 35
Article (CrossRef Link).
62 
73
Li J.
,
Huang X.
,
Hon M.
,
Zhang Y.
2012
“Certificatebased signcryption with enhanced security features”
Computers & Mathematics with Applications
Article (CrossRef Link).
64
(6)
1587 
1601
DOI : 10.1016/j.camwa.2012.01.006
Schnorr C. P.
1989
“Efficient identifications and signatures for smart cards”
in Proc. of Advances in Cryptology  Crypto 1989
August 2024
Article (CrossRef Link).
239 
252
Schnorr C. P.
1991
“Efficient signature generation by smart cards”
Journal of Cryptology
Article (CrossRef Link).
4
(3)
161 
174
DOI : 10.1007/BF00196725
Fujisaki E.
,
Okamoto T.
1999
“How to enhance the security of publickey encryption at minimum cost”
in Proc. of 2nd Int. Workshop on Theory and Practice in Public Key Cryptography
March 13
Article (CrossRef Link).
53 
68
Okamoto T.
,
Pointcheval D.
2001
“The gapproblems: a new class of problems for the security of cryptographic schemes”
in Proc. of 4th Int. Workshop on Theory and Practice in Public Key Cryptography
February 1315
Article (CrossRef Link).
104 
118
Baek J.
,
Steinfeld R.
,
Zheng Y.
2007
“Formal proofs for the security of signcryption”
Journal of Cryptology
Article (CrossRef Link).
20
(2)
203 
235
DOI : 10.1007/s0014500702110
Pointcheval D.
,
Stern J.
2000
“Security arguments for digital signatures and blind signatures”
Journal of Cryptology
Article (CrossRef Link).
13
(3)
361 
396
DOI : 10.1007/s001450010003
Oliveira L. B.
,
Aranha D. F.
,
Gouvêa C. P. L.
,
Scott M.
,
Câmara D. F.
,
López J.
,
Dahab R.
2011
“TinyPBC: Pairings for authenticated identitybased noninteractive key distribution in sensor networks”
Computer Communications
Article (CrossRef Link).
34
(3)
485 
493
DOI : 10.1016/j.comcom.2010.05.013
Aranha D. F.
,
Dahab R.
,
López J.
,
Oliveira L. B.
2010
“Efficient implementation of elliptic curve cryptography in wireless sensors”
Advances in Mathematics of Communications
Article (CrossRef Link).
4
(2)
169 
187
DOI : 10.3934/amc.2010.4.169
Chen L.
,
Morrissey P.
,
Smart N. P.
2008
“Pairings in trusted computing”
in Proc. of 2nd International Conference on Pairingbased Cryptography
September 13
Article (CrossRef Link).
1 
17