Dynamic searchable symmetric encryption with physical deletion and small leakage

Dynamic Searchable Symmetric Encryption (DSSE) allows a client not only to search over ciphertexts as the traditional searchable symmetric encryption does, but also to update these ciphertexts according to requirements, e.g., adding or deleting some ciphertexts. It has been recognized as a fundamental and promising method to build secure cloud storage. In this paper, we propose a new DSSE scheme to overcome the drawbacks of previous schemes. The biggest challenge is to realize the physical deletion of ciphertexts with small leakage. We employ both logical and physical deletions, and run physical deletion in due course to avoid extra information leakage. Our instantiation achieves noticeable improvements throughout all following aspects: search performance, storage cost, functionality, and information leakage when operating its functions. We also demonstrate its provable security under adaptive attacks and practical performance according to experimental results.