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

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 $$, beyond the keyword $$. − yet, the token $$ is specific to the pair $$: the client does not learn if other keywords $$ belong to $$, or if w belongs to other, freshly indexed documents $$. − server cannot fool the client by giving a wrong token $$. We call such a primitive Encapsulated Search Index (ESI). Our ESI scheme can be made $$- distributed among $$ servers in the best possible way: non-interactive, verifiable, and resilient to any coalition of up to $$ 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.