Location-based systems (LBS) represent an emerging genre of applications that exploit
positioning technologies and facilitate a wide range of location-based services. Unlike
conventional information systems, LBS data management is challenging because LBS data
is high dimensional and spatio-temporal in nature, and information leakage may result in
location related privacy crises. The issue has become even more complicated, as database
outsourcing has become inevitable in view of the emerging popularity of LBS deployment.
In this paper, we tackle the research challenge and propose a SecUre Database Outsourcing
system, called SUDO. By combining the techniques of Hilbert space-filling curves, different
invertible encryption algorithms, and genuine mixed data, we show that SUDO is capable
of preserving location privacy and ownership of data for LBS against different attacks.
Moreover, the proposed solution is simple, effective, and scalable; and it shows promise in
supporting LBS data management with outsourced databases.

Location-based systems (LBS) represent an emerging genre of applications that exploit
positioning technologies and facilitate a wide range of location-based services. Unlike
conventional information systems, LBS data management is challenging because LBS data
is high dimensional and spatio-temporal in nature, and information leakage may result in
location related privacy crises. The issue has become even more complicated, as database
outsourcing has become inevitable in view of the emerging popularity of LBS deployment.
In this paper, we tackle the research challenge and propose a SecUre Database Outsourcing
system, called SUDO. By combining the techniques of Hilbert space-filling curves, different
invertible encryption algorithms, and genuine mixed data, we show that SUDO is capable
of preserving location privacy and ownership of data for LBS against different attacks.
Moreover, the proposed solution is simple, effective, and scalable; and it shows promise in
supporting LBS data management with outsourced databases.

[1] R. Agrawal, J. Kiernan, R. Srikant, and Y. Xu. Order-preserving encryption for numeric data. In ACM SIGMOD, 2004.
[2] R. Bayer and E. McCreight. Organization and maintenance of large ordered indices. In Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control (SIGFIDET ’70), pages 107–141, New
York, NY, USA, 1970. ACM.
[3] R. Bayer and K. Unterauer. Prefix b-trees. ACM Trans. Database Syst., 2(1): 11–26, Mar. 1977.
[4] N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The r*-tree: An efficient and robust access method for points and rectangles. SIGMOD Rec., 19(2):322–331, May 1990.
[5] J. Benaloh. Dense probabilistic encryption. In Proceedings of the workshop on selected areas of cryptography, pages 120–128, 1994.
[6] A. Boldyreva, N. Chenette, and A. O’Neill. Order-preserving encryption revisited: Improved security analysis and alternative solutions. In Proceedings of the 31st Annual Conference on Advances in Cryptology (CRYPTO’11), 2011.
[7] R. Cheng, D. V. Kalashnikov, and S. Prabhakar. Querying imprecise data in moving object environments. IEEE Transactions on Knowledge and Data Engineering (TKDE’04), 16(9):1112–1127, Sept. 2004.
[8] R. Cheng, Y. Zhang, E. Bertino, and S. Prabhakar. Preserving user location privacy in mobile data management infrastructures. In Proceedings of the 6th International Conference on Privacy Enhancing Technologies (PET’06), pages
393–412, Berlin, Heidelberg, 2006. Springer-Verlag.
[9] C.-Y. Chow and M. F. Mokbel. Trajectory privacy in location-based services and data publication. ACM SIGKDD Explorations Newsletter, 13(1):19–29, Aug. 2011.
[10] S. Craver, B.-L. Yeo, and M. Yeung. Technical trials and legal tribulations. Commun. ACM, 41(7):45–54, July 1998.
[11] J. Daemen and V. Rijmen. The Design of RijndaeL: AES - The Advanced Encryption Standard. Information Security and Cryptography. Springer, 2002.
[12] E. Damiani, S. Vimercati, S. Jajodia, S. Paraboschi, and P. Samarati. Balancing confidentiality and efficiency in untrusted relational dbmss. In Proceedings of the 10th ACM conference on Computer and Communications Security (CCS’03), pages 93–102. ACM, 2003.
[13] M. Duckham and L. Kulik. A formal model of obfuscation and negotiation for location privacy. In Proceedings of the Third International Conference on Pervasive Computing (PERVASIVE’05), pages 152–170, Berlin, Heidelberg, 2005. Springer-Verlag.
[14] T. El Gamal. A public key cryptosystem and a signature scheme based on discrete logarithms. In Proceedings of CRYPTO 84 on Advances in Cryptology, pages 10–18, New York, NY, USA, 1985. Springer-Verlag New York, Inc.
[15] B. Gedik and L. Liu. Location privacy in mobile systems: A personalized anonymization model. In Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS ’05), pages 620–629, Washington, DC, USA, 2005. IEEE Computer Society.
[16] B. Gedik and L. Liu. Location privacy in mobile systems: A personalized anonymization model. In Proceedings of the 25th IEEE International Conference on Distributed Computing Systems (ICDCS ’05), pages 620–629, Washington, DC, USA, 2005. IEEE Computer Society.
[17] C. Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing (STOC ’09).
[18] S. Goldwasser and S. Micali. Probabilistic encryption & how to play mental poker keeping secret all partial information. In Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing (STOC ’82), pages 365–377, New York, NY, USA, 1982. ACM.
[19] M. Gruteser and D. Grunwald. Anonymous usage of location-based services through spatial and temporal cloaking. In Proceedings of the 1st International Conference on Mobile Systems, Applications and Services (MobiSys ’03), pages 31–42, New York, NY, USA, 2003. ACM.
[20] A. Guttman. R-trees: A dynamic index structure for spatial searching. SIGMOD Rec., 14(2):47–57, June 1984.
[21] H. Hacig¨um¨us¸, B. Iyer, C. Li, and S. Mehrotra. Executing sql over encrypted data in the database-service-provider model. In Proceedings of the 2002 ACM SIGMOD international conference on Management of data, pages 216–227. ACM, 2002.
[22] H. Hacigumus, B. Iyer, and S. Mehrotra. Providing database as a service. In Proceedings of the 18th International Conference on Data Engineering (ICDE’02), pages 29–38. IEEE, 2002.
[23] X. Hao, X. Meng, and J. Xu. Continuous density queries for moving objects. In Proceedings of the Seventh ACM International Workshop on Data Engineering for Wireless and Mobile Access (MobiDE ’08), pages 1–7, New York, NY, USA, 2008. ACM.
[24] D. Hilbert. Ueber die stetige abbildung einer line auf ein fl¨achenst¨uck. Mathematische Annalen, 38(3):459–460, 1891.
[25] D. S. Hochbaum and A. Pathria. Analysis of the greedy approach in problems of maximum k-coverage. Naval Research Logistics (NRL), 45(6):615–627, 1998.
[26] B. Hore, S. Mehrotra, M. Canim, and M. Kantarcioglu. Secure multidimensional range queries over outsourced data. The International Journal on Very Large Data Bases (The VLDB Journal), 21(3):333–358, June 2012.
[27] C. S. Jensen, D. Lin, B. C. Ooi, and R. Zhang. Effective density queries on continuouslymoving objects. In Proceedings of the 22Nd International Conference on Data Engineering (ICDE ’06), pages 71–, Washington, DC, USA, 2006. IEEE Computer Society.
[28] R. Kato, M. Iwata, T. Hara, A. Suzuki, X. Xie, Y. Arase, and S. Nishio. A dummy-based anonymization method based on user trajectory with pauses. In Proceedings of the 20th International Conference on Advances in Geographic Information Systems (SIGSPATIAL ’12), pages 249–258, New York, NY, USA, 2012. ACM.
[29] A. Khoshgozaran and C. Shahabi. Blind evaluation of nearest neighbor queries using space transformation to preserve location privacy. In Proceedings of the 10th International Conference on Advances in Spatial and Temporal Databases (SSTD’07), pages 239–257, Berlin, Heidelberg, 2007. Springer-Verlag.
[30] H. Kim, M. A. Lopez, S. T. Leutenegger, and K. Li. Efficient declustering of non-uniform multidimensional data using shifted hilbert curves. In Proceedings of the 9th International Conference on Database Systems for Advances Applications (DASFAA’04), pages 694–707, 2004.
[31] K.-C. Kim and S.-W. Yun. Mr-tree: A cache-conscious main memory spatial index structure for mobile gis. In Proceedings of the 4th International Conference on Web and Wireless Geographical Information Systems (W2GIS’04), pages 167–180, Berlin, Heidelberg, 2005. Springer-Verlag.
[32] W. Kozaczuk. Enigma: how the German machine cipher was broken, and how it was read by the Allies in World War Two. Univ Pubns of Amer, 1984.
[33] W.-S. Ku, L. Hu, C. Shahabi, and H. Wang. A query integrity assurance
scheme for accessing outsourced spatial databases. Geoinformatica, 17(1):97–124, January 2013.
[34] K. LeFevre, D. J. DeWitt, and R. Ramakrishnan. Mondrian multidimensional
k-anonymity. In Proceedings of the 22Nd International Conference on Data Engineering
(ICDE ’06), pages 25–, Washington, DC, USA, 2006. IEEE Computer Society.
[35] J. Li and E. R. Omiecinski. Efficiency and security trade-off in supporting range queries on encrypted databases. In Proceedings of the 19th Annual IFIP WG 11.3 Working Conference on Data and Applications Security (DBSec’05), pages 69–83, Berlin, Heidelberg, 2005. Springer-Verlag.
[36] N. Li and T. Li. t-closeness: Privacy beyond k-anonymity and -diversity. In Proceedings of IEEE 23rd International Conference on Data Engineering (ICDE07, volume 7, pages 106–115, 2007.
[37] I.-T. Lien, Y.-H. Lin, J.-R. Shieh, and J.-L. Wu. A novel privacy preserving location-based service protocol with secret circular shift for k-nn search. Trans. Info. For. Sec., 8(6):863–873, June 2013.
[38] K. Liu, C. Giannella, and H. Kargupta. An attacker’s view of distance preserving maps for privacy preserving data mining. In Proceedings of the 10th European Conference on Principle and Practice of Knowledge Discovery in Databases (PKDD’06), pages 297–308, Berlin, Heidelberg, 2006. Springer-Verlag.
[39] H. Lu, C. S. Jensen, and M. L. Yiu. Pad: Privacy-area aware, dummy-based location privacy in mobile services. In Proceedings of the Seventh ACM International Workshop on Data Engineering for Wireless and Mobile Access (MobiDE ’08), pages 16–23, New York, NY, USA, 2008. ACM.
[40] A. Machanavajjhala, D. Kifer, J. Gehrke, and M. Venkitasubramaniam. l-diversity: Privacy beyond k-anonymity. ACM Transactions on Knowledge Discovery from Data (TKDD’07), 1(1):3, 2007.
[41] E. M. Manz, J. Haddock, and J. Mittenthal. Optimization of an automated manufacturing system simulation model using simulated annealing. In Proceedings of the 21st Conference on Winter Simulation (WSC ’89), pages 390–395, New York, NY, USA, 1989. ACM.
[42] B. Moon, H. V. Jagadish, C. Faloutsos, and J. H. Saltz. Analysis of the clustering properties of hilbert space-filling curve. Technical report, College Park, MD, USA, 1996.
[43] P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In Eurocrypt, 1999.
[44] X. Pan, J. Xu, and X. Meng. Protecting location privacy against locationdependent attacks in mobile services. IEEE Transactions on Knowledge and Data Engineering (TKDE’12), 24(8):1506–1519, Aug. 2012.
[45] O. Pandey and Y. Rouselakis. Property preserving symmetric encryption. In Proceedings of the 31st Annual International Conference on Theory and Applications of Cryptographic Techniques (EUROCRYPT’12), pages 375–391, Berlin, Heidelberg, 2012. Springer-Verlag.
[46] S. Papadopoulos, S. Bakiras, and D. Papadias. Nearest neighbor search with strong location privacy. Proceedings of the VLDB Endowment (Proc. VLDB Endow.), 3(1-2):619–629, Sept. 2010.
[47] R. L. Rivest, L. Adleman, and M. L. Dertouzos. On data banks and privacy homomorphisms. Foundations of secure computation, 4(11):169–180, 1978.
[48] H. Sagan. Space-filling curves, volume 18. Springer-Verlag New York, 1994.
[49] Y. Tao, D. Papadias, and J. Sun. The tpr*-tree: An optimized spatio-temporal access method for predictive queries. In Proceedings of the 29th International Conference on Very Large Data Bases (VLDB ’03), volume 29, pages 790–801. VLDB Endowment, 2003.
[50] Y. Theodoridis, D. Papadias, E. Stefanakis, and T. Sellis. Direction relations and two-dimensional range queries: Optimisation techniques. Data Knowl. Eng., 27 (3):313–336, Oct. 1998.
[51] S. Tu, M. F. Kaashoek, S. Madden, and N. Zeldovich. Processing analytical queries over encrypted data. Proceedings of the VLDB Endowment (Proc. VLDB Endow.), 6(5):289–300, Mar. 2013.
[52] J. Wang and X. Du. A secure multi-dimensional partition based index in das. In Proceedings of the 10th Asia-Pacific Web Conference on Progress in WWW Research and Development (APWeb’08), pages 319–330, Berlin, Heidelberg, 2008. Springer-Verlag.
[53] S.-L. Wang, C.-Y. Chen, I.-H. Ting, and T.-P. Hong. Anonymous spatial query on non-uniform data. In Proceedings of the 14th International Conference on Information Integration and Web-based Applications & Services (IIWAS ’12), pages 126–131, New York, NY, USA, 2012. ACM.
[54] W. K. Wong, D. W.-l. Cheung, B. Kao, and N. Mamoulis. Secure knn computation on encrypted databases. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data (SIGMOD ’09), pages 139–152, New York, NY, USA, 2009. ACM.
[55] Z. Yang, S. Zhong, and R. N. Wright. Privacy-preserving queries on encrypted data. In Proceedings of the 11th European Conference on Research in Computer Security (ESORICS’06), pages 479–495, Berlin, Heidelberg, 2006. Springer-
Verlag.
[56] T.-H. You, W.-C. Peng, and W.-C. Lee. Protecting moving trajectories with dummies. In Proceedings of the 2007 International Conference on Mobile DatManagement (MDM ’07), pages 278–282, Washington, DC, USA, 2007. IEEE Computer Society.