# Certificateless Public Auditing Protocol withConstant Verification Time

Authors: Dongmin Kim; Ik Rae Jeong
Journal: Security and Communication Networks
 (2017)

---

## Abstract

To provide the integrity of outsourced data in the cloud storage services, many public auditing schemes which allow a user to check the integrity of the outsourced data have been proposed. Since most of the schemes are constructed on Public Key Infrastructure (PKI), they suffer from several concerns like management of certificates. To resolve the problems,certificateless public auditing schemes also have been studied in recent years. In this paper, we propose a certificateless public auditing scheme which has theconstant-time verification algorithm. Therefore, our scheme is more efficient than previous certificateless public auditing schemes. To prove the security of our certificateless public auditing scheme, we first define three formal security models and prove the security of our scheme under the three security models.


---

## Body

## 1. Introduction

Cloud storage is an essential service of cloud computing, which allows users to outsource their data to a cloud server. It is an easy and reliable way to handle a large amount of data due to the characteristics of cloud computing such as ubiquitous network access, location-independent resource pooling, and elasticity [1]. However, there exist challenging security threats with respect to the outsourced data. An untrusted server might discard the data to save a disk space or modify the data for personal gains. Therefore, the users need to be convinced that their data are stored in the cloud server without any loss or modification. That is, the cloud server should ensure the data integrity to the users.To check the integrity of the outsourced files efficiently, many solutions have been proposed in recent years. When the user wishes to check the integrity, the third-party auditor (TPA) executes auditing algorithms in place of the user without downloading the whole files. If the TPA performs auditing process without any secret values delegated from the user, we called itpublic auditing. Most of the public auditing schemes are based on Public Key Infrastructure (PKI) [2–10]. In traditional PKI, Certificate Authority (CA) issues the private/public keys for the users and certificates to bind the users with their public keys. These certificates are generated and managed by the CA. Even though PKI has been widely used in public key cryptography (PKC), it has some security issues related to the management of the certificates, such as revocation, distribution, storage, and the computational cost of the certificates verification as described in [11, 12].Identity-based public key cryptography was introduced to overcome the above issues of PKI by Shamir in [13]. In the identity-based public key cryptography, the users use identity as their public key (e.g., e-mail address) which is assumed to be publicly known, so there is no need to consider the management of the certificates [13–17]. A trusted third party called Key Generation Center (KGC) generates a master secret key and publishes a master public key corresponding to the master secret key. Then the KGC issues users’ private key corresponding to the identity (public keys) using the master secret key. Unfortunately, this approach causes a new inherent problem known as key escrow. Since the users’ private key is entirely generated by the KGC and it is not fully trusted, it can impersonate any valid user whenever it wants. The condition that the KGC is fully trusted has to be assumed to resolve the above inherent problem. The problem also should be considered for the identity-based public auditing schemes [18–20].Al-Riyami and Paterson proposedcertificateless cryptosystem that preserves the advantages of the identity-based public key cryptography and eliminates the vulnerability of it [21]. In other words, certificateless public key cryptography does not require certificates to authenticate the users’ public key and the strong assumption. In the certificateless public cryptography, the KGC cannot know the user’s full secret key unlike the ID-PKC, because the user’s full secret key is generated by combining a partial private key generated by the KGC with a secret value chosen by the user [21–23]. As the related works, many certificateless signature schemes are also proposed [24–27].In [28], the authors proposed the secure certificateless public auditing scheme based on a new certificateless signature scheme constructed by them. However, He et al. pointed out that the certificateless signature scheme cannot withstand the public key replacement attack, where the adversary can replace user’s public key with a manipulated public key [29]. They also proposed the certificateless public auditing scheme suitable for a cloud-assisted Wireless Body Area Networks (WBAN). Even though many authentication schemes are proposed, they are not suitable because they suffer from the certificate management and key escrow problem [30–35]. The certificateless public auditing scheme is constructed to withstand the attack and also ensures the integrity of stored data which is an important issue for the cloud-assisted WBAN, therefore the certificateless public auditing scheme is an essential technology to construct WBAN.


### 1.1. Our Contributions

(1)
We first design a certificateless public auditing (CL-PA) scheme which has the constant computation cost in verification. The previous certificateless public auditing schemes require the linearly increasing verification time with respect to the number of the challenged message blocks. (2)
We define the three formal security models which ensures the security against the public key replacement attack, malicious-but-passive-KGC attack, and proof-forgery. (3)
We show that our certificateless scheme is secure against existential forgery by proving the security under the models.The rest of paper is organized as follows. In Section2, we describe the formal security models and we review some preliminaries in Section 3. We construct our scheme and prove the securities in Section 4. We conclude the paper in Section 5.


## 1.1. Our Contributions

(1)
We first design a certificateless public auditing (CL-PA) scheme which has the constant computation cost in verification. The previous certificateless public auditing schemes require the linearly increasing verification time with respect to the number of the challenged message blocks. (2)
We define the three formal security models which ensures the security against the public key replacement attack, malicious-but-passive-KGC attack, and proof-forgery. (3)
We show that our certificateless scheme is secure against existential forgery by proving the security under the models.The rest of paper is organized as follows. In Section2, we describe the formal security models and we review some preliminaries in Section 3. We construct our scheme and prove the securities in Section 4. We conclude the paper in Section 5.


## 2. Preliminaries

### 2.1. Bilinear Group

Let groupsG and GT be multiplicative cyclic groups with prime order q. A function e:G×G→GT is a bilinear map, if it satisfies the following:(1)
We havee(ga,gb)=e(g,g)ab for all g∈G, a,b∈Zq∗.(2)
Ifg is a generator of group G,e(g,g) is a generator of group GT.(3)
It is easy to computee(ga,gb) for all g∈G.


### 2.2. Complexity Assumptions

Computational Diffie-Hellman (CDH) Assumption. Given a tuple g,ga,gb∈G, an algorithm A tries to compute gab∈G. We assume that there is no algorithm A with a nonnegligible probability ϵ such that (1)Pr⁡Ag,ga,gb=gab≥ε,where the probability is over the random choice of g∈G, the random choice of a,b∈Zq∗, and the random bits of A.Divisible Computational Diffie-Hellman (DCDH) Assumption [36]. Given a tuple g,ga,gb∈G, an algorithm A tries to compute ga-1b∈G. We assume that there is no algorithm A with a nonnegligible probability ϵ such that (2)Pr⁡Ag,ga,gb=ga-1b≥ε,where the probability is over the random choice of g∈G, the random choice of a,b∈Zq∗, and the random bits of A.


## 2.1. Bilinear Group

Let groupsG and GT be multiplicative cyclic groups with prime order q. A function e:G×G→GT is a bilinear map, if it satisfies the following:(1)
We havee(ga,gb)=e(g,g)ab for all g∈G, a,b∈Zq∗.(2)
Ifg is a generator of group G,e(g,g) is a generator of group GT.(3)
It is easy to computee(ga,gb) for all g∈G.


## 2.2. Complexity Assumptions

Computational Diffie-Hellman (CDH) Assumption. Given a tuple g,ga,gb∈G, an algorithm A tries to compute gab∈G. We assume that there is no algorithm A with a nonnegligible probability ϵ such that (1)Pr⁡Ag,ga,gb=gab≥ε,where the probability is over the random choice of g∈G, the random choice of a,b∈Zq∗, and the random bits of A.Divisible Computational Diffie-Hellman (DCDH) Assumption [36]. Given a tuple g,ga,gb∈G, an algorithm A tries to compute ga-1b∈G. We assume that there is no algorithm A with a nonnegligible probability ϵ such that (2)Pr⁡Ag,ga,gb=ga-1b≥ε,where the probability is over the random choice of g∈G, the random choice of a,b∈Zq∗, and the random bits of A.


## 3. Models

### 3.1. System Model

We consider a system model that has four entities, KGC (Key Generation Center), a user, a cloud server, and a third-party auditor (TPA) as shown Figure1. The KGC is responsible for the generation of a master key and a set of public keys for the system and issuing the partial private key for an identity (ID). Unlike the PKG in identity-based system, the KGC cannot issue the user’s full secret key that will be used in the system. The full secret key is generated by combining the partial private key with some random secret values chosen from the user. With this key, the user generates authenticated tags for the file blocks and uploads them to the cloud server. When the user wishes to check the integrity of the stored files, TPA performs it on behalf of the user. For checking the integrity of the stored files, TPA sends a challenge message to the cloud server, and then the server responds with the proof corresponding to the challenge message. TPA is able to check the integrity of them by verifying the validity of the received proof.Figure 1
System model for our CL-PA protocol.We define the algorithms for our certificateless public auditing scheme as follows:(i)
Setup takes a security parameter and returns a master key (MK) and a public parameter (PP).(ii)
Partial-Private-Key-Extract takes an identity (ID), the master key (MK), and the public parameter (PP). It outputs a partial private key (ppk) for the identity (ID).(iii)
KeyGen takes an identity (ID), the public parameter (PP), and the partial private key (psk). It outputs a set of public keys (PK) and a secret key (sk) of the identity (ID).(iv)
TagGen takes as an input the public parameter (PP), a secret key (sk) of a user, and a file F=(m1,…,mn), where n is the number of the file blocks. It outputs tags {ti}1≤i≤n for the file blocks.(v)
Challenge takes as an input the public parameters pp and returns a challenge message C.(vi)
Prove takes as an input the public parameter (PP) and the challenge message C and the pairs of message and tag {mi,ti}1≤i≤n. It outputs a proof (Prf) for the challenge message C.(vii)
Verify takes as an input the public parameter (PP), the set of public keys (PK), the challenge message C, and the proof (Prf). It outputsAccept orReject.


### 3.2. Security Models

We assume that three types of adversaries in our certificateless public auditing scheme, that is, Type I adversaryA1, Type II adversary A2, and Type III adversary A3, and define the adversaries as follows:(i)
Type I adversaryA1 cannot access the master key, but he can replace user’s public key with a manipulated public key and generate a forged pair of message and tag.(ii)
Type II adversaryA2, which represents a malicious KGC, can access the master key and generate a forged pair of message and tag, but he cannot replace user’s public key.(iii)
Type III adversaryA3, which represents a malicious server, can forge a proof for the challenge message without knowing any secret values.Type I adversary and Type II adversary aim to forge the pair of message and tag and are classed as the normal, strong, and super adversaries (ordered by the capability of the adversaries). If the scheme is secure against the super adversary, it is also secure against the normal and strong adversaries. Therefore, we just consider the super Type I adversary and the super Type II adversary in Game I and Game II, respectively. We define three security models using the following games between a challenger and the defined adversaries.Game I. If Type I adversary A1 cannot forge a pair of message and tag, then we consider that a certificateless public auditing scheme is secure against a tag-forgery by the public key replacement attack. It is defined using the following game between a challenger C and Type I adversary A1:(1)
Type I adversary outputs an identityIDtg where it wishes to be forged.(2)
The challengerC runs algorithm Setup to generate a public parameter (PP) and the master key (MK) and sends PP to Type I adversary A1.(3)
Type I adversaryA1 is allowed to access the hash oracles, KeyGen, Partial-Private-Key-Extract, Public-Key-Replacement, Secret-Value-Extract, and TagGen oracle, adaptively. For KeyGen oracle, Type I adversary A1 sends IDu to the challenger C, and then the public key pku is returned. For Partial-Private-Key-Extract oracle, Type I adversary A1 sends IDu to the challenger C, and then the partial private key psku is returned. For Public-Key-Replacement oracle, Type I adversary A1 sends (IDu,pku′) to the challenger C. For Secret-Value-Extract oracle, Type I adversary A1 sends IDu to the challenger C, and then the secret value svIDu is returned. For TagGen oracle, Type I adversary A1 sends (IDu,idi,mi), where idi is the block identifier, to the challenger C. The challenger C responds with a pair of message and tag (mi,ti), where ti = TagGen(sku,IDu,idi,mi).(4)
Finally, Type I adversaryA1 outputs a forged pair of message and tag (idi,m∗,t∗) for an identity IDtg.If the pair(idi,m∗,t∗) is valid pair of message and tag and m∗ has not queried TagGen oracle, then Type I adversary A1 wins the game.Definition 1.
Type I adversaryA1 (t,qh,qk,qppk,qpkr,qsv,qt,ε)-breaks a certificateless public auditing scheme, if A1 runs in time at most t, makes at most qh hash queries, qk KeyGen queries, qppk Partial-Private-Key-Extract queries, qpkr Public-Key-Replacement queries, qsv Secret-Value-Extract queries, and qt TagGen queries, and wins the game with the probability ε. A certificateless public auditing scheme is secure against a tag-forgery by the public key replacement attack, if there is no tag-forger which (t,qh,qk,qppk,qpkr,qsv,qt,ε)-breaks the scheme with a nonnegligible probability ε.
Game II. If Type II adversary A2 cannot forge a pair of message and tag, then we consider that a certificateless public auditing scheme is secure against a tag-forgery by the malicious-but-passive-KGC attack. It is defined using the following game between a challenger C and Type II adversary A2.(1)
Type II adversary outputs an identityIDtg where it wishes to be forged.(2)
The challengerC runs algorithm Setup to generate a public parameter (PP) and the master key (MK) and sends “PP and MK” to Type II adversary A2.(3)
Type II adversaryA2 is allowed to access the hash oracles, KeyGen, Partial-Private-Key-Extract, Secret-Value-Extract, and TagGen oracle, adaptively. For KeyGen oracle, Type II adversary A2 sends IDu to the challenger C, and then the public key pku is returned. For Partial-Private-Key-Extract oracle, Type II adversary A2 sends IDu to the challenger C, and then the partial private key psku is returned. For Secret-Value-Extract oracle, Type II adversary A2 sends IDu to the challenger C, and then the secret value svIDu is returned. For TagGen oracle, Type II adversary A2 sends (IDu,idi,mi), where idi is the block identifier, to the challenger C. The challenger C responds with a pair of message and tag (mi,ti), where ti = TagGen(sku,IDu,idi,mi).(4)
Finally, Type II adversaryA2 outputs a forged pair of message and tag (idi,m∗,t∗) for an identity IDtg.
If the pair(idi,m∗,t∗) is valid pair of message and tag and m∗ has not queried TagGen oracle, then Type II adversary A2 wins the game.Definition 2.
Type II adversaryA2 (t,qh,qk,qppk,qsv,qt,ε)-breaks a certificateless public auditing scheme, if A2 runs in time at most t, makes at most qh hash queries, qk KeyGen queries, qppk Partial-Private-Key-Extract queries, qsv Secret-Value-Extractqueries, and qt TagGen queries, and wins the game with the probability ε. A certificateless public auditing scheme is secure against a tag-forgery by the malicious-but-passive-KGC attack, if there is no tag-forger which (t,qh,qk,qppk,qsv,qt,ε)-breaks the scheme with a nonnegligible probability ε.
Game III. Type III adversary A3 cannot generate a valid proof for the blocks modified or deleted by Type III adversary A3, and then we say that a public auditing scheme satisfies a proof-unforgeability (soundness). It is defined using the following game between a challenger C and Type III adversary A3:(1)
The challengerC runs algorithm Setup to generate a public parameter (PP) and the master key (MK) and sends PP to Type III adversary A3.(2)
Type III adversaryA3 is allowed to access the hash oracles, KeyGen, Partial-Private-Key-Extract, Secret-Value-Extract, and TagGen oracle, adaptively. For KeyGen oracle, Type III adversary A3 sends IDu to the challenger C, and then the public key pku is returned. For Partial-Private-Key-Extract oracle, Type III adversary A3 sends IDu to the challenger C, and then the partial private key psku is returned. For Secret-Value-Extract oracle, Type III adversary A3 sends IDu to the challenger C, and then the secret value svIDu is returned. For TagGen oracle, Type III adversary A3 sends (IDu,idi,mi), where idi is the block identifier, to the challenger C. The challenger C responds with a pair of message and tag (mi,ti), where ti = TagGen(sku,IDu,idi,mi).(3)
The challengerC generates the challenge message C = Challenge(PP) and sends it to Type III adversary A3.(4)
Finally, Type III adversaryA3 outputs a forged proof Prf∗.
If the equation Verify(Prf∗)=Accept holds and the challenge message C includes the index which is not queried in TagGen queries, then Type III adversary A3 wins the game.Definition 3.
Type III adversaryA3 (t,qh,qk,qppk,qsv,qt,ε)-breaks a certificateless public auditing scheme, if A3 runs in time at most t, makes at most qh hash queries, qk KeyGen queries, qppk Partial-Private-Key-Extract queries, qsv Secret-Value-Extract queries, and qt TagGen queries, and wins the game with the probability ε. A certificateless public auditing scheme is proof-unforgeable (sound), if there is no proof-forger which (t,qh,qk,qppk,qsv,qt,ε)-breaks the scheme with a nonnegligible probability ε.


## 3.1. System Model

We consider a system model that has four entities, KGC (Key Generation Center), a user, a cloud server, and a third-party auditor (TPA) as shown Figure1. The KGC is responsible for the generation of a master key and a set of public keys for the system and issuing the partial private key for an identity (ID). Unlike the PKG in identity-based system, the KGC cannot issue the user’s full secret key that will be used in the system. The full secret key is generated by combining the partial private key with some random secret values chosen from the user. With this key, the user generates authenticated tags for the file blocks and uploads them to the cloud server. When the user wishes to check the integrity of the stored files, TPA performs it on behalf of the user. For checking the integrity of the stored files, TPA sends a challenge message to the cloud server, and then the server responds with the proof corresponding to the challenge message. TPA is able to check the integrity of them by verifying the validity of the received proof.Figure 1
System model for our CL-PA protocol.We define the algorithms for our certificateless public auditing scheme as follows:(i)
Setup takes a security parameter and returns a master key (MK) and a public parameter (PP).(ii)
Partial-Private-Key-Extract takes an identity (ID), the master key (MK), and the public parameter (PP). It outputs a partial private key (ppk) for the identity (ID).(iii)
KeyGen takes an identity (ID), the public parameter (PP), and the partial private key (psk). It outputs a set of public keys (PK) and a secret key (sk) of the identity (ID).(iv)
TagGen takes as an input the public parameter (PP), a secret key (sk) of a user, and a file F=(m1,…,mn), where n is the number of the file blocks. It outputs tags {ti}1≤i≤n for the file blocks.(v)
Challenge takes as an input the public parameters pp and returns a challenge message C.(vi)
Prove takes as an input the public parameter (PP) and the challenge message C and the pairs of message and tag {mi,ti}1≤i≤n. It outputs a proof (Prf) for the challenge message C.(vii)
Verify takes as an input the public parameter (PP), the set of public keys (PK), the challenge message C, and the proof (Prf). It outputsAccept orReject.


## 3.2. Security Models

We assume that three types of adversaries in our certificateless public auditing scheme, that is, Type I adversaryA1, Type II adversary A2, and Type III adversary A3, and define the adversaries as follows:(i)
Type I adversaryA1 cannot access the master key, but he can replace user’s public key with a manipulated public key and generate a forged pair of message and tag.(ii)
Type II adversaryA2, which represents a malicious KGC, can access the master key and generate a forged pair of message and tag, but he cannot replace user’s public key.(iii)
Type III adversaryA3, which represents a malicious server, can forge a proof for the challenge message without knowing any secret values.Type I adversary and Type II adversary aim to forge the pair of message and tag and are classed as the normal, strong, and super adversaries (ordered by the capability of the adversaries). If the scheme is secure against the super adversary, it is also secure against the normal and strong adversaries. Therefore, we just consider the super Type I adversary and the super Type II adversary in Game I and Game II, respectively. We define three security models using the following games between a challenger and the defined adversaries.Game I. If Type I adversary A1 cannot forge a pair of message and tag, then we consider that a certificateless public auditing scheme is secure against a tag-forgery by the public key replacement attack. It is defined using the following game between a challenger C and Type I adversary A1:(1)
Type I adversary outputs an identityIDtg where it wishes to be forged.(2)
The challengerC runs algorithm Setup to generate a public parameter (PP) and the master key (MK) and sends PP to Type I adversary A1.(3)
Type I adversaryA1 is allowed to access the hash oracles, KeyGen, Partial-Private-Key-Extract, Public-Key-Replacement, Secret-Value-Extract, and TagGen oracle, adaptively. For KeyGen oracle, Type I adversary A1 sends IDu to the challenger C, and then the public key pku is returned. For Partial-Private-Key-Extract oracle, Type I adversary A1 sends IDu to the challenger C, and then the partial private key psku is returned. For Public-Key-Replacement oracle, Type I adversary A1 sends (IDu,pku′) to the challenger C. For Secret-Value-Extract oracle, Type I adversary A1 sends IDu to the challenger C, and then the secret value svIDu is returned. For TagGen oracle, Type I adversary A1 sends (IDu,idi,mi), where idi is the block identifier, to the challenger C. The challenger C responds with a pair of message and tag (mi,ti), where ti = TagGen(sku,IDu,idi,mi).(4)
Finally, Type I adversaryA1 outputs a forged pair of message and tag (idi,m∗,t∗) for an identity IDtg.If the pair(idi,m∗,t∗) is valid pair of message and tag and m∗ has not queried TagGen oracle, then Type I adversary A1 wins the game.Definition 1.
Type I adversaryA1 (t,qh,qk,qppk,qpkr,qsv,qt,ε)-breaks a certificateless public auditing scheme, if A1 runs in time at most t, makes at most qh hash queries, qk KeyGen queries, qppk Partial-Private-Key-Extract queries, qpkr Public-Key-Replacement queries, qsv Secret-Value-Extract queries, and qt TagGen queries, and wins the game with the probability ε. A certificateless public auditing scheme is secure against a tag-forgery by the public key replacement attack, if there is no tag-forger which (t,qh,qk,qppk,qpkr,qsv,qt,ε)-breaks the scheme with a nonnegligible probability ε.
Game II. If Type II adversary A2 cannot forge a pair of message and tag, then we consider that a certificateless public auditing scheme is secure against a tag-forgery by the malicious-but-passive-KGC attack. It is defined using the following game between a challenger C and Type II adversary A2.(1)
Type II adversary outputs an identityIDtg where it wishes to be forged.(2)
The challengerC runs algorithm Setup to generate a public parameter (PP) and the master key (MK) and sends “PP and MK” to Type II adversary A2.(3)
Type II adversaryA2 is allowed to access the hash oracles, KeyGen, Partial-Private-Key-Extract, Secret-Value-Extract, and TagGen oracle, adaptively. For KeyGen oracle, Type II adversary A2 sends IDu to the challenger C, and then the public key pku is returned. For Partial-Private-Key-Extract oracle, Type II adversary A2 sends IDu to the challenger C, and then the partial private key psku is returned. For Secret-Value-Extract oracle, Type II adversary A2 sends IDu to the challenger C, and then the secret value svIDu is returned. For TagGen oracle, Type II adversary A2 sends (IDu,idi,mi), where idi is the block identifier, to the challenger C. The challenger C responds with a pair of message and tag (mi,ti), where ti = TagGen(sku,IDu,idi,mi).(4)
Finally, Type II adversaryA2 outputs a forged pair of message and tag (idi,m∗,t∗) for an identity IDtg.
If the pair(idi,m∗,t∗) is valid pair of message and tag and m∗ has not queried TagGen oracle, then Type II adversary A2 wins the game.Definition 2.
Type II adversaryA2 (t,qh,qk,qppk,qsv,qt,ε)-breaks a certificateless public auditing scheme, if A2 runs in time at most t, makes at most qh hash queries, qk KeyGen queries, qppk Partial-Private-Key-Extract queries, qsv Secret-Value-Extractqueries, and qt TagGen queries, and wins the game with the probability ε. A certificateless public auditing scheme is secure against a tag-forgery by the malicious-but-passive-KGC attack, if there is no tag-forger which (t,qh,qk,qppk,qsv,qt,ε)-breaks the scheme with a nonnegligible probability ε.
Game III. Type III adversary A3 cannot generate a valid proof for the blocks modified or deleted by Type III adversary A3, and then we say that a public auditing scheme satisfies a proof-unforgeability (soundness). It is defined using the following game between a challenger C and Type III adversary A3:(1)
The challengerC runs algorithm Setup to generate a public parameter (PP) and the master key (MK) and sends PP to Type III adversary A3.(2)
Type III adversaryA3 is allowed to access the hash oracles, KeyGen, Partial-Private-Key-Extract, Secret-Value-Extract, and TagGen oracle, adaptively. For KeyGen oracle, Type III adversary A3 sends IDu to the challenger C, and then the public key pku is returned. For Partial-Private-Key-Extract oracle, Type III adversary A3 sends IDu to the challenger C, and then the partial private key psku is returned. For Secret-Value-Extract oracle, Type III adversary A3 sends IDu to the challenger C, and then the secret value svIDu is returned. For TagGen oracle, Type III adversary A3 sends (IDu,idi,mi), where idi is the block identifier, to the challenger C. The challenger C responds with a pair of message and tag (mi,ti), where ti = TagGen(sku,IDu,idi,mi).(3)
The challengerC generates the challenge message C = Challenge(PP) and sends it to Type III adversary A3.(4)
Finally, Type III adversaryA3 outputs a forged proof Prf∗.
If the equation Verify(Prf∗)=Accept holds and the challenge message C includes the index which is not queried in TagGen queries, then Type III adversary A3 wins the game.Definition 3.
Type III adversaryA3 (t,qh,qk,qppk,qsv,qt,ε)-breaks a certificateless public auditing scheme, if A3 runs in time at most t, makes at most qh hash queries, qk KeyGen queries, qppk Partial-Private-Key-Extract queries, qsv Secret-Value-Extract queries, and qt TagGen queries, and wins the game with the probability ε. A certificateless public auditing scheme is proof-unforgeable (sound), if there is no proof-forger which (t,qh,qk,qppk,qsv,qt,ε)-breaks the scheme with a nonnegligible probability ε.


## 4. Our Certificateless Public Auditing (CL-PA) Scheme

In this section, we propose a provably secure certificateless public auditing scheme. Our scheme consists of the seven algorithms, SetUp, Partial-Private-Key-Extract, KeyGen, TagGen, Challenge, Prove, and Verify. The details of the algorithms are as follows.SetUp: let G and GT be multiplicative cyclic groups of prime order q and e:G×G→GT be a bilinear map. Let g,g1, and g2 be generators of G. H(·):{0,1}∗→Zq∗, H~(·):{0,1}∗→Zq∗, and h(·):{0,1}∗→G are collision resistant hash functions. KGC randomly chooses α,x←Zq∗ and computes {g2αj}0≤j≤s+1 and X1=gx as system parameters. A set of master keys is MK=(α,x) and the public parameters are PP=(G,GT,e,H,h,g,g1,g2,X1,gα,{g2αj}0≤j≤s+1).Partial-Private-Key-Extract: for each identity IDu∈{0,1}∗, KGC picks the random number r←Zq∗ and computes R1=gr, σ~=r+xHIDu,R1mod⁡q, and R2~=gασ~. KGC sends psku=(R1,R2~,σ~) to the user U as the partial private keys for the identity IDu.KeyGen: given the public parameters and the partial private keys, the user U generates his/her secret keys and public keys. The user U chooses w,k←Zq∗ and computes σ=k+σ~=k+r+xH(IDu,R1), R0=gk, R2=R2~·(gα)k, R3=(R1·R0)w, and X2=X1w. The user sets sku=(σ,w) as a set of secret keys and pku=(R0,R1,R2,R3,X2) as a set of public keys.TagGen: let F={mi0,…,mi(s-1)}1≤i≤n be a file. The user computes an authenticated tag ti for each block mi as (3)ti=g1wHi~·hi·∏j=0s-1g2mijαj+2σ=g1wHi~·hi·g2fβi→ασ,where idi is block identifier of mi, fname is the file name, Hi~=H~(IDu,pku,idi), hi=h(fname,idi), βi→=(0,0,mi0,mi1,…,mi(s-1)), and fβi→ is a polynomial with a coefficient vector βi→. Then the user uploads the file F={mi}1≤i≤n with the corresponding authenticated tags {ti}1≤i≤n to the server. The validity of the pair of message and tag could be checked by the equation(4)eti,g=eg1Hi~,R3·X2HIDu,R1·ehi·g2fβi→α,R0·R1·X1HIDu,R1.Challenge: to check the integrity of F, TPA randomly chooses random number rc←Zq∗ and d-elements subset D of [1,n]. Then, TPA sends the challenge messages (rc,D) to the server.Prove: when the server receives the challenge message (rc,D), the server first computes pi=rcimod⁡q for all i∈D and y=fA→(rc)mod⁡q, where A→=(0,0,∑i∈D‍pimi0,…,∑i∈K‍pimi(s-1)).The server computes the quotient polynomialfω→(x)=(fA→(x)-fA→(rc))/(x-rc), where ω→=(ω0,ω1,…,ωs) is the coefficient vector resulting in the quotient polynomial, and ψ=∏j=0s(g2αj)wj=g2fω→(α). Finally, the server computes ρ=∏i∈Dhipi and T=∏i∈Dtipi and then sends the proof (T,ψ,y,ρ) to TPA.Verify: upon receiving the proof (T,ψ,y,ρ), TPA checks the validity of the proof. TPA computes π=∑i∈D‍H~(IDu,pku,idi)pi and checks the equation(5)eT,g=eg1π,gwσ·eρ·g2y,gσ·eψ,R2·gσ·-rc,where gwσ=R3·X2H(IDu,R1) and gσ=R0·R1·X1H(IDu,R1). If the equation holds, TPA outputsAccept; otherwise it outputsReject.The correctness of our scheme can be proved as follows:(6)eg1π,gwσ·eρ·g2y,gσ·eψ,R2·gσ·-rc=e∏i∈Dg1Hi~pi,gwσ·e∏i∈Dhipi,gσ·eg2y,gσ·eψ,gασ·gσ·-rc=e∏i∈Dg1wHi~pi·hipi,gσ·eg2y,gσ·eg2fω→α,gασ·gσ·-rc=e∏i∈Dg1wHi~pi·hipi,gσ·eg2fA→rc,gσ·eg2fω→α·α-rc,gσ=e∏i∈Dg1wHi~pi·hipi,gσ·eg2fA→rc,gσ·eg2fA→α-fA→rc,gσ=e∏i∈Dg1wHi~pi·hipi,gσ·eg2fA→α,gσ=e∏i∈Dg1wHi~pi·hipi·g2fβi→α·pi,gσ=e∏i∈Dg1w·Hi~·hi·g2fβi→ασpi,g=e∏i∈Dtipi,g=eT,g.


### 4.1. Security Analyses

In this section, we analyze the security of our certificateless public auditing scheme. If the scheme is secure against the tag-forgery by Type I adversary and Type II adversary and the proof-forgery by Type III adversary under adaptive chosen message attacks, then we consider that the scheme is secure againstexistential forgery.Theorem 4.
The proposed certificateless public auditing scheme is secure against the tag-forgery by Type I adversary under chosen message attacks in the random oracle model, if the CDH assumption holds inG.Proof of Theorem4.
Suppose Type I adversaryA1 is the forger that could break the scheme by generating a valid pair of message and tag under user’s secret key with a probability ε. Then we can construct an algorithm B that solves the CDH problem on G.
Given an instance(g,ga,gb)∈G of the CDH problem, the algorithm B simulates the challenger and interacts with the forger A1 in Game I.(1)
The forgerA1 outputs an identity IDtg where it wishes to be forged.(2)
The algorithmB chooses random numbers α,z1,z2←Zq∗ and computes {g2αj}0≤j≤s+1, where g2=gz2. The algorithm B sets X1=ga and g1=gz1 and sends PP to the forger A1.(3)
ForKeyGenoracle, at any time the forger A1 can query the KeyGen oracle for an identity IDu. The algorithm B stores Tab1=(IDu,ϵu,ru,σu~,σu,wu,ku,Ru,2~,pku), where Tab1 is initially empty. When the forger A1 queries IDu, the algorithm B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B chooses random number ϵu,σu~,wu,ku←Zq∗ and calculates σu=σu~+ku, Ru,0=gku, Ru,1=gσu~/(ga)ϵu, Ru,2~=gασu~, Ru,2=gα(σu~+ku), Ru,3=(Ru,1·Ru,0)wu, and Xu,2=(ga)wu. The algorithm B sends pku=(Ru,0,Ru,1,Ru,2,Ru,3,Xu,2) to the forger A1 as the set of public keys for the identity IDu and updates Tab1.(b)
IfIDu=IDtg, the algorithm B chooses random number ϵu,ru,wu,ku←Zq∗ and calculates Ru,0=gku, Ru,1=gru, Ru,2~=(Ru,1·gaϵu)α, Ru,2=Ru,1·gaϵuα·gαku, Ru,3=(Ru,1·Ru,0)wu, and Xu,2=gawu. The algorithm B sends pku=(Ru,0,Ru,1,Ru,2,Ru,3,Xu,2) to the forger A1 as the set of public keys for the identity IDu and updates Tab1.(4)
The algorithmB simulates the hash oracles as follows:For Hash OracleH. At any time the forger A1 can query the random oracle H for (IDu,Ru,1). To respond to the hash queries, the algorithm B retrieves the tuple which includes the queried identity IDu in Tab1. Then the algorithm B returns H(IDu,Ru,1)=ϵu in Tab1 to the forger A1.For Hash OracleH~. At any time the forger A1 can query the random oracle H~ for (IDu,pku,idi). To respond to the hash queries, the algorithm B maintains a table Tab2=(IDu,pku,idi,ξu,i), where Tab2 is initially empty. When the forger A1 queries (IDu,pku,idi), the algorithm B responds as follows:
(a)
IfIDu,pku,idi∉Tab2, the algorithm B picks a random number ξu,i∈Zq∗ and sets the hash value Hu,i~=ξu,i. Then the algorithm B stores the tuple Tab2=(IDu,pku,idi,ξu,i) and responds with H(pku,idi)=ξu,i to the forger A1.(b)
If(IDu,pku,idi)∈Tab2, the algorithm B returns H~(pku,idi)=ξu,i in Tab2 to the forger A1.For Hash Oracleh. At any time the forger A1 can query the random oracle h for (fname,idi). To respond to the hash queries, the algorithm B maintains a table Tab3=(fname,idi,δi,ci,hi), where Tab3 is initially empty. When the forger A1 queries (fname,idi), the algorithm B responds as follows:
(a)
If(fname,idi)∉Tab3, the algorithm B flips a random coin ci∈{0,1} with a probability Pr⁡[ci=0]=1/(qt+1), where qt is the maximum number of TagGen queries. The algorithm B picks a random number δi∈Zq∗ and computes hi=(gb)(1-ci)·gδi. Then the algorithm B stores the tuple Tab3=(fname,idi,δi,ci,hi) and returns h(fname,idi)=hi to the forger A1.(b)
If(fname,idi)∈Tab3, the algorithm B responds with h(fname,idi)=hi in Tab3.(5)
The algorithmB simulates Partial-Private-Key-Extract oracle, Public-Key-Replacement oracle, Secret-Value-Extract oracle, and TagGen oracle as follows.ForPartial-Private-Key-ExtractOracle. At any time the forger A1 can request a partial private key for IDu to the oracle. When the forger A1 queries IDu to the oracle, the algorithm B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B retrieves the tuple which contains the queried IDu in Tab1 and returns psku=(Ru,1,Ru,2~,σu) to the forger A1.(b)
IfIDu=IDtg, the algorithm B reports failure.ForPublic-Key-ReplacementOracle. At any time the forger A1 can replace a set of public keys for IDu. Upon receiving a public key replacement query (IDu,pku′), A1 retrieves the tuple which contains IDu in Tab1 and replaces pku with pku′.ForSecret-Value-ExtractOracle. At any time the forger A1 is able to request a secret value for IDu to the oracle. When the forger A1 queries IDu to the oracle, A1 retrieves the tuple which contains IDu in Tab1 and responds with (wu,ku).ForTagGenOracle. At any time the forger A1 can query the oracle for the tuple (IDu,idi,mi). The algorithm B stores Tab4=(IDu,idi,mi,ϵu,ru,wu,ku,σu,ξu,i,δi,hi,ci,ti), where Tab4 is initially empty. When the forger A1 queries IDu, the algorithm B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B retrieves the tuple which is corresponding to the queried tuple (IDu,idi) and computes the tag ti for the queried message mi, where ti=(g1wuξu,i·hi·g2fβi→(α))σu. The algorithm B responds with ti and updates Tab4.(b)
IfIDu=IDtg, the algorithm B retrieves the tuple which is corresponding to the queried tuple (IDu,idi). If ci=1, the algorithm B computes the tag ti for the queried message mi, where ti=g1wuξu,i·hi·g2fβi→αku+ru·gawuz1ξu,i+δi+fβi→αϵu. The algorithm B responds with ti and updates Tab4. Otherwise, the algorithm B reports failure.(6)
Finally, the forgerA1 outputs the forged pair of message and tag (ID∗,idi,mi∗,ti∗) such that no TagGen query was issued for mi∗. If idi∈Tab3, ci=0, and ID∗=IDtg, ti∗ satisfies the following equation: (7)eti∗,g=eg1Hu,i~,Ru,3·Xu,2Hu·ehi·g2fβi∗→α,Ru,0·Ru,1·X1Hu.By using the oracle-replay technique [37] on hash function H, the algorithm B can obtain another forged tag ti∗′ for the same message mi∗. The forged tag ti∗′ also satisfies the following equation: (8)eti∗′,g=eg1Hu,i~,Ru,3·Xu,2Hu′·ehi·g2fβi∗→α,Ru,0·Ru,1·X1Hu′.With the above equations, the algorithm B could compute(9)eti∗ti∗′,g=eg1Hu,i~,Xu,2Hu-Hu′·ehi·g2fβi∗→α,X1Hu-Hu′. From the right-hand-side of the above equation, the algorithm B could get(10)eg1Hu,i~,Xu,2Hu-Hu′·ehi·g2fβi∗→α,X1Hu-Hu′=egz1Hu,i~,gawuHu-Hu′·egbδi·g2fβi∗→α,gaHu-Hu′=egawuz1Hu,i~Hu-Hu′,g·egbδi·gz2fβi∗→α,gaHu-Hu′=egawuz1Hu,i~Hu-Hu′,g·egabδiHu-Hu′,g·egaHu-Hu′z2fβi∗→α,g=egawuz1Hu,i~+z2fβi∗→αHu-Hu′·gabδiHu-Hu′,g.Then the algorithm B outputs (11)gab=ti∗/ti∗′gaC1/δiHu-Hu′,where C=(wuz1Hu,i~+z2fβi∗→(α))(Hu-Hu′).
From now on, we define three events related to the success probability ofB and analyze it as follows:(i)
E1: the algorithm B does not abort in the Partial-Private-Key-Extract queries and TagGen queries.(ii)
E2: the forger A1 outputs a valid pair of message and tag (ID∗,idi,mi∗,ti∗), which has not been queried before.(iii)
E3: event E2 occurs and ci=0 for the tuple containing idi on Tab3.In the case that the all events happen, the algorithm B can solve the CDH problem. Thus, the probability of success is Pr⁡[E1∧E3], and we can compute it as (12)Pr⁡E1∧E3=Pr⁡E1·Pr⁡E2∣E1·Pr⁡E3∣E1∧E2. We analyze the lower bounds of Pr⁡[E1], Pr⁡[E2∣E1], and Pr⁡[E3∣E1∧E2] in the following claims.
Claim 1. The probability Pr⁡[E1] that the algorithm B does not abort in the Partial-Private-Key-Extract queries and the TagGen queries by the forger A1 is at least 1/e2.
Proof of Claim 1. We assume that the forger A1 does not query for the same index twice. At first, in the Partial-Private-Key-Extract oracle the algorithm B cannot respond to the forger A1’s query, if IDu=IDtg. This probability is equal to 1/qk, where qk is the number of KeyGen queries. Therefore, the probability that the algorithm B does not abort is 1-1/qk for each Partial-Private-Key-Extract query. Since the Partial-Private-Key-Extract queries are issued at most qk times, the probability that the algorithm B does not abort is at least (1-1/qk)qk≥1/e. In the TagGen oracle, the algorithm B only aborts if ci=0, where ci is the random value with the probability Pr⁡[ci=0]=1/(qt+1) corresponding to the TagGen query idi in Tab3. By the probability of ci, the probability that the algorithm B does not abort is 1-1/(qt+1). Similarly, the probability that the algorithm B does not abort in the TagGen oracle is at least (1-1/(qt+1))qt≥1/e. Thus, the probability Pr⁡[E1] that the algorithm B does not abort in the forger A1’s Partial-Private-Key-Extract queries and TagGen queries is at least (1-1/qk)qk·(1-1/(qt+1))qt≥1/e2.
Claim 2. The probability Pr⁡[E2∣E1] that the forger A1 outputs a valid pair of message and tag under the condition that the event E1 has occurred is at least ε.
Proof of Claim 2. When the event E1 has occurred, the probability Pr⁡[E2∣E1] depends on the information gathered by the forger A1. The views of A1 in the simulation and the real game are identical as follows:(i)
The distribution of PK given to the forgerA1 in the simulation is identical with the distribution of PK given to the forger A1 in the real game.(ii)
The distribution of the hash values of the hash function in the simulation is identical with the distributions of the hash values of the hash function in the real game.(iii)
The distribution of the responses to the TagGen oracle in the simulation is identical with the distribution of the responses to the TagGen oracle in the real game under the conditional probability.
Thus, the forgerA1 will generate a valid pair of message and tag with a probability at least ϵ.
Claim 3. The probability Pr[E3∣E1∧E2] that the algorithm B does not abort after the forger A1 outputs a valid pair of message and tag is at least 1/(qt+1).
Proof of Claim 3. When the events E1 and E2 have occurred, the algorithm B will abort only in the case that ci=0 for the tuple containing i corresponding to a forged pair of message and tag (idi,mi∗,ti∗) in Tab1. Since the value ci is randomly chosen with the probability Pr[ci=0]=1/(qt+1), the probability Pr[E3∣E1∧E2] is at least 1/(qt+1).
With the above claims, the success probability ofB is ε/(e2·(qt+1)). Thus we can conclude that if the CDH assumption holds in G, there exists no algorithm which breaks the tag-unforgeability of our scheme by the public key replacement attack with a nonnegligible probability.Theorem 5.
The proposed certificateless public auditing scheme is secure against the tag-forgery by Type II adversary under chosen message attacks in the random oracle model, if the CDH assumption holds inG.Proof of Theorem5.
Suppose Type II adversaryA2 is the tag-forger that could break the scheme by generating a valid pair of message and tag under user’s secret key with a probability ε. Then we can construct an algorithm B that solves the CDH problem on G.
Given an instance(g,ga,gb)∈G of the CDH problem, the algorithm B simulates the challenger and interacts with the forger A2 in Game II.(1)
The forgerA2 outputs an identity IDtg where it wishes to be forged.(2)
The algorithmB chooses random numbers α,x,z1,z2←Zq∗ and computes {g2αj}0≤j≤s+1, where g2=gz2. The algorithm B sets X1=gx and g1=gz1 and sends “PP and MK” to the forger A2.(3)
For KeyGen oracle, at any time the forger A2 can query the KeyGen oracle for an identity IDu. The algorithm B stores Tab1=(IDu,ϵu,ru,σu~,σu,wu,ku,Ru,2~,pku), where Tab1 is initially empty. When the forger A2 queries IDu, the algorithm B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B chooses random number ϵu,ru,wu,ku←Zq∗ and calculates Ru,0=gku, Ru,1=gru, σu~=ru+xϵu, σu=ku+ru+ϵu, Ru,2~=gασu~, Ru,2=gασu, Ru,3=(Ru,1·Ru,0)wu, and Xu,2=X1wu. The algorithm B sends pku=(Ru,0,Ru,1,Ru,2,Ru,3,Xu,2) to the forger A2 as the set of public keys for the identity IDu and updates Tab1.(b)
IfIDu=IDtg, the algorithm B chooses random number ϵu,ru,wu←Zq∗ and calculates σu~=ru+xϵu, Ru,0=gku=ga, Ru,1=gru, Ru,2~=gασu~, Ru,2=Ru,2~·(ga)α, Ru,3=(Ru,1·Ru,0)wu, and Xu,2=X1wu. The algorithm B sends pku=(Ru,0,Ru,1,Ru,2,Ru,3,Xu,2) to the forger A2 as the set of public keys for the identity IDu and updates Tab1.(4)
The algorithmB simulates the hash oracles as follows.For Hash OracleH. At any time the forger A2 can query the random oracle H for (IDu,Ru,1). To respond to the hash queries, the algorithm B retrieves the tuple which includes the queried identity IDu in Tab1. Then the algorithm B returns H(IDu,Ru,1)=ϵu in Tab1 to the forger A2.For Hash OracleH~. At any time the forger A2 can query the random oracle H~ for (IDu,pku,idi). To respond to the hash queries, the algorithm B maintains a table Tab2=(IDu,pku,idi,ξu,i), where Tab2 is initially empty. When the forger A2 queries (IDu,pku,idi), the algorithm B responds as follows:
(a)
If(IDu,pku,idi)∉Tab2, the algorithm B picks a random number ξu,i∈Zq∗ and sets the hash value Hu~=ξu,i. Then the algorithm B stores the tuple Tab2=(IDu,pku,idi,ξu,i) and responds with H(pku,idi)=ξu,i to the forger A2.(b)
If(IDu,pku,idi)∈Tab2, the algorithm B returns H~(pku,idi)=ξu,i in Tab2 to the forger A2.For Hash Oracleh. At any time the forger A2 can query the random oracle h for (fname,idi). To respond to the hash queries, the algorithm B maintains a table Tab3=(fname,idi,δi,ci,hi), where Tab3 is initially empty. When the forger A2 queries (fname,idi), the algorithm B responds as follows:
(a)
If(fname,idi)∉Tab3, the algorithm B flips a random coin ci∈{0,1} with a probability Pr[ci=0]=1/(qt+1), where qt is the maximum number of TagGen queries. The algorithm B picks a random number δi∈Zq∗ and computes hi=(gb)(1-ci)·gδi. Then the algorithm B stores the tuple Tab3=(fname,idi,δi,ci,hi) and returns H(fname,idi)=hi to the forger A2.(b)
If(fname,idi)∈Tab3, the algorithm B responds with h(fname,idi)=hi in Tab3.(5)
The algorithmB simulates the Partial-Private-Key-Extract oracle, Secret-Value-Extract oracle, and TagGen oracle as follows.ForPartial-Private-Key-ExtractOracle. At any time the forger A2 can request a partial private key for IDu to the oracle. When the forger A2 queries IDu to the oracle, B retrieves the tuple which contains IDu in Tab1 and responds with (Ru,1,Ru,2~,σu~).ForSecret-Value-ExtractOracle. At any time the forger A2 is able to request a secret value for IDu to the oracle. When the forger A1 queries IDu to the oracle, B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B retrieves the tuple which contains the queried IDu in Tab1 and returns (wu,ku) to the forger A2.(b)
IfIDu=IDtg, the algorithm B reports failure.ForTagGenOracle. At any time the forger A2 can query the oracle for the tuple (IDu,idi,mi). The algorithm B stores Tab4=(IDu,idi,mi,ϵu,ru,wu,ku,σu,ξu,i,δi,hi,ci,ti), where Tab4 is initially empty. When the forger A2 queries IDu, the algorithm B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B retrieves the tuple which is corresponding to the queried tuple (IDu,idi) and computes the tag ti for the queried message mi, where ti=(g1wuξu,i·hi·g2fβi→(α))σu. The algorithm B responds with ti and updates Tab4.(b)
IfIDu=IDtg, the algorithm B retrieves the tuple which is corresponding to the queried tuple (IDu,idi). If ci=1, the algorithm B computes the tag ti for the queried message mi, where ti=(g1wuξu,i·hi·g2fβi→(α))σu~·(ga)wuz2ξu,i+δi+fβi→(α). The algorithm B responds with ti and updates Tab4. Otherwise, the algorithm B reports failure.(6)
Finally, the forgerA2 outputs the forged pair of message and tag (ID∗,idi,mi∗,ti∗) such that no TagGen query was issued for mi∗. If idi∈Tab3, ci=0, and ID∗=IDtg, ti∗ satisfies the equation (13)eti∗,g=eg1Hu,i~,Ru,3·Xu,2Hu·ehi·g2fβi∗→α,Ru,0·Ru,1·X1Hu.
From the right-hand-side of the above equation, the algorithmB could compute (14)eg1Hu,i~,Ru,3·Xu,2Hu·ehi·g2fβi∗→α,Ru,0·Ru,1·X1Hu=egz1Hu,i~,ga+ruwu·gxwuHi·egb+δi·gz2fβi∗→α,ga·gru+xHu=egwuz1Hu,i~,ga·gru+xHu·egb·gδi+z2fβi∗→α,ga·gru+xHu=egawuz1Hu,i~·gru+xHuwuz1Hu,i~,g·egab·gaδi+z2fβi∗→α·gbru+xHu·gδi+z2fβi∗→αru+xHu,g=egab·gawuz1Hi~+δi+z2fβi∗→α·gbru+xHu·gwuz1Hu,i~+δi+z2fβi∗→αru+xHu,g.
Then the algorithmB outputs(15)gab=ti∗gaθ1·gbθ2·gθ3,where θ1=wuz1Hu,i~+δi+z2f←βi∗(α), θ2=ru+xHu, and θ3=ru+xHu(wuz1Hu,i~)+(δi+z2f←βi∗(α))(ru+xHu).
From now on, we define three events related to the success probability ofB and analyze it as follows:(i)
E4: the algorithm B does not abort in the Secret-Value-Extract queries and TagGen queries.(ii)
E5: the forger A2 outputs a valid pair of message and tag (ID∗,idi,mi∗,ti∗), which has not been queried before.(iii)
E6: event E5 occurs and ci=0 for the tuple containing idi on Tab3.In the case that the all events happen, the algorithm B can solve the CDH problem. Thus, the probability of success is Pr[E4∧E6], and we can compute it as (16)PrE4∧E6=PrE4·PrE5∣E4·PrE6∣E4∧E5.
We analyze the lower bounds ofPr[E4], Pr[E5∣E4], and Pr[E6∣E4∧E5] in the following claims.
Claim 4. The probability Pr[E4] that the algorithm B does not abort in the Secret-Value-Extract queries and the TagGen queries by the forger A2 is at least 1/e2.
Claim 5. The probability Pr[E5∣E4] that the forger A2 outputs a valid pair of message and tag under the condition that the event E4 has occurred is at least ε.
Claim 6. The probability Pr[E6∣E4∧E5] that the algorithm B does not abort after the forger A3 outputs a valid pair of message and tag is at least 1/(qt+1).
By the similar analysis method in Theorem4, we can easily compute B’s success probability, thus we omit the detailed probability analyses. With the above claims, the success probability of B is ε/(e2·(qt+1)). Thus we can conclude that if the CDH assumption holds in G, there exists no algorithm which breaks the tag-unforgeability of our scheme by the malicious-but-passive-KGC attack with a nonnegligible probability.Theorem 6.
The proposed certificateless public auditing scheme is secure against the proof-forgery by Type III adversary under chosen message attacks in the random oracle model, if the DCDH assumption holds inG.Proof of Theorem6.
Suppose Type III adversaryA3 is the proof-forger that could break the scheme by generating a fake proof for an arbitrary challenge message with a probability ε. We does not consider the case that the fake proof was generated by the forged tags, since we proved it in the above theorems (even though the theorems ensure the security against the tag-forgery by Type I adversary A1 and Type II adversary A2, it can be easily applied to Type III adversary A3 by eliminating the oracles related to the key extraction in the proof of Theorems 4 and 5). Using the proof-forger, we can construct an algorithm B that solves the DCDH problem on G.
Given an instance(g,ga,gb)∈G of the DCDH problem, the algorithm B simulates the challenger and interacts with the forger A3 in Game III.(1)
The forgerA3 outputs an identity IDtg where it wishes to be forged.(2)
The algorithmB chooses random numbers α,x,z1,z2←Zq∗ and computes {g2αj}0≤j≤s+1, where g2=gz2. The algorithm B sets X1=gx and g1=gz1 and sends PP to the forger A3.(3)
For KeyGen oracle, at any time the forger A3 can query the KeyGen oracle for an identity IDu. The algorithm B stores Tab1=(IDu,ϵu,ru,σu~,σu,wu,ku,γu,Ru,2~,pku), where Tab1 is initially empty. When the forger A3 queries IDu, the algorithm B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B chooses random number ϵu,ru,wu,ku←Zq∗ and calculates Ru,0=gku, Ru,1=gru, σu~=ru+xϵu, σu=ku+ru+ϵu, Ru,2~=gασu~, Ru,2=gασu, Ru,3=(Ru,1·Ru,0)wu, and Xu,2=X1wu. The algorithm B sends pku=(Ru,0,Ru,1,Ru,2,Ru,3,Xu,2) to the forger A2 as the set of public keys for the identity IDu and updates Tab1.(b)
IfIDu=IDtg, the algorithm B chooses random number ϵu,γu,ru←Zq∗ and calculates σu~=ru+xϵu, Ru,0=gku=ga/gσu~, Ru,1=gru, Ru,2~=gασu~,Ru,2=(ga)α, Xu,2=gγu, and Ru,3=gb/(gγuϵu). The algorithm B sends pku=(Ru,0,Ru,1,Ru,2,Ru,3,Xu,2) to the forger A3 as the set of public keys for the identity IDu and updates Tab1.(4)
The algorithmB simulates the hash oracles as follows.For Hash OracleH. At any time the forger A3 can query the random oracle H for (IDu,Ru,1). The algorithm B retrieves the tuple which includes the queried identity IDu in Tab1. Then the algorithm B returns H(IDu,Ru,1)=ϵu in Tab1 to the forger A3.For Hash OracleH~. At any time the forger A3 can query the random oracle H~ for (IDu,pku,idi). To respond to the hash queries, the algorithm B maintains a table Tab2=(IDu,pku,idi,ξu,i), where Tab2 is initially empty. When the forger A3 queries (IDu,pku,idi), the algorithm B responds as follows:
(a)
If(IDu,pku,idi)∉Tab2, the algorithm B picks a random number ξu,i∈Zq∗ and sets the hash value Hu,i~=ξu,i. Then the algorithm B stores the tuple Tab2=(IDu,pku,idi,ξu,i) and responds with H(pku,idi)=ξu,i to the forger A3.(b)
If(IDu,pku,idi)∈Tab2, the algorithm B returns H~(pku,idi)=ξu,i in Tab2 to the forger A3.For Hash Oracleh. At any time the forger A3 can query the random oracle h for (fname,idi). To respond to the hash queries, the algorithm B maintains a table Tab3=(fname,idi,δi,ci,hi), where Tab3 is initially empty. When the forger A2 queries (fname,idi), the algorithm B responds as follows:
(a)
If(fname,idi)∉Tab3, the algorithm B picks a random number δi∈Zq∗ and computes hi=gδi. Then the algorithm B stores the tuple Tab3=(fname,idi,δi,hi) and returns h(fname,idi)=hi to the forger A3.(b)
If(fname,idi)∈Tab3, the algorithm B responds with h(fname,idi)=hi in Tab3.(5)
The algorithmB simulates the Partial-Private-Key-Extract oracle, Secret-Value-Extract oracle, and TagGen oracle as follows.ForPartial-Private-Key-ExtractOracle. At any time the forger A3 can request a partial private key for IDu to the oracle. When the forger A3 queries IDu to the oracle, B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B retrieves the tuple which contains the queried IDu in Tab1 and returns (Ru,1,Ru,2~,σu~) to the forger A3.(b)
IfIDu=IDtg, the algorithm B reports failure.ForSecret-Value-ExtractOracle. At any time the forger A3 is able to request a secret value for IDu to the oracle. When the forger A3 queries IDu to the oracle, B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B retrieves the tuple which contains the queried IDu in Tab1 and returns (wu,ku) to the forger A3.(b)
IfIDu=IDtg, the algorithm B reports failure.ForTagGenOracle. At any time the forger A3 can query the oracle for the tuple (IDu,idi,mi). The algorithm B stores Tab4=(IDu,idi,mi,ϵu,ru,wu,ku,γu,σu,ξu,i,δi,hi,ti), where Tab4 is initially empty. When the forger A3 queries IDu, the algorithm B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B retrieves the tuple which is corresponding to the queried tuple (IDu,idi) and computes the tag ti for the queried message mi, where ti=(g1wuξu,i·hi·g2fβi→(α))σu. The algorithm B responds with ti and updates Tab4.(b)
IfIDu=IDtg, the algorithm B retrieves the tuple which is corresponding to the queried tuple (IDu,idi). The algorithm B computes the tag ti for the queried message mi, where ti=((gb)ξu,i)·(ga)δi+z2fβi→(α).(6)
The algorithmB chooses random number rc←Zq∗ and a random d-elements subset D⊂[1,n]. In this process, B should choose a random subset which contains at least an index idi, where idi is not queried before in TagGen oracle. Let D′ be a subset of D, and it is composed of indices which are not queried in TagGen oracle. Then the algorithm B sends (rc,D) as the challenge message.(7)
Finally, the forgerA3 outputs a forged proof for the challenge message (T,ρ∗,y∗,ψ∗). We assume that T is not able to be forged by the forger A3, since we proved the tag-unforgeability in the previous theorems. Then the algorithm checks the validity of the forged proof by the following equation: (17)eT,g=eg1π,gb·eρ∗·g2y∗,ga·eψ∗,Ru,2·ga·-rc.The algorithm B could compute the right-hand-side of the above equation as (18)eg1π,gb·eρ∗·g2y∗,ga·eψ∗,Ru,2·ga·-rc=egz1π,gb·eρ∗·gz2y∗,ga·eψ∗,gaα-rc=egz1πb,g·eρ∗·gz2y∗,ga·eψ∗α-rc,ga=egz1πb,g·eρ∗·gz2y∗·ψ∗α-rc,ga.To satisfy (18), the value (ρ∗·gz2y∗·ψ∗(α-rc)) should contain (ga-1b)π′, where π′=∑i∈D′ξu,ipi. Thus, we can compute ga-1b as (19)ga-1b=ρ∗·gz2y∗·ψ∗α-rcgC1/π′,where C=∑i∈Dδipi+z2fA→(α).
From now on, we define two events related to the success probability ofB and analyze it as follows:(i)
E7: the algorithm B does not abort in the Partial-Private-Key-Extract queries and Secret-Value-Extract queries.(ii)
E8: the forger A3 outputs a valid proof (T,ρ∗,y∗,ψ∗), which has not been queried before.In the case that the both events happen, the algorithm B can solve the DCDH problem. Thus, the probability of success is Pr⁡[E7∧E8]=Pr⁡[E7]·Pr⁡[E8]. We analyze the lower bounds of Pr⁡[E7] in the following claim.
Claim 7. The probability Pr[E7] that the algorithm B does not abort in the Partial-Private-Key-Extract queries and the Secret-Value-Extract queries by the forger A1 is at least 1/e2.
Proof of Claim 7. We assume that the forger A3 does not query for the same index twice. In the Partial-Private-Key-Extract oracle, the algorithm B aborts only if IDu=IDtg. This probability is equal to 1/qk, where qk is the number of Partial-Private-Key-Extract queries. Therefore, the probability that the algorithm B does not abort is 1-1/qk for each Partial-Private-Key-Extract query. Since the Partial-Private-Key-Extract queries are issued at most qk times, the probability that the algorithm B does not abort is at least (1-1/qk)qk≥1/e. In the Secret-Value-Extract oracle, the algorithm B only aborts if IDu=IDtg. The probability that the algorithm B does not abort is 1-1/qk. Similarly, the probability that the algorithm B does not abort in the Secret-Value-Extract oracle is at least (1-1/qk)qk≥1/e. Thus, the probability Pr⁡[E7] that the algorithm B does not abort in the forger A3’s Partial-Private-Key-Extract queries and Secret-Value-Extract queries is at least (1-1/qk)2qk≥1/e2.
With the above claim, the success probability ofB is ε/e2, since the probability Pr⁡[E8]=ε. Thus we can conclude that if the DCDH assumption holds in G, there exists no algorithm which breaks the proof-unforgeability of our scheme with a nonnegligible probability.According to Theorems4, 5, and 6, we can get Theorem 7 for the security of our proposed scheme. The comparison of the security levels for the certificateless public auditing schemes are explained in Table 1.Table 1
Security levels of certificateless public auditing schemes. LetA1, A2, and A3 be a Type I adversary, Type II adversary, and Type III adversary as defined in Section 3, respectively. Type I adversary and Type II adversary are classed as the normal, strong, and super adversaries (ordered by the capability of the adversaries).
Security againstA1 Security againstA2 Security againstA3 [28] StrongA1 SuperA2 Secure [29] SuperA1 SuperA2 No formal proof provided Ours SuperA1 SuperA2 SecureTheorem 7.
The proposed certificateless public auditing scheme is secure against the existential forgery under chosen message attack in the random oracle model, if the CDH and DCDH assumption hold inG.Proof of Theorem7.
By proving Theorems4, 5, and 6, we have proved that our certificateless public auditing scheme is secure against Type I, Type II, and Type III adversaries, respectively. Thus, our certificateless public auditing scheme is secure against the existential forgery attacks defined in Section 3.2.


### 4.2. Efficiency Analysis

In this section, we compare the computation cost of our scheme with two certificateless public auditing schemes in [28, 29], when TPA performs the auditing in the verification algorithm. Since we aim to construct the scheme which can efficiently verify the proof for the challenge message, we just compare the verification time of the proof in Table 3 (in reality, the computing power of the server is sufficiently larger than that of the TPA (user), so we made an effort to reduce the TPA’s computational cost).LetPair be the bilinear pairing computation and MulG be the multiplication in group G. Let HashG and ExpG be the hash-to-point computation and the exponentiation in group G, respectively. Scott et al. released implementation results for the operations with 3 GHz-Pentium IV using the MIRACL multiprecision library (ver.5.01) [38]. Their results are shown in Table 2.Table 2
Computational cost: letPair be the bilinear pairing computation and MulG be the multiplication in group G. Let HashG and ExpG be the hash-to-point computation and the exponentiation in the group G, respectively.
Computations P a i r M u l G H a s h G E x p G Times (in milliseconds) 3.16 1.17 <1 0.62Table 3
Comparison between certificateless public auditing schemes. LetPair be the bilinear pairing computation and MulG be the multiplication in group G. Let HashG and ExpG be the hash-to-point computation and the exponentiation in group G, respectively. Let d be the number of the challenged blocks.
Computational cost of TPA d = 300 d = 460 [28] 3 ⋅ P a i r + ( 2 d - 1 ) ⋅ M u l G + ( d + 1 ) ⋅ H a s h G + ( 2 d + 1 ) ⋅ E x p G ≈ ( 4.58 × d + 9.93 ) ms 1383.93 ms 2116.73 ms [29] 2 ⋅ Pair + ( d + 2 ) ⋅ M u l G + ( d + 1 ) ⋅ Hash G + ( d + 3 ) ⋅ E x p G ≈ ( 2.79 × d + 11.52 ) ms 848.52 ms 1294.92 ms Ours 4 ⋅ P a i r + 7 ⋅ M u l G + 6 ⋅ E x p G ≈ 23.93 ms 23.93 ms 23.93 msIn [2], Ateniese et al. proved that TPA is able to detect any modification of the outsourced data with 95% or 99% probability by selecting 300 or 460 challenge blocks, respectively. In Table 3, we computed the execution time of the verification algorithm in the case of d=300 and d=460. Note that the computational cost of TPA in [28, 29] is linearly increasing by the number of challenged blocks d. On the other hand, the computational cost of TPA in our scheme is constant with respect to the number of challenged blocks d. In the case of c=300, our scheme is approximately 57.8 times and 35.4 times faster than the schemes in [28] and [29], respectively. In the case of c=460, our scheme is approximately 88.5 times and 54.1 times faster than the schemes in [28] and [29], respectively.


## 4.1. Security Analyses

In this section, we analyze the security of our certificateless public auditing scheme. If the scheme is secure against the tag-forgery by Type I adversary and Type II adversary and the proof-forgery by Type III adversary under adaptive chosen message attacks, then we consider that the scheme is secure againstexistential forgery.Theorem 4.
The proposed certificateless public auditing scheme is secure against the tag-forgery by Type I adversary under chosen message attacks in the random oracle model, if the CDH assumption holds inG.Proof of Theorem4.
Suppose Type I adversaryA1 is the forger that could break the scheme by generating a valid pair of message and tag under user’s secret key with a probability ε. Then we can construct an algorithm B that solves the CDH problem on G.
Given an instance(g,ga,gb)∈G of the CDH problem, the algorithm B simulates the challenger and interacts with the forger A1 in Game I.(1)
The forgerA1 outputs an identity IDtg where it wishes to be forged.(2)
The algorithmB chooses random numbers α,z1,z2←Zq∗ and computes {g2αj}0≤j≤s+1, where g2=gz2. The algorithm B sets X1=ga and g1=gz1 and sends PP to the forger A1.(3)
ForKeyGenoracle, at any time the forger A1 can query the KeyGen oracle for an identity IDu. The algorithm B stores Tab1=(IDu,ϵu,ru,σu~,σu,wu,ku,Ru,2~,pku), where Tab1 is initially empty. When the forger A1 queries IDu, the algorithm B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B chooses random number ϵu,σu~,wu,ku←Zq∗ and calculates σu=σu~+ku, Ru,0=gku, Ru,1=gσu~/(ga)ϵu, Ru,2~=gασu~, Ru,2=gα(σu~+ku), Ru,3=(Ru,1·Ru,0)wu, and Xu,2=(ga)wu. The algorithm B sends pku=(Ru,0,Ru,1,Ru,2,Ru,3,Xu,2) to the forger A1 as the set of public keys for the identity IDu and updates Tab1.(b)
IfIDu=IDtg, the algorithm B chooses random number ϵu,ru,wu,ku←Zq∗ and calculates Ru,0=gku, Ru,1=gru, Ru,2~=(Ru,1·gaϵu)α, Ru,2=Ru,1·gaϵuα·gαku, Ru,3=(Ru,1·Ru,0)wu, and Xu,2=gawu. The algorithm B sends pku=(Ru,0,Ru,1,Ru,2,Ru,3,Xu,2) to the forger A1 as the set of public keys for the identity IDu and updates Tab1.(4)
The algorithmB simulates the hash oracles as follows:For Hash OracleH. At any time the forger A1 can query the random oracle H for (IDu,Ru,1). To respond to the hash queries, the algorithm B retrieves the tuple which includes the queried identity IDu in Tab1. Then the algorithm B returns H(IDu,Ru,1)=ϵu in Tab1 to the forger A1.For Hash OracleH~. At any time the forger A1 can query the random oracle H~ for (IDu,pku,idi). To respond to the hash queries, the algorithm B maintains a table Tab2=(IDu,pku,idi,ξu,i), where Tab2 is initially empty. When the forger A1 queries (IDu,pku,idi), the algorithm B responds as follows:
(a)
IfIDu,pku,idi∉Tab2, the algorithm B picks a random number ξu,i∈Zq∗ and sets the hash value Hu,i~=ξu,i. Then the algorithm B stores the tuple Tab2=(IDu,pku,idi,ξu,i) and responds with H(pku,idi)=ξu,i to the forger A1.(b)
If(IDu,pku,idi)∈Tab2, the algorithm B returns H~(pku,idi)=ξu,i in Tab2 to the forger A1.For Hash Oracleh. At any time the forger A1 can query the random oracle h for (fname,idi). To respond to the hash queries, the algorithm B maintains a table Tab3=(fname,idi,δi,ci,hi), where Tab3 is initially empty. When the forger A1 queries (fname,idi), the algorithm B responds as follows:
(a)
If(fname,idi)∉Tab3, the algorithm B flips a random coin ci∈{0,1} with a probability Pr⁡[ci=0]=1/(qt+1), where qt is the maximum number of TagGen queries. The algorithm B picks a random number δi∈Zq∗ and computes hi=(gb)(1-ci)·gδi. Then the algorithm B stores the tuple Tab3=(fname,idi,δi,ci,hi) and returns h(fname,idi)=hi to the forger A1.(b)
If(fname,idi)∈Tab3, the algorithm B responds with h(fname,idi)=hi in Tab3.(5)
The algorithmB simulates Partial-Private-Key-Extract oracle, Public-Key-Replacement oracle, Secret-Value-Extract oracle, and TagGen oracle as follows.ForPartial-Private-Key-ExtractOracle. At any time the forger A1 can request a partial private key for IDu to the oracle. When the forger A1 queries IDu to the oracle, the algorithm B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B retrieves the tuple which contains the queried IDu in Tab1 and returns psku=(Ru,1,Ru,2~,σu) to the forger A1.(b)
IfIDu=IDtg, the algorithm B reports failure.ForPublic-Key-ReplacementOracle. At any time the forger A1 can replace a set of public keys for IDu. Upon receiving a public key replacement query (IDu,pku′), A1 retrieves the tuple which contains IDu in Tab1 and replaces pku with pku′.ForSecret-Value-ExtractOracle. At any time the forger A1 is able to request a secret value for IDu to the oracle. When the forger A1 queries IDu to the oracle, A1 retrieves the tuple which contains IDu in Tab1 and responds with (wu,ku).ForTagGenOracle. At any time the forger A1 can query the oracle for the tuple (IDu,idi,mi). The algorithm B stores Tab4=(IDu,idi,mi,ϵu,ru,wu,ku,σu,ξu,i,δi,hi,ci,ti), where Tab4 is initially empty. When the forger A1 queries IDu, the algorithm B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B retrieves the tuple which is corresponding to the queried tuple (IDu,idi) and computes the tag ti for the queried message mi, where ti=(g1wuξu,i·hi·g2fβi→(α))σu. The algorithm B responds with ti and updates Tab4.(b)
IfIDu=IDtg, the algorithm B retrieves the tuple which is corresponding to the queried tuple (IDu,idi). If ci=1, the algorithm B computes the tag ti for the queried message mi, where ti=g1wuξu,i·hi·g2fβi→αku+ru·gawuz1ξu,i+δi+fβi→αϵu. The algorithm B responds with ti and updates Tab4. Otherwise, the algorithm B reports failure.(6)
Finally, the forgerA1 outputs the forged pair of message and tag (ID∗,idi,mi∗,ti∗) such that no TagGen query was issued for mi∗. If idi∈Tab3, ci=0, and ID∗=IDtg, ti∗ satisfies the following equation: (7)eti∗,g=eg1Hu,i~,Ru,3·Xu,2Hu·ehi·g2fβi∗→α,Ru,0·Ru,1·X1Hu.By using the oracle-replay technique [37] on hash function H, the algorithm B can obtain another forged tag ti∗′ for the same message mi∗. The forged tag ti∗′ also satisfies the following equation: (8)eti∗′,g=eg1Hu,i~,Ru,3·Xu,2Hu′·ehi·g2fβi∗→α,Ru,0·Ru,1·X1Hu′.With the above equations, the algorithm B could compute(9)eti∗ti∗′,g=eg1Hu,i~,Xu,2Hu-Hu′·ehi·g2fβi∗→α,X1Hu-Hu′. From the right-hand-side of the above equation, the algorithm B could get(10)eg1Hu,i~,Xu,2Hu-Hu′·ehi·g2fβi∗→α,X1Hu-Hu′=egz1Hu,i~,gawuHu-Hu′·egbδi·g2fβi∗→α,gaHu-Hu′=egawuz1Hu,i~Hu-Hu′,g·egbδi·gz2fβi∗→α,gaHu-Hu′=egawuz1Hu,i~Hu-Hu′,g·egabδiHu-Hu′,g·egaHu-Hu′z2fβi∗→α,g=egawuz1Hu,i~+z2fβi∗→αHu-Hu′·gabδiHu-Hu′,g.Then the algorithm B outputs (11)gab=ti∗/ti∗′gaC1/δiHu-Hu′,where C=(wuz1Hu,i~+z2fβi∗→(α))(Hu-Hu′).
From now on, we define three events related to the success probability ofB and analyze it as follows:(i)
E1: the algorithm B does not abort in the Partial-Private-Key-Extract queries and TagGen queries.(ii)
E2: the forger A1 outputs a valid pair of message and tag (ID∗,idi,mi∗,ti∗), which has not been queried before.(iii)
E3: event E2 occurs and ci=0 for the tuple containing idi on Tab3.In the case that the all events happen, the algorithm B can solve the CDH problem. Thus, the probability of success is Pr⁡[E1∧E3], and we can compute it as (12)Pr⁡E1∧E3=Pr⁡E1·Pr⁡E2∣E1·Pr⁡E3∣E1∧E2. We analyze the lower bounds of Pr⁡[E1], Pr⁡[E2∣E1], and Pr⁡[E3∣E1∧E2] in the following claims.
Claim 1. The probability Pr⁡[E1] that the algorithm B does not abort in the Partial-Private-Key-Extract queries and the TagGen queries by the forger A1 is at least 1/e2.
Proof of Claim 1. We assume that the forger A1 does not query for the same index twice. At first, in the Partial-Private-Key-Extract oracle the algorithm B cannot respond to the forger A1’s query, if IDu=IDtg. This probability is equal to 1/qk, where qk is the number of KeyGen queries. Therefore, the probability that the algorithm B does not abort is 1-1/qk for each Partial-Private-Key-Extract query. Since the Partial-Private-Key-Extract queries are issued at most qk times, the probability that the algorithm B does not abort is at least (1-1/qk)qk≥1/e. In the TagGen oracle, the algorithm B only aborts if ci=0, where ci is the random value with the probability Pr⁡[ci=0]=1/(qt+1) corresponding to the TagGen query idi in Tab3. By the probability of ci, the probability that the algorithm B does not abort is 1-1/(qt+1). Similarly, the probability that the algorithm B does not abort in the TagGen oracle is at least (1-1/(qt+1))qt≥1/e. Thus, the probability Pr⁡[E1] that the algorithm B does not abort in the forger A1’s Partial-Private-Key-Extract queries and TagGen queries is at least (1-1/qk)qk·(1-1/(qt+1))qt≥1/e2.
Claim 2. The probability Pr⁡[E2∣E1] that the forger A1 outputs a valid pair of message and tag under the condition that the event E1 has occurred is at least ε.
Proof of Claim 2. When the event E1 has occurred, the probability Pr⁡[E2∣E1] depends on the information gathered by the forger A1. The views of A1 in the simulation and the real game are identical as follows:(i)
The distribution of PK given to the forgerA1 in the simulation is identical with the distribution of PK given to the forger A1 in the real game.(ii)
The distribution of the hash values of the hash function in the simulation is identical with the distributions of the hash values of the hash function in the real game.(iii)
The distribution of the responses to the TagGen oracle in the simulation is identical with the distribution of the responses to the TagGen oracle in the real game under the conditional probability.
Thus, the forgerA1 will generate a valid pair of message and tag with a probability at least ϵ.
Claim 3. The probability Pr[E3∣E1∧E2] that the algorithm B does not abort after the forger A1 outputs a valid pair of message and tag is at least 1/(qt+1).
Proof of Claim 3. When the events E1 and E2 have occurred, the algorithm B will abort only in the case that ci=0 for the tuple containing i corresponding to a forged pair of message and tag (idi,mi∗,ti∗) in Tab1. Since the value ci is randomly chosen with the probability Pr[ci=0]=1/(qt+1), the probability Pr[E3∣E1∧E2] is at least 1/(qt+1).
With the above claims, the success probability ofB is ε/(e2·(qt+1)). Thus we can conclude that if the CDH assumption holds in G, there exists no algorithm which breaks the tag-unforgeability of our scheme by the public key replacement attack with a nonnegligible probability.Theorem 5.
The proposed certificateless public auditing scheme is secure against the tag-forgery by Type II adversary under chosen message attacks in the random oracle model, if the CDH assumption holds inG.Proof of Theorem5.
Suppose Type II adversaryA2 is the tag-forger that could break the scheme by generating a valid pair of message and tag under user’s secret key with a probability ε. Then we can construct an algorithm B that solves the CDH problem on G.
Given an instance(g,ga,gb)∈G of the CDH problem, the algorithm B simulates the challenger and interacts with the forger A2 in Game II.(1)
The forgerA2 outputs an identity IDtg where it wishes to be forged.(2)
The algorithmB chooses random numbers α,x,z1,z2←Zq∗ and computes {g2αj}0≤j≤s+1, where g2=gz2. The algorithm B sets X1=gx and g1=gz1 and sends “PP and MK” to the forger A2.(3)
For KeyGen oracle, at any time the forger A2 can query the KeyGen oracle for an identity IDu. The algorithm B stores Tab1=(IDu,ϵu,ru,σu~,σu,wu,ku,Ru,2~,pku), where Tab1 is initially empty. When the forger A2 queries IDu, the algorithm B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B chooses random number ϵu,ru,wu,ku←Zq∗ and calculates Ru,0=gku, Ru,1=gru, σu~=ru+xϵu, σu=ku+ru+ϵu, Ru,2~=gασu~, Ru,2=gασu, Ru,3=(Ru,1·Ru,0)wu, and Xu,2=X1wu. The algorithm B sends pku=(Ru,0,Ru,1,Ru,2,Ru,3,Xu,2) to the forger A2 as the set of public keys for the identity IDu and updates Tab1.(b)
IfIDu=IDtg, the algorithm B chooses random number ϵu,ru,wu←Zq∗ and calculates σu~=ru+xϵu, Ru,0=gku=ga, Ru,1=gru, Ru,2~=gασu~, Ru,2=Ru,2~·(ga)α, Ru,3=(Ru,1·Ru,0)wu, and Xu,2=X1wu. The algorithm B sends pku=(Ru,0,Ru,1,Ru,2,Ru,3,Xu,2) to the forger A2 as the set of public keys for the identity IDu and updates Tab1.(4)
The algorithmB simulates the hash oracles as follows.For Hash OracleH. At any time the forger A2 can query the random oracle H for (IDu,Ru,1). To respond to the hash queries, the algorithm B retrieves the tuple which includes the queried identity IDu in Tab1. Then the algorithm B returns H(IDu,Ru,1)=ϵu in Tab1 to the forger A2.For Hash OracleH~. At any time the forger A2 can query the random oracle H~ for (IDu,pku,idi). To respond to the hash queries, the algorithm B maintains a table Tab2=(IDu,pku,idi,ξu,i), where Tab2 is initially empty. When the forger A2 queries (IDu,pku,idi), the algorithm B responds as follows:
(a)
If(IDu,pku,idi)∉Tab2, the algorithm B picks a random number ξu,i∈Zq∗ and sets the hash value Hu~=ξu,i. Then the algorithm B stores the tuple Tab2=(IDu,pku,idi,ξu,i) and responds with H(pku,idi)=ξu,i to the forger A2.(b)
If(IDu,pku,idi)∈Tab2, the algorithm B returns H~(pku,idi)=ξu,i in Tab2 to the forger A2.For Hash Oracleh. At any time the forger A2 can query the random oracle h for (fname,idi). To respond to the hash queries, the algorithm B maintains a table Tab3=(fname,idi,δi,ci,hi), where Tab3 is initially empty. When the forger A2 queries (fname,idi), the algorithm B responds as follows:
(a)
If(fname,idi)∉Tab3, the algorithm B flips a random coin ci∈{0,1} with a probability Pr[ci=0]=1/(qt+1), where qt is the maximum number of TagGen queries. The algorithm B picks a random number δi∈Zq∗ and computes hi=(gb)(1-ci)·gδi. Then the algorithm B stores the tuple Tab3=(fname,idi,δi,ci,hi) and returns H(fname,idi)=hi to the forger A2.(b)
If(fname,idi)∈Tab3, the algorithm B responds with h(fname,idi)=hi in Tab3.(5)
The algorithmB simulates the Partial-Private-Key-Extract oracle, Secret-Value-Extract oracle, and TagGen oracle as follows.ForPartial-Private-Key-ExtractOracle. At any time the forger A2 can request a partial private key for IDu to the oracle. When the forger A2 queries IDu to the oracle, B retrieves the tuple which contains IDu in Tab1 and responds with (Ru,1,Ru,2~,σu~).ForSecret-Value-ExtractOracle. At any time the forger A2 is able to request a secret value for IDu to the oracle. When the forger A1 queries IDu to the oracle, B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B retrieves the tuple which contains the queried IDu in Tab1 and returns (wu,ku) to the forger A2.(b)
IfIDu=IDtg, the algorithm B reports failure.ForTagGenOracle. At any time the forger A2 can query the oracle for the tuple (IDu,idi,mi). The algorithm B stores Tab4=(IDu,idi,mi,ϵu,ru,wu,ku,σu,ξu,i,δi,hi,ci,ti), where Tab4 is initially empty. When the forger A2 queries IDu, the algorithm B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B retrieves the tuple which is corresponding to the queried tuple (IDu,idi) and computes the tag ti for the queried message mi, where ti=(g1wuξu,i·hi·g2fβi→(α))σu. The algorithm B responds with ti and updates Tab4.(b)
IfIDu=IDtg, the algorithm B retrieves the tuple which is corresponding to the queried tuple (IDu,idi). If ci=1, the algorithm B computes the tag ti for the queried message mi, where ti=(g1wuξu,i·hi·g2fβi→(α))σu~·(ga)wuz2ξu,i+δi+fβi→(α). The algorithm B responds with ti and updates Tab4. Otherwise, the algorithm B reports failure.(6)
Finally, the forgerA2 outputs the forged pair of message and tag (ID∗,idi,mi∗,ti∗) such that no TagGen query was issued for mi∗. If idi∈Tab3, ci=0, and ID∗=IDtg, ti∗ satisfies the equation (13)eti∗,g=eg1Hu,i~,Ru,3·Xu,2Hu·ehi·g2fβi∗→α,Ru,0·Ru,1·X1Hu.
From the right-hand-side of the above equation, the algorithmB could compute (14)eg1Hu,i~,Ru,3·Xu,2Hu·ehi·g2fβi∗→α,Ru,0·Ru,1·X1Hu=egz1Hu,i~,ga+ruwu·gxwuHi·egb+δi·gz2fβi∗→α,ga·gru+xHu=egwuz1Hu,i~,ga·gru+xHu·egb·gδi+z2fβi∗→α,ga·gru+xHu=egawuz1Hu,i~·gru+xHuwuz1Hu,i~,g·egab·gaδi+z2fβi∗→α·gbru+xHu·gδi+z2fβi∗→αru+xHu,g=egab·gawuz1Hi~+δi+z2fβi∗→α·gbru+xHu·gwuz1Hu,i~+δi+z2fβi∗→αru+xHu,g.
Then the algorithmB outputs(15)gab=ti∗gaθ1·gbθ2·gθ3,where θ1=wuz1Hu,i~+δi+z2f←βi∗(α), θ2=ru+xHu, and θ3=ru+xHu(wuz1Hu,i~)+(δi+z2f←βi∗(α))(ru+xHu).
From now on, we define three events related to the success probability ofB and analyze it as follows:(i)
E4: the algorithm B does not abort in the Secret-Value-Extract queries and TagGen queries.(ii)
E5: the forger A2 outputs a valid pair of message and tag (ID∗,idi,mi∗,ti∗), which has not been queried before.(iii)
E6: event E5 occurs and ci=0 for the tuple containing idi on Tab3.In the case that the all events happen, the algorithm B can solve the CDH problem. Thus, the probability of success is Pr[E4∧E6], and we can compute it as (16)PrE4∧E6=PrE4·PrE5∣E4·PrE6∣E4∧E5.
We analyze the lower bounds ofPr[E4], Pr[E5∣E4], and Pr[E6∣E4∧E5] in the following claims.
Claim 4. The probability Pr[E4] that the algorithm B does not abort in the Secret-Value-Extract queries and the TagGen queries by the forger A2 is at least 1/e2.
Claim 5. The probability Pr[E5∣E4] that the forger A2 outputs a valid pair of message and tag under the condition that the event E4 has occurred is at least ε.
Claim 6. The probability Pr[E6∣E4∧E5] that the algorithm B does not abort after the forger A3 outputs a valid pair of message and tag is at least 1/(qt+1).
By the similar analysis method in Theorem4, we can easily compute B’s success probability, thus we omit the detailed probability analyses. With the above claims, the success probability of B is ε/(e2·(qt+1)). Thus we can conclude that if the CDH assumption holds in G, there exists no algorithm which breaks the tag-unforgeability of our scheme by the malicious-but-passive-KGC attack with a nonnegligible probability.Theorem 6.
The proposed certificateless public auditing scheme is secure against the proof-forgery by Type III adversary under chosen message attacks in the random oracle model, if the DCDH assumption holds inG.Proof of Theorem6.
Suppose Type III adversaryA3 is the proof-forger that could break the scheme by generating a fake proof for an arbitrary challenge message with a probability ε. We does not consider the case that the fake proof was generated by the forged tags, since we proved it in the above theorems (even though the theorems ensure the security against the tag-forgery by Type I adversary A1 and Type II adversary A2, it can be easily applied to Type III adversary A3 by eliminating the oracles related to the key extraction in the proof of Theorems 4 and 5). Using the proof-forger, we can construct an algorithm B that solves the DCDH problem on G.
Given an instance(g,ga,gb)∈G of the DCDH problem, the algorithm B simulates the challenger and interacts with the forger A3 in Game III.(1)
The forgerA3 outputs an identity IDtg where it wishes to be forged.(2)
The algorithmB chooses random numbers α,x,z1,z2←Zq∗ and computes {g2αj}0≤j≤s+1, where g2=gz2. The algorithm B sets X1=gx and g1=gz1 and sends PP to the forger A3.(3)
For KeyGen oracle, at any time the forger A3 can query the KeyGen oracle for an identity IDu. The algorithm B stores Tab1=(IDu,ϵu,ru,σu~,σu,wu,ku,γu,Ru,2~,pku), where Tab1 is initially empty. When the forger A3 queries IDu, the algorithm B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B chooses random number ϵu,ru,wu,ku←Zq∗ and calculates Ru,0=gku, Ru,1=gru, σu~=ru+xϵu, σu=ku+ru+ϵu, Ru,2~=gασu~, Ru,2=gασu, Ru,3=(Ru,1·Ru,0)wu, and Xu,2=X1wu. The algorithm B sends pku=(Ru,0,Ru,1,Ru,2,Ru,3,Xu,2) to the forger A2 as the set of public keys for the identity IDu and updates Tab1.(b)
IfIDu=IDtg, the algorithm B chooses random number ϵu,γu,ru←Zq∗ and calculates σu~=ru+xϵu, Ru,0=gku=ga/gσu~, Ru,1=gru, Ru,2~=gασu~,Ru,2=(ga)α, Xu,2=gγu, and Ru,3=gb/(gγuϵu). The algorithm B sends pku=(Ru,0,Ru,1,Ru,2,Ru,3,Xu,2) to the forger A3 as the set of public keys for the identity IDu and updates Tab1.(4)
The algorithmB simulates the hash oracles as follows.For Hash OracleH. At any time the forger A3 can query the random oracle H for (IDu,Ru,1). The algorithm B retrieves the tuple which includes the queried identity IDu in Tab1. Then the algorithm B returns H(IDu,Ru,1)=ϵu in Tab1 to the forger A3.For Hash OracleH~. At any time the forger A3 can query the random oracle H~ for (IDu,pku,idi). To respond to the hash queries, the algorithm B maintains a table Tab2=(IDu,pku,idi,ξu,i), where Tab2 is initially empty. When the forger A3 queries (IDu,pku,idi), the algorithm B responds as follows:
(a)
If(IDu,pku,idi)∉Tab2, the algorithm B picks a random number ξu,i∈Zq∗ and sets the hash value Hu,i~=ξu,i. Then the algorithm B stores the tuple Tab2=(IDu,pku,idi,ξu,i) and responds with H(pku,idi)=ξu,i to the forger A3.(b)
If(IDu,pku,idi)∈Tab2, the algorithm B returns H~(pku,idi)=ξu,i in Tab2 to the forger A3.For Hash Oracleh. At any time the forger A3 can query the random oracle h for (fname,idi). To respond to the hash queries, the algorithm B maintains a table Tab3=(fname,idi,δi,ci,hi), where Tab3 is initially empty. When the forger A2 queries (fname,idi), the algorithm B responds as follows:
(a)
If(fname,idi)∉Tab3, the algorithm B picks a random number δi∈Zq∗ and computes hi=gδi. Then the algorithm B stores the tuple Tab3=(fname,idi,δi,hi) and returns h(fname,idi)=hi to the forger A3.(b)
If(fname,idi)∈Tab3, the algorithm B responds with h(fname,idi)=hi in Tab3.(5)
The algorithmB simulates the Partial-Private-Key-Extract oracle, Secret-Value-Extract oracle, and TagGen oracle as follows.ForPartial-Private-Key-ExtractOracle. At any time the forger A3 can request a partial private key for IDu to the oracle. When the forger A3 queries IDu to the oracle, B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B retrieves the tuple which contains the queried IDu in Tab1 and returns (Ru,1,Ru,2~,σu~) to the forger A3.(b)
IfIDu=IDtg, the algorithm B reports failure.ForSecret-Value-ExtractOracle. At any time the forger A3 is able to request a secret value for IDu to the oracle. When the forger A3 queries IDu to the oracle, B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B retrieves the tuple which contains the queried IDu in Tab1 and returns (wu,ku) to the forger A3.(b)
IfIDu=IDtg, the algorithm B reports failure.ForTagGenOracle. At any time the forger A3 can query the oracle for the tuple (IDu,idi,mi). The algorithm B stores Tab4=(IDu,idi,mi,ϵu,ru,wu,ku,γu,σu,ξu,i,δi,hi,ti), where Tab4 is initially empty. When the forger A3 queries IDu, the algorithm B responds as follows:
(a)
IfIDu≠IDtg, the algorithm B retrieves the tuple which is corresponding to the queried tuple (IDu,idi) and computes the tag ti for the queried message mi, where ti=(g1wuξu,i·hi·g2fβi→(α))σu. The algorithm B responds with ti and updates Tab4.(b)
IfIDu=IDtg, the algorithm B retrieves the tuple which is corresponding to the queried tuple (IDu,idi). The algorithm B computes the tag ti for the queried message mi, where ti=((gb)ξu,i)·(ga)δi+z2fβi→(α).(6)
The algorithmB chooses random number rc←Zq∗ and a random d-elements subset D⊂[1,n]. In this process, B should choose a random subset which contains at least an index idi, where idi is not queried before in TagGen oracle. Let D′ be a subset of D, and it is composed of indices which are not queried in TagGen oracle. Then the algorithm B sends (rc,D) as the challenge message.(7)
Finally, the forgerA3 outputs a forged proof for the challenge message (T,ρ∗,y∗,ψ∗). We assume that T is not able to be forged by the forger A3, since we proved the tag-unforgeability in the previous theorems. Then the algorithm checks the validity of the forged proof by the following equation: (17)eT,g=eg1π,gb·eρ∗·g2y∗,ga·eψ∗,Ru,2·ga·-rc.The algorithm B could compute the right-hand-side of the above equation as (18)eg1π,gb·eρ∗·g2y∗,ga·eψ∗,Ru,2·ga·-rc=egz1π,gb·eρ∗·gz2y∗,ga·eψ∗,gaα-rc=egz1πb,g·eρ∗·gz2y∗,ga·eψ∗α-rc,ga=egz1πb,g·eρ∗·gz2y∗·ψ∗α-rc,ga.To satisfy (18), the value (ρ∗·gz2y∗·ψ∗(α-rc)) should contain (ga-1b)π′, where π′=∑i∈D′ξu,ipi. Thus, we can compute ga-1b as (19)ga-1b=ρ∗·gz2y∗·ψ∗α-rcgC1/π′,where C=∑i∈Dδipi+z2fA→(α).
From now on, we define two events related to the success probability ofB and analyze it as follows:(i)
E7: the algorithm B does not abort in the Partial-Private-Key-Extract queries and Secret-Value-Extract queries.(ii)
E8: the forger A3 outputs a valid proof (T,ρ∗,y∗,ψ∗), which has not been queried before.In the case that the both events happen, the algorithm B can solve the DCDH problem. Thus, the probability of success is Pr⁡[E7∧E8]=Pr⁡[E7]·Pr⁡[E8]. We analyze the lower bounds of Pr⁡[E7] in the following claim.
Claim 7. The probability Pr[E7] that the algorithm B does not abort in the Partial-Private-Key-Extract queries and the Secret-Value-Extract queries by the forger A1 is at least 1/e2.
Proof of Claim 7. We assume that the forger A3 does not query for the same index twice. In the Partial-Private-Key-Extract oracle, the algorithm B aborts only if IDu=IDtg. This probability is equal to 1/qk, where qk is the number of Partial-Private-Key-Extract queries. Therefore, the probability that the algorithm B does not abort is 1-1/qk for each Partial-Private-Key-Extract query. Since the Partial-Private-Key-Extract queries are issued at most qk times, the probability that the algorithm B does not abort is at least (1-1/qk)qk≥1/e. In the Secret-Value-Extract oracle, the algorithm B only aborts if IDu=IDtg. The probability that the algorithm B does not abort is 1-1/qk. Similarly, the probability that the algorithm B does not abort in the Secret-Value-Extract oracle is at least (1-1/qk)qk≥1/e. Thus, the probability Pr⁡[E7] that the algorithm B does not abort in the forger A3’s Partial-Private-Key-Extract queries and Secret-Value-Extract queries is at least (1-1/qk)2qk≥1/e2.
With the above claim, the success probability ofB is ε/e2, since the probability Pr⁡[E8]=ε. Thus we can conclude that if the DCDH assumption holds in G, there exists no algorithm which breaks the proof-unforgeability of our scheme with a nonnegligible probability.According to Theorems4, 5, and 6, we can get Theorem 7 for the security of our proposed scheme. The comparison of the security levels for the certificateless public auditing schemes are explained in Table 1.Table 1
Security levels of certificateless public auditing schemes. LetA1, A2, and A3 be a Type I adversary, Type II adversary, and Type III adversary as defined in Section 3, respectively. Type I adversary and Type II adversary are classed as the normal, strong, and super adversaries (ordered by the capability of the adversaries).
Security againstA1 Security againstA2 Security againstA3 [28] StrongA1 SuperA2 Secure [29] SuperA1 SuperA2 No formal proof provided Ours SuperA1 SuperA2 SecureTheorem 7.
The proposed certificateless public auditing scheme is secure against the existential forgery under chosen message attack in the random oracle model, if the CDH and DCDH assumption hold inG.Proof of Theorem7.
By proving Theorems4, 5, and 6, we have proved that our certificateless public auditing scheme is secure against Type I, Type II, and Type III adversaries, respectively. Thus, our certificateless public auditing scheme is secure against the existential forgery attacks defined in Section 3.2.


## 4.2. Efficiency Analysis

In this section, we compare the computation cost of our scheme with two certificateless public auditing schemes in [28, 29], when TPA performs the auditing in the verification algorithm. Since we aim to construct the scheme which can efficiently verify the proof for the challenge message, we just compare the verification time of the proof in Table 3 (in reality, the computing power of the server is sufficiently larger than that of the TPA (user), so we made an effort to reduce the TPA’s computational cost).LetPair be the bilinear pairing computation and MulG be the multiplication in group G. Let HashG and ExpG be the hash-to-point computation and the exponentiation in group G, respectively. Scott et al. released implementation results for the operations with 3 GHz-Pentium IV using the MIRACL multiprecision library (ver.5.01) [38]. Their results are shown in Table 2.Table 2
Computational cost: letPair be the bilinear pairing computation and MulG be the multiplication in group G. Let HashG and ExpG be the hash-to-point computation and the exponentiation in the group G, respectively.
Computations P a i r M u l G H a s h G E x p G Times (in milliseconds) 3.16 1.17 <1 0.62Table 3
Comparison between certificateless public auditing schemes. LetPair be the bilinear pairing computation and MulG be the multiplication in group G. Let HashG and ExpG be the hash-to-point computation and the exponentiation in group G, respectively. Let d be the number of the challenged blocks.
Computational cost of TPA d = 300 d = 460 [28] 3 ⋅ P a i r + ( 2 d - 1 ) ⋅ M u l G + ( d + 1 ) ⋅ H a s h G + ( 2 d + 1 ) ⋅ E x p G ≈ ( 4.58 × d + 9.93 ) ms 1383.93 ms 2116.73 ms [29] 2 ⋅ Pair + ( d + 2 ) ⋅ M u l G + ( d + 1 ) ⋅ Hash G + ( d + 3 ) ⋅ E x p G ≈ ( 2.79 × d + 11.52 ) ms 848.52 ms 1294.92 ms Ours 4 ⋅ P a i r + 7 ⋅ M u l G + 6 ⋅ E x p G ≈ 23.93 ms 23.93 ms 23.93 msIn [2], Ateniese et al. proved that TPA is able to detect any modification of the outsourced data with 95% or 99% probability by selecting 300 or 460 challenge blocks, respectively. In Table 3, we computed the execution time of the verification algorithm in the case of d=300 and d=460. Note that the computational cost of TPA in [28, 29] is linearly increasing by the number of challenged blocks d. On the other hand, the computational cost of TPA in our scheme is constant with respect to the number of challenged blocks d. In the case of c=300, our scheme is approximately 57.8 times and 35.4 times faster than the schemes in [28] and [29], respectively. In the case of c=460, our scheme is approximately 88.5 times and 54.1 times faster than the schemes in [28] and [29], respectively.


## 5. Conclusions

In the paper, we proposed a provably secure certificateless public auditing scheme with the constant verification time. We also defined the three security models and proved the security of our scheme under the security models.To the best of our knowledge, no certificateless public auditing scheme forshared data with the constant verification time has been proposed. The shared data system means that the authorized users can share their data in the cloud storage systems. Thus, it would be interesting to construct a certificateless public auditing scheme with the constant verification time for shared data.



---

*Source: 6758618-2017-01-30.xml*