METHOD AND DEVICE FOR PERFORMING HOMOMORPHIC PERMUTATION

A method of performing a homomorphic permutation by a server includes: generating, via a ciphertext generation portion, a first ciphertext by adding noise to the basic ciphertext; transmitting, via a transmission portion, the first ciphertext to a client; performing, via an operation portion, a predetermined operation on the noise; receiving, via a reception portion, a second ciphertext from the client; and extracting, via an extraction portion, the basic ciphertext on which the predetermined operation is performed, by removing, from the second ciphertext, the noise on which the predetermined operation is performed, wherein the second ciphertext is a ciphertext that is re-encrypted by the client after decrypting the first ciphertext and performing the predetermined operation on the decrypted first ciphertext.

CROSS-REFERENCE TO RELATED APPLICATION

This application is based on and claims priority under 35 U.S.C. § 119 to Korean Patent Application No. 10-2022-0061561, filed on May 19, 2022, in the Korean Intellectual Property Office, the disclosure of which is incorporated by reference herein in its entirety.

BACKGROUND

One or more embodiments relate to mixing of homomorphic encryption and multilateral calculations. More particularly, one or more embodiments relate to a method of performing a homomorphic permutation from among multilateral calculations.

2. Description of the Related Art

Homomorphic rotation refers to an operation performed in an encrypted state to enable a cyclic shift on a vector in which a number of pieces of data are respectively moved with a fixed shift step in cyclic manner. However, it may take a long time to perform a homomorphic rotation in an encrypted state.

Also, a different arithmetic key is required for each rotation step of the homomorphic rotation operation. An arithmetic key occupies a memory of dozens to hundreds of megabytes. Thus, as the number of types of rotation steps increases, the number of arithmetic keys may increase too much, which makes it difficult to manage the memory.

Also, since there is no other permutation than homomorphic rotation, a required permutation has to be realized by synthesis of a number of homomorphic rotation operations. In this case, time required for processing a complex operation may significantly increase.

SUMMARY

According to an embodiment of the disclosure, an operation time required when a cyclic shift is generated, by using communication, in an encrypted state for a homomorphic permutation may be reduced, and the homomorphic permutation may be performed without an arithmetic key. Also, a general permutation may be efficiently performed in an encrypted state without going through homomorphic rotation.

According to one or more embodiments, a method of performing a homomorphic permutation by a server includes: generating, via a ciphertext generation portion, a first ciphertext by adding noise to the basic ciphertext; transmitting, via a transmission portion, the first ciphertext to a client; performing, via an operation portion, a predetermined operation on the noise; receiving, via a reception portion, a second ciphertext from the client; and extracting, via an extraction portion, the basic ciphertext on which the predetermined operation is performed, by removing, from the second ciphertext, the noise, on which the predetermined operation is performed, wherein the second ciphertext is a ciphertext that is re-encrypted by the client after decrypting the first ciphertext and performing the predetermined operation on the decrypted first ciphertext. The terminal may include a server.

The predetermined operation may be a permutation operation.

The predetermined operation may be a cyclic shift operation.

The basic ciphertext may be a ciphertext with respect to original data encrypted by using a homomorphic algorithm.

The noise may be in a form of a polynomial expression extracted from a predetermined uniform distribution.

A server and the client may perform wired or wireless communication with each other.

A server and the client may have a prior agreement with respect to the predetermined operation.

According to one or more embodiments, a method of performing a homomorphic permutation by a client includes: receiving, via a reception portion, a first ciphertext from a server; decrypting, via a decryption portion, the first ciphertext by using a secret key; performing, via an operation portion, a predetermined operation on the decrypted first ciphertext; generating, via a re-encryption portion, a second ciphertext by re-encrypting the first ciphertext on which the predetermined operation is performed; and transmitting, via a transmission portion, the second ciphertext to the server, wherein the first ciphertext is a ciphertext that is modified from a basic ciphertext by the server adding noise to the basic ciphertext.

The predetermined operation may be a permutation operation.

The predetermined operation may be a cyclic shift operation.

According to one or more embodiments, a device for performing a homomorphic permutation includes at least one processor to implement: an ciphertext generation portion configured to generate a first ciphertext by adding noise to the basic ciphertext; a transmission portion configured to transmit the first ciphertext to a terminal; a reception portion configured to receive a second ciphertext from the terminal; an operation portion configured to perform a predetermined operation on the noise; and an extraction portion configured to extract the basic ciphertext on which the predetermined operation is performed, by removing, from the second ciphertext, the noise, on which the predetermined operation is performed; wherein the second ciphertext is a ciphertext that is re-encrypted by the terminal after decrypting the first ciphertext and performing the predetermined operation on the decrypted first ciphertext.

DETAILED DESCRIPTION

Hereinafter, detailed embodiments of the disclosure are described with reference to the drawings. The descriptions in detail below are provided to help comprehensive understanding with respect to a method, a device, and/or a system described in this specification. However, the descriptions are only examples, and the disclosure is not limited thereto.

While describing the embodiments of the disclosure, detailed descriptions about related well known arts are omitted, when it is determined that they may unnecessarily blur the points of the disclosure. The terms used below are defined by taking into account corresponding functions in the disclosure and may be different according to an intention of a user or an operator, a precedent, or the like. Therefore, the definitions of the terms have to be understood based on the general aspects throughout the specification. The terms used in the detailed description are merely used to describe embodiments of the disclosure and shall not be understood as restricting the embodiments. Unless clearly otherwise used, a singular expression denotes a meaning of a plural expression. In the description, it should be understood that the terms, such as “including” or “having,” are intended to indicate the existence of the features, numbers, steps, actions, components, parts, or combinations thereof, and are not intended to preclude the possibility that one or more other features, numbers, steps, actions, components, parts, or combinations thereof may exist or may be added.

FIG.1illustrates a system for performing a homomorphic rotation by using a communication network, according to an embodiment of the disclosure.

The system100illustrated inFIG.1shows an example of performing a homomorphic permutation by using communication between two terminals, that is, a first terminal200and a second terminal300. According to an embodiment of the disclosure, the first terminal200may be a client, and the second terminal300may be a server. According to another embodiment of the disclosure, the first terminal200may be, for example, a data provisioning device provisioning data without disclosing personal information. The second terminal300may be, for example, a data analyzing device or a data processing device analyzing or processing personal information received from the first terminal200. According to another embodiment of the disclosure, the first terminal200refers to a device owning input data of an operation. The first terminal200has a secret key with respect to a ciphertext and does not attempt to disclose information about the secret key to the second terminal300. The second terminal300refers to a device performing operations by using encrypted data of the first terminal200. The second terminal300does not have a secret key with respect to a ciphertext and does not attempt to disclose a calculation process to the first terminal200.

According to another embodiment of the disclosure, the second terminal300may provide an artificial intelligence service by analyzing or processing information provided by the first terminal200without disclosing the information to the outside. For example, the second terminal300may analyze health information of a user of the first terminal200, by using DNA information of the user of the first terminal200, without disclosing the DNA information to the outside.

The first and second terminals200and300may include devices capable of performing communication with external devices and performing encryption by using homomorphic encryption, such as a cellular phone, a smartphone, a smart watch, a hand-held device, a wearable device, a robot, a personal computer (PC), a notebook computer, a tablet PC, etc.

Homomorphic encryption denotes an encryption technique to perform operation on encrypted data. It is an encryption method for performing an arbitrary logical operation or arithmetic operation using encrypted data. When homomorphic encryption is used, data leakage and hacking damage may be prevented. When a plurality of pieces of data are encrypted in one ciphertext and a position of each piece of data has to be changed, a homomorphic permutation and homomorphic multiplication of homomorphic encryption are used. One ciphertext is composed of a number of slots, and each slot has a specified order and occupies a specified position in one ciphertext.

According to an embodiment of the disclosure, the first terminal200and the second terminal300may perform a homomorphic permutation by using wired or wireless communication.

Homomorphic rotation refers to an operation of performing a cyclic shift on an encrypted vector in which a number of pieces of data that are encrypted in one ciphertext are respectively moved with a fixed shift step in cyclic manner, in an encrypted state. When a general permutation operation, except for a cyclic shift, is performed on one ciphertext, a vector containing 0 and 1 is multiplied based on homomorphic multiplication, with respect to each of ciphertexts, on which a cyclic shift of all types of steps corresponding to a shift distance of data is performed. Here, the multiplication is performed by using the vector including 1 with respect to data positioned in an intended position and the vector including 0 with respect to data not positioned in an intended position. Thereafter, homomorphic addition is performed on all of the processed ciphertexts.

According to an embodiment of the disclosure, the first terminal200and the second terminal300may perform communication between each other in order to perform a homomorphic permutation. Referring toFIGS.2and3, a method of performing a homomorphic permutation is described, based on an example in which the first terminal200is a client, and the second terminal300is a server.

FIG.2is a flowchart of homomorphic rotation between the first terminal200and the second terminal300, using a communication network, according to an embodiment of the disclosure.

According to an embodiment of the disclosure, it is assumed that the first terminal200and the second terminal300have a prior agreement on a permutation operation.

As shown inFIG.1, the second terminal300may include a ciphertext generation portion310, a transmission portion320, a first operation portion330, a reception portion340, and an extraction portion350. A process performed by the second terminal300for performing a homomorphic rotation is described first.

Referring toFIG.2, the ciphertext generation portion310may perform noise sampling and encoding of the sampled noise in operation S210. Thereafter, a first ciphertext may be generated by adding first noise to a basic ciphertext in operation S220. The basic ciphertext may refer to a ciphertext with respect to original data encrypted by using a homomorphic algorithm.

The transmission portion320may transmit the first ciphertext to the first terminal200in operation S230.

The first operation portion330may apply a predetermined operation to the noise added by the encryption generation portion310, in operation S240.

The reception portion340may receive a second ciphertext from the first terminal200in operation S250. The second ciphertext may refer to a ciphertext that is re-encrypted by the first terminal200after decrypting the first ciphertext received and then performing, on the decrypted first ciphertext, a predetermined operation previously agreed upon between the first terminal200and the second terminal300.

In operation S260, the extraction portion350may remove, from the received second ciphertext, second noise indicating the noise to which the predetermined operation has been applied by the first operation portion300in operation S240. Thereby, a basic ciphertext is extracted in operation S270.

As shown inFIG.1, the first terminal200may include a reception portion210, a decryption portion220, a second operation portion230, a re-encryption portion240, and a transmission portion250. A process of performing a homomorphic rotation operation by the first terminal200is described below.

Referring toFIG.2, the reception portion210may receive a first ciphertext from the second terminal300in operation S201. The first ciphertext may refer to a ciphertext that is modified from a basic ciphertext by the second terminal300adding noise to the basic ciphertext. The decryption portion220may decrypt the received first ciphertext by using a secret key in operation S202.

The second operation portion230may perform, on the decrypted first ciphertext, a predetermined operation that is agreed upon between the first terminal200and the second terminal300in advance, in operation S203. The re-encryption portion240may generate a second ciphertext by re-encrypting the first ciphertext on which the predetermined operation is performed by the second operation portion230, in operation S204. Then, the transmission portion250may transmit the second ciphertext to the second terminal300.

FIG.3illustrates an example of performing a permutation operation of a homomorphic permutation between a server and a client, according to an embodiment of the disclosure.FIG.3illustrates an example of performing the permutation operation of the homomorphic permutation by using homomorphic encryption. Homomorphic encryption may be homomorphic encryption of Cheon-Kim-Kim-Song (CKKS).

The ciphertext generation portion310may generate a first ciphertext that is modified from a basic ciphertext by adding noise to the basic ciphertext in operations S310and S320. The basic ciphertext may correspond to an input ciphertext on which a permutation is to be performed. Also, with respect to N which is one of the powers of 2, and Q which is a product of large prime numbers, RQmay be a set of all polynomial expressions which may correspond to remaining ones after the polynomial expressions are sequentially divided by Q and XN+1. The basic ciphertext may be composed of two polynomial expressions RQ2included in this set. All ciphertexts described hereinafter may be composed in this way. The basic ciphertext may be assumed as shown in Equation 1.

In the description below, a process of obtaining a polynomial expression r (X) in the set RQby encoding a slot vector (r0, r1, . . . , rn-1) may be frequently used. In this case, with respect to a complex number

a calculation is performed such that after obtaining an n−1thorder polynomial expression r′ (X) of an only real number coefficient, satisfying r′(ζ5j)=rj, with respect to j=0, . . . , n−1, r(X)=└Δ·r′(X)┐∈RQmay be obtained with respect to a predetermined integer Δ. All the following encoding process is defined as below.

The ciphertext generation portion310may sample noise in operation S310. The noise may have a form of a slot vector (r0, r1, . . . , rn-1) and each rimay be represented in the form of a polynomial expression extracted from a uniform distribution in the setQ. Here, the setQrefers to a set of remaining ones of an integer divided by Q. This may be encoded to generate a polynomial expression r (X) of the noise.

Also, the polynomial expression r (X) of the noise may be added to a first polynomial expression b (X) of two polynomial expressions included in the basic ciphertext, as shown in Equation 2.

Thereafter, a first ciphertext, which is modified from the basic ciphertext by adding noise thereto, may be generated in operation S320. The first ciphertext is defined as Equation 3.

The transmission portion320may transmit the first ciphertext ct′=(b′(X), a(X))∈RQ2generated by the ciphertext generation portion310to the first terminal200in operation S330.

The first operation portion330may obtain (rσ(0), rσ(1), . . . , rσ(n-1)) by applying a permutation function σ to the slot vector (r0, r1, . . . , r(n-1)) obtained from the ciphertext generation portion310. Then, second noise r′(X) may be obtained by encoding (rσ(0), rσ(1), . . . , rσ(n-1)) based on a polynomial expression in RQin operation S340. That is, the first operation portion330may apply a predetermined operation previously agreed upon between the first terminal200and the second terminal300to the noise added to the basic ciphertext by the ciphertext generation portion310.

The reception portion340may receive a second ciphertext from the client200in operation S350. The second ciphertext may indicate a ciphertext that is re-encrypted by the first terminal200after decrypting the first ciphertext and then performing, on the decrypted first ciphertext, the predetermined operation previously agreed upon between the first terminal200and the second terminal300. The second ciphertext may be defined as Equation 4.

The extraction portion350may extract the basic ciphertext by removing, from the received second ciphertext, the noise to which the predetermined operation is applied, in operation S360. When the second ciphertext ct″=(b″(X), a″(X)) is received from the first terminal200, second noise r′(X) may be calculated by the first operation portion330and may be removed from a first element b″ (X) of the second ciphertext, to obtainb(X)=b″(X)−r′(X) and composect=(b(X), a″(X))∈RQ2. A vector of (v0, v1, . . . v(n-1)) is derived when m(X) decoding is performed by decrypting the basic ciphertext owned by the server300. Specifically, a vector of (v(σ(0)), v(σ(1)), . . . , v(σ(n-1))), which is permutated from the vector of (v0, v1, . . . , v(n-1)) via the permutation function σ, may be derived, when the extraction portion350decrypts and decodes the extracted basic ciphertext.

According to an embodiment of the disclosure, the client200may include the reception portion210, the decryption portion220, the second operation portion230, the re-encryption portion240, and the transmission portion250.

Referring toFIG.3, the client200may receive a first ciphertext from the server300in operation S301. The first ciphertext may be represented by Equation 3. The decryption portion220of the client200may decrypt the first ciphertext by using a secret key s (X) to calculate b′(x)+a(x)s(x)=m(X)+r(X)=m′(X) in operation S302. Here, m(X) denotes a polynomial expression obtained by encoding a slot vector (v0, v1, . . . , v(n-1)) encrypted in an input basic ciphertext.

The decryption portion220may obtain a slot vector (m′0, m′1, . . . , m′n-1) by decoding the calculated m′(X), in operation S303.

(m′σ(0), m′σ(1), . . . , m′σ(n-1)) may maintain an encrypted state by the slot vector (r0, r1, . . . , r(n-1)) obtained by the encryption generation portion310of the server300, and thus, the client200may not know information of the server300after decryption and decoding.

The re-encryption portion240may encrypt m″(X) to generate a second ciphertext as shown in Equation 4, in operation S304. The transmission portion250may transmit the second cryptogam to the server300in operation S305.

FIG.4is an example of performing, via the first terminal200and the second terminal300, a cyclic shift operation of a homomorphic permutation, according to another embodiment of the disclosure. According to an embodiment of the disclosure, when a vector of (v0, v1, . . . , vn-1) is encrypted by the server300in a basic ciphertext, the server300may, through communication with the client200, attempt to obtain a ciphertext in which a vector (vk, vk+1, . . . , vn-1, v0, . . . , vk−1), which is cyclically shifted by k, is encrypted.FIG.4illustrates a case of using homomorphic encryption of CKKS, according to an embodiment.

For descriptions of homomorphic permutation ofFIG.4that are substantially the same as those of homomorphic permutation ofFIG.3will be omitted.

In operation S403, the second operation portion230of the client200may obtain m′(X5k) by applying a cyclic shift operation by substituting X5kfor X in m′(X). Also, in operation S440, the first operation portion330of the server300may obtain r(X5k) by substituting X5krather than X for r(X), which is a noise element added to a basic ciphertext (S420). Also, this may be converted to an element of RQ′2, which is a space of a new ciphertext. In S450, the server200receives a second ciphertext from the client. In operation S460, noise to which the cyclic shift operation is applied may be removed from the second ciphertext. As a result, a basic ciphertext which is generated by encrypting a cyclic shift vector may be extracted. In detail, when the second ciphertext ct″ is received from the client, r(X5k) may be subtracted from b″(X), which is a first element of the second ciphertext, to obtainb(X)=b″(X)−r(X5k) and composect=(b(X), a″(X))∈RQ′2.

FIG.5illustrates an example of a computing environment including a computing terminal12, according to an embodiment of the disclosure. In the embodiment illustrated inFIG.5, each component may have different functions and capabilities from those described hereinafter. Also, in addition to the descriptions below, additional components may be included.

The computing terminal12may include at least one processor14, a computer-readable storage medium16, and a communication bus18. The processor14may enable the computing terminal12to operate according to example embodiments described above. For example, the processor14may execute one or more programs stored in the computer-readable storage medium16. The one or more programs may include one or more computer-executable instructions, and when the computer-executable instructions are executed by the processor14, the computing terminal12may perform operations according to the example embodiments.

The computer-readable storage medium16may be configured to store computer-executable instructions or program codes, program data, and/or other appropriate type information. A program20stored in the computer-readable storage medium16may include a set of instructions executable by the processor14. According to an embodiment, the computer-readable storage medium16may include a memory (a volatile memory such as random-access memory, a non-volatile memory, or an appropriate combination thereof), one or more magnetic disk storage devices, optical disk storage devices, flash memory devices, other types of storage media accessed by the computing terminal12and capable of storing desired information, or an appropriate combination thereof.

The communication bus18may connect various components of the computing terminal12, including the processor14and the computer-readable storage medium16, to one another. The computing terminal12may also include one or more input and output interfaces22providing an interface for one or more input and output devices24and one or more network communication interfaces26. The one or more input and output interfaces22and the one or more network communication interfaces26may be connected to the communication bus18. The one or more input and output devices24may be connected to other components of the computing terminal12through the one or more input and output interfaces22. Examples of the input and output devices24may include a pointing device (a mouse, a track pad, or the like), an input device, such as a keyboard, a touch input device (a touch pad, a touch screen, or the like), a voice or sound input device, various types of sensor devices and/or capturing devices, and/or an output device, such as a display, a printer, a speaker, and/or a network card. The examples of the input and output devices24may be included in the computing terminal12as a component included in the computing terminal12or may be connected to the computing terminal12as a separate device from the computing device12.

At least one of the components, elements or units (collectively “components” in this paragraph) represented by a block in the drawings, such as the first and second terminals200and300and their components illustrated inFIG.1, may be embodied as various numbers of hardware, software and/or firmware structures that execute respective functions described above, according to embodiments. For example, at least one of these components may use a direct circuit structure, such as a memory, processing, logic, a look-up table, etc. that may execute the respective functions through controls of one or more microprocessors or other control apparatuses. Also, at least one of these components may be specifically embodied by a module, a program, or a part of code, which contains one or more executable instructions for performing specified logic functions. Also, at least one of these components may further include a processor such as a central processing unit (CPU) that performs the respective functions, a microprocessor, or the like. Functional aspects of the above exemplary embodiments may be implemented in algorithms that execute on one or more processors. Furthermore, the components represented by a block or processing steps may employ any number of related art techniques for electronics configuration, signal processing and/or control, data processing and the like.

According to an embodiment of the disclosure, an operation time taken when a cyclic shift occurs in an encrypted state may be reduced, with respect to homomorphic permutation, and without an arithmetic key required for each rotation operation with respect to homomorphic permutation, a cyclic shift or a permutation may be performed.

According to an embodiment of the disclosure, an arbitrary permutation may be performed through one time communication between a server and a client or between a first terminal and a second terminal, and thus, a time for an operation may be reduced.