Research on the main methods and schemes of encryption with search capability

Authors

DOI:

https://doi.org/10.30837/rt.2022.2.209.14

Keywords:

database, data warehouse, confidentiality, encryption, searchable encryption

Abstract

The growing popularity of data outsourcing to third-party cloud servers causes their owners to have serious concerns about their security due to possible data leakage. A well-known measure to solve this problem and ensure the confidentiality of data is to encrypt it. However, the use of traditional encryption techniques is faced with the problem of how to allow untrusted cloud servers to perform search operations, while the actual data transmitted must remain confidential. Searchable encryption is a powerful tool, a class of cryptographic techniques that attempts to solve this problem. Searchable encryption acts as a data management technique that allows data owners to store and manage their data on a third-party, untrusted cloud server, and allows the data user to delegate search functions to the cloud server to retrieve that data. Currently, there are a number of approaches to solving this problem, although there is still no dominant solution. Therefore, the paper presents an overview of current secure search solutions. The main searchable encryption techniques are considered, which allow you to perform search operations on encrypted data without disclosing any information about what is being searched. The strengths and weaknesses of the analyzed methods are highlighted. Models and architectures of existing secure search engines are analyzed, taking into account the peculiarities of their operation scenarios. The problem of confidentiality in searchable encryption schemes is discussed. A comparative analysis of the performance of several searchable symmetric encryption schemes is given. Various gaps in the area under consideration are identified, with indication of open research problems.

References

Abadi D., Ailamaki A., Andersen D., Bailis P., Balazinska M., Bernstein P., Boncz P., Chaudhuri S., et al. The Seattle Report on Database Research. ACM SIGMOD Record. 2019. 48. P. 44–53.

General Data Protection Regulation GDPR. URL: https://gdpr-info.eu/ (дата звернення: 12.06.2022).

Payment Card Industry (PCI) Data Security Standard. Requirements and Testing Procedures Version 4.0. 2022. URL: https://www.pcisecuritystandards.org/documents/PCI-DSS-v4_0.pdf (дата звернення: 12.06.2022).

Atchinson B. K., Fox D. M. From the field: the politics of the health insurance portability and accountability act // Health affairs. 1997. 16(3). P. 146-150.

Scholl M., Stine K., Hash J., Bowen P., Johnson A., et al. NIST Special Publication 800-66 Revision 1. An Introductory Resource Guide for Implementing the Health Insurance Portability and Accountability Act (HIPAA) Security Rule. 2008. URL: https://nvlpubs.nist.gov/nistpubs/Legacy/SP/nistspecialpublication800-66r1.pdf (дата звернення: 12.06.2022).

Bösch, C., Hartel, P., Jonker, W., Peter, A. A survey of provably secure searchable encryption // ACM Computing Surveys (CSUR). 2014. 47(2). P. 1–51.

Fuller B., Varia M., Yerukhimovich A., Shen E., Hamlin A., Gadepally V., Shay R., Mitchell J. D., Cunningham R. K. Sok: Cryptographically protected database search // 2017 IEEE Symposium on Security and Privacy (SP), 2017. P. 172–191. https://doi.org/10.1109/SP.2017.10.

Gupta B., Mamta Secure Searchable Encryption and Data Management (1st ed.). CRC Press. 2021. 116 p. https://doi.org/10.1201/9781003107316.

Li R., Xu Z., Kang W., Yow K. C., Xu C. Z. Efficient multi-keyword ranked query over encrypted data in cloud computing // Future Generation Computer Systems. 2014. 30. P. 179–190.

Boneh D., Crescenzo G. D., Ostrovsky R., Persiano G. Public Key Encryption with Keyword Search // Cachin, C., Camenisch, J.L. (eds) Advances in Cryptology – EUROCRYPT 2004. EUROCRYPT 2004. Lecture Notes in Computer Science, 2004. Vol 3027. P. 506–522. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24676-3_30/

Katz J., Sahai A., Waters B. Predicate encryption supporting disjunctions, polynomial equations, and inner products // Smart, N. (eds) Advances in Cryptology – EUROCRYPT 2008. EUROCRYPT 2008. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg, 2008. Vol. 4965. P. 146–162. https://doi.org/10.1007/978-3-540-78967-3_9.

Shamir A. Identity-Based Cryptosystems and Signature Schemes // Blakley, G.R., Chaum, D. (eds) Advances in Cryptology. CRYPTO 1984. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 1985. Vol. 196. P. 47–53. https://doi.org/10.1007/3-540-39568-7_5.

Boneh D., Franklin M. Identity-Based Encryption from the Weil Pairing // Kilian, J. (eds) Advances in Cryptology – CRYPTO 2001. CRYPTO 2001. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 2001. Vol 2139. P. 213–229. https://doi.org/10.1007/3-540-44647-8_13.

Boneh D., Franklin M. Identity-based encryption from the Weil pairing // SIAM journal on computing. 2003. 32(3). P. 586–615.

Cocks C. An Identity Based Encryption Scheme Based on Quadratic Residues // Honary, B. (eds) Cryptography and Coding. Cryptography and Coding 2001. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 2001. Vol 2260. P. 360–363. https://doi.org/10.1007/3-540-45325-3_32.

Boyen X., Waters B. Anonymous Hierarchical Identity-Based Encryption (Without Random Oracles) // Dwork, C. (eds) Advances in Cryptology – CRYPTO 2006. CRYPTO 2006. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 2006. Vol 4117. P. 290–307. https://doi.org/10.1007/11818175_17.

Shi E., Bethencourt J., Chan T. H., Song D., Perrig A. Multi-dimensional range query over encrypted data. // 2007 IEEE Symposium on Security and Privacy (SP'07). IEEE, 2007. P. 350–364. https://doi.org/10.1109/SP.2007.29.

Sahai A., Waters B. Fuzzy Identity-Based Encryption // Cramer, R. (eds) Advances in Cryptology – EUROCRYPT 2005. EUROCRYPT 2005. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 2005. Vol 3494. P. 457–473. https://doi.org/10.1007/11426639_27.

Lewko A., Okamoto T., Sahai A., Takashima K., Waters, B. Fully Secure Functional Encryption: Attribute-Based Encryption and (Hierarchical) Inner Product Encryption // Gilbert, H. (eds) Advances in Cryptology – EUROCRYPT 2010. Lecture Notes in Computer Science, 2010. Vol 6110. P. 62-91. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13190-5_4.

Katz J., Sahai A., Waters B. Predicate encryption supporting disjunctions, polynomial equations, and inner products // Journal of cryptology. 2013. 26(2). P. 191-224. https://doi.org/10.1007/s00145-012-9119-4.

Okamoto T., Takashima K. Hierarchical Predicate Encryption for Inner-Products // Matsui, M. (eds) Advances in Cryptology. ASIACRYPT 2009. Lecture Notes in Computer Science, 2009, Vol 5912. P. 214-231. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10366-7_13.

Okamoto T., Takashima K. Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption // Rabin, T. (eds) Advances in Cryptology – CRYPTO 2010. CRYPTO 2010. Lecture Notes in Computer Science, 2010. Vol 6223. P. 191–208. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14623-7_11.

Okamoto, T., Takashima, K. Adaptively Attribute-Hiding (Hierarchical) Inner Product Encryption // Pointcheval, D., Johansson, T. (eds) Advances in Cryptology – EUROCRYPT 2012. EUROCRYPT 2012. Lecture Notes in Computer Science, 2012. Vol 7237. P. 591–608. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29011-4_35.

Okamoto T., Takashima K. Adaptively attribute-hiding (hierarchical) inner product encryption // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. 2016. 99(1). P. 92-117.

Park J. H. Inner-product encryption under standard assumptions // Designs, Codes and Cryptography, 2011. 58(3), 235–257. https://doi.org/10.1007/s10623-010-9405-9.

Baek J., Safavi-Naini, R., Susilo W. Public Key Encryption with Keyword Search Revisited // Gervasi, O., Murgante, B., Laganà, A., Taniar, D., Mun, Y., Gavrilova, M.L. (eds) Computational Science and Its Applications – ICCSA 2008. ICCSA 2008. Lecture Notes in Computer Science, 2008. Vol 5072. P. 1249-1259. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-69839-5_96.

Rhee H. S. et al. Improved searchable public key encryption with designated tester // Proceedings of the 4th International Symposium on Information, Computer, and Communications Security. ASIACCS '09. ACM. 2009. P. 376-379. https://doi.org/10.1145/1533057.1533108.

Abdalla M., Bellare M., Catalano D., Kiltz E., Kohno T., Lange T., Shi H. Searchable Encryption Revisited: Consistency Properties, Relation to Anonymous IBE, and Extensions // Journal of cryptology, 2008. 21(3). P. 350–391. https://doi.org/10.1007/s00145-007-9006-6.

Gentry C. Practical Identity-Based Encryption Without Random Oracles // Vaudenay, S. (eds) Advances in Cryptology – EUROCRYPT 2006. EUROCRYPT 2006. Lecture Notes in Computer Science, 2006. Vol 4004. P. 445–464. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11761679_27.

Kiltz E. From selective-ID to full security: The case of the inversion-based Boneh-Boyen IBE scheme. Cryptology ePrint Archive. 2007. URL: https://eprint.iacr.org/2007/033.pdf.

Nishide T., Yoneyama K., Ohta K. Attribute-Based Encryption with Partially Hidden Encryptor-Specified Access Structures // Bellovin, S.M., Gennaro, R., Keromytis, A., Yung, M. (eds) Applied Cryptography and Network Security. ACNS 2008. Lecture Notes in Computer Science, 2008. Vol 5037. P. 111-129. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68914-0_7.

Horwitz J., Lynn B. Toward Hierarchical Identity-Based Encryption // Knudsen, L.R. (eds) Advances in Cryptology – EUROCRYPT 2002. EUROCRYPT 2002. Lecture Notes in Computer Science, 2002. Vol 2332. P. 466–481 Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46035-7_31.

Gentry C., Silverberg A. Hierarchical ID-Based Cryptography // Zheng, Y. (eds) Advances in Cryptology — ASIACRYPT 2002. ASIACRYPT 2002. Lecture Notes in Computer Science, 2002, Vol 2501. P. 548–566. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36178-2_34.

Boneh D., Boyen X., Goh EJ. Hierarchical Identity Based Encryption with Constant Size Ciphertext // Cramer R. (eds) Advances in Cryptology – EUROCRYPT 2005. EUROCRYPT 2005. Lecture Notes in Computer Science, 2005. Vol 3494. P. 440–456. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11426639_26.

Shi E., Waters B. Delegating Capabilities in Predicate Encryption Systems // Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds) Automata, Languages and Programming. ICALP 2008. Lecture Notes in Computer Science, 2008. Vol 5126. P. 560–578. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70583-3_46.

Lee K. S., Lee D. H. New techniques for anonymous hibe with short ciphertexts in prime order groups // KSII Transactions on Internet and Information Systems (TIIS). 2010. 4(5). P. 968–988.

Boneh D., Waters B. Conjunctive, Subset, and Range Queries on Encrypted Data // Vadhan, S.P. (eds) Theory of Cryptography. TCC 2007. Lecture Notes in Computer Science, 2007. Vol 4392. P. 535–554. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70936-7_29.

Paillier P. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes // Stern J. (eds) Advances in Cryptology – EUROCRYPT ’99. EUROCRYPT 1999. Lecture Notes in Computer Science, 1999. Vol 1592. P. 223–238. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48910-X_16.

ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms // IEEE transactions on information theory. 1985. 31(4). P. 469-472. https://doi.org/10.1109/TIT.1985.1057074.

Boneh D., Goh EJ., Nissim K. Evaluating 2-DNF Formulas on Ciphertexts // Kilian J. (eds) Theory of Cryptography. TCC 2005. Lecture Notes in Computer Science, 2005. Vol 3378. P. 325–341. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30576-7_18.

Gentry C. Fully homomorphic encryption using ideal lattices // Proceedings of the forty-first annual ACM symposium on Theory of computing. 2009. P. 169-178. https://doi.org/10.1145/1536414.1536440.

Gentry C. Computing arbitrary functions of encrypted data //Communications of the ACM. 2010. 53(3). P. 97-105. https://doi.org/10.1145/1666420.1666444.

van Dijk M., Gentry C., Halevi S., Vaikuntanatha, V. Fully Homomorphic Encryption over the Integers // Gilbert, H. (eds) Advances in Cryptology – EUROCRYPT 2010. EUROCRYPT 2010. Lecture Notes in Computer Science, 2010. Vol 6110. P. 24–43. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-13190-5_2.

Naehrig M., Lauter K., Vaikuntanathan V. Can homomorphic encryption be practical? // Proceedings of the 3rd ACM workshop on Cloud computing security workshop. 2011. P. 113-124. https://doi.org/10.1145/2046660.2046682.

Brakerski Z., Vaikuntanathan V. Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages // Rogaway P. (eds) Advances in Cryptology – CRYPTO 2011. CRYPTO 2011. Lecture Notes in Computer Science, 2011. Vol 6841. P. 505–524. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22792-9_29.

Kamara S., Papamanthou C., Roeder T. Dynamic searchable symmetric encryption // Proceedings of the 2012 ACM conference on Computer and communications security. 2012. P. 965–976.

Shen E., Shi E., Waters B. Predicate Privacy in Encryption Systems // Reingold O. (eds) Theory of Cryptography. TCC 2009. Lecture Notes in Computer Science, 2009. Vol 5444. P. 457–473. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00457-5_27.

Song D. X., Wagner D., Perrig A. Practical techniques for searches on encrypted data // Proceeding 2000 IEEE symposium on security and privacy. S&P 2000. IEEE, 2000. P. 44–55. https://doi.org/10.1109/SECPRI.2000.848445.

Curtmola R., Garay J., Kamara S., Ostrovsky R. Searchable symmetric encryption: improved definitions and efficient constructions // Journal of Computer Security, 2011. 19(5). P. 895–934.

Fiat A., Naor M. Broadcast encryption // Annual International Cryptology Conference. Springer, Berlin, Heidelberg, 1993. P. 480–491.

Goh E. J. Secure Indexes. Cryptology ePrint Archive, Report 2003/216. 2003. URL: http://eprint.iacr.org/2003/216/

Chang Y. C., Mitzenmacher M. Privacy preserving keyword searches on remote encrypted data // International conference on applied cryptography and network security. Springer, Berlin, Heidelberg, 2005. P. 442–455.

Wang Y., Wang J., Chen X. Secure searchable encryption: a survey // Journal of communications and information networks. 2016. 1(4). P. 52–65. https://doi.org/10.11959/j.issn.2096-1081.2016.043.

Kamara S., Papamanthou C. Parallel and dynamic searchable symmetric encryption // International conference on financial cryptography and data security. LNCS 7859. Springer, Berlin, Heidelberg, 2013. P. 258–274. https://doi.org/10.1007/978-3-642-39884-1_22.

van Liesdonk P., Sedghi S., Doumen J., Hartel P., Jonker W. Computationally Efficient Searchable Symmetric Encryption // Jonker, W., Petković, M. (eds) Secure Data Management. SDM 2010. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 2010. Vol 6358. P. 87–100. https://doi.org/10.1007/978-3-642-15546-8_7.

Kurosawa K., Ohtaki Y. UC-secure searchable symmetric encryption // International conference on financial cryptography and data security. LNCS. Springer, Berlin, Heidelberg. 2012. Vol. 7397. P. 285–298. https://doi.org/10.1007/978-3-642-32946-3_21.

Downloads

Published

2022-06-24

How to Cite

Yesin, V. ., & Vilihura, V. . (2022). Research on the main methods and schemes of encryption with search capability. Radiotekhnika, 2(209), 138–155. https://doi.org/10.30837/rt.2022.2.209.14

Issue

No. 209 (2022): Radiotekhnika

Section

Articles

License

Authors who publish with this journal agree to the following terms:

1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).