International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Erik Aronesty , Atakama
David Cash , University of Chicago
Yevgeniy Dodis , New York University
Daniel H. Gallancy , Atakama
Christopher Higley , Atakama
Harish Karthikeyan , New York University
Oren Tysor , Atakama
Search ePrint
Search Google
Conference: PKC 2022
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 a real-world company.
Video from PKC 2022
  title={Encapsulated Search Index : Public-Key, Sub-linear, Distributed, and Delegatable},
  author={Erik Aronesty and David Cash and Yevgeniy Dodis and Daniel H. Gallancy and Christopher Higley and Harish Karthikeyan and Oren Tysor},