Advertisement
Published in:
2013 | OriginalPaper | Chapter
Optimal Re-encryption Strategy for Joins in Encrypted Databases
Authors : Florian Kerschbaum, Martin Härterich, Patrick Grofig, Mathias Kohler, Andreas Schaad, Axel Schröpfer, Walter Tighzert
Published in: Data and Applications Security and Privacy XXVII
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
(
n
3/2
) resp.
O
(
n
log
n
) re-encryptions for
n
columns. We show that there can be no algorithm better than
O
(
n
log
n
). 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.