Result pattern hiding searchable encryption for conjunctive queries

Shangqi Lai, Sikhar Patranabis, Amin Sakzad, Joseph K. Liu, Debdeep Mukhopadhyay, Ron Steinfeld, Shi-Feng Sun, Dongxi Liu, Cong Zuo

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

Abstract

The recently proposed Oblivious Cross-Tags (OXT) protocol (CRYPTO 2013) has broken new ground in designing efficient searchable symmetric encryption (SSE) protocol with support for conjunctive keyword search in a single-writer single-reader framework. While the OXT protocol offers high performance by adopting a number of specialised data-structures, it also trades-off security by leaking ‘partial’ database information to the server. Recent attacks have exploited similar partial information leakage to breach database confidentiality. Consequently, it is an open problem to design SSE protocols that plug such leakages while retaining similar efficiency. In this paper, we propose a new SSE protocol, called Hidden Cross-Tags (HXT), that removes ‘Keyword Pair Result Pattern’ (KPRP) leakage for conjunctive keyword search. We avoid this leakage by adopting two additional cryptographic primitives - Hidden Vector Encryption (HVE) and probabilistic (Bloom filter) indexing into the HXT protocol. We propose a ‘lightweight’ HVE scheme that only uses efficient symmetric-key building blocks, and entirely avoids elliptic curve-based operations. At the same time, it affords selective simulation-security against an unbounded number of secret-key queries. Adopting this efficient HVE scheme, the overall practical storage and computational overheads of HXT over OXT are relatively small (no more than 10% for two keywords query, and 21% for six keywords query), while providing a higher level of security.

Original languageEnglish
Title of host publicationCCS’18 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security
Subtitle of host publicationOctober 15-19, 2018 Toronto, ON, Canada
EditorsMichael Backes, XiaoFeng Wang
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Pages745-762
Number of pages18
ISBN (Electronic)9781450356930
DOIs
Publication statusPublished - 2018
EventACM Conference on Computer and Communications Security 2018 - Beanfield Centre, Toronto, Canada
Duration: 15 Oct 201819 Oct 2018
Conference number: 25th
https://www.sigsac.org/ccs/CCS2018/ (Conference website)

Conference

ConferenceACM Conference on Computer and Communications Security 2018
Abbreviated titleCCS 2018
CountryCanada
CityToronto
Period15/10/1819/10/18
Internet address

Keywords

  • Hidden Vector Encryption
  • Leakage Profile
  • Searchable Encryption

Cite this

Lai, S., Patranabis, S., Sakzad, A., Liu, J. K., Mukhopadhyay, D., Steinfeld, R., ... Zuo, C. (2018). Result pattern hiding searchable encryption for conjunctive queries. In M. Backes, & X. Wang (Eds.), CCS’18 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security: October 15-19, 2018 Toronto, ON, Canada (pp. 745-762). New York NY USA: Association for Computing Machinery (ACM). https://doi.org/10.1145/3243734.3243753
Lai, Shangqi ; Patranabis, Sikhar ; Sakzad, Amin ; Liu, Joseph K. ; Mukhopadhyay, Debdeep ; Steinfeld, Ron ; Sun, Shi-Feng ; Liu, Dongxi ; Zuo, Cong. / Result pattern hiding searchable encryption for conjunctive queries. CCS’18 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security: October 15-19, 2018 Toronto, ON, Canada. editor / Michael Backes ; XiaoFeng Wang. New York NY USA : Association for Computing Machinery (ACM), 2018. pp. 745-762
@inproceedings{2ac3c923c6f7447b9da440e058a86760,
title = "Result pattern hiding searchable encryption for conjunctive queries",
abstract = "The recently proposed Oblivious Cross-Tags (OXT) protocol (CRYPTO 2013) has broken new ground in designing efficient searchable symmetric encryption (SSE) protocol with support for conjunctive keyword search in a single-writer single-reader framework. While the OXT protocol offers high performance by adopting a number of specialised data-structures, it also trades-off security by leaking ‘partial’ database information to the server. Recent attacks have exploited similar partial information leakage to breach database confidentiality. Consequently, it is an open problem to design SSE protocols that plug such leakages while retaining similar efficiency. In this paper, we propose a new SSE protocol, called Hidden Cross-Tags (HXT), that removes ‘Keyword Pair Result Pattern’ (KPRP) leakage for conjunctive keyword search. We avoid this leakage by adopting two additional cryptographic primitives - Hidden Vector Encryption (HVE) and probabilistic (Bloom filter) indexing into the HXT protocol. We propose a ‘lightweight’ HVE scheme that only uses efficient symmetric-key building blocks, and entirely avoids elliptic curve-based operations. At the same time, it affords selective simulation-security against an unbounded number of secret-key queries. Adopting this efficient HVE scheme, the overall practical storage and computational overheads of HXT over OXT are relatively small (no more than 10{\%} for two keywords query, and 21{\%} for six keywords query), while providing a higher level of security.",
keywords = "Hidden Vector Encryption, Leakage Profile, Searchable Encryption",
author = "Shangqi Lai and Sikhar Patranabis and Amin Sakzad and Liu, {Joseph K.} and Debdeep Mukhopadhyay and Ron Steinfeld and Shi-Feng Sun and Dongxi Liu and Cong Zuo",
year = "2018",
doi = "10.1145/3243734.3243753",
language = "English",
pages = "745--762",
editor = "Michael Backes and Wang, {XiaoFeng }",
booktitle = "CCS’18 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security",
publisher = "Association for Computing Machinery (ACM)",
address = "United States of America",

}

Lai, S, Patranabis, S, Sakzad, A, Liu, JK, Mukhopadhyay, D, Steinfeld, R, Sun, S-F, Liu, D & Zuo, C 2018, Result pattern hiding searchable encryption for conjunctive queries. in M Backes & X Wang (eds), CCS’18 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security: October 15-19, 2018 Toronto, ON, Canada. Association for Computing Machinery (ACM), New York NY USA, pp. 745-762, ACM Conference on Computer and Communications Security 2018, Toronto, Canada, 15/10/18. https://doi.org/10.1145/3243734.3243753

Result pattern hiding searchable encryption for conjunctive queries. / Lai, Shangqi; Patranabis, Sikhar; Sakzad, Amin; Liu, Joseph K.; Mukhopadhyay, Debdeep; Steinfeld, Ron; Sun, Shi-Feng; Liu, Dongxi; Zuo, Cong.

CCS’18 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security: October 15-19, 2018 Toronto, ON, Canada. ed. / Michael Backes; XiaoFeng Wang. New York NY USA : Association for Computing Machinery (ACM), 2018. p. 745-762.

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

TY - GEN

T1 - Result pattern hiding searchable encryption for conjunctive queries

AU - Lai, Shangqi

AU - Patranabis, Sikhar

AU - Sakzad, Amin

AU - Liu, Joseph K.

AU - Mukhopadhyay, Debdeep

AU - Steinfeld, Ron

AU - Sun, Shi-Feng

AU - Liu, Dongxi

AU - Zuo, Cong

PY - 2018

Y1 - 2018

N2 - The recently proposed Oblivious Cross-Tags (OXT) protocol (CRYPTO 2013) has broken new ground in designing efficient searchable symmetric encryption (SSE) protocol with support for conjunctive keyword search in a single-writer single-reader framework. While the OXT protocol offers high performance by adopting a number of specialised data-structures, it also trades-off security by leaking ‘partial’ database information to the server. Recent attacks have exploited similar partial information leakage to breach database confidentiality. Consequently, it is an open problem to design SSE protocols that plug such leakages while retaining similar efficiency. In this paper, we propose a new SSE protocol, called Hidden Cross-Tags (HXT), that removes ‘Keyword Pair Result Pattern’ (KPRP) leakage for conjunctive keyword search. We avoid this leakage by adopting two additional cryptographic primitives - Hidden Vector Encryption (HVE) and probabilistic (Bloom filter) indexing into the HXT protocol. We propose a ‘lightweight’ HVE scheme that only uses efficient symmetric-key building blocks, and entirely avoids elliptic curve-based operations. At the same time, it affords selective simulation-security against an unbounded number of secret-key queries. Adopting this efficient HVE scheme, the overall practical storage and computational overheads of HXT over OXT are relatively small (no more than 10% for two keywords query, and 21% for six keywords query), while providing a higher level of security.

AB - The recently proposed Oblivious Cross-Tags (OXT) protocol (CRYPTO 2013) has broken new ground in designing efficient searchable symmetric encryption (SSE) protocol with support for conjunctive keyword search in a single-writer single-reader framework. While the OXT protocol offers high performance by adopting a number of specialised data-structures, it also trades-off security by leaking ‘partial’ database information to the server. Recent attacks have exploited similar partial information leakage to breach database confidentiality. Consequently, it is an open problem to design SSE protocols that plug such leakages while retaining similar efficiency. In this paper, we propose a new SSE protocol, called Hidden Cross-Tags (HXT), that removes ‘Keyword Pair Result Pattern’ (KPRP) leakage for conjunctive keyword search. We avoid this leakage by adopting two additional cryptographic primitives - Hidden Vector Encryption (HVE) and probabilistic (Bloom filter) indexing into the HXT protocol. We propose a ‘lightweight’ HVE scheme that only uses efficient symmetric-key building blocks, and entirely avoids elliptic curve-based operations. At the same time, it affords selective simulation-security against an unbounded number of secret-key queries. Adopting this efficient HVE scheme, the overall practical storage and computational overheads of HXT over OXT are relatively small (no more than 10% for two keywords query, and 21% for six keywords query), while providing a higher level of security.

KW - Hidden Vector Encryption

KW - Leakage Profile

KW - Searchable Encryption

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

U2 - 10.1145/3243734.3243753

DO - 10.1145/3243734.3243753

M3 - Conference Paper

SP - 745

EP - 762

BT - CCS’18 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security

A2 - Backes, Michael

A2 - Wang, XiaoFeng

PB - Association for Computing Machinery (ACM)

CY - New York NY USA

ER -

Lai S, Patranabis S, Sakzad A, Liu JK, Mukhopadhyay D, Steinfeld R et al. Result pattern hiding searchable encryption for conjunctive queries. In Backes M, Wang X, editors, CCS’18 - Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security: October 15-19, 2018 Toronto, ON, Canada. New York NY USA: Association for Computing Machinery (ACM). 2018. p. 745-762 https://doi.org/10.1145/3243734.3243753