Paper 2018/1168

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, and Cong Zuo


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.

Note: This is the full version of our ACM CCS paper "Result Pattern Hiding Searchable Encryption for Conjunctive Queries". It includes the detailed games we defined for security analysis and some supplementary evaluation results. If you want to cite our work, please cite the conference version of it.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.ACM CCS'18
Searchable EncryptionHidden Vector EncryptionLeakage Profile
Contact author(s)
shangqi lai @ monash edu
2018-12-03: received
Short URL
Creative Commons Attribution


      author = {Shangqi Lai and Sikhar Patranabis and Amin Sakzad and Joseph K.  Liu and Debdeep Mukhopadhyay and Ron Steinfeld and Shi-Feng Sun and Dongxi Liu and Cong Zuo},
      title = {Result Pattern Hiding Searchable Encryption for Conjunctive Queries},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1168},
      year = {2018},
      doi = {10.1145/3243734.3243753},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.