A certificateless signature scheme without random oracles

. 
Our resulting scheme enjoys the constant-size of all parameters together with an 
efficient computing time. It is therefore the most efficient CLS scheme in the standard model 
to date. We give in Table 1 the detailed comparison among our CLS scheme and most 
relevant other existing CLS schemes secure in the standard model. 
Table 1. Comparison between our scheme and some previous CLS schemes in the standard 
model. nu, nm are the fixed length corresponding to the parameters of the Water’s function. E, 
P and MG denote the exponentiation in a group G, the pairing computation and the 
multiplication in a group G, respectively. VerifySignpkSig ,,, denote the signature size, public 
key size, signing time, verifying time of a SS secure in the standard model, respectively 
 Sig size Public key size Singing time Verifying time 
[10] G3 Gnn mu 5 Gmu M
nn
E 
 3
2
5 
TGG
mu MM
nn
P 2
2
6 
[19] G4 Gnn mu 4 Gmu M
nn
E 
 7
2
9 
TGG
mu MM
nn
P 2
2
6 
[17] G3 Gnn mu 5 Gmu M
nn
E 
 3
2
5 
TGG
mu MEM
nn
P 21
2
3 
[18] G4 Gnu 7 Gu M
n
E 
 4
2
6 
TGG
u MEM
n
P 21
2
1
5 
[7] pkSig 13 pk1 Sign2 Verify3 
Ours G4 G7 GME 26 EMP G 263 
Hong Duc University Journal of Science, E.3, Vol.8, P (41 - 49), 2017 
44 
Paper organization. The next section introduces definition for a CLS scheme. Section 3 
gives some tools that we will need for our main construction. In Sections 4 we give our CLS 
scheme and its security analysis. 
2. Certificateless signature scheme 
We recall in this section the definition for a CLS scheme, based on the work given in 
[8]. A certificateless signature scheme requires three actors: a designated authority acting as a 
Private Key Generator PKG, a signer and a verifier. 
Informally speaking, the main difference between a standard signature scheme and a 
certificateless signature scheme is the way keys are generated. In a CLS scheme, the key 
generation process is divided into four steps which finally permits to compute the user private 
key SKID, computed from both a secret value IDx chosen by the user him/herself and a partial 
private key DID generate by the PKG from a master key and the user's identity. 
More formally, a CLS scheme consists of seven probabilistic algorithms. 
Setup: This algorithm takes as input a security parameter  and returns the system 
parameters param and a master secret key msk. 
Partial-Private-Key-Extract: This algorithm takes as input param, the master key msk and 
a user's identity ID. It returns a partial private key DID devoted to the user with identity ID. 
Set-Secret-Value: This algorithm takes as input the security parameter and a user's 
identity ID and returns the user's secret value IDx 
Set-Public-Key: This algorithm takes as input a user's secret value IDx . It returns the 
user's public key PKID. 
Set-Private-Key: This algorithm takes a user's partial private key DID and public key 
PKID, and his secret value IDx as input. It returns the user's full private key SKID. 
Sign: This algorithm takes param, a message m, and a user's full private key SKID as 
input. It returns a signature  . 
Verify: This algorithm takes param, a message m, a user's identity ID, a public key PKID, 
and a signature  as input. It returns 1 if  is a valid signature of the message m and 0 otherwise. 
Regarding efficiency, the main purpose of a certificateless signature scheme is to give a 
verification phase for which the time complexity does not correspond to the verification of the 
signature (output by Sign) plus the verification that the partial private key is a correct one (that 
is, output by Partial-Private-Key-Extract and derived by the PKG). 
3. Preliminaries 
In this section, we give some useful tools we will need all along the paper. If needed, 
some other details will be given directly in the description of our scheme, when necessary. 
Hong Duc University Journal of Science, E.3, Vol.8, P (41 - 49), 2017 
45 
In the sequel, a standard signature scheme SS is given by the three algorithms (KeyGen, 
Sign, Verify). 
3.1. Bilinear groups 
Let GG
~
, and TG denote three finite multiplicative abelian groups of large prime order 
2 p where  is the security parameter. Let g be a generator of G and g~ be a generator of 
G
~
. We assume that there exists an admissible asymmetric bilinear map TGGGe 
~
: , 
meaning that for all pZba , . 
1. ;~,~, abba ggegge 
2. For Gg 1 and TGG ggeg 1
~,,1~ ~ 
3. gge ~, is efficiently computable. 
In the sequel, the set eggGGGp T ,~,,,~,, is called a bilinear map group system. In 
this paper, we consider in the sequel type 3 pairings where there is no efficiently computable 
homomorphism GG ~:  exist between G and G~ in either direction [5]. 
3.2. Boneh-Boyen signature scheme 
Boneh and Boyen have proposed in [2] short signature schemes (named BB for short), 
secure in the standard model, under the q-SDH assumption [2]. In this paper, we make use of 
the weak version of the BB signature. 
In a nutshell, the BB scheme requires a bilinear map group system 
 eggGGGp T ,~,,,~,, and works as follows (details can be found in [2]). 
KeyGen: The secret key *pZs , the corresponding public key is 
sgw ~~ . 
Sign: On input the secret s , the signature of a message pZm is obtained by 
computing msg /1 . 
Verify: On input a message m and the corresponding signature  , together with the 
public key w , anybody can verify the validity of ~ by checking that: 
 ggegwe m ~,~~,  
3.3. Pointcheval-Sanders signature scheme 
Recently, Pointcheval and Sanders have proposed in [12] a new construction for a 
signature scheme (called PS in the sequel) with additional features. They prove the security of 
their construction in the standard model, under a new assumption they have introduced, called 
PS assumption 1, and given below. 
Hong Duc University Journal of Science, E.3, Vol.8, P (41 - 49), 2017 
46 
In a nutshell, the PS scheme necessitates a bilinear map group system 
 eggGGGp T ,~,,,~,, and works as follows (details can be found in [12]). 
KeyGen: The secret key is a tuple *, pZyx , and the public key is composed of a 
random generator Gh
~~
 and the corresponding tuple YX ~,~ where xhX ~~ and yhY ~~ 
Sign: On input the secret yx, , the signature of a message pZm is obtained by 
selecting a random Gh
$
 and outputs 21, where h 1 and 
 ymxh 2 
Verify: On input a message m and the corresponding signature 21, , together 
with the public key YXh ~,~,~ , anybody can verify the validity of  by checking that: 
 geYXe m
G
~,
~~
,
;1
21
1 1


4. Construction and security analysis 
We are now ready to describe our construction. We first describe a high-level intuition 
of the construction and the security analysis. 
4.1. Intuition and security analysis 
Intuitively, the master secret key s is a BB signing key and our certificateless signature 
corresponds to a PS signature by the user, with a BB signature as a generator, that is IDsgh 
1
. 
The user's partial private key is then a triplet corresponding to a true PS public key, 
using the above h and a secret key yx, which is common to all users. The differentiation 
between users is done by using a secret value ib to randomize the PS secret key, as 
 ., ybx i Such key finally helps the user (using x and y “in blind”, i.e., without knowing 
them) to compute the certificateless signature as a PS signature. More precisely, we use the 
randomization technique of a PS signature, as described in [12]. 
Regarding security, the unforgeability of the Boneh-Boyen's signature scheme ensures 
that the adversary cannot derive the partial private key of the target user. The security of the 
Pointcheval-Sanders' signature scheme then prevents the adversary from forging a valid 
signature of the target user, on a new message. 
Regarding efficiency, the main point is that, using BB and PS signature schemes in the 
above somewhat generic description, we have found that they are totally compatible in our 
certificateless setting. In fact, we can arrange the verification equations to have only one 
single pairing equation to be directly convinced that both the user's whole public key and the 
given signature are valid. 
Hong Duc University Journal of Science, E.3, Vol.8, P (41 - 49), 2017 
47 
We now give the details of our construction. 
4.2. Detailed description 
The construction of our CLS scheme is detailed as follows. 
Setup 1 : The algorithm takes as input the security parameter  , generates a bilinear 
map group system eggGGGp T ,~,,,~,, . Let *
$
,, pZyxs  
The public parameters param are then 
param = yxyxs gYgXgYgXgSgg ,,~~,~~,~~,~, 
and the master secret key is msk = s. 
Partial-Private-Key-Extract: It takes as input param, msk = s, and the identity ID of user 
i. For notational simplicity, we suppose that identity IDi *pZ . It returns a partial private key 
 iii
i
IDsIDs
y
IDs
x
iiiID
gggDDDD
1
,3,2,1 ,,,, 
for user i. 
Set-Secret-Value: It takes as input user's identity iID . It chooses random values 
*
$
pi Zb  and returns iID bx i as user i's secret value. 
Set-Public-Key: It takes as input param, 
2ID
x and returns ibID gPK
~
2
 as the public key 
for user i. 
Set-Private-Key: It takes as input 
ii IDID
Dx , and returns 
ii IDIDi
DxSK , as the full 
private key for user i. 
Sign: It takes as input param, ii SKID , , and a message m. For notational simplicity, we 
suppose that pZm . The algorithm chooses 
*
$
pZr  and computes: 
 riDU ,1 mriD ,2 rbi iD ,3
,i
i
IDs
rmybx
g 
 riDV ,3 iIDs
r
g 
rgW , r
bi
YL
~
 r
ybi
g~ 
It returns LWVU ,,,  as the signature on the message m. 
Verify: It takes as input param, 
iID
PK , IDi, LWVU ,,,  and a message m, and 
computes i
IDgSU ~.
~
' and gYPKXW mIDi
~.
~
..
~
' . 
It then checks if ),(.',,.',.
iID
PKYeWWeLWeUVUe holds. If this is the case, it 
outputs 1. Otherwise, it outputs 0. 
Hong Duc University Journal of Science, E.3, Vol.8, P (41 - 49), 2017 
48 
Completeness. We can easily show that: 
r
yb
rIDsIDs
r
IDs
rymbx
i
iii
i
ggeggggeLWeUVUe ~...~,.,.',.
..
i
ii
ID
byymbxr PKYeWWeggegge ,.',~,.~, 1. 
4.3. Efficiency considerations 
Regarding efficiency, as shown in Table 1, it is obvious that the signature generation 
necessitates one multi exponentiation in G, two additional modular exponentiations in G and 
one modular exponentiation in G
~
. 
The verification phase consists in executing 2 exponentiations and 4 multiplications in 
G
~
 and then check the pairing equation. As this the latter can be written 
iID
PKYeWLWeUVUe ,'/,.',. 
it suffices to compute 3 pairings, one multiplication in G, and one in G
~
 for this step. 
5. Conclusions 
In this paper, we focus on CLS scheme in the standard model, we in fact introduce a 
new and direct approach to construct an efficient CLS scheme in the standard model, while 
the existing approaches either make use of the Waters' technique or use the generic conversion 
technique which both lead to inefficient CLS schemes. 
References 
[1] S. Al-Riyami and K. G. Paterson (2003), Certificateless public key cryptography. In C.-
S. Laih, editor, Advances in Cryptology - ASIACRYPT. 
[2] D. Boneh and X. Boyen (2008), Short signatures without random oracles and the SDH 
assumption in bilinear groups, J. Cryptology, 21(2):149-177. 
[3] S. Chatterjee and P. Sarkar (2005), Trading time for space: Towards an efficient IBE 
scheme with short(er) public parameters in the standard model, ICISC'05 Proceedings 
of the 8th international conference on Information Security and Cryptology. 
[4] K. Y. Choi, J. H. Park, J. Y. Hwang, and D. H. Lee (2007), Efficient certificateless 
signature schemes, 5th International Conference on Applied Cryptography and 
Network Security, ACNS 2007 - Zhuhai, China. 
[5] S. D. Galbraith, K. G. Paterson, and N. P. Smart (2008), Pairings for cryptographers, 
Discrete Applied Mathematics, 156(16):3113-3121. 
[6] S. Goldwasser, S. Micali, and R. L. Rivest (1988), A digital signature scheme secure 
against adaptive chosen-message attacks, SIAM Journal on Computing. 
Hong Duc University Journal of Science, E.3, Vol.8, P (41 - 49), 2017 
49 
[7] B. C. Hu, D. S. Wong, Z. Zhang, and X. Deng (2006), Key replacement attack against 
 a generic construction of certificateless signature, Conference: Information Security 
 and Privacy, 11th Australasian Conference, ACISP 2006, Melbourne, Australia, July 
 3-5, 2006, Proceedings. 
[8] X. Huang, Y. Mu, W. Susilo, D. S. Wong, and W. Wu (2012), Certificateless 
signatures: New schemes and security models, The Computer Journal. 
[9] X. Huang,W. Susilo, Y. Mu, and F. Zhang (2005), On the security of certificateless 
signature schemes from Asiacrypt 2003, in: CANS 05, LNCS 3810, pp.13-25. 
[10] J. Liu, M. Au, and W. Susilo (2007), Self-generated-certificate public key cryptography 
and certificateless signature/encryption scheme in the standardmodel, ASIACCS '07 
Proceedings of the 2nd ACM symposium on Information, computer and 
communications security, pp. 273-283. 
[11] D. Naccache (2005), Secure and practical identity-based encryption, Cryptology ePrint 
Archive, Report 2005/369. 
[12] D. Pointcheval and O. Sanders (2016), Short randomizable signatures, In Topics in 
Cryptology - CT-RSA 2016 -The Cryptographers' Track at the RSA Conference. 
[13] A. Shamir, Identity-based cryptosystems and signature schemes, In G. R. Blakley and 
D. Chaum, editors, Advances in Cryptology - CRYPTO'84, pp.47-53. 
[14] R. Tso, X. Yi, and X. Huang (2008), Efficient and short certificateless signature, In M. 
K. Franklin, L. C. K. Hui, and D. S. Wong, editors, CANS 08, pp.64-79. 
[15] B. R. Waters (2005), Efficient identity-based encryption without random oracles, In R. 
Cramer, editor, Advances in Cryptology - EUROCRYPT 2005. 
[16] Q. Xia, C. Xu, and Y. Yu (2010), Key replacement attack on two certificateless 
signature schemes without random oracles, Key Eng. Mater. 
[17] H. Xiong, Z. Qin, and F. Li (2008), An improved certificateless signature scheme 
secure in the standard model, Fundamenta Informaticae, vol.88, pp.193-206. 
[18] Y. Yu, Y. Mu, G. Wang, Q. Xia, and B. Yang (2012), Improved certificateless 
signature scheme provably secure in the standard model, IET Inf. Secur, vol.6, issue 2, 
June 2012. 
[19] Y. Yuan, D. Li, L. Tian, and H. Zhu (2009), Certificateless signature scheme without 
random oracles. Proc. ISA, LNCS 5576, pp.31-40. 
[20] D. H. Yum and P. J. Lee (2004), Generic construction of certificateless signature. In H. 
Wang, J. Pieprzyk, and V. Varadharajan, editors, ACISP 04, pp.200-211. 
[21] Z. Zhang, D. S. Wong, J. Xu, and D. Feng (2006), Certificateless public-key signature: 
Security model and ecffient construction.ACNS 06, pp.293-308.