Paper 2022/071

Encapsulated Search Index: Public-Key, Sub-linear, Distributed, and Delegatable

Erik Aronesty, David Cash, Yevgeniy Dodis, Daniel H. Gallancy, Christopher Higley, Harish Karthikeyan, and Oren Tysor


We build the first sub-linear (in fact, potentially constant-time) public-key searchable encryption system: − server can publish a public key $PK$. − anybody can build an encrypted index for document $D$ under $PK$. − client holding the index can obtain a token $z_w$ from the server to check if a keyword $w$ belongs to $D$. − search using $z_w$ is almost as fast (e.g., sub-linear) as the non-private search. − server granting the token does not learn anything about the document $D$, beyond the keyword $w$. − yet, the token $z_w$ is specific to the pair $(D, w)$: the client does not learn if other keywords $w'\neq w$ belong to $D$, or if w belongs to other, freshly indexed documents $D'$. − server cannot fool the client by giving a wrong token $z_w$. We call such a primitive Encapsulated Search Index (ESI). Our ESI scheme can be made $(t, n)$- distributed among $n$ servers in the best possible way: non-interactive, verifiable, and resilient to any coalition of up to $(t − 1)$ malicious servers. We also introduce the notion of delegatable ESI and show how to extend our construction to this setting. Our solution — including public indexing, sub-linear search, delegation, and distributed token generation — is deployed as a commercial application by Atakama.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2022
encapsulated search indexthresholddelegated searching
Contact author(s)
harish @ nyu edu
2022-01-20: received
Short URL
Creative Commons Attribution


      author = {Erik Aronesty and David Cash and Yevgeniy Dodis and Daniel H.  Gallancy and Christopher Higley and Harish Karthikeyan and Oren Tysor},
      title = {Encapsulated Search Index: Public-Key, Sub-linear, Distributed, and Delegatable},
      howpublished = {Cryptology ePrint Archive, Paper 2022/071},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.