CryptoDB
Encapsulated Search Index : Public-Key, Sub-linear, Distributed, and Delegatable
| Authors: |
|
|---|---|
| Download: | |
| 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
BibTeX
@inproceedings{pkc-2022-31726,
title={Encapsulated Search Index : Public-Key, Sub-linear, Distributed, and Delegatable},
publisher={Springer-Verlag},
author={Erik Aronesty and David Cash and Yevgeniy Dodis and Daniel H. Gallancy and Christopher Higley and Harish Karthikeyan and Oren Tysor},
year=2022
}