Access Pattern Hidden Query over Encrypted Data through Multi-Clouds

Searchable encryption seeks to support untrusted third parties to conduct direct searching over encrypted data. However, recent research has found that searchable encryption is vulnerable to attacks, which exploit the statistical relationship or pattern identified from encrypted query results. In this paper, we study the problem of access pattern leakage attack on searchable encryption under a multi-cloud environment. Basically, both database records and queries are distributed among different cloud servers, so that each cloud server can only have partial information about queries and their results. To minimize the query response time while protecting information disclosure, we formulate the record and query assignment as an optimization problem, and solve the problem (i.e., finding the best possible solution) by the minimum s-t cut algorithm. Numerical results show that on average 13% access pattern information can be saved by our assignment strategy while maintaining good query response time.