Visible to the public Integrity of Outsourced Databases

SoS Newsletter- Advanced Book Block

SoS Logo

Integrity of Outsourced Databases

The growth of distributed storage systems such as the Cloud has produced novel security problems.  The works cited here address untrusted servers, generic trusted data, trust extension on commodity computers, defense against frequency-based attacks in wireless networks, and other topics.  These articles were presented or published in the first half of 2014.


Matteo Maffei, Giulio Malavolta, Manuel Reinert, Dominique Schröder, “Brief Announcement: Towards Security And Privacy For Outsourced Data In The Multi-Party Setting,” Proceedings of the 2014 ACM Symposium On Principles Of Distributed Computing, July 2014, Pages 144-146. doi>10.1145/2611462.2611508 Cloud storage has rapidly acquired popularity among users, constituting a seamless solution for the backup, synchronization, and sharing of large amounts of data. This technology, however, puts user data in the direct control of cloud service providers, which raises increasing security and privacy concerns related to the integrity of outsourced data, the accidental or intentional leakage of sensitive information, the profiling of user activities and so on. We present GORAM, a cryptographic system that protects the secrecy and integrity of the data outsourced to an untrusted server and guarantees the anonymity and unlinkability of consecutive accesses to such data. GORAM allows the database owner to share outsourced data with other clients, selectively granting them read and write permissions. GORAM is the first system to achieve such a wide range of security and privacy properties for outsourced storage. Technically, GORAM builds on a combination of ORAM to conceal data accesses, attribute-based encryption to rule the access to outsourced data, and zero-knowledge proofs to prove read and write permissions in a privacy-preserving manner. We implemented GORAM and conducted an experimental evaluation to demonstrate its feasibility.
Keywords: GORAM, ORAM, cloud storage, oblivious ram, privacy-enhancing technologies (ID#: 15-3732)
URL: or


Andrew Miller, Michael Hicks, Jonathan Katz, Elaine Shi, “Authenticated Data Structures, Generically,” Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, January 2014, Pages 411-423. doi>10.1145/2535838.2535851 An authenticated data structure (ADS) is a data structure whose operations can be carried out by an untrusted prover, the results of which a verifier can efficiently check as authentic. This is done by having the prover produce a compact proof that the verifier can check along with each operation's result. ADSs thus support outsourcing data maintenance and processing tasks to untrusted servers without loss of integrity. Past work on ADSs has focused on particular data structures (or limited classes of data structures), one at a time, often with support only for particular operations.  This paper presents a generic method, using a simple extension to a ML-like functional programming language we call λ• (lambda-auth), with which one can program authenticated operations over any data structure defined by standard type constructors, including recursive types, sums, and products. The programmer writes the data structure largely as usual and it is compiled to code to be run by the prover and verifier. Using a formalization of λ• we prove that all well-typed λ• programs result in code that is secure under the standard cryptographic assumption of collision-resistant hash functions. We have implemented λ• as an extension to the OCaml compiler, and have used it to produce authenticated versions of many interesting data structures including binary search trees, red-black+ trees, skip lists, and more. Performance experiments show that our approach is efficient, giving up little compared to the hand-optimized data structures developed previously.
Keywords: authenticated data structures, cryptography, programming languages, security (ID#: 15-3733)
URL: or


Lifei Wei, Haojin Zhu, Zhenfu Cao, Xiaolei Dong, Weiwei Jia, Yunlu Chen, Athanasios V. Vasilakos, “Security and Privacy For Storage And Computation In Cloud Computing,” Information Sciences: an International Journal, Volume 258, February, 2014, Pages 371-386.   doi>10.1016/j.ins.2013.04.028 Cloud computing emerges as a new computing paradigm that aims to provide reliable, customized and quality of service guaranteed computation environments for cloud users. Applications and databases are moved to the large centralized data centers, called cloud. Due to resource virtualization, global replication and migration, the physical absence of data and machine in the cloud, the stored data in the cloud and the computation results may not be well managed and fully trusted by the cloud users. Most of the previous work on the cloud security focuses on the storage security rather than taking the computation security into consideration together. In this paper, we propose a privacy cheating discouragement and secure computation auditing protocol, or SecCloud, which is a first protocol bridging secure storage and secure computation auditing in cloud and achieving privacy cheating discouragement by designated verifier signature, batch verification and probabilistic sampling techniques. The detailed analysis is given to obtain an optimal sampling size to minimize the cost. Another major contribution of this paper is that we build a practical secure-aware cloud computing experimental environment, or SecHDFS, as a test bed to implement SecCloud. Further experimental results have demonstrated the effectiveness and efficiency of the proposed SecCloud.
Keywords: Batch verification, Cloud computing, Designated verifier signature, Privacy-cheating discouragement, Secure computation auditing, Secure storage (ID#: 15-3734)
URL: or


Bryan Jeffery Parno, Trust Extension as a Mechanism for Secure Code Execution on Commodity Computers, ACM Press, New York, NY, 2014. ISBN: 978-1-62705-477-5 doi>10.1145/2611399 From the preface:  As society rushes to digitize sensitive information and services, it is imperative that we adopt adequate security protections. However, such protections fundamentally conflict with the benefits we expect from commodity computers. In other words, consumers and businesses value commodity computers because they provide good performance and an abundance of features at relatively low costs. Meanwhile, attempts to build secure systems from the ground up typically abandon such goals, and hence are seldom adopted [Karger et al. 1991, Gold et al. 1984, Ames 1981].  In this book, a revised version of my doctoral dissertation, originally written while studying at Carnegie Mellon University, I argue thatwecan resolve the tension between security and features by leveraging the trust a user has in one device to enable her to securely use another commodity device or service, without sacrificing the performance and features expected of commodity systems. We support this premise over the course of the following chapters. •Introduction. This chapter introduces the notion of bootstrapping trust from one device or service to another and gives an overview of how the subsequent chapters fit together.  •Background and related work. This chapter focuses on existing techniques for bootstrapping trust in commodity computers, specifically by conveying information about a computer's current execution environment to an interested party. This would, for example, enable a user to verify that her computer is free of malware, or that a remote web server will handle her data responsibly. •Bootstrapping trust in a commodity computer. At a high level, this chapter develops techniques to allow a user to employ a small, trusted, portable device to securely learn what code is executing on her local computer. While the problem is simply stated, finding a solution that is both secure and usable with existing hardware proves quite difficult.  •On-demand secure code execution. Rather than entrusting a user's data to the mountain of buggy code likely running on her computer, in this chapter, we construct an on-demand secure execution environment which can perform security sensitive tasks and handle private data in complete isolation from all other software (and most hardware) on the system. Meanwhile, non-security-sensitive software retains the same abundance of features and performance it enjoys today.  •Using trustworthy host data in the network. Having established an environment for secure code execution on an individual computer, this chapter shows how to extend trust in this environment to network elements in a secure and efficient manner. This allows us to reexamine the design of network protocols and defenses, since we can now execute code on end hosts and trust the results within the network. •Secure code execution on untrusted hardware. Lastly, this chapter extends the user's trust one more step to encompass computations performed on a remote host (e.g., in the cloud).We design, analyze, and prove secure a protocol that allows a user to outsource arbitrary computations to commodity computers run by an untrusted remote party (or parties) who may subject the computers to both software and hardware attacks. Our protocol guarantees that the user can both verify that the results returned are indeed the correct results of the specified computations on the inputs provided, and protect the secrecy of both the inputs and outputs of the computations. These guarantees are provided in a non-interactive, asymptotically optimal (with respect to CPU and bandwidth) manner.   Thus, extending a user's trust, via software, hardware, and cryptographic techniques, allows us to provide strong security protections for both local and remote computations on sensitive data, while still preserving the performance and features of commodity computers. (ID#: 15-3735)


Hongbo Liu, Hui Wang, Yingying Chen, Dayong Jia, “Defending against Frequency-Based Attacks on Distributed Data Storage in Wireless Networks,” ACM Transactions on Sensor Networks (TOSN), Volume 10 Issue 3, April 2014, Article No. 49.  doi>10.1145/2594774As wireless networks become more pervasive, the amount of the wireless data is rapidly increasing. One of the biggest challenges of wide adoption of distributed data storage is how to store these data securely. In this work, we study the frequency-based attack, a type of attack that is different from previously well-studied ones, that exploits additional adversary knowledge of domain values and/or their exact/approximate frequencies to crack the encrypted data. To cope with frequency-based attacks, the straightforward 1-to-1 substitution encryption functions are not sufficient. We propose a data encryption strategy based on 1-to-n substitution via dividing and emulating techniques to defend against the frequency-based attack, while enabling efficient query evaluation over encrypted data. We further develop two frameworks, incremental collection and clustered collection, which are used to defend against the global frequency-based attack when the knowledge of the global frequency in the network is not available. Built upon our basic encryption schemes, we derive two mechanisms, direct emulating and dual encryption, to handle updates on the data storage for energy-constrained sensor nodes and wireless devices. Our preliminary experiments with sensor nodes and extensive simulation results show that our data encryption strategy can achieve high security guarantee with low overhead.
Keywords: Frequency-based attack, secure distributed data storage, wireless networks (ID#: 15-3736)
URL: or


She-I Chang, David C. Yen, I-Cheng Chang, Derek Jan, “Internal Control Framework For A Compliant ERP System,” Information and Management, Volume 51 Issue 2, March, 2014, Pages 187-205.  doi>10.1016/ After the occurrence of numerous worldwide financial scandals, the importance of related issues such as internal control and information security has greatly increased. This study develops an internal control framework that can be applied within an enterprise resource planning (ERP) system. A literature review is first conducted to examine the necessary forms of internal control in information technology (IT) systems. The control criteria for the establishment of the internal control framework are then constructed. A case study is conducted to verify the feasibility of the established framework. This study proposes a 12-dimensional framework with 37 control items aimed at helping auditors perform effective audits by inspecting essential internal control points in ERP systems. The proposed framework allows companies to enhance IT audit efficiency and mitigates control risk. Moreover, companies that refer to this framework and consider the limitations of their own IT management can establish a more robust IT management mechanism.
Keywords: Enterprise resource planning, IT control, Internal control framework (ID#: 15-3737)
URL: or


Miyoung Jang; Min Yoon; Jae-Woo Chang, "A privacy-aware query authentication index for database outsourcing," Big Data and Smart Computing (BIGCOMP), 2014 International Conference on , vol., no., pp.72,76, 15-17 Jan. 2014. doi: 10.1109/BIGCOMP.2014.6741410  Recently, cloud computing has been spotlighted as a new paradigm of database management system. In this environment, databases are outsourced and deployed on a service provider in order to reduce cost for data storage and maintenance. However, the service provider might be untrusted so that the two issues of data security, including data confidentiality and query result integrity, become major concerns for users. Existing bucket-based data authentication methods have problem that the original spatial data distribution can be disclosed from data authentication index due to the unsophisticated data grouping strategies. In addition, the transmission overhead of verification object is high. In this paper, we propose a privacy-aware query authentication which guarantees data confidentiality and query result integrity for users. A periodic function-based data grouping scheme is designed to privately partition a spatial database into small groups for generating a signature of each group. The group signature is used to check the correctness and completeness of outsourced data when answering a range query to users. Through performance evaluation, it is shown that proposed method outperforms the existing method in terms of range query processing time up to 3 times.
Keywords: cloud computing; data integrity; data privacy; database indexing; digital signatures; outsourcing; query processing; visual databases; bucket-based data authentication methods; cloud computing; cost reduction ;data confidentiality; data maintenance; data security; data storage; database management system; database outsourcing; group signature; periodic function-based data grouping scheme; privacy-aware query authentication index; query result integrity; range query answering; service provider; spatial data distribution; spatial database; unsophisticated data grouping strategy; verification object transmission overhead; Authentication; Encryption; Indexes; Query processing; Spatial databases; Data authentication index; Database outsourcing; Encrypted database; Query result integrity (ID#: 15-3738)


Omote, K.; Thao, T.P., "A New Efficient and Secure POR Scheme Based on Network Coding," Advanced Information Networking and Applications (AINA), 2014 IEEE 28th International Conference on , vol., no., pp.98,105, 13-16 May 2014.  doi: 10.1109/AINA.2014.17  Information is increasing quickly, database owners have tendency to outsource their data to an external service provider called Cloud Computing. Using Cloud, clients can remotely store their data without burden of local data storage and maintenance. However, such service provider is untrusted, therefore there are some challenges in data security: integrity, availability and confidentiality. Since integrity and availability are prerequisite conditions of the existence of a system, we mainly focus on them rather than confidentiality. To ensure integrity and availability, researchers have proposed network coding-based POR (Proof of Retrievability) schemes that enable the servers to demonstrate whether the data is retrievable or not. However, most of network coding-based POR schemes are inefficient in data checking and also cannot prevent a common attack in POR: small corruption attack. In this paper, we propose a new network coding-based POR scheme using dispersal code in order to reduce cost in checking phase and also to prevent small corruption attack.
Keywords: cloud computing; data communication; network coding; security of data; cloud computing; corruption attack; corruption attack prevention; ost reduction; data availability; data checking;data confidentiality; data integrity; data security; dispersal code; efficient POR scheme; local data storage; maintenance; network coding-based POR; proof of retrievability; secure POR scheme; Availability; Decoding; Encoding; Maintenance engineering; Network coding; Servers; Silicon; data availability; data integrity; network coding; proof of retrievability (ID#: 15-3739)


Yinan Jing; Ling Hu; Wei-Shinn Ku; Shahabi, C., "Authentication of k Nearest Neighbor Query on Road Networks," Knowledge and Data Engineering, IEEE Transactions on , vol.26, no.6, pp.1494,1506, June 2014. doi: 10.1109/TKDE.2013.174 Outsourcing spatial databases to the cloud provides an economical and flexible way for data owners to deliver spatial data to users of location-based services. However, in the database outsourcing paradigm, the third-party service provider is not always trustworthy, therefore, ensuring spatial query integrity is critical. In this paper, we propose an efficient road network k-nearest-neighbor query verification technique which utilizes the network Voronoi diagram and neighbors to prove the integrity of query results. Unlike previous work that verifies k-nearest-neighbor results in the Euclidean space, our approach needs to verify both the distances and the shortest paths from the query point to its kNN results on the road network. We evaluate our approach on real-world road networks together with both real and synthetic points of interest datasets. Our experiments run on Google Android mobile devices which communicate with the service provider through wireless connections. The experiment results show that our approach leads to compact verification objects (VO) and the verification algorithm on mobile devices is efficient, especially for queries with low selectivity.
Keywords: computational geometry; outsourcing; query processing; smart phones; visual databases;  Euclidean space; Google Android mobile devices; Voronoi diagram; database outsourcing paradigm; k nearest neighbor query; location-based services; road network k-nearest-neighbor query verification technique; spatial databases; spatial query integrity; third-party service provider; Artificial neural networks; Authentication; Generators; Outsourcing; Roads; Spatial databases; Spatial database outsourcing; location-based services; query authentication; road networks (ID#: 15-3740)


Wang, H., "Identity-Based Distributed Provable Data Possession in Multi-Cloud Storage," Services Computing, IEEE Transactions on, vol. PP, no.99, pp.1,1, March 2014. doi: 10.1109/TSC.2014.1 Remote data integrity checking is of crucial importance in cloud storage. It can make the clients verify whether their outsourced data is kept intact without downloading the whole data. In some application scenarios, the clients have to store their data on multi-cloud servers. At the same time, the integrity checking protocol must be efficient in order to save the verifier’s cost. From the two points, we propose a novel remote data integrity checking model: ID-DPDP (identity-based distributed provable data possession) in multi-cloud storage. The formal system model and security model are given. Based on the bilinear pairings, a concrete ID-DPDP protocol is designed. The proposed ID-DPDP protocol is provably secure under the hardness assumption of the standard CDH (computational Diffie- Hellman) problem. In addition to the structural advantage of elimination of certificate management, our ID-DPDP protocol is also efficient and flexible. Based on the client’s authorization, the proposed ID-DPDP protocol can realize private verification, delegated verification and public verification.
Keywords: Cloud computing; Computational modeling; Distributed databases; Indexes; Protocols; Security; Servers (ID#: 15-3741)


Jinguang Han; Susilo, W.; Yi Mu, "Identity-Based Secure Distributed Data Storage Schemes," Computers, IEEE Transactions on , vol.63, no.4, pp.941,953, April 2014. doi: 10.1109/TC.2013.26  Secure distributed data storage can shift the burden of maintaining a large number of files from the owner to proxy servers. Proxy servers can convert encrypted files for the owner to encrypted files for the receiver without the necessity of knowing the content of the original files. In practice, the original files will be removed by the owner for the sake of space efficiency. Hence, the issues on confidentiality and integrity of the outsourced data must be addressed carefully. In this paper, we propose two identity-based secure distributed data storage (IBSDDS) schemes. Our schemes can capture the following properties: (1) The file owner can decide the access permission independently without the help of the private key generator (PKG); (2) For one query, a receiver can only access one file, instead of all files of the owner; (3) Our schemes are secure against the collusion attacks, namely even if the receiver can compromise the proxy servers, he cannot obtain the owner's secret key. Although the first scheme is only secure against the chosen plaintext attacks (CPA), the second scheme is secure against the chosen ciphertext attacks (CCA). To the best of our knowledge, it is the first IBSDDS schemes where an access permission is made by the owner for an exact file and collusion attacks can be protected in the standard model.
Keywords: authorization; data integrity; distributed databases; file servers; private key cryptography; storage management; CCA; CPA; IBSDDS scheme; PKG; access permission; chosen ciphertext attack; chosen plaintext attack; collusion attacks; encrypted files conversion; file access; file maintenance; identity-based secure distributed data storage scheme; outsourced data confidentiality; outsourced data integrity; private key generator; proxy server; receiver; space efficiency; Educational institutions; Encryption; Memory; Receivers; Servers; Distributed data storage; access control; identity-based system; security (ID#: 15-3742)


Al-Anzi, F.S.; Salman, AA; Jacob, N.K.; Soni, J., "Towards Robust, Scalable And Secure Network Storage In Cloud Computing," Digital Information and Communication Technology and it's Applications (DICTAP), 2014 Fourth International Conference on , vol., no., pp.51,55, 6-8 May 2014. doi: 10.1109/DICTAP.2014.6821656 The term Cloud Computing is not something that appeared overnight, it may come from the time when computer system remotely accessed the applications and services. Cloud computing is Ubiquitous technology and receiving a huge attention in the scientific and industrial community. Cloud computing is ubiquitous, next generation's in-formation technology architecture which offers on-demand access to the network. It is dynamic, virtualized, scalable and pay per use model over internet. In a cloud computing environment, a cloud service provider offers “house of resources” includes applications, data, runtime, middleware, operating system, virtualization, servers, data storage and sharing and networking and tries to take up most of the overhead of client. Cloud computing offers lots of benefits, but the journey of the cloud is not very easy. It has several pitfalls along the road because most of the services are outsourced to third parties with added enough level of risk. Cloud computing is suffering from several issues and one of the most significant is Security, privacy, service availability, confidentiality, integrity, authentication, and compliance. Security is a shared responsibility of both client and service provider and we believe security must be information centric, adaptive, proactive and built in. Cloud computing and its security are emerging study area nowadays. In this paper, we are discussing about data security in cloud at the service provider end and proposing a network storage architecture of data which make sure availability, reliability, scalability and security.
Keywords: cloud computing; data integrity; data privacy; security of data; storage management; ubiquitous computing; virtualisation; Internet; adaptive security; authentication; built in security; client overhead; cloud computing environment; cloud service provider; compliance; confidentiality; data security; data sharing; data storage; information centric security; integrity; middleware; network storage architecture; networking; on-demand access; operating system; pay per use model; privacy; proactive security; remote application access; remote service access; robust scalable secure network storage; server; service availability; service outsourcing; ubiquitous next generation information technology architecture virtualization; Availability; Cloud computing; Computer architecture; Data security; Distributed databases; Servers; Cloud Computing; Data Storage; Data security; RAID (ID#: 15-3743)


Articles listed on these pages have been found on publicly available internet pages and are cited with links to those pages. Some of the information included herein has been reprinted with permission from the authors or data repositories. Direct any requests via Email to for removal of the links or modifications to specific citations. Please include the ID# of the specific citation in your correspondence.