Optimization of RNS Base Extension for Homomorphic Encryption Schemes

Optimization of RNS Base Extension for Homomorphic Encryption Schemes

Babenko M.G. (ISP RAS, Moscow, Russia; NCFU, Stavropol, Russia)
Sinitsyn A.A. (ISP RAS, Moscow, Russia)
Deryabin M.A. (SAIT, Suwon, Korea)

Abstract

Homomorphic encryption allows data to be processed without decrypting it in a remote space (such as a cloud data processing system). Despite the fact that it is one of the key promising technologies for protecting personal data of users in the modern world, it faces the problem of low productivity. To improve data processing speed, most major homomorphic encryption systems use modular code through a residue number system (RNS) as an arithmetic basis for high performance computing. Among the complex operations required for homomorphic ciphers, a special place is occupied by the operation of expanding the base system of the RNS. Most popular is the previously proposed approach to this operation, based on calculating the approximate rank of a number in the RNS of floating point uses. To optimize the algorithm for expanding the bases of the RNS, estimates of the accuracy with which it is necessary to calculate the approximate rank of the number were previously obtained, and the authors used the classical theory of error, which does not consider the properties of the modular code. We propose a theoretical study that made it possible to assess the accuracy of calculating the approximate rank of a number. The proven theorem allows you to reduce the length of operands by more than 3 times compared to estimates of other authors. The simulation results show that the previously proposed algorithm optimization can increase the speed of the number scaling algorithm in the residue number system by an average of 46.15%.

Keywords

residue number system; RNS base extension; Chinese Remainder Theorem; rank of a number; approximation of the rank of a number.

Edition

Proceedings of the Institute for System Programming, vol. 38, issue 3, part 1, 2026, pp. 33-44

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2026-38(3)-2

For citation

Babenko M.G., Sinitsyn A.A., Deryabin M.A. Optimization of RNS Base Extension for Homomorphic Encryption Schemes. Proceedings of the Institute for System Programming, vol. 38, issue 3, part 1, 2026, pp. 33-44 DOI: 10.15514/ISPRAS-2026-38(3)-2.

Full text of the paper in pdf (in Russian) Back to the contents of the volume