×

Secret computation of purchase history data using somewhat homomorphic encryption. (English) Zbl 1337.94084

Summary: We consider secret computation of purchase history data among two companies of different type of business in order to identify purchase patterns without revealing customer information of each company. Among several privacy-preserving approaches, we focus on homomorphic encryption, which is public-key encryption supporting meaningful computations on encrypted data. In particular, we apply the somewhat homomorphic encryption scheme proposed by Z. Brakerski and V. Vaikuntanathan [Crypto 2011, Lect. Notes Comput. Sci. 6841, 505–524 (2011; Zbl 1290.94051)], which can support a limited number of both additions and multiplications over polynomials. The main contribution is to introduce a practical packing method in the scheme to efficiently compute the set intersection of purchase history data over packed ciphertexts. Furthermore, we implemented the scheme for several parameters corresponding to various security levels, and demonstrate the efficiency of our packing method. We hope that this work would give the first practical usage of somewhat homomorphic encryption in marketing analysis.

MSC:

94A60 Cryptography

Citations:

Zbl 1290.94051

Software:

BKZ; fhe
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Boneh, D., Goh, EJ., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts Theory of Cryptography-TCC 2005. In: Lecture Notes in Computer Science, pp. 325-341. Springer, (2005) · Zbl 1079.94534
[2] Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Innovations in Theoretical Computer Science-ITCS 2012, pp. 309-325. ACM, (2012) · Zbl 1347.68120
[3] Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: Foundations of Computer Science-FOCS 2011, pp. 97-106. IEEE, (2011) · Zbl 1292.94038
[4] Brakerski, Z., Vaikuntanathan, V.: Fully homomorphic encryption from ring-LWE and security for key dependent messages. In: Advances in Cryptology-CRYPTO 2011. Lecture Notes in Computer Science, pp. 505-524. Springer, (2011) · Zbl 1290.94051
[5] Chen, Y., Nguyen, P.: BKZ 2.0: better lattice security estimates. In: Advances in Cryptology-ASIACRYPT 2011. Lecture Notes in Computer Science, pp. 1-20. Springer, (2011) · Zbl 1227.94037
[6] Coron, JS., Mandal, A., Naccache, D., Tibouchi, M.: Fully homomorphic encryption over the integers with shorter public keys. In: Advances in Cryptology-CRYPTO 2011 Lecture Notes in Computer Science, pp. 487-504. Springer, (2011) · Zbl 1290.94059
[7] Cramer, R., Shoup, V., Schoenmakers, B.: A secure and optimally efficient multi-authority election scheme. In: Advances in Cryptology-EUROCRYPT 1997. Lecture Notes in Computer Science, pp. 103-118. Springer, (1997)
[8] Damgård, I., Pasto, V., Smart, N., Zakarias, S.: Multiparty computation from somewhat homomorphic encryption. In: Advances in Cryptology-CRYPTO 2012. Lecture Notes in Computer Science, pp. 643-662. Springer, (2012) · Zbl 1296.94104
[9] Gentry, C.: A fully homomorphic encryption scheme. PhD thesis, Stanford University (2009) · Zbl 1304.94059
[10] Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Symposium on Theory of Computing-STOC 2009, pp. 169-178. ACM, (2009) · Zbl 1304.94059
[11] Gentry, C., Halevi, S.: Implementing Gentry’s fully-homomorphic encryption scheme. In: Advances in Cryptology-EUROCRYPT 2011. Lecture Notes in Computer Science, pp. 129-148. Springer, (2011) · Zbl 1281.94026
[12] Gentry, C., Halevi, S., Smart, N.: Homomorphic evaluation of the AES circuit, pp. 850-867. Springer, (2012) · Zbl 1296.94117
[13] Lindner, R., Peikert, C.: Better key sizes (and attacks) for LWE-based encryption. In: RSA Conference on Topics in Cryptology-CT-RSA 2011. Lecture Notes in Computer Science, pp. 319-339. Springer, (2011) · Zbl 1284.94088
[14] Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Advances in Cryptology-EUROCRYPT 2010. Lecture Notes in Computer Science, pp. 1-23. Springer, (2010) · Zbl 1279.94099
[15] Micciancio, D., Regev, O.: Worst-case to average-case reduction based on Gaussian measures. SIAM J. Comput. 37(1), 267-302 (2007) · Zbl 1142.68037 · doi:10.1137/S0097539705447360
[16] Naehrig, M., Lauter, K., Vaikuntanathan, V.: Can homomorphic encryption be practical? In: Proceedings of the 3rd ACM workshop on Cloud computing security workshop-CCSW 2011, pp. 113-124. ACM, (2011)
[17] Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Advances in Cryptology-EUROCRYPT 1999. Lecture Notes in Computer Science, pp. 223-238. Springer, (1999) · Zbl 0933.94027
[18] van Dijk, M., Gentry, C., Halevi, S., Vaikuntanathan, V.: Fully homomorphic encryption over the integers. In: Advances in Cryptology-EUROCRYPT 2010 Lecture Notes in Computer Science, pp. 24-43. Springer, (2010) · Zbl 1279.94130
[19] Yasuda, M., Shimoyama, T., Kogure, J., Yokoyama, K., Koshiba, T.: Packed homomorphic encryption based on ideal lattices and its application to biometrics. In: Modern Cryptography and Security Engineering-MoCrySEn 2013. Lecture Notes in Computer Science, pp. 55-74. Springer, (2013) · Zbl 1391.94820
[20] Yasuda, M., Shimoyama, T., Kogure, J., Yokoyama, K., Koshiba, T.: Secure pattern matching using somewhat homomorphic encryption. In: Proceedings of the 5th ACM workshop on Cloud computing security-CCSW 2013, pp. 65-76. ACM, (2013) · Zbl 1337.94085
[21] Yasuda, M., Shimoyama, T., Kogure, J., Yokoyama, K., Koshiba, T.: Practical packing method in somewhat homomorphic encryption. In: Data Privacy Management and Autonomous Spontaneous Security. Lecture Notes in Computer Science, pp. 34-50. Springer, (2014) · Zbl 1337.94085
[22] Yasuda, M., Shimoyama, T., Yokoyama, K., Kogure, J.: A customer information analysis between enterprises using homomorphic encryption (in Japanese). In: Forum on Information Technology-FIT 2013, pp. 15-22. IPSJ, (2013)
[23] Yasuda, M., Yajima, J., Shimoyama, T., Kogure, J.: Secret totalization of purchase histories of companies in cloud (in Japanese). In: 29th Symposium on Cryptography and Information Security-SCIS 2012 number 3D-2. IEICE, (2012)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.