Paper 2018/052

Optimizing Trees for Static Searchable Encryption

Mohammad Etemad, Mohammad Mahmoody, and David Evans


Searchable symmetric encryption (SSE) enables data owners to conduct searches over encrypted data stored by an untrusted server, retrieving only those encrypted files that match the search queries. Several recent schemes employ a server-side encrypted index in the form of a search tree where each node stores a bit vector denoting for each keyword whether any file in its subtree contains that keyword. Our work is motivated by the observation that the way data is distributed in such a search tree has a big impact on the cost of searches. For single-keyword queries, it impacts the number of different paths that must be followed to find all the matching files; for multi-keyword queries, the arrangement of the tree also impacts the number of nodes visited during the search on paths that do not lead to any satisfying data elements. We present three algorithms that improve the performance of SSE schemes based on tree indexes and prove that for cases where the search cost is high, the cost of our algorithms converges to the cost of the optimal tree. In our experiments, the resulting search trees outperform the arbitrary search trees used in previous works by a factor of up to two

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
etemad @ virginia edu
2018-01-15: received
Short URL
Creative Commons Attribution


      author = {Mohammad Etemad and Mohammad Mahmoody and David Evans},
      title = {Optimizing Trees for Static Searchable Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2018/052},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.