Identity-Based Proofs of Storage with Enhanced Privacy

Abstract

Proofs of storage (PoS) refer to an effective solution for checking the integrity of large files stored in clouds, such as provable data possession and proofs of retrievability. Traditional PoS schemes are mostly designed in the public key infrastructure setting, thus they will inevitably suffer from the complex certificate management problem when deployed. Identity-based PoS (IBPoS) is a lightweight variant of traditional PoS that eliminates the certificate management problem via identity-based cryptographic technology. Although there are several IBPoS schemes in the literature, all of them cannot simultaneously protect both identity privacy and data privacy against a third-party verifier that is pervasive in IBPoS systems. To fill this gap, in this paper we propose a new IBPoS scheme, from which a verifier is able to confirm the integrity of the files stored in clouds but cannot get the files or the identity information of their owners. We prove our scheme is secure in the random oracle model under a standard assumption. Finally, we also conduct a series of experiments to evaluate its performance.

1 Introduction

Cloud computing is attracting widespread attentions from both academia and industry since clouds are able to offer many kinds of economical services for users. One of the services is cloud storage, by which users could outsource a mass of files into a cloud. Later, these users may access their outsourced data at anytime and anywhere via any network-connectable devices. Cloud storage services benefit users greatly, they however also bring severe security risks to users, e.g. the cloud may delete some rarely-used outsourced data for storage saving (see [4] for more examples). Therefore, checking the integrity of outsourced data is indispensable for cloud storage.

A crude approach for checking integrity of cloud data is downloading the entire data from the cloud and then detecting its integrity. Obviously, it will incur a huge communication and computation overhead. In order to address this problem, researchers suggest to make use of proofs of storage (PoS) schemes such as provable data possession [1] and proofs of retrievability [17]. Roughly speaking, a PoS scheme first divides a file into many blocks and calculates all block tags, then outsources the file together with the tags into a cloud. The tags are authenticators of blocks and can be aggregated into one authenticator on any linear combination of blocks. As a result, to prove the integrity of an outsourced file, the cloud only needs to give a linear combination of blocks and a corresponding authenticator. In this way, PoS schemes reduce the communication and computation overhead of cloud data integrity checking to be small and independent with the scale of outsourced data.

The first PoS schemes were concurrently proposed by Ateniese et al. [1] and by Juels and Kaliski [17] in 2007; from then on, many new PoS schemes have been published, e.g., [2, 3, 10, 13,14,15,16, 21, 22, 24,25,26,27, 31,32,33, 37, 38] among many others. We note that most of the schemes enjoy the favorable feature of public verifiability, which enables any third-party verifier to check the integrity of outsourced data. Publicly-verifiable PoS schemes usually produce block tags using a variant of some digital signature scheme and most of the underlying signature schemes rely on the public key infrastructure (PKI). Therefore, in those PoS schemes digital certificates are necessary for the authenticity of public keys; otherwise, the integrity of outsourced files cannot be verified. In other words, those PKI-based PoS schemes will inevitably suffer from the certificate management problem when deployed.

To remove digital certificates from PoS schemes, researchers resort to identity-based cryptography [23] and present several identity-based PoS (IBPoS) schemes, e.g. [18, 28,29,30, 34,35,36], where each user’s public key is simply its identity and the corresponding secret key is generated by a trusted private key generator (PKG). These IBPoS schemes can be divided into two categories—one includes [28,29,30] and the other involves [18, 34,35,36]—according to whether they need new secret keys to produce block tags or not. The IBPoS schemes in [28,29,30] are highly compact since they produce block tags directly using the secret keys generated by the PKG via the Schnorr signature scheme [20]. Contrastly, those in [18, 34,35,36] use a new secret key to generate block tags and then bind the secret key with an identity via a secure signature scheme like [9].

Motivation. We notice that Wang et al. [29] recently introduced an efficient anonymous IBPoS scheme upon the anonymous PKI-based PoS in [24, 25], which enables the identity of any file owner to be unavailable for a third-party verifier. In a nutshell, their construction was based on the Schnorr signature [20], the ring signature in [8] and the compact publicly-verifiable PoS scheme due to Shacham and Waters [21, 22]. Very recently, Yu et al. [34] designed a new IBPoS scheme achieving zero knowledge data privacy, hence a third-party verifier cannot get any outsourced file from the scheme. Unfortunately, the two IBPoS schemes both fail to protect identity privacy and data privacy simultaneously. That is, for an outsourced file the third-party verifier either can recognize the identity of its owner or is able to acquire the whole file when executing these schemes. Clearly, the knowledge obtained by the verifier from these IBPoS schemes exceeds what we expect. It’s even insufferable in some scenes such as the outsourced files are private and their owners refuse to disclose whether or not they have deposited them in the cloud.

Our Results. In this paper, we put forward the concept of privacy-enhanced IBPoS as well as an efficient realization, from which the third-party verifier can only confirm the integrity of outsourced files while cannot get the files or the identity information of their owners. We formally prove that our scheme is secure in the random oracle model under the divisible computational Diffie-Hellman assumption (as shown in [5], this assumption is equivalent to the well-known computational Diffie-Hellman assumption [12]). Experimental results also demonstrate the efficiency of our scheme.

Technically, our scheme combines some classic cryptographic techniques in a secure way. Specifically, we first use the Schnorr signature scheme [20] to generate the secret key corresponding to an identity, then load the ring signature of [8] into the compact publicly-verifiable PoS scheme of [21, 22] for preserving the identity privacy of file owners, and finally complete the whole design by supporting data privacy using the data mask method of [26, 27]. At first glance, one may suppose that the scheme in [29] and ours are similar. However, we would like to stress that there exist subtle yet essential differences between the two schemes because our scheme is provably secure while the other is not. More precisely, the IBPoS scheme in [29] is not unconditionally anonymous as claimed. Recall that in [29] the tag for a file consists of a value obtained by hashing the file owner’s signature on the file. An unbounded adversary could simply break the anonymity and find the identity of the file owner by first calculating all signatures on the file and then checking their hashes one-by-one. It implies the security proof in [29] is also faulty. We remark that giving proper security proofs for complex schemes is not an easy task. We address this problem using a slightly weak security model, called semi-adaptive attack model, to prove security of our scheme.

Moreover, we also solve the problem that all the IBPoS schemes in [28,29,30] are not totally identity-based. Observe that in those schemes the secret key corresponding to an identity is a Schnorr signature (R, s) on the identity, where R is a random element picked from some large set $\varSigma$. The random R will later be heavily used by the verifier for data verification. However, the verifier doesn’t know the right R to which an identity corresponds, since all R’s are independent of identities. Therefore, in [28,29,30] R is set to a part of a user’s public key while it violates the principle of identity-based cryptography. To fix this problem, in this paper we introduce a public function f, which is prepared by the PKG in the beginning by choosing unique R’s for identities such that for any inputted identity f will always output the right R.

Paper Organization. The rest of this paper is organized as follows. Section 2 reviews related works. Section 3 introduces the system and security models of IBPoS. Section 4 recalls cryptographic background to be used in this work. Our IBPoS scheme and its security proofs are given in Sect. 5. In Sect. 6, we evaluate the performance of our scheme. Finally, Sect. 7 concludes this paper.

2 Related Work

The first PoS scheme presented by Ateniese et al. [1] named provable data possession and the scheme by Juels and Kaliski [17] called proofs of retrievability. The main difference between the two notions is that proofs of retrievability could provide stronger security guarantees than provable data possession does. Ateniese et al.’s scheme works under the famous RSA assumption [19] and supports public verifiability, while the Juels-Kaliski scheme only provides private verifiability. Shacham and Waters [21] later designed two more efficient PoS schemes, one of which is publicly-verifiable and secure under the well-known computational Diffie-Hellman (CDH) assumption [12]. After that, many other PoS schemes are also proposed, including data privacy preserving PoS [26, 27], identity privacy preserving PoS [24, 25], dynamic PoS [2, 14, 15, 31,32,33, 37], PoS for multicloud storage [38], and so on. However, they mostly rely on PKI and thus will inevitably suffer from the certificate management problem when deployed.

Wang et al. [30] and Yu et al. [36] independently proposed two IBPoS schemes for removing the certificate management problem in PKI-based PoS schemes. Subsequently, anonymous IBPoS and IBPoS for multicloud storage are also presented respectively in [29] and [28]. As mentioned before, the IBPoS in [29] is not unconditionally anonymous. Liu et al. [18] recently have pointed out that the IBPoS in [28] is insecure and they also gave a remedy that is secure under the CDH assumption. As an alternative, Yu et al. [35] built an IBPoS scheme under the RSA assumption. Very recently, Yu et al. [34] designed a new IBPoS scheme that achieves zero knowledge data privacy. However, we remark that the schemes in [18, 34,35,36] are less efficient than their counterparts in [28,29,30] for the same situation since they all employ new secret keys and will need additional signatures to bind the secret keys with the associated identities. Unfortunately, all the schemes in [28,29,30] are not totally identity-based. In addition, we also remark that there is still no IBPoS in the literature that could simultaneously protect both identity privacy and data privacy.

3 Problem Formulation

3.1 System Model

The system considered in this work is illustrated in Fig. 1. The system involves four types of entities namely users, PKG, cloud, and verifier. Users are data owners; each of them produces a large file and wants to outsource it into the cloud. Every file in our system has a distinct identifier, which is public among all participants. Each user also has a unique identity, e.g. its email address, which will serve as its public key. All users’ private keys are generated by the PKG according to their identities. For distributing these private keys securely, we assume secure channels already exist between the PKG and all users. The cloud is the provider of data storage services who owns significant storage space and computation resources. Similarly, we assume that there exists a secure channel between the cloud and each user; hence every user could upload its file into cloud in a secure and guaranteed way. To check the integrity of the outsourced files, a third-party verifier, who is authorized by all users, is activated. The verifier is a professional unit that can effectively check the integrity of massive data stored in the cloud via an IBPoS scheme.

Fig. 1.

The system model of IBPoS.

Generally, in an IBPoS scheme, a user first splits a file to be stored into several blocks and computes a file tag using its secret key. Then the user uploads the file as well as the file tag to the cloud, and then deletes them locally. To check the integrity of the file stored in the cloud, the verifier picks a random challenge and sends it to the cloud. After receiving the challenge, the cloud accesses the file and the corresponding file tag, then calculates and returns a proof of the challenge. Finally, the verifier checks the validity of the proof. If the proof is invalid then the verifier can confirm that the file in the cloud has been destroyed. Otherwise, it must still be intact. The verifier may report the check results upon users’ requests.

The following is the formal definition of IBPoS, where we also take enhanced privacy into consideration.

Definition 1

(IBPoS). An IBPoS scheme is composed by five algorithms Setup, Extract, TagGen, ProofGen and Verify, where:

• $\textsf {Setup}\left( {\lambda ,U }\right) \rightarrow \left( {params,\mathrm{{ }}msk} \right)$. It’s a system setup algorithm run by the PKG. It takes as input a security parameter $\lambda$ and the universe U of identities, and outputs the system public parameters params and the PKG’s master secret key msk.

• $\textsf {Extract}\left( {params,\mathrm{{ }}msk,\mathrm{{ }}ID} \right) \rightarrow {sk_{ID}}$. It’s the private-key extraction algorithm also run by the PKG. It takes as input the system public parameters params, the master secret key msk, a user’s identity $ID\in U$, and outputs the user’s private key $sk_{ID}$.

• $\textsf {TagGen}\left( {params,\mathrm{{ }}s{k_{ID}},\mathrm{{ }}F} \right) \rightarrow T$. It’s the tag generation algorithm run by the user who owns a file F and an identity $ID\in U$. It takes as input the system public parameters params, the user’s secret key $sk_{ID}$ and a file F, the user selects an identity set S involving ID and outputs a file tag T. For achieving identity privacy, we require the set S must contain at least two identities.

• $\textsf {ProofGen}\left( params,\mathrm{{ }}chal,\mathrm{{ }}F,\mathrm{{ }}T \right) \rightarrow P$. It’s the proof generation algorithm run by the cloud. It takes as input the system public parameters params, the challenge chal received from the verifier, a file F and the corresponding file tag T. It outputs a proof P.

• $\textsf {Verify}\left( {params,\mathrm{{ }}chal,\mathrm{{ }}P} \right) \rightarrow {0\ \mathrm{{ }}or\mathrm{{ }}\ 1}$: It’s the proof verifying algorithm run by the verifier. It takes as input the system public parameters params, the challenge chal and a proof P, and returns 0 or 1. Return 0 means the outsourced file has been destroyed while return 1 indicates the file is still intact.

Correctness. All IBPoS schemes must observe correctness, namely if the file stored in the cloud remains intact and all entities involved are honest, then the algorithm Verify should always output 1. More formally, we say an IBPoS scheme is correct if for all security parameter $\lambda$, identity universe U, file F and identity $ID\in U$, let (${params,\mathrm{{ }}msk}$) = Setup(${\lambda ,U }$), ${sk_{ID}}$ = Extract(${params,\mathrm{{ }}msk,\mathrm{{ }}ID}$), T be the output of TagGen(${params,\mathrm{{ }}s{k_{ID}},\mathrm{{ }}F}$) and let chal be any challenge, if P is the output of ProofGen($params,\mathrm{{ }}chal,\mathrm{{ }}F,\mathrm{{ }}T$), then Verify(${params,\mathrm{{ }}chal,\mathrm{{ }}P}$) should always output 1.

3.2 Security Model

Similar to the security models of other IBPoS schemes (e.g. [18, 28,29,30, 34,35,36]), in this work we assume all users are honest while the verifier is semi-honest, i.e., it will honestly follow the predefined procedures but may seek to obtain some additional knowledge such as a file stored in the cloud and the identity of its owner. In addition, the cloud may be malicious in some cases, e.g. it may delete some rarely used file blocks for economic reasons. Therefore, we require an IBPoS scheme to possess the following security and privacy characters.

The primary one is soundness, which models the character that in a secure IBPoS scheme the proofs generated by the cloud could pass the verifier’s checking only with a negligible probability when the outsourced data has been damaged. Moreover, we enforce our IBPoS scheme to provide enhanced privacy, i.e., it should protect both identity privacy and data privacy against the verifier simultaneously. Identity privacy requires that in an IBPoS scheme the verifier cannot link a stored file to the identity of its owner, and data privacy declares that the verifier cannot acquire the outsourced file when executing the scheme.

The formal definitions of soundness, identity privacy and data privacy are respectively given below. Our security definition for soundness is inspired by the definition of unforgeability of ring signature against chosen-subring attacks [7], and we call it soundness against semi-adaptive chosen identity and subring attacks.

Definition 2

(Soundness). We say an IBPoS scheme is sound under the semi-adaptive chosen identity and subring attacks if for any probabilistic polynomial time (PPT) adversary $\mathcal {A}$ the probability that $\mathcal {A}$ wins the following game played between a challenger $\mathcal {C}$ and the adversary $\mathcal {A}$ is negligible.

• Setup. The challenger $\mathcal {C}$ runs the algorithm Setup(${\lambda , U }$) to obtain the system parameters params and the master secret key msk. It sends params to the adversary $\mathcal {A}$, while keeps msk confidential.

• Queries. The adversary $\mathcal {A}$ could semi-adaptively make the following types of queries to the challenger $\mathcal {C}$. More specifically, $\mathcal {A}$ can make TagGen queries when all Extract queries end.

  • Extract Queries. The adversary $\mathcal {A}$ can make such a query to get the private key associated with an identity. The challenger $\mathcal {C}$ will maintain a set $S_E$ of extracted identities to record all such queries. For a query on identity ID, the challenger $\mathcal {C}$ first adds ID into $S_E$, then obtains the private key $sk_{ID}$ by running the algorithm $\textsf {Extract}\left( {params,\mathrm{{ }}msk,\mathrm{{ }}ID} \right)$ and finally forwards $sk_{ID}$ to $\mathcal {A}$.

  • TagGen Queries. The adversary $\mathcal {A}$ can get the tag of any file F by issuing (ID, F) to this query, where ID denotes the owner identity of the file F. The challenger $\mathcal {C}$ runs $\textsf {TagGen}\left( {params,\mathrm{{ }}\textsf {Extract}\left( {params,\mathrm{{ }}msk,\mathrm{{ }}ID} \right) ,\mathrm{{ }}F} \right)$ to get the file tag T and then forwards it to $\mathcal {A}$. Note that in generating T, the challenger $\mathcal {C}$ will select an identity set S satisfying $ID\in S$ to achieve identity privacy.

• Proof. In this phase, the challenger $\mathcal {C}$ behaves as the verifier and the adversary $\mathcal {A}$ serves as the cloud. For an outsourced file F and the corresponding tag T, the challenger $\mathcal {C}$ generates a random challenge chal and requests the adversary $\mathcal {A}$ to return a proof. After receiving the request, $\mathcal {A}$ runs the algorithm $\textsf {ProofGen}\left( params,\mathrm{{ }}chal,\mathrm{{ }}F,\mathrm{{ }}T \right)$ to get a proof and forwards it to $\mathcal {C}$.

• Forgery. When the above process ends, the adversary $\mathcal {A}$ outputs a proof P of some challenge chal on an outsourced file F. We say $\mathcal {A}$ wins the game if $\textsf {Verify}\left( {params,\mathrm{{ }}chal,\mathrm{{ }}P} \right) =1$, F has been broken and $\mathcal {A}$ does’t make any Extract query on identities in S, where S is the identity set used in TagGen.

Definition 3

(Identity Privacy). We say an IBPoS scheme achieves identity privacy if for any PPT adversary $\mathcal {A}$ its advantage in the following game is negligible. This game is also played between a challenger $\mathcal {C}$ and the adversary $\mathcal {A}$.

• Setup. The adversary $\mathcal {A}$ runs the algorithm Setup(${\lambda , U}$) to obtain the system public parameters params and the master secret key msk. It sends both params and msk to the challenger $\mathcal {C}$.

• Challenge. The adversary $\mathcal {A}$ outputs a tuple $(ID_1,ID_2,F)$. Upon receiving the tuple, the challenger $\mathcal {C}$ picks a random b from $\{1,2\}$, runs the algorithm TagGen($params,\textsf {Extract}\left( {params,\mathrm{{ }}msk,\mathrm{{ }}ID_b} \right) ,F$) to output a file tag $T_b$ for $\mathcal {A}$. Here, we require the identity set S used in the algorithm TagGen for producing $T_b$ must include $\{ID_1,ID_2\}$.

• Guess. The adversary $\mathcal {A}$ outputs a guess $b'\in \{1,2\}$.

  We define $\mathcal {A}$’s advantage in this game as $|\text {Pr}[b'=b]-\frac{1}{2}|$.

Similarly, we can define a stronger notion of identity privacy called unconditional identity privacy, that is for any adversary $\mathcal {A}$ (who may have unbounded computational resources) the probability $\text {Pr}[b'=b]$ in the above game is no more than 1/2.

Unconditional identity privacy means that from a set of file tags even an unbounded adversary cannot uncover the identity information of the data owner. Our IBPoS scheme presented in this paper will fulfill the stronger definition.

Definition 4

(Data Privacy). We say an IBPoS scheme achieves data privacy if there exists a polynomial time simulator such that the distributions of the following two conversations are computationally indistinguishable.

• C1. This conversation is the real conversation between the cloud and the verifier.

• C2. This conversation is the simulated conversation between the simulator and the verifier, in which the simulator behaves as the cloud but cannot access to any file stored in the cloud.

Definition 5

We say an IBPoS scheme is secure and provides enhanced privacy if it achieves soundness, identity privacy and data privacy.

4 Cryptographic Background

In this section we give some cryptographic background involved in this paper.

Definition 6

(Bilinear Pairing). Let $\mathbb {G}_1$ and $\mathbb {G}_2$ be two cyclic groups with the same prime order p. A map $e:\mathbb {G}_1\times \mathbb {G}_1\rightarrow \mathbb {G}_2$ is called a bilinear map if it satisfies three properties listed as below.

• 1. Bilinearity: For all $a,b\in \mathbb {Z}$ and $u,v\in \mathbb {G}_1$, we have $e(u^a,v^b)=e(u,v)^{ab}$.

• 2. Non-degeneracy: Let g be a generator of $\mathbb {G}_1$ and $1_{\mathbb {G}_2}$ denote the identity element of group $\mathbb {G}_2$, then we have $e(g,g)\ne 1_{\mathbb {G}_2}$.

• 3. Computability: There exists an efficient algorithm to compute the map e.

The divisible computational Diffie-Hellman (DCDH) assumption is as follows.

Definition 7

(DCDH Assumption). Given a cyclic group $\mathbb {G}$ of order p and a generator $g\in \mathbb {G}$, for random $g^a,g^{ab}\in \mathbb {G}$, it’s intractable to output $g^{b}$.

Bao et al. [5] have shown that this assumption is equivalent to the CDH one.

5 Our Scheme

Throughout the paper, we will work in the group $\mathbb {Z}_p$ for some large prime p. When we work in the bilinear setting, the group $\mathbb {Z}_p$ is the support of the group $\mathbb {G}_1$. We denote the number of elements in a set S by |S| and for a positive integer k, we let $[1,k]=\{1,\ldots ,k\}$.

5.1 Construction

• Setup$(\lambda ,U)$. Given a security parameter $\lambda$ and the universe U of identities in the system, the algorithm outputs a prime $p>2^{\lambda }$, two cyclic groups $\mathbb {G}_1$ and $\mathbb {G}_2$ of order p, a generator g of ${\mathbb {G}_1}$, a bilinear map $e:\mathrm{{ }}{\mathbb {G}_1} \times {\mathbb {G}_1} \rightarrow {\mathbb {G}_2}$, three hash functions ${H_1}:{\{ 0,1\} ^*} \rightarrow {\mathbb {Z}_p},{H_2}:{\{ 0,1\} ^*} \rightarrow {\mathbb {G}_1}$ and ${H_3}:{\{ 0,1\} ^*} \rightarrow {\mathbb {Z}_p}$, and a secure identity-based ring signature scheme RSig. The PKG chooses |U| elements $r_1,\cdots ,r_{|U|}$ from ${\mathbb {Z}_p}$ uniformly at random, calculates $R_i=g^{r_i}$ for all $i\in [1,|U|]$, and finally releases a public function $f:U \rightarrow \varSigma =\{R_i|{i\in [1,|U|]}\}$ to map each identity to an unique element in $\varSigma$. In addition, the PKG also selects random x from ${\mathbb {Z}_p}$ and sets $pub = {g^x}$ as its public key. The system public parameters $params=(p, {\mathbb {G}_1},{\mathbb {G}_2},g,e,{H_1},{H_2},{H_3},RSig,\varSigma ,f,pub)$ and the master secret key $msk=(x,r_1,\cdots ,r_{|U|})$.

• Extract$\left( {params,\mathrm{{ }}msk,\mathrm{{ }}ID_i} \right)$. Given an identity $I{D_i}$ of a user, the PKG first gets $R_i=f(ID_i)$ and $r_i$ corresponding to $R_i$, then computes $s{k_i} = {r_i} +x{H_1}(ID_i,R_i)$. The PKG distributes $sk_i$ to the user as its private key by a secure channel. Let $v_i = {R_i}\cdot (pub)^{{H_1}(ID_i,R_i)}$. The user can check the validity of $sk_i$ by verifying whether ${g^{s{k_i}}} = v_i$ (note that $R_i=f(ID_i)$ can be calculated by any user). If so, the user accepts $sk_i$ and rejects otherwise.

• TagGen$\left( {params,\mathrm{{ }}s{k_{d}},\mathrm{{ }}F} \right)$. Given a private key $sk_d$ and a file F of the user with identity $ID_d$, the user does as follows:

  • 1. Encode F into n blocks, i.e., $F=(m_1,\ldots ,m_n) \in (\mathbb {Z}_p)^n$.

  • 2. Select a random name from $\mathbb {Z}_p$ and set it as the identifier of the file F.

  • 3. Pick a random $u\in \mathbb {G}_1$ and a random subset S of U satisfying $ID_d\in S$. Without loss of generality, we may assume $S=\{ID_1,\cdots ,ID_{|S|}\}$.

  • 4. For all $ID_i\in S$, calculate $R_i=f(ID_i)$ and $v_i = {R_i}\cdot (pub)^{{H_1}(ID_i,R_i)}$.

  • 5. Sign the message name||u||S||n using RSig and get a ring signature sig related to S, where “||” refers to a string concatenation operation. Let $t=\textsf {sig}||name||u||S||n$. We stress that sig can be independently produced by an identity-based ring signature scheme under new secret keys.

  • 6. For each identity $ID_j\in S\setminus \{ID_d\}$, pick random $a_{i,j}$ for all $i\in [1,n]$ from $\mathbb {Z}_p$ and compute $\sigma _{i,j}=g^{a_{i,j}}$.

  • 7. For the identity $ID_d$ and all $i\in [1,n]$, calculate

    

  • 8. Set the tag for block $m_i$ as ${\sigma _i} = ({\sigma _{i,1}}, \ldots ,{\sigma _{i,|S|}})$ where $i\in [1,n]$, and let $T=(t,\sigma _1,\ldots ,\sigma _n)$ be the tag of the file F.

  • 9. Upload the file F together with the file tag T to the cloud, and then delete them locally.

• ProofGen$\left( params,\mathrm{{ }}chal,\mathrm{{ }}F,\mathrm{{ }}T \right)$. To check the integrity of file F, the verifier picks a random $I=\{(i, c_i)\}$ where $i\in [1, n]$ and $c_i \in \mathbb {Z}_p$, and issues a challenge $chal=(name, I)$ to the cloud. After receiving the challenge, the cloud first finds a matched file $F=(m_1,\ldots ,m_n)$ and file tag $T=(t,\sigma _1,\ldots ,\sigma _n)$ by inspecting t. Then the cloud computes $\beta _j=\prod _{(i,c_i)\in I}(\sigma _{i,j})^{c_i}$ for each $j\in [1,|S|]$, chooses a random $\tau \in \mathbb {Z}_p$, calculates $\alpha =e(u,g)^{\tau }$, $\mu =\sum _{(i,c_i)\in I}c_im_i+\tau \cdot {H_3}\left( \alpha ,\beta \right)$, where $\beta = ({\beta _1}, \ldots ,{\beta _{|S|}})$. Finally, the cloud returns a proof $P = (t,\alpha ,\beta ,\mu )$ to the verifier.

• Verify$\left( {params,\mathrm{{ }}chal,\mathrm{{ }}P} \right)$. Given a challenge $chal=(name, I)$ and a proof $P = (t,\alpha ,\beta ,\mu )$, the verifier first parses t and checks the validity of the ring signature sig on the message name||u||S||n. If it’s invalid, the algorithm outputs 0 and terminates. Otherwise, the verifier goes on to check whether

  $$ e\big ({\prod \nolimits _{(i,c_i)\in I} {{H_2}{{( {name,S,i} )}^{{c_i}}}} \cdot {u^\mu },g} \big ) =B \cdot \alpha ^{H_3\left( \alpha ,\beta \right) },$$

  where $B=\prod \nolimits _{i\in [1,|S|]} {e({\beta _i},v_i})$. If so, output 1, and 0 otherwise.

Correctness. If all entities are honest, then for all proofs produced by the cloud using the algorithm ProofGen, the algorithm Verify will always return 1 because the ring signature sig will always be valid and

$$\begin{aligned} B= & {} \prod \nolimits _{j = 1}^{|S|} {e({\beta _j},v_j}) \\= & {} \prod \nolimits _{j = 1}^{|S|} {e\Big ({\prod \nolimits _{(i,c_i)\in I}(\sigma _{i,j})^{c_i}},v_j} \Big ) \\= & {} \prod \nolimits _{j = 1,j\ne d}^{|S|} {e\Big ({\prod \nolimits _{(i,c_i)\in I}(\sigma _{i,j})^{c_i}},v_j} \Big ) \cdot e\Big ({\prod \nolimits _{(i,c_i)\in I}(\sigma _{i,d})^{c_i}},v_d \Big ) \\= & {} \prod \nolimits _{j = 1,j\ne d}^{|S|}e\Big ({\prod \nolimits _{(i,c_i)\in I}(v_j)^{c_ia_{i,j}}},g \Big ) \cdot e\Big (\frac{\prod \nolimits _{(i,c_i)\in I}\big (H_2(name,S,i) \cdot u^{m_i} \big )^{c_i}}{\prod _{(i,c_i)\in I} \prod \nolimits _{j = 1,j\ne d}^{|S|}v_j^{c_ia_{i,j}}},g \Big ) \\= & {} e\Big (\prod \nolimits _{(i,c_i)\in I}H_2(name,S,i)^{c_i} \cdot u^{\sum _{(i,c_i)\in I}m_ic_i},g \Big ). \end{aligned}$$

As a result, we know

$$\begin{aligned}&B \cdot \alpha ^{H_3\left( \alpha ,\beta \right) } \\= & {} e\Big (\prod \nolimits _{(i,c_i)\in I}H_2(name,S,i)^{c_i} \cdot u^{\sum _{(i,c_i)\in I}m_ic_i},g \Big ) \cdot e\big (u^{\tau {H_3}\left( \alpha ,\beta \right) },g \big ) \\= & {} e\Big ({\prod \nolimits _{(i,c_i)\in I} {{H_2}{{( {name,S,i} )}^{{c_i}}}} \cdot {u^\mu },g} \Big ). \end{aligned}$$

5.2 Security

Theorem 1

If the identity-based ring signature scheme RSig is secure and the DCDH assumption holds in bilinear groups, then the IBPoS scheme above is secure and achieves enhanced privacy in the random oracle model.

We prove the theorem using the following three lemmas.

Lemma 1

If the identity-based ring signature scheme RSig is secure and the DCDH assumption holds in bilinear groups, then in the random oracle model no PPT adversary could break the soundness of our IBPoS scheme under the semi-adaptive chosen identity and subring attacks with non-negligible probability.

Proof

According to Definition 2, we will prove that if there exists a PPT adversary $\mathcal {A}$ who breaks the soundness of the above IBPoS scheme with non-negligible probability, then we can construct a polynomial time algorithm $\mathcal {B}$ that uses the adversary $\mathcal {A}$ as a subroutine to solve a DCDH problem with non-negligible probability too. Algorithm $\mathcal {B}$ does so by interacting with $\mathcal {A}$ as follows.

Setup: Given a security parameter $\lambda$ and the universe U of identities in the system, the algorithm $\mathcal {B}$ selects a prime $p>2^{\lambda }$, two cyclic groups $\mathbb {G}_1$ and $\mathbb {G}_2$ of order p, a generator g of ${\mathbb {G}_1}$, a bilinear map $e:\mathrm{{ }}{\mathbb {G}_1} \times {\mathbb {G}_1} \rightarrow {\mathbb {G}_2}$, an identity-based ring signature scheme RSig, and three hash functions ${H_1}:{\{ 0,1\} ^*} \rightarrow {\mathbb {Z}_p},{H_2}:{\{ 0,1\} ^*} \rightarrow {\mathbb {G}_1}$ and ${H_3}:{\{ 0,1\} ^*} \rightarrow {\mathbb {Z}_p}$. In this proof, all the hash functions will be viewed as random oracles controlled by $\mathcal {B}$. Additionally, the algorithm $\mathcal {B}$ also chooses 2|U| elements $r_1,\cdots ,r_{|U|}$ and $s_1,\cdots ,s_{|U|}$ from ${\mathbb {Z}_p}$ uniformly at random.

Suppose the input of the DCDH problem is $(g,g^a,g^{ab})$. Let $g_1=g^a$. Then $\mathcal {B}$ sets the PKG’s public key pub as $g_1$. In addition, $\mathcal {B}$ will maintain a list of tuples in the form of ($ID_k,R_k,b,r_k,s_k$). The list is initially empty and we denote it as the Setup-list. For each identity $ID_i\in U$, $\mathcal {B}$ flips a coin that shows $b=0$ with probability $\zeta$ (it will be determined later) and $b=1$ with probability $1-\zeta$. If $b=0$, $\mathcal {B}$ sets $v_i=g^{s_i}$. Otherwise, $\mathcal {B}$ sets $v_i=g_1^{s_i}$. For both cases, $\mathcal {B}$ calculates $R_i=v_i/g_1^{r_i}$, programs $H_1(ID_i,R_i)=r_i$ and stores ($ID_i,R_i,b,r_i,s_i$) in the Setup-list. Finally, $\mathcal {B}$ releases a public function $f:U \rightarrow \varSigma =\{R_i|{i\in [1,|U|]}\}$ that maps each identity $ID_i$ to $R_i$. The system public parameters $params=(p, {\mathbb {G}_1},{\mathbb {G}_2},g,e,{H_1},{H_2},{H_3},RSig,\varSigma ,f,pub)$.

Hash Queries: The adversary $\mathcal {A}$ could make the following types of hash queries adaptively.

• To get the value $H_1(ID_i,R_i)$, the adversary $\mathcal {A}$ issues an $H_1$ query on $(ID_i,R_i)$. Upon receiving the query, $\mathcal {B}$ looks up a matched tuple ($ID_i,R_i,b,r_i,s_i$) in the Setup-list and responds with $r_i$.

• To get the value $H_2(name,S,i)$, the adversary $\mathcal {A}$ would issue an $H_2$ query on (name, S, i). In response to such queries, the algorithm $\mathcal {B}$ will maintain a list of tuples. We refer to the list as $H_2$-list that is initially empty with each tuple like ($name,S,k,y_k,h_k$). When $\mathcal {B}$ receives an $H_2$ query on (name, S, i), $\mathcal {B}$ first looks up it in the $H_2$-list. If a matched tuple is found, $\mathcal {B}$ just responds with $h_i$. Otherwise, $\mathcal {B}$ selects random $y_i\in \mathbb {Z}_p$, retrieves the file $F=(m_1,\ldots ,m_n)$ and u matched with the identifier name, and then confirms whether $S\subseteq S_E$ ($S_E$ will be described later). If so, $\mathcal {B}$ calculates $h_i=g^{y_i}/u^{m_i}$ and $h_i=g_1^{y_i}/u^{m_i}$ otherwise. For both cases, $\mathcal {B}$ finally stores ($name,S,i,y_i,h_i$) in the $H_2$-list and returns $h_i$ to $\mathcal {A}$. (Notice that $y_i$ should also be related with name and S, but for notation simplicity we omit them.)

• To get the value $H_3(\alpha ,\beta )$, the adversary $\mathcal {A}$ would issue an $H_3$ query on $(\alpha ,\beta )$. Similarly, the algorithm $\mathcal {B}$ will maintain a list of tuples with each tuple like ($\alpha ,\beta ,w$). We refer to the list as $H_3$-list that is initially empty. When $\mathcal {B}$ receives an $H_3$ query on $(\alpha ,\beta )$, $\mathcal {B}$ first looks up it in the $H_3$-list. If a matched tuple is found, $\mathcal {B}$ simply responds with w. Otherwise, $\mathcal {B}$ selects random $w\in \mathbb {Z}_p$, stores ($\alpha ,\beta ,w$) in the $H_3$-list and returns w to $\mathcal {A}$.

Extract Queries: The adversary $\mathcal {A}$ could make such queries adaptively to get the secret keys of users. To record the queries, the algorithm $\mathcal {B}$ will maintain an initially empty set $S_E$. For a query on the identity $I{D_i}$, $\mathcal {B}$ first updates $S_E=S_E\bigcup \{ID_i\}$ and then looks up a matched tuple ($ID_i,R_i,b,r_i,s_i$) in the Setup-list. If $b=0$, $\mathcal {B}$ returns $s_i$. Otherwise, $\mathcal {B}$ aborts. Suppose $\mathcal {A}$ issues at most $q_E$ such queries on identities, then we know the probability that $\mathcal {B}$ doesn’t abort is not less than $\zeta ^{q_E}$.

By construction, we know that for all $s_i$’s returned from $\mathcal {B}$ we have ${g^{s_i}} = v_i={R_i}\cdot g_1^{r_i}={R_i}\cdot (pub)^{{H_1}(ID_i,R_i)}$. Therefore, $s_i$ is a valid secret key of the identity $ID_i$.

TagGen Queries: When the above extract queries end, the adversary $\mathcal {A}$ is able to make this type of queries for getting file tags. Assume $\mathcal {A}$ issues such a query on file F and identity $ID_d\in U$, the algorithm $\mathcal {B}$ first encodes F into n blocks such that $F=(m_1,\ldots ,m_n) \in (\mathbb {Z}_p)^n$ and selects a random file identifier name for F from $\mathbb {Z}_p$. Then $\mathcal {B}$ responds in the following two ways according to whether $ID_d\in S_E$.

Case 1. When $ID_d\in S_E$, then $\mathcal {B}$ knows the secret key associated with $ID_d$. So, $\mathcal {B}$ could pick a random set $S\subseteq S_E$ satisfying $ID_d\in S$, and simply runs the algorithm TagGen in Sect. 5.1 and returns a file tag T to $\mathcal {A}$. Here $\mathcal {B}$ will also store (F, T) in its local memory.

Case 2. If $ID_d\notin S_E$, $\mathcal {B}$ will pick a random set $S\subseteq U\backslash S_E$ so that $ID_d\in S$. We require that $v_i = g_1^{s_i}$ for any identity $ID_i\in S$. (This happens with probability $(1-\zeta )^{|S|}$.) Then $\mathcal {B}$ does as follows.

• 1. Let $u=g^{ab}$. Get a signature sig associated with S and message name||u||S||n using RSig. Then set $t=\textsf {sig}||name||u||S||n$. Without loss of generality, we let $S=\{ID_1,\cdots ,ID_{|S|}\}$.

• 2. For each identity $ID_j\in S\setminus \{ID_d\}$, pick random $a_{i,j}$ from $\mathbb {Z}_p$ for all $i\in [1,n]$ and compute $\sigma _{i,j}=g_1^{a_{i,j}}$.

• 3. For the identity $ID_d$ and all $i\in [1,n]$, retrieve $y_i$ matched with (name, S, i) in the $H_2$-list and all $s_j$’s matched with $ID_j\in S$ in the Setup-list, then calculate $a_{i,d}=(y_i-\sum \nolimits _{j\in [1,|S|]\backslash \{d\}}s_j\cdot a_{i,j})/s_d$ and ${\sigma _{i,d}}=g^{a_{i,d}}$.

  Observe that $H_2( {name,S,i}) \cdot u^{m_i}=g_1^{y_i}$ for all $i\in [1,n]$ by construction. Furthermore, we have

  $$g_1^{a_{i,d}\cdot s_d}\cdot \prod \limits _{j=1,j\ne d}^{|S|} v_j^{a_{i,j}} =g_1^{a_{i,d}\cdot s_d}\cdot \prod \limits _{j=1,j\ne d}^{|S|} g_1^{s_j\cdot a_{i,j}}= g_1^{y_i}.$$

  Thus, the tag ${\sigma _i} = ({\sigma _{i,1}}, \ldots ,{\sigma _{i,|S|}})$ for block $m_i$ generated as the above is indistinguishable from the real one.

• 4. Finally, $\mathcal {B}$ returns the file tag T to $\mathcal {A}$ but also stores (F, T) in its local memory, where $T=(t,\sigma _1,\ldots ,\sigma _n)$.

We can see that in the simulation $\mathcal {B}$ does not abort with probability at least $\zeta ^{q_E}\cdot (1-\zeta )^{|S|}$, which is maximized when $\zeta =q_E/(q_E+|S|)$.

Proof. To check whether the file F stored in the cloud with identifier name remains intact or not, $\mathcal {B}$ picks a random set $I=\{(i, c_i)\}$ where $i\in [1, n]$ and $c_i \in \mathbb {Z}_p$, and issues a challenge $chal=(name, I)$ to the adversary $\mathcal {A}$. After receiving the challenge, $\mathcal {A}$ does the same as the algorithm ProofGen in Sect. 5.1 and then returns a proof to $\mathcal {B}$.

Forgery. Finally, $\mathcal {A}$ with non-negligible probability outputs a proof $P = (t,\alpha ,\beta ,\mu )$ of a challenge $I=\{(i,c_i)\}$ on a file F with identifier name. Let $t=\textsf {sig}||name||u||S||n$, $\beta = ({\beta _1}, \ldots ,{\beta _{|S|}})$. According to Definition 2, we know that F has been broken, $S\subseteq U\backslash S_E$, the ring signature sig on the message name||u||S||n is valid, and

$$\begin{aligned} e\big ({\prod \nolimits _{(i,c_i)\in I} {{H_2}{{( {name,S,i} )}^{{c_i}}}} \cdot {u^\mu },g} \big ) =B \cdot \alpha ^{w}, \end{aligned}$$

(1)

where $B=\prod \nolimits _{i\in [1,|S|]} {e({\beta _i},v_i})$, $w=H_3\left( \alpha ,\beta \right)$.

Since the identity-based ring signature scheme RSig is secure, we know t must always be invariable for the same file F.

Now, the algorithm $\mathcal {B}$ reruns the adversary $\mathcal {A}$ with the same random tape but different responses of $H_3$ queries. By the general forking lemma [6], $\mathcal {B}$ with non-negligible probability will obtain another valid proof $P' = (t,\alpha ,\beta ,\mu ')$ of the challenge I on the file F. Let $w'$ be the output of $H_3\left( \alpha ,\beta \right)$ at this time. Therefore, we have

$$\begin{aligned} e\big ({\prod \nolimits _{(i,c_i)\in I} {{H_2}{{( {name,S,i} )}^{{c_i}}}} \cdot {u^{\mu '} },g} \big ) =B \cdot \alpha ^{w'}, \end{aligned}$$

(2)

where $B=\prod \nolimits _{i\in [1,|S|]} {e({\beta _i},v_i})$.

Dividing Eq. (1) by Eq. (2), we obtain

$$e( u^{\mu -\mu '}, g ) =\alpha ^{w-w'}.$$

Let $\varDelta \mu =\mu -\mu '$, $\varDelta w=w-w'$. We have

$$\begin{aligned} \alpha = e( u, g )^{\frac{\varDelta \mu }{\varDelta w}}. \end{aligned}$$

(3)

Substituting $\alpha$ in Eq. (1) with Eq. (3) yields

$$\begin{aligned} e\big ({\prod \nolimits _{(i,c_i)\in I} {{H_2}{{( {name,S,i} )}^{{c_i}}}} \cdot {u^\mu },g} \big ) =B \cdot e( u, g )^{\frac{w\cdot \varDelta \mu }{\varDelta w}}. \end{aligned}$$

(4)

Recall that $\mathcal {B}$ has stored the original (F, T) in its local memory, hence $\mathcal {B}$ could calculate $\beta ^*_j=\prod _{(i,c_i)\in I}(\sigma _{i,j})^{c_i}$ for all $j\in [1,|S|]$ and $\mu ^*=\sum _{(i,c_i)\in I}c_im_i$, satisfying

$$\begin{aligned} e\big ({\prod \nolimits _{(i,c_i)\in I} {{H_2}{{( {name,S,i} )}^{{c_i}}}} \cdot {u^{\mu ^*} },g} \big ) =\prod \nolimits _{i\in [1,|S|]} {e({\beta ^*_i},v_i}). \end{aligned}$$

(5)

Dividing Eq. (5) by Eq. (4) and then rearranging terms, we obtain

$$\begin{aligned} e\big ( u^{\mu ^*-\mu +\frac{w\cdot \varDelta \mu }{\varDelta w}} ,g \big ) =\prod \nolimits _{i\in [1,|S|]} e(\beta ^*_i\cdot \beta ^{-1}_i,v_i). \end{aligned}$$

(6)

Since $v_i=g_1^{s_i}$ for all $i\in [1,|S|]$, $u=g^{ab}$ and ${\mu ^*-\mu +\frac{w\cdot \varDelta \mu }{\varDelta w}}$ is nonzero with a large probability, we found the solution to the DCDH problem

This concludes the proof.

Lemma 2

For any adversary its advantage in the game of Definition 3 is negligible.

Proof

We prove that for any $F=(m_1,\ldots ,m_n)$ and any two identities $ID_1,ID_2$, the distributions of TagGen($params,\textsf {Extract}\left( {params,\mathrm{{ }}msk,\mathrm{{ }}ID_b} \right) ,F$) are identical. Here $b\in \{1,2\}$ and $S=\{ID_1,ID_2\}$. Therefore, in our scheme anyone (except the file owner himself and the cloud) cannot acquire the identity information of the file owner from the file tag and/or its combinations.

Observe that in our scheme the file tag for file F is $T=(t,\sigma _1,\ldots ,\sigma _n)$ where $t=\textsf {sig}||name||u||S||n$, $S=\{ID_1,ID_2\}$, sig is a ring signature and ${\sigma _i} = ({\sigma _{i,1}},{\sigma _{i,2}})$ is the tag for block $m_i$. By our construction, we know $(\sigma _{i,1})^{sk_1} \cdot (\sigma _{i,2})^{sk_2}={H_2}\left( {name\left| {\left| i \right| } \right| S} \right) \cdot u^{m_i}$ for any block $m_i ~(i\in [1,n])$, where $sk_1$ (resp. $sk_2$) is the private key of $ID_1$ (resp. $ID_2$). In addition, for any $b\in \{1,2\}$ and any $h\in \mathbb {G}_1$, we know the distribution is the same as the distribution $\{ g^{a_1},{g^{a_2}}:a_1, a_2 \in {\mathbb {Z}_p}$ such that $(g^{a_1})^{sk_1} \cdot (g^{a_2})^{sk_2}= h \}$. That is, the distribution of file tags for file F generated using no matter which identity is always the same. As a result, even an unbounded adversary cannot win the game of Definition 3 with non-negligible advantage. So, our IBPoS scheme enjoys identity privacy.

Lemma 3

Our IBPoS scheme provides data privacy.

Proof

We show below that a simulator without accessing to any file stored in the cloud can produce valid proofs for the verifier. Let the system public parameters $params=(p, {\mathbb {G}_1},{\mathbb {G}_2},g,e,{H_1},{H_2},{H_3},RSig,\varSigma ,f,pub)$. For a challenged file F, let $T=(t,\sigma _1,\ldots ,\sigma _n)$ be the tag of F and ${\sigma _i} = ({\sigma _{i,1}}, \ldots ,{\sigma _{i,|S|}})$ be the tag of the i-th file block. Here S is an identity set used to produce T. Suppose the random challenge selected by the verifier is $I=\{(i, c_i)\}$ where $i\in [1, n]$ and $c_i \in \mathbb {Z}_p$. According to Definition 4, we just need to show the simulator without F could produce a proof for the challenge that is indistinguishable from the real one. The simulator does the following. (Here we treat $H_3$ as a random oracle controlled by the simulator.)

• 1. Pick $\mu ,z\in \mathbb {Z}_p$ uniformly at random.

• 2. Set $R_i=f(ID_i)$ and $v_i = {R_i}\cdot (pub)^{{H_1}(ID_i,R_i)}$ for all identities $ID_i\in S$.

• 3. For each $j\in [1,|S|]$, let $\beta _j=\Pi _{(i,c_i)\in I}(\sigma _{i,j})^{c_i}$.

• 4. Calculate $A=e\big ({\prod \nolimits _{(i,c_i)\in I} {{H_2}{{( {name,S,i} )}^{{c_i}}}} \cdot {u^\mu },g} \big )$, $B=\prod \nolimits _{i\in [1,|S|]} {e({\beta _i},v_i})$, and $\alpha =(\frac{A}{B})^{1/z}$.

• 5. Program $H_3(\alpha ,\beta )=z$, where $\beta = ({\beta _1}, \ldots ,{\beta _{|S|}})$.

The proof of the challenge I generated by the simulator is $P = (t,\alpha ,\beta ,\mu )$. We can easily check that . And the simulated proof is clearly indistinguishable from the real one generated by the cloud, as required.

6 Performance Evaluation

In this section, we conduct experiments to evaluate the performance of our IBPoS scheme. We also implement the recent IBPoS schemes in [29, 34] for comparison (yet we stress that the two schemes don’t provide enhanced privacy as defined in this work). In the following, we will denote Wang et al.’s scheme [29] by A-IBPoS and refer to Yu et al.’s scheme [34] as PP-IBPoS.

6.1 Experiment Setup

The simulations are implemented on a Windows 7 system using Intel Core i5-4590 CPU at 3.30 GHz and the memory is 8.00 GB. The system security parameter is set to be 80 bits. All experiments utilize JPBC library of version 2.0.0 and the type A elliptic curve. The file F we choose is of size 1 GB and its total number of blocks may change from 1000 to 10000. All simulation results represent the mean of 10 trials. We apply the identity-based ring signature scheme of [11] in our scheme to sign the message name||u||S||n and employ the short signature scheme of [9] in A-IBPoS to sign the file F. We construct the pseudorandom functions used in A-IBPoS from a linear congruential generator.

According to the results of [1], we know that to detect misbehavior of the cloud with success probabilities up to 99% and 95%, one just needs to respectively select the challenge blocks in I with the numbers of 460 and 300. We also notice that the strength of identity privacy in our IBPoS scheme is proportional to the size of the identity set S used in generating file tags. More users are involved in S, then the strength of identity privacy will be higher. For most practical applications, 10 users may be enough.

6.2 Computation Cost

User Side. We first evaluate the computation overhead of the user side. On the user side, the essential computation overhead comes from the cost of generating tag for a file, which depends on the total number of file blocks (and the size of the identity set S in our scheme and in A-IBPoS). First, we fill 10 users in S and range the file blocks from 1000 to 10000. Figure 2(a) illustrates that the computation costs of tag generation of all three schemes are linearly increasing with the total number of file blocks. And the cost for our scheme is slightly worse than that for A-IBPoS. PP-IBPoS is the most efficient one. Then we fix the file block number to be 5000, and set the number of identities in S to be ranged from 2 to 20. Figure 2(b) shows that the tag generation times of our scheme and A-IBPoS are both larger than that of PP-IBPoS. And our scheme is also slightly less efficient than A-IBPoS.

Fig. 2.

Computation cost. (a) Tag generation times for various numbers of file blocks. (b) Tag generation times for various numbers of users.

Cloud Side. The computation overhead of the cloud is mainly from the cost of generating proof for the challenge picked by the verifier. It depends on the number of challenged blocks and the size of S. First, we fill 10 users in S and range the number of selected blocks in a challenge from 100 to 1000. Figure 3(a) illustrates that the computation times of all three schemes are linearly increasing with the number of selected blocks, but ours is lower than that of A-IBPoS. The computation cost of PP-IBPoS is the lowest one. Then we set the number of challenge blocks to be 460 and range the size of S from 2 to 20. Figure 3(b) shows that the proof generation times of our scheme and A-IBPoS are linearly increasing with the size of S, and ours is slightly lower than that of A-IBPoS. The proof computation time of PP-IBPoS is the lowest and has nothing to do with the size of S.

Fig. 3.

Computation cost. (a) Proof generation times for various numbers of selected blocks. (b) Proof generation times for various numbers of users.

Verifier Side. The computation overhead of the verifier is mainly from the cost of verifying proof sent from the cloud, which depends on the challenge size and the size of S. First, we set the size of S as 10 and range the number of selected blocks in a challenge from 100 to 1000. Figure 4(a) illustrates that the proof verification time in our scheme is less than that of A-IBPoS, and the computation time for PP-IBPoS is the highest one. Then we set the number of challenge blocks to be 460 and range the size of S from 2 to 20. Figure 4(b) shows that the proof verification time of our scheme is the least among all the three schemes and PP-IBPoS needs the most time.

Fig. 4.

Computation cost. (a) Proof verification times for various numbers of selected blocks. (b) Proof verification times for various numbers of users.

Fig. 5.

Communication cost. (a) Communication overhead for various numbers of selected blocks. (b) Communication overhead for various numbers of users.

6.3 Communication Cost

We now compare the communication performance of our IBPoS scheme with those of A-IBPoS and PP-IBPoS. The communication cost of one-round communication is due to the verifier sends a challenge to the cloud and then the cloud returns a proof to the verifier. In Fig. 5(a), we fix the size of S to be 10 and range the number of selected challenge blocks from 100 to 1000. In Fig. 5(b), we set the number of selected challenge blocks to be 460 and range the size of S from 2 to 20. From the figures, we can see that our scheme requires the most communication cost than others, but it’s still very small in value.

7 Conclusion

In this paper we propose a privacy-enhanced IBPoS scheme that could protect identity privacy as well as data privacy against the third-party verifier. We believe our scheme would be useful in some privacy-sensitive scenarios. We formally prove that our scheme is secure in the random oracle model under the DCDH assumption. We also conduct experiments to validate its efficiency.