Abstract
With the current advances in Cloud Computing, outsourcing data has never been so tempting. Along with outsourcing a database comes the privacy versus performance discussion. Order-Preserving Encryption (OPE) is one of the most attractive techniques for database encryption since it allows to execute range and rank queries efficiently without decrypting the data. On the other hand, people are reluctant to use OPE-based techniques in practice because of their vulnerability against adversaries with knowledge of the domain, its frequency distribution and query logs. This paper formally defines three real world driven attacks, called Domain Attack, Frequency Attack and Query Log Attack, typically launched by an honest-but-curious database or systems administrator. We also introduce measures to capture the probability distribution of the adversary’s advantage under each attacker model. Most importantly, we present a novel technique called Randomly Partitioned Encryption (RPE) to minimize the adversary’s advantage. Finally, we show that RPE not only withstands real world database adversaries, but also shows good performance that is close to state-of-art OPE schemes for both, read- and write-intensive workloads.
Chapter PDF
Similar content being viewed by others
Keywords
References
Agrawal, R., et al.: Order preserving encryption for numeric data. In: Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, pp. 563–574. ACM (2004)
Agrawal, R., et al.: Privacy-preserving data mining. ACM Sigmod Record 29(2), 439–450 (2000)
Arasu, A., et al.: Orthogonal Security with Cipherbase. In: CIDR. Citeseer (2013)
Bajaj, S., et al.: TrustedDB: a trusted hardware based database with privacy and data confidentiality. In: Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, pp. 205–216. ACM (2011)
Berger, B., et al.: Approximation alogorithms for the maximum acyclic subgraph problem. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 236–243. Society for Industrial and Applied Mathematics (1990)
Boldyreva, A., Chenette, N., O’Neill, A.: Order-preserving encryption revisited: Improved security analysis and alternative solutions. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 578–595. Springer, Heidelberg (2011)
Boldyreva, A., Chenette, N., Lee, Y., O’Neill, A.: Order-preserving symmetric encryption. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 224–241. Springer, Heidelberg (2009)
Chow, R., et al.: Controlling data in the cloud: outsourcing computation without outsourcing control. In: Proceedings of the 2009 ACM Workshop on Cloud Computing Security, pp. 85–90. ACM (2009)
Damiani, E., et al.: Balancing confidentiality and efficiency in untrusted relational DBMSs. In: Proceedings of the 10th ACM Conference on Computer and Communications Security, pp. 93–102. ACM (2003)
ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1985)
Elovici, Y., Waisenberg, R., Shmueli, E., Gudes, E.: A structure preserving database encryption scheme. In: Jonker, W., Petković, M. (eds.) SDM 2004. LNCS, vol. 3178, pp. 28–40. Springer, Heidelberg (2004)
Gentry, C.: A fully homomorphic encryption scheme. PhD thesis. Stanford University (2009)
Guruswami, V., et al.: Beating the random ordering is hard: Inapproximability of maximum acyclic subgraph. In: IEEE 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 573–582. IEEE (2008)
Hacigümüş, H., et al.: Executing SQL over encrypted data in the database-service-provider model. In: Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, pp. 216–227. ACM (2002)
Hildenbrand, S., et al.: Query processing on encrypted data in the cloud. Tech. rep. 735. Department of Computer Science, ETH Zurich (2011)
Hsueh, S.: Database encryption in SQL server 2008 enterprise edition. Microsoft, SQL Server Technical Article (2008)
Kadhem, H., et al.: A Secure and Efficient Order Preserving Encryption Scheme for Relational Databases. In: KMIS, pp. 25–35 (2010)
Kadhem, H., et al.: MV-OPES: Multivalued-order preserving encryption scheme: A novel scheme for encrypting integer value to many different values. IEICE Transactions on Information and Systems 93(9), 2520–2533 (2010)
Katz, J., et al.: Introduction to modern cryptography: principles and protocols. CRC Press (2007)
Malkin, T., et al.: Order-Preserving Encryption Secure Beyond One-Wayness. Tech. rep. Citeseer (2013)
Nanda, A.: Transparent Data Encryption. Oracle Magazine (2005)
Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999)
Popa, R.A., et al.: An ideal-security protocol for order-preserving encoding. In: 2013 IEEE Symposium on Security and Privacy (SP), pp. 463–477. IEEE (2013)
Popa, R.A., et al.: Cryptdb: protecting confidentiality with encrypted query processing. In: Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, pp. 85–100. ACM (2011)
Sanamrad, T., et al.: POP: a new encryption scheme for dynamic databases. Tech. rep. 782. Department of Computer Science, ETH Zurich (2013)
Seungmin, L., et al.: Chaotic order preserving encryption for efficient and secure queries on databases. IEICE Transactions on Information and Systems 92(11), 2207–2217 (2009)
Sion, R.: Secure data outsourcing. In: Proceedings of the 33rd International Conference on Very Large Data Bases, pp. 1431–1432. VLDB Endowment (2007)
Smart, N.P., Vercauteren, F.: Fully homomorphic encryption with relatively small key and ciphertext sizes. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 420–443. Springer, Heidelberg (2010)
Tu, S., et al.: Processing analytical queries over encrypted data. In: Proceedings of the 39th International Conference on Very Large Data Bases, pp. 289–300. VLDB Endowment (2013)
van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 24–43. Springer, Heidelberg (2010)
Wang, H., et al.: Efficient secure query evaluation over encrypted XML databases. In: Proceedings of the 32nd International Conference on Very Large Data Bases, pp. 127–138. VLDB Endowment (2006)
Wang, S., et al.: Is Homomorphic Encryption the Holy Grail for Database Queries on Encrypted Data? Technical report, Department of Computer Science, UCSB (2012)
Wozniak, S., et al.: Beyond the ideal object: towards disclosure-resilient order-preserving encryption schemes. In: Proceedings of the 2013 ACM Workshop on Cloud Computing Security Workshop, pp. 89–100. ACM (2013)
Xiao, L., et al.: A Note for the Ideal Order-Preserving Encryption Object and Generalized Order-Preserving Encryption. In: IACR Cryptology ePrint Archive 2012, p. 350 (2012)
Yang, Z., Zhong, S., Wright, R.N.: Privacy-preserving queries on encrypted data. In: Gollmann, D., Meier, J., Sabelfeld, A. (eds.) ESORICS 2006. LNCS, vol. 4189, pp. 479–495. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 IFIP International Federation for Information Processing
About this paper
Cite this paper
Sanamrad, T., Braun, L., Kossmann, D., Venkatesan, R. (2014). Randomly Partitioned Encryption for Cloud Databases. In: Atluri, V., Pernul, G. (eds) Data and Applications Security and Privacy XXVIII. DBSec 2014. Lecture Notes in Computer Science, vol 8566. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43936-4_20
Download citation
DOI: https://doi.org/10.1007/978-3-662-43936-4_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-43935-7
Online ISBN: 978-3-662-43936-4
eBook Packages: Computer ScienceComputer Science (R0)