In the outsourced database model, the third-party server provides query services to users on behalf of the data owner. However, the service provider may be unreliable or susceptible to attacks. The service provider can also produce inauthentic or incomplete query results. An authentication scheme for multi-dimensional data is proposed in the present study to investigate this problem. The authors introduce a new concept of tower head node based on the k-dimensional skip list and use it to construct a new authenticated data structure. This structure supports both multi-dimensional range query and dynamic maintenance. They also show how to verify the authenticity and completeness of query results on multi-dimensional datasets in the outsourced database model. Moreover, this structure can be fully outsourced, thus the service provider can perform the entire maintenance, which is crucial for users with limited computational resources. The proof of security and the evaluation of experiment demonstrate that the scheme is secure and outperforms previous schemes in terms of the construction cost, proof size, query time, verification time and update cost.

References

1. 1)
  - 20. Xie, M., Wang, H.X., Yin, J., et al: ‘Providing freshness guarantees for outsourced databases’. Proc. of Int. Conf. on Extending Database Technology, Nantes, France, March 2008, pp. 323–332.
2. 2)
  - 14. Erway, C., Kupcu, A., Papamanthou, C., et al: ‘Dynamic provable data possession’. Proc. of Int. Conf. on ACM on Computer and Communications Security, Chicago, USA, November 2009, pp. 213–222.
3. 3)
  - 27. Devanbu, P., Gertz, M., Martel, C., et al: ‘Authentic data publication over the internet’, J. Comput. Secur., 2003, 11, (3), pp. 291–314.
4. 4)
  - 31. Yang, Y., Papadopoulos, S., Papadias, D., et al: ‘Authenticated indexing for outsourced spatial databases’, Int. J. Very Large Data Bases, 2009, 18, (3), pp. 631–648 (doi: 10.1007/s00778-008-0113-2).
5. 5)
  - 2. Hsiao, H.C., Lin, Y.H., Studer, A., et al: ‘A study of user-friendly hash comparison schemes’. Proc. of Int. Conf. on Computer Security Applications, Hawaii, USA, December 2009, pp. 105–114.
6. 6)
  - 5. Wang, X.M., Lin, Y.C., Yao, G.X.: ‘Data integrity verification scheme with designated verifiers for dynamic outsourced databases’, Secur. Commun. Netw., 2014, 7, (12), pp. 2293–2301 (doi: 10.1002/sec.938).
7. 7)
  - 30. Yang, Y., Papadopoulos, S., Papadias, D., et al: ‘Spatial outsourcing for location-based services’. Proc. of Int. Conf. on Data Engineering, Cancún, México, April 2008, pp. 1082–1091.
8. 8)
  - 9. Di Battista, G., Palazzi, B.: ‘Authenticated relational tables and authenticated skip lists’. Proc. of Int. Conf. on IFIP WG 11.3 Working on Data and Applications Security, CA, USA, July 2007, pp. 31–46.
9. 9)
  - 18. Chen, L.X., Zhou, S.M., Huang, X.Y., et al: ‘Data dynamics for remote data possession checking in cloud storage’, Comput. Electr. Eng., 2013, 39, (7), pp. 2413–2424 (doi: 10.1016/j.compeleceng.2013.07.010).
10. 10)
  - 1. Li, F., Hadjieleftheriou, M., Kollios, G., Reyzin, L.: ‘Dynamic authenticated index structures for outsourced databases’. Proc. of Int. Conf. on ACM SIGMOD on Management of Data, Chicago, Illinois, USA, June 2006, pp. 121–132.
11. 11)
  - 15. Wang, Q., Wang, C., Ren, K., et al: ‘Enabling public auditability and data dynamics for storage security in cloud computing’, IEEE Trans. Parallel Distrib. Syst., 2012, 22, (5), pp. 847–859 (doi: 10.1109/TPDS.2010.183).
12. 12)
  - 25. Cheng, W., Pang, H.H., Tan, K.L.: ‘Authenticating multi-dimensional query results in data publishing’, Lect. Notes Comput. Sci., 2006, 4127, pp. 60–73 (doi: 10.1007/11805588_5).
13. 13)
  - 7. Goodrich, M., Tamassia, R.: ‘Efficient authenticated dictionaries with skip lists and commutative hashing’ (Johns Hopkins Information Security Institute, 2001), pp. 1–14.
14. 14)
  - 23. De Capitani di Vimercati, S., Foresti, S., Jajodia, S., et al: ‘Optimizing integrity checks for join queries in the cloud’, Lect. Notes Comput. Sci., 2014, 8648, pp. 1–12 (doi: 10.1007/978-3-319-10067-8_1).
15. 15)
  - 3. Wang, X.M., Yuan, D.B.: ‘A query verification scheme for dynamic outsourced databases’, J. Comput., 2012, 7, (1), pp. 156–160.
16. 16)
  - 22. De Capitani di Vimercati, S., Foresti, S., Jajodia, S., et al: ‘Integrity for join queries in the cloud’, IEEE Trans. Cloud Comput., 2013, 1, (2), pp. 187–200 (doi: 10.1109/TCC.2013.18).
17. 17)
  - 26. Merkle, R.C.: ‘A certified digital signature’. Proc. of Int. Conf. on Advances in Cryptology, London, UK, August 1989, pp. 218–238.
18. 18)
  - 29. Cheng, W., Tan, K.L.: ‘Query assurance verification for outsourced multi-dimensional databases’, J. Comput. Secur., 2009, 17, (1), pp. 101–126.
19. 19)
  - 16. Yang, K., Jia, X.H.: ‘An efficient and secure dynamic auditing protocol for data storage in cloud computing’, IEEE Trans. Parallel Distrib. Syst., 2013, 24, (9), pp. 1717–1726 (doi: 10.1109/TPDS.2012.278).
20. 20)
  - 10. Heitzmann, A., Palazzi, B., Papamanthou, C., et al: ‘Efficient integrity checking of untrusted network storage’. Proc. of Int. Conf. on ACM Workshop on Storage Security and Survivability, Alexandria, VA, USA, October 2008, pp. 43–53.
21. 21)
  - 11. Ateniese, G., Burns, R., Curtmola, R., et al: ‘Provable data possession at untrusted stores’. Proc. of Int. Conf. on ACM on Computer and Communications Security, Alexandria, VA, USA, October 2007, pp. 598–609.
22. 22)
  - 12. Juels, A., Burton, J., Kaliski, S.: ‘PoRs: proofs of retrievability for large files’. Proc. of Int. Conf. on ACM on Computer and Communications Security, Alexandria, VA, USA, October 2007, pp. 584–597.
23. 23)
  - 32. Pang, H., Tan, K.: ‘Verifying completeness of relational query answers from online servers’, ACM Trans. Inf. Syst. Secur., 2008, 11, (2), pp. 1–5 (doi: 10.1145/1330332.1330337).
24. 24)
  - 33. Nickerson, B.G.: ‘Skip list data structures for multidimensional data’ (University of Maryland Institute for Advanced Computer Studies, 1994), pp. 1–39.
25. 25)
  - 19. Xie, M., Wang, H., Jian, Y., et al: ‘Integrity auditing of outsourced data’. Proc. of Int. Conf. on Very Large Data Bases, Austria, September 2007, pp. 782–793.
26. 26)
  - 28. Cheng, W., Tan, K.L.: ‘Authenticating kNN query results in data publishing’, Lect. Notes Comput. Sci., 2007, 4721, pp. 47–63 (doi: 10.1007/978-3-540-75248-6_4).
27. 27)
  - 4. Shu, J., Shen, Z., Xue, W.: ‘Shield: a stackable secure storage system for file sharing in public storage’, J. Parallel Distrib. Comput., 2014, 74, (9), pp. 2872–2883 (doi: 10.1016/j.jpdc.2014.06.003).
28. 28)
  - 21. Wang, H., Yin, J., Perng, C., et al: ‘Dual encryption for query integrity assurance’. Proc. of Int. Conf. on ACM Information and Knowledge Management, Napa Valley, CA, October 2008, pp. 863–872.
29. 29)
  - 17. Tajuddin, Md., China Busi, K.: ‘An enhanced dynamic auditing protocol in cloud computing’, Int. J. Eng. Trends Technol., 2013, 4, (7), pp. 3173–3176.
30. 30)
  - 13. Xiao, D., Yang, Y., Yao, W.B., et al: ‘Multiple-file remote data checking for cloud storage’, Comput. Secur., 2012, 31, (2), pp. 192–201 (doi: 10.1016/j.cose.2011.12.005).
31. 31)
  - 24. De Capitani di Vimercati, S., Foresti, S., Jajodia, S., et al: ‘Integrity for distributed queries’. IEEE Conf. on Communications and Network Security, San Francisco, CA, USA, October 2014, pp. 1–9.
32. 32)
  - 8. Wang, J., Du, X.Y.: ‘Skip list based authenticated data structure in DAS paradigm’. Proc. of Int. Conf. on Grid and Cooperative Computing, Lanzhou, China, August 2009, pp. 69–75.
33. 33)
  - 6. Wei, W., Yu, T., Xue, R.: ‘iBigTable: practical data integrity for bigtable in public cloud’. Proc. of Int. Conf. on ACM on Data and Application Security and Privacy, New York, USA, February 2013, pp. 341–352.

Authenticating multi-dimensional query results in outsourced database

References

Related content