Privacy-Preserving Range Queries from Keyword Queries

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download
Contributor : Hal Ifip <>
Submitted on : Wednesday, March 28, 2018 - 3:57:17 PM
Last modification on : Wednesday, March 28, 2018 - 3:59:32 PM
Long-term archiving on : Thursday, September 13, 2018 - 11:59:13 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Giovanni 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⟩



Record views


Files downloads