A) Introduction to POR and PDP

As s widely studied mechanism to ensure data integrity, POR was firstly proposed by Juels and Kaliski in 2007 [Reference Juels and Kaliski9]. Figure 2 depicts the general schematic of the proposed POR system, which ensures the server (prover) to a client (verifier) that the stored data are intact during the storing and retrieving process of the client. The client first encode a raw file F through an encoding algorithm into an encoded file F' and then stores it in the prover. A key generation algorithm produces a key K stored in the verifier, and it is used to encode. For the checking process, the verifier can perform challenge–response process with prover in order to check if F can be retrieved.

Fig. 2. Schematic of a POR system [9].

The first POR scheme introduced by Juels and Kaliski employed a sentinel scheme. POR protocol encrypts F and inserts randomly several sentinels into the other file data blocks after encryption. These sentinels play an crucial role for verification. The verifier can challenge the prover by pointing out the positions of a collection of sentinels, and the prover should return the values of the sentinels. If the values are different from the verifier's data, then it shows that prover has deleted or modified F. POR also includes error-correcting code to recover a small portion F if corrupted. However, this scheme requires pre-processing and encoding of F prior to store into the data storage, and it is bounded use – number of sentinels can be used up for limited queries. Therefore, Juels and Kaliski proposed another technique from Lillibridge et al. [Reference Lillibridge, Elnikety, Birrell, Burrows and Isard10], Naor and Rothblum [Reference Naor and Rothblum11]. It stores the redundantly encoded data blocks with message authentication code (MAC) to replace sentinels, and the MACs are stored together with data blocks. In this case, verification algorithm can examine the data integrity and ensures retrievability by requesting random number of block positions with their MACs. This approach resolves bounded use problem of the previous scheme, but at the cost of higher communication complexity of the audit.

On the other hand, PDP came out concurrently with Juels–Kaliski's scheme. It was proposed by Ateniese et al. [Reference Ateniese12] and constructed based on symmetric key cryptography. PDP firstly chose RSA-based homomorphic verifiable tags [Reference Johnson, Molnar, Song and Wagner13] to combine multiple file blocks into a single value. A similar approach was also adopted later by Shacham and Waters [Reference Shacham and Waters14]'s POR scheme in 2008. PDP scheme also provides data format independence, and it puts no restriction on the format of data. In other words, PDP allows any verifier (not only client) to query the server. POR and PDP both employed erasure code, which is a Forward Error Correction (FEC) for the binary erasure channel, helping recovery of the original message from slightly damaged data. The major difference between initial POR and PDP is that POR ensures not only data integrity at the server end but also retrievability, whereas PDP guarantees only data integrity at cloud data storage. Nevertheless, PDP is more efficient compared to Juels–Kaliski's POR, since it does not require any bulk encryption, and PDP requires smaller storage space on the client side and fewer bandwidths for challenges and responses. However, both schemes work on static data only, even though Ateniese et al. [Reference Ateniese, Di Pietro, Mancini and Tsudik15] proposed a dynamic version later in 2008, but it is restricted by number of queries and basic block operations (Fig. 3).

Fig. 3. Schematic of a PDP system.

B) Improvement on public verifiability

Since the Juels–Kaliski's original POR scheme was proposed without implementation of public verifiability, and its complexity was still high for communication and client storage, it became a popular topic for researchers to improve public verifiability and efficiency (discussed in the next subsection). In 2008, Shacham and Waters [Reference Shacham and Waters14] proposed two new PORs system structures based on Juels–Kaliski's POR concept. Both solutions allow only one authentication value for the purpose of verification. The first one is privately verifiable using pseudorandom functions (PRFs); the second one is publicly verifiable, and it was built based on signature scheme of Boneh, Lynn, and Shacham in a bilinear group [Reference Boneh, Lynn and Shacham16]. Since the BLS signature was adopted, the public retrievability was achieved, and the proofs are reduced to a single authentication value, thus reduced communication complexity from O(t) to O(1), where t is the number of block positions. However, this scheme still works on static data only, without support of dynamic data update. Besides, the security parameter relies on Random Oracles, which means the client's challenge size grows up to O(t ²).

A new system model, as depicted in Fig. 4, which aimed at establishing a trustable mechanism between client and CSS by introducing a Third Party Auditor (TPA), was proposed in 2009 [Reference Wang, Wang, Ren and Lou18]. By using a privacy-preserving third-party auditing protocol, the TPA is trusted to monitor the stored data in cloud and transactions between the client and CSS, as well as assess and expose risks of the cloud services. This new scheme has been further developed based upon existing PORs and newly developed cryptographic primitives [Reference Wang, Wang, Li, Ren and Lou17, Reference Wang, Chow, Wang, Ren and Lou19–Reference Wang, Wang, Ren and Lou22].

Fig. 4. TPA structure [17].

TPA typically adopts a public-key-based homomorphic authenticator with random masking to perform traffic auditing without a local copy of the data for integrity check. This public audit system can be constructed from the setup stage, which allows a user to initialize the secret parameters of the system, send the verification metadata to TPA, and audit the corresponding result. In this process, TPA will issue an audit message to the server for checking the user's data.

Homomorphic authenticators are used to verify metadata generated from individual data blocks while the aggregated authenticators can justify a linear combination of data blocks. As a paradigm, one can use a homomorphic token with distributed verification to check the integrity of erasure-coded data. The erasure-correcting codes play a vital role in preparing files for distribution so that the distributed files have redundancy parity vectors and the data dependability property. However, the linear combination of data blocks may potentially reveal users' privacy. With random masking, TPA cannot derive user's data content by building a correct group of linear equations.

The above model was further improved in [Reference Wang, Wang, Ren, Lou and Li23] by integrating dynamic data support in 2011. Zhu et al. [Reference Zhu, Wang, Hu, Ahn, Hu and Yau24] also proposed a construction of dynamic audit services for untrusted and out-sourced storage. It can detect abnormal behavior by using fragment structure, random sampling, and index-hash table.

Even though TPA-based schemes allows public verification of data integrity checking, They have a potential obstacle that requires an additional constituency, which is a third party auditor, added to the entire existing data storage scheme. The implementation of such schemes might be a burden for service providers because of additional costs. To address this concern, Han and Xin [Reference Han and Xing25] proposed a new scheme offering the traditional TPA functions provided by CSP in a trustful manner. This scheme utilizes RSA and Bilinear Diffie–Hellman techniques, creates message header and mechanisms to achieve authentication process, while reducing complexity of cloud computing. Another work that provides public verifiability without help from the third party auditor was examined in [Reference Hao, Zhong and Yu26] based on the work of Sebe et al. [Reference Sebé, Domingo-Ferrer, Martinez-Balleste, Deswarte and Quisquater27], and it has been proved to be secure from an untrusted server.

C) Improvement on efficiency

Efficiency of POR and PDP has been improved from different aspects of the verification process. For instance, Curtmola et al. [Reference Curtmola, Khan and Burns28] showed how to integrate error-correcting codes with PDP and an adversarial error-correcting code construction similar to PORs. It also enabled PDP scheme to secure multiple replicas over distributed system without encoding each separate replica.

Besides, Dodis et al. [Reference Dodis, Vadhan and Wichs29] provided different solutions of optimized POR schemes under different constraints, such as bounded-use or unbounded-use, knowledge-soundness, or information-soundness. They analyzed the tradeoffs in parameters and security between bounded and unbounded use schemes, and they also compared PORs under different circumstances in detail. It also improved the Shacham–Waters POR scheme by avoiding the usage of Random Oracles, which reduced the challenge size down to be linear in the security parameter, from O(t ²) to O(t).

In addition, a theoretical framework of PORs improvement was concurrently proposed by Bowers et al. [Reference Bowers, Juels and Oprea30]. The model offers an improvement over the protocols of Juels–Kaliski [Reference Juels and Kaliski9] and Shacham–Waters [Reference Shacham and Waters31] by proposing a new variant to achieve lower storage overhead and tolerate higher error rates. The proposed POR scheme also decreased the challenge size to be linear of the security parameter. Another POR scheme was proposed by Kumar and Saxena in 2011 [Reference Sravan Kumar and Saxena32]. It targeted on simplification of Juels–Kaliski's sentinel scheme, making it suitable for limited computational power or small storage at verifier end. For PDP, Ateniese and Burns et al. concluded previous research developments and implementations of PDP in 2011 [Reference Ateniese33], and proposed two improved provably secure PDP schemes with higher efficiency than previous ones.

D) Improvement on dynamic data support

Supporting dynamic data update in data integrity verification schemes are especially challenging. Ateniese et al. [Reference Ateniese, Di Pietro, Mancini and Tsudik15] proposed the first partially dynamic PDP scheme in 2008. This scheme was more efficient in setup and verification phase compared to its previous version in [Reference Ateniese12], since it was only relied on symmetric-key cryptography. On the other hand, it only allowed a limited number of queries and basic block operations with limited functionality. For example, block insertion was not supported. Moreover, public verifiability was not supported either.

In 2009, Erway et al. proposed an improvement on PDP, referred as dynamic provable data possession (DPDP) [Reference Erway, Küpçü, Papamanthou and Tamassia34]. In order to support provable updates on the stored data, this new model utilized authenticated directories based on rank information, and it defined the update as block insertion, modification, or deletion to achieve dynamic PDP scheme. Nevertheless, this scheme maintains skip list [Reference Papamanthou, Tamassia and Triandopoulos35] for tags and stores root metadata in clients side to prevent replay attack, so its computational and communication complexity can be up to O(log t).

The dynamic data updates on POR were first considered in 2009. Wang et al. [Reference Wang, Wang, Li, Ren and Lou17, Reference Wang, Wang, Ren and Lou18] proposed the first scheme that achieved efficient data dynamics of the POR model by utilizing the homomorphic token with distributed verification of erasure-coded data, and manipulation of the Merkle Hash Tree (MHT) [Reference Merkle36], respectively. The first scheme supported block update, delete and append operations only, while the second scheme provided both public verifiability and data dynamics for remote data integrity check, but the verification complexity increased to O(log n) from O(1) as a trade-off, and it achieved partially dynamic instead of fully dynamic. Both schemes also showed a new system model involving TPA.

In addition, Zheng and Xu presented a new POR scheme with a fresh property, namely, fairness, to deal with dynamic data [Reference Zheng and Xu37]. This property prevents unscrupulous clients from accusing a legitimate server about modifying their stored data. This issue arises because of the feature of dynamic data. POR for static data storage can solve this problem simply by asking the verifier to approve and sign digitally when the data has not been stored into the storage. The proposed fair and dynamic proof of retrievability (FDPOR) was mainly composed of two parts, a new authenticated data structure: range-based 2–3 tree (rb23Tree) and a new incremental signature scheme called hash-compress-and-sign. However, FDPOR did not support public verifiability, and complexity for both the verifier and the prover were higher than that of previous PORs.

E) Summary

PORs and PDPs are the major remote data integrity checking protocols proposed in cloud storage systems. The original POR and PDP protocols differs in many aspects. PORs are considered to be more secure compared to PDPs, because it requires encryption of the original data and error correction coding to recover damaged data, whereas PDPs are known for higher efficiency and applicability to large-scale public databases, such as digital libraries. With further improvement of each, the two schemes have been converging toward the same objectives. For example, although public verifiability and homomorphic verifiable tags were first known for PDPs, these characteristics are also applicable to PORs. On the other hand, some PDP variants may also adopt encryption and/or error correction coding tools to strengthen their security measurement. Therefore, it is all about making tradeoffs among security functionalities and efficiency.

In Table 1, we summarize the above reviewed POR and PDP schemes by a thorough comparison of their performances. It is noteworthy that schemes with dynamic data support suffers higher complexities compared to their counterparts. Future research directions include further improvements on efficiency and fully dynamic data support. To improve efficiency of those schemes, reducing communication cost and storage overhead are rightful considerations. However, fully dynamic data support is a challenging objective, because it increases complexity but reduces update information on server-end.

Table 1. Performance comparison for data integrity verification schemes

A) Access control

As mentioned above, access control has been one of the key mechanisms to protect data confidentiality in traditional data networks. It is designed to block unauthorized users and malicious hackers from accessing data. Although the objective of access control in cloud storage does not differ from that in traditional data network, the requirement does change. Traditional access control enforced by the service provider could not stop a curious cloud service provider accessing users' sensitive data, which was stored in the service provider's infrastructure and managed by the service provider. A curious cloud storage server trying to derive sensitive information from its stored data, or from data operations performed by data owner and authorized users, is a new threat model against data confidentiality in cloud storage service. Moreover, a malicious service provider could intentionally leak the data to unauthorized parties for profit, or a malicious attacker could compromise the service provider and get unauthorized access to the data.

To address this challenge, cryptographic access control schemes that shifted the access control agency from the service provider to the users have been proposed. Instead of relying on untrusted service provider to grant access control, users can enforce their own access control by selectively granting different decryption access to a certain part of encrypted data. By means of encryption, the owners of data, i.e., cloud storage users who lost their physical control over their own data could regain their control at the semantic level.

Plutus [Reference Kallahalla, Riedel, Swaminathan, Wang and Fu39] and SiRiUS [Reference Goh, Shacham, Modadugu and Boneh40] are examples of using encryption to secure file sharing on remote untrusted storage. These schemes encrypted different files with different keys, thus changing the problem of access to files to the problem of key management. However, this approach is not scalable when applying to cloud storage, because the complexity of key management increases with the number of files and/or the number of users, which both could be enormous in a cloud storage system. As a large number of users are sharing the same infrastructure in a public cloud storage built upon a complicated network scale, it is crucial to have efficient, scalable and reliable access control mechanism in place.

In the following, we examine recent research on more efficient access control using encryption techniques developed for cloud storage systems.

B) Searchable encryption

With more and more data moving to the cloud storage, it becomes imperative to enable search over the huge amount of data for many user applications. To preserve data confidentiality and integrity, it is necessary to store encrypted data in the cloud storage servers. To perform searching over data, the user has to either store an index locally, or download all the encrypted data, decrypt it and search locally. Neither approach is efficient when the data size grows in the cloud. When users seek to search and download relevant files from a cloud storage system, it is often desirable for the SSP to host search service, because it can minimize the network traffic and reduce management complexity for the users.Therefore, how to perform searching on encrypted databases without the need of decryption has become an increasingly fascinating topic in cloud storage systems. Recently, there have been new cryptographic primitives, called searchable encryption schemes [Reference Boneh, Di Crescenzo, Ostrovsky and Persiano69, Reference Song, Wagner and Perrig70], proposed to address this problem.

The basic idea of searchable encryption schemes is to encrypt a search index generated over a collection of data in such a way that its contents are hidden without appropriate tokens, which can only be generated with a secrete key. Given a token for a keyword, one can retrieve pointers to the encrypted data files that contain the keyword. During the retrieval process, there is no contents of either the data files or the keyword revealed, other than the fact that all the retrieved data files contain one keyword in common.

Searchable encryption schemes, including Symmetric Search Encryption (SSE) [Reference Song, Wagner and Perrig70], Asymmetric Search Encryption (ASE) [Reference Boneh, Di Crescenzo, Ostrovsky and Persiano69] and other improvements on both schemes are reviewed in [Reference Kamara and Lauter71]. SSE employs symmetric cryptographic algorithms, such as block cipher or hash function, therefore is suitable when the party that performs search over the data are also the one who generates it, whereas ASE employs asymmetric cryptographic algorithms such as elliptic curve, thus is also suitable when the party that performs search over the data are different than the one who generates it. Therefore, ASE has wider applications than SSE in cloud storage than SSE. Meanwhile, compared to SSE schemes, ASE can achieve more complex search queries, such as conjunctions of terms, but at the cost of higher complexity and weaker security guarantees [Reference Abdalla72]. Efficient ASE, or ESE scheme was introduced in [Reference Bellare, Boldyreva and O'Neill73] to improve the efficiency when the keywords are hard to guess. However, it is more vulnerable to dictionary attacks.

Since SSE achieves higher efficiency and stronger security, it has been further developed recently. For example, dynamic SSE [Reference Kamara and Papamanthou74, Reference Kamara, Papamanthou and Roeder75] extended the inverted index approach [Reference Curtmola, Garay, Kamara and Ostrovsky76] to allow update of the encrypted index and data files, and to achieve adaptive security against chosen-keyword attacks. Furthermore, Parallel and dynamic SSE [Reference Kamara and Papamanthou74] enables more efficient and scalable construction based on a keyword red-black tree-based multi-map data structure. On the other hand, SSE schemes with improved functionalities but compromised security have been proposed. Kuzu et al. [Reference Kuzu, Islam and Kantarcioglu77] utilized locality sensitive hashing (LSH), which is widely used for fast similarity search in high-dimensional spaces for plain data, and proposed a search scheme to enable fast similarity search in the context of encrypted data. Another approach, which was proposed by Wang and Cao et al. [Reference Wang, Cao, Ren and Lou78] to secure ranked keyword search in encrypted cloud data. This method utilized the Order-Preserving Symmetric Encryption (OPSE) [Reference Boldyreva, Chenette, Lee and O'Neill79, Reference Boldyreva, Chenette and O'Neill80], which achieves both security and privacy-preserving by protecting sensitive weighted information.

For cloud storage that are accessible with multiple users, how to enforce privileges and access control while searching through cloud storage has attracted researchers' attentions. One approach was proposed by Singh et al. [Reference Singh, Srivatsa and Liu81] in 2009 which performs indexing in the trusted enterprise domain, and utilizes the resulting indices systematically with the Access Control Barrel (ACB) [Reference Singh, Srivatsa and Liu82] primitives and concepts of user access hierarchy. This solution improves indexing efficiency and allows transferring the indices to the SSP for hosting, and it can be developed based on the integrity of search results returned by the SSP in the future.

Other than search algorithms on encrypted database, more general computation on encrypted database is a related topic. Secure Computation ON an Encrypted Database (SCONEDB) [Reference Wong, Wai-lok Cheung, Kao and Mamoulis83] was proposed to solve the k-Nearest Neighbor (kNN) computation in an encrypted database utilizing asymmetric scalar-product preserving encryption (ASPE). Besides, SCONEDB can incorporate other existing techniques, such as OPSE for the range query and homomorphic encryption for aggregate queries. CryptDB [Reference Popa, Redfield, Zeldovich and Balakrishnan84] implemented an integrated system that supports more general SQL query operations over encrypted database, by adapting a number of existing and new SQL-aware encryption primitives with different security properties and functionalities. CryptDB dynamically adjusts the encryption strategies using layered onion structures, where each data was dressed in increasingly stronger encryption, such that the outmost layer provides maximum security, whereas inner layers provide more functionality. A trusted proxy determines whether layers of encryption need to be removed when receiving a query from the user application.

C) Fully homomorphic encryption

Homomorphic encryption allows specific algebraic operations to be manipulated on a ciphertext, so it can produce the same encrypted result as the ciphertext of the result of the same (or different but known) operations performed on the plaintext. In other words, the operations to be performed on original data can now be performed on the encrypted ciphertext without knowing the original data. Homomorphic encryption can be categorized into two types: partially homomorphic encryption (PHE) and FHE. PHE allows only one homomorphic operation, either addition (e.g. Paillier [Reference Paillier85]) or multiplication (e.g., unpadded RSA), while FHE supports both addition and multiplication operations. Since the original unpadded RSA algorithm published in 1977, there have been many PHE algorithms developed. However, the partially homomorphic property of an encryption algorithm has rarely been considered advantageous, but rather vulnerable to adaptive CCAs. Therefore, PHE algorithms have been found useful only in limited security applications such as electronic voting systems. On the other hand, since the first FHE algorithm was announced in 2009 [Reference Gentry86], it has been recognized as a huge breakthrough in the computing security field. Practical application of FHE cryptosystems will potentially enable development of computing programs, which runs on encrypted input data to generate encrypted output. These programs can thus be run by untrusted entities without revealing any sensitive information during the computing process.

A homomorphic cryptosystem ε consists of four algorithms, KeyGen _ε, Encrypt _ε, Decrypt _ε, and an Evaluate _ε algorithm. The first three algorithms are defined the same as those in any public-key cryptosystems. The KeyGen _ε (λ) produces key-pair (pk, sk) given a security parameter λ. The Encrypt _ε algorithm takes pk and a plaintext π as input, and it outputs a ciphertext ϕ. The Decrypt _ε takes sk and ϕ as input, and outputs the plaintext π. In addition, the Evaluate _ε algorithm takes as input pk, a circuit C from a permitted set C _ε, and a set of ciphertexts ϕ = (ϕ₁, …ϕ _t ), consequently outputs a ciphertext ϕ. The homomorphic cryptosystem ε is correct for C _ε if for any key-pair (pk, sk) generated by KeyGen _ε (λ), any circuit C ∈ C _ε, any plaintexts π₁, …, π _t , and any ciphertexts ϕ = (ϕ₁, … ϕ _t ) with ϕ _i  → Encrypt _ε (pk, π _i ), it is the case that

$$\eqalign{&If\ \phi \leftarrow Evaluate_{\varepsilon}\lpar pk\comma \; C\comma \; \varphi\rpar \comma \; \cr &then Decrypt_{\varepsilon}\lpar sk\comma \; \phi\rpar \rightarrow C\lpar \pi_{1}\comma \; \ldots \comma \; \pi_{t}\rpar }$$

The computation complexity of all the above algorithms has to be polynomial in the size of C and security level parameter λ, which is defined as all known attacks against the scheme take time at least 2^λ. ε is fully homomorphic if it is homomorphic for all circuits [Reference Gentry86].

A family of schemes ε(d): d ∈ Z ⁺ is leveled fully homomorphic if they all use the same decryption circuit, ε(d) is homomorphic for all circuits of depth at most d (that use some specified set of gates Γ), and the computational complexity of ε(d)'s algorithms is polynomial in λ, d, and (in the case of Evaluate ε(d)) the size of C.

The first FHE scheme proposed by Craig Gentry in 2009 [Reference Gentry86] applies lattice-based cryptography to construct the scheme, where lattice L was a set of points in the n-dimensional Euclidean space R ⁿ with a strong periodicity property. The proposed scheme started from a somewhat homomorphic encryption scheme using ideal lattices, which is limited to “low-degree” polynomials evaluation on encrypted data due to the augment of noise in the ciphertext during evaluation. After this “initial construction” stage, a “squash the decryption circuit” technique was used to modify the scheme to make it “bootstrappable”. The modified encryption scheme can evaluate its own decryption circuit, and effectively refresh the ciphertext to reduce the augmented noises, which eliminates the limitation on the depth of circuit evaluated over the ciphertext. In short, Craig Gentry slightly modified somewhat homomorphic encryption by recursive self-embedding. The resulting scheme can reduce the accumulated noise caused by multiple algebraic operations, thus make it possible to realize FHE in arbitrary depth.

However, this first FHE scheme is impractical since the computation complexity and ciphertext size are high-order polynomials in the security level parameter λ, which means they increase sharply in order to achieve a practically high-enough security level. This prohibit the practical application of the FHE, especially in the cloud computing context where high security level is crucial. Another major concern of this scheme is that its security was based on two relatively new assumptions, namely, the hardness of the worst-case bounded distance decoding problem (BDD) on ideal lattice, and the hardness of the average-case sparse subset sum problem (SSSP) of the squashing step. Both are relatively untested cryptographic assumptions.

More recently, there have been growing research efforts made in searching practical FHE algorithms, which are more efficient and/or based on more reliable security assumptions. A second version of FHE scheme, known as DGHV, was proposed by Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan in 2010 [Reference Van Dijk, Gentry, Halevi and Vaikuntanathan87]. DGHV uses Gentry's techniques with only elementary modular arithmetic over integers to convert a simple somewhat homomorphic encryption scheme to a bootstappable FHE scheme. This scheme achieved conceptual simplicity because all computations were performed over integers instead of ideal lattice. It also reduced the security assumption to the hardness of the greatest common divisor (GCD) problem. However, the price of this tradeoff is the immense size of public key, which can be impractical for the current systems. Stehle and Steinfeld [Reference Stehle and Steinfeld88] presented a faster homomorphic encryption in order to improve Gentry's scheme by a more aggressive analysis of the SSSP assumption, and introducing a probabilistic decryption algorithm implemented by an algebraic circuit of low multiplicative degree. With these two enhancements, this scheme obtains O(λ^3.5) bit complexity for refreshing a cipher text, whereas previous scheme claimed O(λ ⁶ ) for the same task, where λ is the security parameter. However, there is a non-zero probability of decryption error associated with this scheme.

Besides, Zvika Brakerski and Vinod Vaikuntanathan gave another improvement on Gentry's scheme [Reference Brakerski and Vaikuntanathan89] by changing the two security assumptions made in [Reference Gentry86]. First, the somewhat homomorphic encryption was based on ring learning with errors (RLWE) assumption from Lyubashevsky, Peikert and Regev [Reference Lyubashevsky, Peikert and Regev90] instead of the ideal lattices BDD problem. Second, to make the somewhat homomorphic encryption scheme bootstrappalbe, it used a dimension-modulus reduction technique instead of Gentry's squashing technique, thus eliminating the assumption of SSSP. This new bootstrapping technique also shortened the ciphertext and reduced the complexity. Based on the above improvement, Brakerski, Gentry, and Vaikuntanathan worked together to propose a new leveled FHE scheme without Gentry's bootstrapping procedure in 2011 [Reference Brakerski, Gentry and Vaikuntanathan91]. By applying RLWE, this FHE scheme has O(λ·L ³) per-gate computation for L-level arithmetic circuits. As an optional approach, they also proposed a leveled FHE scheme using bootstrapping as optimization to further reduce the per-gate computation down to O(λ²), independent of L.

Following up in 2011, Coron et al. proposed an improvement of FHE over the integers described by van Dijk et al. The proposed new scheme shortened the public key size from O(λReference Lillibridge, Elnikety, Birrell, Burrows and Isard ¹⁰ ) to O(λReference Paul and Saxena ⁷ ) [Reference Coron, Mandal, Naccache and Tibouchi92]. This procedure is done by using quadratic form instead of linear one in the public key elements, so that the full-length public key is compressed to a smaller subset of the original key. Instead of proposing any further improvement on FHE, Ron Rothblum manifests how to transform any additively homomorphic private-key encryption scheme into a public-key encryption scheme [Reference Rothblum93]. To construct this process, this scheme develops a theorem that any compact additively homomorphic with respect to addition modulo two can be transformed into a semantically scheme. In consequence, the public-key encryption scheme save one hop homomorphic with regard to the same set operations with private-key encryption, which are prior FHE schemes.

With all the theoretical development of different FHE algorithms, it is necessary to investigate their practical implementation. There were several implementations of Gentry's FHE in 2010, and the first attempt was made by Smart and Vercauteren [Reference Smart and Vercauteren94]. They were able to implement the somewhat homomorphic scheme using “principle-ideal lattices” of prime determinant, which can be implied by two integers only. However, they were not able to implement the bootstrapping functionality to obtain a fully homomorphic scheme. Bottleneck of this implementation was the failure to support a large amount of parameters.

Based on this work, in 2011, Gentry and Halevi developed a series of simplifications and optimizations that made bootstrapping implementation possible. As the result, the asymptotic complexity is reduced from Smart and Vercauteren's O(n ².5) to O(n ¹.5). The optimizations from this paper were also used in [Reference Coron, Mandal, Naccache and Tibouchi92] in order to implement the fully homomorphic DGHV scheme under new variant. With the result of having similar performance, Coron et al. successfully showed that FHE can be implemented with a simple arithmetic scheme.

In Table 2, we provide a comparison of performance for different FHE schemes. BDD and SSSP are the problems that stated in the first FHE scheme.

Table 2. Performance comparison for FHE schemes

D) Other data confidentiality approaches

There are several other data confidentiality methods beside above. For instance, The application of cryptographic algorithms to data blocks in the cloud storage is a popular method used to ensure the confidentiality of stored data. A data confidentiality scheme in coreFS, which is a user-level network file system, was proposed in 2009 [Reference Yun, Shi and Kim96]. This scheme is constructed based on a new universal-hash stateful MAC. It has smaller computational overhead of cryptographic operations comparing to the MHT. Besides, it allows better communication capability. However, the choice of caching strategy, MAC tree update schedule, and the method to store the tree can affect the performance of this scheme.

Another data confidentiality scheme exploited the newly proposed secure provenance (SP) model based on the bilinear pairing techniques in 2010 [Reference Lu, Lin, Liang and Shen97]. This scheme records the ownership and the process history of data objects in the cloud storage in order to increase the trust from public users. The SP model consists of the following modules: system setup, key generation, anonymous authentication, authorized access, and provenance tracking. The provable security technique has been tested on this scheme under the standard SP model. It demands some practical considerations in real-world applications and further improvement under the current framework.

Different from above schemes, an compelling statement was proposed by Dijk and Juel in 2010 [Reference Van Dijk and Juels98], which claimed that no cryptographic protocol, even including power primitives such as FHE, can enforce privacy requested by common cloud services alone. This paper also demonstrated that above demand can be achieved by other enforcements instead, such as tamperproof hardware, distributed computing, and complex trust ecosystems.

E) Summary

Data confidentiality is one of the most critical issues for applications with sensitive data, such as personal information, customer's account information, financial and healthcare information. The new challenge of storing those data in clouds is how to prevent accidental or intentional data leakage to the cloud SSP, such that even if the service provider is compromised, the information can still be kept confidential. The fundamental solution to this problem is still data encryption. The user has to encrypt the data before they are moved to the cloud server, and keep it encrypted for the entire period during which the data are in the cloud. When the data needs to be accessed or processed by either the data owner or other legitimate users who have the key for decryption, it is not efficient to retrieve the encrypted data, decrypt it, process and re-encrypt it before sending back to the server. Therefore, new encryption mechanisms that allow for processing of the ciphertext directly without revealing the original information in the plaintext will have a significant potential in cloud storage of sensitive data. WIth encryption, data owners or users regain their control over their data that are not physically stored by themselves.

FHE is an ideal example of these encryption algorithms. However, the promising applications of current FHE algorithms are hindered by its computation complexity and other implementation difficulties. Improvements must be made before it can be put in practical applications. In addition, more implementations of various improvements are awaited to be evaluated on current platforms.

Unlike FHE, which has an ambitious aim at arbitrary computing on the ciphertext, other cloud encryption schemes aimed at specific type of control over encrypted data. For example, ABE allows access control being enforced on the encrypted data by incorporating attribute-based access structure into either the ciphertext or the decryption key. Searchable encryption schemes provide a way to search the ciphertext for a keyword token without revealing the real content of either data or the keyword.