Forward and Backward Secure Searchable Encryption Scheme Supporting Conjunctive Queries Over Bipartite Graphs

Dynamic searchable encryption, which allows clients to outsource their encrypted data to cloud servers and retain the ability to query and update data, has received wide attention. In the setting, it is essential to ensure that a server infers as little as possible about the content of the outsourced data and the queries it processes. In this article, we propose a forward and backward secure searchable encryption scheme on bipartite graphs (FBSSE-BG) that offers the strongest level of backward security. In particular, we introduce the notion of update counter to construct a new bi-directional index structure, which realizes conjunctive queries over bipartite graphs and supports flexible updates of outsourced data. Besides, to minimize the information revealed to servers, we propose a new oblivious data structure to store the bi-directional index and use a semantically-secure encryption scheme to encrypt node information, such that servers can only observe a series of ORAM locations and encrypted paths. Finally, we prove the security of FBSSE-BG by using the real-world versus ideal-world formalization and provide experimental efficiency evaluations for its implementations.