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
Creative Commons Attribution
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},
      url = {https://eprint.iacr.org/2017/659}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.