Batch Symmetric Fully Homomorphic Encryption Using Matrix Polynomials
https://doi.org/10.15514/ISPRAS-2014-26(5)-5
Abstract
Fully homomorphic encryption (FHE) is a recognized tool to obtain the cryptographic protec-tion of cloud computing. However, the characteristics of existing FHE schemes are not suffi-cient for use in practice � the security of some FHE is unsatisfying, others require too much computational resources. For improvement the efficiency of the last one IBM researchers pro-posed a method for "ciphertexts batching", which was applied by them to public key FHE scheme whose security is based on the complexity of the lattice theory hardness assumptions. In this paper, we discuss several methods for embedding "ciphertexts batching" into recently proposed symmetric encryption scheme based on matrix polynomials. For one of this method we completely specify how cryptosystem algorithms should work. The results of computer experiments are given.
References
1. [1]. R. L. Rivest, L. Adleman, M. L. Dertouzos. On data banks and privacy homomorphisms. Foundations of secure computation. 1978, Vol. 4, №. 11. pp. 169-180
2. [2]. C. Gentry. Fully homomorphic encryption using ideal lattices. Proceedings of the 41st annual ACM symposium on Symposium on theory of computing-STOC'09. – ACM Press, 2009. Vol. 9, pp. 169-169. doi:10.1145/1536414.1536440
3. [3]. A. Silverberg. Fully homomorphic encryption for mathematicians. Women in Numbers 2: Research Directions in Number Theory, 2013. Vol. 606. p. 111.
4. [4]. N.P. Varnovskij, А.V. Shokurov. Gomomorfnoe shifrovanie. [Homomorphic encryption]. Trudy ISP RАN [The Proceedings of ISP RAS], 2007. Vol. 12, pp. 27-36. (in Russian).
5. [5]. O. Zhirov, O. V. Zhirova, and S. F. Krendelev. Bezopasnye oblachnye vychisleniya s pomoshhyu homomorfnoj cryptographii. [Secure cloud computing using homomorphic cryptography]. BIT (bezopasnost’ informacionnyx technology) journal [Security of Information Technologies Magazine], 2013, Vol. 1, pp. 6–12. (in Russian).
6. [6]. Nigel P. Smart, F. Vercauteren. Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes. Public Key Cryptography-PKC 2010: 13th International Conference on Practice and Theory in Public Key Cryptography, Paris, France, May 26-28, 2010, Proceedings. – Springer, 2010. p. 420.
7. [7]. Naehrig M., Lauter K., Vaikuntanathan V. Can homomorphic encryption be practical? Proceedings of the 3rd ACM workshop on Cloud computing security workshop. – ACM, 2011. pp. 113-124. doi: 10.1145/2046660.2046682
8. [8]. C. Gentry, S. Halevi, N. P. Smart. Fully homomorphic encryption with polylog overhead. Advances in Cryptology–EUROCRYPT 2012. – Springer Berlin Heidelberg, 2012. pp. 465-482. doi: 10.1007/978-3-642-29011-4_28
9. [9]. Cheon, J. H., Coron, J. S., Kim, J., Lee, M. S., Lepoint, T., Tibouchi, M., Yun, A. Batch Fully Homomorphic Encryption over the Integers. Advances in Cryptology–EUROCRYPT. – Vol. 7881. – 2013. pp. 315-335. doi: 10.1007/978-3-642-38348-9_20
10. [10]. Z. Brakerski, C. Gentry, S. Halevi. Packed ciphertexts in LWE-based homomorphic encryption. Public-Key Cryptography–PKC 2013. – Springer Berlin Heidelberg, 2013. – pp. 1-13. doi: 10.1007/978-3-642-36362-7_1
11. [11]. Yasuda, M., Shimoyama, T., Kogure, J., Yokoyama, K., Koshiba, T. Packed homomorphic encryption based on ideal lattices and its application to biometrics. Security Engineering and Intelligence Informatics. – Springer Berlin Heidelberg, 2013. pp. 55-74.
12. [12]. Nigel P. Smart, F. Vercauteren. Fully homomorphic SIMD operations. Designs, codes and cryptography, 2014. Vol. 71, №. 1. – pp. 57-81. doi: 10.1007/s10623-012-9720-4
13. [13]. Yasuda, M., Shimoyama, T., Kogure, J., Yokoyama, K., Koshiba, T. Practical packing method in somewhat homomorphic encryption. Data Privacy Management and Autonomous Spontaneous Security. – Springer Berlin Heidelberg, 2014. pp. 34-50.
14. [14]. Zhirov A., Zhirova O., Krendelev S. F. Practical fully homomorphic encryption over polynomial quotient rings. Internet Security (WorldCIS), 2013 World Congress on. – IEEE, 2013. pp. 70-75. doi: 10.1109/WorldCIS.2013.6751020
15. [15]. Hojsík M., Půlpánová V. A fully homomorphic cryptosystem with approximate perfect secrecy. Proceedings of the 13th international conference on Topics in Cryptology. – Springer-Verlag, 2013. pp. 375-388. doi: 10.1007/978-3-642-36095-4_24
16. [16]. J. Domingo-Ferrer. A Provably Secure Additive and Multiplicative Privacy Homomorphism*. Information Security. – Springer Berlin Heidelberg, 2002. pp. 471-483.
17. [17]. Gavin G. An efficient FHE based on the hardness of solving systems of non-linear multivariate equations. IACR Cryptology ePrint Archive, 2013. №. 262.
18. [18]. Albrecht, M. R., Farshim, P., Faugere, J. C., Perret, L. Polly cracker, revisited. Advances in Cryptology–ASIACRYPT 2011. – Springer Berlin Heidelberg, 2011. pp. 179-196.
19. [19]. Herold G. Polly cracker, revisited, revisited. Public Key Cryptography–PKC 2012. – Springer Berlin Heidelberg, 2012. – pp. 17-33.
20. [20]. Armknecht, F., Augot, D., Perret, L., Sadeghi, A. R. On constructing homomorphic encryption schemes from coding theory. Cryptography and Coding. – Springer Berlin Heidelberg, 2011. – pp. 23-40.
21. [21]. Rostovtsev A., Bogdanov A., Mikhaylov M. Metod bezopasnogo vychislenija polinoma v nedoverennoj srede s pomowqju gomomorfizmov kolec [Secure evaluation of polynomial using privacy ring homomorphisms]. Problemy informacionnoj bezopasnosti. Kompqjuternye sistemy [Information security issues. Computer systems], 2011. Vol. 2. – pp. 76-85. (in Russian).
22. [22]. Wagner D. Cryptanalysis of an algebraic privacy homomorphism. Proc. of 6th Information Security Conference (ISC'03). – 2003. doi: 10.1.1.5.1420
23. [23]. Trepacheva A., Babenko L. Known plaintexts attack on polynomial based homomorphic encryption. Proceedings of the 7th International Conference on Security of Information and Networks. – ACM, 2014. – pp. 157. doi: 10.1145/2659651.2659692
24. [24]. Ph. Burtyka, O. Makarevich. Symmetric Fully Homomorphic Encryption Using Decidable Matrix Equations. Proceedings of the 7th International Conference on Security of Information and Networks. ACM, 2014, pp. 186–196. doi: 10.1145/2659651.2659693
25. [25]. F. B. Burtyka. Simmetrichnoe polnost'ju gomomorfnoe shifrovanie s ispol'zovaniem neprivodimyh matrichnyh polinomov [Symmetric fully homomorphic encryption using irreducible matrix polynomials]. Izvestija Juzhnogo federal'nogo universiteta. Tehnicheskie nauki [Proceedings of Southern Federal University. Engineering sciences], 2014, Vol. 158, №. 9, pp. 107-122. (in Russian).
26. [26]. Boneh, D., Gentry, C., Halevi, S., Wang, F., Wu, D. J. Private database queries using somewhat homomorphic encryption. Applied Cryptography and Network Security. – Springer Berlin Heidelberg, 2013. – pp. 102-118. doi: 10.1007/978-3-642-38980-1_7
27. [27]. S. Halevi, V. Shoup. Algorithms in HElib. IACR Cryptology ePrint Archive, 2014. №. 106.
28. [28]. S. Halevi. (2012) Performance of HElib. [Online]. Available: http://mpclounge.files.wordpress.com/2013/04/hespeed.pdf (Visited on 18.12.2014)
29. [29]. Burtyka Ph. B. O slozhnosti naxozhdenija kornej bulevyx matrichnyx polinomov [On the complexity of finding the roots of Boolean matrix polynomials]. Matematicheskoe modelirovanie [Matematical modelling], 2015. Vol. 27, №. 7. (in Russian).
30. [30]. Dennis, Jr J. E., Traub J. F., Weber R. P. The algebraic theory of matrix polynomials. SIAM Journal on Numerical Analysis, 13(6), 1976. pp. 831-845.
31. [31]. Dennis, Jr J. E., Traub J. F., Weber R. P. Algorithms for solvents of matrix polynomials. SIAM Journal on Numerical Analysis, 1978. Vol. 15. – №. 3. – pp. 523-533.
32. [32]. Antoine Guellier. Can Homomorphic Cryptography ensure Privacy? [Research Report] RR-8568, 2014, pp.111. https://hal.inria.fr/hal-01052509v1
Review
For citations:
Burtyka P. Batch Symmetric Fully Homomorphic Encryption Using Matrix Polynomials. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2014;26(5):99-116. (In Russ.) https://doi.org/10.15514/ISPRAS-2014-26(5)-5
Email this article 