A Trust Based Probabilistic Method for Efficient Correctness Verification in Database Outsourcing



1 Department of Computer Engineering, Payame Noor University (PNU), Iran

2 Malek Ashtar University of Technology, Tehran, Iran

3 Department of Computer Engineering, Vali-e-Asr University of Rafsanjan, Rafsanjan, Iran


Correctness verification of query results is a significant challenge in database outsourcing. Most of the proposed approaches impose high overhead, which makes them impractical in real scenarios. Probabilistic approaches are proposed in order to reduce the computation overhead pertaining to the verification process. In this paper, we use the notion of trust as the basis of our probabilistic approach to efficiently verify the correctness of query results. The trust is computed based on observing the history of interactions between clients and the service provider. Our approach exploits Merkle Hash Tree as an authentication data structure. The amount of trust value towards the service provider leads to investigating just an appropriate portion of the tree. Implementation results of our approach show that considering the trust, derived from the history of interactions, provides a trade-off between performance and security, and reduces the imposed overhead for both clients and the service provider in database outsourcing scenario.


 [1] Michael T. Goodrich, Roberto Tamassia, and Nikos Triandopoulos. Super-efficient verification of dynamic outsourced databases. In Proceedings of the 2008 The Cryptopgraphers’ Track at the RSA Conference on Topics in Cryptology, CTRSA’08, pages 407–424, Berlin, Heidelberg, 2008. Springer-Verlag. ISBN 3-540-79262-7, 978-3-540- 79262-8. 

[2] Radu Sion. Query execution assurance for outsourced databases. In Proceedings of the 31st International Conference on Very Large Data Bases, VLDB ’05, pages 601–612. VLDB Endowment, 2005. ISBN 1-59593-154-6.

[3] Min Xie, Haixun Wang, Jian Yin, and Xiaofeng Meng. Integrity auditing of outsourced data. In Proceedings of the 33rd International Conference on Very Large Data Bases, VLDB ’07, pages 782– 793. VLDB Endowment, 2007. ISBN 978-1-59593- 649-3.

[4] Einar Mykletun, Maithili Narasimha, and Gene Tsudik. Authentication and integrity in outsourced databases. Trans. Storage, 2(2):107–138, May 2006. ISSN 1553-3077.

[5] R. Tamassia and N. Triandopoulos. Efficient content authentication over distributed hash tables. Technical report, CS Department, Brown University, 2005.

[6] Charles Martel, Glen Nuckolls, Premkumar Devanbu, Michael Gertz, April Kwong, and Stuart G. Stubblebine. A general model for authenticated data structures. Algorithmica, 39(1):21–41, January 2004. ISSN 0178-4617.

[7] Ayesha Kanwal, Rahat Masood, Muhammad Awais Shibli, and Rafia Mumtaz. Taxonomy for trust models in cloud computing. The Computer Journal, 58(4):601–626, 2015.

[8] P. N. Mahalle, P. A. Thakre, N. R. Prasad, andR. Prasad. A fuzzy approach to trust based access control in internet of things. In Wireless VITAE 2013, pages 1–5, June 2013.

[9] Jorge Bernal Bernabe, Jose Luis Hernandez Ramos, and Antonio F. Skarmeta Gomez. Taciot: multidimensional trust-aware access control system for the internet of things. Soft Computing, 20(5):1763–1779, May 2016. ISSN ”1433- 7479. [10] Andrew G. West, Adam J. Aviv, Jian Chang, Vinayak S. Prabhu, Matt Blaze, Sampath Kannan, Insup Lee, Jonathan M. Smith, and Oleg Sokolsky. Quantm: a quantitative trust management system. In Proceedings of the Second European Workshop on System Security, EUROSEC, pages 28–35, 2009.

[11] B. Dong, R. Liu, and H. W. Wang. Trustbut-verify: Verifying result correctness of outsourced frequent itemset mining in data-miningas-a-service paradigm. IEEE Transactions on Services Computing, 9(1):18–32, Jan 2016. ISSN 1939-1374. [12] Ron Babin, Kim Bates, and Sajeev Sohal. The role of trust in outsourcing: More important than the contract? Journal of Strategic Contracting and Negotiation, 3(1):38–46, 2017.

[13] Jae-Nam Lee and Byounggu Choi. Effects of initial and ongoing trust in it outsourcing: A bilateral perspective. Information & Management, 48 (2):96 – 105, 2011.

[14] Ralph C. Merkle. A certified digital signature. In ”Advances in Cryptology — CRYPTO’ 89 Proceedings, pages 218–238. Springer New York, 1990.

[15] Roberto Tamassia. Authenticated data structures. In Algorithms - ESA 2003, pages 2–5. Springer Berlin Heidelberg, 2003.

[16] Premkumar Devanbu, Michael Gertz, Charles Martel, and Stuart G. Stubblebine. Authentic Third-Party Data Publication, pages 101–112. Springer US, 2001. ISBN 978-0-306-47008-0.

[17] Feifei Li, Marios Hadjieleftheriou, George Kollios, and Leonid Reyzin. Dynamic authenticated index structures for outsourced databases. In Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, SIGMOD ’06, pages 121–132, New York, NY, USA, 2006. ACM. ISBN 1-59593-434-0.

[18] X. Wang, Y. Lin, and G. Yao. Data integrity verification scheme with designated verifiers for dynamic outsourced databases. Security and Communication Networks, 7(12):2293–2301, Jan 2014.

[19] Maithili Narasimha and Gene Tsudik. Authentication of outsourced databases using signature aggregation and chaining. In Proceedings of the 11th International Conference on Database Systems for Advanced Applications, DASFAA’06, pages 420– 436, Berlin, Heidelberg, 2006. Springer-Verlag. ISBN 3-540-33337-1, 978-3-540-33337-1.

[20] HweeHwa Pang, Arpit Jain, Krithi Ramamritham, and Kian-Lee Tan. Verifying completeness of relational query results in data publishing. In Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, SIGMOD ’05, pages 407–418, New York, NY, USA, 2005. ACM. ISBN 1-59593-060-4.

[21] Giuseppe Ateniese, Randal Burns, Reza Curtmola, Joseph Herring, Lea Kissner, Zachary Peterson, and Dawn Song. Provable data possession at untrusted stores. In Proceedings of the 14th ACM Conference on Computer and Communications Security, CCS ’07, pages 598–609, New York, NY, USA, 2007. ACM. ISBN 978-1-59593-703-2.

[22] Simin Ghasemi, Morteza Noferesti, Mohammad Ali Hadavi, Sadegh Dorri Nogoorani, and Rasool Jalili. Correctness verification in database outsourcing: A trust-based fake tuples approach. In Information Systems Security, pages 343–351, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.

[23] Morteza Noferesti, Simin Ghasemi, Mohammad Ali Hadavi, and Rasool Jalili. A trust-based approach for correctness verification of query results in data outsourcing. JOURNAL OF COMPUTING AND SECURITY, 1(1):3–14, January 2014. ISSN 0178-4617.

[24] L. Mui, M. Mohtashemi, and A. Halberstadt. A computational model of trust and reputation. In Proceedings of the 35th Annual Hawaii International Conference on System Sciences, pages 2431–2439, Jan 2002.

[25] T. Grandison and M. Sloman. A survey of trust in internet applications. IEEE Communications Surveys Tutorials, 3(4):2–16, Fourth 2000. ISSN 1553-877X.