Method and apparatus for modulus refresh in homomorphic encryption

Disclosed is a method and apparatus for modulus refresh, where the method for modulus refresh of a ciphertext in homomorphic encryption includes receiving a first ciphertext corresponding to a first modulus, generating a second ciphertext by performing a blind rotation on the first ciphertext, and generating a target ciphertext corresponding to a second modulus greater than the first modulus based on the first ciphertext and the second ciphertext.

CROSS-REFERENCE TO RELATED APPLICATIONS

This application claims the benefit under 35 USC § 119(a) of Korean Patent Application No. 10-2021-0065429, filed on May 21, 2021, and Korean Patent Application No. 10-2021-0112965, filed on Aug. 26, 2021, in the Korean Intellectual Property Office, the entire disclosures, all of which, are incorporated herein by reference for all purposes.

BACKGROUND

The following description relates to a method and apparatus for modulus refresh in homomorphic encryption supporting integers or real numbers.

2. Description of Related Art

Homomorphic encryption enables arbitrary operations between encrypted data. Homomorphic encryption is lattice-based and enables arbitrary operations on encrypted data without decrypting the encrypted data. Thus, homomorphic encryption is safer and resistant to quantum algorithms.

Since a modulus corresponding to a ciphertext, which is an encrypted text, decreases between encrypted data in homomorphic encryption, a modulus refresh process for restoring the modulus is needed.

Modulus refresh methods in the conventional homomorphic encryption represent a decryption algorithm as a circuit capable of homomorphic operations. The conventional modulus refresh methods include a method that approximates a modulus operation with a sine function and then performs an approximate polynomial operation close to the sine function, a method that directly approximates a modulus operation to have a low minimum error and variance without sine function approximation, and the like.

The conventional modulus refresh methods have low precision bits for an output value due to an approximate polynomial, when compared to existing ciphertext. When an approximate polynomial of a high order is used, a value of modulus obtained in the modulus refresh process is not large.

SUMMARY

In one general aspect, there is provided a processor-implemented method for modulus refresh of a ciphertext in homomorphic encryption, the method including receiving a first ciphertext corresponding to a first modulus, generating a second ciphertext by performing a blind rotation on the first ciphertext, and generating a target ciphertext corresponding to a second modulus greater than the first modulus based on the first ciphertext and the second ciphertext.

The generating of the second ciphertext may include performing homomorphic operation-based preprocessing on the first ciphertext based on the first modulus and an order of a polynomial of the first ciphertext, and generating the second ciphertext by performing the blind rotation on the first ciphertext on which the homomorphic operation-based preprocessing is performed.

The performing of the homomorphic operation-based preprocessing on the first ciphertext may include determining a transformed first modulus by transforming the first modulus based on the order of the polynomial, generating a third ciphertext by transforming the first ciphertext based on the transformed first modulus, and preprocessing the first ciphertext based on the transformed first modulus and the third ciphertext.

The preprocessing of the first ciphertext based on the transformed first modulus and the third ciphertext may include preprocessing by dividing a difference between the first ciphertext and the third ciphertext by the transformed first modulus.

The generating of the second ciphertext by performing the blind rotation on the first ciphertext may include extracting a learning with error (LWE) vector based on a coefficient of the first ciphertext on which the homomorphic operation-based preprocessing is performed, and generating the second ciphertext by performing the blind rotation based on the LWE vector.

The method of claim5, wherein the generating of the second ciphertext by performing the blind rotation based on the LWE vector may include generating an encryption constant based on a secret key used to generate the first ciphertext, generating a blind rotation key based on the encryption constant, and generating the second ciphertext by performing the blind rotation based on the blind rotation key.

The generating of the second ciphertext by performing the blind rotation based on the blind rotation key may include generating blind rotation ciphertexts corresponding to the blind rotation key according to the order of the polynomial of the first ciphertext, and generating the second ciphertext by combining the blind rotation ciphertexts.

The performing of the homomorphic operation-based preprocessing on the first ciphertext may include determining a transformed first modulus by transforming the first modulus based on the order of the polynomial, generating a third ciphertext by transforming the first ciphertext based on the transformed first modulus, and preprocessing the first ciphertext by performing a rotation operation on the third ciphertext at intervals that are based on a number of plaintexts.

The performing of the homomorphic operation-based preprocessing on the first ciphertext may include generating a transformed first ciphertext by transforming the first ciphertext based on the first modulus and the order of the polynomial, and preprocessing the first ciphertext based on the transformed first ciphertext.

The preprocessing of the first ciphertext based on the transformed first ciphertext may include preprocessing based on a difference between the transformed first ciphertext and a value obtained by multiplying the first ciphertext by twice the order of the polynomial.

The generating of the target ciphertext may include generating the target ciphertext by adding the first ciphertext and the second ciphertext.

In another general aspect, there is provided an apparatus for modulus refresh of a ciphertext in homomorphic encryption, the apparatus including a receiver configured to receive a first ciphertext corresponding to a first modulus, a processor configured to generate a second ciphertext by performing a blind rotation on the first ciphertext, and generate a target ciphertext corresponding to a second modulus greater than the first modulus based on the first ciphertext and the second ciphertext.

The processor may be configured to perform homomorphic operation-based preprocessing on the first ciphertext based on the first modulus and an order of a polynomial of the first ciphertext, and generate the second ciphertext by performing the blind rotation on the first ciphertext on which the homomorphic operation-based preprocessing is performed.

The processor may be configured to determine a transformed first modulus by transforming the first modulus based on the order of the polynomial, generate a third ciphertext by transforming the first ciphertext based on the transformed first modulus, and preprocess the first ciphertext based on the transformed first modulus and the third ciphertext.

The processor may be configured to preprocess based on dividing a difference between the first ciphertext and the third ciphertext by the transformed first modulus.

The processor may be configured to extract a learning with error (LWE) vector based on a coefficient of the first ciphertext on which the homomorphic operation-based preprocessing is performed, and generate the second ciphertext by performing the blind rotation based on the LWE vector.

The processor may be configured to generate an encryption constant based on a secret key used to generate the first ciphertext, generate a blind rotation key based on the encryption constant, and generate the second ciphertext by performing the blind rotation based on the blind rotation key.

The processor may be configured to generate blind rotation ciphertexts corresponding to the blind rotation key according to the order of the polynomial of the first ciphertext, and generate the second ciphertext by combining the blind rotation ciphertexts.

The processor may be configured to determine a transformed first modulus by transforming the first modulus based on the order of the polynomial, generate a third ciphertext by transforming the first ciphertext based on the transformed first modulus, and preprocess the first ciphertext by performing a rotation operation on the third ciphertext at intervals that are based on a number of plaintexts.

The processor may be configured to generate a transformed first ciphertext by transforming the first ciphertext based on the first modulus and the order of the polynomial, and preprocess the first ciphertext based on the transformed first ciphertext.

The processor may be configured to preprocess based on a difference between the transformed first ciphertext and a value obtained by multiplying the first ciphertext by twice the order of the polynomial.

The processor may be further configured to generate the target ciphertext by adding the first ciphertext and the second ciphertext.

DETAILED DESCRIPTION

When describing the example embodiments 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 example embodiments, 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.

Although terms such as “first,” “second,” A, B, (a), or (b) are used to explain various components, the components are not limited to the terms. These terms should be used only to distinguish one component from another component. For example, a “first” component may be referred to as a “second” component, or similarly, and the “second” component may be referred to as the “first” component within the scope of the right according to the concept of the present disclosure.

It should be noted that if it is described in the specification that one component is “connected,” “coupled,” “attached,” or “joined” to another component, a third component may be “connected,” “coupled,” and “joined” between the first and second components, although the first component may be directly connected, coupled or joined to the second component. In addition, it should be noted that if it is described in the specification that one component is “directly connected” or “directly joined” to another component, a third component may not be present therebetween. Likewise, expressions, for example, “between” and “immediately between” and “adjacent to” and “immediately adjacent to” may also be construed as described in the foregoing.

The use of the term “may” herein with respect to an example or embodiment (e.g., 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 same name may be used to describe an element included in the example embodiments described above and an element having a common function. Unless otherwise mentioned, the descriptions on the example embodiments may be applicable to the following example embodiments and thus, duplicated descriptions will be omitted for conciseness.

FIG.1illustrates an example of a modulus refresh apparatus.

Referring toFIG.1, a modulus refresh apparatus10may perform modulus refresh on a ciphertext corresponding to data. The modulus refresh apparatus10may receive encrypted data generated through data encryption. Hereinafter, encrypted data or encrypted text may be referred to as a ciphertext. The ciphertext may be in the form of a polynomial or a vector including a polynomial. Data or a message before encryption may be referred to as a plaintext.

The modulus refresh apparatus10may provide an encryption technique for performing an operation on data encrypted using homomorphic encryption dealing with integers and real numbers without decryption. For example, the modulus refresh apparatus10may decrypt a result of operating data encrypted using homomorphic encryption, thereby deriving the same result as an operation on data in a plaintext. The modulus refresh apparatus10may provide homomorphic encryption operations for arbitrary real or complex numbers.

The modulus refresh apparatus10may perform modulus refresh that is needed for homomorphic encryption. When an operation is performed using a ciphertext generated using homomorphic encryption, a modulus value corresponding to the ciphertext may be reduced. The modulus refresh may refer to an operation of changing a reduced modulus to a larger modulus to perform more ciphertext operations.

The modulus refresh apparatus10may perform an encryption process of encrypting an input value in an arbitrary device and service using homomorphic encryption. The modulus refresh apparatus10may perform encryption using an approximate homomorphic encryption that calculates a ciphertext of a plaintext including real numbers. The modulus refresh apparatus10may perform an encryption operation using a ring learning with error (RLWE)-based approximate homomorphic encryption that supports a ciphertext operation of a plaintext including real numbers.

The modulus refresh apparatus10may perform an encryption process of encrypting an input value in privacy preserving machine learning (PPML) and application services. The modulus refresh apparatus10may not greatly increase an error after performing modulus refresh and thus, may be applied to encryption services requiring high accuracy bits.

The modulus refresh apparatus10may perform modulus refresh of a ciphertext without level consumption. The modulus refresh apparatus10may obtain an accurate result in an operation using the ciphertext even after the modulus refresh is performed. The modulus refresh apparatus10has no level consumption, and thus, may use a polynomial of a low order in the encryption process.

The modulus refresh apparatus10may be implemented in the form of a chip and mounted on a hardware accelerator that utilizes homomorphic encryption. In addition, the modulus refresh apparatus10may be implemented in a personal computer (PC), a data server, a mobile device, a home appliance such as a television, a digital television (DTV), a smart television, a refrigerator, a smart home device, a vehicle such as a smart vehicle, an Internet of Things (IoT) device, or a portable device.

The portable device may be implemented as a laptop computer, a mobile phone, a smart phone, a tablet PC, a mobile internet device (MID), a personal digital assistant (PDA), an enterprise digital assistant (EDA), a digital still camera, a digital video camera, a portable multimedia player (PMP), a speaker, a personal navigation device or portable navigation device (PND), a handheld game console, an e-book, or a smart device. The smart device may be implemented as a smart watch, a smart band, or a smart ring.

The modulus refresh apparatus10includes a receiver100and a processor200. The modulus refresh apparatus10may further include a memory300.

The receiver100may include a receiving interface. The receiver100may receive data. The receiver100may receive a plaintext or a ciphertext. The ciphertext may have a modulus corresponding to the ciphertext. The receiver100may output the received plaintext or ciphertext to the processor200.

The processor200may process data stored in the memory300. The processor200may execute a computer-readable code (for example, software) stored in the memory300and instructions triggered by the processor200.

The “processor200” 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 code or instructions included in a program.

For example, the hardware-implemented data processing device may include a microprocessor, a single processor, an independent processors, a parallel processors, a single-instruction single-data (SISD) multiprocessing, a single-instruction multiple-data (SIMD) multiprocessing, a multiple-instruction single-data (MISD) multiprocessing, a multiple-instruction multiple-data (MIMD) multiprocessing, a microcomputer, a processor core, a multi-core processor, a multiprocessor, a central processing unit (CPU), a neural processing unit (NPU), a graphics processing unit (GPU), a tensor processing unit (TPU), a digital signal processor (DSP), a controller and an arithmetic logic unit (ALU), a field-programmable gate array (FPGA), an application-specific integrated circuit (ASIC), a programmable logic unit (PLU), or an application processor (AP).

The processor200may perform modulus refresh necessary for encryption using homomorphic encryption. The processor200may receive a first ciphertext corresponding to a first modulus, generated by encrypting the data.

The processor200may generate a second ciphertext by performing a blind rotation operation (e.g., a look-up table (LUT) operation) on the first ciphertext. The processor200may perform homomorphic operation-based preprocessing on the first ciphertext based on the first modulus and an order of a polynomial of the first ciphertext. The processor200may calculate a transformed first modulus by transforming the first modulus based on the order of the polynomial. The processor200may generate a third ciphertext by transforming the first ciphertext based on the transformed first modulus. The processor200may perform preprocessing on the first ciphertext by performing a rotation operation on the third ciphertext at intervals that are based on the number of plaintexts. The rotation operation will be described in detail with reference toFIG.4.

The processor200may calculate the transformed first modulus by transforming the first modulus based on the order of the polynomial. The processor200may generate a third ciphertext by transforming the first ciphertext based on the transformed first modulus.

The processor200may perform preprocessing on the first ciphertext based on the transformed first modulus and the third ciphertext. The processor200may perform the preprocessing by dividing a difference between the first ciphertext and the third ciphertext by the transformed first modulus.

The processor200may generate a transformed first ciphertext by transforming the first ciphertext based on the first modulus and the order of the polynomial. The processor200may perform preprocessing on the first ciphertext based on the transformed first ciphertext. The processor200may perform the preprocessing based on a difference between the transformed first ciphertext and a value obtained by multiplying the first ciphertext by twice the order of the polynomial.

The processor200may generate the second ciphertext by performing the blind rotation operation on the first ciphertext on which the homomorphic operation-based preprocessing is performed. The processor200may extract a learning with error (LWE) vector based on a coefficient of the first ciphertext on which the homomorphic operation-based preprocessing is performed. The process of extracting the LWE vector will be described in more detail with reference toFIG.3.

The processor200may generate the second ciphertext by performing the blind rotation operation based on the LWE vector. The processor200may generate an encryption constant based on a secret key used to generate the first ciphertext. The processor200may generate a blind rotation key based on the encryption constant. The processor200may generate the second ciphertext by performing the blind rotation operation based on the blind rotation key.

The processor200may generate a plurality of blind rotation ciphertexts corresponding to the blind rotation key according to the order of the polynomial of the first ciphertext. The processor200may generate the second ciphertext by combining the plurality of blind rotation ciphertexts. The blind rotation operation will be described in more detail with reference toFIG.3.

The processor200may generate a target ciphertext corresponding to a second modulus greater than the first modulus based on the first ciphertext and the second ciphertext. The processor200may generate the target ciphertext by adding the first ciphertext and the second ciphertext.

The memory300stores instructions (or programs) executable by the processor200. For example, the instructions include instructions to perform an operation of the processor200and/or an operation of each element of the processor200.

The memory300may 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 a modulus refresh operation of the modulus refresh apparatus ofFIG.1. The operations inFIG.2may be performed in the sequence and manner as shown, although the order of some operations may be changed or some of the operations omitted without departing from the spirit and scope of the illustrative examples described. Many of the operations shown inFIG.2may be performed in parallel or concurrently. One or more blocks ofFIG.2, and combinations of the blocks, can be implemented by special purpose hardware-based computer, such as a processor, that perform the specified functions, or combinations of special purpose hardware and computer instructions. In addition to the description ofFIG.2below, the descriptions ofFIG.1are also applicable toFIG.2, and are incorporated herein by reference. Thus, the above description may not be repeated here.

Referring toFIG.2, the processor200may perform modulus refresh in an encryption process using homomorphic encryption. The processor200may generate a ciphertext with an increased modulus by performing modulus refresh.

In homomorphic encryption, a plaintext and a ciphertext may have the form of an Nth-order polynomial in which a coefficient for an arbitrary integer q is an integer on a modulus q. N may be an integer greater than or equal to “1”.

When a homomorphic operation is performed, a modulus of a ciphertext is reduced. Thus, to perform a repetitive homomorphic operation, a process of refreshing the reduced modulus to a larger modulus may be needed.

In operation210, the processor200may receive a ciphertext on a modulus q as an input. The ciphertext on the modulus q may correspond to the first ciphertext described with reference toFIG.1.

In operation220, the processor200may perform preprocessing on the initial ciphertext (e.g., the first ciphertext). For example, the processor200may perform preprocessing on the first ciphertext based on a first modulus and an order of a polynomial of the first ciphertext. The preprocessing process will be described in detail with reference to the examples ofFIGS.3to5.

In operation230, the processor220may perform preprocessing on a ciphertext (e.g., a third ciphertext) for a blind rotation operation. The processor200may perform preprocessing on the first ciphertext based on a transformed first modulus and the third ciphertext. In other words, the processor200may transform the first ciphertext into a form suitable for performing the blind rotation operation.

In operation240, the processor200may perform a blind rotation operation (e.g., a homomorphic LUT operation) on the preprocessed first ciphertext. In operation250, the processor200may generate a second ciphertext by combining (or repacking) the first ciphertext on which the blind rotation operation is performed.

In operation260, the processor200may correct the first ciphertext (or the third ciphertext) using the second ciphertext. In operation270, the Processor200may output a ciphertext on a modulus Q, where Q is greater than q.

FIG.3illustrates an example of implementing ciphertext generation using the modulus refresh operation ofFIG.2. The operations inFIG.3may be performed in the sequence and manner as shown, although the order of some operations may be changed or some of the operations omitted without departing from the spirit and scope of the illustrative examples described. Many of the operations shown inFIG.3may be performed in parallel or concurrently. One or more blocks ofFIG.3, and combinations of the blocks, can be implemented by special purpose hardware-based computer, such as a processor, that perform the specified functions, or combinations of special purpose hardware and computer instructions. In addition to the description ofFIG.3below, the descriptions ofFIGS.1-2are also applicable toFIG.3, and are incorporated herein by reference. Thus, the above description may not be repeated here.

Referring toFIG.3, in operation311, a processor (e.g., the processor200ofFIG.1) may receive a first ciphertext. The processor200may perform modulus refresh on the first ciphertext satisfying a·s+b=+e (mod q) for a secret key s with coefficients {−1, 0, 1} and a first ciphertext (a, b), thereby increasing a modulus q of an input ciphertext to a modulus Q of an output ciphertext. In this case, an order N of a polynomial of the ciphertext may be a power of “2” and satisfy 2N|q.

In the following equations, alphabets marked in bold may be N-th order polynomials, and alphabets not in bold may be normal numbers such as integers or real numbers. “·” may be a multiplication operation between polynomials, mod may be a remainder operation, and x|y may be a condition in which y is divisible by x. a mod q may denote performing an operation mod q on all coefficients of a polynomial and may be expressed as [a]q.

The first ciphertext may be (a, b)∈Rq2, and a decryption process may be expressed as a·s+b=m+e (mod q). The decryption process may be expressed as a·s+b=m+e+q·v on real numbers. Encs(m) may be a ciphertext obtained by encrypting a message m using a secret key s.

In operation313, the processor200may perform preprocessing on the first ciphertext based on a first modulus and an order of a polynomial of the first ciphertext. The processor200may calculate a transformed first modulus by transforming the first modulus. The processor200may generate a third ciphertext by transforming the first ciphertext based on the transformed first modulus. The processor200may obtain (a1, b1)=([a]q′, [b]q′)∈Rq′2by performing an operation modulus q′=q/2N on the first ciphertext (a,b)∈Rq2. (a1, b1)∈Rq′2may be expressed as a1·s+b1=m+e1+q′·u on real numbers.

In operation315, the processor200may perform preprocessing on the first ciphertext based on the transformed first modulus and the third ciphertext. The processor200may perform the preprocessing by dividing a difference between the first ciphertext and the third ciphertext by the transformed first modulus. The processor200may obtain the preprocessed first ciphertext by subtracting the third ciphertext (a1, b1) from the first ciphertext (a, b) and dividing the result value by the transformed first modulus q′. The preprocessed first ciphertext may be expressed as a2·s+b2=−u+2N·v on real numbers.

In operation317, the processor200may substitute “0” for a loop index i to repeatedly perform a blind rotation operation. The processor200may repeatedly perform the blind rotation operation by repeatedly performing operations319to325. For the repeated blind rotation operation, the processor200may determine whether i is less than or equal to N−1, in operation319. The processor200may perform operation321if i is less than or equal to N−1, and may perform operation327if i is greater than N−1.

The processor200may generate the second ciphertext by performing the blind rotation operation on the preprocessed first ciphertext. In operation321, the processor200may extract an LWE vector based on a coefficient of the preprocessed first ciphertext. ExtractLWEi(a, b) may be a function for extracting the LWE vector in the form of ({right arrow over (a)}i=(ai, ai−1, . . . , a0, −aN-1, −aN-2, . . . , −ai+1), bi) using polynomials a=a0+a1X+ . . . +aN-1XN-1and b=b0+b1X+ . . . +bN-1XN-1.

In operation323, the processor200may perform a blind rotation operation based on the LWE vector.

The processor200may generate a second ciphertext (a3, b3)∈RQ2by performing an operation using a function ƒ(X)=−Σu=−ccuq·Xuon the preprocessed first (a2, b2)∈R2N2. The second ciphertext (a3, b3)∈RQ2may satisfy a3·s+b3=−u·q′+e3(mod Q). LUTƒ,s({right arrow over (a)}, b) may be an operation of performing a blind rotation operation on the function f and the secret key s.

The processor200may generate a blind rotation key. The processor200may generate an encryption constant based on a secret key used to generate the first ciphertext.

The processor200may generate encryption constants sj+and sj−for the coefficients sj∈{−1,0,1} of the secret key s, according to the conditions described below. If sj=1, the processor200may generate the encryption constants as sj+=1 and sj−=0. If sj=0, the processor200may generate the encryption constants as sj+=0 and sj−=0. If sj=−1, the processor200may generate the encryption constants as sj+=0 and sj−=1.

The processor200may generate the blind rotation key based on the encryption constant, and perform the blind rotation operation based on the blind rotation key. For example, the processor200may generate a ring Gentry, Sahai, Waters (RGSW) ciphertext for a polynomial with constant terms sj+and sj−and use the RGSW ciphertext as the blind rotation key. The blind rotation key including the RGSW ciphertext may be expressed as {RGSW(sj+), RGSW(sj−)}j=[0,N-1].

The processor200may generate the RGSW ciphertext using a ring learning with error (RLWE) ciphertext. The RLWE ciphertext of a message m for the secret key s may be defined as RLWE(m)=(a,a·s+e+m). Here, a may be a polynomial with a coefficient on the modulus q, and e may be an error polynomial with a small coefficient. The processor200may randomly generate a and e at every encryption.

The processor200may define an RLWE′ ciphertext of the message m for s as RLWE′(m)=(RLWE(g0·m), RLWE(g1·m), . . . , RLWE(gd-1·m)). Here, (g0, g1, . . . , gd-1) may be a vector defined in advance for decomposing an arbitrary integer, may have the form of (1, B, B2, . . . , Bd-1) for an arbitrary integer B or may be set to (Q0·[Q0−1]q0, . . . ,Qd-1·[Qd-1−1]qd-1) forQi=Q/qi. Finally, the processor200may define the RGSW ciphertext of the message m for the secret key s as RGSW(m)=(RLWE′(−sm),RLWE′(m)).

The processor200may perform the blind rotation operation on each coefficient uiusing (āi, bi). The processor200may define the function ƒ as ƒ(X)=Σl=−ccql·Xl, and perform initialization to ACC0←ƒ(X)·Xbi. The processor200may obtain a ciphertext ACCN=(ai′, bi′)∈RQ2for mi=−qui+d1·X+ . . . +dN-1·XN-1by repeatedly performing ACCj+1←ACCj·(1+(Xaj−1)·RGSW(sj+)+(X−aj−1)·RGSW(sj−)) for all j∈{0, . . . , N−1}.

In operation325, the processor200may add “1” to the loop index i.

In operation327, the processor200may generate the second ciphertext by combining or repacking the first ciphertexts on which the blind rotation operation is performed. RePacki=0 . . . N-1(ai, bi) may be an operation of combining a plurality of ciphertext polynomials into one polynomial. The processor200may obtain ciphertexts for m0, . . . , mN-1by repeating the blind rotation operation N times, and then combine the obtained ciphertexts into the second ciphertext (a3, b3)∈RQ2for m=−(qu0+qu1X+ . . . +quN-1XN-1).

In operation329, the processor200may generate a target ciphertext by correcting the first ciphertext using the second ciphertext. For example, the processor200may obtain the target ciphertext (a4, b4)∈RQ2for (a1, b1)∈Rq′2and (a3, b3)∈RQ2. (a4, b4)∈RQ2may be expressed as a4·s+b4=m+e1+e3(mod Q).

In operation331, the processor200may output the target ciphertext with the modulus increased to Q for the message m.

FIG.4illustrates an example of implementing ciphertext generation using the modulus refresh operation ofFIG.2. The operations inFIG.4may be performed in the sequence and manner as shown, although the order of some operations may be changed or some of the operations omitted without departing from the spirit and scope of the illustrative examples described. Many of the operations shown inFIG.4may be performed in parallel or concurrently. One or more blocks ofFIG.4, and combinations of the blocks, can be implemented by special purpose hardware-based computer, such as a processor, that perform the specified functions, or combinations of special purpose hardware and computer instructions. In addition to the description ofFIG.4below, the descriptions ofFIGS.1-3are also applicable toFIG.4, and are incorporated herein by reference. Thus, the above description may not be repeated here.

Referring toFIG.4, in operation411, a processor (e.g., the processor200ofFIG.1) may receive a first ciphertext. The processor200may calculate a transformed first modulus by transforming the first modulus based on the order of the polynomial. The processor200may generate a third ciphertext by transforming the first ciphertext based on the transformed first modulus. In operation415, the processor200may perform a rotation operation on the third ciphertext at intervals that are based on the number of plaintexts. Hereinafter, the rotation operation process will be described in detail.

In homomorphic encryption, up to N/2 messages in the form of (z0, . . . , zN/2-1) may be encoded and encrypted in the form of m=m0+m1X+ . . . +mN-1XN-1in a polynomial. If the number of messages n is less than N/2, only a portion of the total space N/2 is used. Thus, it may be referred to as sparse encoding.

If the number of messages n is less than N/2, only a portion of the total space N/2 is used. Thus, it may be referred to as sparse encoding, and the polynomial may include some coefficients being “0” as in m=m0+m1XN/2n+m2XN/n+ . . . +m2n-1XN(2n-1)/n. In this case, the processor200may reduce the amount of computation by performing a blind rotation operation only on uithat is non-zero among the coefficients of u.

The processor200may receive, as an input, a ciphertext (e.g., the first ciphertext) on a modulus q for a message m to perform modulus refresh on the sparsely encoded ciphertext, and finally output a ciphertext (e.g., the target ciphertext) on a modulus Q for the message m.

The processor200may perform a modified preprocessing process to process the sparsely encoded ciphertext. The processor200may obtain (a2, b2)∈Rq′2by sequentially performing a rotation operation ConRot2non the ciphertext (a1, b1)∈Rq′2at intervals of N/2, N/4, . . . 2n. (a2, b2)∈Rq′2may be expressed as

Unlike the blind rotation operation process in the example ofFIG.3in which the blind rotation operation is performed for all coefficients ui, the processor200may obtain 2n ciphertexts by performing the blind rotation operation only for non-zero coefficients uiand generate the second ciphertext by combining the obtained 2n ciphertexts. In the case of full encoding in which the number of messages is N/2, the processor200may perform N blind rotation operations and combines N ciphertexts. Meanwhile, in the case of sparse encoding, the processor200may efficiently perform the operation through 2n blind rotation operations and a combination of 2n ciphertexts.

In operation417, the processor200may perform preprocessing on the first ciphertext based on a transformed first modulus and the third ciphertext. Operation417may be the same as operation315ofFIG.3.

In operation419, the processor200may substitute “0” for a loop index i to repeatedly perform a blind rotation operation. The processor200may repeatedly perform the blind rotation operation by repeatedly performing operations421to427. For the repeated blind rotation operation, the processor200may determine whether i is less than or equal to 2n−1, in operation421. The processor200may perform operation423if i is less than or equal to 2n−1, and may perform operation429if i is greater than 2n−1.

The processor200may generate the second ciphertext by performing the blind rotation operation on the preprocessed first ciphertext. In operation423, the processor200may extract an LWE vector based on a coefficient of the preprocessed first ciphertext. Operation423may be the same as operation321ofFIG.3.

In operation425, the processor200may perform a blind rotation operation based on the LWE vector. Operation425may be the same as operation323ofFIG.3. In operation427, the processor200may add “1” to the loop index i.

In operation429, the processor200may generate the second ciphertext by combining or repacking the first ciphertexts on which the blind rotation operation is performed. Operation429may be the same as operation327ofFIG.3.

In operation431, the processor200may generate a target ciphertext by correcting the first ciphertext using the second ciphertext. In operation433, the processor200may output the target ciphertext with the modulus increased to Q for the message M. Operation431may be the same as operation329ofFIG.3, and operation433may be the same as operation331ofFIG.3.

FIG.5illustrates an example of implementing ciphertext generation using the modulus refresh operation ofFIG.2. The operations inFIG.5may be performed in the sequence and manner as shown, although the order of some operations may be changed or some of the operations omitted without departing from the spirit and scope of the illustrative examples described. Many of the operations shown inFIG.5may be performed in parallel or concurrently. One or more blocks ofFIG.5, and combinations of the blocks, can be implemented by special purpose hardware-based computer, such as a processor, that perform the specified functions, or combinations of special purpose hardware and computer instructions. In addition to the description ofFIG.5below, the descriptions ofFIGS.1-4are also applicable toFIG.5, and are incorporated herein by reference. Thus, the above description may not be repeated here.

Referring toFIG.5, in operation511, a processor (e.g., the processor200ofFIG.1) may receive a first ciphertext. The processor200may perform preprocessing on the first ciphertext based on a first modulus and an order of a polynomial of the first ciphertext.

The processor200may perform preprocessing on a transformed first ciphertext by transforming the first ciphertext based on the first modulus and the order of the polynomial. The processor200may perform preprocessing on the first ciphertext based on the transformed first ciphertext. The processor200may perform the preprocessing based on a difference between the transformed first ciphertext and a value obtained by multiplying the first ciphertext by twice the order of the polynomial.

The processor200may perform a modified preprocessing process to process a residue number system (RNS) architecture not satisfying 2N|q. In operation513, the processor200may generate a third ciphertext by transforming the first ciphertext. In operation515, the processor200may perform a preprocessed first ciphertext by performing preprocessing based on the first ciphertext, the third ciphertext, and the order of the polynomial. Hereinafter, the modified preprocessing process will be described.

In homomorphic encryption, a ciphertext may be expressed as a ciphertext on a modulus for Q=q1·q2. . . qL, which is the product of arbitrarily small primes qi. In this case, the processor200may divide the ciphertext corresponding to Q into ciphertexts on modulus for each qi. This architecture may be referred to as the residue number system described above, and since the residue number system does not satisfy 2N|q, the processor200may modify the preprocessing process to process the residue number system.

The processor200may obtain (a1, b1)=([2N·a]q′, [2N·b]q′)∈Rq2by multiplying the first ciphertext (a, b)∈Rq2by 2N and then performing an operation of modulus q′. The transformed ciphertext (a1, b1)∈Rq2may be expressed as a1·s+b1=m+e1+q1·u on real numbers.

The processor200may obtain (a2, b2)=((a−a1)/q, (b−b1)/q)∈R2N2by subtracting (a1, b1) from the ciphertext (2N·a, 2N·b) and then dividing the result value by q. The preprocessed ciphertext (a2, b2)∈R2N2may be expressed as a2·s+b2=−u+2N·v on real numbers.

In operation517, the processor200may substitute “0” for a loop index i to repeatedly perform a blind rotation operation. The processor200may repeatedly perform the blind rotation operation by repeatedly performing operations519to527. For the repeated blind rotation operation, the processor200may determine whether i is less than or equal to N−1, in operation519. The processor200may perform operation521if i is less than or equal to N−1, and may perform operation527if i is greater than N−1.

The processor200may generate the second ciphertext by performing the blind rotation operation on the preprocessed first ciphertext. In operation521, the processor200may extract an LWE vector based on a coefficient of the preprocessed first ciphertext. Operation521may be the same as operation321ofFIG.3.

In operation523, the processor200may perform a blind rotation operation based on the LWE vector. Operation523may be the same as operation323ofFIG.3. In operation525the processor200may add “1” to the loop index i.

In operation527, the processor200may generate the second ciphertext by combining or repacking the first ciphertexts on which the blind rotation operation is performed. Operation527may be the same as operation327ofFIG.3.

In operation529, the processor200may generate a target ciphertext by correcting the first ciphertext using the second ciphertext. In operation531, the processor200may output the target ciphertext with the modulus increased to Q for the message M. Operation529may be the same as operation329ofFIG.3, and operation531may be the same as operation331ofFIG.3.

FIG.6illustrates an example of the operation of the modulus refresh apparatus ofFIG.1. The operations inFIG.6may be performed in the sequence and manner as shown, although the order of some operations may be changed or some of the operations omitted without departing from the spirit and scope of the illustrative examples described. Many of the operations shown inFIG.6may be performed in parallel or concurrently. One or more blocks ofFIG.6, and combinations of the blocks, can be implemented by special purpose hardware-based computer, such as a processor, that perform the specified functions, or combinations of special purpose hardware and computer instructions. In addition to the description ofFIG.6below, the descriptions ofFIGS.1-5are also applicable toFIG.6, and are incorporated herein by reference. Thus, the above description may not be repeated here.

Referring toFIG.6, in operation610, a receiver (e.g., the receiver100ofFIG.1) may receive a first ciphertext corresponding to a first modulus. The receiver100may output the received first ciphertext to a processor (e.g., the processor200ofFIG.1).

The processor200may perform modulus refresh for a homomorphic encryption operation.

In operation630, the processor200may generate a second ciphertext by performing a blind rotation operation on the first ciphertext. The processor200may perform homomorphic operation-based preprocessing on the first ciphertext based on the first modulus and an order of a polynomial of the first ciphertext. For example, the processor200may perform preprocessing on the first ciphertext by performing a rotation operation on the first ciphertext at intervals that are based on the order of the polynomial.

The processor200may calculate the transformed first modulus by transforming the first modulus based on the order of the polynomial. The processor200may generate a third ciphertext by transforming the first ciphertext based on the transformed first modulus.

The processor200may perform preprocessing on the first ciphertext based on a transformed first modulus and the third ciphertext. The processor200may perform the preprocessing by dividing a difference between the first ciphertext and the third ciphertext by the transformed first modulus.

The processor200may calculate the transformed first modulus by transforming the first modulus based on the order of the polynomial, and generate the third ciphertext by transforming the first ciphertext based on the transformed first modulus. The processor200may perform preprocessing on the first ciphertext by performing a rotation operation on the third ciphertext at intervals that are based on the number of plaintexts.

Alternatively, the processor200may generate a transformed first ciphertext by transforming the first ciphertext based on the first modulus and the order of the polynomial. The processor200may perform preprocessing on the first ciphertext based on the transformed first ciphertext. The processor200may perform the preprocessing based on a difference between the transformed first ciphertext and a value obtained by multiplying the first ciphertext by twice the order of the polynomial.

The processor200may generate the second ciphertext by performing the blind rotation operation on the preprocessed first ciphertext. The processor200may extract an LWE vector based on a coefficient of the preprocessed first ciphertext.

The processor200may generate the second ciphertext by performing the blind rotation operation based on the LWE vector. The processor200may generate an encryption constant based on a secret key used to generate the first ciphertext. The processor200may generate a blind rotation key based on the encryption constant. The processor200may generate the second ciphertext by performing the blind rotation operation based on the blind rotation key.

The processor200may generate a plurality of blind rotation ciphertexts corresponding to the blind rotation key according to the order of the polynomial of the first ciphertext. The processor200may generate the second ciphertext by combining the plurality of blind rotation ciphertexts.

In operation650, the processor200may generate a target ciphertext corresponding to a second modulus greater than the first modulus based on the first ciphertext and the second ciphertext. The processor200may generate the target ciphertext by adding the first ciphertext and the second ciphertext.

As described above, methods are provided for achieving a high modulus and high accuracy through a direct approach for calculating a modulus function obtained as a result of modulus refresh.

The instructions or software to control a processor or computer to implement the hardware components and perform the methods as described above, and any associated data, data files, and data structures, are recorded, stored, or fixed in or on one or more non-transitory computer-readable storage media. Examples of a non-transitory computer-readable storage medium include read-only memory (ROM), random-access programmable read only memory (PROM), electrically erasable programmable read-only memory (EEPROM), random-access memory (RAM), magnetic RAM (MRAM), spin-transfer torque (STT)-MRAM, static random-access memory (SRAM), thyristor RAM (T-RAM), zero capacitor RAM (Z-RAM), twin transistor RAM (TTRAM), conductive bridging RAM (CBRAM), ferroelectric RAM (FeRAM), phase change RAM (PRAM), resistive RAM (RRAM), nanotube RRAM, polymer RAM (PoRAM), nano floating gate Memory (NFGM), holographic memory, molecular electronic memory device), insulator resistance change memory, dynamic random access memory (DRAM), static random access memory (SRAM), flash memory, non-volatile memory, CD-ROMs, CD-Rs, CD+Rs, CD-RWs, CD+RWs, DVD-ROMs, DVD-Rs, DVD+Rs, DVD-RWs, DVD+RWs, DVD-RAMs, BD-ROMs, BD-Rs, BD-R LTHs, BD-REs, blue-ray or optical disk storage, hard disk drive (HDD), solid state drive (SSD), flash memory, a card type memory such as multimedia card micro or a card (for example, secure digital (SD) or extreme digital (XD)), magnetic tapes, floppy disks, magneto-optical data storage devices, optical data storage devices, hard disks, solid-state disks, and any other device that is configured to store the instructions or software and any associated data, data files, and data structures in a non-transitory manner and providing the instructions or software and any associated data, data files, and data structures to a processor or computer so that the processor or computer can execute the instructions. In an example, the instructions or software and any associated data, data files, and data structures are distributed over network-coupled computer systems so that the instructions and software and any associated data, data files, and data structures are stored, accessed, and executed in a distributed fashion by the one or more processors or computers.