Patent Publication Number: US-2023163945-A1

Title: Method and apparatus for hardware-based accelerated arithmetic operation on homomorphically encrypted message

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application claims priority to and the benefit of Korean Patent Applications No. 10-2021-0163684, filed on Nov. 24, 2021, and No. 10-2022-0045015, filed on Apr. 12, 2022, the disclosures of which are incorporated herein by reference in its entirety. 
     BACKGROUND 
     1. Field of the Invention 
     The present invention relates to a method and apparatus for a hardware-based accelerated arithmetic operation for reducing the time required for an operation on homomorphically encrypted messages. 
     2. Discussion of Related Art 
     Homomorphic encryption technology is the same as other encryption technologies in that data (plaintext) is encrypted to generate ciphertext, but unlike other encryption technologies, may have the characteristic that it may perform an operation on encrypted ciphertext without decrypting the encrypted ciphertext. Due to this characteristic, the homomorphic encryption technology requires a large amount of computation, and thus, has a problem in that an operation processing speed is slow. This problem is an obstacle to the practical use of the homomorphic encryption technology. 
     The homomorphic encryption technology has the characteristic that it may perform the homomorphic operation without decrypting the ciphertext, and it takes a long processing time to obtain the operation result by performing the homomorphic operation on the ciphertext. To reduce this problem, methods of increasing an operation speed are being studied. As a representative method, there is a method of using a mathematically efficient calculation algorithm for arithmetic operations between polynomials since ciphertext is a polynomial. Nevertheless, the homomorphic operation process has a limitation in that it requires a long processing time. 
     SUMMARY OF THE INVENTION 
     The present invention is directed to providing a method and apparatus for a hardware-based accelerated arithmetic operation on homomorphically encrypted messages capable of reducing the operation processing time of a homomorphically encrypted message by introducing a hardware-based parallel operation processing technique. 
     An aspect of the present invention is not limited to the above-mentioned aspect. That is, other aspects that are not mentioned may be clearly understood by those skilled in the art from the following specification. 
     According to an aspect of the present invention, there is provided a method of performing hardware-based modular multiplication on homomorphically encrypted messages, including: performing a ciphertext division operation of receiving a plurality of homomorphically encrypted messages expressed in a polynomial form and a modulus for modular multiplication, decomposing the modulus into a product of a plurality of disjoint factors through a Chinese remainder theorem (CRT) operation, and extracting a divided ciphertext from a plurality of homomorphically encrypted messages based on each of the disjoint factors; performing number theoretic transform (NTT) transformation on each coefficient of the divided ciphertext; performing a pointwise multiplication operation between result values of the NTT transformation; performing inverse number theoretic transform (INTT) transformation on a result value of the pointwise multiplication operation to obtain the divided ciphertext; and merging the divided ciphertext obtained in the performing of the INTT transformation through an inverse Chinese remainder theorem (ICRT) operation to generate an output ciphertext. 
     The performing of the ciphertext division operation may include extracting the divided ciphertext from the plurality of homomorphically encrypted messages through a modulus operation with each coefficient of the homomorphically encrypted message as a first operand and the disjoint factor as a second operand. 
     The performing of the ciphertext division operation may include extracting the divided ciphertext by performing the modulus operation after applying a sequence of the same disjoint factor to each of the homomorphically encrypted messages. 
     The performing of the ciphertext division operation may include decomposing the modulus into a product of disjoint factors less than or equal to a predetermined word size. 
     The performing of the NTT transformation may include performing the NTT transformation on each coefficient of the divided ciphertext after inputting each coefficient of the divided ciphertext to a CT butterfly. 
     The CT butterfly may determine the number of input terminals based on a highest order of the homomorphically encrypted message. 
     The CT butterfly may determine the number of calculation stages based on a highest order of the homomorphically encrypted message. 
     The performing of the pointwise multiplication operation may include performing a pointwise multiplication operation for each disjoint factor by the same order using result values of all NTT transformation obtained in the performing of the NTT transformation as a target. 
     The performing of the NTT transformation may include inputting a result value of the pointwise multiplication operation to a Gentleman-Sande (GS) butterfly to perform the INTT transformation. 
     The GS butterfly may determine the number of calculation stages based on a highest order of the homomorphically encrypted message. 
     According to another aspect of the present invention, there is provided, a homomorphically encrypted message modular multiplier, including: a CRT logic circuit unit configured to receive a plurality of homomorphically encrypted messages expressed in a polynomial form and a modulus for modular multiplication, decompose the modulus into a product of a plurality of disjoint factors through a CRT operation, and extract a divided ciphertext from the plurality of homomorphically encrypted messages based on each of the disjoint factors; an NTT logic circuit unit configured to perform NTT transformation on each coefficient of the divided ciphertext; a pointwise multiplication unit configured to perform a pointwise multiplication operation between result values of the NTT transformation; an INTT logic circuit unit configured to perform INTT transformation on a result value of the pointwise multiplication operation to obtain the divided ciphertext; and an ICRT logic circuit unit configured to merge the divided ciphertext obtained by the INTT transformation through an ICRT operation to generate an output ciphertext. 
     The CRT logic circuit unit may decompose the modulus into a product of disjoint factors less than or equal to a predetermined word size. 
     The NTT logic circuit unit may perform the NTT transformation on each coefficient of the divided ciphertext after inputting each coefficient of the divided ciphertext to a Cooley-Turkey (CT) butterfly. 
     The CT butterfly may determine the number of input terminals based on a highest order of the homomorphically encrypted message. 
     The CT butterfly may determine the number of calculation stages based on a highest order of the homomorphically encrypted message. 
     The pointwise multiplication unit may perform a pointwise multiplication operation for each disjoint factor by the same order using result values of all NTT transformation derived from the plurality of homomorphically encrypted messages as a target. 
     The INTT logic circuit unit may input a result value of the pointwise multiplication operation to a Gentleman-Sande (GS) butterfly to perform the INTT transformation. 
     The GS butterfly may determine the number of calculation stages based on a highest order of the homomorphically encrypted message. 
     According to still another aspect of the present invention, there is provided, a homomorphically encrypted message modular multiplier, including: a CRT logic circuit unit configured to receive a plurality of homomorphically encrypted messages expressed in a polynomial form and a modulus for modular multiplication, decompose the modulus into a product of a plurality of disjoint factors through a CRT operation, and extract a divided ciphertext from the plurality of homomorphically encrypted messages based on each of the disjoint factors; an NTT logic circuit unit configured to perform NTT transformation on each coefficient of the divided ciphertext; and a pointwise multiplication unit configured to perform a pointwise multiplication operation between result values of the NTT transformation, in which the NTT logic circuit unit may perform INTT transformation on result values of the pointwise multiplication operation to obtain the divided ciphertext, and the CRT logic circuit unit may merge the divided ciphertext obtained by the INTT transformation through an ICRT operation to generate an output ciphertext. 
     The CRT logic circuit unit may decompose the modulus into a product of disjoint factors less than or equal to a predetermined word size. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The above and other objects, features and advantages of the present invention will become more apparent to those of ordinary skill in the art by describing exemplary embodiments thereof in detail with reference to the accompanying drawings, in which: 
         FIG.  1    is a flowchart for describing a method of performing hardware-based modular multiplication on homomorphically encrypted messages according to an embodiment of the present invention; 
         FIGS.  2 A to  2 F  are reference diagrams for operations of each operation of the method of performing hardware-based modular multiplication on homomorphically encrypted messages according to the embodiment of the present invention; 
         FIG.  3    is a block diagram illustrating a configuration of a homomorphically encrypted message modular multiplier according to a first embodiment of the present invention; and 
         FIG.  4    is a block diagram illustrating a configuration of a homomorphically encrypted message modular multiplier according to a second embodiment of the present invention. 
         FIG.  5    is a block diagram illustrating a computer system for implementing the method according to the embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS 
     Various advantages and features of the present invention and methods accomplishing them will become apparent from the following description of embodiments with reference to the accompanying drawings. However, the present invention is not limited to embodiments to be described below, but may be implemented in various different forms, these embodiments will be provided only in order to make the present invention complete and allow those skilled in the art to completely recognize the scope of the present invention, and the present invention will be defined by the scope of the claims. Meanwhile, terms used in the present specification are for describing embodiments rather than limiting the present invention. Unless otherwise stated, a singular form includes a plural form in the present specification. “Comprise” and/or “comprising” used in the present invention indicate(s) the presence of stated components, steps, operations, and/or elements but do(es) not exclude the presence or addition of one or more other components, steps, operations, and/or elements. 
     When it is decided that the detailed description of the known art related to the present invention may unnecessary obscure the gist of the present invention, a detailed description thereof will be omitted. 
     Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings. The same means will be denoted by the same reference numerals throughout the accompanying drawings in order to facilitate the general understanding of the present invention in describing the present invention. 
       FIG.  1    is a flowchart for describing a method of performing hardware-based modular multiplication on homomorphically encrypted messages according to an embodiment of the present invention, and  FIGS.  2 A to  2 F  are reference diagrams for operations of each operation of the method of performing hardware-based modular multiplication on homomorphically encrypted messages according to the embodiment of the present invention. 
     The method of performing hardware-based modular multiplication on homomorphically encrypted messages according to the embodiment of the present invention includes operations S 110  to S 150 . 
     Operation S 110  is a ciphertext division operation. A homomorphically encrypted message modular multiplier according to the present invention (hereinafter, “homomorphically encrypted message modular multiplier”) receives a modulus q to be applied to a modular multiplication operation and a plurality of homomorphically encrypted messages targeted for a multiplication operation. In this case, it is assumed that the homomorphically encrypted message is expressed in a polynomial form. The homomorphically encrypted message modular multiplier decomposes the modulus q into a product of a plurality of disjoint factors (pairwise coprime) through a Chinese remainder theorem (CRT) operation, and extracts a divided ciphertext for each homomorphically encrypted message through the modulus operation with each coefficient of the homomorphically encrypted message expressed in a polynomial form as a first operand and a disjoint factor obtained through the CRT operation as a second operand. The extraction of the divided ciphertext is performed according to a certain order of disjoint factors. 
     Operation S 110  will be described below in detail with reference to  FIGS.  2 A and  2 B . In the present embodiment, it is assumed that there are two homomorphically encrypted messages a and b input to the homomorphically encrypted message modular multiplier. The homomorphically encrypted messages a and b each have a highest order (n- 1 ). It may be expressed as a polynomial (Equations 1 and 2) having n terms. 
         a=a   0   +a   1   x+a   2   x   2  + . . . + a   n−1   x   n−1    [Equation 1]
 
         b=b   0   +b   1   x+b   2   x   2  + . . . + b   n−1   x   n−1    [Equation 2]
 
     In Equation 1, a 0 , a 1 , . . . , and a n−1  are coefficients of each term of a, and in Equation 2, b 0 , b 1 , . . . , and b n−1  are coefficients of each term of b. The coefficients of each term of a and b have an integer value, which corresponds to an integer value of the state before being divided by the modulus q. 
     There is an equation (a 0 =(a 0 +a 1 x+a 2 x 2 + . . . +a n−1 x n−1 ) (mod q)) related to a q  in  FIG.  2 A , and the equation means that the modular operation by the modulus q is finally applied to the homomorphically encrypted message a expressed as a polynomial. The equation for b q  of  FIG.  2   b    is also used to mean that the modular operation by the modulus q is finally applied to the homomorphically encrypted message b. 
     The homomorphically encrypted message modular multiplier divides the modulus q into q 0 , q 1 , . . . , and q r−1  through the CRT operation. That is, the homomorphically encrypted message modular multiplier extracts a plurality of disjoint factors q 0 , and q r−1  from the modulus q through the CRT operation. q may be represented by a product of q 0 , and q r−i , and q 0 , and q r−i  have a coprime relationship in any pair. Meanwhile, the CRT operation is also referred to as a residue number system (RNS) operation. 
     The homomorphically encrypted message modular multiplier acquires the divided ciphertext for each homomorphically encrypted message through the modulus operation with each coefficient of the homomorphically encrypted message and the disjoint factors q 0 , q 1 , q r−1  extracted through the CRT operation as operands. 
     For example, the homomorphically encrypted message modular multiplier obtains a divided ciphertext a q o through the modulus operation with each coefficient of the homomorphically encrypted message a and the disjoint factor q 0  as operands of the modulus operation. a q0  may be expressed as in Equation 3. 
         a   q     0   =( a   0,0   +a   1,0   x+a   2,0   x   2 + . . . + a   n−1,0   x   n−1 )(mod  q   0 )   [Equation 3]
 
     In Equation 3, a 0,0  is the remainder obtained by dividing a constant term a 0  of the homomorphically encrypted message a by q 0 , and a 1,0  is the remainder obtained by dividing the coefficient a 1  of a first term of the homomorphically encrypted message a by q 0 . Also, a n−1,0  is the remainder obtained by dividing the coefficient a n−1  of a (n−1) th -order term of the homomorphically encrypted message a by q 0 . (mod q 0 ) is used to mean that the modular operation by the modulus q 0  is finally applied to the divided ciphertext a q0  expressed as a polynomial. 
     In this way, the divided ciphertext for each disjoint factor may be obtained by sequentially applying q 0  to q r−1  to the modulus operation. As a result, the homomorphically encrypted message modular multiplier may obtain as many divided ciphertexts (a q0 , a q1 , . . . , and a qr−i ) as the number r of disjoint factors for homomorphically encrypted message a (see  FIG.  2 A ). 
     In the same way, even for the homomorphically encrypted message b, the homomorphically encrypted message modular multiplier applies each disjoint factor to the modulus operation in the same order as in the case of homomorphically encrypted message a to obtain as many divided ciphertexts b q0 , b q1 , . . . , and b qr−1  as the number r of disjoint factors (see  FIG.  2 B ). 
     Through operation S 110 , the homomorphically encrypted message modular multiplier may divide each coefficient of the homomorphically encrypted messages a and b having a large arithmetic word size (LAWS) and the modulus q into coefficients (a 0,0 , etc.) having a small arithmetic word size (SAWS) and the modulus (q 0 , etc.). For reference, the LAWS means a word size that exceeds a default word size (e.g., 64 bits) of a processor, and the SAWS means a word size that is less than or equal to the default word size of the processor. 
     In the present invention, the coefficients or modulus may be divided into various word sizes using the CRT operation (“support for dividing into variable word sizes” in  FIG.  2 A ). That is, the homomorphically encrypted message modular multiplier may obtain coefficients and a modulus corresponding to variably set word sizes (e.g., 64 bits, 128 bits, 256 bits, 512 bits, etc.) through coefficient/modulus division using the CRT operation. The number r of CRT division may also vary according to the variably set word size, that is, the word size of the targeted coefficient or modulus. The homomorphically encrypted message modular multiplier divides a polynomial having a large coefficient value into polynomials having a coefficient value of a small disjoint factor, and thus, independently processes modular operations in parallel. 
     Operation S 120  is a number theoretic transform (NTT) transformation operation. In the present operation, the homomorphically encrypted message modular multiplier performs NTT transformation on the divided ciphertext for each homomorphically encrypted message. That is, the homomorphically encrypted message modular multiplier performs the NTT transformation on the coefficients of the divided ciphertext obtained in operation S 110  to obtain a result value (function value) of the NTT transformation. As the coefficient of the divided ciphertext may be expressed as a sequence, the result value (function value) of the NTT transformation may also be expressed as a sequence. 
     Operation S 120  will be described below in detail with reference to  FIGS.  2 C and  2 D . In the present embodiment, a Cooley-Tukey (CT) butterfly operation is used for the NTT transformation.  FIG.  2 D  illustrates a process in which two output values (u+w*v, u−w*v) are calculated through a CT butterfly operation process when two input values u and v are given. However, since the corresponding NTT transformation is performed on a ring polynomial composed of a modulus q, a modulus operation by q (i.e., mod q) is performed on two output values.  FIG.  2 D  illustrates a process in which the NTT transformation is performed after inputting each coefficient (a 0,0 , a 1,0 , . . . , or a 7,0 ) of the divided ciphertext a q0  to the CT butterfly when it is assumed that n=8. In the NTT transformation process of the divided ciphertext a q0 , q 0  is applied as the modulus. Looking at a part where a 0,0  (corresponding to u) and a 4,0  (corresponding to v) are input in stage 0 of the CT butterfly, it can be seen that a 4,0 *w n   0  is added to or subtracted from a 0,0  and then, the result value obtained by performing the modular operation by q 0  is an output value of stage 0. In the same way, the output value of stage 0 may be obtained for (a 1,0 , a 5,0 ), (a 2,0 , a 6,0 ), and (a 3,0 , a 7,0 ). When an order n of a polynomial input to the NTT transformation is 8, the NTT transformation is performed through (log 2 8), that is, three stages (stage 0, stage 1, and stage 2). As a result of the NTT transformation, it is possible to obtain a result value (function value) A q0  of NTT transformation composed of {A 0,0 , A 1,0 , . . . , A 7,0 }. As described above, the number n of input stages and the number login of stages of the CT butterfly operation may be changed according to the order n of the polynomial of the homomorphically encrypted message. 
     As described above, the NTT transformation is performed on all divided ciphertexts of homomorphic ciphertexts a and b, so result values (A q0 , . . . , A qr−1 , B q0 , . . . , and B qr−1 ) of the NTT transformation for each divided ciphertext may be obtained. 
     Meanwhile, even when the polynomial order of the homomorphically encrypted message changes, the NTT transformation in operation S 120  may be performed by forming the CT butterfly structure accordingly (“support for variable order” in  FIG.  2 D ). A twiddle factor used in the CT butterfly is composed of n roots of equation X n +1=0 (mod q) as illustrated in  FIG.  2 D . That is, the twiddle factor is a primitive root of a residual system composed of modulo q, and is obtained by changing parameters and finding a number that satisfies conditions. The twiddle factor is arranged on the CT butterfly according to the NTT algorithm, and is arranged as follows for each stage according to the example of  FIG.  2 D . 
     stage 0: Since w n   4k  (k=0), w n   0    
     stage 1: Since w n   2k  (k=0,1), w n   0 , w n   2    
     stage 2: Since w n   k  (k=0,1,2,3), w n   0 , w n   1 , w n   2 , w n   3    
     Operation S 130  is an operation of performing a pointwise multiplication operation. In the present operation, the homomorphically encrypted message modular multiplier performs a pointwise multiplication operation between homomorphically encrypted messages. Specifically, the homomorphically encrypted message modular multiplier performs a pointwise multiplication operation according to an order of extracting divided ciphertexts (refer to the description of operation S 110 ) between the result values of the NTT transformation of each divided ciphertext of the homomorphically encrypted messages. The pointwise multiplication operation between the result values of each NTT transformation is an operation to obtain a multiplication result between coefficients of the same order for each same-order term (point-wise). Referring to the embodiment illustrated in  FIG.  2 C , the homomorphically encrypted message modular multiplier sequentially performs the pointwise multiplication operation between the result values (A q0 , . . . , and A qr−1 ) of the NTT transformation of the divided ciphertext of the homomorphically encrypted message a and the result values (B q0 , . . . , and B qr−1 ) of the NTT transformation of the divided ciphertext of the homomorphically encrypted message b according to the order of extracting the ciphertexts (an order of disjoint factors) to obtain result values (C q0 , C q1 , . . . , and C qr−1 ) of the pointwise multiplication operation. For example, C q0  is the result of the pointwise multiplication operation of A q0  and B q0 , and C qr−1  is the result of the pointwise multiplication operation of A qr−1  and B qr−1 . C 0,0 , which is one of the components of C q,0 , is a product of A 0,0  and B 0,0 . Each result value of the pointwise multiplication operation may be expressed as a sequence. 
     As a different example from the present embodiment, when three homomorphically encrypted messages k, l, and m are input to the homomorphically encrypted message modular multiplier, the homomorphically encrypted message modular multiplier performs the ciphertext division (CRT operation) and the NTT transformation to obtain the result values of the NTT transformation for each of the three homomorphically encrypted messages, and then, performs the pointwise multiplication operation between a result value of NTT transformation of a divided ciphertext of homomorphically encrypted message k and a result value of NTT transformation of a divided ciphertext of homomorphically encrypted message  1  and additionally performs a pointwise multiplication operation between the result value of the operation and a result value of NTT transformation of a divided ciphertext of homomorphically encrypted message m, thereby obtaining a final result value of the pointwise multiplication operation. That is, the homomorphically encrypted message modular multiplier repeatedly performs the pointwise multiplication operation on all result values of NTT transformation of a plurality of homomorphically encrypted messages until one final result value of the pointwise multiplication operation is obtained. 
     The homomorphically encrypted message modular multiplier according to the present invention may process the computational complexity required for the multiplication operation between n th —order polynomials with the number of times of multiplications at an O (n log n) level by the NTT transformation and the pointwise multiplication operation. 
     Operation S 140  is an INTT transformation operation. In the present operation, the homomorphically encrypted message modular multiplier obtains the divided ciphertext by performing the INTT transformation on the final result value of the pointwise multiplication operation obtained in operation S 130 . 
     Operation S 140  will be described below in detail with reference to FIGS.  2 E and  2 F. In the present embodiment, a Gentleman-Sande (GS) butterfly operation is used for the INTT transformation.  FIG.  2 F  illustrates a process in which two output values (u+w*v, u−w*v) are calculated through the CT butterfly operation process when two input values u and v are given. However, since the corresponding NTT transformation is performed on the ring polynomial composed of the modulus q, the modulus operation by q (i.e., mod q) is performed on two output values.  FIG.  2 F  illustrates that the INTT transformation is performed after inputting each component (C 0,0 , C 1,0 , . . . , or C 7,0 ) of the result value C q0  of the pointwise multiplication operation corresponding to q 0  to the GS butterfly and INTT when it is assumed that n=8. In the INTT transformation process of the result value C q0  of the pointwise multiplication operation corresponding to q 0 , q 0  is applied as the modulus. Looking at a part where c 0,0  (corresponding to u) and c 4,0  (corresponding to v) are input in stage 0 of the GS butterfly, it can be seen that the result value obtained by performing the modular operation by q 0  on (C 0,0 +C 4,0 ) and (C 0,0 −C 4,0 )*w is an output value of stage 0. In the same way, the output value of stage 0 may be obtained for (C 1,0 , C 5,0 , (C 2,0 , C 6,0 ), and (C 3,0 , C 7,0 ). When an order n of a polynomial input to the INTT transformation is 8, the INTT transformation is performed through (log28), that is, three stages (stage 0, stage 1, and stage 2). The divided polynomial c q0  with the results c 0,0 , c 1,0 , . . . , and c 7,0  of the NTT transformation as coefficients may be obtained. For example, c 0,0  is a coefficient of a constant term of c q0 , and c 7,0  is a coefficient of a 7 th -order term of c q0 . As described above, the number n of input stages and the number log 2 n of stages of the GS butterfly operation may be changed according to the order n of the polynomial of the homomorphically encrypted message. 
     In the same manner as described above, the divided ciphertext (c q0 , c q,1 , . . . , and c qr−1 ) for each disjoint factor may be obtained by performing the INTT transformation on all the result values of the pointwise multiplication operation. 
     Meanwhile, even when the polynomial order of the homomorphically encrypted message changes, the NTT transformation may be performed by forming the GS butterfly structure accordingly (“support for variable order” in  FIG.  2 F ). 
     The method of obtaining a twiddle factor is the same as in operation S 120 . 
     The twiddle factor is arranged on the GS butterfly according to the INTT algorithm, and is arranged as follows for each stage according to the example of  FIG.  2 F . 
     stage 0: Since w n   −k  (k=0,1,2,3), w n   −0 , w n   −1 , w n   −2 , w n   −3    
     stage 1: Since W n   −2k  (k=0,1), w n   −0 , w n   −2    
     stage 2: Since W n   −4k  (k=0), w n   −0    
     Operation S 150  is a ciphertext merging operation. In the present operation, the homomorphically encrypted message modular multiplier generates an output ciphertext by merging the divided ciphertext obtained in operation S 140  through an inverse Chinese remainder theorem (ICRT) operation (see  FIG.  2 E ). The CRT expresses a ciphertext (divided ciphertext) by dividing each coefficient using q 0  to q r−1  divided by q, whereas the ICRT is a process of merging polynomials expressed by division, and performs the process of merging polynomials in a reverse order of the CRT. 
     In  FIG.  2 E , 
     c 0  may be represented by (c 0,0 *M 0 *M 0−1 + . . . +c 0,r−1 *M r−1 *M r−1−1 ) (mod q). 
     Here, M i =q/q i , and M i−1  is a modular multiplication inverse that satisfies M i *M 1−1 (mod q i )=1. 
     In the description with reference to  FIGS.  1  and  2    ( FIGS.  2 A to  2 F ), each operation may be further divided into additional operations or combined into fewer operations according to an implementation example of the present invention. Also, some operations may be omitted if necessary, and an order between the operations may be changed. In addition, even when other contents are omitted, the contents of  FIGS.  3  and  4    may be applied to the contents of  FIGS.  1  and  2    ( FIGS.  2 A to  2 F ). Also, the contents of  FIGS.  1  and  2    ( FIGS.  2 A to  2 F ) may be applied to the contents of  FIGS.  3  and  4   . 
     The above-described method of performing hardware-based modular multiplication on homomorphically encrypted messages has been described with reference to the flowcharts presented in the drawings. For simplicity, the method has been illustrated and described as a series of blocks, but the invention is not limited to the order of the blocks, and some blocks may occur with other blocks in a different order or at the same time as illustrated and described in the present specification. Also, various other branches, flow paths, and orders of blocks that achieve the same or similar result may be implemented. In addition, all the illustrated blocks may be not required for implementation of the methods described in the present specification. 
       FIG.  3    is a block diagram illustrating a configuration of a homomorphically encrypted message modular multiplier according to a first embodiment of the present invention. 
     A modular multiplier  200  on homomorphically encrypted messages according to the first embodiment is configured to include a CRT logic circuit unit  210 , an NTT logic circuit unit  220 , a pointwise multiplication unit  230 , an INTT logic circuit unit  240 , and an ICRT logic circuit unit  250 . 
     When a word size of a coefficient and modulus of a homomorphically encrypted message input to a homomorphically encrypted message modular multiplier is large or the number of input homomorphically encrypted messages is large, the first embodiment is suitable for processing a modular multiplication operation of the homomorphically encrypted message through a parallel operation at a high speed. 
     The CRT logic circuit unit  210  receives a plurality of homomorphically encrypted messages expressed in a polynomial form and a modulus for modular multiplication, and decomposes the received modulus through a CRT operation into a product of a plurality of disjoint factors. In addition, the CRT logic circuit unit  210  extracts a divided ciphertext for each homomorphically encrypted message through a modulus operation with each coefficient of the received homomorphically encrypted message as a first operand and the disjoint factor as a second operand. The CRT logic circuit unit  210  extracts the divided ciphertext from each homomorphically encrypted message according to a predetermined order of the disjoint factors decomposed from the modulus. 
     The CRT logic circuit unit  210  may decompose the received modulus into the disjoint factor corresponding to the set word size by using the CRT operation, and extract a divided ciphertext having a coefficient corresponding to the set word size. The modular multiplier  200  on homomorphically encrypted messages may divide a polynomial having a large coefficient value into polynomials having a coefficient value of a small disjoint factor, and thus, independently process modular operations in parallel. 
     The CRT logic circuit unit  210  may have a single CRT logic circuit, but may include a plurality of CRT logic circuits. When the CRT logic circuit unit  210  includes a plurality of CRT logic circuits, each CRT logic circuit independently processes a modular operation in parallel to generate the divided ciphertext. 
     Details of the CRT logic circuit unit  210  may be understood with reference to the contents of the above-described method of performing hardware-based modular multiplication on homomorphically encrypted messages in operation S 110  and  FIGS.  2 A and  2 B . 
     The NTT logic circuit unit  220  performs NTT transformation on the divided ciphertext. That is, the NTT logic circuit unit  220  obtains the result value (function value) of NTT transformation by performing the NTT transformation on the coefficient of the divided ciphertext calculated by the CRT logic circuit unit  210 . The NTT logic circuit unit  220  may use the CT butterfly operation to perform the NTT transformation, and may perform the NTT transformation by changing the CT butterfly structure according to the polynomial order of the input homomorphically encrypted message (support for variable order). 
     The NTT logic circuit unit  220  may have a single CRT logic circuit, but may include a plurality of CRT logic circuits. When the NTT logic circuit unit  220  includes a plurality of NTT logic circuits, each NTT logic circuit independently processes the NTT transformation (operation) in parallel. 
     Details of the NTT logic circuit unit  220  may be understood with reference to the contents of the above-described method of performing hardware-based modular multiplication on homomorphically encrypted messages in operation S 120  and  FIGS.  2 C and  2 D . 
     The pointwise multiplication unit  230  repeatedly performs the pointwise multiplication operation between the result values of the NTT transformation for all of the plurality of homomorphically encrypted messages. Specifically, the pointwise multiplication unit  230  performs the pointwise multiplication operation between the result values of the NTT transformation of each divided ciphertext of the homomorphically encrypted messages according to the order of extracting the divided ciphertexts (a constant order of the disjoint factors). The pointwise multiplication operation between the result values of each NTT transformation is an operation to obtain a multiplication result between coefficients of the same order for each same-order term (point-wise). 
     The modular multiplier  200  on homomorphically encrypted messages according to the present invention may process the computational complexity required for the multiplication operation between n th —order polynomials with the number of times of multiplications at an  0  (n log n) level by the NTT transformation and the pointwise multiplication operation. 
     Details of the pointwise multiplication unit  230  may be understood with reference to the contents of the above-described method of performing hardware-based modular multiplication on homomorphically encrypted messages in operation S 130  and  FIG.  2 C . 
     The INTT logic circuit unit  240  transforms the final result value of the pointwise multiplication operation obtained by the pointwise multiplication unit  230  into the INTT to obtain the divided ciphertext. The NTT logic circuit unit  240  may use the GS butterfly operation to perform the NTT transformation, and may perform the INTT transformation by changing the GS butterfly structure according to the polynomial order of the input homomorphically encrypted message (support for variable order). 
     Details of the INTT logic circuit unit  240  may be understood with reference to the contents of the above-described method of performing hardware-based modular multiplication on homomorphically encrypted messages in operation S 140  and  FIGS.  2 E and  2 F . 
     The ICRT logic circuit unit  250  generates the output ciphertext by allowing the INTT logic circuit unit  240  to merge the divided ciphertext, which is obtained through the INTT transformation, through the ICRT operation. 
     Details of the ICRT logic circuit unit  250  may be understood with reference to the above-described method of performing hardware-based modular multiplication on homomorphically encrypted messages in operation S 150  and with reference to  FIG.  2 E . 
       FIG.  4    is a block diagram illustrating a configuration of a homomorphically encrypted message modular multiplier according to a second embodiment of the present invention. 
     A modular multiplier  200 ′ on homomorphically encrypted messages according to the second embodiment is configured to include a CRT logic circuit unit  210 ′, an NTT logic circuit unit  220 ′, and a pointwise multiplication unit  230 ′. 
     The second embodiment is different from the first embodiment in the configuration of the homomorphically encrypted message modular multiplier. The second embodiment may be implemented relatively inexpensively compared to the first embodiment, and is suitable when high parallel operation processing performance is not required (e.g., the number of input homomorphically encrypted messages is two). 
     The CRT logic circuit unit  210 ′ performs a function of the CRT logic circuit unit  210  as well as a function of the ICRT logic circuit unit  250 . That is, the CRT logic circuit unit  210 ′ extracts the divided ciphertext through the CRT operation based on the homomorphically encrypted message, transfers the extracted divided ciphertext to the NTT logic circuit unit  220 ′, and generates an output ciphertext by allowing the NTT logic circuit unit  220 ′ to merge the divided ciphertext, which is obtained through INTT transformation, through an ICRT operation. For example, the CRT logic circuit unit  210 ′ includes a CRT logic circuit and an ICRT logic circuit, and may selectively operate the CRT logic circuit or the ICRT logic circuit as necessary. The CRT logic circuit unit  210 ′ receives a plurality of homomorphically encrypted messages expressed in a polynomial form and a modulus for modular multiplication, decomposes the modulus into a product of a plurality of disjoint factors through the CRT operation, and extracts divided ciphertexts according to a predetermined order of the plurality of disjoint factors for each of the homomorphically encrypted messages by the modulus operation with each coefficient of the homomorphically encrypted message as a first operand and the disjoint factor as a second operand. 
     The NTT logic circuit unit  220 ′ performs a function of the INTT logic circuit unit  240  as well as a function of the NTT logic circuit unit  220 . That is, the NTT logic circuit unit  220 ′ not only performs the NTT transformation on the divided ciphertext of the homomorphically encrypted message to transfer the transformation result (result value of the NTT transformation) to the pointwise multiplication unit  230 ′, but also performs the INTT transformation on the final result value of the pointwise multiplication operation of the pointwise multiplication unit  230 ′ to obtain the divided ciphertext for generating an output ciphertext and transfer the obtained divided ciphertext to the CRT logic circuit unit  210 ′. 
     The pointwise multiplication unit  230 ′ performs the same function as the pointwise multiplication unit  230 . That is, the pointwise multiplication unit  230 ′ repeatedly performs the pointwise multiplication operation between the result values of the NTT transformation for all of the plurality of homomorphically encrypted messages. Specifically, the pointwise multiplication unit  230 ′ performs the pointwise multiplication operation between the result values of the NTT transformation of each divided ciphertext of the homomorphically encrypted messages according to the order of extracting the divided ciphertexts (a constant order of the disjoint factors). The pointwise multiplication unit  230 ′ transfers the final result value of the pointwise multiplication operation to the NTT logic circuit unit  220 ′. 
     Specific details of each component of the homomorphically encrypted message modular multiplier  200 ′ according to the second embodiment may be readily understood by those of ordinary skill in the art to which the present invention pertains based on the description with reference to  FIGS.  1  and  2    ( FIGS.  2 A to  2 F ) and  FIG.  3   . 
       FIG.  5    is a block diagram illustrating a computer system for implementing the method according to the embodiment of the present invention. 
     Referring to  FIG.  5   , a computer system  1000  may include at least one of a processor  1010 , a memory  1030 , an input interface device  1050 , an output interface device  1060 , and a storage device  1040  which communicate via a bus  1070 . The computer system  1000  may further include a transceiver  1020  coupled to a network. The processor  1010  may be a central processing unit (CPU) or a semiconductor device that executes instructions stored in the memory  1030  or the storage device  1040 . The memory  1030  and the storage device  1040  may include various types of volatile or non-volatile storage media. For example, the memory may include a read only memory (ROM) and a random-access memory (RAM). In the embodiment of the present invention, the memory may be positioned inside or outside the processor, and the memory may be connected to the processor through various known units. The memory may include various types of volatile or non-volatile storage media. For example, the memory may include a ROM or a RAM. 
     Therefore, the embodiment of the present invention may be implemented as a method implemented in a computer or as a non-transitory computer-readable medium having computer-executable instructions stored therein. In an embodiment, when the computer-executable instructions are executed by the processor, the computer-executable instructions may perform the method according to at least one aspect of the present invention. 
     The tranceiver  1020  may transmit or receive a wired signal or a wireless signal. 
     Further, the method according to the embodiment of the present invention may be implemented in the form of program instructions that can be executed through various computer units and recorded on computer readable media. 
     The computer readable media may include program instructions, data files, data structures, or combinations thereof. The program instructions recorded on the computer readable media may be specially designed and prepared for the embodiments of the invention or may be available well-known instructions for those skilled in the field of computer software. The computer readable media may include a hardware device configured to store and execute program instructions. Examples of the computer readable media include magnetic media such as a hard disk, a floppy disk, and a magnetic tape, optical media such as a compact disc read only memory (CD-ROM) and a digital video disc (DVD), magneto-optical media such as a floptical disk, and a hardware device, such as a ROM, a RAM, or a flash memory, that is specially made to store and perform the program instructions. Examples of the program instruction include machine code generated by a compiler and high-level language code that can be executed in a computer using an interpreter and the like. 
     For reference, the components according to the embodiment of the present invention may be implemented in the form of hardware, such as a fully homomorphic encryption application specific integrated circuit (ASIC) or the like dedicated to cloud computation, but may also be implemented in a software form. 
     The term “unit” used in the embodiment of the present invention means hardware components such as ASIC or software, and “unit” performs certain roles. However, the “unit” is not meant to be limited to software or hardware. 
     According to an embodiment of the present invention, it is possible to process computational complexity with the number of times of multiplications of a 0 (n log n) level only by point-wise multiplication between coefficients of the same order, not by computational complexity of a O(n 2 ) level required for a multiplication operation between nth-order polynomials, and independently process a modular operation in parallel by dividing a polynomial having a large coefficient value into coefficient values of a small disjoint factor. 
     Therefore, according to the present invention, it is possible to greatly reduce the number of times of multiplication in homomorphic encryption by an NTT logic circuit operator and a CRT logic circuit operator arranged in parallel, and to process multiplication and modular operations between ciphertexts at high speed by allowing each CRT logic circuit operator to independently perform the modular operation in parallel using values in small units obtained by dividing the modulo operation of large coefficient values. 
     Effects which can be achieved by the present invention are not limited to the above-mentioned effects. That is, other objects that are not described may be clearly understood by those skilled in the art to which the present invention pertains from the following description. 
     Although exemplary embodiments of the present invention have been disclosed hereinabove, it may be understood by those skilled in the art that the present invention may be variously modified and altered without departing from the scope and spirit of the present invention described in the following claims.