The problem of efficiently searching into outsourced encrypted data, while providing strong privacy guarantees, is a challenging problem arising from the separation of data ownership and data management typical of cloud-based applications. Several cryptographic solutions allowing a client to look-up occurrences of a substring of choice in an outsourced document collection have been publicly presented. Nonetheless, practical application requirements in terms of privacy, security and efficiency actively push for new and improved solutions. We present a privacy-preserving substring search protocol exhibiting a sub-linear communication cost, with a limited computational effort on the server side. The proposed protocol provides search pattern and access pattern privacy, while its extension to a multi-user setting shows significant savings in terms of outsourced storage w.r.t. a baseline solution where the whole dataset is replicated. The performance figures of an optimized implementation of our protocol, searching into a remotely stored genomic dataset, validate the practicality of the approach exhibiting a data transfer of less than 200 kiB to execute a query over a document of 40 MiB, with execution times on client and server in the range of a few seconds and a few minutes, respectively.

Privacy Preserving Substring Search Protocol with Polylogarithmic Communication Cost

N. Mainardi;A. Barenghi;G. Pelosi
2019-01-01

Abstract

The problem of efficiently searching into outsourced encrypted data, while providing strong privacy guarantees, is a challenging problem arising from the separation of data ownership and data management typical of cloud-based applications. Several cryptographic solutions allowing a client to look-up occurrences of a substring of choice in an outsourced document collection have been publicly presented. Nonetheless, practical application requirements in terms of privacy, security and efficiency actively push for new and improved solutions. We present a privacy-preserving substring search protocol exhibiting a sub-linear communication cost, with a limited computational effort on the server side. The proposed protocol provides search pattern and access pattern privacy, while its extension to a multi-user setting shows significant savings in terms of outsourced storage w.r.t. a baseline solution where the whole dataset is replicated. The performance figures of an optimized implementation of our protocol, searching into a remotely stored genomic dataset, validate the practicality of the approach exhibiting a data transfer of less than 200 kiB to execute a query over a document of 40 MiB, with execution times on client and server in the range of a few seconds and a few minutes, respectively.
2019
Proceedings of the the 35th Annual Computer Security Applications Conference (ACSAC 2019), San Juan, Puerto Rico, USA. December 9-13, 2019. ACM 2019
978-1-4503-7628-0
Secure substring search, Cryptography, Homomorphic encryption, Privacy-preserving protocol
File in questo prodotto:
File Dimensione Formato  
main.pdf

Accesso riservato

Descrizione: main article
: Publisher’s version
Dimensione 1.26 MB
Formato Adobe PDF
1.26 MB Adobe PDF   Visualizza/Apri

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/11311/1121480
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 5
social impact