Cryptology ePrint Archive: Report 2022/071

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

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

Abstract: 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.

Category / Keywords: public-key cryptography / encapsulated search index, threshold, delegated searching

Original Publication (with major differences): IACR-PKC-2022

Date: received 18 Jan 2022

Contact author: harish at nyu edu

Available format(s): PDF | BibTeX Citation

Version: 20220120:155708 (All versions of this report)

Short URL: ia.cr/2022/071