Optimal Re-encryption Strategy for Joins in Encrypted Databases

Abstract : In order to perform a join in a deterministically, adjustably encrypted database one has to re-encrypt at least one column. The problem is to select that column that will result in the minimum number of re-encryptions even under an unknown schedule of joins. Naive strategies may perform too many or even infinitely many re-encryptions. We provide two strategies that allow for a much better performance. In particular the asymptotic behavior is O(n3/2) resp. O(n logn) re-encryptions for n columns. We show that there can be no algorithm better than O(n logn). We further extend our result to element-wise re-encryptions and show experimentally that our algorithm results in the optimal cost in 41% of the cases.
Type de document :
Communication dans un congrès
Lingyu Wang; Basit Shafiq. 27th Data and Applications Security and Privacy (DBSec), Jul 2013, Newark, NJ, United States. Springer, Lecture Notes in Computer Science, LNCS-7964, pp.195-210, 2013, Data and Applications Security and Privacy XXVII. 〈10.1007/978-3-642-39256-6_13〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01490705
Contributeur : Hal Ifip <>
Soumis le : mercredi 15 mars 2017 - 17:15:39
Dernière modification le : jeudi 16 mars 2017 - 09:24:25
Document(s) archivé(s) le : vendredi 16 juin 2017 - 15:05:15

Fichier

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

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Florian Kerschbaum, Martin Härterich, Patrick Grofig, Mathias Kohler, Andreas Schaad, et al.. Optimal Re-encryption Strategy for Joins in Encrypted Databases. Lingyu Wang; Basit Shafiq. 27th Data and Applications Security and Privacy (DBSec), Jul 2013, Newark, NJ, United States. Springer, Lecture Notes in Computer Science, LNCS-7964, pp.195-210, 2013, Data and Applications Security and Privacy XXVII. 〈10.1007/978-3-642-39256-6_13〉. 〈hal-01490705〉

Partager

Métriques

Consultations de la notice

39

Téléchargements de fichiers

17