Encryption method and apparatus based on homomorphic encryption using composition of functions

An encryption method and apparatus based on homomorphic encryption using a composition of functions. The encryption method includes generating a ciphertext by encrypting data, and bootstrapping the ciphertext by performing a modular reduction based on a composition of a function for a modulus corresponding to the ciphertext.

BACKGROUND

The following description relates to an encryption method and apparatus based on homomorphic encryption using a composition of functions.

2. Description of Related Art

Fully homomorphic encryption is an encryption scheme that enables an arbitrary logical operation or a mathematical operation to be performed on encrypted data. A fully homomorphic encryption method maintains security in data processing.

However, the conventional encryption method is difficult to process encrypted data and thus, inadequate for protecting customer privacy.

Fully homomorphic encryption enables customers to receive many services while preserving privacy.

SUMMARY

In one general aspect, an encryption method using homomorphic encryption includes generating a ciphertext by encrypting data, and bootstrapping the ciphertext by performing a modular reduction based on a composition of a function for a modulus corresponding to the ciphertext.

The bootstrapping may include bootstrapping the ciphertext by approximating the modular reduction based on the function and an inverse function of the function.

The bootstrapping of the ciphertext by approximating the modular reduction based on the function and the inverse function of the function may include obtaining an approximate polynomial of the function, obtaining an approximate polynomial of the inverse function, and generating a composite function that approximates the modular reduction based on a composite function of the approximate polynomial of the function and the approximate polynomial of the inverse function.

The function may include a trigonometric function.

The obtaining of the approximate polynomial of the function may include obtaining, in response to the function being a trigonometric function, a double-angle function of the trigonometric function by applying the double-angle formula to the trigonometric function.

The obtaining of the approximate polynomial of the function may include determining one or more reference points based on a degree of the approximate polynomial, obtaining an arbitrary polynomial based on the one or more reference points, and generating the approximate polynomial of the function based on one or more extreme points selected from the arbitrary polynomial.

The obtaining of the arbitrary polynomial may include obtaining a piecewise continuous function that passes through the one or more reference points, and obtaining the arbitrary polynomial, by generating a polynomial such that absolute values of errors between the polynomial and the piecewise continuous function at the one or more reference points are a specific value.

The obtaining of the arbitrary polynomial by generating the polynomial may include obtaining the arbitrary polynomial, by generating a polynomial such that a first error at a first reference point included in the one or more reference points and a second error at a second reference point adjacent to the first reference point are different in sign, and absolute values of the first and second errors are the specific value.

The generating of the approximate polynomial based on the one or more extreme points selected from the arbitrary polynomial may include obtaining candidate points whose absolute values are greater than or equal to a predetermined value among extreme points of errors between the arbitrary polynomial and a piecewise continuous function that passes through the one or more reference points, selecting target points from among the candidate points, where the number of target points is based on the degree of the approximate polynomial, and generating the approximate polynomial based on the target points.

In another general aspect, an encryption apparatus using homomorphic encryption includes a processor configured to generate a ciphertext by encrypting data, and bootstrap the ciphertext by performing a modular reduction based on a composition of a function for a modulus corresponding to the ciphertext, and a memory configured to store instructions to be executed by the processor.

The processor may be configured to bootstrap the ciphertext by approximating the modular reduction based on the function and an inverse function of the function.

The processor may be configured to obtain an approximate polynomial of the function, obtain an approximate polynomial of the inverse function, and generate a composite function that approximates the modular reduction based on a composite function of the approximate polynomial of the function and the approximate polynomial of the inverse function.

The function may include a trigonometric function.

The processor may be configured to obtain, in response to the function being a trigonometric function, a double-angle function of the trigonometric function by applying the double-angle formula to the trigonometric function.

The processor may be configured to determine one or more reference points based on a degree of the approximate polynomial, obtain an arbitrary polynomial based on the one or more reference points, and generate the approximate polynomial of the function based on one or more extreme points selected from the arbitrary polynomial.

The processor may be configured to obtain a piecewise continuous function that passes through the one or more reference points, and obtain the arbitrary polynomial, by generating a polynomial such that absolute values of errors between the polynomial and the piecewise continuous function at the one or more reference points are a specific value.

The processor may be configured to obtain the arbitrary polynomial, by generating a polynomial such that a first error at a first reference point included in the one or more reference points and a second error at a second reference point adjacent to the first reference point are different in sign, and absolute values of the first and second errors are the specific value.

The processor may be configured to obtain candidate points whose absolute values are greater than or equal to a predetermined value among extreme points of errors between the arbitrary polynomial and a piecewise continuous function that passes through the one or more reference points, select target points from among the candidate points, where the number of target points is based on the degree of the approximate polynomial, and generate the approximate polynomial based on the target points.

DETAILED DESCRIPTION

Hereinafter, examples will be described in detail with reference to the accompanying drawings. However, various alterations and modifications may be made to the examples. Here, the examples are not construed as limited to the disclosure. The examples should be understood to include all changes, equivalents, and replacements within the idea and the technical scope of the disclosure.

When describing the examples with reference to the accompanying drawings, like reference numerals refer to like constituent elements and a repeated description related thereto will be omitted. In the description of examples, detailed description of well-known related structures or functions will be omitted when it is deemed that such description will cause ambiguous interpretation of the present disclosure.

Also, in the description of the components, terms such as first, second, A, B, (a), (b) or the like may be used herein when describing components of the present disclosure. These terms are used only for the purpose of discriminating one constituent element from another constituent element, and the nature, the sequences, or the orders of the constituent elements are not limited by the terms. When one constituent element is described as being “connected”, “coupled”, or “attached” to another constituent element, it should be understood that one constituent element can be connected or attached directly to another constituent element, and an intervening constituent element can also be “connected”, “coupled”, or “attached” to the constituent elements.

The same name may be used to describe an element included in the examples described above and an element having a common function. Unless otherwise mentioned, the descriptions on the examples may be applicable to the following examples and thus, duplicated descriptions will be omitted for conciseness.

FIG.1illustrates an example of an encryption apparatus.

Referring toFIG.1, an encryption apparatus10may encrypt data. The encryption apparatus10may generate encrypted data through encryption of data. Hereinafter, the encrypted data may be referred to as a ciphertext.

The encryption apparatus10may perform encryption and decryption using homomorphic encryption. The encryption apparatus10may provide an encryption technique for performing an operation on data encrypted using homomorphic encryption without decryption. For example, the encryption apparatus10may decrypt a result of operating data encrypted using homomorphic encryption, thereby deriving the same result as an operation on data of a plain text. The encryption apparatus10may provide homomorphic encryption operations for real or complex numbers.

The encryption apparatus10may perform bootstrapping required for homomorphic encryption. The encryption apparatus10may generate an approximate polynomial that approximates a function corresponding to a modular reduction required for homomorphic encryption.

The encryption apparatus10may find a minimax approximation error for each degree of an optimal minimax approximate polynomial.

The encryption apparatus10may find an approximate polynomial that optimally approximates a modular reduction operation, thereby providing excellent performance in terms of the minimax approximation error of homomorphic encryption.

The encryption apparatus10may generate an approximate polynomial that approximates the modular reduction function based on approximation region information for approximating the modular reduction function. The encryption apparatus10may perform modular reduction based on a composition of a function. The encryption apparatus10may perform bootstrapping by performing modular reduction based on the composition of the function.

The encryption apparatus10includes a processor100and a memory200.

The processor100may process data stored in the memory. The processor100may execute a computer-readable code (for example, software) stored in the memory200and instructions triggered by the processor100.

The “processor100” may be a data processing device implemented by hardware including a circuit having a physical structure to perform desired operations. For example, the desired operations may include instructions or codes included in a program.

For example, the hardware-implemented data processing device may include a microprocessor, a central processing unit (CPU), a processor core, a multi-core processor, a multiprocessor, an application-specific integrated circuit (ASIC), and a field-programmable gate array (FPGA).

The processor100may generate a ciphertext by encrypting data. The data may be information in the form of characters, numbers, sounds, or pictures that may be processed by a computer.

The processor100may bootstrap the ciphertext by performing a modular reduction based on a composition of a function for a modulus corresponding to the generated ciphertext.

The processor100may perform bootstrapping by approximating the modular reduction based on the function and an inverse function of the function. The processor100may obtain an approximate polynomial of the function. The processor100may obtain an approximate polynomial of the inverse function.

The processor100may determine one or more reference points based on a degree of the approximate polynomial. The processor100may obtain an arbitrary polynomial based on the one or more reference points. The processor100may obtain a piecewise continuous function that passes through the one or more reference points. The processor100may obtain the arbitrary polynomial, by generating a polynomial such that absolute values of errors between the polynomial and the piecewise continuous function at the one or more reference points are a predetermined value.

The processor100may obtain the arbitrary polynomial, by generating a polynomial such that an error at a first reference point included in the one or more reference points and an error at a second reference point adjacent to the first reference point are different in sign, and absolute values of the errors are the predetermined value.

The processor100may generate the approximate polynomial based on one or more extreme points selected from the arbitrary polynomial. The processor100may obtain candidate points whose absolute values are greater than or equal to a predetermined value among extreme points of errors between the arbitrary polynomial and the piecewise continuous function that passes through the one or more reference points.

The processor100may select target points from among the candidate points, where the number of target points is based on the degree of the approximate polynomial. The processor100may generate the approximate polynomial based on the target points.

The processor100may obtain an approximate polynomial of at least one of the function and the inverse function thereof, and perform modular reduction by performing a composition of a function based on the obtained approximate polynomial. The process of obtaining the approximate polynomials of the function and the inverse function thereof will be described in detail with reference toFIGS.3and4.

The processor100may generate a composite function that approximates the modular reduction based on a composite function of the approximate polynomial of the function and the approximate polynomial of the inverse function. In this case, the function may include a trigonometric function. For example, the trigonometric function may include at least one of a sine function and a cosine function.

In response to the function being a trigonometric function, the processor100may obtain a double-angle function of the trigonometric function by applying the double-angle formula to the trigonometric function.

The memory200may store instructions (or programs) executable by the processor. For example, the instructions may include instructions to perform an operation of the processor and/or an operation of each element of the processor.

The memory200may be implemented as a volatile memory device or a non-volatile memory device.

The volatile memory device may be implemented as a dynamic random access memory (DRAM), a static random access memory (SRAM), a thyristor RAM (T-RAM), a zero capacitor RAM (Z-RAM), or a Twin Transistor RAM (TTRAM).

The non-volatile memory device may be implemented as an electrically erasable programmable read-only memory (EEPROM), a flash memory, a magnetic RAM (MRAM), a spin-transfer torque (STT)-MRAM, a conductive bridging RAM (CBRAM), a ferroelectric RAM (FeRAM), a phase change RAM (PRAM), a resistive RAM (RRAM), a nanotube RRAM, a polymer RAM (PoRAM), a nano floating gate Memory (NFGM), a holographic memory, a molecular electronic memory device), or an insulator resistance change memory.

FIG.2illustrates an example of obtaining an approximation function by the encryption apparatus ofFIG.1.

Referring toFIG.2, the processor100may perform bootstrapping by approximating a modular reduction function. In operation210, the processor100may detect a ciphertext that requires a modulus operation (for example, a modulus reduction operation) during the bootstrapping process. For example, the processor100may detect a ciphertext on which an operation cannot be performed any further due to its modulus being less than or equal to a threshold point.

The processor100may approximate a modular reduction function to perform bootstrapping. The processor100may obtain an approximate polynomial of an arbitrary function and obtain an approximate polynomial of an inverse function. For example, the arbitrary function may include a trigonometric function.

The example ofFIG.2shows a case in which the arbitrary function is a sine function. However, the modular reduction function may be approximated in the same manner, even if the arbitrary function is a cosine function.

The processor100may generate a composite function that approximates the modular reduction based on a composite function of the approximate polynomial of the function and the approximate polynomial of the inverse function. The processor100may approximate a modular reduction function through a composition of polynomials with relatively low degree.

For example, in operation230, the processor100may obtain an approximate polynomial f(t) for sin(t). In operation250, the processor100may obtain an approximate polynomial g(t) for arcsin(t). The process of obtaining the approximate polynomials will be described in detail with reference toFIGS.3and4.

In operation270, the processor100may obtain g f(t) by composing the obtained g(t) and f(t). In operation290, the processor100may approximate a modulus function (for example, a modular reduction function) based on a composite function.

The processor100may approximate the modulus function with a composite function of a trigonometric function and an inverse trigonometric function, thereby reducing errors compared to approximating the modulus function using only a trigonometric function.

The processor100uses the modular reduction function based on the composition of the approximate polynomials of the function and the inverse function thereof, thereby reducing fundamental errors caused by an approximation using only a trigonometric function. The processor100may reduce the number of nonscalar multiplications by applying the double-angle formula of a trigonometric function. Through the composition of the function and the inverse function thereof, the processor100may reduce the number of operations for the approximation function.

If a function f is a sine function and a function g is an arcsine function, the two functions may be defined as in Equations 1 and 2.

Here, ∈ may be in the range of 0<∈<¼.

A composite function for the functions of Equations 1 and 2 may be expressed by Equation 3.

Here, when substituting

t=x2⁢π,
the composite function may be expressed by Equation 4.

Here, normod(t) denotes a normalized modular reduction function. Referring to Equations 1 to 4, the processor100may approximate the functions f and g through approximate polynomials and compose the functions, thereby reducing errors in the modular reduction function.

The processor100may approximate g(x) with a linear polynomial even for relatively small ∈. For example, the processor100may approximate g(x) with x, that is, an identity function.

Further, a cosine function is a parallel shift of the sine function. Thus, the processor100may perform the same composition of functions for the cosine function as well.

If the arbitrary function is an odd function, an approximate polynomial thereof may also be an odd function. That is, if the inverse function is an arcsine function, an approximate polynomial of the arcsine function may be an odd function.

Thus, since the approximate polynomial of the arcsine function among the polynomials of degree less than or equal to two is a linear polynomial, error function between the approximate polynomial and the arcsine function may have four global extreme points that satisfy the Chebyshev alternating theorem.

The processor100may obtain a minimax approximate polynomial cminin for the arcsine function in an interval [−sin ∈, sin ∈], as expressed by Equation 5.

In addition, the relationship in Equation 6 may be satisfied.

In this example, the domain of all functions may be [−sin ∈, sin ∈].

If ƒ(x)=sin x and

g⁡(x)≈(1+π22⁢ϵ2)⁢x,⁢
the normalized modular reduction function in Equation 4 may be evaluated as in Equation 7.

Here, the minimax linear polynomial of g(x) may be

g0⁡(x)=(1+π22⁢ϵ2)⁢x.
This is just a multiplication of a constant

1+π22⁢ϵ2
at the original approximation formula. Thus, the processor100may reduce the fundamental limitation of the approximation error for the cosine approximation by ¼.

Through this, the processor100may obtain 2 more-bit precision by only adjusting the multiplicative factor.

Equations 5 to 7 describe a case in which the degree of the approximate polynomial of the inverse function is one, and the processor100may approximate the degree of the approximate polynomial of the inverse function to 2 or higher, thereby further reducing the minimax error.

The processor100may perform approximation by increasing the degree of the approximate polynomial to 3, as expressed by Equation 8.
g(x)≈c1x+c3x3=g1(x)  [Equation 8]

Here, the process of obtaining coefficients c1and c3of the polynomial will be described with reference toFIG.3. By applying Equation 8 to Equation 4, a normalized modular reduction function as shown in Equation 9 may be obtained.

To approximate the modular reduction function, the processor100may approximate the sine or cosine function with a minimax approximate polynomial, and then approximate of Equation 8. The processor100may apply the double-angle formula for the approximation of the sine or cosine function.

The application of the double-angle formula requires two more nonscalar multiplications and two more depths after the sine or cosine function is approximated. Through the double-angle formula, the minimax approximation error for the normalized modular reduction function may have a value between δ0, which is the approximation flat error when the degree of the approximate polynomial of the inverse function is 1 and δ1, which is the minimax approximation error when the modular reduction function is approximated using Equation 8.

If gn(x) denotes the optimal minimax approximate polynomial of degree 2n+1 for g(x), gn(x) may have only odd degree terms. Hereinafter, δnmay be the minimax approximation error of gn(x).

To obtain the minimax approximation error between δnand δn+1, the processor100may obtain a normalized modular reduction function expressed by Equation 10.

Here, δnmay go to zero as n increases. The processor100may reduce the approximation error through the composition of approximation functions of a trigonometric function and an inverse trigonometric function.

Hereinafter, the process of obtaining the approximate polynomials of the function and the inverse function thereof will be described in detail with reference toFIGS.3and4.

FIG.3illustrates an example of an algorithm for obtaining an approximate polynomial for a function and an inverse function thereof by the encryption apparatus ofFIG.1.

Referring toFIG.3, the processor100may obtain an approximate polynomial of a function and/or an approximate polynomial of an inverse function of the function. The processor100may obtain the approximate polynomial of the function and/or the approximate polynomial of the inverse function thereof by using Algorithm 1 ofFIG.3.

The processor100may obtain an approximate polynomial of at least one of the function and the inverse function thereof. The approximate polynomial of the function and the approximate polynomial of the inverse function thereof may be obtained through the same process.

The processor100may generate an approximate polynomial by finding a minimax approximate polynomial for any continuous function on an interval [a, b] using Algorithm 1 ofFIG.3. The processor100may use Chebyshev alternation theorem to generate an approximate polynomial satisfying equioscillation condition.

The processor100may determine one or more reference points based on the degree d of an approximate polynomial to be obtained. The processor100may initialize the set of reference points that are converged to the extreme points of the minimax approximate polynomial. The processor100may obtain the minimax approximate polynomial in regard to the set of reference points. Since the set of reference points is the set of finite points in [a, b], it may be a closed subset of [a, b], and thus Chebyshev alternation theorem may be satisfied for the set of reference points.

The processor100may obtain an arbitrary polynomial based on the one or more reference points. The processor100may obtain a piecewise continuous function that passes through the one or more reference points. The processor100may obtain the arbitrary polynomial, by generating a polynomial such that absolute values of errors between the polynomial and the piecewise continuous function at the one or more reference points are a predetermined value.

The processor100may obtain the arbitrary polynomial, by generating a polynomial such that an error at a first reference point included in the one or more reference points and an error at a second reference point adjacent to the first reference point are different in sign, and absolute values of the errors are the predetermined value.

ƒ(x) may be the piecewise continuous function that passes through the one or more reference points. When ƒ(x) is a continuous function on [a, b], the minimax approximate polynomial on the set of reference points may be a generalized polynomial p(x) with the basis {g1, . . . , gn} satisfying the condition of Equation 11 for some E. The value of E may be the predetermined value described above.
p(xi)−ƒ(xi)=(−1)iE i=1, . . . ,d+2  [Equation 11]

The processor100may obtain an arbitrary polynomial p(x) using Equation 11. According to Equation 11, a system of linear equations having n+1 equations and n+1 variables of n coefficients of p(x) and E, and the linear equations are not singular by the Haar condition, and thus the processor100may obtain the polynomial p(x) satisfying the condition of Equation 11.

The processor100may generate the approximate polynomial based on one or more extreme points selected from the arbitrary polynomial. In detail, the processor100may obtain candidate points whose absolute values are greater than or equal to a predetermined value among extreme points of errors between the arbitrary polynomial and the piecewise continuous function that passes through the one or more reference points. The processor100may select target points from among the candidate points, where the number of target points is based on the degree of the approximate polynomial. The processor100may generate the approximate polynomial based on the selected target points.

The processor100may select the minimum point of p(x)−ƒ(x) in [zi−1, zi] if p(xi)−ƒ(xi)<0, and select the maximum point of p(x)−ƒ(x) in [zi−1, zi] if p(xi)−ƒ(xi)>0.

Through this, the processor100may select a new set of extreme points y1, . . . , yn+1as candidate points. If these candidate points satisfy equioscillation condition, the processor100may generate an approximate polynomial of a function or an inverse function thereof by returning a minimax approximate polynomial from the Chebyshev alternation theorem.

Further, the processor100may replace a set of reference points with the new set of extreme points y1, . . . , yn+1obtained through the above process, and iteratively perform the polynomial generating process described above.

Algorithm 1 shown inFIG.3may be extended to the multiple sub-intervals of an interval. When Algorithm 1 extended to the multiple sub-intervals is applied, steps3and4ofFIG.3may be changed.

For each iteration, the processor100may obtain all local extreme points of an error function p−f whose absolute error values may be larger than the absolute error values at the current reference points.

Then, the processor100may select, from among all of the obtained local extreme points, n+1 new extreme points satisfying the following two criteria:

1. The error values alternate in sign; and

2. A new set of extreme points includes the global extreme point.

The above two criteria may ensure the convergence to the minimax generalized polynomial.

FIG.4illustrates an example of an algorithm for obtaining an approximate polynomial for a function and an inverse function thereof by the encryption apparatus ofFIG.1.

Referring toFIG.4, the processor100may obtain an approximate polynomial of a function and/or an approximate polynomial of an inverse function of the function by using Algorithm 2.

The function to be obtained through approximation by the processor100may be a normalized modular reduction function defined in only near finitely many integers as expressed by Equation 12.

Equation 12 may express the modular reduction function scaled for both its domain and range.

The processor100may use the cosine function to approximate normod(x) to use double-angle formula for efficient homomorphic evaluation.

If the double-angle formula is used l times, the cosine function in Equation 13 may need to be approximated.

To approximate the piecewise continuous functions including the functions of Equations 12 and 13, the processor100may assume a general piecewise continuous function defined on a union of finitely many closed intervals, which is given as Equation 14.

To approximate a given piecewise continuous function with a polynomial having a degree less than or equal to d on D of Equation 14, the processor100may set a criterion for selecting new d+2 reference points from among multiple extreme points.

The processor100may generate an approximate polynomial by using {g1, . . . , gn} satisfying the Haar condition on [a, b] as the basis of polynomial. The processor100may obtain the minimax approximate polynomial in regard to the set of reference points for each iteration, and select a new set of reference points for next iteration.

There may be many cases where the processor100selects n+1 points from among extreme points of an error function evaluated using the arbitrary polynomial obtained using the set of reference points. The processor100may consider many intervals during the encryption process, and thus there may be lots of candidate extreme points.

The processor100may select n+1 target points from among many candidate points for each iteration to minimize the number of iterations. Through this, the processor100may generate the minimax approximate polynomial by converging the approximate polynomial generated for each iteration. In this example, the finally generated minimax approximate polynomial may be the approximate polynomial of the function and/or the approximate polynomial of the inverse function thereof described above.

In order to set the criterion for selecting n+1 target points, the processor100may define the function of Equation 15.

Here, denotes an arbitrary polynomial obtained in each iteration, and ƒ(x) denotes a piecewise continuous function to be approximated. For convenience, μp,ƒmay be hereinafter referred to as μ.

The processor100may obtain all extreme points of p(x)−ƒ(x) into a set B. B may be a finite set and expressed as B={x1, x2, . . . , xm}. The processor100may select a point in an interval in B.

Assuming that B is ordered in increasing order, x1<x2< . . . <xm, then the values of μ may be 1 or −1. The number of extreme points may satisfy m≥n+1.

The processor100may define a set of functions S as expressed by Equation 16.
S={σ:[n+1]→[m]|σ(i+1) for alli=1, . . . ,n}[Equation 16]

In this example, the set S may include only the identity function if n+1=m.

The processor100may set three criteria for selecting n+1 extreme points.

The processor100may set a local extreme value condition as the first condition. If E is the absolute error at the set reference points, the condition of Equation 17 may be set.

To satisfy the local extreme value condition, the processor100may remove the extreme points if the local maximum value of p(x)−ƒ(x) is negative or the local minimum value of p(x)−ƒ(x) is positive.

Secondly, the processor100may set an alternating condition. In other words, the condition of Equation 18 may be set. In detail, if one of two adjacent extreme points has a local maximum value, the other extreme point may have a local minimum value.
μ(xσ(i)·μ(xσ(i+1))=−1 fori=1, . . . ,n.[Equation 18]

Thirdly, the processor100may set a maximum absolute sum condition. The processor100may select σ maximizing the value of Equation 19 from among σ satisfying the local extreme value condition and the alternating condition.

The absolute error value at current reference points x1, . . . , xn+1may be less than the minimax approximation error, and converge to the minimax approximation error as the number of iterations increases.

Further, the absolute error value at the current reference points may be a weighted average of the absolute error values of the approximate polynomial in the previous iteration at x1, . . . , xn+1.

The processor100may help for the absolute error value at the current reference points to converge to the minimax approximation error fast, using the maximum absolute sum condition.

The local extreme value condition and the alternating condition may be applied to both the algorithms ofFIGS.3and4(Algorithm 1 and Algorithm 2), and the maximum absolute sum condition may be applied to Algorithm 2 ofFIG.4. The processor100may apply the maximum absolute sum condition, thereby expediting the convergence to the minimax approximate polynomial.

The set S always contains at least one element σ0that satisfies the local extreme value condition and the alternating condition, and may have σ0(i0) satisfying |p(xσ0(i0))−ƒ(xσ0(i0)|=∥p−ƒ∥∞for some i0.

The processor100may more efficiently perform steps2,3, and4of Algorithm 2 ofFIG.4as follows. The processor100may find coefficients of the approximate polynomial with a power basis at the current reference points for the continuous function ƒ(x).

That is, the processor100may generate an approximate polynomial by obtaining the values of the coefficient cjin Equation 20.

Here, E may be an unknown in a linear equation. As the degree of basis of an approximate polynomial increases, the coefficients may decrease. The processor100may need to set a higher precision for the coefficients of a higher degree basis.

Thus, the processor100may effectively solve the precision problem by using the basis of Chebyshev polynomials as the basis of the approximate polynomial. Since the coefficients of a polynomial with the Chebyshev basis usually have almost the same order, the processor100may generate the approximate polynomial using the Chebyshev basis instead of the power basis.

The Chebyshev polynomials satisfy the Haar condition described above, and the processor100may obtain the approximate polynomial by calculating and cjby solving the system of d+2 linear equations of Equation 21 using d+2 reference points.

FIG.5illustrates an example of an operation of the encryption apparatus ofFIG.1.

Referring toFIG.5, in operation510, the processor100may generate a ciphertext by encrypting data. In operation530, the processor100may bootstrap the ciphertext by performing a modular reduction based on a composition of a function for a modulus corresponding to the ciphertext. In this case, the function may include a trigonometric function.

The processor100may perform bootstrapping by approximating the modular reduction based on the function and an inverse function of the function. The processor100may obtain an approximate polynomial of the function and obtain an approximate polynomial of the inverse function.

The processor100may determine one or more reference points based on a degree of the approximate polynomial, and obtain an arbitrary polynomial based on the one or more reference points.

The processor100may obtain a piecewise continuous function that passes through the one or more reference points, and obtain the arbitrary polynomial, by generating a polynomial such that absolute values of errors between the polynomial and the piecewise continuous function at the one or more reference points are a predetermined value.

The processor100may obtain the arbitrary polynomial, by generating a polynomial such that an error at a first reference point included in the one or more reference points and an error at a second reference point adjacent to the first reference point are different in sign, and absolute values of the errors are the predetermined value.

The processor100may generate the approximate polynomial based on one or more extreme points selected from the arbitrary polynomial. The processor100may obtain candidate points whose absolute values are greater than or equal to a predetermined value among extreme points of errors between the arbitrary polynomial and the piecewise continuous function that passes through the one or more reference points, and select target points from among the candidate points, where the number of target points is based on the degree of the approximate polynomial.

The processor100may generate the approximate polynomial of the function or the inverse function thereof based on the selected target points.

The processor100may generate a composite function that approximates the modular reduction based on a composite function of the approximate polynomial of the function and the approximate polynomial of the inverse function. In this example, in response to the function being a trigonometric function, the processor100may obtain a double-angle function of the trigonometric function by applying the double-angle formula to the trigonometric function.

A number of examples have been described above. Nevertheless, it should be understood that various modifications may be made to these examples. For example, suitable results may be achieved if the described techniques are performed in a different order and/or if components in a described system, architecture, device, or circuit are combined in a different manner and/or replaced or supplemented by other components or their equivalents.