1. Practical Backward-Secure Searchable Encryption from Symmetric Puncturable Encryption 2018 CCS SearchableEncryption SymmetricKey
    Shi-Feng Sun, Xingliang Yuan, Joseph K. Liu, Ron Steinfeld, Amin Sakzad, Viet Vo, and Surya Nepal
    [View PDF on dl.acm.org]
    [Show BibTex Citation]

    author = {Sun, Shi-Feng and Yuan, Xingliang and Liu, Joseph K. and Steinfeld, Ron and Sakzad, Amin and Vo, Viet and Nepal, Surya},
    title = {Practical Backward-Secure Searchable Encryption from Symmetric Puncturable Encryption},
    booktitle = {Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security},
    series = {CCS '18},
    year = {2018},
    isbn = {978-1-4503-5693-0},
    location = {Toronto, Canada},
    pages = {763--780},
    numpages = {18},
    url = {http://doi.acm.org/10.1145/3243734.3243782},
    doi = {10.1145/3243734.3243782},
    acmid = {3243782},
    publisher = {ACM},
    address = {New York, NY, USA},
    keywords = {backward security, puncturable encryption, symmetric searchable encryption},

Symmetric Searchable Encryption (SSE) has received wide attention due to its practical application in searching on encrypted data. Beyond search, data addition and deletion are also supported in dynamic SSE schemes. Unfortunately, these update operations leak some information of updated data. To address this issue, forward-secure SSE is actively explored to protect the relations of newly updated data and previously searched keywords. On the contrary, little work has been done in backward security, which enforces that search should not reveal information of deleted data. In this paper, we propose the first practical and non-interactive backward-secure SSE scheme. In particular, we introduce a new form of symmetric encryption, named symmetric puncturable encryption (SPE), and construct a generic primitive from simple cryptographic tools. Based on this primitive, we then present a backward-secure SSE scheme that can revoke a server’s searching ability on deleted data. We instantiate our scheme with a practical puncturable pseudorandom function and implement it on a large dataset. The experimental results demonstrate its efficiency and scalability. Compared to the state-of-the-art, our scheme achieves a speedup of almost 50x in search latency, and a saving of 62% in server storage consumption.