Optimal Re-encryption Strategy for Joins in Encrypted Databases

详细信息    查看全文

• 作者：Florian Kerschbaum (18)
  Martin H?rterich (18)
  Patrick Grofig (18)
  Mathias Kohler (18)
  Andreas Schaad (18)
  Axel Schr?pfer (18)
  Walter Tighzert (18)
  
• 关键词：Encrypted Database ; Proxy Re ; encryption ; Adjustable Join
• 刊名：Lecture Notes in Computer Science
• 出版年：2013
• 出版时间：2013
• 年：2013
• 卷：7964
• 期：1
• 页码：211-225
• 全文大小：251KB
• 参考文献：1. Bellare, M., Boldyreva, A., O’Neill, A.: Deterministic and efficiently searchable encryption. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol.?4622, pp. 535-52. Springer, Heidelberg (2007) CrossRef
  2. Binnig, C., Hildenbrand, S., F?rber, F.: Dictionary-based order-preserving string compression for main memory column stores. In: Proceedings of the ACM International Conference on Management of Data (SIGMOD) (2009)
  3. Blaze, M., Bleumer, G., Strauss, M.J.: Divertible protocols and atomic proxy cryptography. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol.?1403, pp. 127-44. Springer, Heidelberg (1998) CrossRef
  4. Boldyreva, A., Chenette, N., Lee, Y., O’Neill, A.: Order-preserving symmetric encryption. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol.?5479, pp. 224-41. Springer, Heidelberg (2009) CrossRef
  5. James, G.: The representation theory of the symmetric groups. LNM 682. Springer (1978)
  6. Galler, B., Fischer, M.: An improved equivalence algorithm. Communications of the ACM?7(5) (1964)
  7. Hacigümüs, H., Iyer, B., Li, C., Mehrotra, S.: Executing SQL over encrypted data in the database-service-provider model. In: Proceedings of the ACM International Conference on Management of Data (SIGMOD) (2002)
  8. Pohlig, S., Hellman, M.: An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Transactions on Information Theory?24 (1978)
  9. Popa, R., Redfield, C., Zeldovich, N., Balakrishnan, H.: CryptDB: Protecting confidentiality with encrypted query processing. In: Proceedings of the 23rd ACM Symposium on Operating Systems Principles (SOSP) (2011)
  10. Popa, R., Zeldovich, N.: Cryptographic treatment of CryptDB’s adjustable join. Technical Report MIT-CSAIL-TR-2012-006 (2012)
  
• 作者单位：Florian Kerschbaum (18)
  Martin H?rterich (18)
  Patrick Grofig (18)
  Mathias Kohler (18)
  Andreas Schaad (18)
  Axel Schr?pfer (18)
  Walter Tighzert (18)
  
  18. SAP Applied Research, Vincenz-Priessnitz-Str. 1, Karlsruhe, Germany
  

文摘

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 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.