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
[ Cryptology ePrint archive ]