In this paper, we study Symmetric Searchable Encryption (SSE) in a multi-user setting in which each user dynamically shares its documents with selected other users, allowing sharees also to perform searches. We introduce the concept of a Symmetric Searchable Encryption with Sharing and Unsharing, an extension of Multi-Key Searchable Encryption (NSDI ’14), that supports dynamic sharing and unsharing of documents amongst users. We also strengthen the security notion by considering a simulation-based notion that does not restrict sharing between honest and compromised users. We present the notion of cross-user leakage, the information leaked about a user’s documents and/or queries from the queries of other users, and introduce a novel technique to quantify cross-user leakage. Specifically, we model cross-user leakage by using a graph where nodes correspond to users and the presence of edges between two nodes indicates the existence of cross-user leakage between the two adjacent users. The statistics on the connected components of the cross-user leakage graph provide a quantifiable way to compare the leakage of multi-user schemes which has eluded previous works. Our main technical contribution is mx-u, an efficient scheme with small cross-user leakage, whose security is based on the decisional Diffie-Hellman assumption. We prove a tight bound on the leakage of mx-u in the presence of an honest-but-curious adversary that colludes with a non-adaptively chosen subset of users. We report on experiments showing that mx-u is efficient and that cross-user leakage grows slowly as queries are performed.

Symmetric searchable encryption with sharing and unsharing

Persiano G.
;
2018-01-01

Abstract

In this paper, we study Symmetric Searchable Encryption (SSE) in a multi-user setting in which each user dynamically shares its documents with selected other users, allowing sharees also to perform searches. We introduce the concept of a Symmetric Searchable Encryption with Sharing and Unsharing, an extension of Multi-Key Searchable Encryption (NSDI ’14), that supports dynamic sharing and unsharing of documents amongst users. We also strengthen the security notion by considering a simulation-based notion that does not restrict sharing between honest and compromised users. We present the notion of cross-user leakage, the information leaked about a user’s documents and/or queries from the queries of other users, and introduce a novel technique to quantify cross-user leakage. Specifically, we model cross-user leakage by using a graph where nodes correspond to users and the presence of edges between two nodes indicates the existence of cross-user leakage between the two adjacent users. The statistics on the connected components of the cross-user leakage graph provide a quantifiable way to compare the leakage of multi-user schemes which has eluded previous works. Our main technical contribution is mx-u, an efficient scheme with small cross-user leakage, whose security is based on the decisional Diffie-Hellman assumption. We prove a tight bound on the leakage of mx-u in the presence of an honest-but-curious adversary that colludes with a non-adaptively chosen subset of users. We report on experiments showing that mx-u is efficient and that cross-user leakage grows slowly as queries are performed.
2018
978-3-319-98988-4
978-3-319-98989-1
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4740577
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 14
  • ???jsp.display-item.citation.isi??? 11
social impact