[Resource Topic] 2022/071: Encapsulated Search Index: Public-Key, Sub-linear, Distributed, and Delegatable

Welcome to the resource topic for 2022/071

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

Authors: Erik Aronesty, David Cash, Yevgeniy Dodis, Daniel H. Gallancy, Christopher Higley, Harish Karthikeyan, 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.

ePrint: https://eprint.iacr.org/2022/071

Talk: https://www.youtube.com/watch?v=mILzFFpZIMo

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .