Paper 2017/659

Forward-Secure Searchable Encryption on Labeled Bipartite Graphs

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


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.ACNS 2017
Contact author(s)
russell @ ie cuhk edu hk
2017-07-07: revised
2017-07-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Russell W.  F.  Lai and Sherman S.  M.  Chow},
      title = {Forward-Secure Searchable Encryption on Labeled Bipartite Graphs},
      howpublished = {Cryptology ePrint Archive, Paper 2017/659},
      year = {2017},
      doi = {10.1007/978-3-319-61204-1_24},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.