Private Database Search with Sublinear Query Time

Abstract : The problem of private database search has been well studied. The notion of privacy considered is twofold: i) the querier only learns the result of the query (and things that can be deduced from it), and ii) the server learns nothing (in a computational sense) about the query. A fundamental drawback with prior approaches is that the query computation is linear in the dataset. We overcome this drawback by making the following assumption: the server has its dataset ahead of time and is able to perform linear precomputation for each query. This new model, which we call the precomputation model, is appropriate in circumstances where it is crucial that queries are answered efficiently once they become available. Our main contribution is a precomputed search protocol that requires linear precomputation time but that allows logarithmic search time. Using this protocol, we then show how to answer the following types of queries with sublinear query computation in this precomputation model: i) point existence queries, ii) rank queries, iii) lookup queries, and iv) one-dimensional range queries.
Type de document :
Communication dans un congrès
Yingjiu Li. 23th Data and Applications Security (DBSec), Jul 2011, Richmond, VA, United States. Springer, Lecture Notes in Computer Science, LNCS-6818, pp.154-169, 2011, Data and Applications Security and Privacy XXV. 〈10.1007/978-3-642-22348-8_13〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01586594
Contributeur : Hal Ifip <>
Soumis le : mercredi 13 septembre 2017 - 08:56:13
Dernière modification le : mercredi 13 septembre 2017 - 14:28:18
Document(s) archivé(s) le : jeudi 14 décembre 2017 - 12:40:39

Fichier

978-3-642-22348-8_13_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Keith Frikken, Boyang Li. Private Database Search with Sublinear Query Time. Yingjiu Li. 23th Data and Applications Security (DBSec), Jul 2011, Richmond, VA, United States. Springer, Lecture Notes in Computer Science, LNCS-6818, pp.154-169, 2011, Data and Applications Security and Privacy XXV. 〈10.1007/978-3-642-22348-8_13〉. 〈hal-01586594〉

Partager

Métriques

Consultations de la notice

16

Téléchargements de fichiers

6