# A Forward-Secure Certificate-Based Signature Scheme with Enhanced Security in the Standard Model.

1. IntroductionPublic key cryptography (PKC) is a crucial cryptographic primitive to accomplish information security. In a public key cryptosystem, each user possesses a public/secret key pair. The public key is usually made public. Anyone can use a user's public key to encrypt some messages for the user or verify the validness of the digital signatures issued by the user. The private key is kept secret. Anyone can decrypt the received ciphertexts or produce the digital signatures on some messages by using his/her private key. The security of a public key cryptosystem is dependent on an assumption that all secret keys have gotten perfect protection. Nevertheless, the cryptographic computations are often made on unprotected or easily stolen devices in the reality. The secret key leakage seems inevitable, because the hackers have a wide variety of means to obtain a secret key from an insecure device. Actually, for a hacker, it is easier to hack into a device to grab a user's secret key than to break the computational complexity problem(s) on which a public key cryptosystem lies. Undoubtedly, secret key disclosure has become the gravest threat on the security of PKC, since it means that all security guarantees are missing.

In order to alleviate the damage caused by private key leakage, a feasible solution is to design the public key cryptosystems with forward security. Forward security provides the benefits of frequently evolving the users' private keys without incurring the costs of changing the public keys. More specifically, in a public key cryptosystem with forward security, the system lifespan (e.g., one year) is split into several time slots (e.g., 365 days). Every user in the system initially produces a public/secret key pair. Then, the user makes his/her public key public and stores his/her initial secret key in a digital device where the cryptographic operations are executed actually. With the update of system time, the user's secret key will evolve periodically. At the beginning of each time slot, the device executes a key-evolving algorithm to derive a new secret key for user from the previous one and then deletes the old key permanently. Meanwhile, the user's public key remains unchanged during the whole life cycle of the system. Forward security guarantees that the leakage of a user's secret key in the current time slot does not make a hacker deduce the user's secret key used in any the past time slot. In this way, the forward security mechanism offers an effective cryptographic solution to address the threat of secret key leakage in public key cryptosystems. The concept of forward-secure PKC was introduced by Anderson [1] in ACM CCS 1997. In Crypto 1999, Bellare and Miner [2] formalized the notion of forward security in the setting of digital signature. They also presented a concrete forward-secure digital signature scheme. In Eurocrypt 2003, Canetti et al. [3] proposed a non-interactive forward-secure public key encryption (PKE) scheme. Motivated by the works [2, 3], many forward-secure digital signature schemes [4-10] and forward-secure PKE schemes [11-16] were proposed. However, most of the previous schemes were over either conventional PKC or identity-based cryptography (IBC) [17]. Therefore, they are inevitably subject to either the complicated certificate management or the key escrow issue.

In Eurocrypt 2003, Gentry [18] presented a practical public key cryptographic primitive named certificate-based cryptography (CBC). This new primitive not only greatly simplifies the complicated management of public key certificates in conventional PKC, but also overcomes the key escrow and distribution issues in IBC. In a CBC system, a user needs to produce a pair of public and secret keys independently. Then, he/she submits his/her identity, public key and some other necessary information to a trusted certificate authority (CA) to apply for a public key certificate. Unlike the certificates in conventional PKC systems, a certificate in CBC is merely pushed to its holder and used as a partial decryption/signing key. As discussed in [18], this interesting property of the certificate offers an implicit authentication function so that a user requires both his/her secret key and certificate to execute the decryption/signing tasks, while the others need not be concerned about his/her certificate status. In this way, CBC avoids the issue of third-party queries for the certificate status and predigests the complicated certificate management in conventional PKI-assisted PKC systems. In addition, CBC also addresses the key escrow and distribution problems. In recent years, CBC has attracted much attention in academic circle and a lot of cryptographic schemes [19-36] (includeing many certificate-based encryption (CBE) and certificate-based signature (CBS) schemes) have been proposed.

To address the key leakage issue in CBC, Lu and Li [37] first extended the forward security mechanism into CBC and proposed the notion of forward-secure CBE (FS-CBE). They also provided a generic method to construct the FS-CBE schemes. Subsequently, Li et al. [38] put forward the concept of forward-secure CBS (FS-CBS) along with a FS-CBS scheme without random oracles. In the standard model, Li et al. proved the security of their scheme under the complexity assumptions of the many Diffie-Hellman (Many-DH) and the generalized computational Diffie-Hellman (GCDH) problems. In addition, Li et al. [39] also presented a much more efficient FS-CBS scheme but in the random oracle model.

1.1 Contributions

The goal of this paper is to fix the security vulnerability in the FS-CBS scheme presented by Li et al. in [38]. In Li et al.'s scheme, the CA is supposed to be honest but curious. More specifically, it is assumed that the CA initializes the system in accordance with the system specifications completely. But, once the system has started running, it gets curious and starts eavesdropping on or impersonating users. Nevertheless, such an assumption does not mirror the reality. In practice, a CA possibly is untrusted and malicious. As shown in [27, 35], it is very likely to compromise a target's message privacy or signature unforgeability without the knowledge of the corresponding secret key by injecting some malicious trapdoors into the system. In this paper, we demonstrate that Li et al.'s FS-CBS scheme [38] is insecure under the existential forgery attack from the malicious CA. Our presented attack shows that a CA can easily inject trapdoors into the system and forge valid signatures in the name of any user.

To address this problem, we propose a FS-CBS scheme with enhanced security. The enhanced FS-CBS scheme repairs the security defect in the original scheme and provides immunity against the attacks by the malicious CA. Furthermore, it also significantly optimizes the scheme performance. Our proofs in the standard model demonstrate that it achieves the unforgeability against chosen-message attacks under the complexity assumption of the square computational Diffie-Hellman problem. Compared with Li et al.'s FS-CBS scheme [38], the enhanced scheme enjoys three advantages. First of all, it can offer stronger safety guarantee for the practical application since it is immune to the existential forgery attack by the malicious CA. Second, its security is over a complexity problem that is harder than the ones on which Li et al.'s scheme is based. Finally yet importantly, it has better efficiency, especially on the communication and storage costs.

1.2 Paper organization

In Section 2, some notations and preliminaries are briefly introduced. In Section 3, a malicious CA attack is presented on Li et al.'s FS-CBS scheme. In Section 4, an enhanced FS-CBS scheme is proposed. Finally, a conclusion is given in Section 5.

2. Background Knowledge

2.1 Notations

A list of notations utilized throughout the paper is summarized as below:

--k: A security system parameter;

--p: A k-bit prime number;

--[G.sub.1], [G.sub.2]: Two order p cyclic groups;

--e(v): A bilinear map from [G.sub.1] x [G.sub.1] to [G.sub.2];

--g: A generator of [G.sub.1];

--[Z*.sub.p]: The field of integer numbers modulo p;

--params: A set of public system parameters;

--msk: The CA's master secret key;

--T: The number of the system time slots;

--[[omega].sup.j]: The label of the node associated with the time slot j;

--[mathematical expression not reproducible]: The node secret key of the node [[omega].sup.j];

--d: Depth of the node that is corresponds to a time slot;

--ID: An identity;

--[PK.sub.ID]: The public key of a user with identity ID;

--[Cert.sub.ID]: The certificate of a user with identity ID;

--[SK.sup.j.sub.ID] : The secret key of a user with identity ID that is used in the time slot j;

--[H.sub.u],[H.sub.v], H : Three cryptographic hash functions;

--[n.sub.u], [n.sub.v]: Bit length of a hash value outputted by [H.sub.u] and [H.sub.v] respectively.

2.2 Bilinear map and computational assumption

Assuming that e is a map from [G.sub.1] x [G.sub.1] to [G.sub.2]. The map e is called a bilinear pairing if it satisfies: (1) Bilinearity: [for all]x, y [member of] [Z*.sub.p], e([g.sup.x], [g.sup.y]) = e[(g, g).sup.xy]; (2) Non-degeneracy: e(g, g) [not equal to] 1; (3) Computability: [for all]x, y [member of] [Z*.sub.p], e([g.sup.x], g) can be calculated efficiently.

The enhanced FS-CBS scheme is proven secure under the complexity assumption of the square computational Diffie-Hellman (Squ-CDH) problem [40].

Definition 1. Given the generator g of the group [G.sub.1] and [g.sup.x] [member of] [G.sub.1] for unknown value x [member of] [Z*.sub.p], the Squ-CDH problem over [G.sub.1] is to calculate [mathematical expression not reproducible]. The Squ-CDH assumption states that for any polynomial-time algorithm A, it has negligible advantage [mathematical expression not reproducible] in resolving the Squ-CDH problem, where [mathematical expression not reproducible] is defined to be the probability [mathematical expression not reproducible].

The equivalence between the Squ-CDH problem and the standard computational Diffie-Hellman (CDH) problem has been demonstrated in [40].

2.3 Framework and security definitions of FS-CBS

A FS-CBS scheme comprises six polynomial-time algorithms [38]:

--Setup(k, T): Inputing k and T, this algorithm creates the CA's master secret key msk and a set of public system parameters params.

--UserKeyGen(params, ID): Inputing params and an identity ID, this algorithm creates a public key [PK.sub.ID] and an initial secret key [SK.sup.0.sub.ID] for the user with identity ID.

--CertGen(params, msk, ID, [PK.sub.ID]): Inputing params, msk, ID and [PK.sub.ID], this algorithm create a certificate [Cert.sub.ID] for the user with identity ID.

--KeyEvolve(params, j, [SK.sup.j.sub.ID]): Inputing params, the index of a time slot j [member of] [0, T-1) and a secret key [SK.sup.j.sub.ID] in the time slot j, this algorithm creates a secret key [SK.sup.j+1.sub.ID] for the following time slot j + 1.

--Sign(params, j, m, ID, [Cert.sub.ID], [SK.sup.j.sub.ID]): Inputing params, the index of a time slot j [member of] [0, T-1], a message m to be signed and a signer's identity ID, certificate [Cert.sub.ID] and secret key [SK.sup.j.sub.ID], this algorithm creates a signature <j, [sigma]> for the message m.

--Verify(params, m, <j, [sigma]>, ID, [PK.sub.ID]): Inputing params, m, <j, [sigma]>, the signer's identity ID and public key [PK.sub.ID], this algorithm returns 1 if <j, [sigma]> is a correct signature on the message m signed by a signer with identity ID and public key [PK.sub.ID] in the time slot j or 0 else.

Definition 2. A FS-CBS scheme is correct if for any m and j [member of] [0, T-1], <j, [sigma]> [left arrow] Sign(params, j, m, ID, [Cert.sub.ID], [SK.sup.j.sub.ID]), then 1 [left arrow] Verify'(params, m, <j, [sigma]>, ID, [PK.sub.ID]), where params, [PK.sub.ID], [Cert.sub.ID] and [SK.sup.j.sub.ID] are respectively created in accordance with the algorithm specifications.

As introduced in [38, 39], the adversarial model for FS-CBS should distinguish two different types of adversaries. The Type-I adversary (denoted by [A.sub.I]) acts as an outside attacker who has not been certified by the CA. This adversary is able to execute public key replacement and query any secret key (including the secret key of the target user), but is prohibited from querying the certificate for the target user. The Type-II adversary (denoted by [A.sub.II]) acts as a malicious CA that possesses the master secret key. This adversary is able to issue a certificate for each user using the master secret key, but is prohibited from querying the secret key of the target user and replacing public keys.

To formalize the security model of FS-CBS, we introduce five oracles. These oracles are controlled by a challenger. The adversaries are allowed to adaptively ask some of these oracles.

--[O.sup.UserCreate]: To create a user, the adversary submits an identity ID to the oracle. Input ID, this oracle responds with a public key [PK.sub.ID] if ID has been previously created. Otherwise, the oracle first produces a public key [PK.sub.ID] and an initial secret key [SK.sup.0.sub.ID] and then returns [PK.sub.ID]. Note that other four oracles merely respond to an identity only if it has been created.

--[O.sup.PnvnteKeyCorrupt]: To corrupt the secret key of a user in a time slot j [member of] [0, T-1], the adversary submits an identity ID and the index of a time slot j to the oracle. Once receiving (ID, j), this oracle responds with a private key [SK.sup.j.sub.ID] in the time period j.

--[O.sup.Certify]: To query a user's certificate, the adversary submits an identity ID to the oracle. Once receiving ID, this oracle returns a certificate [Cert.sub.ID].

--[O.sup.PubllicKeyReplace]: To replace a public key, the adversary submits an identity ID and a fake public key [PK.sup.f.sub.ID] to the oracle. Once receiving (ID, [PK.sup.f.sub.ID]), this oracle replaces the current public key corresponding to ID with [PK.sup.f.sub.ID]. Note that the adversary might be required to submit the secret value used to generate [PK.sup.f.sub.ID] so that the oracles [O.sup.PrivateKeyCorrupt] and [O.sup.Sign] can be correctly simulated.

--[O.sup.Sign]: To query the signature on a message issued by a user, the adversary submits an identity ID, the index of a time slot j [member of] [0, T-1] and a message m to the oracle. Once receiving (ID, j, m), this oracle responds with a signature <j, [sigma]>. This oracle executes as essentially same as the strong-signing oracle [O.sup.CB-StrongSign] introduced in [32]. Concretely, if the public key corresponding to ID is the original one created by [O.sup.UserCreate], this oracle answers in a normal way. Otherwise, namely that the user's public key has been replaced by the adversary, it responds with a signature that is calculated by utilizing the secret key and the certificate corresponding to the false public key [PK.sup.f.sub.ID].

A FS-CBS scheme should achieve forward security and existential unforgeability under chosen-message attacks (FS&EUF-CMA). This security notion is defined by a game as described below, in which a game challenger interacts with a Type-I adversary or a Type-II adversary.

--Setup Phase. The challenger simulates the algorithm Setup(k, T) to create (msk, params). It then supplies the adversary A with params if it is a Type-I adversary or both (msk, params) if it is is a Type-II adversary.

--Query-Answer Phase. The adversary A is allowed to send queries to the oracles {[O.sup.UserCreate], [O.sup.PrivateKeyCorrupt], [O.sup.Certify], [O.sup.PublicKeyReplace], [O.sup.Sign]} if it is a Type-I adversary or the oracles {[O.sup.UserCreate], [O.sup.PrivateKeyCorrupt], [O.sup.Sign]} if it is a Type-II adversary.

--Forge Phase. The adversary A submits a forgery (ID*, m*, <j*, [sigma]*>). The adversary A succeeds if the following conditions are met:

* Verify (params, m*, <j*, [sigma]*>, ID*, [PK.sub.ID*]) = 1;

* The adversary A has never submitted (ID*, j*, m*) to the oracle [O.sup.Sign];

* The adversary A has never submitted ID* to the oracle [O.sup.Cortify] if it is a Type-I adversary;

* The adversary A has never submitted ID (*) and any time period j [member of] [0, j (*)] to the oracle [O.sup.PrivateKeyCorrupt] if it is a Type-II adversary.

We define the advantage of the adversary A in winning the game to be the probability that it forges a legitimate signature.

Definition 3. A FS-CBS scheme satisfies the FS&EUF-CMA security if for any polynomial-time algorithm A, it has a negligible advantage to win the above game.

2.4 Tree-based key-evolving mechanism

Like most of the previous forward-secure schemes, the FS-CBS scheme presented by Li et al. [38] exploits a binary tree structure to evolve the users' secret keys. To construct a scheme with T time slots, a key-evolving tree with [log.sub.2](T + 1) - 1 levels should be exploited. In this tree, each node is labeled with a binary number. More specifically, the root node is labeled with an empty symbol [epsilon] and if a node is labeled with a binary number [omega], then its left child node and right child node are labeled with [omega]0 and [omega]1 respectively. In addition, the nodes of the key-evolving tree are associated with the system time slots in a pre-order style. Fig. 1 shows a concrete example of how to associate the nodes of a key-evolving tree with 3 levels with the time slots {0,1,...,14}.

Fig. 2. An example of a user's secret key in each time slot The private key of a user with identity ID in each time period j [SK.sup.0.sub.ID] = {[NSK.sub.[epsilon]]} [SK.sup.1.sub.ID] = {[NSK.sub.0],[NSK.sub.1]} [SK.sup.2.sub.ID] = {[NSK.sub.00],[NSK.sub.01],[NSK.sub.1]} [SK.sup.3.sub.ID] = {[NSK.sub.000],[NSK.sub.001],[NSK.sub.01], [NSK.sub.1]} [SK.sup.4.sub.ID] = {[NSK.sub.001],[NSK.sub.01],[NSK.sub.1]} [SK.sup.5.sub.ID] = {[NSK.sub.01], [NSK.sub.1]} [SK.sup.6.sub.ID] = {[NSK.sub.010], [NSK.sub.011],[NSK.sub.1]} [SK.sup.7.sub.ID] = {[NSK.sub.011], [NSK.sub.1]} [SK.sup.8.sub.ID] = {[NSK.sub.1]} [SK.sup.9.sub.ID] = {[NSK.sub.10], [NSK.sub.11]} [SK.sup.10.sub.ID] = {[NSK.sub.100],[NSK.sub.101],[NSK.sub.11]} [SK.sup.11.sub.ID] = {[NSK.sub.101], [NSK.sub.11]} [SK.sup.10.sub.ID] = {[NSK.sub.11]} [SK.sup.13.sub.ID] = {[NSK.sub.110], [NSK.sub.111]} [SK.sup.14.sub.ID] = {[NSK.sub.111]}

In the key-evolving tree, every node [omega] is endowed with a secret key [NSK.sub.[omega]]. Let [[omega].sup.j] be the node corresponding to the time slot j. A user secret key in the time slot j is composed of the node secret keys of [[omega].sup.j] and all right siblings of those nodes on the path from the root node to [[omega].sup.j]. Fig. 2 gives a concrete example to show how to create the secret key of a user in each time slot by using a 3-level key-evolving tree.

For easy of description, we represent a user secret key as a stack (referred to as NSK-[STACK.sub.ID]). The top of the stack NSK-[STACK.sub.ID] stores the node key of [[omega].sup.j] and the followings are the node keys of all right siblings of those nodes on the route from [[omega].sup.j] to the root.

3. Forgery Attack on Li et al.'s FS-CBS Scheme

In this section, we demonstrate that the FS-CBS scheme presented by Li et al. in [38] cannot resist the existential forgery attack by the malicious CA.

3.1 Description of Li et al.'s FS-CBS scheme

Li et al.'s FS-CBS scheme is described as follows:

--Setup: This algorithm chooses [alpha] [member of] [Z*.sub.p] randomly and sets [g.sub.1] = [g.sup.[alpha]]. It then randomly chooses [mathematical expression not reproducible] and [mathematical expression not reproducible], where [n.sub.u],[n.sub.v] [member of] [Z.sup.+]. Furthermore, it chooses two cryptographic hash functions [mathematical expression not reproducible], [mathematical expression not reproducible]. Finally, it sets params = {l, [G.sub.1], [G.sub.2], p, e, g, [g.sub.1], [g.sub.2], [??], [??], [H.sub.u], [H.sub.v]} and msk = [g.sup.a.sub.2], where l = [log.sub.2](T + 1) - 1.

--UserKeyGen: A user randomly selects x [member of] [Z*.sub.p] as his/her initial secret key [SK.sup.0.sub.ID] and calculates his/her public key [PK.sub.ID] = ([PK.sub.ID,1], [PK.sub.ID,2]) = ([g.sup.x], [g.sup.x.sub.1]). The node key [NSK.sub.[epsilon]] of the root in the key-evolving tree is set to be the user's initial secret key [SK.sup.0.sub.ID].

--CertGen: Let [??] = [H.sub.u] ([PK.sub.ID], ID) and [??][i] be the ith bit of the hash value [??]. Assuming that I [??] {1,2,...,[n.sub.u]} is the set of indices i such that [??][i] = 1. The CA randomly chooses [r.sub.u] [member of] [Z*.sub.p] and calculates [mathematical expression not reproducible].

--KeyUpdate: Let [[omega].sup.j] = [[omega].sub.1] [[omega].sub.2]... [[omega].sub.d] [member of] [{0,1}.sup.d] (1 [less than or equal to] d[less than or equal to] l) be the node corresponding to the time slot j. The node key of d that comprises d + 1 elements (including d elements in [G.sub.1] and one element in [Z*.sub.p]) has the form [mathematical expression not reproducible], where [[omega].sup.j]|i (1 [less than or equal to] i [less than or equal to] d-1) is the i-length prefix of [[omega].sup.j]. Specially, the secret key of the root node is [NSK.sub.[epsilon]] = [SN.sub.[epsilon]]. Inputing the index of a time slot j [member of] [0, T-1) and a secret key [SK.sup.j.sub.ID], this algorithm creates a secret key [SK.sup.j-1.sub.ID] for the time slot j + 1 as follows:

* If [[omega].sup.j] is an internal node, it pops [mathematical expression not reproducible] off the stack NSK-[STACK.sub.ID]. Then, it randomly chooses [[rho].sub.0], [[rho].sub.1] [member of] [Z*.sub.p], computes [mathematical expression not reproducible] and [mathematical expression not reproducible], and sets the secret keys [mathematical expression not reproducible] and [mathematical expression not reproducible] as

[mathematical expression not reproducible] (1)

[mathematical expression not reproducible] (2)

Finally, it pushes [mathematical expression not reproducible] and [mathematical expression not reproducible] onto the stack NSK-[STACK.sub.ID] respectively. Now, the node keys in the stack compose the secret key [SK.sup.j+1.sub.ID].

* Else if [[omega].sup.j] is a leaf node, it pops [mathematical expression not reproducible] off the stack NSK-[STACK.sub.ID]. Now, the node key on the top of NSK-[STACK.sub.ID] is [mathematical expression not reproducible]. Then, the remaining node keys in the stack compose the secret key [STACK.sup.j+1.sub.ID].

--Sign: Let [[omega].sup.j] [member of] [{0,1}.sup.d] (1 [less than or equal to] d [less than or equal to] l) be the node corresponding to the time slot j. Let [??] = [H.sub.v](m) and [??][i] be the i-th bit of the hash value [??]. Define M. [??] {1,2,...,[n.sub.v]} to be the set of indices i such that [??][i] = 1. To sign the message m in the time period j [member of] [0, T-1], the signer ID randomly chooses [r.sub.[pi]], [r.sub.m] [member of] [Z*.sub.p], pops the node secret key [mathematical expression not reproducible] off the stack NSK-[STACK.sub.ID] and computes

[mathematical expression not reproducible] (3)

Then, it sets the signature to be <j, (C, [R.sub.[pi]], [R.sub.m]), [mathematical expression not reproducible].

--Verify: To verify a signature <j, (C, [R.sub.[pi]], [R.sub.m]), [mathematical expression not reproducible] by using the signer ID's public key [PK.sub.ID] = ([PK.sub.ID,1], [PK.sub.ID,2]), a user tests whether the following equality holds:

[mathematical expression not reproducible] (4)

The algorithm returns 1 if the equality holds or 0 else.

3.2 The presented attack

Li et al. 's FS-CBS scheme suffers from the security weankness that a malicious CA is able to fake the signature on any message in the name of any user without knowing the target user's secret key. The malicious CA can do this only by implanting some trapdoors into the system parameters. More specifically, a CA executes such attack in the following way.

--Implanting trapdoors: During initializing the system, the malicious CA randomly picks [n.sub.v] + 1 integers [beta]', [[beta].sub.1],..., [mathematical expression not reproducible] and calculates [mathematical expression not reproducible] as follows:

[mathematical expression not reproducible] (5)

Other public system parameters are created according to the specification of the algorithm Setup in Li et al.'s FS-CBS scheme.

--Faking signatures: To simulate a user with identity ID, the malicious CA first gets a message/signature pair (m, <j, (C, [R.sub.[pi]], [R.sub.m]), [mathematical expression not reproducible]) issued by the user.

After that, it selects [r'.sub.m] [member of] [Z*.sub.p] randomly and creates a new signature <j, (C', [R'.sub.[pi]], [R'.sub.m]), [mathematical expression not reproducible] on a different message m'([not equal to] m)in the following way:

[mathematical expression not reproducible] (6)

where M = {i | [??][i] = 1, [??] = [H.sub.v](m)}, M' = {i | [??]'[i] = 1, [??]' = [H.sub.v](m')} and [??][i] is the ith bit of [??] and [??]'[i] is the ith bit of [??]'.

According to the above scheme description, if <j, (C, [R.sub.[pi]], [R.sub.m]), [mathematical expression not reproducible] is a legitimate signature signed on the message m by the user ID, then

[mathematical expression not reproducible] (7)

Thus, we have

[mathematical expression not reproducible]

Clearly, the CA's forgery (m', <j,(C', [R'.sub.[pi]], [R'.sub.m]), [mathematical expression not reproducible]) passes the following signature verification equation

[mathematical expression not reproducible] (8)

Therefore, the CA succeeds in faking a legitimate pair of message and signature in the name of the user ID. This implies that the existential unforgeability of the scheme is broken by the CA completely.

4. An Enhanced FS-CBS Scheme

Next, we propose an enhanced FS-CBS scheme to fix the security defect in Li et al. 's FS-CBS scheme [38]. Our proofs in the standard model demonstate that the enhanced scheme meets the FS&EUF-CMA security under the compexity assumtion of the Squ-CDH problem.

4.1 Basic idea

The security weakness in Li et al.'s FS-CBS scheme [38] is mainly due to the reason that the component pertaining to the message (i.e., [mathematical expression not reproducible]) in a signature is independent on the signer's secret key. Thus, by injecting trapdoors into public system parameters properly, a CA can tamper a signature by replacing [mathematical expression not reproducible] with [mathematical expression not reproducible] without affecting the correctness of the signature. To overcome this security weakness, we implant part of the signer's public key (i.e., [PK.sub.ID,2]) in the signatures. Specifically, in the enhanced scheme, the component of a signature <j, [sigma] = ([[sigma].sub.1], [[sigma].sub.2], [[sigma].sub.3], [[sigma].sub.4])> pertaining to the message (namely [[sigma].sub.3]) is defined to the form [mathematical expression not reproducible]. If wanting to fake a new signature from a signature <j, [sigma] = ([[sigma].sub.1], [[sigma].sub.2], [[sigma].sub.3], [[sigma].sub.4])>, the CA needs to remove [([PK.sup.[phi].sub.ID,2] * [v.sub.[beta]]).sup.r] from [[sigma].sub.3]. Clearly, it can do this unless it knows either the secret value to generate the signer's public key or the random r chosen by the singer to create the signature<j, [sigma]= ([[sigma].sub.1], [[sigma].sub.2], [[sigma].sub.3], [[sigma].sub.4])>. Obviously, both of these two values are unkonw to the CA. In this way, the enhanced scheme obtains the security against the malicious CA attack presented in Subsection 3.2.

Besides the secuirty enhancement, the enhanced scheme also optimizes the system performance. Specifically, it refines the key update algorithm so as to greatly shorten the length of the node keys. In the original scheme, the secret key of a node at depth d consists of d + 1 elements (including d elements in [G.sub.1] and an element in [Z*.sub.p]), while that in the enhanced scheme only consists of two elements (including an element in [G.sub.1] and an element in [Z*.sub.p]). Therefore, the enhanced scheme enjoys the shorter private key/signature length, which leads to the lower storage and communication costs.

4.2 Description of the enhanced FS-CBS scheme

The enhanced FS-CBS scheme is composed of the following algorithms:

--Setup(k, T): This algorithm selects an integer [alpha] [member of] [Z*.sub.p] randomly and sets [g.sub.1] = [g.sup.[alpha]]. It also randomly chooses [g.sub.2], [v.sub.0], [v.sub.1] [member of] [G.sub.1], a vector [mathematical expression not reproducible] and two hash functions H: {0,1}* [right arrow] [Z*.sub.p] and [mathematical expression not reproducible], where [n.sub.u] [member of] [Z.sup.+]. Additionally, it defines a two-value function f: [G.sub.1] [right arrow] {0,1}: for any point [pi] [member of] [G.sub.1], f([pi]) = 1 if the x-coordinate of the point [pi] is odd or f([pi]) = 0 else. Finally, it outputs params = {T, [G.sub.1], [G.sub.2], p, e, g, [g.sub.1], [g.sub.2], [v.sub.0], [v.sub.1], [??], [H.sub.u], H, f} and msk = [g.sup.[alpha].sub.1]. For simplicity, for any [n.sub.u]-bit binary string [mathematical expression not reproducible], we define a function [mathematical expression not reproducible].

--UserKeyGen(params, ID): This algorithm chooses an integer x [member of] [Z*.sub.p] randomly, calculates an initial secret key [SK.sup.0.sub.ID] = [x.sup.2] and a public key [mathematical expression not reproducible]. The node key of the root of the key-evolving tree emplyed by the user ID is set to be [NSK.sub.[epsilon]] = [SK.sup.0.sub.ID] and pushed into the stack NSK-[STACK.sub.ID]. Note that the validity of a public key [PK.sub.ID] = ([PK.sub.ID,1], [PK.sub.ID.2], [PK.sub.ID,3]) can be checked by verifying whether the equations e([PK.sub.ID.1], [PK.sub.ID,2]) = e([g.sub.1], [g.sub.2]) and e([PK.sub.ID,1], [PK.sub.ID,1]) = [PK.sub.ID,3] hold.

--CertGen(params, msk, ID, [PK.sub.ID]): This algorithm chooses a random integer s [member of] [Z*.sub.p] and creates a certificate [Cert.sub.ID] = ([Cert.sub.ID,1], [Cert.sub.ID,2]) = ([g.sup.s], [g.sup.[alpha].sub.1] * F[([[lambda].sub.ID]).sup.s]), where [[lambda].sub.ID] = [H.sub.1](ID, [PK.sub.ID]).

--KeyUpdate(params, j, [SK.sup.j.sub.ID]): Let [[omega].sup.j] = [[omega].sub.1] [[omega].sub.2]... [[omega].sub.n] [member of] [{0,1}.sup.d] be the node in the key-evolving tree corresponding to the time slot j. The node key of [[omega].sup.j] has the form [mathematical expression not reproducible]. Specially, the node key corresponding to the root node is [NSK.sub.[epsilon]] = [Y.sub.[epsilon]]. Given the index of a time slot j [member of] [0, T-1) and a secret key [SK.sup.j.sub.ID], this algorithm pops the node key [mathematical expression not reproducible] off the stack NSK-[STACK.sub.ID] and creates a secret key [SK.sup.j+1.sub.ID] for the time slot j + 1 as follows:

* If [[omega].sup.j] is an internal node, then it selects two random integers [mathematical expression not reproducible] and computes the node secret keys [mathematical expression not reproducible] and [mathematical expression not reproducible] for the nodes [[omega].sup.j]0 and [[omega].sup.j]1 as follows:

[mathematical expression not reproducible] (9)

[mathematical expression not reproducible] (10)

It pushes [mathematical expression not reproducible] and then [mathematical expression not reproducible] onto the stack NSK-[STACK.sub.ID] and sets the node keys in the stack as the secret key [SK.sup.j+1.sub.ID]. Obviously, the node key of any [omega] (j > 0) has the form [mathematical expression not reproducible] for some t' [member of] [Z*.sub.p].

* Else if [[omega].sup.j] is a leaf node, it sets the remaining node keys in the stack NSK-[STACK.sub.ID] as the secret key [SK.sup.j+1.sub.ID]. Now, the node key on the top of NSK-[STACK.sub.ID] is [mathematical expression not reproducible].

--Sign(params, j, m, ID, [SK.sup.j.sub.ID], [Cert.sub.ID]): Assuming that [[omega].sup.j] [member of] [{0,1}.sup.n] is the node in the key-evolving tree corresponding to the time slot j [member of] [0, T-1]. This algorithm selects two random integers r, r' [member of] [Z*.sub.p], retrieves the node key [mathematical expression not reproducible] from NSK-[STACK.sub.ID] and sets

[mathematical expression not reproducible] (11)

where [[lambda].sub.ID] = [H.sub.1] (ID, [PK.sub.ID]), [beta]=f([[sigma].sub.2]) and [phi] = [H.sub.2](ID, [PK.sub.ID], [[sigma].sub.1] [[sigma].sub.2], m, [v.sub.[beta]]). Finally, it outputs <j, [sigma]> as the signature for the message m. Because [Cert.sub.ID] = ([Cert.sub.ID,1], [Cert.sub.ID,2]) = ([g.sup.s], [g.sup.[alpha].sub.1] F[([[lambda].sub.ID]).sup.s]), we have that

[mathematical expression not reproducible] (12)

where [mathematical expression not reproducible].

--Verify(params, m, <j, [sigma]>, ID, [PK.sub.ID]): To verify a signature <j, [sigma]= ([[sigma].sub.1], [[sigma].sub.2], [[sigma].sub.3], [[sigma].sub.4])> by using the signer's public key [PK.sub.ID] = ([PK.sub.ID,1], [PK.sub.ID,2], [PK.sub.ID,3]), this algorithm verifies if the following equality is satisfied:

e([[sigma].sub.3], g) = [PK.sub.ID,3] * e([g.sub.1], [[sigma].sub.4]) * e (F ([[lambda].sub.ID]), [[sigma].sub.2]) * e ([PK.sup.[phi].sub.ID,2] * [v.sub.[beta]], [[sigma].sub.1]), (13)

where [[lambda].sub.ID] = [H.sub.1](ID, [PK.sub.ID]), [beta] = f([[sigma].sub.2]) and [phi] = [H.sub.2](ID, [PK.sub.ID], [[sigma].sub.1], [[sigma].sub.2], m, [v.sub.[beta]]). The algorithm outputs 1 if it does or 0 else.

4.3 Correctness and security proofs

First of all, we demonstrate the correctness of the enhanced FS-CBS scheme.

Theorem 1. The enhanced FS-CBS scheme is correct.

Proof. Let <j, [sigma]> be the signature on a message m signed by a user with identity ID. Then, [mathematical expression not reproducible], where r, [??] [member of] [Z*.sub.p], [[lambda].sub.ID] = [H.sub.1](ID, [PK.sub.ID]), [beta]= f([[sigma].sub.2]) and [phi] = [H.sub.2](ID, [PK.sub.ID], [[sigma].sub.1], [[sigma].sub.2], m, [v.sub.[beta]]). Because the node key associated with the node [[omega].sup.j] in the key-evolving tree corresponding to the time slot j has the form [mathematical expression not reproducible], for some t' [member of] [Z*.sub.p], we can deduce that

[mathematical expression not reproducible]

Therefore, the correctness of the scheme is proved. #

The following are the security statement and proof.

Theorem 2. The enhanced FS-CBS scheme achieves the FS&EUF-CMA security in the standard model if the Squ-CDH assumption holds in the group [G.sub.1].

Proof. Assuming that [A.sub.I] is a Type-I adversary who has a non-negligible advantage [epsilon] to crack the FS&EUF-CMA security of the enhanced FS-CBS scheme. We show how to construct an algorithm B who has a non-negligible advantage [epsilon]' [greater than or equal to] [[epsilon]/8([n.sub.u] + 1)([q.sub.C] + [q.sub.S])] to resolve the Squ-CDH problem in [G.sub.1] by employing the adversary [A.sub.I] as a subprocedure, where [q.sub.C] and [q.sub.S] are the maximum number of the adversary [A.sub.I]'s queries submitted to [O.sup.Certify] and [O.sup.Sign] respectively.

Given a random Squ-CDH problem instance (g, A = [g.sup.a]) in the group [G.sub.1], the algorithm B simulates as a game challenger and plays with the adversary [A.sub.I] to compute [mathematical expression not reproducible] in the following way:

--Setup Phase. We set l = 2([q.sub.C] + [q.sub.S]). Suppose that p is a large prime number that is greater than l([n.sub.u] + 1). The algorithm B selects integers [beta]',[[beta].sub.1],..., [mathematical expression not reproducible] and b, c, [d.sub.0], [d.sub.1] [member of] [Z*.sub.p] randomly. Furthermore, it selects a random number k [member of] {0,1,...,[n.sub.u]}. Then, it sets [g.sub.1] = A, [g.sub.2] = [g.sup.b], u' = [A.sup.p-lk+[beta]'] [g.sup.[gamma]'], [mathematical expression not reproducible], [mathematical expression not reproducible] and [mathematical expression not reproducible]. Other public system parameters are created according to the specification of the algorithm Setup. The above simulation implies that the CA's master secret key is implicitly defined to be [mathematical expression not reproducible] which is unknown to the algorithm B. As a matter of convenience, for any [n.sub.u]-bit binary string [mathematical expression not reproducible], we introduce the following two functions:

[mathematical expression not reproducible] (14)

[mathematical expression not reproducible] (15)

We can easily derive that [mathematical expression not reproducible].

--Query-Answer Phase. After receiving the public system parameters params, the adversary [A.sub.I] sends queries to the oracles {[O.sup.UserCreate], [O.sup.PhvateKeyCorrupt], [O.sup.Certify], [O.sup.PublicKeyReplace], [O.sup.Sign]} adaptively. The algorithm B keeps a list UserList containing tuples ([ID.sub.i], [mathematical expression not reproducible], [x.sub.i]) and a list PrivateKeyList containing tuples ([ID.sub.i], j, [mathematical expression not reproducible]), and answers the adversary's various oracle queries as below:

* [O.sup.UserCreate]: Inputing an identity [ID.sub.i], the algorithm B retrieves UserList to seek out a tuple ([ID.sub.i], [mathematical expression not reproducible], [x.sub.i]).

(a) If such a tuple exists, it returns [mathematical expression not reproducible];

(b) Otherwise, it selects a random integer [x.sub.i] [member of] [Z*.sub.p] and calculates [mathematical expression not reproducible]. Then, it adds ([ID.sub.i], [mathematical expression not reproducible], [x.sub.i]) to UserList and outputs [mathematical expression not reproducible].

* [O.sup.Certify]: Inputing an identity [ID.sub.i], the algorithm B retrieves UserList to seek out a tuple ([ID.sub.i], [mathematical expression not reproducible], [x.sub.i]) and performs as below:

(a) If J ([mathematical expression not reproducible]) = 0 (mod p) where [mathematical expression not reproducible] = [H.sub.1] ([ID.sub.i], [mathematical expression not reproducible]), it terminates the game;

(b) Else, it selects a random integer s [member of] [Z*.sub.p] and creates a certificate

[mathematical expression not reproducible]. (16)

Then, it returns [mathematical expression not reproducible] to the adversary [A.sub.I]. It is clear that the algorithm B is able to produce such certificate iff J ([mathematical expression not reproducible]) [not equal to] 0 (mod l), which also implies J ([mathematical expression not reproducible]) [not equal to] 0 (mod p). If let s' = s - a/J([mathematical expression not reproducible]), then we get

[mathematical expression not reproducible]

* [O.sup.PrivateKeyCorrupt]: Inputing an identity [ID.sub.i] and the index of a time slot j, the algorithm B retrieves PrivateKeyList to seek out a tuple ([ID.sub.i], j, [mathematical expression not reproducible]).

(a) If PrivateKeyList has contained such a tuple, it returns [mathematical expression not reproducible] directly;

(b) Else if j = 0, it retrieves UserList to seek out a tuple ([ID.sub.i], [mathematical expression not reproducible], [x.sub.i]), computes [mathematical expression not reproducible] = [x.sup.2.sub.i] and then returns [mathematical expression not reproducible];

(c) Otherwise, it retrieves the list UserList to seek out a tuple ([ID.sub.i], [mathematical expression not reproducible], [x.sub.i]) and creates a secret key [mathematical expression not reproducible] for the time slot j by performing KeyEvolve(... KeyEvolve(params, [x.sup.2.sub.i], 0),..., j - 1). Then, it adds ([ID.sub.i], j, [mathematical expression not reproducible]) to PrivateKeyList and returns [mathematical expression not reproducible].

* [O.sup.PublicKeyReplace]: Inputing an identity [ID.sub.i], a false public key [mathematical expression not reproducible] and a secret value [x'.sub.i], the algorithm B retrieves UserList to seek out a tuple ([ID.sub.i], [mathematical expression not reproducible], [x.sub.i]) and replaces it with ([ID.sub.i], [mathematical expression not reproducible], [x'.sub.i]).

* [O.sup.Sign]: Inputing an identity [ID.sub.i], the index of a time slot j and a message m, the algorithm B retrieves UserList to seek out a tuple ([ID.sub.i], [mathematical expression not reproducible], [x.sub.i]) and does the following:

(a) If J ([mathematical expression not reproducible]) = 0 (mod p) where [mathematical expression not reproducible] = [H.sub.1] ([ID.sub.i], [mathematical expression not reproducible]), then it terminates the game;

(b) Else, it first derives a certificate [mathematical expression not reproducible] by calling the oracle [O.sup.Certify] and a secret key [mathematical expression not reproducible] for the time slot j by calling the oracle [O.sup.PrivateKeyCorrupt] respectively. Then, it runs the algorithm Sign(params, j, m, [ID.sub.i], [mathematical expression not reproducible], [mathematical expression not reproducible]) to generate a signature <j, [sigma]> and outputs the result to the adverary.

--Forge Phase. In the end, the adversary [A.sub.I] outputs a forgery (ID*, m*, <j*, [sigma]*>), where [sigma]* = ([[sigma]*.sub.1], [[sigma]*.sub.2], [[sigma]*.sub.3], [[sigma]*.sub.4]). If J ([[lambda].sub.ID*]) [not equal to] 0 (mod p) or f ([[sigma]*.sub.2]) = 1 where [[lambda].sub.ID*] = [H.sub.1] (ID*, [PK.sup.ID*]), the algorithm B terminates the game. Else, it first fetches back the secret value x* from the tuple (ID*, [PK.sup.ID*], x*) and the secret key [mathematical expression not reproducible] from the private key [mathematical expression not reproducible] after querying the oracle [O.sup.PrivateKeyCorrupt] on <ID*, j*>. Then, it sets [phi]* = [H.sub.2] (ID*, [PK.sup.ID*], [[sigma]*.sub.1], [[sigma]*.sub.2], m*, [v.sub.0]), computes

[mathematical expression not reproducible] (17)

and then outputs it as the answer to the given Squ-CDH problem.

If <j*, [sigma]*> is a legitimate signature under ID* and [PK.sup.ID*] = ([PK.sup.ID*,1], [PK.sup.ID*,2], [PK.sup.ID*,3]), then we have that

[mathematical expression not reproducible] (18)

where r, [??] [member of] [Z*.sub.p] and [[lambda].sub.ID*] = [H.sub.1] (ID*, [PK.sup.ID*]). In addition, [mathematical expression not reproducible] because J([[lambda].sub.ID*]) = 0 (mod p). Thus, we can deduce that

[mathematical expression not reproducible]

Therefore, T is the correct solution to the Squ-CDH problem.

Analysis. Next, we derive the bound on the algorithm B's advantage. Accodrding to the above interaction, the algorithm B does not terminate the game if the following constraints are satisfied:

--All the adversary [A.sub.I]'s requests to [O.sup.Certify] satisfy J([mathematical expression not reproducible]) [not equal to] 0 (mod p);

--All the adversary [A.sub.I]'s requests to [O.sup.Sign] satisfy J([mathematical expression not reproducible]) [not equal to] 0 (mod p);

--The adversary [A.sub.I]'s forgery (ID*, m*, <j*, [sigma]*>) satisfies J([[lambda].sub.ID*]) = 0 (mod p) and f ([[sigma]*.sub.2]) = 0.

In the adversary [A.sub.I]'s queries, we assume [[lambda].sub.1], [[lambda].sub.2],..., [mathematical expression not reproducible] to be the hash values that are not equal to [[lambda].sub.ID*]. Clearly, we have [q.sub.h] [less than or equal to] [q.sub.C] + [q.sub.S]. We define the following events:

--A*: J ([[lambda].sub.ID*]) = 0 (mod p),

--[A.sub.i]: J ([[lambda].sub.ID*]) [not equal to] 0 (modp), where i = 1, 2,..., [q.sub.h],

--B*: f ([[sigma]*.sub.2]) = 0.

Clearly, the probability of the event that the algorithm B does not terminate the game is [mathematical expression not reproducible]. The premise l([n.sub.u] + 1)<< p means that if J ([[lambda].sub.ID*]) = 0 (mod p) then J ([[lambda].sub.ID*]) = 0 (mod l). In addition, this premise also means that if J ([[lambda].sub.ID*]) = 0 (mod l). As a result, there uniquely exists an integer k (0 [less than or equal to] k [less than or equal to] [n.sub.u]) such that J ([[lambda].sub.ID*]) = 0 (mod p). Hence, we have

Pr[A*] = Pr[J ([[lambda].sub.ID*]) = 0 (mod p) [and] J ([[lambda].sub.ID*]) = 0 (mod l)] = Pr[J ([[lambda].sub.ID*]) = 0 (mod p) | J ([[lambda].sub.ID*]) = 0 (mod l)] * Pr[J([[lambda].sub.ID*]) = 0 (mod l)] = [1/[[n.sub.u] + 1]l].

Because the events A* and [A.sub.i] (i = 1, 2,..., [q.sub.h]) are independent with each other, we get

[mathematical expression not reproducible]

Furthermore, B* and [mathematical expression not reproducible] are also independent with each other and Pr[B] = 1/2. Therefore, we get

[mathematical expression not reproducible]

Clearly, if the algorithm B does not terminate the game, then the adversary [A.sub.I] succeeds in forging a valid signature with advantage [epsilon]. Thus, the algorithm B's advantage in successfully resolving the Squ-CDH problem is [epsilon]'[greater than or equal to] [[epsilon]/8[([n.sub.u] + 1) ([q.sub.c] + [q.sub.s])]]. This contradicts the Squ-CDH assumption.

In a similar way, we can demonstrate that if there exists a Type-II adversary who has a non-negligible advantage to crack the FS&EUF-CMA security of the enhanced FS-CBS scheme, then a polynomial-time algorithm can be constructed to successfully resolve the Squ-CDH problem with a non-negligible advantage. #

4.4 Comparison

Below, we compare the enhanced FS-CBS scheme with Li et al.'s scheme [38]. Considering that the FS-CBS scheme in [39] is designed in the random oracle model, we do not include it in the comparison.

As listed in Table 1, we mainly consider four distinct cryptographic operations in the computation cost comparison, including the bilinear pairing, the multiplication in [G.sub.2], the exponentiation in [G.sub.1] and the multiplication in [G.sub.1], respectively. The running time of hash and integer modular addition are ignored as usual. On average, computing u' [[product].sub.i[member of]u][u.sub.i] and v' [[product].sub.i[member of]M][v.sub.i] in Li et al. 's scheme respectively requires performing [n.sub.u]/2 and [n.sub.v]/2 multiplication operations in [G.sub.1], while computing [F.sub.u] ([lambda]) in our scheme requires performing [n.sub.u]/2 multiplication operations in [G.sub.1]. We evaluate the computational efficiency of an algorithm by adding the time of the basic operations. As an example, the enhanced FS-CBS scheme needs to calculate 7 exponentiations and ([n.sub.u]/2 + 4) multiplications in [G.sub.1] to sign a message. Therefore, the time cost of the algorithm Sign is 7[T.sub.E] + ([n.sub.u]/2 + 4)[T.sub.M1]. In the comparison of communication/storage cost, the size of the public system parameters/a user secret key/a signature is measured by the sizes of involved elements and integers. For instance, a signature in the enhanced FS-CBS scheme comprises 4 elements in [G.sub.1]. Thus, the signature size is 4|[G.sub.1]| bits. In addition, the secret key of root node in Li et al.'s scheme consists of one integer in [Z*.sub.p], while the secret key of any other node at depth d comprises one integer in [Z*.sub.p] and d elements in [G.sub.1]. Recall that a user secret key used in the time slot j is composed of the node key of [[omega].sup.j] and all node keys of the right siblings of the nodes on the routine from the root node to [[omega].sup.j]. Therefore, the size of a private key is at most d |[Z*.sub.p] | + [[summation].sup.d.sub.i=1]i |[G.sub.1]| bits. Table 2 shows the details of Li et al.'s scheme and the enhanced scheme.

We implement two FS-CBS schemes on a PC that runs Windows 7 (64bit) with Intel(R) Core i7 CPU@2.3GHz and 8GB RAM memory by employing the PBC library [41]. Table 3 provides the time cost of distinct cryptographic operations and the size of distinct elements. We instantiate the bilinear map using the Type 1 pairing over the elliptic curve E([F.sub.q]): [y.sup.2] = [x.sub.3] + x with embedding degree 2. The group size q is a 512-bit prime satisfying q + 1 = pr and p is a 160-bit Solinas prime number. For ease of comparison, the number of the system time slots T is set to be 127. Therefore, the depth d of the node in the evolving tree associated with the time slot in which the message is signed changes from 1 to 6 (= [log.sub.2](127 + 1) - 1). In addition, all cryptographic hash functions in two schemes are simulated by SHA-512. Therefore, the size of a hash value is 512 bits (namely that [n.sub.u] = 512 and [n.sub.v] = 512). Table 4 and Table 5 respectively show the concrete computation and commnication/storage costs of two schemes corresponding to the different values of the depth d.

To shorten the length of node keys, the enhanced FS-CBS scheme has to compute two additional multiplications in [G.sub.1]. Therefore, as shown in Table 4, the key evolving operation is less efficient than that of the original scheme. But, the short node keys in the enhanced scheme lead to the better computation efficiency in both the message signing and signature verifying algorithms. Table 5 indicates that it enjoys better performance in the communication and storage efficiency than the original scheme. Moreover, the security of the enhanced scheme is over the complexity assumption of the Squ-CDH problem that is harder than the GCDH and Many-DH problems on which Li et al.'s scheme is based. At last and most importantly, the enhanced scheme provides much stronger security guarantee, because it resists the malicious CA attack while Li et al.'s scheme does not.

5. Conclusions

In this paper, we demonstrate that the FS-CBS scheme presented by Li et al. [38] can not resist the existential forgery attack from the malicious CA. To address this issue, we put forward an enhanced FS-CBS scheme and formally prove it to satisfy the existential unforgeability under the complexity assumption of the Squ-CDH problem in the standard model. The enhanced scheme repaires the defect in Li et al.'s FS-CBS scheme and provides resistance against the attacks by the malicious CA. Comparisons show that it offers stronger security guarantee and enjoys better performance than the original scheme.

References

[1] R. Anderson, "Two Remarks on public key cryptology," in Proc. of ACM CCS 1997, invited lecture, April 1-4, 1997. Article (CrossRef Link).

[2] M. Bellare and S. K. Miner, "A forward-secure digital signature scheme," in Proc. of Crypto 1999, pp. 431-448, August 15-19, 1999. Article (CrossRef Link).

[3] R. Canetti, S. Halevi and J. Katz, "A forward-secure public-key encryption scheme," in Proc. of Eurocrypt 2003, pp. 255-271, May 4-8, 2003. Article (CrossRef Link).

[4] M. Abdalla and L. Reyzin, "A new forward-secure digital signature scheme," in Proc. of Asiacrypt 2000, pp. 116-129, December 3-7, 2000. Article (CrossRef Link).

[5] G. Itkis and L. Reyzin, "Forward-secure signatures with optimal signing and verifying," in Proc. of Crypto 2001, pp. 499-514, August 19-23, 2001. Article (CrossRef Link).

[6] T. Malkin, D. Micciancio, S. K. Miner, "Efficient generic forward-secure signatures with an unbounded number of time periods," in Proc. of Eurocrypt 2002, pp. 400-417, April 28 - May 2, 2002. Article (CrossRef Link).

[7] B. Libert, J. Quisquater, M. Yung, "Forward-secure signatures in untrusted update environments," in Proc. of ACM CCS 2007, pp. 266-275, Oct 29 - Nov 2, 2007. Article (CrossRef Link).

[8] J. Yu, R. Hao, F. Kong, X. Cheng, J. Fan and Y. Chen, "Forward-secure identity-based signature: security notions and construction," Information Sciences, vol. 181, no. 3, pp. 648-660, February, 2011. Article (CrossRef Link).

[9] J. Wei, W. Liu and X. Hu, "Forward-secure identity-based signature with efficient revocation," International Journal of Computer Mathematics, vol. 94, no. 7, July, 2016. Article (CrossRef Link).

[10] J. Yu, H. Xia, H. Zhao, R. Hao, Z. Fu and X. Cheng, "Forward-secure identity-based signature scheme in untrusted update environments," Wireless Personal Communications, vol. 86, no. 3, pp. 1467-1491, February, 2016. Article (CrossRef Link).

[11] D. Yao, N. Fazio, Y. Dodis, A. Lysyanskaya, "ID-based encryption for complex hierarchies with applications to forward security and broadcast encryption," in Proc. of ACM CCS 2004, pp. 354-363, October 25 - 29, 2004. Article (CrossRef Link).

[12] Y. Lu and J. Li, "A practical forward-secure public-key encryption scheme," Journal of Networks, vol. 6, no. 9, pp. 1254-1261, June, 2011. Article (CrossRef Link).

[13] J. Yu, F. Kong, X. Cheng, R. Hao and J. Fan, "Forward-secure identity-based public-key encryption without random oracles," Fundamenta Informaticae, vol. 111, no. 2, pp. 241-256, February, 2011. Article (CrossRef Link).

[14] K. Singh and N. Trichy, "Lattice forward-secure identity based encryption scheme," Journal of Internet Services and Information Security, vol. 2, no. 3/4, pp. 118-128, April, 2012. Article (CrossRef Link).

[15] Y. Lu and J. Li, "New forward-secure public-key encryption without random oracles," International Journal of Computer Mathematics, vol. 90, no. 12, pp. 2603-2613, December, 2013. Article (CrossRef Link).

[16] Y. Lu and J. Li, "Forward-secure identity-based encryption with direct chosen-ciphertext security in the standard model," Advances in Mathematics of Communications, 2017, vol. 11, vol. 1, pp. 161-177, March, 2017. Article (CrossRef Link).

[17] A. Shamir, "Identity-based cryptosystems and signature schemes," in Proc. of Crypto 1984, pp. 47-53, August 19-22, 1984. Article (CrossRef Link).

[18] C. Gentry, "Certificate-based encryption and the certificate revocation problem," in Proc. of Eurocrypt 2003, pp. 272-293, May 4-8, 2003. Article (CrossRef Link).

[19] W. Wu, Y. Mu, W. Susilo, X. Huang and L. Xu, "A provably secure construction of certificate-based encryption from certificateless encryption," The Computer Journal, vol. 55, no. 10, pp. 1157-1168, January, 2012. Article (CrossRef Link).

[20] D. Galindo, P. Morillo and C. Rafols, "Improved certificate-based encryption in the standard model," Journal of Systems and Software, vol. 81, no. 7, pp. 1218-1226, July, 2008. Article (CrossRef Link).

[21] J. K. Liu and J. Zhou, "Efficient certificate-based encryption in the standard model," in Proc. of SCN 2008, pp. 144-155, September 10-12, 2008. Article (CrossRef Link).

[22] Y. Lu and J. Li, "Efficient construction of certificate-based encryption secure against public key replacement attacks in the standard model," Journal of Information Science and Engineering, vol. 30, no. 5, pp. 1553-1568, September, 2014. Article (CrossRef Link).

[23] Q. Yu, J. Li and Y. Zhang, "Leakage-resilient certificate-based encryption," Security and Communication Networks, vol. 8, no, 18, pp. 3346-3355, May, 2015. Article (CrossRef Link).

[24] Y. Lu and Q. Zhang, "Enhanced certificate-based encryption scheme without bilinear pairings," KSII Transactions on Internet and Information Systems, vol. 10, no. 2, pp. 881-896, February, 2016. Article (CrossRef Link).

[25] Q. Yu, J. Li, Y. Zhang, W. Wu, X. Huang and Y. Xiang, "Certificate-based encryption resilient to key leakage," Journal of Systems and Software, vol. 116, pp. 101-112, June, 2016. Article (CrossRef Link).

[26] J. Li, Y. Guo, Q. Yu, Y. Lu, Y. Zhang, F. Zhang, "Continuous leakage-resilient certificate-based encryption," Information Sciences, vol. 355-356, pp. 1-14, August, 2016. Article (CrossRef Link).

[27] Y. Lu and J. Li, "A provably secure certificate-based encryption scheme secure against malicious CA attacks in the standard model," Information Sciences, vol. 372, pp. 745-757, December, 2016. Article (CrossRef Link).

[28] Y. Lu and J. Li, "A pairing-free certificate-based proxy re-encryption scheme for secure data sharing in public clouds," Future Generation Computer Systems, vol. 62, pp. 140-147, September, 2016. Article (CrossRef Link).

[29] B. G. Kang, J. H. Park and S. G. Hahn, "A certificate-based signature scheme," in Proc. of Topics in Cryptology - CT-RSA 2004, pp. 99-111, February 23-27, 2004. Article (CrossRef Link).

[30] M.H. Au, J.K. Liu, W. Susilo and T.H. Yuen, "Certificate based (linkable) ring signature," in Proc. of ISPEC 2007, pp. 79-92, May 7 - 10, 2007. Article (CrossRef Link).

[31] W. Wu, Y. Mu, W. Susilo, X. Huang, "Certificate-based signatures, revisited," Journal of Universal Computer Science, vol. 15, no. 8, pp. 1659-1684, April, 2009. Article (CrossRef Link).

[32] J.K. Liu, F. Bao and J. Zhou, "Short and efficient certificate-based signature," in Proc. of Networking 2011 Workshops, pp. 167-178, May 13, 2011. Article (CrossRef Link).

[33] J. Li, X. Huang, Y. Zhang, L. Xu, "An Efficient short certificate-based signature scheme," Journal of Systems and Software, vol. 85, no. 2, pp. 314-322, February, 2012. Article (CrossRef Link).

[34] J. Li, Z. Wang and Y. Zhang, "Provably secure certificate-based signature scheme without pairings," Information Science, vol. 233, pp. 313-320, June, 2013. Article (CrossRef Link).

[35] Y. Lu and J. Li, "An improved certificate-based signature scheme without random oracles," IET Information Security, vol. 10, no. 2, pp. 80-86, February, 2016. Article (CrossRef Link).

[36] Y. Lu, Jiguo Li and Jian Shen, "Weakness and improvement of a certificate-based key-insulated signature in the standard model," The Computer Journal, vol. 60, no. 12, pp. 1729-1744, December, 2017. Article (CrossRef Link).

[37] Y. Lu and J. Li, "Forward-secure certificate-based encryption and its generic construction," Journal of Networks, vol. 5, no. 5, pp. 527-534, May, 2010. Article (CrossRef Link).

[38] J. Li, Y. Zhang, H. Teng, "A forward-secure certificate-based signature scheme in the standard model," in Proc. of CSS 2012, pp. 362-376, December 12-13, 2012. Article (CrossRef Link).

[39] J. Li, H. Teng, X. Huang, Y. Zhang and J. Zhou, "A forward-secure certificate-based signature scheme," The Computer Journal, vol. 58, no. 4, pp. 853-866, April, 2015. Article (CrossRef Link).

[40] F. Zhang, R. Safavi-Naini and W. Susilo, "An efficient signature scheme from bilinear parings and its applications," in Proc. of PKC 2004, pp. 277-290, March 1-4, 2004. Article (CrossRef Link).

[41] B. Lynn, "PBC library: The pairing-based cryptography library," http://crypto.stanford.edu/pbc/. Article (CrossRef Link).

Yang Lu received the Ph.D. degree in computer science from PLA University of Science and Technology, Nanjing, China, in 2009. He is currently a professor with the School of Computer Science and Technology, Nanjing Normal University, Nanjing, China. His major research interests include information security and cryptography, network security and cloud security, etc. He has published more than 60 scientific papers in international conferences and journals.

Jiguo Li received the Ph.D. degree from Harbin Institute of Technology in 2003. He is currently a professor with the College of Mathematics and Informatics, Fujian Normal University, Fuzhou, China. His research interests include cryptography and information security, cloud computing, wireless security and trusted computing etc. He has published over 100 research papers in refereed international conferences and journals. His work has been cited more than 2000 times at Google Scholar.

Yang Lu (1) and Jiguo Li (2)

(1) School of Computer Science and Technology, Nanjing Normal University Nanjing 210023, China

[e-mail: luyangnsd@163.com]

(2) College of Mathematics and Informatics, Fujian Normal University Fuzhou 350117, China

[e-mail: ljg1688@163.com]

(*) Corresponding author: Yang Lu

Received December 25, 2017; revised August 10, 2018; accepted October 1, 2018; published March 31 2019

http://doi.org/10.3837/tils.2019.03.022

Table 1. Notations used in the comparison Notations Descriptions [T.sub.B] Running time of a pairing operation [T.sub.E] Running time of an exponentiation operation in [G.sub.1] [T.sub.M1] Running time of a multiplication in [G.sub.1] [T.sub.M2] Running time of a multiplication in [G.sub.2] |[G.sub.1]| Length of an element in [G.sub.1] |[Z*.sub.p]| Length of an integer in [Z*.sub.p] Table 2. Comparison of two FS-CBS schemes without random oracles Compared items Original scheme [38] Complexity problem(s) GCDH + Many-DH Secure against the malicious no CA attack? Secret key evolving cost 2[T.sub.E] Message signing cost 6[T.sub.E] + ([n.sub.u]/2 + [n.sub.v]/2 + 3) [T.sub.M1] Signature verifying cost 5[T.sub.B]+([n.sub.u]/2 + [n.sub.v]/2 + d - 1) [T.sub.M1] + 3[T.sub.M2] Public system parameters size ([n.sub.u] + [n.sub.v] + 5) |[G.sub.1]| Signature size (d + 3) |[G.sub.1]| Private key size d |[Z*.sub.p]| + [[summation].sup.d.sub.i=1]i |[G.sub.1]| Compared items Enhanced scheme Complexity problem(s) Squ-CDH Secure against the malicious yes CA attack? Secret key evolving cost 2[T.sub.E] + 2[T.sub.M1] Message signing cost 7[T.sub.E] + ([n.sub.u]/2 + 4) [T.sub.M1] Signature verifying cost 4[T.sub.B] + [T.sub.E] + ([n.sub.u]/2+1) [T.sub.M1] + 3[T.sub.M2] Public system parameters size ([n.sub.u] + 6) |[G.sub.1]| Signature size 4|[G.sub.1]| Private key size d |[Z*.sub.p]| + d |[G.sub.1]| Table 3. Benchmark time of various cryptographic operations and size of various elements Operations/Elements Running Time (ms)/Bit-Length (bit) [T.sub.B] 3.296 [T.sub.E] 2.757 [T.sub.M1] 0.013 [T.sub.M2] 0.003 |[G.sub.1]| 512 |[Z*.sub.p]| 160 Table 4. Experimental results of the computation costs Schemes Compared Computation costs (ms) items d = 1 d = 2 d = 3 d = 4 d = 5 d = 6 Key evolving 5.514 Li et Signing 23.237 al.'s [38] Verifying 23.145 23.158 23.171 23.184 23.197 23.210 Key evolving 5.54 Ours Signing 22.679 Verifying 19.291 Table 5. Experimental results of the communication and storage costs Schemes Compared Communication and storage costs (bit) items d = 1 d = 2 d = 3 d = 4 d = 5 d = 6 Public 526848 parameters Li et Signature 2048 2560 3072 3584 4096 4608 al.'s [38] Private key 672 1856 3552 5760 8480 11712 Public 265216 parameters Ours Signature 2408 Private key 672 1344 2016 2688 3360 4032

Printer friendly Cite/link Email Feedback | |

Author: | Lu, Yang; Li, Jiguo |
---|---|

Publication: | KSII Transactions on Internet and Information Systems |

Article Type: | Report |

Date: | Mar 1, 2019 |

Words: | 10509 |

Previous Article: | Node Incentive Mechanism in Selfish Opportunistic Network. |

Next Article: | Adaptively Secure Anonymous Identity-based Broadcast Encryption for Data Access Control in Cloud Storage Service. |

Topics: |