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. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1007/978-3-642-39256-6_13 | DBSec |
Keywords | Field | DocType |
optimal re-encryption strategy,unknown schedule,n column,asymptotic behavior,encrypted databases,algorithm result,optimal cost,adjustably encrypted database,minimum number,n logn,better performance,naive strategy | Joins,Encryption,Optimal cost,Asymptotic analysis,Database,Mathematics,Proxy re-encryption | Conference |
Volume | ISSN | Citations |
7964 | 0302-9743 | 11 |
PageRank | References | Authors |
0.58 | 8 | 7 |
Name | Order | Citations | PageRank |
---|---|---|---|
Florian Kerschbaum | 1 | 1186 | 89.43 |
Martin Härterich | 2 | 27 | 2.70 |
Patrick Grofig | 3 | 22 | 1.90 |
Mathias Kohler | 4 | 46 | 4.32 |
Andreas Schaad | 5 | 50 | 5.10 |
Axel Schröpfer | 6 | 67 | 4.90 |
Walter Tighzert | 7 | 31 | 3.47 |