Top

World Wide Web

Published in:

13-03-2020

An enhanced wildcard-based fuzzy searching scheme in encrypted databases

Authors: Jiaxun Hua, Yu Liu, He Chen, Xiuxia Tian, Cheqing Jin

Published in: World Wide Web | Issue 3/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Under the overwhelming trend in Cloud Computing, Cloud Databases possessing high scalability / high availability / high parallel performance have become a prevalent paradigm of data outsourcing. In consideration of security and privacy, both individuals and enterprises prefer to outsource service data in encrypted form. Unfortunately, most encrypted databases cannot support such complicated queries as wildcard-based fuzzy searching, which, to some extent, limits the practicability in real applications. To explore more business logic in encrypted databases, an enhanced wildcard-based fuzzy searching scheme (enWFS) is proposed in this paper, which integrates specialized Adjacent Character Matrix/Tensor into proxy middleware, appends two types of ancillary columns into data tables, as well as designs an advanced adaptive overwriting method to revise query expressions with wildcards (‘%’ and ‘_’). Meanwhile, some security enhancements and TupleRank are added to enWFS scheme so as to achieve superior fuzzy searching experiences. Extensive experiments based on real datasets demonstrate effectiveness, feasibility of our proposal.

previous article Personalized top-n influential community search over large social networks

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

For the sake of simplicity, among illustrations of this paper, the beginning and the end of a string will be uniformly represented as ‘#’ (as you can see in Table 1). But these two cases will be treated respectively during the implementation.

In many real applications, sensitive information may only contained in some of the columns in data tables, so data owners just need to focus on those specific columns. i.e. attribute values in those specific columns are regarded as the corpus.

LSH dimension means the number of features returned from LSH corresponding to a word in attribute values. Details will be introduced in the next section.

This is an offline process conducted by data owners regularly. After updates of CFA, ACM and ACT are completed locally, both will be outsourced to the cloud.

After several tuples are matched via ancillary columns, corresponding DET ciphertext will be returned for decryption. i.e. Ancillary columns are used for fuzzy searching, and all matched results are achieved by decrypting DET ciphertext.

A word’s signature on each dimension is assured of an equal width by padding zero.

We use popular n-gram methods described in Section 3.1.1 .

Remark: In the clause ‘a__le%’, ‘a__le’ may refer to ‘apple’, ‘ankle’, etc, so ‘a__le’ can be treated as an unbroken word in the clause ‘a__le%’; On the contrary, ‘app%’ may refer to ‘applaud’, ‘applicant’, etc, so ‘app’ in the clause ‘app%’ is reckoned to be a fragment of words.

This flag array provides a reference for our algorithm, and it will be revised in the process.

We don’t consider the number of total underscores. e.g.mcu = 2 for ‘a__l_’.

This is a limitation of Searchable Symmetric Encryption constructions [6, 12, 15, 20, 21], which is out of the scope of our scheme.

About 5000 rows of data are processed in the c-LSH experiment while nearly 50000 rows of data are processed here.

We construct these three structures separately in the experiment. In fact, the construction can be conducted simultaneously in real applications.

So we evaluate the FSE (LSH) and FSE (BF) respectively with regard to c-LSH and c-BF.

Following the standard of good accuracy stated above the accuracy metrics, if the result set from a scheme has false negative phenomenon, we won’t evaluate its # of false positive tuples anymore.

Results from experiments in Section 5.2.4 are used here.

e.g. If the original clause is ‘a__le%’, attribute values satisfying ‘apple%’, ‘ankle%’, etc, should all be retrieved.

Boldyreva, A., Chenette, N.: Efficient Fuzzy Search on Encrypted Data. In: FSE 2014 Workshop, pp. 613–633 (2014)CrossRef

Cash, D., Jaeger, J., Jarecki, S., Jutla, C.S., Krawczyk, H., Rosu, M., Steiner, M.: Dynamic Searchable Encryption in Very-Large Databases: Data Structures and Implementation. In: NDSS (2014)

Cash, D., Jarecki, S., Jutla, C.S., Krawczyk, H., Rosu, M., Steiner, M.: Highly-Scalable Searchable Symmetric Encryption with Support for Boolean Queries. In: CRYPTO 2013, Proceedings, Part I, pp. 353–373 (2013)CrossRef

Chase, M., Kamara, S.: Structured Encryption and Controlled Disclosure. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 577–594 (2010)CrossRef

Chen, H., Tian, X., Jin, C.: Fuzzy Searching Encryption with Complex Wild-Cards Queries on Encrypted Database. In: APWeb-WAIM 2018, pp. 3–18 (2018)

Curtmola, R., Garay, J., Kamara, S., Ostrovsky, R.: Searchable Symmetric Encryption:Improved Definitions and Efficient Constructions. In: ACM Conference on Computer and Communications Security, pp. 79–88 (2006)

Fan, K., Yin, J., Wang, J., Li, H., Yang, Y.: Multi-Keyword Fuzzy and Sortable Ciphertext Retrieval Scheme for Big Data. In: GLOBECOM 2017, pp. 1–6 (2017)

Fu, Z., Wu, X., Guan, C., Sun, X., Ren, K.: Toward efficient multi-keyword fuzzy search over encrypted outsourced data with accuracy improvement. IEEE Trans. Inf. Forensic. Secur. 11(12), 2706–2716 (2017)CrossRef

Gonzalez, L.M.V., Rodero-merino, L., Caceres, J., Lindner, M.A.: A break in the clouds: towards a cloud definition. Comput. Commun. Rev. 39(1), 50–55 (2009)

10.

Hahn, F., Kerschbaum, F.: Searchable encryption with secure and efficient updates. In: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, pp. 310–320 (2014)

11.

Kamara, S., Papamanthou, C.: Parallel and Dynamic Searchable Symmetric Encryption. In: International Conference on Financial Cryptography and Data Security, pp. 258–274 (2013)CrossRef

12.

Kamara, S., Papamanthou, C., Roeder, T.: Dynamic Searchable Symmetric Encryption. In: Acm Conference on Computer and Communications Security, pp. 965–976 (2012)

13.

Kurosawa, K., Ohtaki, Y.: Uc-Secure Searchable Symmetric Encryption. In: International Conference on Financial Cryptography and Data Security, pp. 285–298 (2012)CrossRef

14.

Kurosawa, K., Sasaki, K., Ohta, K., Yoneyama, K.: Uc-Secure Dynamic Searchable Symmetric Encryption Scheme. In: IWSEC, pp. 73–90 (2016)

15.

Kuzu, M., Islam, M.S., Kantarcioglu, M.: Efficient Similarity Search over Encrypted Data. In: IEEE International Conference on Data Engineering, pp. 1156–1167 (2012)

16.

Li, J., Liu, Z., Chen, X., Xhafa, F., Tan, X., Wong, D.S.: L-encdb: a lightweight framework for privacy-preserving data queries in cloud computing. Knowl.-Based Syst. 79, 18–26 (2015)CrossRef

17.

Liu, Z., Li, J., Li, J., Jia, C., Yang, J., Yuan, K.: Sql-based fuzzy query mechanism over encrypted database. Int. J. Data Warehous. Min. (IJDWM) 10 (4), 71–87 (2014)CrossRef

18.

Liu, Z., Ma, H., Li, J., Jia, C., Li, J., Yuan, K.: Secure Storage and Fuzzy Query over Encrypted Databases. In: International Conference on Network and System Security, pp. 439–450 (2013)CrossRef

19.

Popa, R.A., Li, F.H., Zeldovich, N.: An ideal-security protocol for order-preserving encoding. IEEE Symposium on Security and Privacy, pp. 463–477 (2013)

20.

Popa, R.A., Redfield, C.M.S., Zeldovich, N., Balakrishnan, H.: Cryptdb: Protecting Confidentiality with Encrypted Query Processing. In: ACM SOSP, pp. 85–100 (2011)

21.

Song, D.X., Wagner, D.A., Perrig, A.: Practical Techniques for Searches on Encrypted Data. In: IEEE Symposium on Security and Privacy, pp. 44–55 (2000)

22.

Tetali, S.D., Lesani, M., Majumdar, R., Millstein, T.D.: Mrcrypt: Static Analysis for Secure Cloud Computations. In: ACM SIGPLAN OOPSLA, pp. 271–286 (2013)CrossRef

23.

Wang, B., Yu, S., Lou, W., Hou, Y.T.: Privacy-Preserving Multi-Keyword Fuzzy Search over Encrypted Data in the Cloud. In: IEEE INFOCOM, pp. 2112–2120 (2014)

24.

Wang, C., Cao, N., Li, J., Ren, K.: Secure Ranked Keyword Search over Encrypted Cloud Data. In: IEEE International Conference on Distributed Computing Systems (ICDCS), pp. 253–262 (2010)

25.

Wang, J., Ma, H., Tang, Q., Li, J., Zhu, H., Ma, S., Chen, X.: Efficient verifiable fuzzy keyword search over encrypted data in cloud computing. Comput. Sci. Inf. Syst. 10(2), 667–684 (2013)CrossRef

26.

Wang, Q., He, M., Du, M., Chow, S.S.M., Lai, R.W.F., Zou, Q.: Searchable encryption over feature-rich data. IEEE Trans. Dependable Sec. Comput. 15(3), 496–510 (2018)CrossRef

27.

Wei, X., Zhang, H.: Verifiable Multi-Keyword Fuzzy Search over Encrypted Data in the Cloud. In: International Conference on Advanced Materials and Information Technology Processing, pp. 271–277 (2016)

Title: An enhanced wildcard-based fuzzy searching scheme in encrypted databases
Authors: Jiaxun Hua
Yu Liu
He Chen
Xiuxia Tian
Cheqing Jin
Publication date: 13-03-2020
Publisher: Springer US
Published in: World Wide Web / Issue 3/2020
Print ISSN: 1386-145X
Electronic ISSN: 1573-1413
DOI: https://doi.org/10.1007/s11280-019-00774-x

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Other articles of this Issue 3/2020

A comprehensive analysis of adverb types for mining user sentiments on amazon product reviews

Web service QoS prediction: when collaborative filtering meets data fluctuating in big-range

From ideal to reality: segmentation, annotation, and recommendation, the vital trajectory of intelligent micro learning

Special issue on Web information management and applications

Robust SVM with adaptive graph learning

iLinker: a novel approach for issue knowledge acquisition in GitHub projects

Premium Partner