Полный текст

1.     Introduction

People have long been interested in the idea of hidden computing. The need to decrypt data for subsequent processing made it vulnerable. Now, with the introduction of public networks and the ability to process data on external, often public, resources, the task of performing hidden computations on encrypted data has become extremely relevant. To address this challenge, in the mid-20th century, the idea of homomorphic encryption was proposed, a method of transforming (encrypting) numerical data that allows operations to be performed on encrypted data without decryption [1, 2].

© 2026 Krouk, A. E.

                               This work is licensed under a Creative Commons “Attribution-NonCommercial 4.0 International” license.

First, so-called partially homomorphic encryption systems were developed. These systems typically allowed for one type of arithmetic operation without decryption. For example, the RSA and ElGamal systems [3] enable multiplication without decryption, while the Paillier and Benaloh systems enable addition.

For a long time, attempts to create a fully homomorphic encryption system or combine several partially homomorphic encryption systems into one have been unsuccessful. The turning point was the introduction of a system developed by Craig Gentry in 2009 [4]. The system is based on ideal lattices. Numerical noise is added to the data, making it impossible to decrypt without knowing the key. The system allows for any arithmetic operations without decrypting the data. As the number of operations increases, the noise level increases as well, but the system includes a procedure to reduce the noise level. This allows for an arbitrary number of operations without decrypting the data, but at the cost of increased computational complexity.

Development of homomorphic encryption systems has significantly expanded the possibilities for conducting calculations in cloud and collaborative systems [1, 5].

In 2010, a revised version of Gentry’s scheme based on integers was introduced [6]. Despite using a different mathematical foundation, this scheme employs Gentry’s method of encryption through the addition of noise and a noise reduction procedure. However, many fully homomorphic encryption systems are based on lattices [7].

Along with systems that perform precise arithmetic operations, usually on integers, systems that perform approximate arithmetic operations have begun to appear, which are applicable to performing operations on real numbers. In 2016, the CKKS system [8] was released, the first system that performs approximate calculations and is designed to work with real and complex numbers. In this system, data is first represented as circular polynomials, and then the problem of learning with errors in the ring is solved to create a homomorphic encryption system that has a public key for encrypting data. However, this system is designed to perform a finite number of operations, as increasing the number of operations increases the complexity of the calculations and negatively affects the system’s security. The re-encryption procedure proposed a little later [9] only partially solves the problem, as its use leads to an increase in the complexity of calculations, which does not allow it to be used too often [10]. A detailed comparison of the CKKS system [8, 11] with systems that perform exact calculations, such as the BFV system [12–14], is provided in [15]. It should also be noted that although the presence of a public key opens up additional possibilities for using the system, it is not necessary for solving certain problems and negatively affects the system’s security [16, 17].

This article presents several variants of approximate fully homomorphic encryption systems that use a fundamentally new approach to creating systems: representing numbers as polynomials and, additionally, replacing the represented polynomials with a set of their values at points. Although this approach does not allow for the use of a public key, it provides near-absolute security by using session-specific keys that are not transmitted outside of the trusted PC.

This method can be effectively used to process large amounts of data on external (unsecure) computing resources (so-called public cloud computing).

2. Usage of polynomials for construction of partially homomorphic

encryption system

Simple homomorphic encryption system can be built using residue number system based on Chinese Reminder Theorem (CRT) [18, 19].

This system can be further developed by replacement of residual number system with a polynomial representation. Let’s discuss this approach in more detail.

Let’s suppose that a sequence of arithmetic operations has to be performed on a set of numbers. We will encode the data for calculations in two stages:

1. We assign to each number a polynomial such that the value of this polynomial at some point 𝑥_𝑠 is equal to the number. The value of 𝑥_𝑠 is the same for all pairs of number-polynomial and is the secret key of the system.
2. We will choose a set of points. Values of polynomials in these points we will use to define these polynomials. (It is preferable to choose points where the polynomial values can be calculated relatively easily.) We will assign a set of values in the selected points to each polynomial. This set of values will be the result of the encoding process.

Let’s combine into sets the values of all selected polynomials at each of the points (each set consists of the values of all polynomials in one of the points). Now, to perform any sequence of arithmetic operations on the original numbers, it is enough to perform the same sequence of operations within each set. Indeed, since the result of adding (multiplying) two polynomials will be a polynomial whose values at any point will be the addition (multiplication) of the values of the polynomial terms (multipliers) at these points, the resulting values match the values of the polynomial that would result from performing the given sequence of arithmetic operations on the polynomials corresponding to the original data. Let us call this polynomial the result polynomial.

The degree of this result polynomial (𝑚) can be easily estimated by the degrees of the original polynomials. Indeed, when adding polynomials, the degree of the result can be estimated by the highest degree of the terms, and when multiplying, it can be estimated by the sum of the degrees of multipliers.

Thus, when we receive 𝑚 + 1 calculated values back, we can perform polynomial interpolation and obtain the result polynomial.

By calculating the value of the result polynomial in the secret point 𝑥_𝑠, we can find the final result of the calculation.

Let’s evaluate the advantages and disadvantages of the proposed method. This method retains both the many advantages of the original method (simplicity of calculations, ease of parallelization of calculations) and the main disadvantage (the absence of a division operation). At the same time, the presence of a two-step encoding operation and a secret key allows for high data security without the use of false requests or other additional techniques for data protection.

3.      Approximate calculations

Integer homomorphic encryption systems do not allow calculations with non-integer numbers. When working with real numbers, in particular when performing division, it is necessary to perform approximate calculations.

Approximate calculations are widely used, especially in technical and physical problems. This is because many data can only be measured with finite precision, and many elements can also be produced with finite precision. Increasing the precision of calculations leads to an excessive increase in the complexity [8, 20, 21]. In the same time there is no reason to increase the precision of calculations beyond the precision of measurements or production, as the precision of the final result is determined by the precision of the most inaccurate value.

When a computer works with real variables, it also limits the precision of the calculations, and these calculations are strictly speaking approximate.

4.       Representation of numbers as polynomials

Let’s improve the encoding procedure so that we can implement an approximate division procedure.

This time, we will encode the data in stages and evaluate the resulting system at each stage.

Let’s replace operations on numbers with operations on polynomials. To do this, we assign to each number a polynomial so that the value of this polynomial at some point 𝑥_𝑠 is equal to the number. The value of 𝑥_𝑠 must be the same for all pairs of number–polynomial and is the secret key of the system (we will call it the “secret point”).

In this representation, it is easy to implement addition and multiplication operations, but there are problems with implementing division. Indeed, in most cases, it is impossible to divide polynomials completely, meaning that there will be a remainder when dividing.

𝑓(𝑥) 𝑟(𝑥) = 𝑞(𝑥) + .

                                                                   𝑔(𝑥)                       𝑔(𝑥)

However, this problem can be resolved by considering division as an approximate operation and choosing 𝑥 to be sufficiently big. Indeed, since the degree of the remainder 𝑟(𝑥) is less than the degree of the divisor 𝑔(𝑥), the following formula holds

𝑟(𝑥)

⟶ 0.

𝑔(𝑥) 𝑥→∞

However, this imposes restrictions on the encoding procedure. In order to use this formula, it is necessary that 𝑥 be sufficiently big, meaning that the value (weight) of the leading term of the polynomial at the secret point would be significantly greater than the sum of the values of the other terms.

In addition, it is necessary to complicate the system somewhat in order to be able to divide polynomials in the case when the degree of the dividend is less than the degree of the divisor. We will use not polynomials to represent numbers, but constructions 𝑓(𝑥)/𝑥^𝑘, i.e. polynomials divided by the degree of 𝑥. In this representation, when performing the division operation, we get the opportunity to multiply and divide the dividend by 𝑥^𝑘 (division will be carried out after calculating the result of the main operation, by simply adding the corresponding degree of 𝑥 to the denominator) so that its degree exceeds the degree of the divisor. Choosing bigger values of 𝑘 allows to improve the operation precision. In addition, this method can be used to improve the precision of division even when the degree of the dividend is greater than the degree of the divisor.

5.    Homomorphic encryption system based on representation of numbers as polynomials

Let’s build a homomorphic encryption system that satisfies the principles described in the previous paragraph. We will calculate multiplication, addition, and subtraction in the traditional exact way, and division in an approximate way. To do this, we will assign to each number in our system a polynomial divided by the power of 𝑥 (𝑓(𝑥)/𝑥^𝑘) such that the values of the polynomials at a secret point (the secret point is the same for all polynomials) are equal to the encoded numbers, and replace operations on numbers with operations on the coefficients of the polynomials. It is impossible to restore the values of the numbers in the system without knowing the secret point. The absence of the need to transmit this secret value and the ability to choose a new secret value for each session ensure high security of the system.

Operations on polynomial coefficients are implemented as follows.

• An approximate operation. First, the degree of the dividend is increased by multiplying it by 𝑥^𝑘, and then division with remainder is performed. The incomplete quotient is used as the result of the division, and the remainder is neglected. Increasing the degree of 𝑥^𝑘 allows for greater precision in division, at the cost of increase in the complexity of the calculations and potentially the complexity of decryption. Finally, 𝑥^𝑘 is included in the weight factor (denominator) of the element.

For example, when dividing 𝑥 + 1 by 𝑥³, you can multiply and divide 𝑥 + 1 by 𝑥²

𝑥³ + 𝑥² 1 1 1 1 = (1 + )( ) = .

                                                            𝑥3       _𝑥2                   𝑥       _𝑥2          _𝑥2

If 𝑥⁵ is used instead of 𝑥², the result will be

𝑥6𝑥+3 𝑥5 𝑥15 = (𝑥3 + 𝑥2) 𝑥15 ,

this provides greater accuracy, as the polynomials are completely divided.

• Polynomials are multiplied classically, and the weight factors (denominators) 𝑥^𝑘 are also multiplied. For example:

(𝑥 + 1)𝑥⁻¹(𝑥 + 2)𝑥⁻² = (𝑥² + 3𝑥 + 2)𝑥⁻³.

• Addition and subtraction. To add and subtract elements, they should first be brought to a common weight factor (denominator) (will be 𝑥 with the highest absolute value of the degree), and then the polynomials are added or subtracted using the classical method. For example:

(𝑥 + 1)𝑥⁻¹ + (𝑥 + 2)𝑥⁻² = (𝑥² + 𝑥)𝑥⁻² + (𝑥 + 2)𝑥⁻² = (𝑥² + 2𝑥 + 2)𝑥⁻².

It is necessary to choose an encoding algorithm to implement the system within the restrictions described in the previous paragraph. That is, it is necessary to choose the value of the secret point to be sufficiently big, and the coefficients of the polynomials to be chosen so that the leading term of the polynomials is sufficiently heavy (that is, so that the leading term contains most of the value of the number; with 70% of the value, the error is approximately 10 times greater than with 90%). The following algorithm was used during the analysis of the system.

• The degree of the polynomial and the weight of the leading term as a percentage are selected. These are the parameters of the algorithm.
• The coefficient at the highest power is calculated so that the leading term has a value equal to the specified part of the encoded value.
• The next coefficient is chosen so that the value of the second term is equal to the specified part of the difference between the required value and the value of the leading term. And so on.
• The constant term is selected as the difference between the required value and the values of all other terms, ensuring that the required value is accurately matched.

Let’s consider the algorithm’s operation using the following example. Let’s encrypt the number 100 using a polynomial of the second degree at the point 10 with a weight of 80% for the leading term. – With the selected parameters, the value of the leading term should be 100 × 0.8 = 80. Since the degree of the polynomial is 2, the coefficient for the 𝑥² should be 80/10² = 0.8.

• The value of the second term should be (100 − 80) × 0.8 = 16. Since the degree of the second term is 1, the coefficient for the 𝑥 should be 16/10 = 1.6.
• Finally, the value of the constant term is obtained as 100 − 80 − 16 = 4.

Thus, the number 100 is associated with a polynomial 0.8𝑥² + 1.6𝑥 + 4.

When encoding using this algorithm, the weight factors 𝑥^−𝑘 of the polynomials obtained during the encoding phase are always assumed to be equal to 1 (𝑘 = 0). However, during the division operation, the weight factor may change and participate in further calculations.

Additional measures can be taken to improve security of the system:

• Variable polynomial degrees: the polynomials describing the different points must have different degrees, but at least 2.
• Variable weight of the leading term: the weight of the leading term for each polynomial (or even for each term in each polynomial) is chosen as a random number within a specified range that ensures acceptable precision, such as between 70% and 90%.

To decrypt, it is enough to calculate the value of the polynomial at the secret point (taking into account the weight coefficient 𝑥^−𝑘).

Let’s evaluate the advantages and disadvantages of the proposed system. The main advantages of this system are its completeness (it supports all four arithmetic operations) and its high security due to the use of one-time, non-transmittable secret keys. The main disadvantage of this system is its computational complexity, as it requires operations on sets of numbers instead of individual numbers, and it does not support easy parallelization of calculations, which is very convenient for external networks.

6.       Usage of interpolation for operations with polynomials

To increase the security of the system, as well as to facilitate parallel calculations, each polynomial can be represented as a set of values at points. After that, operations are performed not on the coefficients of the polynomial, but on these values. As the operations on the values at different points are independent of each other, they can be performed in parallel or, for example, as separate tasks for cloud computing (including in the public cloud, due to high security of the system).

There is no point in describing these arithmetic operations in detail, as they are literally operations on values (numbers) — addition, subtraction, multiplication, or division of values.

In principle, to speed up calculations, it is possible to use the values of polynomials at small points, but research has shown that this leads to a noticeable loss of division operation precision. However, this allows for the construction of an effective partially homomorphic encription system for three operations (addition, subtraction, and multiplication), with a high computational speed that can compete with modular arithmetic (such system was described above). At the same time, as long as the values used in the calculations (or a part of them) are comparable to the secret value, the precision of the operations is sufficient, allowing for the freedom to choose specific values or patterns for their generation. For example, to simplify calculations, values of the form 2^𝑘 can be used as long as at least one of them is greater than the secret value. Encoding process follows these steps:

• Encoding of values with polynomials (as described in the previous paragraph).
• Selecting of a set of points and calculating the values of the polynomials at those points.

The values of the points in the selected set are also a secret, and are also not transmitted anywhere, which contributes to the high security of the system. The number of points in the set is selected based on the estimation of the degree of the polynomial that should be obtained as a result of the calculations.

Decryption process follows these steps:

• Estimating of the 𝑥^−𝑘 weight coefficient on your own computing base (this is easy to do because all operations process it uniquely) and the degree of the resulting polynomial (to determine the number of points required for decryption)
• Calculating of the values of the polynomial at all points, taking into consideration the weight coefficient 𝑥^−𝑘 (that is, multiply the obtained values by 𝑥^𝑘).
• Restoring of the polynomial using the interpolation method.
• Calculating the value at the secret point (again, taking into consideration the 𝑥^−𝑘 weight coefficient).

To further improve security and reduce waiting times, an excessive set of points can be used

(decoding can be performed as soon as sufficient number of values is obtained). This reduces the impact of various delays that occur both on data-processing servers and during packet transition through the network (so-called transport coding) [22].

It should be noted that in order to improve the precision of the system, when evaluating the weight coefficient, it is possible to include a multiplication-division operation by a weight coefficient of a relatively high degree in division operation (as in description of division in the previous section),

which allows for a more precise division operation. Let’s refer to the degree of 𝑥 used for the multiplication-division operation as the correction and use it as a parameter for evaluating the precision of the operations. Using higher values of the correction can result in an increase in the degree of the final polynomial, which can lead to increase in complexity of the decryption process and number of points required for decryption.

When using the interpolation representation of polynomials, the coefficients of the polynomials and their degrees are hidden. This makes it unnecessary to use the additional security measures mentioned in the previous paragraph, as they can negatively impact precision. Moreover, using the interpolation representation allows for the selection of a specific structure of the polynomials to facilitate subsequent calculations, such as encoding numbers with monomials of a given degree (i.e., using 100% weight in the leading term) without compromising security.

Let’s evaluate the advantages and disadvantages of the proposed system. Usage of interpolation for polynomial operations further enhances the system’s security while reducing overall computational complexity by representing data as independent sets that can be processed in parallel.

7.     Results of experiments

The system was tested both with and without the interpolation representation of polynomials.

The system’s functionality was tested without the use of interpolation representation. Proposed methods for increasing the system’s security were also tested. As a result of these tests, the division precision sufficient for engineering calculations was proved. As this method is inferior to the interpolation representation, the purpose of these tests was to verify the feasibility of the idea, and multiple tests were not conducted to verify the precision.

Multiple tests were conducted for the interpolation representation. The interpolation point sets were selected according to the principle (𝑖 + 1) • 25, where 𝑖 = 0,1,..., as they allowed for more precise calculations, and 2^𝑖, as using this set allows for faster calculations. The secret point was not part of either set. The results were obtained for different values of the correction parameter (the correction parameter was introduced in the section describing the use of interpolation for polynomial operations) and different numbers of interpolation points.

 

Table 1 Single division error with leading monomial weight of 95%

             Correction                          Number of points                  Average error rate                   Maximum error

Selecting points based on the principle (𝑖 + 1) • 25

Table 2

Multiple operation (8 divisions, 7 multiplications, 2 additions) error with leading monomial weight of 95%

             Correction                          Number of points                  Average error rate                   Maximum error

Selecting points based on the principle (𝑖 + 1) • 25

During the tests, two important results were achieved. First, by using a weight of 95% for the leading term in the encoding algorithm, the division precision was achieved at the level of the PC’s precision in performing precise (addition and multiplication) arithmetic operations (due to the PC’s inaccuracy in handling real-number variables) for real numbers (with a maximum deviation of 10⁻¹⁴ and an average deviation of 10⁻¹⁵).

The results of the most interesting test runs are presented in Tables 1 and 2.

Secondly, a research was conducted on the growth of the error as a function of the number of operations performed. In this research, significantly less convenient encoding parameters were used, with the weight of the leading term for each point randomly selected between 80% and 90%. A large number of operations was achieved through consecutive divisions and multiplications (with one more division to ensure that the degree of the result polynomial was 0, before taking correction in consideration) of various randomly selected five-digit numbers. As a result, it was possible to find parameter values (albeit not optimal) under which the increase in error with increase in operations number is almost non-existent.

Examples of errors for such parameter values (with different numbers of operations) are given in Tables 3 and 4.

Table 3 Error for different number of consecutive operations

           Number of operations                               Average error rate                                         Maximum error

Encoding is used with a leading term weight of 80%–90%, and the values of the points (where the calculations are performed) are selected using the formula (𝑖 + 1) • 25. 11 points are used for correction of 8.

Table 4 Error for different number of consecutive operations

           Number of operations                               Average error rate                                         Maximum error

Encoding is used with a leading term weight of 80%–90%, and the values of the points (where the calculations are performed) are selected using the formula 2^𝑖. 14 points are used for correction of 12.

8.      System security evaluation

The system decryption is performed in two stages. Let’s try to assess the security of these stages.

1. At the first stage, a polynomial is determined based on the values. The main problem for unauthorized decryption at this stage is that the attacker does not have information about the degree of the polynomial (this information is calculated on the base computer and is not transmitted anywhere) and about the points where the polynomial values are calculated (these values are also not transmitted anywhere). The attacker may attempt to obtain some information by using points in the set that are close to the secret point, but he does not know which points in the set to use for evaluation, and the accuracy of the evaluation remains questionable.
2. In the second step, the value at the secret point is determined using the polynomials. To determine the value at the secret point, secret key is needed. This key is unique for each calculation and is not shared with anyone, so the attacker does not know its value. If there are several values in the result, the attacker can try to exploit the higher weight of the leading term and find the relationship between them by dividing one polynomial by another. The information obtained in this way depends on the specific polynomials used for the encoding. For example, if this attack is performed on a system used during research, the result will be inaccurate because the weight of the leading term is chosen with considerable random error during the encoding process.

9.      Conclusions

• The paper proposes a method of approximate homomorphic encription that provides sufficient precision for engineering calculations. The conducted research allows to hope for the existence of encoding algorithms that ensure the precision of the system’s operation at the precision level of PC operations with real numbers.
• The high security of the method and the ease of dividing calculations into parallel processes make it suitable for use in public cloud networks.
• The ability to increase the number of points and the division operation parameters allows to adjust the precision and speed of calculations.
• The conducted research shows that there are system parameters under which the errors of multiple operations do not accumulate significantly.

Об авторах

А. Е. Крук

Санкт-Петербургский государственный университет аэрокосмического приборостроения

Автор, ответственный за переписку.
Email: svinenka@mail.ru
ORCID iD: 0009-0008-1162-2020

Candidate of Technical Sciences, Associate Professor

ул. Б. Морская, д. 67, Санкт-Петербург, 190000, Российская Федерация

Список литературы

Дополнительные файлы