A framework for searching encrypted databases

• Pedro Geraldo M. R. Alves Unicamp
• Diego F. Aranha Unicamp

DOI: https://doi.org/10.5753/sbseg.2016.19304

Resumo

Cloud computing is a ubiquitous paradigm. It has been responsible for a fundamental change in the way distributed computing is performed. The possibility to outsource the installation, maintenance and scalability of servers, added to competitive prices, makes this platform highly attractive to the industry. Despite this, privacy guarantees are still insufficient for data processed in the cloud, since the data owner has no real control over the processing hardware. This work proposes a framework for database encryption that preserves data secrecy on an untrusted environment and retains searching and updating capabilities. It employs order-revealing encryption to provide selection with time complexity in Θ(log n), and homomorphic encryption to enable computation over ciphertexts. When compared to the current state of the art, our approach provides higher security and flexibility. A proof-of-concept implementation on top of MongoDB is offered and presents an 11-factor overhead for a selection query over an encrypted database.

Referências

Alves, P. (2016). A proof-of-concept searchable encryption backend for mongodb. https://github.com/pdroalves/encrypted-mongodb. Last accessed: 09/08/2016.

BBC News (2016). Yahoo ’state’ hackers stole data from 500 million users. Last accessed: 23/09/2016.

Bellare, M., Desai, A., Pointcheval, D., and Rogaway, P. (1998). Advances in Cryptology—CRYPTO ’98: 18th Annual International Cryptology Conference Santa Barbara, California, USA August 23–27, 1998 Proceedings, chapter Relations among notions of security for public-key encryption schemes, pages 26–45. Springer Berlin Heidelberg, Berlin, Heidelberg.

Boldyreva, A., Chenette, N., Lee, Y., and O’Neill, A. (2009). Orderpreserving symmetric encryption. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5479 LNCS:224–241.

Boneh, D., Gentry, C., Halevi, S., Wang, F., and Wu, D. J. (2013). Private database queries using somewhat homomorphic encryption. In Proceedings of the 11th International Conference on Applied Cryptography and Network Security, ACNS’13, pages 102–118, Berlin, Heidelberg. Springer-Verlag.

Boneh, D., Lewi, K., Raykova, M., Sahai, A., Zhandry, M., and Zimmerman, J. (2015). Semantically Secure Order-Revealing Encryption: Multi-input Functional Encryption Without Obfuscation, pages 563–594. Springer Berlin Heidelberg, Berlin, Heidelberg.

Bösch, C., Hartel, P., Jonker, W., and Peter, A. (2014). A survey of provably secure searchable encryption. ACM Comput. Surv., 47(2):18:1–18:51.

Chenette, N., Lewi, K., Weis, S. A., and Wu, D. J. (2016). Practical order-revealing encryption with limited leakage. In FSE.

Chodorow, K. and Dirolf, M. (2010). MongoDB: The Definitive Guide. O’Reilly Media, Inc., 1st edition.

Codd, E. F. (1983). A relational model of data for large shared data banks. Commun. ACM, 26(6):64–69.

Daemen, J. and Rijmen, V. (1999). AES Proposal: Rijndael.

Dinh, H. T., Lee, C., Niyato, D., and Wang, P. (2013). A survey of mobile cloud computing: architecture, applications, and approaches. Wireless Communications and Mobile Computing, 13(18):1587–1611.

ElGamal, T. (1985). A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. In Blakley, G. and Chaum, D., editors, Advances in Cryptology, volume 196 of Lecture Notes in Computer Science, pages 10–18. Springer Berlin Heidelberg.

Greenwald, G. and MacAskill, E. (2013). NSA Prism program taps in to user data of Apple, Google and others.

Hoffa, C., Mehta, G., Freeman, T., Deelman, E., Keahey, K., Berriman, B., and Good, J. (2008). On the Use of Cloud Computing for Scientific Workflows. In eScience, 2008. eScience ’08. IEEE Fourth International Conference on, pages 640–645.

Kolesnikov, V. and Shikfa, A. (2012). On the limits of privacy provided by Order-Preserving Encryption. Bell Labs Technical Journal.

Lewi, K. and Wu, D. J. (2016). Order-revealing encryption: New constructions, applications, and lower bounds. Cryptology ePrint Archive, Report 2016/612.

Litzenberger, D. (2016). Python Cryptography Toolkit. http://www.pycrypto.org/. Last accessed: 07/03/2016.

Loftus, J., May, A., Smart, N. P., and Vercauteren, F. (2012). On CCASecure Somewhat Homomorphic Encryption. In Proceedings of the 18th International Conference on Selected Areas in Cryptography, SAC’11, pages 55–72, Berlin, Heidelberg. Springer-Verlag.

Miller, C. C. (2014). Revelations of N.S.A. spying cost U.S. tech companies. The New York Times. Last accessed: 02/04/2016.

Naveed, M., Kamara, S., and Wright, C. V. (2015). Inference attacks on property-preserving encrypted databases. In Proceedings of the 22Nd ACM SIGSAC Conference on Computer and Communications Security, CCS ’15, pages 644–655, New York, NY, USA. ACM.

Paillier, P. (1999). Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In Stern, J., editor, Advances in Cryptology — EUROCRYPT ’99, volume 1592 of Lecture Notes in Computer Science, pages 223–238. Springer Berlin Heidelberg.

Poddar, R., Boelter, T., and Popa, R. A. (2016). Arx: A strongly encrypted database system. Cryptology ePrint Archive, Report 2016/591.

Popa, R. A., Redfield, C. M. S., Zeldovich, N., and Balakrishnan, H. (2011). Cryptdb: Protecting confidentiality with encrypted query processing. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, SOSP ’11, pages 85–100, New York, NY, USA. ACM.

Sedgewick, R. (1983). Algorithms, chapter 15, page 199. Addison-Wesley.

Song, D. X., Wagner, D., Perrig, A., and Perrig, A. (2000). Practical techniques for searches on encrypted data. Proceeding 2000 IEEE Symposium on Security and Privacy. S&P 2000, pages 44–55.

Thomsen, S. (2015). Extramarital affair website Ashley Madison has been hacked and attackers are threatening to leak data online. Last accessed: 25/05/2016.

Weber, H. (2014). How the NSA & FBI made Facebook the perfect mass surveillance tool. Venture Beat. Published on 05/15/2014.

Xiao, Z. and Xiao, Y. (2013). Security and Privacy in Cloud Computing. IEEE Communications Surveys Tutorials, 15(2):843–859.