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

Contributor : Hal Ifip <>
Submitted on : Wednesday, March 15, 2017 - 5:15:39 PM
Last modification on : Thursday, March 16, 2017 - 9:24:25 AM
Long-term archiving on : Friday, June 16, 2017 - 3:05:15 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Florian Kerschbaum, Martin Härterich, Patrick Grofig, Mathias Kohler, Andreas Schaad, et al.. Optimal Re-encryption Strategy for Joins in Encrypted Databases. 27th Data and Applications Security and Privacy (DBSec), Jul 2013, Newark, NJ, United States. pp.195-210, ⟨10.1007/978-3-642-39256-6_13⟩. ⟨hal-01490705⟩



Record views


Files downloads