Cryptology ePrint Archive: Report 2017/659

Forward-Secure Searchable Encryption on Labeled Bipartite Graphs

Russell W. F. Lai and Sherman S. M. Chow

Abstract: Forward privacy is a trending security notion of dynamic searchable symmetric encryption (DSSE). It guarantees the privacy of newly added data against the server who has knowledge of previous queries. The notion was very recently formalized by Bost (CCS '16) independently, yet the definition given is imprecise to capture how forward secure a scheme is. We further the study of forward privacy by proposing a generalized definition parametrized by a set of updates and restrictions on them. We then construct two forward private DSSE schemes over labeled bipartite graphs, as a generalization of those supporting keyword search over text files. The first is a generic construction from any DSSE, and the other is a concrete construction from scratch. For the latter, we designed a novel data structure called cascaded triangles, in which traversals can be performed in parallel while updates only affect the local regions around the updated nodes. Besides neighbor queries, our schemes support flexible edge additions and intelligent node deletions: The server can delete all edges connected to a given node, without having the client specify all the edges.

Category / Keywords: cryptographic protocols /

Original Publication (with major differences): ACNS 2017

Date: received 4 Jul 2017, last revised 7 Jul 2017

Contact author: russell at ie cuhk edu hk

Available format(s): PDF | BibTeX Citation

Version: 20170707:075511 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]