# Balancing Access Control and Privacy for Data Deduplication via Functional Encryption

Authors: Bo Mi; Ping Long; Yang Liu; Fengtian Kuang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Data deduplication serves as an effective way to optimize the storage occupation and the bandwidth consumption over clouds. As for the security of deduplication mechanism, users’ privacy and accessibility are of utmost concern since data are outsourced. However, the functionality of redundancy removal and the indistinguishability of deduplication labels are naturally incompatible, which bring about a lot of threats on data security. Besides, the access control of sharing copies may lead to infringement on users’ attributes and cumbersome query overheads. To balance the usability with the confidentiality of deduplication labels and securely realize an elaborate access structure, a novel data deduplication scheme is proposed in this paper. Briefly speaking, we drew support from learning with errors (LWE) to make sure that the deduplication labels are only differentiable during the duplication check process. Instead of authority matching, the proof of ownership (PoW) is then implemented under the paradigm of inner production. Since the deduplication label is light-weighted and the inner production is easy to carry out, our scheme is more efficient in terms of computation and storage. Security analysis also indicated that the deduplication labels are distinguishable only for duplication check, and the probability of falsifying a valid ownership is negligible.


---

## Body

## 1. Introduction

As a flourishing service mode, cloud computing adopts load balancing, distributed computing, and other technologies to conveniently provide computation and storage functions for remote follow-up users, thus saving local resources and promoting work efficiency. However, if the users immoderately outsource their data to the cloud, a serious problem may occur due to massive duplicated data. As reported in [1], almost half of the cloud storage is wasted because of data redundancy. Consequently, the budget for managing duplicate data raises up to eight times than that of source data maintenance [2, 3]. With the explosive growth of data nowadays, the tremendous storage requirements or the exorbitant administrative expenses have put enormous pressure on cloud service providers. Therefore, how to store and manage data economically and efficiently has become a serious challenge for these enterprises.To cut down the costs caused by redundant data, deduplication technology has been widely used by cloud service providers [4]. In such a technology, duplication check and proof of ownership are two key problems. Till now, the problem of how to balance the conflict between comparability and confidentiality for secure duplication check remains unsolved [5]. Meanwhile, the problems of how to efficiently validate the access authority and how to achieve complex access structures are also urgent to address, considering that the mechanism of query matching is cumbersome and the downloading certificates may be abused to launch various attacks.As a research hotspot, lots of attentions are put on the efficiency and security of data deduplication. In the published literature, Li et al. [6] suggested carrying out deduplication by comparing the fingerprint of the outsourced file with the uploaded ones in a direct way. However, this method is deficient since the communication and comparison of those fingerprints are inefficient and the contents of data are exposed. To reduce the traffic of deduplication labels and conceal the data, Puzio et al. [7] used the hash function to code the same plaintexts into identical values, which serve as the labels for duplication check. Although this method achieved the goals of transmission efficiency and storage saving, it is vulnerable to dictionary attacks since the hash values are overt.In order to ensure the confidentiality of deduplication labels, Chen et al. [8] utilized the message lock encryption (MLE) to encrypt those hash values of data. However, the traditional MLE scheme is not semantic secure and vulnerable against quantum attacks [9].Fortunately, cryptographers have been devoted to design secure, efficient, and effective crypto systems to resist quantum attacks in recent years. In 2005, Regev et al. [10] proposed a novel paradigm as an underpinning of cryptography, namely, learning with errors. They proved that the difficulty of solving it is equivalent to the hardness of shortest vector problem (SVP) over lattice, and thus, it can resist the attacks based on quantum computing. Besides, it is provided with the capacity of homomorphic and linear computation. Therefore, we consider exploiting it in our scheme to ensure the functionality, efficiency, and security of deduplication labels.As for the proof of ownership, the best solutions till now are all based on Merkle hash tree (MHT) [11, 12]. In detail, the cloud and the user independently hold an MHT computed from the outsourced data. Thus, the user can upload the same MHT to the cloud for comparison. The disadvantages of such scheme are not only high storage and communication overheads but also low computation efficiency. Therefore, Chen et al. [13] improved it by randomly asking the cloud to select some leaf nodes of the MHT to challenge the user. The user must trace the path from the root to these leaves as a reply to prove that he possesses the same tree. Although this method does not require the transmission of the whole MHT for comparison, it demanded that the user and the cloud should construct and store a complete MHT for each file. Moreover, the challenge-response mode implies a long delay.In order to promote the performance of PoW, the advantages of inner product predicate gradually entered the researchers’ sight [14–16]. Roughly speaking, only if the inner product results 0, the user can be granted a permission to access the corresponding file. The most significant merit of this method is using computation instead of comparison to efficiently perform ownership proof. Therefore, we adopted it in our scheme to balance the conflict between the variety of access structures and the security of users’ privacy.Aiming at checking replication over semantic secure deduplication labels and achieving fine-grained access control, this paper proposed a novel cloud data deduplication scheme by exploiting LWE (learning with errors) together with inner product predicate. Our contributions are abbreviated as follows:(i)
Though designed for the purpose of deduplication, the deduplication labels are indistinguishable to any process except for duplication check. This property is achieved in virtue of semantic secure and homomorphic LWE, which is also resistant to quantum attack.(ii)
The proof of ownership is carried out by inner product, which is computationally efficient. Besides, we impose the accessibility of users on their attributes, implying the functionality of the elaborate access structure and ownership transfer.(iii)
For each file, only one light-weighted downloading certificate should be stored by the cloud, while the clients should only carry out and upload its corresponding proof on demand. That is to say that both the storage and bandwidth are economic for cross-user access.The rest of this paper is organized as follows. In Section2, some formal definitions related to LWE and inner product predicate are given. Section 3 depicts our deduplication scheme, including the detailed way for duplication check and ownership proof. The correctness of our scheme is formally validated in Section 4, followed by security and performance analysis in Sections 5–7 that concludes the paper.


## 2. Preliminaries

For better understanding of our scheme, the concepts related to learning with errors and inner product predicate [2, 17] will be introduced in advance.Definition 1.
(Integer lattice). An integer latticeΛ is the integer linear combination of vectors a1,a2,…,aka1,a2,…,ak over ℤm, expressed as(1)Λa1,a2,…,ak=∑i=1kaizi:zi∈ℤ.Definition 2.
(LWE hardness assumption). On parametersn,m,q,α and a discrete Gaussian distribution χ, where(2)Prx⟵χ:x>αq<negln,for x∈ℤq, we select a noise e from χm and uniformly sample a vector s∈ℤqn together with a matrix P∈ℤqn×m. Based on the value of(3)b=sP+eq,two versions of LWE hardness can be defined as follows:(a)
LWE-Search hardness: Given multiple pairs ofP,b on constant P and s, searching for the value of s is difficult.(b)
LWE-Determination hardness: For uniformly sampledb′∈ℤqn, the tuples of P,b and P,b′ are statistically indistinguishable. It means that it is difficult to tell if the second term of those tuples are randomly chosen or computed from formula (3).
In fact, the LWE-search hardness is equivalent to the problem of finding a short enough vector in lattice (GapSVP), and the LWE-determination hardness can be reduced to the problem of solving linearly independent shortest vectors (SIVP) of a lattice in the worst case. Therefore, the LWE assumption can be used to guarantee the one-way property for encryption with semantic security.Definition 3.
(Inner product predicate). The inner product predicatePn,q is defined on the Cartesian product K×I that(4)Pn,qv⟶,w⟶=1,∑i=1,…,nviwi=0,0,other.
From the perspective of functional encryption (FE), I can be deemed as the space of ciphertexts andK is composed of secret keys. Once a correct key v⟶ is known, we are able to learn the output of function Pn,qv⟶,w⟶.
To construct an attribute-based access control policy, the access structure is coded as a vectorw⟶, thus the access authority can be verified with respect to the consistency of authorization certificate v⟶.To avoid obfuscation, the symbols used in this paper is listed in advance, as in Table 1.Table 1
Symbols and notations.
SymbolNotationfLength of a filebLength of each file blockgLength of the hash valueNNumber of users participating in key aggregationKTotal number of bloom filtersLLength of bloom filter arrayQ(n)Number of common attributes in a user groupnNumber of attributes for an individual userHashComputational cost of performing a hash functionCE_KComputational cost of performing a key aggregationEncComputational overhead of performing a symmetric encryptionPoWComputational cost of performing a proof of ownershipAddComputational cost of performing an addition


## 3. Duplication Check Based on LWE

To prevent dictionary attacks caused by the exposure of deduplication labels, we intended to make them indistinguishable except for the process of duplication check. Therefore, LWE is adopted to randomize the hash value of file to ensure the indistinguishability of deduplication labels and resist the attacks of quantum computation. In addition, we exploit inner product predicate to control the accessibility of clients, which is flexible for functions such as cross-user sharing and ownership transfer. The logical idea of our scheme is illustrated below, which is shown in Figure1.Figure 1
The overall framework of the deduplication program.


## 4. File Upload

A user denoted asA, who possesses a file MA and expects to upload it, is not aware of its existence over cloud at the very beginning. To avoid unnecessary storage and bandwidth, he is supposed to check if there is a copy already held by the server.Drawing support from any strong-collision resistant hash function(5)H:0,1∗⟶0,1ℓ,the user figures out the hash value of file MA as(6)hA=HMA,and codes it as a vector of ℓ elements. On fixed public matrix P∈ℤqn×m and a pseudorandom sequence generator (PSRG), he produces a vector(7)s⟶A=PSRGhA,−1∈ℤqn+1,and exploits LWE to obtain(8)vA⟶=P,bA⋅rA∈ℤqn+1.Herein,bA=PSRGhAP+eAq stands for the last row of P,bA, where PSRGhA is considered as a n dimensional vector and rA is randomly chosen from −1,0,1m.To this point, the user is ready to take the n+1 dimensional vector vA⟶ as a deduplication label and upload it to the cloud. Since the subsequent actions he should take depend directly on the result of duplication check, we will discuss the situations for original uploader and repeated uploader, respectively, who are denoted as A and B for clarity.


### 4.1. The Process of Original Uploading

We defer the description of duplication check to the circumstance of repeated upload, if suppose that userA is informed with the inexistence of file MA. For further deduplication, he should secretly upload the deduplication certificate sA⟶ to the cloud. To ensure the confidentiality of his file, its hash value can be taken as a symmetric key skA=hA to hide the plaintext as(9)EncskAMA=CA.Then, the cloud preserves the uploaded ciphertextCA for storage and the deduplication certificate sA⟶ for duplication check. To further retrieve the file, user A ought to upload a downloading certificate as well, like the following.Assuming that the attributes of userA correspond to a secret vector μA⟶=μA,0,μA,1,…,μA,n−1∈Zqn, which can also be regarded as a polynomial(10)fμA⟶=μA,0+μA,1x+⋯+μA,n−1xn−1modq.It is worth mentioning that the user is aware of the elements ofμA⟶ only if he corresponds to those attributes. To actualize a functional encryption which reflects the access structure in covert manner, he uniformly samples two vectors wii=0,1,…,n−2 and uA⟶=uA,0,uA,n−1,uA,n−2,…,uA,1. Similarly, the vector uA⟶=uA,0,uA,n−1,…,uA,1∈Zqn can also be expressed as a polynomial guA⟶=uA,0+uA,n−1x+⋯+uA,1xn−1modq, which is equivalent to a cyclic matrix(11)UA=uA,0uA,n−1⋯uA,1uA,1uA,0⋯uA,2⋮⋮⋯⋮uA,n−1uA,n−2⋯uA,0∈Zqn×n,with respect to the homorganic between polynomials and cyclic matrices.In order to construct the correct downloading certificate, he computesUA⋅μA⟶=XA⟶=xA,0,xA,1,…xA,n−1T and figures out wn−1 for <XA⟶,w⟶>=0modq by(12)wn−1=−∑i=0n−2xA,iwixn−1modq.After that, the user uploadsw⟶=w0,w1,…,wn−1 as the downloading certificate and submits(13)y=wn−2xA,n−2+wn−1xA,n−1=−∑i=0n−3wixA,i,to the cloud for further expansions on access structure.At the end, the user preserves the hash valueskA, the essential elements uA⟶=uA,n−1,…,uA,1,uA,0 of matrix UA, and the replied link of outsourced file. While the ciphertext CA can be held by the cloud server, attached with sA⟶,y, and w⟶ for duplication check, access expansion, and ownership proof.


### 4.2. The Process of Repeated Uploading

As mentioned before, once a deduplication label is figured out, any user should firstly hand it over to the cloud for duplication check. Assume that the deduplication certificate of an existing fileMA is sA⟶, the cloud can inspect its consistency with another deduplication label vB⟶ as the following:When userB expects to upload his file MB, he submits its deduplication label vB⟶=P,bB⋅rB to the cloud and keeps the hash value hB private.Based on an outsourced deduplication certificatesA⟶, the cloud computes within a lifted interval −q−1/2,q−1/2 which is as follows:(14)<sA⟶,vB⟶>=<PSRGhAP−PSRGhBP−eB,rB>.It can be seen that, if the two files are identical, only−eB,rB will remain in formula (14). Therefore, when the result satisfies(15)sA⟶,vB⟶∞≤αq,the cloud can ensure the duplication of file MB with negligible false positive.To validate his accessibility, userB should also figure out the downloading right of the corresponding file. However, it is more reasonable to use existing download rights w⟶ held by the cloud server for the purpose of storage saving. Based on this, user B can use the following subprotocol to obtain the download right of the duplicate file, and the cloud will simply send the link back to him for further retrieval.


### 4.3. The Subprotocol for Access Expansion

Denoting the secret corresponding to the attributes of repeated uploaderB as μB⟶=μB,0,μB,1,…,μB,n−1T. To bind the access structure with his own attributes, he should also figure out a cyclic matrix UB which can be used to compute his proof of ownership which is as follows:(16)<UB⋅μB⟶,w⟶>=0.Though the downloading certificatew⟶ cannot be exposed to prevent unauthorized access, the cloud can provide user B with the values of wn−3,wn−2,wn−1 and y to help him calculate the correct cyclic matrix UB. Thus, the downloading right can be carried out by user B in Algorithm 1.Algorithm 1: Calculation process chart of repeated file.
UserBInput: wn−3,wn−2,wn−1,y,μB⟶(1)
SamplesuB⟶=uB,0,uB,n−1,uB,n−2,…,uB,1, where uB,i is irreversible and cofficients belong to ℤq(2)
ComputesfμB⟶←μB⟶, guB⟶←uB⟶, xB,0←guB⟶⋅fμB⟶for allk∈1,…,n−1guB,k⟶←guB⟶⋅xmodxn, xB,k←guB,k⟶⋅fμB⟶, uB⟶←uB,k⟶, k←k+1(3)
Computesy′←wn−2⋅xB,n−2+wn−1⋅xB,n−1, xB,n−3′←xB,n−3−y−y′/wn−3(4)
SamplesxB,n−2′←$ℤqn, xB,n−2←xB,n−2′; and computes xB,n−1←y−wn−2⋅xB,n−2′/wn−1(5)
For allk∈1,…,n−1(6)
uB,iμB,0+uB,i+n−1modnμB,1+⋯+uB,i+1modnμB,n−1←xB,iOutput: uB⟶=uB,n−1,…,uB,1,uB,0


## 4.1. The Process of Original Uploading

We defer the description of duplication check to the circumstance of repeated upload, if suppose that userA is informed with the inexistence of file MA. For further deduplication, he should secretly upload the deduplication certificate sA⟶ to the cloud. To ensure the confidentiality of his file, its hash value can be taken as a symmetric key skA=hA to hide the plaintext as(9)EncskAMA=CA.Then, the cloud preserves the uploaded ciphertextCA for storage and the deduplication certificate sA⟶ for duplication check. To further retrieve the file, user A ought to upload a downloading certificate as well, like the following.Assuming that the attributes of userA correspond to a secret vector μA⟶=μA,0,μA,1,…,μA,n−1∈Zqn, which can also be regarded as a polynomial(10)fμA⟶=μA,0+μA,1x+⋯+μA,n−1xn−1modq.It is worth mentioning that the user is aware of the elements ofμA⟶ only if he corresponds to those attributes. To actualize a functional encryption which reflects the access structure in covert manner, he uniformly samples two vectors wii=0,1,…,n−2 and uA⟶=uA,0,uA,n−1,uA,n−2,…,uA,1. Similarly, the vector uA⟶=uA,0,uA,n−1,…,uA,1∈Zqn can also be expressed as a polynomial guA⟶=uA,0+uA,n−1x+⋯+uA,1xn−1modq, which is equivalent to a cyclic matrix(11)UA=uA,0uA,n−1⋯uA,1uA,1uA,0⋯uA,2⋮⋮⋯⋮uA,n−1uA,n−2⋯uA,0∈Zqn×n,with respect to the homorganic between polynomials and cyclic matrices.In order to construct the correct downloading certificate, he computesUA⋅μA⟶=XA⟶=xA,0,xA,1,…xA,n−1T and figures out wn−1 for <XA⟶,w⟶>=0modq by(12)wn−1=−∑i=0n−2xA,iwixn−1modq.After that, the user uploadsw⟶=w0,w1,…,wn−1 as the downloading certificate and submits(13)y=wn−2xA,n−2+wn−1xA,n−1=−∑i=0n−3wixA,i,to the cloud for further expansions on access structure.At the end, the user preserves the hash valueskA, the essential elements uA⟶=uA,n−1,…,uA,1,uA,0 of matrix UA, and the replied link of outsourced file. While the ciphertext CA can be held by the cloud server, attached with sA⟶,y, and w⟶ for duplication check, access expansion, and ownership proof.


## 4.2. The Process of Repeated Uploading

As mentioned before, once a deduplication label is figured out, any user should firstly hand it over to the cloud for duplication check. Assume that the deduplication certificate of an existing fileMA is sA⟶, the cloud can inspect its consistency with another deduplication label vB⟶ as the following:When userB expects to upload his file MB, he submits its deduplication label vB⟶=P,bB⋅rB to the cloud and keeps the hash value hB private.Based on an outsourced deduplication certificatesA⟶, the cloud computes within a lifted interval −q−1/2,q−1/2 which is as follows:(14)<sA⟶,vB⟶>=<PSRGhAP−PSRGhBP−eB,rB>.It can be seen that, if the two files are identical, only−eB,rB will remain in formula (14). Therefore, when the result satisfies(15)sA⟶,vB⟶∞≤αq,the cloud can ensure the duplication of file MB with negligible false positive.To validate his accessibility, userB should also figure out the downloading right of the corresponding file. However, it is more reasonable to use existing download rights w⟶ held by the cloud server for the purpose of storage saving. Based on this, user B can use the following subprotocol to obtain the download right of the duplicate file, and the cloud will simply send the link back to him for further retrieval.


## 4.3. The Subprotocol for Access Expansion

Denoting the secret corresponding to the attributes of repeated uploaderB as μB⟶=μB,0,μB,1,…,μB,n−1T. To bind the access structure with his own attributes, he should also figure out a cyclic matrix UB which can be used to compute his proof of ownership which is as follows:(16)<UB⋅μB⟶,w⟶>=0.Though the downloading certificatew⟶ cannot be exposed to prevent unauthorized access, the cloud can provide user B with the values of wn−3,wn−2,wn−1 and y to help him calculate the correct cyclic matrix UB. Thus, the downloading right can be carried out by user B in Algorithm 1.Algorithm 1: Calculation process chart of repeated file.
UserBInput: wn−3,wn−2,wn−1,y,μB⟶(1)
SamplesuB⟶=uB,0,uB,n−1,uB,n−2,…,uB,1, where uB,i is irreversible and cofficients belong to ℤq(2)
ComputesfμB⟶←μB⟶, guB⟶←uB⟶, xB,0←guB⟶⋅fμB⟶for allk∈1,…,n−1guB,k⟶←guB⟶⋅xmodxn, xB,k←guB,k⟶⋅fμB⟶, uB⟶←uB,k⟶, k←k+1(3)
Computesy′←wn−2⋅xB,n−2+wn−1⋅xB,n−1, xB,n−3′←xB,n−3−y−y′/wn−3(4)
SamplesxB,n−2′←$ℤqn, xB,n−2←xB,n−2′; and computes xB,n−1←y−wn−2⋅xB,n−2′/wn−1(5)
For allk∈1,…,n−1(6)
uB,iμB,0+uB,i+n−1modnμB,1+⋯+uB,i+1modnμB,n−1←xB,iOutput: uB⟶=uB,n−1,…,uB,1,uB,0


## 5. Proof of Ownership

Once any legal user obtained his downloading right, he should be authorized to retrieve the corresponding file from the cloud. To improve the efficiency of ownership proof, access authorization is executed in a computational way.After uploading, the legal userA will be provided with the last row uA⟶=uA,n−1,…,uA,1,uA,0 of the cyclic matrix. Therefore, he only needs to form the cyclic matrix UA and combines it with his attribute vector uA⟶ to figure out the downloading right. Based on the resulted vector, the cloud can easily verify his accessibility by functional encryption. The process of PoW is completely given in Algorithm 2.Algorithm 2: Process chart of PoW for the original file user.
User AInput: uA⟶,μA⟶,n,skA(1)
ComputesfμA⟶←μA⟶, guA′⟶←guA⟶⋅xmodxn,uA⟶←uA′⟶, xA,0←guA⟶⋅fμA⟶(2)
ComputesfμB⟶←μB⟶, guB⟶←uB⟶;xB,0←guB⟶⋅fμB⟶(3)
For allk∈1,…,n−1guA,k⟶←guA⟶⋅xmodxn, xA,k←guA,k⟶⋅fμA⟶uA⟶←uA,k⟶, k←k+1(4)
SendsXA⟶=xA,0,xA,1,…,xA,n−1 to Cloud.CloudInput: w⟶,XA⟶,CA,α,q(5)
Computes<w⟶,XA⟶>←∑i=0n−1wi⋅xA,i(6)
If<w⟶,XA⟶>=0Output: CA,wn−3,wn−2,wn−1,y; OtherwiseOutput: NULL.(7)
SendsCA,wn−3,wn−2,wn−1,y to User AAfter obtaining the ciphertextCA, user A can decrypt the file by computing DecskACA=MA because he is aware of the secret key skA=HMA.In fact, the ownership proof process for userB is similar to that of user A. The reason why user B can also decrypt the file CA is due to the equality of plaintexts MA and MB. Since skB=HMA he is able to obtain the corresponding file via DecskBCA=MA.


## 6. Downloading Right Transfer

On noting that, without the secret vectors corresponding to the attributes of legal users, other users are incapable of computing the downloading right even if the last row of cyclic matrix is known. Since the access controls subprotocol, any legal user can directly transfer the resultant downloading right to other users to avoid redundant operations such as peer to peer transmission. However, it may lead to the abuse of downloading right and violate the confidentiality of user’s attributes. Practically, legal users are prone to transfer the downloading right of their file to others who share party of common attributes with him. Therefore, we designed a protocol that any legal user can update the downloading right and transfer it to a group of users with the same set of attributes. In this way, the owner does not have to download the file from the cloud and only needs to transfer the downloading right to other users to complete file sharing, which effectively reduces the consumption of communication bandwidth.Definition 4.
(Common attributes vector). Suppose that the file ownerA can be identified by attributes vector μA⟶=μA,0,μA,1,…,μA,n−1, and all users in the same group have Qn common attributes denoted by μall⟶=μall,0,…,μall,n−1,…,μall,Qn. Then, the common attributes vector μteam⟶=μteam,0,…,μteam,n−1 can be defined as a partial ordering relation that μteam,i=μA,i if μA,i∈μtall,j|j=0,…,Qn and μteam,i=0, otherwise.
Specifically, the process that the userA constructs the common attribute vector μteam⟶=μteam,0,μteam,1,…,μteam,n−1 is detailed in Figures 2 and 3.
As shown in Figures2 and 3, the user A mainly retains the secret attributes shared by the same group and sets the attributes which are distinct in the user group as 0. Finally, he outputs a common attribute vector μteam⟶.Figure 2
Common attributes.Figure 3
Noncommon attributes.


### 6.1. Proof of Ownership

The userA performs the following steps to realize the PoW and retrieves wn−3,wn−2,wn−1 and y.If the downloading right is valid, the inner product will result in 0, meaning that the user A is authorized to retrieve the file. Therefore, the cloud server returns CAwn−3,wn−2,wn−1 and y back to him. Similarly, the values of wn−3,wn−2,wn−1 and y can be used to update the downloading right for a group of users. Specifically, the process of PoW is shown in Algorithm 2, which is the same for any valid user even if the updated downloading right is used.


### 6.2. Update the Downloading Right

To share the file to a group, the downloading right update process can be carried out by the userA as the following. In a clear form, the process that the user A calculates the downloading right for a group of users is shown in Algorithm 3.Algorithm 3: Calculation process chart of common downloading right.
User AInput: μteam⟶,n,wn−3,wn−2,wn−1,y(1)
Samplesuteam⟶=uteam,0,uteam,1,…,uteam,n−1, where uteam,0 is irreversible with cofficients belong to ℤq(2)
Computesfμteam⟶←μteam⟶for allk∈1,…,n−1guteam,k⟶←guteam⟶⋅xmodxn+1; xteam,n−k−1←guteam,k⟶⋅fμteam⟶; uteam⟶←uteam,k⟶; k←k+1(3)
Computesy′←wn−2⋅xteam,n−2+wn−1⋅xteam,n−1(4)
Computesxteam,n−3′←xteam,n−3−y−y′/wn−3(5)
Samplesxteam,n−2′←$ℤqn, xteam,n−2←xteam,n−2′, and Computes xteam,n−1←y−wn−2⋅xteam,n−2′/wn−1(6)
For allk∈1,…,n−1uteam,i⋅μteam,0+uteam,i+n−1modn⋅μteam,1+⋯+uteam,i+1modn⋅μteam,n−1←xteam,iOutput: uteam⟶=uteam,0,uteam,n−1,…,uteam,1


### 6.3. Sharing the Downloading Right

After the previous two stages, the userA can share the vector uteam′⟶=uteam,n−1′,…,uteam,1′,uteam,0′ and the secret key skA to all users who are within the same attributes set. In these ways, a group of users are provided with the downloading right, which can be valid if the common attributes vector μteam⟶ is known.


## 6.1. Proof of Ownership

The userA performs the following steps to realize the PoW and retrieves wn−3,wn−2,wn−1 and y.If the downloading right is valid, the inner product will result in 0, meaning that the user A is authorized to retrieve the file. Therefore, the cloud server returns CAwn−3,wn−2,wn−1 and y back to him. Similarly, the values of wn−3,wn−2,wn−1 and y can be used to update the downloading right for a group of users. Specifically, the process of PoW is shown in Algorithm 2, which is the same for any valid user even if the updated downloading right is used.


## 6.2. Update the Downloading Right

To share the file to a group, the downloading right update process can be carried out by the userA as the following. In a clear form, the process that the user A calculates the downloading right for a group of users is shown in Algorithm 3.Algorithm 3: Calculation process chart of common downloading right.
User AInput: μteam⟶,n,wn−3,wn−2,wn−1,y(1)
Samplesuteam⟶=uteam,0,uteam,1,…,uteam,n−1, where uteam,0 is irreversible with cofficients belong to ℤq(2)
Computesfμteam⟶←μteam⟶for allk∈1,…,n−1guteam,k⟶←guteam⟶⋅xmodxn+1; xteam,n−k−1←guteam,k⟶⋅fμteam⟶; uteam⟶←uteam,k⟶; k←k+1(3)
Computesy′←wn−2⋅xteam,n−2+wn−1⋅xteam,n−1(4)
Computesxteam,n−3′←xteam,n−3−y−y′/wn−3(5)
Samplesxteam,n−2′←$ℤqn, xteam,n−2←xteam,n−2′, and Computes xteam,n−1←y−wn−2⋅xteam,n−2′/wn−1(6)
For allk∈1,…,n−1uteam,i⋅μteam,0+uteam,i+n−1modn⋅μteam,1+⋯+uteam,i+1modn⋅μteam,n−1←xteam,iOutput: uteam⟶=uteam,0,uteam,n−1,…,uteam,1


## 6.3. Sharing the Downloading Right

After the previous two stages, the userA can share the vector uteam′⟶=uteam,n−1′,…,uteam,1′,uteam,0′ and the secret key skA to all users who are within the same attributes set. In these ways, a group of users are provided with the downloading right, which can be valid if the common attributes vector μteam⟶ is known.


## 7. Correctness Proof

The previous section is mainly composed of three parts, namely, the file uploading, the proof of ownership, and the downloading right transfer. To verify the correctness of our design, this section intends to prove that file duplication can be effectively eliminated and only authenticated users can access the file.Firstly, the correctness for the deduplication label is given by Theorem1.Theorem 1 (Correctness of deduplication label).
Suppose that the cloud holds a deduplication certificatesA⟶ which is correspondent to file MA. After the user B uploaded the deduplication label vB⟶ before outsourcing the same file MA, the cloud can perform deduplication correctly with negligible false positive.Proof.
Due to the deduplication certificatesA⟶=PSRGhA,−1∈ℤqn+1 stored on the cloud, where hA=HMA. After the user B uploaded the deduplication label vB⟶=P,bB⋅rB∈ℤqn+1 of the same file MA to the cloud for bB=PSRGhB+eB, the cloud executes the following calculation on each deduplication certificate. Once sA⟶ is met, the inner product can be carried out as follows:(17)<sA⟶,vB⟶>=PSRGhA︸nbits,−1⋅P︸n×mbB︸1×mn+1×m⋅rB=PSRGhA︸1×n,−1⋅P︸n×mbB︸1×mn+1×m⋅rB=PSRGhA⋅P−bB⋅rB=<PSRGhA⋅P−PSRGhB⋅P+eB,rB>=<PSRGhA⋅P−PSRGhB⋅P−eB,rB>.
SincePSRG⋅ is a deterministic algorithm, when hA=hB,PSRGhA=PSRGhB. Meanwhile, according to the common matrix P, it is obvious that PSRGhA⋅P=PSRGhB⋅P. Thus, we can easily see that sA⟶,vB⟶=−eB,rB from equation (17). Because the inner product of <−eB,rB>≤1/Qm is definite, the inner product of <sA⟶,vB⟶>≤1/Qm can also be guaranteed, meaning that duplication can be detected with 100% probability.Theorem 2 (Correctness of download right).
Suppose that the cloud possesses a downloading certificatew⟶ corresponding to file MA, then any legal user can correctly pass the procedure of PoW in terms of his downloading right.Proof.
For userA, who uploads the original file MA to the cloud, he rotates uA⟶=uA,n−1,…,uA,1,uA,0 to right by one bit to get uA′⟶=uA,0,uA,n−1,…,uA,1 and uses it to reconstruct the cyclic matrix UA. Then, user A calculates download right(18)XA⟶=UA⋅μA⟶=xA,0,xA,1,…xA,n−1T,where μA⟶=μA,0,μA,1,…,μA,n−1 are the attributes of the user A. After which the user A sends the download right XA⟶ to the cloud. Finally, the cloud calculates the inner product of(19)<w⟶,XA⟶>=∑i=0n−1wi⋅xA,i=∑i=0n−2wi⋅xA,i+wn−1⋅xA,n−1=∑i=0n−2wi⋅xA,i+−∑i=0n−2wi⋅xA,i=0.
Based on the last element of download certificatew⟶ is wn−1=−∑i=0n−2xA,iwi/xn−1modq, so that the result of wn−1xA,n−1 can transfer as −∑i=0n−2wixA,i. Therefore, the inner product of XA⟶,w⟶ is zero. For the repeated file user B, the first two steps are the same for the user B.
Then, he also gets the result of download rightXB⟶ and sends it to the cloud. Moreover, the inner product of w⟶,XB′⟶ calculates the process as follows:(20)<w⟶,XB′⟶>=w⟶⋅xB,0,xB,0,…,xB,n−3′,xB,n−2′,xB,n−1′T=∑i=0n−4wixB,i+wn−3xB,n−3′+wn−2xB,n−2′+wn−1xB,n−1′=∑i=0n−4wixB,i+wn−3xB,n−3′+y=∑i=0n−4wixB,i+wn−3xB,n−3+y′−y+y=−y′+y′−y+y=−y+y=0.
In a word, all legal users who hold the download right corresponding to fileMA can pass the PoW.


## 8. Security Analysis

This part will prove that the deduplication label is indistinguishable except for duplication check process, and the downloading right is resistant to forgery. To begin with, the security about deduplication label is given in Theorem3.Theorem 3 (Security of deduplication label).
For legitimate users, whether uploading the same or different files to perform deduplication, the deduplication labels are only distinguishable to the duplication check process.Proof.
The following analysis will be divided into two cases, with respect to the deduplication labels corresponding to same files and different files.Case 1. Supposing userA and user B possess the same file. They have the same hash value hA=hB of two identical files, and their deduplication labels are(21)vA1⟶=PSRGhA⋅P+eA1⋅rA1,vB1⟶=PSRGhB⋅P+eB1⋅rB1.According to the deterministic algorithmPSRG⋅, we can see PSRGhA=PSRGhB. Moreover, for the common matrix P, it is obvious that PSRGhA⋅P=PSRGhB⋅P. However, eA,eB and rA,rB are randomly sampled from χqm and −1,0,1m, respectively. The probability that the deduplication labels are identical is 1/3qm<1/Qm, which is negligible. Therefore, we claim that the results vA1⟶=vB1⟶ is almost impossible, which means vA1⟶ and vB1⟶ satisfy semantic security.Case 2. Supposing userA and user B possess different files. That is to say, they have different file hash values that hA≠hB, and the deduplication labels are(22)vA2⟶=PSRGhA⋅P+eA2⋅rA2,vB2⟶=PSRGhB⋅P+eB2⋅rB2.
Similarly, sincePSRGhA≠PSRGhB, the probability that deduplication labels are the same is 1/n+13qm<1/Qm, which is indistinguishable from the distribution of Case 1.
Therefore, we can conclude that, since the deduplication labels of the same file are different, Case1 is of the same distribution indistinguishable from Case2, and the deduplication labels are semantic secure. In summary, the deduplication tags corresponding to the same file and different files are indistinguishable.Theorem 4 (Security proof of downloading right).
None of the users can forge a valid downloading rightXA⟶ which can deceive access control.Specifically, the security analysis of the downloading right can be guided by Lemmas1 and 2.Lemma 1.
After the original uploaderA outsourced the file MA to the cloud, the entire download certificate w⟶ is known only by the cloud.Proof.
According to inner product predicate, the userA's downloading right XA⟶ can make the inner products XA⟶,w⟶ output 0.
However, the download certificatew⟶ is calculated by the user A who samples wii=0,…,n−2 and sets the last element wn−1 of the download certificate w⟶ to be wn−1=−∑i=0n−2xA,iwi/xn−1modq.
Then, when the userA uploads for the first time, the cloud obtains the completed download certificate w⟶ corresponding to A’s secret attributes. For now, if there is an illegal user who tries to falsify the download certificate w⟶←$ℤqn to cheat the PoW system, his advantage is(23)Pr<XA⟶,w′⟶>=0=1qn−1≤1Qn,which is negligible.Lemma 2.
For repeated file uploaders, they do not know the remaining elements of the download certificatew⟶ except for wn−3,wn−2,wn−1.Proof.
Take a repeated file uploaderB as an example, he uses wn−3,wn−2,wn−1 to update the last three elements of download right XB⟶ into xB,n−3′,xB,n−2′,xB,n−1′.
In detail,(24)xB,n−3′=xB,n−3−y−y′wn−3,(25)wn−2xB,n−2′+wn−1xB,n−1′=y.
Since the value ofwn−3 is known, the result of xB,n−3′ can be calculated. However, because the rank of formula (25) is equal to 1 and wn−2xB,n−2′+wn−1xB,n−1′=y, the formula of (25) contains two unknowns variables. Thus, the results of xB,n−2′ and xB,n−1′ are infinite. Therefore, when the user B calculates the downloading right, he does not know the remaining elements of the download certificate w⟶ except for wn−3,wn−2,wn−1.
Considering that the solutions of formula (25) are infinite, the security of downloading right can be effectively protected, namely, XB⟶ of the user B. Thus, it also guarantees the confidentiality of legal users’ attributes. If an illegal user attempts to forge the remaining n−3 elements of w⟶ to get the new download certificate w″⟶=w0′′,…,wn−4′′,wn−3…,wn−1, his advantage is just(26)Pr<XB′⟶,w″⟶>=0=1qn−3≤1Qn,which is negligible. Therefore, our scheme will not expose the remaining elements of the download certificate w⟶.
In terms of Lemmas1 and 2, it can be seemed that no user can forge a valid downloading right since the complete download certificate and the attributes vector μA⟶ will not be exposed.


## 9. Performance Analysis

Then, the performance of our schemes will be analysed comparing with other main technologies. The notation of symbols can be found in Table1, as for functions, such as the necessity of third-party, deduplication level, participants, and the necessity of key fusion, and the comparison can be found in Table 2.Table 2
Function comparison between main data deduplication schemes.
SchemesTechnologyTTPLevelObjectKey fusion[8]BL-MLE + PoW—BlockSingle userYes[3]Threshold blind signature + verifiable secret sharingKey serversFileSingle userYes[2]Authentication protocol + authorization detectionCloud serverFileMultiple usersYes[9]Attribute encryption + random samplingAttribute centerBlockMultiple usersYesThis paperAttribute access policy + inner product predicate—FileMultiple usersNoCompared with the schemes from [2, 3, 9], our scheme does not require any third-party, which effectively avoided extra trusting relationships and can save numerous computation/communication resources. Moreover, our scheme executes file deduplication amongst multiple users, implying that it is more flexible and more adaptive to various cloud environment. From the perspective of key fusion, when compared with the literature from [2, 3, 8, 9], any key fusion process is unnecessary in our scheme, so that it can be applied even if the user resources are limited.Then, we compare the computation overheads for deduplication taken by the client, third-party, and cloud in the above schemes. The details are given in Table3.Table 3
Computation overheads for deduplication.
SchemesClientTTPCloud[8]ObHash⋅Hash—ObPoW[3]OfHash+ONCE_KOfHashOg[2]OfOf—[9]OfHash+OfPoWOfHashOfPoWThis paperOfHash+O1PSRG—OgCompared with the cost on client side in scheme [3], that of our scheme is OfHash+O1PSRG, where a pseudorandom number sequence is generated instead of N convergence keys. In fact, it means that our scheme is more efficient since PSRG can be iterated generated via small numbers, not saying that our scheme if free of any third-party. Moreover, the hash value of file can be secretly used as the encryption key in this paper. Therefore, there is no need for multiple users to reconstruct the convergence key, which further outperformed the scheme of [3] by avoiding the consumption of key distribution and fusion.Compared with the schemes in [8, 9], our method does not need to construct Bloom filter or attribute binary tree on client side, so the computational cost is slightly advantageous. In addition, since our scheme does not involve any third-party, the computational cost of TTP can be neglected. As for the overhead on cloud side, our scheme does not have to initialize any ownership data structure compared with that of schemes [8, 9]. Therefore, the calculation is deduced to Og since it is not related to the file size but only to the length hash value.Now, we compare the computational overhead for PoW, respectively on client, third-party and cloud side. The results are shown in Table4.Table 4
Computation overheads for PoW.
SchemesClientTTPCloud[8]ObHash+Ob—OfAdd[3]OfHash+OkLONCE_KOkLfAdd[2]Of+OkL—OkLfAdd[9]OfHash+ONlogNONCE_KOkLfAddThis paperOfHash+OnAdd—OnAddIt can be seen from Table4 that users have to preserve and search the Bloom filter or attribute binary tree to accomplish PoW in [2, 3, 8, 9]. So, there is an additional cost OkL or ONlogN on the client side. However, our scheme does not require this process, so the calculation cost is only OfHash+OnAdd, where the second term is just n times of add operation. Comparing the cost on cloud side, our scheme dose also outperformed that of [2, 3, 8, 9], which is OnAdd. The reason is similar that the calculation cost on cloud side has nothing to do with the file size but only the number of attributes.Finally, taking the file of 256 bits as an example, we compare the communication overhead for deduplication and PoW amongst the same set of schemes. The details are shown in Figure4.Figure 4
Histogram of communication cost of similar schemes.According to Figure4, our scheme has obvious advantage on communication overheads compared with other schemes. Our solution can effectively reduce the usage of bandwidth as well as time delay. Moreover, since all deduplication check and ownership proof processes are independent, our scheme is capable of parallel processing, which is more fit for batch implementation.


## 10. Conclusions

This paper proposed a novel deduplication scheme based on LWE and FE to balance the conflict between the accessibility and the indistinguishability of data. Focusing on the purpose of deduplication check, LWE is exploited to construct deduplication labels which are distinguishable only if their deduplication certificates are known. To realize more efficient and flexible access control, inner product predicate is used that data can be retrieved only if both users downloading right and attributes vector are possessed. Thanks to the separation of downloading right and user’s attributes, the downloading right can be recalculated for repeated uploading and authorization transfer without changing the corresponding deduplication label or download certificate over cloud. Correctness and security analyses proved that deduplication can be accomplished only by the duplication check process with negligible false positive, and it is almost impossible for any adversaries to fabricate a legal downloading right. Compared with other main technologies, our scheme is more applicable to multiuser environment and freed from trusted third-party. Since both duplication check and ownership proof are realized by inner product, the performances of computation and communication are more advantageous in our method, not mentioning its capacity of batch processing due to parallelism.



---

*Source: 6662662-2020-12-10.xml*