(1) Bilinearity: e(aP,bQ)=e(P,Q)
ab
for P; Q 2 G
1
; a; b 2 Z
q
.
(2) Non-degeneracy: There exists P,Q 2 G
1
such that e(P,Q) – 1.
(3) Computability: There exists an efficient algorithm to compute e(P,Q) for any P, Q 2 G
1
.
Computational Diffie–Hellman (CDH) Problem in G
1
: Given a generator P of G
1
, and (aP, bP) for unknown a; b 2 Z
q
;to
compute abP. The CDH assumption is that there is no polynomial-time algorithm that can solve the CDH problem with
non-negligible probability.
2.2. Certificateless proxy signature schemes
A CLPS scheme consists of eight algorithms: Setup, Partial-Private-Key-Extract, Delegate, UserKeyGen, DVerify, PKgen, PSign
and PVerify. The first two algorithms are performed by the KGC, and the rest ones are performed by the users. The description
of each algorithm comes as follows:
Setup: This algorithm accepts a security parameter k and returns a master-key and a list of system parameters params.
Partial-Private-Key-Extract: This algorithm accepts a user’s identity ID and produces the user’s partial private key D
ID
.
UserKeyGen: This algorithm takes as input a user’s identity ID and outputs the user’s secret/public key x
ID
/P
ID
.
Delegate: This algorithm takes as input the original signer’s partial private key D
O
, secret key x
O
, a warrant m
w
and outputs
the delegation
-
=(m
w
,
r
w
).
DVerify: This algorithm takes as input
-
and verifies whether
-
is a valid delegation from the original signer.
PKgen: This is the proxy key generation algorithm that takes as input
-
, the partial private key D
P
and secret key x
P
of the
proxy signer, and outputs a proxy signing key K
P
.
PSign: This is the proxy signing algorithm that takes as input
-
=(m
w
,
r
w
), a proxy signing key K
P
and a message
m 2 {0, 1}
⁄
to generate a proxy signature (m, m
w
,
r
).
PVerify: The proxy signature verification algorithm takes as input the original signer’s identity/public key ID
O
/P
O
, the
proxy signer’s identity/public key ID
P
/P
P
, a proxy signature (m, m
w
,
r
), and outputs true if the proxy signature is valid
or false otherwise.
3. Security definitions of certificateless proxy signature schemes
3.1. Adversaries in certificateless public key cryptography
Two types of adversaries [1] with different capabilities are generally considered in CL-PKC. They are known as Type I
Adversaries and Type II Adversaries.
A Type I Adversary A
I
models an ‘‘outsider’’ adversary, who has the ability to replace the public key of any user with a
value of his choice, but he does not have access to the master-key.
A Type II Adversary A
II
models the KGC who has access to the master-key (which is used to generate a user’s partial private
key) but cannot perform public key replacement.
1
Obviously, a secure CLPS scheme must avoid both types of the adversaries to forge a valid CLPS.
3.2. The model
Boldyreva et al. [3] were the first to introduce a formal security model for proxy signatures. They gave a significant
improvement over previous treatments of proxy signatures in terms of security analysis. Later, Malkin et al. [13] proposed
an extended security model, allowing multi-level proxy signatures. The security model for proxy signatures was further im-
proved in [15], in which they allow the security notion of proxy signature unforgetability under an adaptive chosen message
attack with proxy key exposure. In this paper, integrating the properties of certificateless public key cryptosystems and tra-
ditional proxy signatures, we present the model of certificateless proxy signatures.
Before defining the security model of CLPS schemes, we first discuss the potential attacks on CLPS schemes. Roughly
speaking, a CLPS signature scheme is secure, if the scheme can resist to the following types of attacks:
Type A: A Type I/II Adversary who does not know the full private key of the original signer forges a valid delegation on
behalf of the original signer.
Type B: A Type I/II Adversary who does not know the full private key of the original signer forges a valid proxy signature.
Type C: A Type I/II Adversary who does not know the full private key of the proxy signer forges a valid proxy signature.
1
Note that if A
II
replaces a user’s public key, it is equivalent to a CA in a traditional PKI forgers a user’s certificate. In this way, the trust level of CL-PKC is
similar to the trust level in a traditional PKI.
300 L. Zhang et al. / Information Sciences 184 (2012) 298–309