SQL queries over encrypted databases: a survey

References

• Agrawal, R., Kiernan, J., Srikant, R., & Xu, Y. (2004). Order preserving encryption for numeric data. In Proceedings of the 2004 ACM SIGMOD international conference on management of data (pp. 563–574).
   Google Scholar
• Alsirhani, A., Bodorik, P., & Sampalli, S. (2017). Improving database security in cloud computing by fragmentation of data. In 2017 International conference on computer and applications (ICCA) (pp. 43–49).
   Google Scholar
• Amorim, I., & Costa, I. (2023). Leveraging searchable encryption through homomorphic encryption: A comprehensive analysis. Mathematics, 11(13), 2948. https://doi.org/10.3390/math11132948
   Web of Science ®Google Scholar
• Antonopoulos, P., Arasu, A., Singh, K. D., Eguro, K., Gupta, N., Jain, R., Kaushik, R., Kodavalla, H., Kossmann, D., Ogg, N., & Ramamurthy, R. (2020). Azure SQL database always encrypted. In Proceedings of the 2020 ACM SIGMOD international conference on management of data (pp. 1511–1525).
   Google Scholar
• Arasu, A., Blanas, S., Eguro, K., Kaushik, R., Kossmann, D., Ramamurthy, R., & Venkatesan, R. (2013). Orthogonal security with cipherbase. In Conference on innovative data systems research.
   Google Scholar
• Arasu, A., & Kaushik, R. (2013). Oblivious query processing. arXiv preprint arXiv:1312.4012.
   Google Scholar
• Armbrust, M., Fox, A., Griffith, R., Joseph, A. D., Katz, R., Konwinski, A., Lee, G., Patterson, D., Rabkin, A., Stoica, I., & Zaharia, M. (2010). A view of cloud computing. Communications of the ACM, 53(4), 50–58. https://doi.org/10.1145/1721654.1721672
   Web of Science ®Google Scholar
• Bajaj, S., & Sion, R. (2011). 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).
   Google Scholar
• Barber, R., Lohman, G., Pandis, I., Raman, V., Sidle, R., Attaluri, G., Chainani, N., Lightstone, S., & Sharpe, D. (2014). Memory-efficient hash joins. Proceedings of the VLDB Endowment, 8(4), 353-364. https://doi.org/10.14778/2735496.2735499
   Google Scholar
• Bellare, M., Boldyreva, A., & O'Neill, A. (2007). Deterministic and efficiently searchable encryption. In Advances in cryptology-CRYPTO 2007: 27th annual international cryptology conference (pp. 535–552).
   Google Scholar
• Benabbas, S., Gennaro, R., & Vahlis, Y. (2011). Verifiable delegation of computation over large datasets. In Annual cryptology conference (pp. 111–131).
   Google Scholar
• Bindschaedler, V., Naveed, M., Pan, X., Wang, X. F., & Huang, Y. (2015). Practicing oblivious access on cloud storage: The gap, the fallacy, and the new way forward. In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security (pp. 837–849).
   Google Scholar
• Blackstone, L., Kamara, S., & Moataz, T. (2019). Revisiting leakage abuse attacks. IACR Cryptology ePrint Archive, 2019, 1175. https://doi.org/10.14722/ndss.2020.23103
   Google Scholar
• Boldyreva, A., Chenette, N., Lee, Y., & O'neill, A. (2009). Order-preserving symmetric encryption. In Advances in cryptology-EUROCRYPT 2009: 28th annual international conference on the theory and applications of cryptographic techniques (pp. 224–241).
   Google Scholar
• Boldyreva, A., Chenette, N., & O'Neill, A. (2011). Order-preserving encryption revisited: Improved security analysis and alternative solutions. In Advances in cryptology–CRYPTO 2011: 31st annual cryptology conference (pp. 578–595).
   Google Scholar
• Cao, W., Liu, Y., Cheng, Z., Zheng, N., Li, W., Wu, W., Ouyang, L., Wang, P., Wang, Y., Kuan, R., & Liu, Z. (2020). {POLARDB} meets computational storage: Efficiently support analytical workloads in {Cloud−Native} relational database. In 18th USENIX conference on file and storage technologies (FAST 20) (pp. 29–41).
   Google Scholar
• Carbunar, B., & Sion, R. (2011). Toward private joins on outsourced data. IEEE Transactions on Knowledge and Data Engineering, 24(9), 1699–1710. https://doi.org/10.1109/TKDE.2011.142
   Web of Science ®Google Scholar
• Cash, D., Jaeger, J., Jarecki, S., Jutla, C., Krawczyk, H., Roşu, M.-C., & Steiner, M. (2014). Dynamic searchable encryption in very-large databases: Data structures and implementation. IACR Cryptology ePrint Archive, 2014, 853. https://doi.org/10.14722/NDSS.2014.23264
   Google Scholar
• Cash, D., Jarecki, S., Jutla, C., Krawczyk, H., Roşu, M.-C., & Steiner, M. (2013). Highly-scalable searchable symmetric encryption with support for boolean queries. In Advances in cryptology–CRYPTO 2013: 33rd annual cryptology conference (pp. 353–373).
   Google Scholar
• Cash, D., Ng, R., & Rivkin, A. (2021). Improved structured encryption for SQL databases via hybrid indexing. In International conference on applied cryptography and network security (pp. 480–510).
   Google Scholar
• Chamberlin, D. D., & Boyce, R. F. (1974). SEQUEL: A structured English query language. In Proceedings of the 1974 ACM SIGFIDET (now SIGMOD) workshop on data description, access and control (pp. 249–264).
   Google Scholar
• Chandra, A. K., & Merlin, P. M. (1977). Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the ninth annual ACM symposium on theory of computing (pp. 77–90).
   Google Scholar
• Chase, M., & Kamara, S. (2010). Structured encryption and controlled disclosure. In Advances in cryptology-ASIACRYPT 2010: 16th international conference on the theory and application of cryptology and information security (pp. 577–594).
   Google Scholar
• Chen, L., & Li, J., & Li, J. (2023). Toward forward and backward private dynamic searchable symmetric encryption supporting data deduplication and conjunctive queries. IEEE Internet of Things Journal, 10(19), 17408–17423. https://doi.org/10.1109/JIOT.2023.3274390
   Web of Science ®Google Scholar
• Chen, N., Li, J., Zhang, Y., & Guo, Y. (2022). Efficient CP-ABE scheme with shared decryption in cloud storage. IEEE Transactions on Computers, 71(1), 175–184. https://doi.org/10.1109/TC.2020.3043950
   Web of Science ®Google Scholar
• Chen, S., Li, J., Zhang, Y., & Han, J. (2023). Efficient revocable attribute-based encryption with verifiable data integrity. IEEE Internet of Things Journal. https://doi.org/10.1109/JIOT.2023.3325996
   Google Scholar
• Chen, X., Li, H., Li, J., Wang, Q., Huang, X., Susilo, W., & Xiang, Y. (2021). Publicly verifiable databases with all efficient updating operations. IEEE Transactions on Knowledge and Data Engineering, 33(12), 3729–3740. https://doi.org/10.1109/TKDE.2020.2975777
   Web of Science ®Google Scholar
• Chen, X., Li, J., Huang, X., Ma, J., & Lou, W. (2015). New publicly verifiable databases with efficient updates. IEEE Transactions on Dependable and Secure Computing12(5), 546–556. https://doi.org/10.1109/TDSC.2014.2366471
   Web of Science ®Google Scholar
• Chen, X., Li, J., Weng, J., Ma, J., & Lou, W. (2015). Verifiable computation over large database with incremental updates. IEEE Transactions on Computers, 65(10), 3184–3195. https://doi.org/10.1109/TC.2015.2512870
   Web of Science ®Google Scholar
• Chenmaodong and Huawei Co. Ltd. (n.d.). secGear. Retrieved February 22, 2021, from https://gitee.com/src-openeuler/secGear.
   Google Scholar
• Chu, C.-K., Zhu, W.-T., Han, J., Liu, J. K., Xu, J., & Zhou, J. (2013). Security concerns in popular cloud storage services. IEEE Pervasive Computing, 12(4), 50–57. https://doi.org/10.1109/MPRV.2013.72
   Web of Science ®Google Scholar
• Ciriani, V., di Vimercati, S. D. C., Foresti, S., Jajodia, S., Paraboschi, S., & Samarati, P. (2009). Keep a few: Outsourcing data while maintaining confidentiality. In Computer Security–ESORICS 2009: 14th European symposium on research in computer security (pp. 440–455).
   Google Scholar
• Codd, E. F. (1970). A relational model of data for large shared data banks. Communications of the ACM, 13(6), 377–387. https://doi.org/10.1145/362384.362685
   Web of Science ®Google Scholar
• Cooney, M. (2009). IBM touts encryption innovation; new technology performs calculations on encrypted data without decrypting it. Computer World. https://www.computerworld.com/article/2526031/ibm-toutsencryption-innovation.html
   Google Scholar
• Costan, V., & Devadas, S. (2016). Intel SGX explained. IACR Cryptology ePrint Archive, 2016, 86.
   Google Scholar
• Curtmola, R., Garay, J., Kamara, S., & Ostrovsky, R. (2006). Searchable symmetric encryption: Improved definitions and efficient constructions. In Proceedings of the 13th ACM conference on computer and communications security (pp. 79–88).
   Google Scholar
• Damiani, E., Vimercati, S. D. C., Jajodia, S., Paraboschi, S., & Samarati, P. (2003). Balancing confidentiality and efficiency in untrusted relational DBMSs. In Proceedings of the 10th ACM conference on computer and communications security (pp. 93–102).
   Google Scholar
• Eltayesh, F. (2017). Verifiable outsourced database model: A game-theoretic approach [Ph.D. Dissertation]. Concordia University.
   Google Scholar
• Eskandarian, S., & Zaharia, M. (2017). Oblidb: Oblivious query processing using hardware enclaves. arXiv preprint arXiv:1710.00458.
   Google Scholar
• Espiritu, Z., Markatou, E. A., & Tamassia, R. (2022). Time-and space-efficient aggregate range queries over encrypted databases. Proceedings on Privacy Enhancing Technologies, 2022(4), 684–704. https://doi.org/10.56553/popets-2022-0128
   Google Scholar
• Fuller, B., Varia, M., Yerukhimovich, A., Shen, E., Hamlin, A., Gadepally, V., Shay, R., Mitchell, J. D., & Cunningham, R. K. (2017). Sok: Cryptographically protected database search. In 2017 IEEE symposium on security and privacy (SP) (pp. 172–191).
   Google Scholar
• Gentry, C. (2009). Fully homomorphic encryption using ideal lattices. In Proceedings of the forty-first annual ACM symposium on Theory of computing (pp. 169–178).
   Google Scholar
• Goh, E.-J. (2003). Secure indexes. IACR Cryptology ePrint Archive, 2003, 216.
   Google Scholar
• Goldreich, O., Micali, S., & Wigderson, A. (2019). How to play any mental game, or a completeness theorem for protocols with honest majority. In Providing sound foundations for cryptography: On the work of Shafi Goldwasser and Silvio Micali (pp. 307–328).
   Google Scholar
• Goldreich, O., & Ostrovsky, R. (1996). Software protection and simulation on oblivious RAMs. Journal of the ACM (JACM), 43(3), 431–473. https://doi.org/10.1145/233551.233553
   Web of Science ®Google Scholar
• Goyal, V., Pandey, O., Sahai, A., & Waters, B. (2006). Attribute-based encryption for fine-grained access control of encrypted data. In Proceedings of the 13th ACM conference on computer and communications security (pp. 89–98).
   Google Scholar
• Grubbs, P., Sekniqi, K., Bindschaedler, V., Naveed, M., & Ristenpart, T. (2017). Leakage-abuse attacks against order-revealing encryption. In 2017 IEEE symposium on security and privacy (SP) (pp. 655–672).
   Google Scholar
• Gu, Q., & Liu, P. (2007). Denial of service attacks. Handbook of Computer Networks: Distributed Networks, Network Planning, Control, Management, and New Trends and Applications, 3, 454–468. https://doi.org/10.1002/9781118256107
   Google Scholar
• Hahn, F., Loza, N., & Kerschbaum, F. (2019). Joins over encrypted data with fine granular security. In 2019 IEEE 35th international conference on data engineering (ICDE) (pp. 674–685).
   Google Scholar
• Hur, J., & Noh, D. K. (2010). Attribute-based access control with efficient revocation in data outsourcing systems. IEEE Transactions on Parallel and Distributed Systems, 22(7), 1214–1221. https://doi.org/10.1109/TPDS.2010.203
   Web of Science ®Google Scholar
• Islam, M. S., Kuzu, M., & Kantarcioglu, M. (2012). Access pattern disclosure on searchable encryption: Ramification, attack and mitigation. In Ndss (Vol. 20, p. 12).
   Google Scholar
• Jutla, C., & Patranabis, S. (2022). Efficient searchable symmetric encryption for join queries. In International conference on the theory and application of cryptology and information security (pp. 304–333).
   Google Scholar
• Kamara, S., & Moataz, T. (2018). SQL on structurally-encrypted databases. In Advances in cryptology–ASIACRYPT 2018: 24th international conference on the theory and application of cryptology and information security (pp. 149–180).
   Google Scholar
• Kerschbaum, F., Härterich, M., Grofig, P., Kohler, M., Schaad, A., Schröpfer, A., & Tighzert, W. (2013). Optimal re-encryption strategy for joins in encrypted databases. In Data and applications security and privacy XXVII: 27th annual IFIP WG 11.3 conference (pp. 195–210).
   Google Scholar
• Krastnikov, S., Kerschbaum, F., & Stebila, D. (2020). Efficient oblivious database joins. arXiv preprint arXiv:2003.09481.
   Google Scholar
• Lacharité, M.-S., & Paterson, K. G. (2015). A note on the optimality of frequency analysis vs. ℓp-optimization. IACR Cryptology ePrint Archive, 2015, 1158.
   Google Scholar
• Latif, R., Abbas, H., Assar, S., & Ali, Q. (2014). Cloud computing risk assessment: A systematic literature review. Future Information Technology: FutureTech 2013, 285–295. https://doi.org/10.1007/978-3-642-40861-8
   Google Scholar
• Li, J., & Chen, X., & Huang, X. (2015). New attribute–based authentication and its application in anonymous cloud access service. International Journal of Web and Grid Services, 11(1), 125–141. https://doi.org/10.1504/IJWGS.2015.067161
   Web of Science ®Google Scholar
• Li, J., Liu, Z., Chen, X., Xhafa, F., Tan, X., & Wong, D. S. (2015). L-EncDB: A lightweight framework for privacy-preserving data queries in cloud computing. Knowledge-Based Systems, 79, 18–26. https://doi.org/10.1016/j.knosys.2014.04.010
   Web of Science ®Google Scholar
• Li, J., Zhang, Y., Ning, J., Huang, X., Poh, G. S., & Wang, D. (2022). Attribute based encryption with privacy protection and accountability for CloudIoT. IEEE Transactions on Cloud Computing, 10(2), 762–773. https://doi.org/10.1109/TCC.2020.2975184
   Web of Science ®Google Scholar
• Li, M., Du, R., & Jia, C. (2021). A multi-user shared searchable encryption scheme supporting SQL query. In Security and privacy in new computing environments: Third EAI international conference (pp. 406–422).
   Google Scholar
• Li, M., Zhao, X., Chen, L., Tan, C., Li, H., Wang, S., Mi, Z., Xia, Y., Li, F., & Chen, H. (2023). Encrypted databases made secure yet maintainable. In 17th USENIX symposium on operating systems design and implementation (OSDI 23) (pp. 117–133).
   Google Scholar
• Lv, C., Wang, J., Sun, S.-F., Wang, Y., & Qi, S., & Chen, X. (2023). Towards practical multi-client order-revealing encryption: Improvement and application. IEEE Transactions on Dependable and Secure Computing, 1–16. https://doi.org/10.1109/tdsc.2023.3268652
   Google Scholar
• Mell, P., & Grance, T. (2009). Effectively and securely using the cloud computing paradigm. NIST, Information Technology Laboratory, 2(8), 304–311.
   Google Scholar
• Microsoft (2022). https://azure.microsoft.com/en-us/.
   Google Scholar
• Microsoft (2023a). Virtualization-based security (VBS). https://learn.microsoft.com/en-us/windows-hardware/design/device-experiences/oem-vbs.
   Google Scholar
• Microsoft (2023b). What's new for azure key vault. https://learn.microsoft.com/en-us/azure/key-vault/general/whats-new.
   Google Scholar
• Mironov, I., Segev, G., & Shahaf, I. (2017). Strengthening the security of encrypted databases: Non-transitive joins. In Theory of cryptography: 15th international conference (pp. 631–661).
   Google Scholar
• Mishra, P., Poddar, R., Chen, J., Chiesa, A., & Popa, R. A. (2018). Oblix: An efficient oblivious search index. In 2018 IEEE symposium on security and privacy (SP) (pp. 279–296).
   Google Scholar
• Naveed, M., Kamara, S., & Wright, C. V. (2015). Inference attacks on property-preserving encrypted databases. In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security (pp. 644–655).
   Google Scholar
• Paillier, P. (1999). Public-key cryptosystems based on composite degree residuosity classes. In International conference on the theory and applications of cryptographic techniques (pp. 223–238).
   Google Scholar
• Pandey, O., & Rouselakis, Y. (2012). Property preserving symmetric encryption. In Advances in cryptology–EUROCRYPT 2012: 31st annual international conference on the theory and applications of cryptographic techniques (pp. 375–391).
   Google Scholar
• Pang, H., & Ding, X. (2014). Privacy-preserving ad-hoc equi-join on outsourced data. ACM Transactions on Database Systems (TODS), 39(3), 1–40. https://doi.org/10.1145/2629501
   Web of Science ®Google Scholar
• Papadimitriou, A., Bhagwan, R., Chandran, N., Ramjee, R., Haeberlen, A., Singh, H., Modi, A., & Badrinarayanan, S. (2016). Big data analytics over encrypted datasets with seabed. In 12th USENIX symposium on operating systems design and implementation (OSDI 16) (pp. 587–602).
   Google Scholar
• Pappas, V., Krell, F., Vo, B., Kolesnikov, V., Malkin, T., Geol Choi, S., George, W., Keromytis, A., & Bellovin, S. (2014). Blind seer: A scalable private DBMS. In 2014 IEEE symposium on security and privacy (pp. 359–374).
   Google Scholar
• Pinto, S., & Santos, N. (2019). Demystifying arm trustzone: A comprehensive survey. ACM Computing Surveys (CSUR), 51(6), 1–36. https://doi.org/10.1145/3291047
   Web of Science ®Google Scholar
• Poddar, R., Boelter, T., & Popa, R. A. (2019). Arx: An encrypted database using semantically secure encryption. Proceedings of the VLDB Endowment, 12(11), 1664–1678. https://doi.org/10.14778/3342263.3342641
   Web of Science ®Google Scholar
• Popa, R. A., Redfield, C. M. S., Zeldovich, N., & Balakrishnan, H. (2011). CryptDB: Protecting confidentiality with encrypted query processing. In Proceedings of the twenty-third ACM symposium on operating systems principles (pp. 85–100).
   Google Scholar
• Popa, R. A., Stark, E., Valdez, S., Helfer, J., Zeldovich, N., & Balakrishnan, H. (2014). Building web applications on top of encrypted data using Mylar. In 11th USENIX symposium on networked systems design and implementation (NSDI 14) (pp. 157–172).
   Google Scholar
• Premkamal, P. K., Pasupuleti, S. K., & Alphonse, P. J. A (2019). A new verifiable outsourced ciphertext-policy attribute based encryption for big data privacy and access control in cloud. Journal of Ambient Intelligence and Humanized Computing, 10(7), 2693–2707. https://doi.org/10.1007/s12652-018-0967-0
   Web of Science ®Google Scholar
• Priebe, C., Vaswani, K., & Costa, M. (2018). EnclaveDB: A secure database using SGX. In 2018 IEEE symposium on security and privacy (SP) (pp. 264–278).
   Google Scholar
• Reddy, K. S., & Kumari, K. P. (2022). A scheme for verifying integrity of SQL query processing on encrypted databases. CVR Journal of Science and Technology, 22(1), 1–6.
   Google Scholar
• Sabt, M., Achemlal, M., & Bouabdallah, A. (2015). Trusted execution environment: What it is, and what it is not. In 2015 IEEE trustcom/BigDataSE/ISPA (Vol. 1, pp. 57–64).
   Google Scholar
• Shafieinejad, M., Gupta, S., Liu, J. Y., Karabina, K., & Kerschbaum, F. (2022). Equi-joins over encrypted data for series of queries. In 2022 IEEE 38th international conference on data engineering (ICDE) (pp. 1635–1648).
   Google Scholar
• Song, D. X., Wagner, D., & Perrig, A. (2000). Practical techniques for searches on encrypted data. In Proceeding 2000 IEEE symposium on security and privacy (pp. 44–55).
   Google Scholar
• Sun, Y., Wang, S., & Li, H., & Li, F. (2021). Building enclave-native storage engines for practical encrypted databases. Proceedings of the VLDB Endowment, 14(6), 1019–1032. https://doi.org/10.14778/3447689.3447705
   Web of Science ®Google Scholar
• Tu, S., Kaashoek, M. F., Madden, S., & Zeldovich, N. (2013). Processing analytical queries over encrypted data. Proceedings of the VLDB Endowment, 6(5), 289–300. https://doi.org/10.14778/2535573.2488336
   Google Scholar
• Van Schaik, S., Minkin, M., Kwong, A., Genkin, D., & Yarom, Y. (2021). CacheOut: Leaking data on Intel CPUs via cache evictions. In 2021 IEEE symposium on security and privacy (SP) (pp. 339–354).
   Google Scholar
• Vinayagamurthy, D., Gribov, A., & Gorbunov, S. (2019). StealthDB: A scalable encrypted database with full SQL query support. Proceedings on Privacy Enhancing Technologies, 2019(3), 370–388. https://doi.org/10.2478/popets-2019-0052
   Google Scholar
• Wei, J., Chen, X., Huang, X., Hu, X., & Susilo, W. (2021). RS-HABE: Revocable-storage and hierarchical attribute-based access scheme for secure sharing of e-health records in public cloud. IEEE Transactions on Dependable and Secure Computing, 18(5), 2301–2315.
   Web of Science ®Google Scholar
• Zhang, Y., Katz, J., & Papamanthou, C. (2016). All your queries are belong to us: The power of {File−Injection} attacks on searchable encryption. In 25th USENIX security symposium (USENIX Security 16) (pp. 707–720).
   Google Scholar
• Zhang, Z., Chen, X., Li, J., Tao, X., & Ma, J. (2019). HVDB: A hierarchical verifiable database scheme with scalable updates. Journal of Ambient Intelligence and Humanized Computing, 10(8), 3045–3057. https://doi.org/10.1007/s12652-018-0757-8
   Web of Science ®Google Scholar
• Zheng, W., Dave, A., Beekman, J. G., Popa, R. A., Gonzalez, J. E., & Stoica, I. (2017). Opaque: An oblivious and encrypted distributed analytics platform. In 14th USENIX symposium on networked systems design and implementation (NSDI 17) (pp. 283–298).
   Google Scholar
• Zhu, J., Cheng, K., Liu, J., & Guo, L. (2021). Full encryption: An end to end encryption mechanism in GaussDB. Proceedings of the VLDB Endowment, 14(12), 2811–2814. https://doi.org/10.14778/3476311.3476351
   Web of Science ®Google Scholar