Comparative Analysis of Homomorphic Encryption Algorithms Based on Learning with Errors

The widespread use of cloud technology allows optimizing the economic costs of maintaining the IT infrastructure of enterprises, but this increases the likelihood of theft of confidential data. One of the mechanisms to protect data from theft is cryptography. Using the classical primitives of symmetric and asymmetric encryption does not allow processing data in encrypted form. Homomorphic encryption is used for processing confidential data. Homomorphic encryption allows performing of arithmetic operations over encrypted text and obtaining an encrypted result that corresponds to the result of operations performed over plaintext. One of the perspective directions for constructing homomorphic ciphers is homomorphic ciphers based on Learning with Errors. In this paper we examine the cryptographic properties of existing homomorphic ciphers (CKKS, BFV) based on Learning with Errors, compare their technical characteristics: cryptographic strength and data redundancy, data encoding and decoding speed, speed of arithmetic operations, such as addition and multiplication, KeySwitching operation speed.

1. Craig Gentry. A Fully Homomorphic Encryption Scheme. PhD thesis, Stanford University, 2009, 199 p.

2. Martin R. Albrecht, Shi Bai, and Léo Ducas. A subfield lattice attack on overstretched NTRU assumptions - cryptanalysis of some FHE and graded encoding schemes. Lecture Notes in Computer Science, vol. 9814, 2016, pp. 153-178.

3. Marten Van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. Fully Homomorphic Encryption over the Integers. In Proc. of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2010, pp. 24-43.

4. Zvika Brakerski. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. Lecture Notes in Computer Science, vol. 7417, 2012, pp. 868-886.

5. Adriana López-Alt, Eran Tromer, and Vinod Vaikuntanathan. On-the-Fly Multiparty Computation on the Cloud via Multikey Fully Homomorphic Encryption. In Proc. of the forty-fourth Annual ACM Symposium on Theory of Computing, 2012, pp. 1219-1234.

6. Junfeng Fan and Frederik Vercauteren. Somewhat Practical Fully Homomorphic Encryption. IACR Cryptology ePrint Archive, 2012:144, 2012.

7. Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic encryption from Learning with Errors: Conceptually-Simpler, Asymptotically Faster, Attribute-Based. Lecture Notes in Computer Science, vol. 8042, 2013, pages 75-92.

8. Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (Leveled) Fully Homomorphic Encryption without Bootstrapping. ACM Transactions on Computation Theory (TOCT), vol. 6, issue 3, 2014, article no. 13.

9. Tancrède Lepoint, Michael Naehrig. A Comparison of the Homomorphic Encryption Schemes FV and YASHE. Lecture Notes in Computer Science, vol. 8469, 2014, pp. 318=335.

10. Jean-Claude Bajard, Julien Eynard, M Anwar Hasan, and Vincent Zucca. A Full RNS Variant of FV Like Somewhat Homomorphic Encryption Schemes. Lecture Notes in Computer Science, vol. 10532, 2016, pp. 423-442.

11. Shai Halevi, Yuriy Polyakov, and Victor Shoup. An Improved RNS Variant of the BFV Homomorphic Encryption Scheme. Lecture Notes in Computer Science, vol. 11405, 2019, pp. 83-105.

12. Hao Chen, Kim Laine and Rachel Player. Simple Encrypted Arithmetic Library-SEAL (v2.1). Lecture Notes in Computer Science, vol. 10323, 2017, pp. 3-18.

13. Lattigo: lattice-based cryptographic library in Go. Available at: https://github.com/ldsec/lattigo, accessed: 10.05.2020.

14. Behrooz Parhami. Computer Arithmetic: Algorithms and Hardware Design. 2nd edition, Oxford University Press, New York, 2010. 641+xxv p.

15. Varnovsky N.P., Shokurov A.V. Homomorphic Encryption. Trudy ISP RAN/Proc. ISP RAS, vol. 12, 2007, pp. 27-36 (in Russian) / Варновский Н.П., Шокуров А.В. Гомоморфное шифрование. Труды ИСП РАН, том 12, 2007 г., стр. 27–36.

16. Babenko L.K., Burtyka Ph.B., Makarevich O.B., Trepacheva A.V. Fully Homomorphic Encryption Techniques using Matrix Polynomials. Voprosy kiberbezopasnosti, no. 1(9), 2015, pp. 14-25 (in Russian) / Бабенко Л.К., Буртыка Ф.Б., Макаревич О.Б., Трепачева А.В. Методы полностью гомоморфного шифрования на основе матричных полиномов. Вопросы кибербезопасности, no. 1(9), 2015 г., стр. 14-25.

17. Erdnieva N.S. The use of special modules of the system of residual classes for redundant representations. Vestnik of Astrakhan State Technical University. Series: Management, Computer Science and Informatics, № 2, 2013, pp. 75-85 (in Russian) / Эрдниева Н.С. Использование специальных модулей системы остаточных классов для избыточного представления. Вестник Астраханского государственного технического университета. Серия: управление, вычислительная техника и информатика, № 2, 2013 г., стр. 75-85.

18. Sagalovich Yu. L. Introduction to algebraic codes, 2nd ed. M., IPPI RAS, 2011, 302 p. (in Russian) / Сагалович Ю. Л. Введение в алгебраические коды, 2-е изд. М., ИППИ РАН, 2011, 302 c.

19. Lavrinenko A.N., Chervyakov N.I. Research of non-modular operations in the system of residual classes. Belgorod State University Scientific Bulletin. Series: Economics. Computer science, no. 1(120), 2012, pp. 110-122 (in Russian) / Лавриненко А.Н., Червяков Н.И. Исследование немодульных операций в системе остаточных классов. Научные ведомости Белгородского государственного университета. Серия: Экономика. Информатика, no. 1 (120), 2012 г., стр. 110-122.

20. Martin Albrecht et al. Homomorphic encryption security standard. Technical report, HomomorphicEncryption.org, Toronto, Canada, 2018, 33 p.