Privacy-Preserving Range Queries from Keyword Queries - Archive ouverte HAL Access content directly
Conference Papers Year : 2015

Privacy-Preserving Range Queries from Keyword Queries

(1) , (1)
1

Abstract

We consider the problem of a client performing privacy-preserving range queries to a server’s database. We propose a cryptographic model for the study of such protocols, by expanding previous well-studied models of keyword search and private information retrieval to the range query type and to incorporate a multiple-occurrence attribute column in the database table.Our first two results are 2-party privacy-preserving range query protocols, where either (a) the value domain is linear in the number of database records and the database size is only increased by a small constant factor; or (b) the value domain is exponential (thus, essentially of arbitrarily large size) in the number of database records and the database size is increased by a factor logarithmic in the value domain size. Like all previous work in private information retrieval and keyword search, this protocol still satisfies server time complexity linear in the number of database payloads.We discuss how to adapt these results to a 3-party model where encrypted data is outsourced to a third party (i.e., a cloud server). The result is a private database retrieval protocol satisfying a highly desirable tradeoff of privacy and efficiency properties; most notably: (1) no unintended information is leaked to clients or servers, and the information leaked to the third party is characterized as ‘access pattern’ on encrypted data; (2) for each query, all parties run in time only logarithmic in the number of database records and linear in the answer size; (3) the protocol’s query runtime is practical for real-life applications.
Fichier principal
Vignette du fichier
340025_1_En_3_Chapter.pdf (650.71 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01745815 , version 1 (28-03-2018)

Licence

Attribution - CC BY 4.0

Identifiers

Cite

Giovanni Di Crescenzo, Abhrajit Ghosh. Privacy-Preserving Range Queries from Keyword Queries. 29th IFIP Annual Conference on Data and Applications Security and Privacy (DBSEC), Jul 2015, Fairfax, VA, United States. pp.35-50, ⟨10.1007/978-3-319-20810-7_3⟩. ⟨hal-01745815⟩
59 View
122 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More