Оптимизация алгоритма расширения оснований в модулярном коде для гомоморфных шифров

Гомоморфное шифрование позволяет обрабатывать данные без их расшифровки в удаленном пространстве (таком как облачной системы обработки данных). Несмотря на то, что это одна из ключевых перспективных технологий защиты персональных данных пользователей в современном мире, она сталкивается с проблемой низкой производительности. Для повышения скорости обработки данных большинство основных систем гомоморфного шифрования используют модулярный код через систему остаточных классов (СОК) как арифметическую основу для высокопроизводительных вычислений. Среди сложных операций, необходимых для гомоморфных шифров, особое место занимает операция расширения системы оснований СОК. Наибольшую популярность имеет ранее предложенный подход к этой операции, основанный на вычислении приближенного ранга числа в СОК использований числа с плавающей запятой. Для оптимизации алгоритма расширения оснований СОК ранее были получены оценки точности, с которой необходимо выполнять вычисления приближенного ранга числа, причем авторы использовали классическую теорию погрешности, не учитывающую свойства модулярного кода. Мы предлагаем теоретическое исследование позволявшее оценить точность вычисления приближенного ранга числа. Доказанная теорема позволяет уменьшить длину операндов более, чем в 3 раза по сравнению с оценками других авторов. Результаты моделирования показывают, что ранее предложенная оптимизация алгоритма позволяет повысить скорость алгоритма масштабирования чисел в системе остаточных классов в среднем на 46.15%.

1. Brakerski Z. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. In Safavi-Naini R., Canetti R. (eds) Advances in Cryptology. CRYPTO 2012. CRYPTO 2012. Lecture Notes in Computer Science, vol. 7417, 2012, pp. 868-886. DOI: 10.1007/978-3-642-32009-5_50.

2. Fan J., Vercauteren F. Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, 2012. Available at: https://eprint.iacr.org/2012/144, accessed 05.11.2025.

3. Badawi A. Al, Polyakov Y., Kaung. M. M., Veeravalli B., Rohloff K. Implementation and performance evaluation of RNS variants of the BFV homomorphic encryption scheme. IEEE Transactions on Emerging Topics in Computing, 2019, vol. 9, no. 2, pp. 941-956. DOI: 10.1109/TETC.2019.2902799.

4. Halevi S., Polyakov Y., Shoup V. An improved RNS variant of the BFV homomorphic encryption scheme. In Matsui M. (eds) Topics in Cryptology. CT-RSA 2019. CT-RSA 2019. Lecture Notes in Computer Science, 2019, vol. 11405, pp 83-105. Springer, Cham. DOI: 10.1007/978-3-030-12612-4_5.

5. Geelen R., Vercauteren F. Bootstrapping for BGV and BFV Revisited. Journal of Cryptology, 2023, vol. 36, no. 2, pp. 12. DOI: 10.1007/s00145-023-09454-6.

6. Cheon J.H., Han K., Kim A., Kim M., Song Y. A full RNS variant of approximate homomorphic encryption. In: Cid, C., Jacobson Jr., M. (eds) Selected Areas in Cryptography – SAC 2018. SAC 2018. Lecture Notes in Computer Science, vol 11349, pp. 347-368. DOI: 10.1007/978-3-030-10970-7_16.

7. Brakerski Z., Vaikuntanathan V. Fully homomorphic encryption from ring-LWE and security for key dependent messages. In: Rogaway, P. (eds) Advances in Cryptology – CRYPTO 2011. CRYPTO 2011. Lecture Notes in Computer Science, vol 6841, pp. 505-524. DOI: 10.1007/978-3-642-22792-9_29.

8. Brakerski Z., Gentry C., Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT), vol. 6, no. 3. 2014, pp. 1-36. DOI: 10.1145/2633600.

9. Van Vu T. Efficient implementations of the Chinese remainder theorem for sign detection and residue decoding. IEEE Transactions on Computers. vol. 100, no. 7, 1985, pp. 646-651. DOI: 10.1109/TC.1985.1676602.

10. Chervyakov N., Babenko M., Tchernykh A., Kucherov N., Miranda-López V., Cortés-Mendoza J. M. AR-RRNS: Configurable reliable distributed data storage systems for Internet of Things to ensure security. Future Generation Computer Systems, vol. 92, 2019, pp. 1080-1092. DOI: 10.1016/j.future.2017.09.061.