A certificateless signature scheme without random oracles
Hong Duc University Journal of Science, E.3, Vol.8, P (41 - 49), 2017
A CERTIFICATELESS SIGNATURE SCHEME WITHOUT RANDOM
ORACLES
Trinh Viet Cuong1
Received: 15 March 2017 / Accepted: 7 June 2017 / Published: July 2017
©Hong Duc University (HDU) and Hong Duc University Journal of Science
Abstract: In the context of certificateless public key cryptography, there is no need to use the
certificate to certify the public key, and neither the user nor the authority can derive the full
private key by himself. There have been several efforts to propose a certificateless signature
(CLS) scheme in the standard model, but all of them either make use of the Waters' technique
or of the generic conversion technique which both lead to inefficient schemes. In this paper,
we introduce a new and direct approach to construct a CLS scheme, secured in the standard
model, with constant-size of all parameters and having efficient computing time. Our scheme
is therefore very efficient when comparing to existing CLS schemes in the standard model.
Keywords: Certificateless, signature, standard model, strong adversary.
1. Introduction
The era of modern cryptography has started with the introduction of public key
cryptography (PKC). In the context of PKC, each user possesses a private key (e.g., to
digitally sign a message) and a corresponding public key (e.g., to verify the obtained
signature). To verify whether a public key belongs to the correct identified user, the public
key needs to be associated to a certificate provided by a trusted Certificate Authority (CA),
introducing the notion of Public Key Infrastructure (PKI). During the life-cycle of e.g., a
signature scheme, the PKI is therefore in charge of providing, maintaining and revoking a
large amount of certificates, which requires using a lot of resources when deployed in the real
world. To deal with this drawback, Shamir [13] has introduced the concept of identity-based
cryptography for which the public key of a user is exactly his/her identity, such as his/her
phone number or email address. The corresponding private key is next generated by some
private key generator (PKG), from a master secret key and the identity of the requesting user.
However, identity-based cryptography naturally suffers an important disadvantage (named
key escrow problem): the PKG knows the private key of all users. One basic solution is to
distribute the key of the PKG into several entities. But first, such distribution is not
compatible with all identity-based schemes, or leads to non-efficient solutions. And second,
the whole infrastructure may become too complex for a practical deployment.
Trinh Viet Cuong
Faculty of Information and Communication Technologies, Hong Duc University
41
Hong Duc University Journal of Science, E.3, Vol.8, P (41 - 49), 2017
Certificateless Cryptography. To eliminate this new problem, Al-Riyami and Paterson
have introduced in [1] the notion certificateless cryptography. There is still no need for a
certificate and, this time, the PKG has no way to obtain the user private key. In fact, the key is
computed by both the PKG and the user such that only the latter obtains the result. The part
which is still provided by the PKG is computed from a master secret key and the user's identity.
We now focus on the case of certificateless signature (CLS) schemes and give some
words about related work before explaining our contribution on this topic.
1.1. Related work on certificateless signature schemes
To date, there have been numerous efforts to propose CLS schemes in both the random
oracle (using hash function in the construction and then model it as random oracle in the
security proof) [1], [9], [21], [4], [14], [16], [8] and the standard models (not model hash
function as random oracle in the security proof) [20], [7], [10], [17], [19], [18]. Al-Riyami and
Paterson [1] have proposed the first CLS scheme, but Huang et al. [9] have then pointed out
that their work is insecure.
Regarding constructions secure on the random oracle model, Zhang et al. [21], Choi et
al. [4], and Tso et al. [14] have proposed three efficient CLS schemes, where all parameters
are of constant-size. In [8], Huang et al. go one step further by revisiting the security model
and proposing two efficient constructions in the random oracle model.
We now focus on the constructions that are secure in the standard model. In this case,
there are currently two types of constructions in the literature.
Using Waters' hash function. In [15], Waters has proposed a new hash function
technique that can be used to map an identity (of arbitrary length) to a key (of fixed bit length)
in a CLS scheme. The main problem of such technique is that it leads to relatively large public
parameters and heavy computing time. More precisely, both the space and time complexities
are a function of the size of the expected fixed bit length. One possibility is then to apply the
Naccache's [11] or Chatterjee-Sarkar's [3] techniques to reduce this fixed length, but the price
to pay is either a security loss or a less efficient scheme.
The first concrete construction using Waters' hash function has been given by Liu et al
[10]. Three other schemes can now be found in the literature [17], [19], [18].
Yum-Lee generic transformation. In [20], Yum and Lee have introduced a generic
construction for certificateless signature schemes (applied in both the random oracle and the
standard models). The first step of this construction consists in designing an identity-based
signature (IBS) scheme and then combining it with a standard signature (SS). The resulting
efficiency for the CLS scheme is however approximately worse than the one of the chosen
IBS plus the one of the chosen SS. Moreover, a way to construct an IBS scheme is to apply
the folklore conversion technique which either uses two SS schemes or a 2-level Hierarchical
Identity-Based Encryption (but we then fall into the above case of using Waters' technique).
Again, the resulting efficiency is approximately three times worse than the efficiency of the
underlying SS scheme. It is also worth to remark that Hu et al. [7] have pointed out that Yum
42
Hong Duc University Journal of Science, E.3, Vol.8, P (41 - 49), 2017
and Lee's technique is insecure against a Type I forger. They have next given a modification
but at the price of a loss in terms of efficiency.
To the best of our knowledge, it then remains an open problem to design a truly
efficient CLS scheme secure in the standard model. In this paper, we propose such
construction by providing a new technique.
1.2. Our contribution and organization of the paper
Our construction is based on the stacking of the Boneh-Boyen BB standard signature
[2] in the recent Pointcheval-Sanders PS one [12], both secure in the standard model. More
precisely, the generator used in the PS signature corresponds to a BB signature including the
master secret key and user's identity. Adding one element in the signature, we obtain a
unique pairing equation to verify both the validity of our CLS and the one of the related
public key, instead of two if basically applied together, or if other standard signature
schemes are used.
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. Sig , pk , Sign,Verify 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
n n
nu nm
u
m
3G
nu nm 5
G
G
G
5E
9E
5E
3 M
[10]
[19]
[17]
[18]
6P
6P
MG 2MG
G
G
G
T
2
2
n n
nu nm
u
m
4G
3G
4G
nu nm 4
7 M
MG 2MG
T
2
2
n n
nu nm
u
m
nu nm 5
3 M
3P
5P
MG 1E 2MG
T
2
2
n
2
nu 1
2
u
nu 7
G
6E
4 M
MG 1E 2MG
G
T
2Sign
6E 2MG
3Verify
3Sig 1 pk
4G
1 pk
7G
[7]
3P 6MG 2E
Ours
43
Hong Duc University Journal of Science, E.3, Vol.8, P (41 - 49), 2017
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
x
ID 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
parameters param and a master secret key msk.
and returns the system
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
identity ID and returns the user's secret value xID
and a user's
Set-Public-Key: This algorithm takes as input a user's secret value
user's public key PKID.
x
ID . It returns the
Set-Private-Key: This algorithm takes a user's partial private key DID and public key
PKID, and his secret value xID 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.
44
Hong Duc University Journal of Science, E.3, Vol.8, P (41 - 49), 2017
In the sequel, a standard signature scheme SS is given by the three algorithms (KeyGen,
Sign, Verify).
3.1. Bilinear groups
~
Let
and T denote three finite multiplicative abelian groups of large prime order
G
G,G
~
p 2 where
is the security parameter. Let g be a generator of G and be a generator of
g
~
~
e :G G GT
G
. We assume that there exists an admissible asymmetric bilinear map
,
a,bZ p
meaning that for all
.
ab
a
b
~
~
e
g , g
e
g, g
;
1.
~
~
~
g 1G ,e
g, g 1G
2. For
G and
g 1
T
~
3.
e
g, g
is efficiently computable.
~
~
p,G,G,GT , g, g,e
In the sequel, the set
is called a bilinear map group system. In
this paper, we consider in the sequel type 3 pairings where there is no efficiently computable
~
~
:G G
G
G
in either direction [5].
homomorphism
exist between
and
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
p,G,G,GT , g, g,e
and works as follows (details can be found in [2]).
KeyGen: The secret key s Z *p , the corresponding public key is w g
.
s
~
~
s
m Z p
Sign: On input the secret , the signature of a message
is obtained by
computing g1/
.
sm
m
Verify: On input a message
and the corresponding signature , together with the
~
w
public key , anybody can verify the validity of
by checking that:
~
m
~~
e
, wg
e
g, g
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.
45
Hong Duc University Journal of Science, E.3, Vol.8, P (41 - 49), 2017
In a nutshell, the PS scheme necessitates a bilinear map group system
~
~
p,G,G,GT , g, g,e
and works as follows (details can be found in [12]).
x, y
Z *
KeyGen: The secret key is a tuple
p , and the public key is composed of a
~ ~
~
~
~
~
~
~
where X h x and Y h y
m Z p
is obtained by
X ,Y
random generator h G and the corresponding tuple
x, y
Sign: On input the secret
, the signature of a message
$
x ym
selecting a random h G and outputs
1,2
where 1 h and 2 h
1,2
by checking that:
m
Verify: On input a message
and the corresponding signature
, together
~
~ ~
h, X ,Y
with the public key
, anybody can verify the validity of
1 1G ;
~1~
1, XY m
e 2 , g
~
e
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
s
Intuitively, the master secret key is a BB signing key and our certificateless signature
1
h g sID
corresponds to a PS signature by the user, with a BB signature as a generator, that is
.
The user's partial private key is then a triplet corresponding to a true PS public key,
x, y
which is common to all users. The differentiation
using the above
between users is done by using a secret value bi to randomize the PS secret key, as
x b , y
y “in blind”, i.e., without knowing
h
and a secret key
.
Such key finally helps the user (using and
x
i
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.
46
Hong Duc University Journal of Science, E.3, Vol.8, P (41 - 49), 2017
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
$
~
. Let s, x, yZ*p
~
p,G,G,GT , g, g,e
map group system
The public parameters param are then
~
~
~
s
x
y
x
y
~
~
~
~
param =
g, g, S g , X g ,Y g , X g ,Y g
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
. It returns a partial private key
Zp
x
y
1
sIDi
sID
i
i
DID
D1,i , D2,i , D3,i
g
, g sID , g
i
for user i.
Set-Secret-Value: It takes as input user's identity
ID
i . It chooses random values
$
bi Z*p and returns xID bi as user i's secret value.
i
b
~
i
Set-Public-Key: It takes as input param, xID and returns PKID g as the public key
2
2
for user i.
Set-Private-Key: It takes as input xID , DID and returns SKi
xID , DID
as the full
i
i
i
i
private key for user i.
Sign: It takes as input param, IDi ,SKi , and a message m. For notational simplicity, we
$
suppose that m Z p . The algorithm chooses r Z*p and computes:
xb my
r
r
i
r
mr
b r
r
sID
i
i
i
U
D1,i
D2,i
D3,i
V
D3,i
g
,
g sID
bi y
r
bi
~
W gr
,
L Y g
~
r
U,V,W, L
It returns
as the signature on the message m.
U,V,W, L
and a message m, and
Verify: It takes as input param, PKID , IDi,
i
~
~
~
m
~
ID
~
i
U' S.g
W ' X.PK .Y .g
.
computes
It then checks if
outputs 1. Otherwise, it outputs 0.
and
ID
i
e
U.V,U'
.e
W, L
e
W,W' .e(Y, PKID )
holds. If this is the case, it
i
47
Hong Duc University Journal of Science, E.3, Vol.8, P (41 - 49), 2017
Completeness. We can easily show that:
xbi m.y
sIDi
.r
r
bi y
r
IDi
s
r
~
~
i
e
U .V ,U '
.e
W , L
e g
.g sID , g .g
.e g .g
xb m.y1 .e
g , g
e
W ,W ' .e Y , PKID
r
y
b
~
~
i
i
e
g , g
i
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
and then check the pairing equation. As this the latter can be written
~
G
e
U.V,U'
.e
W, L /W'
e
Y, PKID
i
~
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.
48
Hong Duc University Journal of Science, E.3, Vol.8, P (41 - 49), 2017
[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.
49
9 trang
22000
Free
Bạn đang xem tài liệu "A certificateless signature scheme without random oracles", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- a_certificateless_signature_scheme_without_random_oracles.pdf
