Practical Packing Method in Somewhat Homomorphic Encryption
Somewhat homomorphic encryption is public key encryption supporting a limited number of both additions and multiplications on encrypted data, which is useful for performing fundamental computations with protecting the data confidentiality. In this paper,
- PDF / 272,121 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 73 Downloads / 298 Views
Fujitsu Laboratories Ltd., Kamikodanaka 4-chome, Nakahara-ku, Kawasaki 211-8588, Japan {yasuda.masaya,shimo-shimo,kogure}@jp.fujitsu.com 2 Department of Mathematics, Rikkyo University, Nishi-Ikebukuro, Tokyo 171-8501, Japan [email protected] 3 Division of Mathematics, Electronics and Informatics, Graduate School of Science and Engineering, Saitama University, 255 Shimo-Okubo, Sakura, Saitama 338-8570, Japan [email protected]
Abstract. Somewhat homomorphic encryption is public key encryption supporting a limited number of both additions and multiplications on encrypted data, which is useful for performing fundamental computations with protecting the data confidentiality. In this paper, we focus on the scheme proposed by Lauter, Naehrig and Vaikuntanathan (ACM CCSW 2011), and present two types of packed ciphertexts based on their packing technique. Combinations of two types of our packing method give practical size and performance for wider computations such as statistical analysis and distances. To demonstrate its efficiency, we implemented the scheme with our packing method for secure Hamming distance, which is often used in privacy-preserving biometrics. For secure Hamming distance between two binary [email protected] of 2048bit, it takes 5.31 ms on an Intel Xeon X3480 at 3.07 GHz. This gives the best performance in the state-of-the-art work using homomorphic encryption. Keywords: Somewhat homomorphic encryption · Ring-LWE assumption · Packed ciphertexts · Secure Hamming distance
1
Introduction
Homomorphic encryption is public key encryption with the additional property that it supports some operations on encrypted data. This gives a useful method in performing meaningful computations with protecting the data privacy. The recent development of cloud storage and computing allows users to outsource their data to cloud services. On the other hand, new privacy concerns for both individuals and business have risen (see [10]). With homomorphic encryption, J. Garcia-Alfaro et al. (Eds.): DPM 2013 and SETOP 2013, LNCS 8247, pp. 34–50, 2014. c Springer-Verlag Berlin Heidelberg 2014 DOI: 10.1007/978-3-642-54568-9 3,
Practical Packing Method in Somewhat Homomorphic Encryption
35
users send their data in encrypted form to the cloud, and the cloud still can perform computations on encrypted data. Since all data in the cloud are in encrypted form, the confidentiality of users’ data is preserved irrespective of any actions in the cloud. Therefore this encryption would give a powerful tool to break several barriers to the adoption of cloud services for various uses. In cryptography, homomorphic encryption schemes proposed before 2000 can only support simple operations such as either additions or multiplications on encrypted data (see [12,18,26] for examples), and hence the applications of these schemes are very limited (typical applications of additive schemes are electronic voting and cash). The first scheme supporting both additions and multiplications is the BGN scheme [3] proposed in 2005
Data Loading...
