Сравнительный анализ алгоритмов гомоморфного шифрования на основе обучения с ошибками

Повсеместное использование облачных технологий позволяет оптимизировать экономические издержки на содержание ИТ-инфраструктуры предприятий, но при этом увеличивает вероятность кражи конфиденциальных данных. Одним из механизмов для защиты данных от кражи является криптография. Использование классических примитивов симметричного и ассиметричного шифрования не позволяет обрабатывать данные в зашифрованном виде. Для обработки конфиденциальных данных используют гомоморфное шифрование. Гомоморфное шифрование позволяет производить арифметические действия с зашифрованным текстом и получать зашифрованный результат, который соответствует результату операций, выполненных с открытым текстом. Одним из перспективных направлений для построения гомоморфных шифров является гомоморфные шифры, основанные на обучении с ошибками. В статье мы исследуем криптографические свойства существующих гомоморфных шифров (CKKS, BFV) на основе обучения с ошибками, сравниваем их технические характеристики: криптостойкость и избыточность данных, скорость кодирования и декодирования данных, скорость выполнения арифметических операций сложения и умножения данных, скорость выполнения операции KeySwitching.

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.