Dynamic Searchable Symmetric Encryption For Range Queries

Cloud computing technology has been widely used in information systems and information service platforms of various institutions in recent years due to its high flexibility,high scalability,and high cost performance.It has gradually become the infrastructure of an information society.However,in the cloud computing environment,data is separated from the user's control,and it is facing more attacks than the traditional computing environment.The widespread application of cloud computing technology brings convenience to users while also bringing people concerns about data security and privacy on the cloud.Searchable Symmetric Encryption(SSE)technology enables users to outsource their encrypted databases to the server while maintaining the ability for users to search in ciphertext,providing a feasible solution for the use of data on the cloud under conditions that ensure confidentiality and privacy.Dynamic Searchable Symmetric Encryption(DSSE)enables clients to further update their encrypted databases.DSSE with forward/backward privacy received numerous attention lately as they can withstand the powerful file-injection attack.DSSE with forward and backward privacy enhances the security of traditional DSSE schemes,in that the forward privacy disables the server to link an update operation with previous queries,and the backward privacy conceals the information about the entries that have been deleted from the database.For the first time,Bost et al.(CCS 17)formally proposed the concept of three backward privacy from weak to strong in dynamic searchable encryption,namely,type ? to type ?.Until now,only ORAM-based schemes can achieve type ? backward privacy,but ORAM-based solutions are still difficult to use because of efficiency issues.DSSE schemes with range queries that satisfy forward and backward security are very recently proposed,but due to the impact of additional information leakage caused by range queries on the security of the scheme,there are some substances in constructing schemes that meet these properties.The performance of the existing scheme is unsatisfactory.This article focuses on solutions that are not based on ORAM.We first discuss how to support range queries based on the binary tree structure,the information leakage and the impact of this structure.Then,based on the binary tree structure,we propose two dynamic searchable encryption schemes that support range queries.Both of them have forward and backward privacy,and are proved to be safe in the Random Oracle model.As far as we know,our second scheme is the first dynamic searchable encryption scheme reaching one-round type ?backward privacy and the asymptotic communication complexity of search operation is also the best of existing type ? backward privacy dynamic searchable encryption schemes.Besides,they require less storage on the client side than the existing schemes.We implemented our schemes and measured its performance.The experiment results show that our scheme is efficient and practical.