Practices of backuping homomorphically encrypted databases

Abstract

Ideal homomorphic encryption is theoretically achievable but impractical in reality due to tremendous computing overhead. Homomorphically encrypted databases, such as CryptDB, leverage replication with partially homomorphic encryption schemes to support different SQL queries over encrypted data directly. These databases reach a balance between security and efficiency, but incur considerable storage overhead, especially when making backups. Unfortunately, general data compression techniques relying on data similarity exhibit inefficiency on encrypted data. We present CryptZip, a backup and recovery system that could highly reduce the backup storage cost of encrypted databases. The key idea is to leverage the metadata information of encryption schemes and selectively backup one or several columns among semantically redundant columns. The experimental results show that CryptZip could reduce up to 90.5% backup storage cost on TPC-C benchmark.

Keywords

homomorphic encryption / security / deduplication

References

[1] Popa R A, Redfield C, Zeldovich N, Balakrishnan H. Cryptdb: protecting confidentiality with encrypted query processing. In: Proceedings of the 23rd ACM Symposium on Operating Systems Principles. 2011, 85–100

[2] Ferretti L, Colajanni M, Marchetti M. Supporting security and consistency for cloud database. In: Proceedings of the 4th International Conference on Cyberspace Safety and Security. 2012, 179–193

[3] Ferretti L, Colajanni M, Marchetti M. Distributed, concurrent, and independent access to encrypted cloud databases. IEEE Transactions on Parallel and Distributed Systems. 2014, 25(2): 437–446

[4] Kerschbaum K, Härterich M, Grofig P, Kohler M, Schaad A, Schröpfer A, Tighzert W. Optimal re-encryption strategy for joins in encrypted databases. In: Proceedings of IFIP Annual Conference on Data and Applications Security and Privacy. 2013, 195–210

[5] Tu S, Kaashoek M F, Madden S, Zeldovich N. Processing analytical queries over encrypted data. Proceedings of the VLDB Endowment, 2013, 6(5): 289–300

[6] Kerschbaum F, Grofig P, Hang I, Härterich M, Kohler M, Schaad A, Schröpfer A, Tighzert W. Adjustably encrypted in-memory columnstore. In: Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security. 2013, 1325–1328

[7] Kerschbaum F, Härterich M, Kohler M, Hang I, Schaad A, Schröpfer A, Tighzert W. An encrypted in-memory column-store: the onion selection problem. In: Proceedings of the International Conference on Information Systems Security. 2013, 14–26

[8] Papadimitriou A, Bhagwan R, Chandran N, Ramjee R, Haeberlen A, Singh H, Modi A, Badrinarayanan S. Big data analytics over encrypted datasets with seabed. In: Proceedings of USENIX Symposium on Operating Systems Design and Implementation. 2016, 587–602

[9] Rivest R, Adleman L, Dertouzos M. On data banks and privacy homomorphisms. Foundations of Secure Computation, 1978, 4(11): 169–177

[10] Gentry C. Fully homomorphic encryption using ideal lattices. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing. 2009, 169–178

[11] Popa R A. Building practical systems that compute on encrypted data. DissertationTip, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014

[12] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 1978, 21(2): 120–126

[13] ElGamal T. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 1985, 31(4): 469–472

[14] Paillier P. Public-key cryptosystems based on composite degree residuosity classes. In: Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques. 1999, 223–238

[15] Boldyreva A, Chenette N, Lee Y, O’neill A. Order-preserving symmetric encryption. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2009, 224–241

[16] Agrawal R, Kiernan J, Srikant R, Xu Y. Order preserving encryption for numeric data. In: Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. 2004, 563–574

[17] Boldyreva A, Chenette N, O’Neill A. Order-preserving encryption revisited: improved security analysis and alternative solutions. In: Proceedings of Annual Cryptology Conference. 2011, 578–595

[18] Song D X, Wagner D, Perrig A. Practical techniques for searches on encrypted data. In: Proceedings of IEEE Symposium on Security and Privacy. 2000, 44–55

[19] Curtmola R, Garay J, Kamara S, Ostrovsky R. Searchable symmetric encryption: improved definitions and efficient constructions. Journal of Computer Security, 2011, 19(5): 895–934

[20] Kamara S, Papamanthou C, Roeder T. Dynamic searchable symmetric encryption. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security. 2012, 965–976

[21] Rijmen V, Daemen J. Advanced encryption standard. In: Proceedings of Federal Information Processing Standards Publications, National Institute of Standards and Technology. 2001, 19–22

[22] Kaplan D, Powell J, Woller T. Amd memory encryption. White Paper, 2016

[23] Johnson S, Scarlata V, Rozas C, Brickell E, Mckeen F. IntelR software guard extensions: epid provisioning and attestation services. White Paper, 2016, 1–10

[24] Xia W, Jiang H, Feng D, Douglis F, Shilane P, Hua Y, Fu M, Zhang Y, Zhou Y. A comprehensive study of the past, present, and future of data deduplication. Proceedings of the IEEE, 2016, 104(9): 1681–1710

[25] Huffman D A. A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 1952, 40(9): 1098–1101

[26] Ziv J, Lempel A. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 1977, 23(3): 337–343

[27] Ziv J, Lempel A. Compression of individual sequences via variablerate coding. IEEE Transactions on Information Theory, 1978, 24(5): 530–536

[28] Muthitacharoen A, Chen B, Mazières D. A low-bandwidth network file system. ACM SIGOPS Operating Systems Review, 2001, 35(5): 174–187

[29] Quinlan S, Dorward S. Venti: a new approach to archival storage. In: Proceedings of USENIX Conference on File and Storage Technologies. 2002, 89–101

[30] Wallace G, Douglis F, Qian H, Shilane P, Smaldone S, Chamness M, Hsu W. Characteristics of backup workloads in production systems. In: Proceedings of the 10th USENIX Conference on File and Storage Technologies. 2012, 4

[31] Zhu B, Li K, Patterson R H. Avoiding the disk bottleneck in the data domain deduplication file system. In: Proceedings of the 6th USENIX Conference on File and Storage Technologies. 2008, 1–14

[32] Lillibridge M, Eshghi K, Bhagwat D, Deolalikar V, Trezis G, Camble P. Sparse indexing: large scale, inline deduplication using sampling and locality. In: Proceedings of the 7th USENIX Conference on File and Storage Technologies. 2009, 111–123

[33] Dubnicki C, Gryz L, Heldt L, Kaczmarczyk M, Kilian W, Strzelczak P, Szczepkowski J, Ungureanu C, Welnicki M. Hydrastor: a scalable secondary storage. In: Proceedings of the 7th USENIX Conference on File and Storage Technologies. 2009, 197–210

[34] Guo F, Efstathopoulos P. Building a high-performance deduplication system. In: Proceedings of the 2011 USENIX Annual Technical Conference. 2011, 25

[35] Srinivasan K, Bisson T, Goodson G R, Voruganti K. iDedup: latencyaware, inline data deduplication for primary storage. In: Proceedings of the 10th USENIX Conference on File and Storage Technologies. 2012, 1–14

[36] Whiting D L, Dilatush T. System for backing up files from disk volumes on multiple nodes of a computer network. 1998, US Patent 5,778,395

[37] Bellare M, Keelveedhi S, Ristenpart T. Message-locked encryption and secure deduplication. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2013, 296–312

[38] Keelveedhi S, Bellare M, Ristenpart T. Dupless: server-aided encryption for deduplicated storage. In: Proceedings of USENIX Security Symposium. 2013, 179–194

[39] Li J, Chen X, Li M, Li J, Lee P P, Lou W. Secure deduplication with efficient and reliable convergent key management. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(6): 1615–1625

RIGHTS & PERMISSIONS

2019 Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature