Efficient integrity checks for join queries in the cloud 1

Abstract

Cloud computing is receiving massive interest from users and companies for its convenient support of scalable access to data and services. The variety and diversification of offers by cloud providers allow users to selectively adopt storage and computational services as they best suit their needs, including cost saving considerations. In such an open context, security remains a major concern, as confidentiality and integrity of data and queries over them can be at risk. In this paper, we present efficient techniques to verify the integrity of join queries computed by potentially untrusted cloud providers, while also protecting data and computation confidentiality. Our techniques support joins among multiple data sources and introduce a limited overhead in query computation, enabling also economical savings, as the ability to assess integrity increases the spectrum of offers that can be considered for performing the computation. Formal analysis and experimental evaluations confirm the effectiveness and efficiency of our solutions.

Keywords

Query integrity distributed join semi-join execution verification object

Get full access to this article

View all access options for this article.

References

Ateniese ,

Di Pietro ,

Mancini and

Tsudik , Scalable and efficient provable data possession, in: Proc. of SECURECOMM, Istanbul, Turkey, 2008.

Basu ,

Vaidya ,

Kikuchi and

Dimitrakos , Privacy-preserving collaborative filtering on the cloud and practical implementation experiences, in: Proc. of IEEE Cloud, Santa Clara, CA, 2013.

Damiani ,

De Capitani di Vimercati ,

Jajodia ,

Paraboschi and

Samarati , Balancing confidentiality and efficiency in untrusted relational DBMSs, in: Proc. of CCS, Washington, DC, 2003.

De Capitani di Vimercati ,

Foresti ,

Jajodia and

Livraga , Enforcing subscription-based authorization policies in cloud scenarios, in: Proc. of DBSec, Paris, France, 2012.

De Capitani di Vimercati ,

Foresti ,

Jajodia ,

Livraga ,

Paraboschi and

Samarati , Integrity for distributed queries, in: Proc. of CNS, San Francisco, CA, 2014.

De Capitani di Vimercati ,

Foresti ,

Jajodia ,

Paraboschi and

Samarati , Encryption policies for regulating access to outsourced data, ACM TODS 35(2) (2010), 12:1–12:46.

De Capitani di Vimercati ,

Foresti ,

Jajodia ,

Paraboschi and

Samarati , Integrity for join queries in the cloud, IEEE TCC 1(2) (2013), 187–200.

De Capitani di Vimercati ,

Foresti ,

Jajodia ,

Paraboschi and

Samarati , Optimizing integrity checks for join queries in the cloud, in: Proc. of DBSec, Vienna, Austria, 2014.

De Capitani di Vimercati ,

Foresti ,

Jajodia ,

Paraboschi and

Samarati , Integrity for approximate joins on untrusted computational servers, in: Proc. of SEC, Hamburg, Germany, 2015.

10.

De Capitani di Vimercati ,

Foresti and

Samarati , Managing and accessing data in the cloud: Privacy risks and approaches, in: Proc. of CRiSIS, Cork, Ireland, 2012.

11.

Franco-Contreras ,

Coatrieux ,

Cuppens ,

Cuppens-Boulahia and

Roux , Robust lossless watermarking of relational databases based on circular histogram modulation, IEEE TIFS 9(3) (2014), 397–410.

12.

Ghazizadeh ,

Mukkamala and

Olariu , Data integrity evaluation in cloud database-as-a-service, in: Proc. of IEEE SERVICES, Santa Clara, CA, 2013.

13.

Hacigümüs ,

Iyer and

Mehrotra , Ensuring integrity of encrypted databases in database as a service model, in: Proc. of DBSec, Estes Park, CO, 2003.

14.

Hacigümüş ,

Iyer ,

Mehrotra and

Li , Executing SQL over encrypted data in the database-service-provider model, in: Proc. of SIGMOD, Madison, WI, 2002.

15.

Jhawar and

Piuri , Fault tolerance management in IaaS clouds, in: Proc. of ESTEL, Rome, Italy, 2012.

16.

Jhawar ,

Piuri and

Samarati , Supporting security requirements for resource management in cloud computing, in: Proc. of CSE, Paphos, Cyprus, 2012.

17.

Jhawar ,

Piuri and

Santambrogio , Fault tolerance management in cloud computing: A system-level perspective, IEEE Systems Journal 7(2) (2013), 288–297.

18.

Juels and

B.S.

Kaliski Jr. , PORs: Proofs of retrievability for large files, in: Proc. of ACM CCS, Alexandria, VA, 2007.

19.

Kossmann ,

Kraska and

Loesing , An evaluation of alternative architectures for transaction processing in the cloud, in: Proc. of SIGMOD, Indianapolis, IN, 2010.

20.

Li ,

Hadjieleftheriou ,

Kollios and

Reyzin , Dynamic authenticated index structures for outsourced databases, in: Proc. of SIGMOD, Chicago, IL, 2006.

21.

Li ,

Hadjieleftheriou ,

Kollios and

Reyzin , Authenticated index structures for aggregation queries, ACM TISSEC 13(4) (2010), 32:1–32:35.

22.

Mykletun ,

Narasimha and

Tsudik , Authentication and integrity in outsourced databases, ACM TOS 2(2) (2006), 107–138.

23.

Pang ,

Jain ,

Ramamritham and

Tan , Verifying completeness of relational query results in data publishing, in: Proc. of SIGMOD, Baltimore, MA, 2005.

24.

Ren ,

Wang and

Wang , Security challenges for the public cloud, IEEE Internet Computing 16(1) (2012), 69–73.

25.

Samarati and

De Capitani di Vimercati , Cloud security: Issues and concerns, in: Encyclopedia on Cloud Computing,

Murugesan and

Bojanova , eds, Wiley, New York, 2016.

26.

Sheng ,

Wen ,

Guo and

Yin , Verifying correctness of inner product of vectors in cloud computing, in: Proc. of Cloud Computing, Hangzhou, China, 2013.

27.

The transaction processing performance council (TPC) benchmark H, available at: http://www.tpc.org/tpch/.

28.

Umadevi and

Saxena , Correctness verification in outsourced databases: More reliable fake tuples approach, in: Proc. of ICISS, Kolkata, India, December, 2013.

29.

Wang ,

Chow ,

Wang ,

Ren and

Lou , Privacy-preserving public auditing for secure cloud storage, IEEE Transactions on Computers 62(2) (2013), 362–375.

30.

Wang ,

Yin ,

Perng and

P.S.

Yu , Dual encryption for query integrity assurance, in: Proc. of CIKM, Napa Valley, CA, 2008.

31.

Xie ,

Wang ,

Yin and

Meng , Integrity auditing of outsourced data, in: Proc. of VLDB, Vienna, Austria, 2007.

32.

Xie ,

Wang ,

Yin and

Meng , Providing freshness guarantees for outsourced databases, in: Proc. of EDBT, Nantes, France, 2008.

33.

Yang ,

Gao ,

Xu and

Choi , Authentication of range query results in MapReduce environments, in: Proc. of CloudDB, Glasgow, UK, 2011.

34.

Zhu ,

G.-J.

Ahn ,

Hu ,

S.S.

Yau ,

H.G.

An and

C.-J.

Hu , Dynamic audit services for outsourced storages in clouds, IEEE TSC 6(2) (2013), 227–238.