TY - GEN
T1 - Encapsulated Search Index
T2 - 25th IACR International Conference on Practice and Theory of Public-Key Cryptography, PKC 2022
AU - Aronesty, Erik
AU - Cash, David
AU - Dodis, Yevgeniy
AU - Gallancy, Daniel H.
AU - Higley, Christopher
AU - Karthikeyan, Harish
AU - Tysor, Oren
N1 - Publisher Copyright:
© 2022, International Association for Cryptologic Research.
PY - 2022
Y1 - 2022
N2 - 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 zw from the server to check if a keyword w belongs to D.search using zw 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 zw is specific to the pair (D, w): the client does not learn if other keywords w′≠ w belong to D, or if w belongs to other, freshly indexed documents D′.server cannot fool the client by giving a wrong token zw. 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.
AB - 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 zw from the server to check if a keyword w belongs to D.search using zw 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 zw is specific to the pair (D, w): the client does not learn if other keywords w′≠ w belong to D, or if w belongs to other, freshly indexed documents D′.server cannot fool the client by giving a wrong token zw. 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.
UR - http://www.scopus.com/inward/record.url?scp=85126213513&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85126213513&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-97131-1_9
DO - 10.1007/978-3-030-97131-1_9
M3 - Conference contribution
AN - SCOPUS:85126213513
SN - 9783030971304
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 256
EP - 285
BT - Public-Key Cryptography - PKC 2022 - 25th IACR International Conference on Practice and Theory of Public-Key Cryptography, Proceedings
A2 - Hanaoka, Goichiro
A2 - Shikata, Junji
A2 - Watanabe, Yohei
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 8 March 2022 through 11 March 2022
ER -