Paper 2014/362

Nothing is for Free: Security in Searching Shared & Encrypted Data

Qiang Tang


Most existing symmetric searchable encryption schemes aim at allowing a user to outsource her encrypted data to a cloud server and delegate the latter to search on her behalf. These schemes do not qualify as a secure and scalable solution for the multi-party setting, where users outsource their encrypted data to a cloud server and selectively authorize each other to search. Due to the possibility that the cloud server may collude with some malicious users, it is a challenge to have a secure and scalable multi-party searchable encryption (MPSE) scheme. This is shown by our analysis on the Popa-Zeldovich scheme, which says that an honest user may leak all her search patterns even if she shares only one of her documents with another malicious user. Based on our analysis, we present a new security model for MPSE by considering the worst-case and average-case scenarios, which capture different server-user collusion possibilities. We then propose a MPSE scheme by employing the bilinear property of Type-3 pairings, and prove its security based on the Bilinear Diffie-Hellman Variant (BDHV) and Symmetric eXternal Diffie-Hellman (SXDH) assumptions in the random oracle model.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Multi-party Searchable Encryption (MPSE)Data PrivacyTrapdoor PrivacyPairing
Contact author(s)
qiang tang @ uni lu
2014-05-25: received
Short URL
Creative Commons Attribution


      author = {Qiang Tang},
      title = {Nothing is for Free: Security in Searching Shared & Encrypted Data},
      howpublished = {Cryptology ePrint Archive, Paper 2014/362},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.