%0 Conference Proceedings
%T Privacy-Preserving Range Queries from Keyword Queries
%+ Applied Communication Sciences [Basking Ridge, NJ] (ACS)
%A Crescenzo, Giovanni, Di
%A Ghosh, Abhrajit
%Z Part 1: Data Anonymization and Computation
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 29th IFIP Annual Conference on Data and Applications Security and Privacy (DBSEC)
%C Fairfax, VA, United States
%Y Pierangela Samarati
%I Springer International Publishing
%3 Data and Applications Security and Privacy XXIX
%V LNCS-9149
%P 35-50
%8 2015-07-13
%D 2015
%R 10.1007/978-3-319-20810-7_3
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 11
%Z WG 11.3
%2 https://inria.hal.science/hal-01745815/document
%2 https://inria.hal.science/hal-01745815/file/340025_1_En_3_Chapter.pdf
%L hal-01745815
%U https://inria.hal.science/hal-01745815
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-WG
%~ IFIP-TC11
%~ IFIP-WG11-3
%~ IFIP-DBSEC
%~ IFIP-LNCS-9149