FETCH: A cloud-native searchable encryption scheme enabling efficient pattern search on encrypted data within cloud services

Shen Ming Chung, Ming Der Shieh, Tzi Cker Chiueh

Research output: Contribution to journalArticle

Abstract

Searchable encryption (SE) is considered important as it provides both confidentiality and searchability for the data stored in semi-trusted environments such as cloud. However, it is rarely deployed because most SE schemes are not native to cloud services as they require database modifications. In this paper, we present an SE scheme called Frequency-Eliminated Trapdoor-Character Hopping (FETCH) that, based on novel common-conditioned-subsequence-preserving (CCSP) techniques, is able to work natively with off-the-shelf databases and supports wildcard-based pattern search on encrypted data thereof. In fact, with the CCSP techniques, we transform the problem of wildcard SE searching into a problem of subsequence searching, which is solved fast in most databases and thus fits well with cloud services in general. Although in our security analysis, CCSP removes the possibility of obtaining theoretical indistinguishability between indexed items, we show that FETCH does provide adequate confidentiality protection and fares much better than other existing wildcard SE schemes in terms of query performance, storage overhead, and deployment complexity. In particular, FETCH is able to efficiently handle data sets whose size is multiple orders of magnitude larger than those that existing schemes can comfortably support.

Original languageEnglish
Article numbere4141
JournalInternational Journal of Communication Systems
DOIs
Publication statusAccepted/In press - 2019 Jan 1

Fingerprint

Cryptography

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Cite this

@article{fb87cc9d63d84149b4a3d79ee521d535,
title = "FETCH: A cloud-native searchable encryption scheme enabling efficient pattern search on encrypted data within cloud services",
abstract = "Searchable encryption (SE) is considered important as it provides both confidentiality and searchability for the data stored in semi-trusted environments such as cloud. However, it is rarely deployed because most SE schemes are not native to cloud services as they require database modifications. In this paper, we present an SE scheme called Frequency-Eliminated Trapdoor-Character Hopping (FETCH) that, based on novel common-conditioned-subsequence-preserving (CCSP) techniques, is able to work natively with off-the-shelf databases and supports wildcard-based pattern search on encrypted data thereof. In fact, with the CCSP techniques, we transform the problem of wildcard SE searching into a problem of subsequence searching, which is solved fast in most databases and thus fits well with cloud services in general. Although in our security analysis, CCSP removes the possibility of obtaining theoretical indistinguishability between indexed items, we show that FETCH does provide adequate confidentiality protection and fares much better than other existing wildcard SE schemes in terms of query performance, storage overhead, and deployment complexity. In particular, FETCH is able to efficiently handle data sets whose size is multiple orders of magnitude larger than those that existing schemes can comfortably support.",
author = "Chung, {Shen Ming} and Shieh, {Ming Der} and Chiueh, {Tzi Cker}",
year = "2019",
month = "1",
day = "1",
doi = "10.1002/dac.4141",
language = "English",
journal = "International Journal of Communication Systems",
issn = "1074-5351",
publisher = "John Wiley and Sons Ltd",

}

TY - JOUR

T1 - FETCH

T2 - A cloud-native searchable encryption scheme enabling efficient pattern search on encrypted data within cloud services

AU - Chung, Shen Ming

AU - Shieh, Ming Der

AU - Chiueh, Tzi Cker

PY - 2019/1/1

Y1 - 2019/1/1

N2 - Searchable encryption (SE) is considered important as it provides both confidentiality and searchability for the data stored in semi-trusted environments such as cloud. However, it is rarely deployed because most SE schemes are not native to cloud services as they require database modifications. In this paper, we present an SE scheme called Frequency-Eliminated Trapdoor-Character Hopping (FETCH) that, based on novel common-conditioned-subsequence-preserving (CCSP) techniques, is able to work natively with off-the-shelf databases and supports wildcard-based pattern search on encrypted data thereof. In fact, with the CCSP techniques, we transform the problem of wildcard SE searching into a problem of subsequence searching, which is solved fast in most databases and thus fits well with cloud services in general. Although in our security analysis, CCSP removes the possibility of obtaining theoretical indistinguishability between indexed items, we show that FETCH does provide adequate confidentiality protection and fares much better than other existing wildcard SE schemes in terms of query performance, storage overhead, and deployment complexity. In particular, FETCH is able to efficiently handle data sets whose size is multiple orders of magnitude larger than those that existing schemes can comfortably support.

AB - Searchable encryption (SE) is considered important as it provides both confidentiality and searchability for the data stored in semi-trusted environments such as cloud. However, it is rarely deployed because most SE schemes are not native to cloud services as they require database modifications. In this paper, we present an SE scheme called Frequency-Eliminated Trapdoor-Character Hopping (FETCH) that, based on novel common-conditioned-subsequence-preserving (CCSP) techniques, is able to work natively with off-the-shelf databases and supports wildcard-based pattern search on encrypted data thereof. In fact, with the CCSP techniques, we transform the problem of wildcard SE searching into a problem of subsequence searching, which is solved fast in most databases and thus fits well with cloud services in general. Although in our security analysis, CCSP removes the possibility of obtaining theoretical indistinguishability between indexed items, we show that FETCH does provide adequate confidentiality protection and fares much better than other existing wildcard SE schemes in terms of query performance, storage overhead, and deployment complexity. In particular, FETCH is able to efficiently handle data sets whose size is multiple orders of magnitude larger than those that existing schemes can comfortably support.

UR - http://www.scopus.com/inward/record.url?scp=85076376334&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85076376334&partnerID=8YFLogxK

U2 - 10.1002/dac.4141

DO - 10.1002/dac.4141

M3 - Article

AN - SCOPUS:85076376334

JO - International Journal of Communication Systems

JF - International Journal of Communication Systems

SN - 1074-5351

M1 - e4141

ER -