Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2019, Vol. 13 Issue (2) : 220-230    https://doi.org/10.1007/s11704-019-8394-8
RESEARCH ARTICLE
Practices of backuping homomorphically encrypted databases
Sa WANG1,2(), Yiwen SHAO1,2, Yungang BAO1,2
1. SKL Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
2. University of Chinese Academy of Sciences, Beijing 100049, China
 Download: PDF(521 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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     
Corresponding Author(s): Sa WANG   
Just Accepted Date: 31 January 2019   Online First Date: 26 March 2019    Issue Date: 08 April 2019
 Cite this article:   
Sa WANG,Yiwen SHAO,Yungang BAO. Practices of backuping homomorphically encrypted databases[J]. Front. Comput. Sci., 2019, 13(2): 220-230.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-019-8394-8
https://academic.hep.com.cn/fcs/EN/Y2019/V13/I2/220
1 R APopa, C Redfield, NZeldovich, HBalakrishnan. Cryptdb: protecting confidentiality with encrypted query processing. In: Proceedings of the 23rd ACM Symposium on Operating Systems Principles. 2011, 85–100
https://doi.org/10.1145/2043556.2043566
2 LFerretti, M Colajanni, MMarchetti. Supporting security and consistency for cloud database. In: Proceedings of the 4th International Conference on Cyberspace Safety and Security. 2012, 179–193
https://doi.org/10.1007/978-3-642-35362-8_15
3 LFerretti, M Colajanni, MMarchetti. Distributed, concurrent, and independent access to encrypted cloud databases. IEEE Transactions on Parallel and Distributed Systems. 2014, 25(2): 437–446
https://doi.org/10.1109/TPDS.2013.154
4 KKerschbaum, M Härterich, PGrofig, MKohler, ASchaad, ASchröpfer, WTighzert. 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
https://doi.org/10.1007/978-3-642-39256-6_13
5 STu, M F Kaashoek, SMadden, NZeldovich. Processing analytical queries over encrypted data. Proceedings of the VLDB Endowment, 2013, 6(5): 289–300
https://doi.org/10.14778/2535573.2488336
6 FKerschbaum, PGrofig, IHang, M Härterich, MKohler, ASchaad, A Schröpfer, WTighzert . Adjustably encrypted in-memory columnstore. In: Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security. 2013, 1325–1328
7 FKerschbaum, M Härterich, MKohler, IHang, ASchaad, ASchröpfer, WTighzert. An encrypted in-memory column-store: the onion selection problem. In: Proceedings of the International Conference on Information Systems Security. 2013, 14–26
https://doi.org/10.1007/978-3-642-45204-8_2
8 APapadimitriou, R Bhagwan, NChandran, RRamjee, A Haeberlen, HSingh, AModi, S Badrinarayanan. Big data analytics over encrypted datasets with seabed. In: Proceedings of USENIX Symposium on Operating Systems Design and Implementation. 2016, 587–602
9 RRivest, L Adleman, MDertouzos. On data banks and privacy homomorphisms. Foundations of Secure Computation, 1978, 4(11): 169–177
10 CGentry. Fully homomorphic encryption using ideal lattices. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing. 2009, 169–178
https://doi.org/10.1145/1536414.1536440
11 R APopa. Building practical systems that compute on encrypted data. DissertationTip, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2014
12 R LRivest, AShamir, LAdleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 1978, 21(2): 120–126
https://doi.org/10.1145/359340.359342
13 TElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 1985, 31(4): 469–472
https://doi.org/10.1109/TIT.1985.1057074
14 PPaillier. 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
https://doi.org/10.1007/3-540-48910-X_16
15 ABoldyreva, N Chenette, YLee, AO’neill. Order-preserving symmetric encryption. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2009, 224–241
https://doi.org/10.1007/978-3-642-01001-9_13
16 RAgrawal, J Kiernan, RSrikant, YXu. Order preserving encryption for numeric data. In: Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data. 2004, 563–574
https://doi.org/10.1145/1007568.1007632
17 ABoldyreva, N Chenette, AO’Neill. Order-preserving encryption revisited: improved security analysis and alternative solutions. In: Proceedings of Annual Cryptology Conference. 2011, 578–595
https://doi.org/10.1007/978-3-642-22792-9_33
18 D XSong, DWagner, APerrig. Practical techniques for searches on encrypted data. In: Proceedings of IEEE Symposium on Security and Privacy. 2000, 44–55
19 RCurtmola, JGaray, SKamara, R Ostrovsky. Searchable symmetric encryption: improved definitions and efficient constructions. Journal of Computer Security, 2011, 19(5): 895–934
https://doi.org/10.3233/JCS-2011-0426
20 SKamara, C Papamanthou, TRoeder. Dynamic searchable symmetric encryption. In: Proceedings of the 2012 ACM Conference on Computer and Communications Security. 2012, 965–976
https://doi.org/10.1145/2382196.2382298
21 VRijmen, JDaemen. Advanced encryption standard. In: Proceedings of Federal Information Processing Standards Publications, National Institute of Standards and Technology. 2001, 19–22
22 DKaplan, JPowell, TWoller. Amd memory encryption. White Paper, 2016
23 SJohnson, V Scarlata, CRozas, EBrickell, FMckeen. IntelR software guard extensions: epid provisioning and attestation services. White Paper, 2016, 1–10
24 WXia, HJiang, DFeng, F Douglis, PShilane, YHua, MFu, YZhang, Y Zhou. A comprehensive study of the past, present, and future of data deduplication. Proceedings of the IEEE, 2016, 104(9): 1681–1710
https://doi.org/10.1109/JPROC.2016.2571298
25 D AHuffman. A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 1952, 40(9): 1098–1101
https://doi.org/10.1109/JRPROC.1952.273898
26 JZiv, ALempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 1977, 23(3): 337–343
https://doi.org/10.1109/TIT.1977.1055714
27 JZiv, ALempel. Compression of individual sequences via variablerate coding. IEEE Transactions on Information Theory, 1978, 24(5): 530–536
https://doi.org/10.1109/TIT.1978.1055934
28 AMuthitacharoen, B Chen, DMazières. A low-bandwidth network file system. ACM SIGOPS Operating Systems Review, 2001, 35(5): 174–187
https://doi.org/10.1145/502059.502052
29 SQuinlan, S Dorward. Venti: a new approach to archival storage. In: Proceedings of USENIX Conference on File and Storage Technologies. 2002, 89–101
30 GWallace, F Douglis, HQian, PShilane, S Smaldone, MChamness, WHsu. Characteristics of backup workloads in production systems. In: Proceedings of the 10th USENIX Conference on File and Storage Technologies. 2012, 4
31 BZhu, KLi, R HPatterson. 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 MLillibridge, KEshghi, DBhagwat, V Deolalikar, GTrezis, PCamble. 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 CDubnicki, LGryz, LHeldt, M Kaczmarczyk, WKilian, PStrzelczak, J Szczepkowski, CUngureanu, MWelnicki. Hydrastor: a scalable secondary storage. In: Proceedings of the 7th USENIX Conference on File and Storage Technologies. 2009, 197–210
34 FGuo, P Efstathopoulos. Building a high-performance deduplication system. In: Proceedings of the 2011 USENIX Annual Technical Conference. 2011, 25
35 KSrinivasan, TBisson, G RGoodson, K Voruganti. iDedup: latencyaware, inline data deduplication for primary storage. In: Proceedings of the 10th USENIX Conference on File and Storage Technologies. 2012, 1–14
36 D LWhiting, T Dilatush. System for backing up files from disk volumes on multiple nodes of a computer network. 1998, US Patent 5,778,395
37 MBellare, S Keelveedhi, TRistenpart. Message-locked encryption and secure deduplication. In: Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2013, 296–312
https://doi.org/10.1007/978-3-642-38348-9_18
38 SKeelveedhi, M Bellare, TRistenpart. Dupless: server-aided encryption for deduplicated storage. In: Proceedings of USENIX Security Symposium. 2013, 179–194
39 JLi, XChen, MLi, JLi, P PLee, W Lou. Secure deduplication with efficient and reliable convergent key management. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(6): 1615–1625
https://doi.org/10.1109/TPDS.2013.284
[1] Article highlights Download
[1] Bin GUO, Yasan DING, Yueheng SUN, Shuai MA, Ke LI, Zhiwen YU. The mass, fake news, and cognition security[J]. Front. Comput. Sci., 2021, 15(3): 153806-.
[2] Abhishek MAJUMDAR, Arpita BISWAS, Atanu MAJUMDER, Sandeep Kumar SOOD, Krishna Lal BAISHNAB. A novel DNA-inspired encryption strategy for concealing cloud storage[J]. Front. Comput. Sci., 2021, 15(3): 153807-.
[3] Zeli WANG, Hai JIN, Weiqi DAI, Kim-Kwang Raymond CHOO, Deqing ZOU. Ethereum smart contract security research: survey and future research opportunities[J]. Front. Comput. Sci., 2021, 15(2): 152802-.
[4] Je Sen TEH, Weijian TENG, Azman SAMSUDIN, Jiageng CHEN. A post-processing method for true random number generators based on hyperchaos with applications in audio-based generators[J]. Front. Comput. Sci., 2020, 14(6): 146405-.
[5] Xiaochen LIU, Chunhe XIA, Tianbo WANG, Li ZHONG, Xiaojian LI. A behavior-aware SLA-based framework for guaranteeing the security conformance of cloud service[J]. Front. Comput. Sci., 2020, 14(6): 146808-.
[6] Yanwei ZHOU, Bo YANG. Practical continuous leakage-resilient CCA secure identity-based encryption[J]. Front. Comput. Sci., 2020, 14(4): 144804-.
[7] Yudi ZHANG, Debiao HE, Mingwu ZHANG, Kim-Kwang Raymond CHOO. A provable-secure and practical two-party distributed signing protocol for SM2 signature algorithm[J]. Front. Comput. Sci., 2020, 14(3): 143803-.
[8] Xingyue CHEN, Tao SHANG, Feng ZHANG, Jianwei LIU, Zhenyu GUAN. Dynamic data auditing scheme for big data storage[J]. Front. Comput. Sci., 2020, 14(1): 219-229.
[9] Tianyong WU, Xi DENG, Jun YAN, Jian ZHANG. Analyses for specific defects in Android applications: a survey[J]. Front. Comput. Sci., 2019, 13(6): 1210-1227.
[10] Yan ZHU, Khaled RIAD, Ruiqi GUO, Guohua GAN, Rongquan FENG. New instant confirmation mechanism based on interactive incontestable signature in consortium blockchain[J]. Front. Comput. Sci., 2019, 13(6): 1182-1197.
[11] Mei LI, Hongjun ZHANG, Yanjun WU, Chen ZHAO. Prefetch-aware fingerprint cache management for data deduplication systems[J]. Front. Comput. Sci., 2019, 13(3): 500-515.
[12] Wei GAO, Guilin WANG, Kefei CHEN, Xueli WANG. Efficient identity-based threshold decryption scheme from bilinear pairings[J]. Front. Comput. Sci., 2018, 12(1): 177-189.
[13] Lip Yee POR, Chin Soon KU, Amanul ISLAM, Tan Fong ANG. Graphical password: prevent shoulder-surfing attack using digraph substitution rules[J]. Front. Comput. Sci., 2017, 11(6): 1098-1108.
[14] Cheqing JIN, Jie CHEN, Huiping LIU. MapReduce-based entity matching with multiple blocking functions[J]. Front. Comput. Sci., 2017, 11(5): 895-911.
[15] Xuzhou LI,Yilong YIN,Yanbin NING,Gongping YANG,Lei PAN. A hybrid biometric identification framework for high security applications[J]. Front. Comput. Sci., 2015, 9(3): 392-401.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed