Paper 2021/948

How to Make a Secure Index for Searchable Symmetric Encryption, Revisited

Yohei Watanabe, Takeshi Nakai, Kazuma Ohara, Takuya Nojima, Yexuan Liu, Mitsugu Iwamoto, and Kazuo Ohta


Searchable symmetric encryption (SSE) enables clients to search encrypted data. Curtmola et al. (ACM CCS 2006) formalized a model and security notions of SSE and proposed two concrete constructions called SSE-1 and SSE-2. After the seminal work by Curtmola et al., SSE becomes an active area of encrypted search. In this paper, we focus on two unnoticed problems in the seminal paper by Curtmola et al. First, we show that SSE-2 does not appropriately implement Curtmola et al.'s construction idea for dummy addition. We refine SSE-2's (and its variants') dummy-adding procedure to keep the number of dummies sufficiently many but as small as possible. We then show how to extend it to the dynamic setting while keeping the dummy-adding procedure work well and implement our scheme to show its practical efficiency. Second, we point out that the SSE-1 can cause a search error when a searched keyword is not contained in any document file stored at a server and show how to fix it.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Searchable Symmetric Encryption
Contact author(s)
watanabe @ uec ac jp
t-nakai @ uec ac jp
2021-07-13: received
Short URL
Creative Commons Attribution


      author = {Yohei Watanabe and Takeshi Nakai and Kazuma Ohara and Takuya Nojima and Yexuan Liu and Mitsugu Iwamoto and Kazuo Ohta},
      title = {How to Make a Secure Index for Searchable Symmetric Encryption, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2021/948},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.