Efficient Boolean SSE: A Novel Encrypted Database (EDB)

Searchable symmetric encryption (SSE) with increasing expressiveness was proposed to acquire optimal communication complexity, but it has poor efficiency compared to the single-word query. Many of the existing expressive SSE mechanisms use the inverted index to build the encrypted database (EDB) for the sub-linear search complexity. However, this inevitably brings about the problems of repeated storage and low efficiency of set operations. To this end, we introduced a new approach, using the boolean vectors (BV) instead of the inverted indexes to build EDB, which dramatically improves the search efficiency and reduces the storage space. While boolean operation must run on the closed space, we divided the full queried space into several disjoint closed sub-spaces and proved its correctness theoretically. Our construction supports arbitrary conjunctive, disjunctive, and boolean queries. The experiments prove that our system is more efficient in storage and search complexity than existing methods.