METHOD AND DEVICE FOR MULTI-KEY HOMOMORPHIC ENCRYPTION

Abstract

A device for performing multi-key homomorphic encryption includes a public key generator configured to generate a public key by using a secret key for each client, and a multiplication key generator configured to generate a multiplication key by reusing a public key protection error used in the generating of the public key. By reducing the size of the multiplication key by reusing the public key protection error, the operation time and memory may be reduced.

Claims

1. A device for performing multi-key homomorphic encryption, the device comprising: a public key generator configured to generate a public key by using a secret key for each client; and a multiplication key generator configured to generate a multiplication key by reusing a public key protection error used in the generating of the public key.

2. The device of claim 1, wherein the multiplication key is generated using a modified Ring Learning with Error (RLWE) sample, and the modified RLWE sample is defined in the form of(α,−αs+x, αx+e), where a denotes an element selected from a uniform distribution on Rq, s denotes a secret key distribution, and x and e denote an error distribution.

3. The device of claim 1, wherein the public key is defined in the form that pk.sub.i=(α,b.sub.i=−α.Math.s.sub.i+x.sub.i), where a denotes an element selected from a uniform distribution on Rq, s.sub.i denotes a secret key, and x.sub.i denotes the public key protection error.

4. The device of claim 1, wherein the public key is that mk.sub.i=α.Math.x.sub.i+e.sub.i+P.Math.s.sub.i, where a denotes an element selected from a uniform distribution on Rq, s.sub.i denotes a secret key, and x.sub.i denotes the public key protection error, and e.sub.i denotes a multiplication key protection error.

5. The device of claim 4, wherein, when prior communication between the clients is possible, a common multiplication key that $=\underset{i=0}{\overset{k-1}{.Math.}}{\mathrm{mk}}_i,$ mk.sub.i=α.Math.x.sub.i+e.sub.i+P.Math.s.sub.i is generated with respect to all multiplication keys.

6. A device for performing multi-key homomorphic encryption, the device comprising: a secret key generator configured to generate a secret key; a public key protection error selector configured to select a public key protection error from an error distribution; a public key generator configured to generate a public key by using the secret key and the public key protection error; a multiplication key protection error selector configured to select a multiplication key protection error from the error distribution; and a multiplication key generator configured to generate a multiplication key by using the secret key, the public key protection error, and the multiplication key protection error.

7. The device of claim 6, wherein the secret key is generated using a modified Ring Learning with Error (RLWE) sample, and the modified RLWE sample is defined in the form of (α, −αs+x, αx+e), and generates the multiplication key, where a denotes an element selected from a uniform distribution on Rq, s denotes a secret key distribution, x denotes a public key protection error, and e denotes a multiplication key protection error.

8. A method of performing multi-key homomorphic encryption, the method comprising: generating, by a public key generator, a public key by using a secret key for each client; and generating, by a multiplication key generator, a multiplication key by reusing a public key protection error used in the generating of the public key.

9. The method of claim 8, wherein the multiplication key is generated using a modified Ring Learning with Error (RLWE) sample, and the modified RLWE sample is defined in the form of (α, −αs+x, αx+e), where a denotes an element selected from a uniform distribution on Rq, s denotes a secret key distribution, and x and e denote an error distribution.

10. The method of claim 8, wherein the public key is defined in the form that pk.sub.i=(α,b.sub.i=−α.Math.s.sub.i+x.sub.i), and a denotes an element selected from a uniform distribution on Rq, s.sub.i denotes a secret key, and x.sub.i denotes the public key protection error.

11. The method of claim 8, wherein the public key is that mk.sub.i=α.Math.x.sub.i+e.sub.i+P.Math.s.sub.i, and a denotes an element selected from a uniform distribution on Rq, s.sub.i denotes a secret key, and x.sub.i denotes the public key protection error, and e.sub.i denotes a multiplication key protection error.

12. The method of claim 11, wherein, when prior communication between the clients is possible, a common multiplication key that $=\underset{i=0}{\overset{k-1}{.Math.}}{\mathrm{mk}}_i,$ mk.sub.i=α.Math.x.sub.i+e.sub.i+P.Math.s.sub.i is generated with respect to all multiplication keys.

13. A computer-readable recording medium having recorded thereon a program for executing the method of claim 8.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0014] The above and other aspects, features, and advantages of certain embodiments of the disclosure will be more apparent from the following description taken in conjunction with the accompanying drawings, in which:

[0015] FIG. 1 illustrates an example of performing multi-key homomorphic encryption when prior communication between clients is impossible in a Ring Learning with Error (RLWE)-based multi-key homomorphic encryption system;

[0016] FIG. 2 illustrates an internal configuration of a device for performing multi-key homomorphic encryption, according to an embodiment; and

[0017] FIG. 3 illustrates an example of generating a multiplication key through multi-key homomorphic encryption when prior communication between clients is impossible, according to an embodiment.

DETAILED DESCRIPTION

[0018] Reference will now be made in detail to embodiments, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to like elements throughout. In this regard, the present embodiments may have different forms and should not be construed as being limited to the descriptions set forth herein. Accordingly, the embodiments are merely described below, by referring to the figures, to explain aspects of the present description. As used herein, the term “and/or” includes any and all combinations of one or more of the associated listed items. Expressions such as “at least one of,” when preceding a list of elements, modify the entire list of elements and do not modify the individual elements of the list.

[0019] Hereinafter, the disclosure is described with reference to the drawings.

[0020] FIG. 1 illustrates an example of performing multi-key homomorphic encryption when prior communication between users is impossible in a Ring Learning with Error (RLWE)-based multi-key homomorphic encryption system 100.

[0021] The multi-key homomorphic encryption system 100 includes clients 110, 112, and 114 and a server 120. The clients 110, 112, and 114 and the server 120 each include a processor and a memory.

[0022] The server 120 may perform homomorphic encryption according to a Learning with Error (LWE)-based encryption method, and may perform an arithmetic operation through a homomorphic encryption operation unit 122, by using homomorphic encryption according to a Ring Learning with Error (RLWE)-based encryption method.

[0023] The server 120 requires a public key and a multiplication key of each client in order to perform a multiplication operation on two ciphertexts of the multi-key homomorphic encryption system 100.

[0024] A common public key and a common multiplication key are used when prior communication is possible between clients in a RLWE-based multi-key homomorphic encryption system.

[00002]$\widehat{pk}=\left(a,b=\underset{i=0}{\overset{k-1}{.Math.}}{b}_i\right)=\left(a,-a.Math.\underset{i=0}{\overset{k-1}{.Math.}}{s}_i+\underset{i=0}{\overset{k-1}{.Math.}}{x}_i\right)=\left(a,-a.Math.s+x\right)$$\widehat{\mathrm{mk}}=\left({\widehat{\mathrm{mk}}}_{0_i},{\widehat{\mathrm{mk}}}_1\right)=\left({\widehat{\mathrm{mk}}}_0=\underset{i=0}{\overset{k-1}{.Math.}}{\mathrm{mk}}_{i,0},{\widehat{\mathrm{mk}}}_1=\underset{i=0}{\overset{k-1}{.Math.}}{\mathrm{mk}}_{i,1}\right)$

[0025] However, as in the example illustrated in FIG. 1, when prior communication between clients is impossible, the clients 110, 112, and 114 each transmit a public key pk.sub.i, a multiplication key mk.sub.i, and a cipher text ct.sub.i to the server 120, and the homomorphic encryption operation unit 122 of the server 120 performs a homomorphic encryption operation and transmits a generated cipher text ct to each of the clients 110, 112, and 114. Then, the clients 110, 112, and 114 perform decryption by cooperating with each other.

[0026] Here, when the number of clients increases, the number of the public keys pk.sub.i and the multiplication keys mk.sub.i of the clients 110, 112, and 114 that the server 120 has to possess increases, resulting in an increase in memory usage. In addition, when communication between the clients 110, 112, and 114 is impossible, all homomorphic operations is to be performed by the server 120, and the operation time for the multiplication operation becomes long.

[0027] Referring to FIG. 1, a method of performing RLWE-based multi-key homomorphic encryption when communication between clients is impossible is described.

[0028] In order to perform multi-key homomorphic encryption, each of the clients 110, 112, and 114 generates ciphertext moduli q.sub.0,q.sub.1, . . . q.sub.L and special moduli p.sub.0,p.sub.1, . . . ,p.sub.K. In this case, a format of a RLWE sample is defined as follows.

(α,−αs+x),α←R.sub.Q,s←χ.sub.Key,x←χ.sub.err

[0029] , where a denotes an element that all clients need to be sharing, and is selected from a uniform distribution defined on R.sub.Q*R.sub.P, and s denotes a secret key distribution, and e denotes an error distribution. Here, R.sub.Q*R.sub.P=R.sub.q0× . . . ×R.sub.qL×R.sub.p0× . . . ×R.sub.pK, and

[00003]$Q=\underset{i=0}{\overset{L}{.Math.}}{q}_i,\mathrm{and}P=\underset{i=0}{\overset{K}{.Math.}}{p}_i.$

[0030] Each client generates a secret key s.sub.i through a RLWE sample, and generates a public key pk.sub.i and a multiplication key mk.sub.i by using the secret key s.sub.i.

pk.sub.i=(α,b.sub.i=−α.Math.s.sub.i+x.sub.i),mk.sub.i=(mk.sub.i,0,mk.sub.i,1,mk.sub.i,2)

[0031] Each element of the multiplication key mk.sub.i is as follows.

[0032] mk.sub.i,0 is selected from the uniform distribution defined on R.sub.Q*R.sub.P.

mk.sub.i,1=−s.sub.i.Math.mk.sub.i,0+e.sub.i,1+P.Math.r.sub.i

mk.sub.i,2=−r.sub.i.Math.α+e.sub.i,2+P.Math.s.sub.i

e.sub.i,1 and e.sub.i,2 denote an error distribution on R.sub.Q, r.sub.i←X, and r.sub.i is selected from a key distribution. For example, r.sub.i is selected from the secret key distribution, and n is removed during a multiplication operation to function as a temporary secret key used to perform the multiplication operation.

[0033] When prior communication between the clients 110, 112, and 114 is impossible, as illustrated in the example illustrated in FIG. 1, the public key pk.sub.i=(α,b.sub.i=−as.sub.i+x.sub.i) and the multiplication key mk.sub.i=(mk.sub.i,0,mk.sub.i,1,mk.sub.i,2) that the server 120 has to possess becomes massive. In addition, when a client uses an electronic device having, for example, a memory with limited resources, such as a mobile phone, generating a key for homomorphic operation may be burdensome.

[0034] In order to solve this problem, in an embodiment, a public key protection error used when generating a RLWE sample may be reused to reduce the size of the multiplication key and reduce the operation time. This will be described with reference to FIG. 2.

[0035] FIG. 2 illustrates an internal configuration of a device 200 for performing multi-key homomorphic encryption, according to an embodiment.

[0036] The device 200 for performing multi-key homomorphic encryption is implemented in a Re-RLWE environment. The Re-RLWE environment refers to a modified environment in which an error used when generating a RLWE sample is reused. A format of a Re-RLWE sample is defined as follows.

(α.sub.i−αs+x.sub.iαx+e),α←R.sub.Q,s←χ.sup.key,x.sub.ie←χ.sub.err

, where a is an element selected from a uniform distribution on R.sub.Q, s is a secret key distribution, and x and e denote an error distribution on R.sub.Q, and x represents a public key protection error, and e represents a multiplication key protection error. The public key protection error and the multiplication key protection error are selected from an arbitrary key distribution, and an example of the arbitrary key distribution includes a Discrete Gaussian Distribution.

[0037] The device 200 for performing multi-key homomorphic encryption includes a secret key generator 210, a public key generator 220, a public key protection error selector 230, a multiplication key generator 240, and a multiplication key protection error selector 250.

[0038] The secret key generator 210 generates a secret key s.sub.i through the Re-RLWE sample. Unlike the RLWE sample, by adding ax+e to the Re-RLWE sample, the size of a multiplication key may be reduced.

[0039] For example, when communication between clients is difficult, in order to perform multiplication of RLWE multi-key homomorphic encryption, a public key pk.sub.i=(α,b.sub.i=−α.Math.s.sub.i+x.sub.i) and a multiplication key mk.sub.i=(a′,b′,c′)=′)=(mk.sub.0,mk.sub.1,mk.sub.2) were required. However, according to an embodiment, in order to perform multiplication of RLWE multi-key homomorphic encryption when communication between clients is difficult, the public key pk.sub.i=(α, b.sub.i=−α.Math.s.sub.i+x.sub.i) and the multiplication key mk.sub.i=c=ax+e are required. That is, in the related art, there are multiplication keys(mk.sub.0,mk.sub.1,mk.sub.2), requiring three elements, but in the disclosure, the multiplication key is reduced to one element, mk.sub.i, and thus, the size of the multiplication key is reduced.

[0040] The public key generator 220 generates a public key pk.sub.i=(α, b.sub.i=−α.Math.s.sub.i+x.sub.i) by using the secret key s.sub.i and a public key protection error x.sub.i selected by the public key protection error selector 230.

[0041] The multiplication key generator 240 generates a multiplication key mk.sub.i=α.Math.x.sub.i+e.sub.i+P.Math.s.sub.i by using the secret key s.sub.i, the public key protection error x.sub.i, and the multiplication key protection error e.sub.i selected by the multiplication key protection error selector 250. In other words, the public key protection error x.sub.i that is used when generating the public key pk.sub.i=(α, b.sub.i=−α.Math.s.sub.i+x.sub.i) is reused when generating a multiplication key to thereby reduce the size of the multiplication key. The multiplication key protection error selector 250 selects the multiplication key protection error e.sub.i from e←χ.sub.err. For example, the multiplication key protection error e.sub.i may be selected from a Discrete Gaussian Distribution.

[0042] In the multiplication key mk.sub.i=α.Math.x.sub.i+e.sub.i+P.Math.s.sub.i, α.Math.x.sub.i, and e.sub.i are elements constituting a Re-RLWE sample. e.sub.i denotes a multiplication key protection error, and it is not easy to find the public key protection error x.sub.i through e.sub.i, making the entire distribution appear as a uniform distribution. P is a variable to prevent an error value from rapidly increasing when multiplication is performed in a homomorphic encryption operation.

[0043] The multiplication key generator 240 generates a common multiplication key that

[00004]$=\underset{i=0}{\overset{k-1}{.Math.}}{\mathrm{mk}}_i$

for all multiplication keys when prior communication is possible between clients. k denotes the number of clients.

[0044] FIG. 3 illustrates a multiplication key in each of a RLWE environment and a Re-RLWE environment when prior communication between clients is impossible, according to an embodiment.

[0045] In the related art, when prior communication between clients is impossible, a client 310 generates a secret key, public keys a and b, and multiplication keys(mk.sub.0,mk.sub.1,mk.sub.2). In an embodiment, a client 320 generates a secret key, public keys a and b, and a modified multiplication key mk.sub.i, and accordingly, the multiplication keys of the related art (mk.sub.0,mk.sub.1,mk.sub.2) are changed to mk.sub.i, and the size of the multiplication keys is reduced to ⅓.

[0046] Even when prior communication between clients is possible, according to the related art, a clients generates a secret key, public keys a and b, and multiplication keys ({circumflex over (m)}k.sub.0, {circumflex over (m)}k.sub.1). In an embodiment, a client generates a secret key, public keys a and b, and a multiplication key mk.sub.i, and accordingly, the multiplication keys of the related art ({circumflex over (m)}k.sub.0,{circumflex over (m)}k.sub.1) are changed to mk.sub.i, and the size of the multiplication keys is reduced by ½.

[0047] The device described above may be implemented as hardware components, software components, and/or a combination of hardware components and software components. For example, devices and components described in the embodiments may be realized by using at least one or more general-use computers or special-purpose computers, such as a processor, a controller, an arithmetic logic unit (ALU), a digital signal processor, a microcomputer, a field programmable gate array (FPGA), a programmable logic unit (PLU), microprocessor, or any other device that may execute and respond to an instruction. A processing apparatus may execute an operating system (OS) and one or more software applications running on the OS. In addition, the processing apparatus may access, store, manipulate, process, and generate data in response to execution of software. For ease of understanding, it may be described that a single processing apparatus is used, but one of ordinary skill in the art will be aware that the processing apparatus may include a plurality of processing elements and/or a plurality of types of processing elements. For example, the processing apparatus may include a plurality of processors or a single processor, and a controller. The processing apparatus may have another processing configuration, such as a parallel processor.

[0048] A method according to an embodiment may be embodied as program commands executable by various computer means and may be recorded on a computer-readable recording medium. The computer-readable recording medium may include program commands, data files, data structures, and the like separately or in combinations. The program commands recorded on the computer-readable recording medium may be specially designed and configured for the embodiments or may be well-known to and be usable by one of ordinary skill in the art of computer software. Examples of the computer-readable recording medium include a magnetic medium such as a hard disk, a floppy disk, or a magnetic tape, an optical medium such as a CD-ROM or a DVD, a magneto-optical medium such as a floptical disk, and a hardware device specially configured to store and execute program commands such as a ROM, a RAM, or a flash memory. Examples of the program commands include high-level language codes that may be executed by a computer by using an interpreter or the like as well as machine language codes made by a compiler.

[0049] According to the method of generating a multiplication key by reusing an error in multi-key homomorphic encryption, as an embodiment, the size of the multiplication key may be reduced, thereby reducing the usage amount of memory by a client and a server.

[0050] In addition, in multi-key homomorphic encryption without using inter-client communication, ModUp and ModDown operations are required twice each to perform one homomorphic multiplication in an existing method. However, according to the multi-key homomorphic encryption method according to an embodiment, the size of a multiplication key may be reduced, and also a ModUp operation and a ModDown operation are required only once, thereby reducing the entire multiplication operation time.

[0051] While the disclosure has been particularly shown and described with reference to examples thereof, it will be understood by those of ordinary skill in the art that various changes in form and details may be made therein without departing from the spirit and scope of the disclosure as defined by the following claims. For example, an appropriate result may be attained even when the above-described techniques are performed in a different order from the above-described method, and/or components, such as the above-described system, structure, device, and circuit, are coupled or combined in a different form from the above-described methods or substituted for or replaced by other components or equivalents thereof. Therefore, other implementations, other embodiments, and equivalents of the claims fall within the scope of the claims.

[0052] It should be understood that embodiments described herein should be considered in a descriptive sense only and not for purposes of limitation. Descriptions of features or aspects within each embodiment should typically be considered as available for other similar features or aspects in other embodiments. While one or more embodiments have been described with reference to the figures, it will be understood by those of ordinary skill in the art that various changes in form and details may be made therein without departing from the spirit and scope of the disclosure as defined by the following claims.