Patent Description:
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, in the conventional encryption method, it 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. <NPL>, relates to a polynomial approximation of a modulus reduction as the most difficult part of the bootstrapping for the Chean-Kim-Kim-Song homomorphic encryption scheme for complex numbers. The problem of finding an approximate polynomial for a modulus reduction is cast into an L2- norm minimization problem. As a result, an approximate polynomial is found for the modulus reduction without using the sine function, which is the upper bound for the approximation of the modulus reduction. With the proposed method, the degree of the polynomial required for an approximate modulus reduction can be reduced, while also reducing the error. The solution of the cast problem is determined in an efficient manner without iteration. <NPL> relates to a cloud service scenario to provide private predictive analyses on encrypted medical data utilizing homomorphic encryption (HE) scheme. A new efficient approach to provide the service is presented using minimax approximation and Non-Adjacent Form (NAF) encoding. With the method, it is possible to remove the limitation of input range and reduce maximum errors, allowing faster analyses than the previous work. Moreover, it is proven that the NAF encoding allows to use more efficient parameters than the binary encoding used in the previous work or balanced base-B encoding. For comparison with the previous work, implementation results using HElib are presented. <NPL>, relates to a comparison of two numbers. This is one of the most frequently used operations, but it has been a challenging task to efficiently compute the comparison function in homomorphic encryption (HE) which basically support addition and multiplication. A new comparison method is proposed with optimal asymptotic complexity based on composite polynomial approximation. The main idea is to systematically design a constant-degree polynomial f by identifying the core properties to make a composite polynomial f ∘ f ∘. ∘ f get close to the sign function (equivalent to the comparison function) as the number of compositions increases. <NPL>, relates to some new methods for obtaining the minimax polynomial approximation of degree n to a continuous function are introduced, and applied to several simple functions. The amount of computation required is substantially reduced compared with that of previous methods.

The invention is provided as defined in the independent claims.

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 selection of one or more target points for a modulus corresponding to the ciphertext.

The bootstrapping may include bootstrapping the ciphertext by approximating a function corresponding to the modular reduction.

The bootstrapping of the ciphertext by approximating the function corresponding to the modular reduction may include generating a target approximate polynomial that approximates the function corresponding to the modular reduction.

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

The determining may include determining a piecewise continuous function that passes through the one or more reference points, and determining 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 determining of the arbitrary polynomial by generating the polynomial may include determining 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 generating of the target approximate polynomial based on the one or more extreme points selected from the arbitrary polynomial may include determining 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 target approximate polynomial, and generating the target approximate polynomial based on the target points.

The selecting of the target points may include selecting the target points from among the candidate points such that a maximum and a minimum appear in alternation.

The selecting of the target points may include selecting the target points such that the sum of the absolute values of the errors is maximized.

The generating of the target approximate polynomial based on the one or more extreme points selected from the arbitrary polynomial may include generating, as the target approximate polynomial, a polynomial for a case where a relative error between a maximum value and a minimum value among the absolute values of the one or more extreme points is less than a threshold.

A basis of the target approximate polynomial may be the basis of the Chebyshev polynomials.

A non-transitory computer-readable storage medium may store instructions that, when executed by one or more processors, configure the one or more processors to perform the method above.

In another general aspect, an encryption apparatus using homomorphic encryption includes one or more processors configured to generate a ciphertext by encrypting data, and bootstrap the ciphertext by performing a modular reduction based on a selection of one or more target points for a modulus corresponding to the ciphertext.

The encryption apparatus may further include a memory configured to store instructions. The one or more processors may be further configured to execute the instructions to configure the one or more processors to: generate the ciphertext by encrypting data, and bootstrap the ciphertext by performing the modular reduction based on the selection of the one or more target points for the modulus corresponding to the ciphertext.

The one or more processors may be configured to bootstrap the ciphertext by approximating a function corresponding to the modular reduction.

The one or more processors may be configured to generate a target approximate polynomial that approximates the function corresponding to the modular reduction.

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

The one or more processors may be configured to determine a piecewise continuous function that passes through the one or more reference points, and determine 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 one or more processors may be configured to determine 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 one or more processors may be configured to determine 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 target approximate polynomial, and generate the target approximate polynomial based on the target points.

The one or more processors may be configured to select the target points from among the candidate points such that a maximum and a minimum appear in alternation.

The one or more processors may be configured to select the target points such that the sum of the absolute values of the errors is maximized.

The one or more processors may be configured to generate, as the target approximate polynomial, a polynomial for a case where a relative error between a maximum value and a minimum value among the absolute values of the one or more extreme points is less than a threshold.

In another general aspect, an apparatus configured to perform a fully homomorphic encryption scheme includes one or more processors configured to generate a ciphertext by encrypting data, bootstrap the ciphertext by performing an approximation of a function correspoinding to a modular reduction based on a selection of one or more target points for a modulus corresponding to the ciphertext, and generate a target approximate polynomial configured to approximate the function corresponding to the modular reduction.

The target approximate polynomial may be generated using Chebyshev alternation theorem.

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

Also, descriptions of features that are known after understanding of the disclosure of this application may be omitted for increased clarity and conciseness.

Spatially relative terms such as "above," "upper," "below," and "lower" may be used herein for ease of description to describe one element's relationship to another element as shown in the figures. Such spatially relative terms are intended to encompass different orientations of the device in use or operation in addition to the orientation depicted in the figures. For example, if the device in the figures is turned over, an element described as being "above" or "upper" relative to another element will then be "below" or "lower" relative to the other element. Thus, the term "above" encompasses both the above and below orientations depending on the spatial orientation of the device. The device may also be oriented in other ways (for example, rotated <NUM> degrees or at other orientations), and the spatially relative terms used herein are to be interpreted accordingly.

<FIG> illustrates an example of an encryption apparatus.

In <FIG>, an encryption apparatus <NUM> may encrypt data. The encryption apparatus <NUM> may generate encrypted data through encryption of data. Hereinafter, the encrypted data may be referred to as a ciphertext. The use of the term "may" herein with respect to an example or embodiment (for example, as to what an example or embodiment may include or implement) means that at least one example or embodiment exists where such a feature is included or implemented, while all examples are not limited thereto.

The encryption apparatus <NUM> may provide an encryption technique for performing an operation in a computer and/or server, e.g., by performing calculations on data encrypted using fully homomorphic encryption, without decrypting it first. The result of the operation is in an encrypted form and when the output of the operation is decrypted, the output is the same as if the operations had been performed on an unencrypted data. The encryption apparatus <NUM> allows for data privacy to be preserved even when data is shared with a <NUM>rd party because the data can remain encrypted when the <NUM>rd party uses or performs computations on the data.

The encryption apparatus <NUM> may provide an encryption technique for performing an operation, e.g., calculations, on data encrypted using homomorphic encryption without decrypting it first. In an example, the encryption apparatus <NUM> may 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 apparatus <NUM> may provide homomorphic encryption operations for real or complex numbers.

The encryption apparatus <NUM> may perform bootstrapping required for homomorphic encryption. The encryption apparatus <NUM> may generate a target approximate polynomial that approximates a function corresponding to a modular reduction required for homomorphic encryption.

The encryption apparatus <NUM> may find a minimax approximation error for each degree of an optimal minimax approximate polynomial.

The encryption apparatus <NUM> may find an optimal approximate polynomial through the target approximate polynomial, thereby providing excellent performance in terms of the minimax approximation error of homomorphic encryption.

The encryption apparatus <NUM> may generate a target approximate polynomial that approximates the modular reduction function based on approximation region information for approximating the modular reduction function.

The encryption apparatus <NUM> includes a processor <NUM> and a memory <NUM>.

The processor <NUM> may process data stored in the memory. The processor <NUM> may execute a computer-readable code (for example, software) stored in the memory <NUM> and instructions triggered by the processor <NUM>.

The "processor <NUM>" 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 processor <NUM> may generate a ciphertext by encrypting data. The processor <NUM> may bootstrap the ciphertext by performing a modular reduction on a modulus corresponding to the generated ciphertext.

The processor <NUM> may bootstrap the ciphertext by approximating a function corresponding to the modular reduction. The processor <NUM> may generate a target approximate polynomial that approximates the function corresponding to the modular reduction.

The processor <NUM> may determine one or more reference points based on a degree of the target approximate polynomial.

The processor <NUM> may obtain an arbitrary polynomial based on the determined one or more reference points. The processor <NUM> may obtain a piecewise continuous function that passes through the one or more reference points. The processor <NUM> may 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 processor <NUM> may obtain the arbitrary polynomial by generating a polynomial, where 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 processor <NUM> may generate the target approximate polynomial based on one or more extreme points selected from the arbitrary polynomial. In detail, the processor <NUM> may 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 processor <NUM> may select target points from among the obtained candidate points, where the number of target points is based on the degree of the target approximate polynomial. The processor <NUM> may select the target points from among the candidate points such that a maximum and a minimum appear in alternation. The processor <NUM> may select the target points such that the sum of the absolute values of the errors between the arbitrary polynomial and the piecewise continuous function that passes through the one or more reference points is maximized.

The processor <NUM> may generate the target approximate polynomial based on the selected target points. The processor <NUM> may generate, as the target approximate polynomial, a polynomial for a case where a relative error between a maximum value and a minimum value among the absolute values of the one or more extreme points is less than a threshold.

In this example, a basis of the target approximate polynomial may be the basis of the Chebyshev polynomials.

The memory <NUM> may 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 memory <NUM> may 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.

Hereinafter, a process of performing encryption and bootstrapping by the encryption apparatus <NUM> will be described in further detail with reference to <FIG>. Specifically, an encryption operation performed by the encryption apparatus <NUM> will be described, and then a bootstrapping process will be described in more detail.

<FIG> illustrate examples of algorithms for generating a target approximate polynomial by the encryption apparatus of <FIG>, and <FIG> illustrates an example of generating a target approximate polynomial by the encryption apparatus of <FIG>.

In <FIG>, the processor <NUM> may encrypt data.

Hereinafter, notations for describing the encryption operation of the processor <NUM> will be described.

<IMG>, <IMG>, <IMG>, and <IMG> denote sets of integers, rational numbers, real numbers, and complex numbers, respectively. C[D] denotes a set of continuous functions on a domain D. [d] denotes a set of positive integers less than or equal to d. For example, [d] may be {<NUM>, <NUM>,. round(x) denotes a function that outputs the integer nearest to x. For M, which is a power of <NUM>, ΦM(X) = XN + <NUM> denotes an M-th cyclotomic polynomial, where M=2N. <IMG> and <IMG> denote <MAT> and <IMG> = <IMG>/q<IMG>, respectively. <MAT> denotes an M-th cyclotomic field.

For a positive real number α, <IMG>G(α) is defined as the distribution in <MAT> whose entries may be sampled independently from the discrete Gaussian distribution of a variance α<NUM>.

<IMG>WT(h) denotes a subset of {<NUM>,±<NUM>}N with a Hamming weight h. <IMG>O(ρ) denotes the distribution in {<NUM>,±<NUM>}N whose entries may be sampled independently with a probability ρ/<NUM> for each of ±<NUM> and a probability being zero, <NUM>-ρ.

The Chebyshev polynomials Tn(x) are defined by cos nθ = Tn(cosθ). The base of a logarithm described below is <NUM>.

Hereinafter, the encryption operation performed by the processor <NUM> will be described.

The processor <NUM> may support several operations for encrypted data of real numbers or complex numbers. Since the encryption apparatus <NUM> deals with usually real numbers, the noise that ensures the security of the encryption scheme may be embraced in the outside of the significant figures of the data.

Several independent messages may be encoded into one polynomial by the canonical embedding before encryption. The canonical embedding σ may embed a ∈ <MAT> into an element of <MAT>, and the elements of <MAT> may be values of a evaluated at the distinct roots of ΦM(X).

The roots of ΦM(X) may be the power of odd integers of the M-th root of unity, and <MAT>.

<IMG> may be <MAT>, and π may be a natural projection from <IMG> to <MAT>. The range of σ may be <IMG>.

When N/<NUM> messages of complex numbers constitute an element in <MAT>, each coordinate may be called a slot. The encoding and decoding procedures may be given as below.

For a vector <MAT>, encoding Ecd(z;Δ) may return the value of Equation <NUM>.

Here, Δ is the scaling factor, and
<MAT>
denotes discretization or rounding operation of π-<NUM>(z) into an element of σ(<IMG>).

For a polynomial m(X) ∈ <IMG>, decoding Dcd(m;Δ) may return a vector <MAT> whose entry of index j satisfies <MAT> for j ∈ {<NUM>, <NUM>,. , N/<NUM> - <NUM>}, where ζM may be the M-th root of unity.

The encryption apparatus <NUM> may generate keys. For a given security parameter λ, the encryption apparatus <NUM> may select a power of two M, an integer h, an integer P, a real positive number α , a fresh ciphertext modulus qL, and a big ciphertext modulus Q, which will be the maximum ciphertext modulus.

A fresh ciphertext may be encrypted data on which no operation is performed or data that is encrypted first.

The processor <NUM> may set a public key pk and a secret key sk as expressed by Equation <NUM>.

Here, s, a, and e denote s ← <IMG>WT(h), a ← <IMG>, and e ← <IMG>G(α<NUM>), respectively.

The processor <NUM> may set an evaluation key as expressed by Equation <NUM>.

a' and e' denote a' ← <IMG> and e' ←<IMG>(α<NUM>), respectively.

The processor <NUM> may return the result of Equation <NUM> by performing encoding Encpk(m ∈ <IMG>).

Here, υ, and e<NUM> and e<NUM> may be sampled as expressed by <MAT> and e<NUM>, e<NUM> ← <IMG>(α<NUM>), respectively.

The processor <NUM> may return m = 〈c, sk〉 mod qℓ by performing decoding <MAT>.

The processor <NUM> may return the result of Equation <NUM> by performing addition <MAT> on two ciphertexts.

The processor <NUM> may return the result of Equation <NUM> by performing multiplication <MAT> on the two ciphertexts c<NUM> = (b<NUM>, a<NUM>) and c<NUM> = (b<NUM>, a<NUM>).

Here, (d<NUM>, d<NUM>, d<NUM>) := (b<NUM>b<NUM>, a<NUM>b<NUM> + a<NUM>b<NUM>, a<NUM>a<NUM>) mod ql.

Further, the processor <NUM> may return the result of Equation <NUM> by performing <MAT>.

Each ciphertext may have a level ℓ representing the maximum number of possible multiplications without bootstrapping. The modulus qℓ for each ciphertext of level ℓ may have a value of pℓq<NUM>, where p is the scaling factor, and q<NUM> is the base modulus.

In addition, the processor <NUM> may perform rotation and complex conjugation operations which are used for homomorphic linear transformation in bootstrapping.

Hereinafter, the bootstrapping operation performed by the encryption apparatus <NUM> will be described.

The purpose of bootstrapping may be to refresh a ciphertext of level <NUM>, whose multiplication cannot be performed any further, to a fresh ciphertext of level L having the same messages.

A ciphertext may be encrypted data. The level of ciphertext may be the number of possible multiplications without bootstrapping.

Bootstrapping may include four operations. Firstly, bootstrapping may include a modulus raising operation, and secondly, bootstrapping may include a homomorphic linear transformation operation. Thirdly, bootstrapping may include a homomorphic modular reduction operation, and fourthly, bootstrapping may include a homomorphic linear transformation operation.

The processor <NUM> may perform a modulus raising operation. To describe the modulus raising operation, a ciphertext of level <NUM> may be used as an element of <MAT>, instead <MAT>.

The ciphertext of level <NUM> may be in a state of 〈ct, sk〉 ≈ m mod q<NUM>. Here, ct denotes a ciphertext, and sk denotes a secret key. When the processor <NUM> tries to decrypt the ciphertext, the ciphertext may have the form of 〈ct, sk〉 ≈ m+q<NUM>I mod Q for some I ∈ <IMG>.

Here, coefficients of sk include small numbers, and thus the absolute values of coefficients of I may be small. For example, the absolute values of coefficients of I may be smaller than <NUM>.

The processor <NUM> may generate ct' that satisfies 〈ct', sk〉 ≈ m mod qL by bootstrapping the ciphertext of level <NUM>. To this end, the processor <NUM> may perform homomorphic linear transformation and homomorphic evaluation of the modular reduction function.

Hereinafter, the homomorphic linear transformation performed by the processor <NUM> will be described. The ciphertext ct after modulus raising may be considered as a ciphertext encrypting m + g<NUM>I. The processor <NUM> may perform a modular reduction to coefficients of message polynomial homomorphically.

The operations are all for slots, not for coefficients of the message polynomial. Thus, to perform meaningful operations on coefficients, the processor <NUM> may convert ct into a ciphertext that encrypts coefficients of m + q<NUM>I as its slots.

After evaluating the homomorphic modular reduction function, the processor <NUM> may reversely convert this ciphertext into the other ciphertext ct' that encrypts the slots of the previous ciphertext as the coefficients of its message. Hereinafter, these conversion and reverse conversion operations are called COEFFTOSLOT and SLOTTOCOEFF, respectively.

The two conversion operations described above may be regarded as homomorphic evaluation of encoding and decoding of messages, which may be a linear transformation by some variants of a Vandermonde matrix for roots of ΦM(x). Further, the conversion operations may be performed by general homomorphic matrix multiplication or FFT-like operation.

The processor <NUM> may perform the homomorphic modular reduction (or modular reduction) operation. In detail, the processor <NUM> may perform the modular reduction operation using the homomorphic modular reduction function.

After COEFFTOSLOT conversion is performed, the processor <NUM> may perform a modular reduction homomorphically on each slot in modulus q<NUM>. Hereinafter, this procedure may be called EVALMOD.

By restricting the range of the messages such that m/q<NUM> is small enough, the processor <NUM> may restricts the approximation region near multiples of q<NUM>. Through this range restriction, the processor <NUM> may perform the modular reduction more effectively.

Hereinafter, the algorithm of <FIG> will be described in detail.

The processor <NUM> may generate a target approximate polynomial by finding a minimax approximate polynomial for any continuous function on an interval [a, b] using Algorithm <NUM> of <FIG>. The processor <NUM> may use Chebyshev alternation theorem to generate a target approximate polynomial satisfying equioscillation condition.

The processor <NUM> may generate a target approximate polynomial whose basis function {g<NUM>, ··· ,gn} satisfies the Haar condition. To generate a target approximate polynomial of degree d, the processor <NUM> may select the basis function {g<NUM>,··· ,gn} by the power basis {<NUM>,x, ··· ,xd}. Here, n=d+<NUM>.

The processor <NUM> may initialize the set of reference points that are converged to the extreme points of the minimax approximate polynomial. The processor <NUM> may 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.

When f(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 {g<NUM>,···,gn} satisfying the condition of Equation <NUM> for some E.

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

The processor <NUM> may obtain n zeros zi of p(x) - f(x) between xi and xi+<NUM> if z<NUM> = a, zn+<NUM> = b, and i = <NUM>, <NUM>, ··· , n , and may obtain n+<NUM> extreme points y<NUM> ···, yn+<NUM> of p(x) - f(x) in each [zi-<NUM>, zi].

The processor <NUM> may select the minimum point of p(x) - f(x) in [zi-<NUM>, zi] if p(xi) - f(xi) < <NUM>, and select the maximum point of p(x) - f(x) in [zi-<NUM>, zi] if p(xi) - f(xi) > <NUM>.

Through this, the processor <NUM> may select a new set of extreme points y<NUM>, ··· ,yn+<NUM> as candidate points. If these candidate points satisfy equioscillation condition, the processor <NUM> may generate a target approximate polynomial by returning a minimax approximate polynomial from the Chebyshev alternation theorem.

Further, the processor <NUM> may replace a set of reference points with the new set of extreme points y<NUM>, ···, yn+<NUM> obtained through the above process, and iteratively perform the polynomial generating process described above.

Algorithm <NUM> shown in <FIG> may be extended to the multiple sub-intervals of an interval. When Algorithm <NUM> extended to the multiple sub-intervals is applied, steps <NUM> and <NUM> of <FIG> may be changed.

For each iteration, the processor <NUM> may 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 processor <NUM> may select, from among all of the obtained local extreme points, n+<NUM> new extreme points satisfying the following two criteria:.

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

<FIG> and <FIG> show a polynomial generating method modified from the algorithm of <FIG>. The processor <NUM> may modify the method of selecting new extreme points from among all local extreme points.

The algorithm of <FIG> may be illustrated as the flowchart of <FIG>. In operation <NUM>, the processor <NUM> may set d+<NUM> points in an approximation region. The d+<NUM> points may be the one or more reference points described above.

The processor <NUM> may obtain an arbitrary polynomial based on the d+<NUM> reference points. For example, in operation <NUM>, the processor <NUM> may find a polynomial p(x) and the value of E satisfying Equation <NUM>.

In operation <NUM>, the processor <NUM> may obtain points whose absolute values are greater than or equal to E among local maximum points and local minimum points of p(x) - f(x). Here, the value of E may be the predetermined value described above, and the obtained local maximum point and local minimum point may be the candidate points described above.

In operation <NUM>, the processor <NUM> may select d+<NUM> points from among the obtained points such that the maximum and the minimum appear in altemation, where the d+<NUM> points may be selected such that the sum of absolute values of p(x) - f(x) is maximized. The d+<NUM> points at which the sum of absolute values is maximized may be the target points described above. The process of selecting d+<NUM> points such that the sum of absolute values is maximized will be described in detail with reference to <FIG> and <FIG>.

In operation <NUM>, the processor <NUM> may determine whether the relative error between the maximum value and the minimum value of the absolute values among the selected d+<NUM> target points is less than δ. δ may be the threshold described above.

In operation <NUM>, the processor <NUM> may output an arbitrary polynomial p(x) as a target approximate polynomial if the relative error between the maximum value and the minimum value of the absolute values corresponding to the target points is less than δ. Otherwise, the processor <NUM> may iteratively perform the process of operations <NUM> to <NUM>.

Hereinafter, the operations of <FIG> and <FIG> will be described in more detail.

The function to be approximated by the processor <NUM> may be a normalized modular reduction function defined in only near finitely many integers as expressed by Equation <NUM>.

Equation <NUM> may express the modular reduction function scaled for both its domain and range.

The processor <NUM> may use the cosine function to approximate normod(x) to use double-angle formula for efficient homomorphic evaluation.

If the double-angle formula is used ℓ times, the cosine function in Equation <NUM> may need to be approximated.

To approximate the piecewise continuous functions including the functions of Equations <NUM> and <NUM>, the processor <NUM> may assume a general piecewise continuous function defined on a union of finitely many closed intervals, which is given as Equation <NUM>.

Here, ai < bi < ai+<NUM> < bi+<NUM> for all i = <NUM>, ··· ,t - <NUM>.

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

The processor <NUM> may generate a target approximate polynomial by using {g<NUM>,···,gn} satisfying the Haar condition on [a, b] as the basis of polynomial. The processor <NUM> may 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 processor <NUM> selects n+<NUM> points from among extreme points of an error function evaluated using the arbitrary polynomial obtained using the set of reference points. The processor <NUM> may consider many intervals during the encryption process, and thus there may be lots of candidate extreme points.

The processor <NUM> may select n+<NUM> target points from among many candidate points for each iteration to minimize the number of iterations. Through this, the processor <NUM> may generate the minimax approximate polynomial by converging the approximate polynomial generated for each iteration.

In order to set the criterion for selecting n+<NUM> target points, the processor <NUM> may define the function of Equation <NUM>.

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

The processor <NUM> may obtain all extreme points of p(x) - f(x) into a set B. B may be a finite set and expressed as B = {x<NUM>,x<NUM>,···,xm}. The processor <NUM> may select a point in an interval in B.

Assuming that B is ordered in increasing order, x<NUM> < x<NUM> < ··· < xm, then the values of µ may be <NUM> or -<NUM>. The number of extreme points may satisfy m ≥ n + <NUM>.

The processor <NUM> may define a set of functions <IMG> as expressed by Equation <NUM>.

In this example, the set <IMG> may include only the identity function if n+<NUM>=m.

The processor <NUM> may set three criteria for selecting n+<NUM> extreme points.

The processor <NUM> may 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 <NUM> may be set.

To satisfy the local extreme value condition, the processor <NUM> may remove the extreme points if the local maximum value of p(x) - f(x) is negative or the local minimum value of p(x) - f(x) is positive.

Secondly, the processor <NUM> may set an alternating condition. In other words, the condition of Equation <NUM> 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.

Thirdly, the processor <NUM> may set a maximum absolute sum condition. The processor <NUM> may select σ maximizing the value of Equation <NUM> from among σ satisfying the local extreme value condition and the alternating condition.

The absolute error value at current reference points x<NUM>, ···, xn+<NUM> may 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 x<NUM>,··· , xn+<NUM>.

The processor <NUM> may 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 of <FIG>, and the maximum absolute sum condition may be applied to Algorithm <NUM> of <FIG>. The processor <NUM> may apply the maximum absolute sum condition, thereby expediting the convergence to the minimax approximate polynomial.

The set <IMG> always contains at least one element σ<NUM> that satisfies the local extreme value condition and the alternating condition, and may have σ<NUM>(i<NUM>) satisfying |p(xσ<NUM>(i<NUM>)) - f(xσ<NUM>(i<NUM>))| = ∥p - f∥∞ for some i<NUM>.

The processor <NUM> may more efficiently perform steps <NUM>, <NUM>, and <NUM> of Algorithm <NUM> of <FIG> as follows. The processor <NUM> may find coefficients of the approximate polynomial with a power basis at the current reference points for the continuous function f(x).

That is, the processor <NUM> may generate a target approximate polynomial by obtaining the values of the coefficient cj in Equation <NUM>.

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 processor <NUM> may need to set a higher precision for the coefficients of a higher degree basis.

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

The Chebyshev polynomials satisfy the Haar condition described above, and the processor <NUM> may obtain the target approximate polynomial by calculating cj and E by solving the system of d+<NUM> linear equations of Equation <NUM> using d+<NUM> reference points.

<FIG> illustrates an example of searching for extreme points by the encryption apparatus of <FIG>.

In <FIG>, the processor <NUM> may obtain an arbitrary polynomial based on reference points, and search for extreme points of errors between the arbitrary polynomial and a piecewise continuous function that passes through the reference points. The processor <NUM> may obtain candidate points whose absolute values are greater than or equal to a predetermined value among the extreme points of errors between the arbitrary polynomial and the piecewise continuous function that passes through the reference points. Hereinafter, the process of obtaining candidate points by searching for extreme points by the processor <NUM> will be described.

The processor <NUM> may obtain extreme points where the increase and decrease are exchanged by scanning the errors p(x) - f(x) between the arbitrary polynomial and the piecewise continuous function with a small scan step.

In general, a small scan step may increase the precision of searching for the extreme points but cause a long scan time. To be more specific, it may take a time proportional to <NUM>ℓ to obtain the extreme points with the ℓ-bit precision.

However, the processor <NUM> may search for the extreme points within a linear time of ℓ instead of 2ℓ a time of through the search operation which will be described below.

The processor <NUM> may reduce the search time for the extreme points where the increase and the decrease are exchanged, using a binary search. Hereinafter, the errors between the arbitrary polynomial and the piecewise continuous function may be denoted as r(x) = p(x) - f(x), and sc denotes the scan step.

The processor <NUM> may search for x<NUM> satisfying µ(x<NUM>)r(x<NUM>) ≥ |E| and (r(x<NUM>) - r(x<NUM> - sc))(r(x<NUM> + sc) - r(x<NUM>)) ≤ <NUM>, and obtain the i-th extreme points by performing the process of Equation <NUM> successively ℓ times.

Through the process of Equation <NUM>, the processor <NUM> may obtain the extreme points with the precision of O(log(sc) + ℓ) bits.

Hereinafter, the process of obtaining candidate points through the above extreme point search will be described in detail. In operation <NUM>, the processor <NUM> may obtain the smallest point x in an approximation region. In operation <NUM>, the processor <NUM> may determine whether r(x) is greater than or equal to the absolute value of E if x is a maximum value, and determine whether r(x) is less than or equal to a value obtained by multiplying the absolute value of E by -<NUM> if x is a minimum value.

If the condition of operation <NUM> is satisfied, the processor <NUM> may add x<NUM> to an array B, in operation <NUM>. If the condition of operation <NUM> is not satisfied, the processor <NUM> may replace x with x+sc, in operation <NUM>.

Then, in operation <NUM>, the processor <NUM> may determine whether x is included in the approximation region. If x is included in the approximation region, the processor <NUM> may determine whether r(x)-r(x-sc) and r(x+sc)-r(x) are different in sign, in operation <NUM>.

If x is not included in the approximation region, the processor <NUM> may replace x with the greatest value in a corresponding interval, in operation <NUM>. In this case, in operation <NUM>, the processor <NUM> may determine whether r(x) is greater than or equal to the absolute value of E if x is a maximum value, and determine whether r(x) is less than or equal to a value obtained by multiplying the absolute value of E by -<NUM> if x is a minimum value.

If the condition of operation <NUM> is satisfied, the processor <NUM> may add x<NUM> to the array B, in operation <NUM>. If the condition of operation <NUM> is not satisfied, the processor <NUM> may determine whether x is the maximum value in the approximation region, in operation <NUM>. In this example, if x is the maximum value in the approximation region, the processor <NUM> may terminate the operation. If x is not the maximum value in the approximation region, the processor <NUM> may replace x with the smallest value in a subsequent interval, in operation <NUM>.

If r(x)-r(x-sc) and r(x+sc)-r(x) have the same sign, the processor <NUM> may perform operation <NUM> again. If r(x)-r(x-sc) and r(x+sc)-r(x) are different in sign, the processor <NUM> may replace ℓ with <NUM> and t with sc/<NUM>, in operation <NUM>.

In operation <NUM>, the processor <NUM> may determine whether the value of r(x)-r(x-sc) is greater than <NUM>. If the condition of operation <NUM> is satisfied, the processor <NUM> may select one having the greatest value of r(x) from among x-t, x, and x+t, and replace x with the selected one, in operation <NUM>. Then, in operation <NUM>, the processor <NUM> may replace ℓ with ℓ+<NUM> and t with t/<NUM>.

In operations <NUM> and <NUM>, the processor <NUM> may determine whether ℓ is a precision value. If ℓ is not the precision value, the processor <NUM> may perform operation <NUM> again. If the condition of operation <NUM> is not satisfied or ℓ is not the precision value in operation <NUM>, the processor <NUM> may select one having the smallest value of r(x) from among x-t, x, and x+t, and replace x with the selected one, in operation <NUM>. Then, in operation <NUM>, the processor <NUM> may replace ℓ with ℓ+<NUM> and t with t/<NUM>.

If the conditions of operations <NUM> and <NUM> are satisfied, the processor <NUM> may perform operation <NUM> again. Finally, the processor <NUM> may obtain extreme points in the array B as candidate points.

If the value of sc is sufficiently small, |r(x)| may be a > <NUM> and operate similar to a(x-x*)<NUM>+b for b near x*. Through such operations, the processor <NUM> may guarantee |r(x<NUM>)| > |r(x<NUM>)| and the reverse thereof if |x<NUM>-x*| < |x<NUM>-x*| near x*.

Through the operation of obtaining candidate points through the extreme point search described above, the processor <NUM> may obtain candidate points by searching for the extreme points with the ℓ-bit precision within a linear time of ℓ instead of <NUM>ℓ.

<FIG> illustrates an example of an algorithm for selecting target points by the encryption apparatus of <FIG>, and <FIG> illustrates an example of selecting target points by the encryption apparatus of <FIG>.

<FIG> and <FIG>, the processor <NUM> may select target points from among candidate points obtained through the search operation of <FIG>, where the number of target points is based on the degree of a target approximate polynomial.

The processor <NUM> may select the target points from among the candidate points such that a maximum and a minimum appear in alternation, and select the target points such that the sum of absolute values of errors is maximized. The target points may be new reference points in a subsequent iteration operation.

Hereinafter, the process of obtaining target points will be described in detail. The processor <NUM> may select points satisfying the local extreme value condition, the alternating condition, and maximum absolute sum condition in a naive approach to find target points (or new reference points).

The naive approach is to select n+<NUM> points having the maximum absolute sum by calculating absolute sums for all n+<NUM> points satisfying the alternating condition. If there are m local extreme points, the naive approach may need to investigate all <MAT> points.

Compared to the naive approach, the processor <NUM> may reduce the time for selecting target points through the operations of <FIG> and <FIG>. Hereinafter, the operation of effectively selecting target points will be described.

The processor <NUM> may finally obtain n+<NUM> target points by eliminating some elements from candidate points for each iteration. If m > n + <NUM>, at least one element may not be included in the target points.

Through the algorithm of <FIG>, the processor <NUM> may select target points within a time O(m log m). In other words, the processor <NUM> may select the target points within a quasi-linear time.

Whenever an element in the ordered set B is removed, the remaining elements may be arranged, and indices may be relabeled in increasing order.

When comparing the values to remove some extreme points in Algorithm <NUM> of <FIG>, the compared values may be equal, or the smallest element may be more than one. In that case, the processor <NUM> may randomly remove these elements.

The flowchart of <FIG> shows the sequence of operations in the algorithm of <FIG>. Through the operations of <FIG> and <FIG>, the processor <NUM> may obtain an array B having target points as elements.

In operation <NUM>, the processor <NUM> may replace i with <NUM>. In operation <NUM>, the processor <NUM> may determine whether both xi and xi+<NUM> are maximum or minimum.

If the condition of operation <NUM> is satisfied, the processor <NUM> may remove one of xi and xi+<NUM> having smaller |r(x)| from the array, and rearrange the remaining elements in the array, in operation <NUM>. The value of |r(x)| may be the value of an error between the arbitrary polynomial and the piecewise continuous function described above. If the condition of operation <NUM> is not satisfied, the processor <NUM> may replace i with i+<NUM>, in operation <NUM>.

After the rearrangement, the processor <NUM> may determine whether xi is the largest point in the array B, in operation <NUM>. If xi is not the largest point, the processor <NUM> may perform operation <NUM> again.

Operations <NUM> to <NUM> may correspond to the operations in steps <NUM> to <NUM> of Algorithm <NUM> of <FIG>.

If xi is the largest point, the processor <NUM> may determine whether the number of elements in B is d+<NUM>, in operation <NUM>. If the number of elements in B is d+<NUM>, the processor <NUM> may terminate the operation of selecting target points.

If the number of elements in B is not d+<NUM>, the processor <NUM> may insert the sum of |r(x)| values of every two adjacent points into an array T and arrange the array T, in operation <NUM>. That is, |r(x<NUM>)| + |r(x<NUM>)|, |r(x<NUM>)| + |r(x<NUM>)|, |r(x<NUM>)| + |r(x<NUM>)|,··· may be inserted into T, and T may be arranged.

Operations <NUM> and <NUM> may correspond to the operations in steps <NUM> and <NUM> of Algorithm <NUM> of <FIG>.

In operation <NUM>, the processor <NUM> may determine whether the number of elements in B is d+<NUM>. If the number of elements in B is d+<NUM>, the processor <NUM> may remove one of x<NUM> and xd+<NUM> having smaller |r(x)| from the array, rearrange the array, and terminate the operation, in operation <NUM>.

In operation <NUM>, the processor <NUM> may determine whether the number of elements in B is d+<NUM>. If the number of elements in B is d+<NUM>, the processor <NUM> may add |rx<NUM>| + |rxd+<NUM>| to T and rearrange T, in operation <NUM>. After that, in operation <NUM>, the processor <NUM> may remove two points corresponding to the smallest value in T from B, rearrange B, and terminate the operation.

If the number of elements in B is not d+<NUM>, the processor <NUM> may determine whether one of the two end points is included in the two points corresponding to the smallest value in T, in operation <NUM>. If the condition of operation <NUM> is satisfied, the processor <NUM> may remove one of the two end points from B, and rearrange B, in operation <NUM>. If the condition of operation <NUM> is not satisfied, the processor <NUM> may remove both two points corresponding to the smallest value in T from B, and rearrange B, in operation <NUM>.

After that, the processor <NUM> may remove the value in which the removed elements are included from T, add the sums of |r(x)| values of two newly adjacent points to T, and rearrange T in operation <NUM>, and perform operation <NUM> again. Operations <NUM> to <NUM> may correspond to the operations in steps <NUM> to <NUM> of Algorithm <NUM> of <FIG>.

Describing an example of removing an extreme point x<NUM> at the last part of the algorithm of <FIG>, T = {|r(x<NUM>)| + |r(x<NUM>)|, |r(x<NUM>)| + |r(x<NUM>)|, |r(x<NUM>)| + |r(x<NUM>)|,···} may be changed to T = {|r(x<NUM>)| + |r(x<NUM>)|, |r(x<NUM>)| + |r(x<NUM>)|,···}.

Through the operation of selecting target points of <FIG> and <FIG>, the processor <NUM> may select target points from among candidate points within a quasi-linear time.

The processor <NUM> may generate a target approximate polynomial that optimally approximates a modular reduction function based on the selected target points. In other words, the processor <NUM> may generate a polynomial of degree d that passes through the selected target points as the target approximate polynomial.

<FIG> illustrates an example of an overall operation of the encryption apparatus of <FIG>.

The processor <NUM> may encrypt data using homomorphic encryption. In operation <NUM>, the processor <NUM> may generate a ciphertext by encrypting data.

In operation <NUM>, the processor <NUM> may bootstrap the ciphertext by performing a modular reduction based on a selection of one or more target points for a modulus corresponding to the generated ciphertext.

The processor <NUM> may determine one or more reference points based on a degree of the target approximate polynomial. The processor <NUM> may obtain an arbitrary polynomial based on the determined one or more reference points.

In detail, the processor <NUM> may 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 processor <NUM> may 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 processor <NUM> may generate the target approximate polynomial based on one or more extreme points selected from the obtained arbitrary polynomial. The processor <NUM> may 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 processor <NUM> may select target points from among the obtained candidate points, where the number of target points is based on the degree of the target approximate polynomial. In detail, the processor <NUM> may select the target points from among the candidate points such that a maximum and a minimum appear in alternation. The processor <NUM> may select the target points such that the sum of the absolute values of the errors between the arbitrary polynomial and the piecewise continuous function is maximized.

As a non-exhaustive example only, a terminal as described herein may be a mobile device, such as a cellular phone, a smart phone, a wearable smart device (such as a ring, a watch, a pair of glasses, a bracelet, an ankle bracelet, a belt, a necklace, an earring, a headband, a helmet, or a device embedded in clothing), a portable personal computer (PC) (such as a laptop, a notebook, a subnotebook, a netbook, or an ultra-mobile PC (UMPC), a tablet PC (tablet), a phablet, a personal digital assistant (PDA), a digital camera, a portable game console, an MP3 player, a portable/personal multimedia player (PMP), a handheld e-book, a global positioning system (GPS) navigation device, or a sensor, or a stationary device, such as a desktop PC, a high-definition television (HDTV), a DVD player, a Blu-ray player, a set-top box, or a home appliance, or any other mobile or stationary device configured to perform wireless or network communication. In one example, a wearable device is a device that is designed to be mountable directly on the body of the user, such as a pair of glasses or a bracelet. In another example, a wearable device is any device that is mounted on the body of the user using an attaching device, such as a smart phone or a tablet attached to the arm of a user using an armband, or hung around the neck of the user using a lanyard.

The encryption apparatus <NUM>, processor <NUM>, and memory <NUM> in <FIG> that perform the operations described in this application are implemented by hardware components configured to perform the operations described in this application that are performed by the hardware components. Examples of hardware components that may be used to perform the operations described in this application where appropriate include controllers, sensors, generators, drivers, memories, comparators, arithmetic logic units, adders, subtractors, multipliers, dividers, integrators, and any other electronic components configured to perform the operations described in this application. In other examples, one or more of the hardware components that perform the operations described in this application are implemented by computing hardware, for example, by one or more processors or computers. A processor or computer may be implemented by one or more processing elements, such as an array of logic gates, a controller and an arithmetic logic unit, a digital signal processor, a microcomputer, a programmable logic controller, a field-programmable gate array, a programmable logic array, a microprocessor, or any other device or combination of devices that is configured to respond to and execute instructions in a defined manner to achieve a desired result. In one example, a processor or computer includes, or is connected to, one or more memories storing instructions or software that are executed by the processor or computer. Hardware components implemented by a processor or computer may execute instructions or software, such as an operating system (OS) and one or more software applications that run on the OS, to perform the operations described in this application. The hardware components may also access, manipulate, process, create, and store data in response to execution of the instructions or software. For simplicity, the singular term "processor" or "computer" may be used in the description of the examples described in this application, but in other examples multiple processors or computers may be used, or a processor or computer may include multiple processing elements, or multiple types of processing elements, or both. For example, a single hardware component or two or more hardware components may be implemented by a single processor, or two or more processors, or a processor and a controller. One or more hardware components may be implemented by one or more processors, or a processor and a controller, and one or more other hardware components may be implemented by one or more other processors, or another processor and another controller. One or more processors, or a processor and a controller, may implement a single hardware component, or two or more hardware components. A hardware component may have any one or more of different processing configurations, examples of which include a single processor, independent processors, parallel processors, single-instruction single-data (SISD) multiprocessing, single-instruction multiple-data (SIMD) multiprocessing, multiple-instruction single-data (MISD) multiprocessing, and multiple-instruction multiple-data (MIMD) multiprocessing.

Claim 1:
A processor-implemented encryption method using homomorphic encryption, the encryption method comprising:
generating (<NUM>) a ciphertext by encrypting data;
bootstrapping (<NUM>) the ciphertext by performing an approximation of a function corresponding to a modular reduction for a modulus corresponding to the ciphertext, wherein preforming the approximation is based on a selection of one or more target points; and
generating a target approximate polynomial that approximates the function corresponding to the modular reduction comprising determining one or more reference points based on a degree of the target approximate polynomial, determining an arbitrary polynomial based on the one or more reference points, and generating the target approximate polynomial based on one or more extreme points selected from the arbitrary polynomial.