Zhiwei
Shang,
Master’s
candidate
David
R.
Cheriton
School
of
Computer
Science
Searchable symmetric encryption scheme allows data owner to outsource its data to a cloud server while maintaining the ability to search over it. Most existing SSE schemes allow access-pattern leakage, which are vulnerable to query recovery attacks like IKK attack. Oblivious RAM and PIR can be used to construct SSE schemes fully hiding access patterns. However, such schemes are suffering heavy communication overhead or computation overhead making them impractical. Chen et al. proposed an obfuscation mechanism to protect existing SSE schemes against access-pattern leakage. This mechanism can produce differentially private access patterns per keyword. However, it cannot hide whether the same keyword has been searched for multiple times, i.e. the search patterns.
In this paper, we proposed a stronger security definition for differentially private searchable symmetric encryption scheme and presented a real construction DPSSE fulfilling it. On the one hand, DPSSE is adaptively semantically secure and provides differential privacy for both keywords and documents. On the other hand, DPSSE has communication complexity as small as O(|D(w)| × log log n) and computation complexity of O(n × log log n) while querying relatively frequent keyword w. When assuming queries follow Zipfian distribution, the amortized communication complexity would be O(|D(w)| × log n log log n). By replicating IKK attack, we showed that DPSSE could actually hide access patterns and make it difficult to extract useful information from differentially private access-pattern leakage. By performing KMeans clustering algorithm, we were able to show that inferring search patterns from differentially private access-pattern leakage is difficult, namely search patterns are hidden.