Generic multi-keyword ranked search on encrypted cloud data

Shabnam Kasra Kermanshahi, Joseph K. Liu, Ron Steinfeld, Surya Nepal

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

Although searchable encryption schemes allow secure search over the encrypted data, they mostly support conventional Boolean keyword search, without capturing any relevance of the search results. This leads to a large amount of post-processing overhead to find the most matching documents and causes an unnecessary communication cost between the servers and end-users. Such problems can be addressed efficiently using a ranked search system that retrieves the most relevant documents. However, existing state-of-the-art solutions in the context of Searchable Symmetric Encryption (SSE) suffer from either (a) security and privacy breaches due to the use of Order Preserving Encryption (OPE) or (b) non-practical solutions like using the two non-colluding servers. In this paper, we present a generic solution for multi-keyword ranked search over the encrypted cloud data. The proposed solution can be applied over different symmetric searchable encryption schemes. To demonstrate the practicality of our technique, in this paper we leverage the Oblivious Cross Tags (OXT) protocol of Cash et al. (2013) due to its scalability and remarkable flexibility to support different settings. Our proposed scheme supports the multi-keyword search on Boolean, ranked and limited range queries while keeping all of the OXT’s properties intact. The key contribution of this paper is that our scheme is resilience against all common attacks that take advantage of OPE leakage while only a single cloud server is used. Moreover, the results indicate that using the proposed solution the communication overhead decreases drastically when the number of matching results is large.
Original languageEnglish
Title of host publicationComputer Security - ESORICS 2019
Subtitle of host publication24th European Symposium on Research in Computer Security Luxembourg, September 23–27, 2019 Proceedings, Part I
EditorsKazue Sako, Steve Schneider, Peter Y. A. Ryan
Place of PublicationCham Switzerland
PublisherSpringer
Pages322-343
Number of pages22
ISBN (Electronic)9783030299590
ISBN (Print)9783030299583
DOIs
Publication statusPublished - 2019
EventEuropean Symposium On Research In Computer Security 2019 - Luxembourg, Luxembourg, Luxembourg
Duration: 23 Sep 201927 Sep 2019
Conference number: 24th
https://esorics2019.uni.lu/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11735
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceEuropean Symposium On Research In Computer Security 2019
Abbreviated titleESORICS 2019
CountryLuxembourg
CityLuxembourg
Period23/09/1927/09/19
Internet address

Keywords

  • SSE
  • Multi keywords
  • Ranked search

Cite this

Kasra Kermanshahi, S., Liu, J. K., Steinfeld, R., & Nepal, S. (2019). Generic multi-keyword ranked search on encrypted cloud data. In K. Sako, S. Schneider, & P. Y. A. Ryan (Eds.), Computer Security - ESORICS 2019: 24th European Symposium on Research in Computer Security Luxembourg, September 23–27, 2019 Proceedings, Part I (pp. 322-343). (Lecture Notes in Computer Science ; Vol. 11735). Cham Switzerland: Springer. https://doi.org/10.1007/978-3-030-29962-0_16
Kasra Kermanshahi, Shabnam ; Liu, Joseph K. ; Steinfeld, Ron ; Nepal, Surya. / Generic multi-keyword ranked search on encrypted cloud data. Computer Security - ESORICS 2019: 24th European Symposium on Research in Computer Security Luxembourg, September 23–27, 2019 Proceedings, Part I. editor / Kazue Sako ; Steve Schneider ; Peter Y. A. Ryan. Cham Switzerland : Springer, 2019. pp. 322-343 (Lecture Notes in Computer Science ).
@inproceedings{09bf1f8156e94cb7a278b37265040211,
title = "Generic multi-keyword ranked search on encrypted cloud data",
abstract = "Although searchable encryption schemes allow secure search over the encrypted data, they mostly support conventional Boolean keyword search, without capturing any relevance of the search results. This leads to a large amount of post-processing overhead to find the most matching documents and causes an unnecessary communication cost between the servers and end-users. Such problems can be addressed efficiently using a ranked search system that retrieves the most relevant documents. However, existing state-of-the-art solutions in the context of Searchable Symmetric Encryption (SSE) suffer from either (a) security and privacy breaches due to the use of Order Preserving Encryption (OPE) or (b) non-practical solutions like using the two non-colluding servers. In this paper, we present a generic solution for multi-keyword ranked search over the encrypted cloud data. The proposed solution can be applied over different symmetric searchable encryption schemes. To demonstrate the practicality of our technique, in this paper we leverage the Oblivious Cross Tags (OXT) protocol of Cash et al. (2013) due to its scalability and remarkable flexibility to support different settings. Our proposed scheme supports the multi-keyword search on Boolean, ranked and limited range queries while keeping all of the OXT’s properties intact. The key contribution of this paper is that our scheme is resilience against all common attacks that take advantage of OPE leakage while only a single cloud server is used. Moreover, the results indicate that using the proposed solution the communication overhead decreases drastically when the number of matching results is large.",
keywords = "SSE, Multi keywords, Ranked search",
author = "{Kasra Kermanshahi}, Shabnam and Liu, {Joseph K.} and Ron Steinfeld and Surya Nepal",
year = "2019",
doi = "10.1007/978-3-030-29962-0_16",
language = "English",
isbn = "9783030299583",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "322--343",
editor = "Sako, {Kazue } and Steve Schneider and {Y. A. Ryan}, {Peter }",
booktitle = "Computer Security - ESORICS 2019",

}

Kasra Kermanshahi, S, Liu, JK, Steinfeld, R & Nepal, S 2019, Generic multi-keyword ranked search on encrypted cloud data. in K Sako, S Schneider & P Y. A. Ryan (eds), Computer Security - ESORICS 2019: 24th European Symposium on Research in Computer Security Luxembourg, September 23–27, 2019 Proceedings, Part I. Lecture Notes in Computer Science , vol. 11735, Springer, Cham Switzerland, pp. 322-343, European Symposium On Research In Computer Security 2019, Luxembourg, Luxembourg, 23/09/19. https://doi.org/10.1007/978-3-030-29962-0_16

Generic multi-keyword ranked search on encrypted cloud data. / Kasra Kermanshahi, Shabnam; Liu, Joseph K.; Steinfeld, Ron; Nepal, Surya.

Computer Security - ESORICS 2019: 24th European Symposium on Research in Computer Security Luxembourg, September 23–27, 2019 Proceedings, Part I. ed. / Kazue Sako; Steve Schneider; Peter Y. A. Ryan. Cham Switzerland : Springer, 2019. p. 322-343 (Lecture Notes in Computer Science ; Vol. 11735).

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

TY - GEN

T1 - Generic multi-keyword ranked search on encrypted cloud data

AU - Kasra Kermanshahi, Shabnam

AU - Liu, Joseph K.

AU - Steinfeld, Ron

AU - Nepal, Surya

PY - 2019

Y1 - 2019

N2 - Although searchable encryption schemes allow secure search over the encrypted data, they mostly support conventional Boolean keyword search, without capturing any relevance of the search results. This leads to a large amount of post-processing overhead to find the most matching documents and causes an unnecessary communication cost between the servers and end-users. Such problems can be addressed efficiently using a ranked search system that retrieves the most relevant documents. However, existing state-of-the-art solutions in the context of Searchable Symmetric Encryption (SSE) suffer from either (a) security and privacy breaches due to the use of Order Preserving Encryption (OPE) or (b) non-practical solutions like using the two non-colluding servers. In this paper, we present a generic solution for multi-keyword ranked search over the encrypted cloud data. The proposed solution can be applied over different symmetric searchable encryption schemes. To demonstrate the practicality of our technique, in this paper we leverage the Oblivious Cross Tags (OXT) protocol of Cash et al. (2013) due to its scalability and remarkable flexibility to support different settings. Our proposed scheme supports the multi-keyword search on Boolean, ranked and limited range queries while keeping all of the OXT’s properties intact. The key contribution of this paper is that our scheme is resilience against all common attacks that take advantage of OPE leakage while only a single cloud server is used. Moreover, the results indicate that using the proposed solution the communication overhead decreases drastically when the number of matching results is large.

AB - Although searchable encryption schemes allow secure search over the encrypted data, they mostly support conventional Boolean keyword search, without capturing any relevance of the search results. This leads to a large amount of post-processing overhead to find the most matching documents and causes an unnecessary communication cost between the servers and end-users. Such problems can be addressed efficiently using a ranked search system that retrieves the most relevant documents. However, existing state-of-the-art solutions in the context of Searchable Symmetric Encryption (SSE) suffer from either (a) security and privacy breaches due to the use of Order Preserving Encryption (OPE) or (b) non-practical solutions like using the two non-colluding servers. In this paper, we present a generic solution for multi-keyword ranked search over the encrypted cloud data. The proposed solution can be applied over different symmetric searchable encryption schemes. To demonstrate the practicality of our technique, in this paper we leverage the Oblivious Cross Tags (OXT) protocol of Cash et al. (2013) due to its scalability and remarkable flexibility to support different settings. Our proposed scheme supports the multi-keyword search on Boolean, ranked and limited range queries while keeping all of the OXT’s properties intact. The key contribution of this paper is that our scheme is resilience against all common attacks that take advantage of OPE leakage while only a single cloud server is used. Moreover, the results indicate that using the proposed solution the communication overhead decreases drastically when the number of matching results is large.

KW - SSE

KW - Multi keywords

KW - Ranked search

U2 - 10.1007/978-3-030-29962-0_16

DO - 10.1007/978-3-030-29962-0_16

M3 - Conference Paper

SN - 9783030299583

T3 - Lecture Notes in Computer Science

SP - 322

EP - 343

BT - Computer Security - ESORICS 2019

A2 - Sako, Kazue

A2 - Schneider, Steve

A2 - Y. A. Ryan, Peter

PB - Springer

CY - Cham Switzerland

ER -

Kasra Kermanshahi S, Liu JK, Steinfeld R, Nepal S. Generic multi-keyword ranked search on encrypted cloud data. In Sako K, Schneider S, Y. A. Ryan P, editors, Computer Security - ESORICS 2019: 24th European Symposium on Research in Computer Security Luxembourg, September 23–27, 2019 Proceedings, Part I. Cham Switzerland: Springer. 2019. p. 322-343. (Lecture Notes in Computer Science ). https://doi.org/10.1007/978-3-030-29962-0_16