Forward-Secure Searchable Encryption on Labeled Bipartite Graphs

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

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Major revision. ACNS 2017
DOI: 10.1007/978-3-319-61204-1_24
Contact author(s): russell @ ie cuhk edu hk
History: 2017-07-07: revised; 2017-07-05: received; See all versions
Short URL: https://ia.cr/2017/659
License: CC BY

BibTeX

@misc{cryptoeprint:2017/659,
      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{https://eprint.iacr.org/2017/659}},
      url = {https://eprint.iacr.org/2017/659}
}