Practical Private Information Retrieval from a Time-Varying, Multi-attribute, and Multiple-Occurrence Database

Abstract : We study the problem of privately performing database queries (i.e., keyword searches and conjunctions over them), where a server provides its own database for client query-based access. 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 incorporate a more practical data model: a time-varying, multi-attribute and multiple-occurrence database table.Our first result is a 2-party private database retrieval protocol. Like all previous work in private information retrieval and keyword search, this protocol still satisfies server time complexity linear in the database size.Our main result is a private database retrieval protocol in a 3-party model where encrypted data is outsourced to a third party (i.e., a cloud server), satisfying highly desirable privacy and efficiency properties; most notably: (1) no unintended information is leaked to clients or servers, and only minimal ‘access pattern’ information is leaked to the third party; (2) for each query, all parties run in time only logarithmic in the number of database records; (3) the protocol’s runtime is practical for real-life applications, as shown in our implementation where we achieve response time that is only a small constant slower than commercial non-private protocols like MySQL.
Type de document :
Communication dans un congrès
David Hutchison; Takeo Kanade; Bernhard Steffen; Demetri Terzopoulos; Doug Tygar; Gerhard Weikum; Vijay Atluri; Günther Pernul; Josef Kittler; Jon M. Kleinberg; Alfred Kobsa; Friedemann Mattern; John C. Mitchell; Moni Naor; Oscar Nierstrasz; C. Pandu Rangan. 28th IFIP Annual Conference on Data and Applications Security and Privacy (DBSec), Jul 2014, Vienna, Austria. Springer, Lecture Notes in Computer Science, LNCS-8566, pp.339-355, 2014, Data and Applications Security and Privacy XXVIII. 〈10.1007/978-3-662-43936-4_22〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01284868
Contributeur : Hal Ifip <>
Soumis le : mardi 8 mars 2016 - 11:11:04
Dernière modification le : lundi 9 mai 2016 - 17:58:30
Document(s) archivé(s) le : dimanche 13 novembre 2016 - 09:56:20

Fichier

978-3-662-43936-4_22_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Giovanni Crescenzo, Debra Cook, Allen Mcintosh, Euthimios Panagos. Practical Private Information Retrieval from a Time-Varying, Multi-attribute, and Multiple-Occurrence Database. David Hutchison; Takeo Kanade; Bernhard Steffen; Demetri Terzopoulos; Doug Tygar; Gerhard Weikum; Vijay Atluri; Günther Pernul; Josef Kittler; Jon M. Kleinberg; Alfred Kobsa; Friedemann Mattern; John C. Mitchell; Moni Naor; Oscar Nierstrasz; C. Pandu Rangan. 28th IFIP Annual Conference on Data and Applications Security and Privacy (DBSec), Jul 2014, Vienna, Austria. Springer, Lecture Notes in Computer Science, LNCS-8566, pp.339-355, 2014, Data and Applications Security and Privacy XXVIII. 〈10.1007/978-3-662-43936-4_22〉. 〈hal-01284868〉

Partager

Métriques

Consultations de la notice

45

Téléchargements de fichiers

20