KR102821562B1 - Apparatus for sorting of homomorphic encrypted data and method thereof - Google Patents

Abstract

A method for processing homomorphic ciphertexts is disclosed. The method for processing homomorphic ciphertexts includes the steps of dividing a plurality of homomorphic ciphertexts into a plurality of groups, the step of performing sorting for each of the divided groups, the step of selecting a candidate homomorphic ciphertext corresponding to a sorting order from among the plurality of homomorphic ciphertexts sorted for each group, and the step of determining a homomorphic ciphertext corresponding to the sorting order by performing a homomorphic operation on the selected candidate homomorphic ciphertexts.

Description

{APPARATUS FOR SORTING OF HOMOMORPHIC ENCRYPTED DATA AND METHOD THEREOF}

The present disclosure relates to a sorting device and method for homomorphic ciphertexts, and more particularly, to a sorting device and method that performs sorting by comparing maximum values of candidate homomorphic ciphertexts corresponding to the order to be sorted, in order to efficiently perform sorting of homomorphic ciphertexts.

As communication technology develops and electronic devices become more widespread, efforts are continuously being made to maintain communication security between electronic devices. Accordingly, encryption/decryption technology is used in most communication environments.

When a message encrypted by encryption technology is transmitted to the other party, the other party must perform decryption in order to use the message. In this case, the other party wastes resources and time in the process of decrypting the encrypted data. In addition, there is also the problem that if a third party hacks while the other party temporarily decrypts the message for calculation, the message can be easily leaked to the third party.

To solve this problem, homomorphic encryption methods are being studied. Using homomorphic encryption, even if encrypted information is not decrypted and calculations are performed on the ciphertext itself, the same result as the encrypted value obtained after calculating on the plaintext can be obtained. Therefore, various calculations can be performed without decrypting the ciphertext.

Homomorphic ciphertexts have recently been required to be aligned, as alignment is required for operations such as k-means clustering, top-k data operations, binning, and statistical analysis.

However, the operations of homomorphic ciphertexts only support limited basic operations such as addition and multiplication, and since conventionally widely used methods such as Quick Sort and Merge Sort consist of repeating the process of determining the next target to be compared with the comparison result of the previous step, a sorting algorithm suitable for homomorphic ciphertexts was required.

Accordingly, the present disclosure is designed to solve the above-described problems, and provides a sorting device and method that performs sorting through maximum value comparison for candidate homomorphic ciphertexts corresponding to the order to be sorted.

The present disclosure is to achieve the above-described purpose, and a method for processing homomorphic ciphertext according to an embodiment of the present disclosure includes the steps of dividing a plurality of homomorphic ciphertexts into a plurality of groups, performing sorting for each of the divided groups, selecting a candidate homomorphic ciphertext corresponding to a sorting order among the plurality of homomorphic ciphertexts sorted for each group, and determining a homomorphic ciphertext corresponding to the sorting order through a homomorphic operation on the selected candidate homomorphic ciphertexts.

In this case, the step of selecting the candidate homomorphic ciphertext may include the step of calculating a first order for the first group and a second order for the second group corresponding to the sorting order, the step of comparing the first homomorphic ciphertext corresponding to the first order in the first group with the second homomorphic ciphertext corresponding to the second order in the second group, and the step of determining the candidate homomorphic ciphertext for which the sorting order is possible based on the comparison result.

In this case, the step of calculating the above order can calculate the lower integer value of the value obtained by dividing the above sort order by 2 as the first order, and the higher integer value of the value obtained by dividing the above sort order by 2 as the second order.

In this case, the step of determining the candidate homomorphic ciphertext may include determining, as the candidate homomorphic ciphertext, a homomorphic ciphertext in the first group having a size smaller than the first homomorphic ciphertext corresponding to the first order, a second homomorphic ciphertext corresponding to the second order, and a homomorphic ciphertext in the second group having a size larger than the second homomorphic ciphertext, if the first homomorphic ciphertext is larger than the second homomorphic ciphertext and is sorted in descending order.

Meanwhile, the step of determining a homomorphic ciphertext corresponding to the above-mentioned sorting order can determine a homomorphic ciphertext corresponding to the above-mentioned sorting order by using a comparison function that selectively outputs a larger homomorphic ciphertext or a smaller homomorphic ciphertext among two input homomorphic ciphertexts, and outputting a comparison function between the selected candidate homomorphic ciphertexts.

Meanwhile, the method for processing homomorphic ciphertexts may further include a step of sorting a plurality of homomorphic ciphertexts within the two groups by repeating the step of selecting the candidate homomorphic ciphertexts as many times as the number of homomorphic ciphertexts included in two groups among the plurality of groups and the step of determining a homomorphic ciphertext corresponding to the sorting order.

Meanwhile, the step of performing sorting by the above-mentioned separated groups can sort multiple homomorphic ciphertexts by group using a k-way sorter capable of sorting three or more homomorphic ciphertexts in one stage.

In this case, the step of dividing into the plurality of groups can divide into the plurality of groups corresponding to the alignment units of the k-way sorter.

Meanwhile, an electronic device according to an embodiment of the present disclosure includes a memory that stores a plurality of homomorphic ciphertexts, and a processor that sorts the plurality of homomorphic ciphertexts, wherein the processor can divide the plurality of homomorphic ciphertexts into a plurality of groups, perform sorting for each of the divided groups, select a candidate homomorphic ciphertext corresponding to a sorting order among the plurality of homomorphic ciphertexts sorted for each group, and determine a homomorphic ciphertext corresponding to the sorting order through a homomorphic operation on the selected candidate homomorphic ciphertexts.

In this case, the processor may calculate a first order for the first group corresponding to the sorting order, a second order for the second group, compare a first homomorphic ciphertext corresponding to the first order in the first group with a second homomorphic ciphertext corresponding to the second order in the second group, and determine a candidate homomorphic ciphertext for which the sorting order is possible based on the comparison result.

In this case, the processor can produce a lower integer value of the sorting order divided by 2 as a first order, and a higher integer value of the sorting order divided by 2 as a second order.

In this case, if the first homomorphic ciphertext is larger than the second homomorphic ciphertext and is sorted in descending order, the processor can determine a homomorphic ciphertext in the first group having a size smaller than the first homomorphic ciphertext corresponding to the first order, a second homomorphic ciphertext corresponding to the second order, and a homomorphic ciphertext in the second group having a size larger than the second homomorphic ciphertext as candidate homomorphic ciphertexts.

Meanwhile, the processor can determine a homomorphic ciphertext corresponding to the sorting order through the output of a comparison function between the selected candidate homomorphic ciphertexts by using a comparison function that selectively outputs a larger homomorphic ciphertext or a smaller homomorphic ciphertext among two input homomorphic ciphertexts.

Meanwhile, the processor may sort a plurality of homomorphic ciphertexts within the two groups by repeating the step of selecting the candidate homomorphic ciphertexts as many as the number of homomorphic ciphertexts included in two groups among the plurality of groups and the step of determining a homomorphic ciphertext corresponding to the sorting order.

Meanwhile, the processor can sort multiple homomorphic ciphertexts by group using a k-way sorter capable of sorting three or more homomorphic ciphertexts in one stage.

In this case, the processor can be divided into a plurality of groups corresponding to the alignment units of the k-way sorter.

Meanwhile, in a computer-readable recording medium including a program for executing a method for processing homomorphic ciphertext according to an embodiment of the present disclosure, the method for processing homomorphic ciphertext includes the steps of: dividing a plurality of homomorphic ciphertexts into a plurality of groups; performing sorting for each of the divided groups; selecting a candidate homomorphic ciphertext corresponding to a sorting order among the plurality of homomorphic ciphertexts sorted for each group; and determining a homomorphic ciphertext corresponding to the sorting order through a homomorphic operation on the selected candidate homomorphic ciphertexts.

According to various embodiments of the present disclosure as described above, sorting can be performed on a large amount of homomorphic ciphertexts, and the sorting can be performed using a comparison function consisting of additions and multiplications, so that the sorting can be performed with a lower computational depth than before, enabling faster computation.

FIG. 1 is a drawing for explaining the structure of a network system according to one embodiment of the present disclosure;
FIG. 2 is a block diagram showing the configuration of a computational device according to one embodiment of the present disclosure;
FIG. 3 is a drawing for explaining the alignment operation of the calculation device of the present disclosure;
Figure 4 is a diagram illustrating the forms of various composite functions related to the sign function.
FIG. 5 is a diagram illustrating an algorithm for selecting a homomorphic ciphertext corresponding to a specific sorting sequence according to an embodiment of the present disclosure;
FIG. 6 is a diagram for explaining the operation of a k-sorter according to one embodiment of the present disclosure;
FIG. 7 is a diagram for explaining a sorting algorithm according to one embodiment of the present disclosure;
Figure 8 is a drawing for explaining the operation when using a 3-way alignment network.
Figure 9 is a drawing for explaining the operation when using a 5-way alignment network.
Figure 10 is a diagram for explaining an example of alignment for 25 homomorphic ciphertexts.
Figure 11 is a drawing for explaining the stage type.
FIG. 12 is a drawing for explaining the parallel processing operation of the sorter of the present disclosure, and
FIG. 13 is a flowchart illustrating a cryptographic operation method according to one embodiment of the present disclosure.

Hereinafter, the present disclosure will be described in detail with reference to the attached drawings. The information (data) transmission process performed in the present disclosure may apply encryption/decryption as needed, and expressions describing the information (data) transmission process in the present disclosure and patent claims should be interpreted to include cases of encryption/decryption even if not mentioned separately. Expressions in the form of "transmitting (transmitting) from A to B" or "A receiving from B" in the present disclosure include cases where another medium is included in the transmission (transmitting) or reception, and do not necessarily express only direct transmission (transmitting) or reception from A to B.

In the description of the present disclosure, the order of each step should be understood as non-limiting, unless a preceding step must be performed logically and temporally before a succeeding step. That is, except for the exceptional cases mentioned above, even if a process described as a succeeding step is performed before a process described as a preceding step, the essence of the disclosure is not affected, and the scope of rights should be defined regardless of the order of the steps. In addition, the description of "A or B" in this specification is defined to mean not only selectively referring to either A or B, but also including both A and B. In addition, the term "including" in this disclosure has a comprehensive meaning that includes other components in addition to the elements listed as including.

In this disclosure, only essential components necessary for the description of the present disclosure are described, and components that are not related to the essence of the present disclosure are not mentioned. In addition, it should not be interpreted as an exclusive meaning that includes only the mentioned components, but should be interpreted as a non-exclusive meaning that may also include other components.

And in the present disclosure, the term “value” is defined as a concept that includes not only a scalar value but also a vector.

In this disclosure, the sorting is explained assuming that it is performed in descending order, but it may be performed in ascending order during implementation.

The mathematical operations and calculations of each step of the present disclosure described below can be implemented as computer operations by a known coding method for performing the corresponding operations or calculations and/or by coding designed to suit the present disclosure.

The specific mathematical formulas described below are provided as examples among several possible alternatives, and the scope of the rights of the present disclosure should not be construed as being limited to the mathematical formulas mentioned in the present disclosure.

For convenience of explanation, the following notation is used in this disclosure.

a ← D: Select an element (a) according to the distribution (D)

s1, s2 ∈ R : S1 and S2 are each elements belonging to the set R.

mod(q) : Modular operation with q elements

: 내부 값을 반올림함

: Round internal values

: 내부 값을 내림함

: Rounds down internal values

: 내부 값을 올림함

: Round up internal values

Hereinafter, various embodiments of the present disclosure will be described in detail using the attached drawings.

FIG. 1 is a diagram showing the configuration of a network system according to one embodiment of the present disclosure.

Referring to FIG. 1, the network system may include a plurality of electronic devices (100-1 to 100-n), a first server device (200), and a second server device (300), and each component may be connected to each other through a network (10).

The network (10) can be implemented as various types of wired/wireless communication networks, broadcast communication networks, optical communication networks, cloud networks, etc., and each device can be connected without a separate medium through methods such as Wi-Fi, Bluetooth, NFC (Near Field Communication), etc.

In Fig. 1, a plurality of electronic devices (100-1 to 100-n) are illustrated, but it is not necessary to use a plurality of electronic devices, and a single device may be used. For example, the electronic devices (100-1 to 100-n) may be implemented in various forms of devices such as smartphones, tablets, game players, PCs, laptop PCs, home servers, kiosks, etc., and may also be implemented in the form of home appliances with IoT functions applied.

A user can input various information through the electronic devices (100-1 to 100-n) that he or she uses. The input information may be stored in the electronic devices (100-1 to 100-n) themselves, but may also be transmitted to and stored in an external device for reasons such as storage capacity and security. In Fig. 1, the first server device (200) may perform a role of storing such information, and the second server device (300) may perform a role of utilizing some or all of the information stored in the first server device (200).

Each electronic device (100-1 to 100-n) can homomorphically encrypt input information and transmit the homomorphic ciphertext to the first server device (200).

Each electronic device (100-1 to 100-n) can include encryption noise, i.e., errors, generated in the process of performing homomorphic encryption in the ciphertext. Specifically, the homomorphic ciphertext generated by each electronic device (100-1 to 100-n) can be generated in a form in which a result value including a message and an error value is restored when decrypted later using a secret key.

For example, a homomorphic ciphertext generated in an electronic device (100-1 to 100-n) can be generated in a form that satisfies the following properties when decrypted using a secret key.

[Mathematical Formula 1]

Dec(ct, sk) = <ct, sk> = M+e(mod q)

Here, < , > represent the usual inner product, ct represents the ciphertext, sk represents the secret key, M represents the plaintext message, e represents the encrypted error value, and mod q represents the modulus of the ciphertext. q should be chosen so that the scaling factor (Δ) is larger than the result M multiplied by the message. If the absolute value of the error value e is sufficiently smaller than M, the decrypted value M+e of the ciphertext is a value that can replace the original message with the same precision in the calculation of significant digits. In the decrypted data, the error is placed on the least significant bit (LSB) side, and M can be placed on the next lowest bit side.

If the size of the message is too small or too large, the size can be adjusted using a scaling factor. Using a scaling factor allows encryption of not only integer-type messages but also real-type messages, which greatly increases usability. In addition, by adjusting the size of the message using a scaling factor, the size of the area where messages exist in the ciphertext after the operation is performed, i.e., the effective area, can also be adjusted.

Depending on the embodiment, the ciphertext modulus q can be set and used in various forms. For example, the modulus of the ciphertext can be set in the form of q=Δ ^L , an exponentiation of a scaling factor Δ. If Δ is 2, q=2 ¹⁰ can be set as a value.

Meanwhile, the storage method for messages can be largely divided into two. One is bit-based storage, and the other is word-based storage. Bit-based storage is a method of encrypting data in bit units, and has the advantage of logical operations. However, since this method only supports bit-based operations, it is inefficient for arithmetic operations between multi-bit numbers (or word-sized numbers). In other words, if stored in bit units, many operations are required when processing multi-bit numbers, and the resulting computational cost is similar to that of storing in word units.

In this respect, the message storage method of the present disclosure is explained on the premise that it is performed in word units. However, when implemented, since bit-unit storage also has advantages in logical operations, that is, in an environment where many logical operations are required, the bit-unit storage method may be used.

The first server device (200) can store the received homomorphic ciphertext in an ciphertext state without decrypting it.

The second server device (300) can request a specific processing result for a homomorphic ciphertext from the first server device (200). The first server device (200) can perform a specific operation according to the request of the second server device (300) and then transmit the result to the second server device (300).

For example, if ciphertexts ct1 and ct2 transmitted by two electronic devices (100-1, 100-2) are stored in the first server device (200), the second server device (300) can request the first server device (200) for a value obtained by adding up the information provided from the two electronic devices (100-1, 100-2). The first server device (200) can perform an operation to add up the two ciphertexts according to the request and then transmit the resulting value (ct1 + ct2) to the second server device (300).

Due to the nature of homomorphic ciphertext, the first server device (200) can perform an operation without decryption, and the resulting value also becomes a ciphertext. In this disclosure, the resulting value obtained by the operation is referred to as an operation result ciphertext.

The first server device (200) can transmit the calculation result ciphertext to the second server device (300). The second server device (300) can decrypt the received calculation result ciphertext and obtain the calculation result values of the data included in each homomorphic ciphertext.

The operation for such homomorphic ciphertexts may be not only an operation formula consisting of addition, subtraction, and multiplication, but also a comparison operation such as calculating a maximum value, calculating a minimum value, and comparing sizes. In addition, it may be an alignment for multiple homomorphic ciphertexts using a comparison operation. In this way, the first server device (200) may be referred to as an arithmetic device in that it can perform an arithmetic operation. A specific alignment method will be described later with reference to FIG. 3.

And the first server device (200) can perform a bootstrapping operation when the approximate message weight exceeds a threshold. The bootstrapping operation will be described later with reference to FIG. 3.

Meanwhile, in Fig. 1, a case is illustrated where encryption is performed in the first electronic device and the second electronic device, and decryption is performed in the second server device, but it is not limited thereto.

FIG. 2 is a block diagram showing the configuration of a computing device according to one embodiment of the present disclosure.

Specifically, in the system of Fig. 1, a device performing homomorphic encryption, such as a first electronic device, a second electronic device, etc., a device calculating homomorphic ciphertext, such as a first server device, etc., a device decrypting homomorphic ciphertext, such as a second server device, etc., may be referred to as a computing device. These computing devices may be various devices, such as a personal computer (PC), a laptop, a smartphone, a tablet, a server, etc.

Referring to FIG. 2, the computing device (400) may include a communication device (410), a memory (420), a display (430), an operating input device (440), and a processor (450).

The communication device (410) is formed to connect the computing device (400) to an external device (not shown), and may be connected to the external device not only through a local area network (LAN) and the Internet, but also through a universal serial bus (USB) port or a wireless communication (e.g., WiFi 802.11a/b/g/n, NFC, Bluetooth) port. This communication device (410) may also be referred to as a transceiver.

The communication device (410) can receive a public key from an external device and transmit a public key generated by the computing device (400) to the external device.

And the communication device (410) can receive a message from an external device and transmit the generated homomorphic ciphertext to the external device. In addition, the communication device (410) can also receive a homomorphic ciphertext from an external device.

In addition, the communication device (410) can receive various parameters required for generating a ciphertext from an external device. Meanwhile, during implementation, various parameters can be directly input from a user through an operation input device (440) described later.

In addition, the communication device (410) may be requested to perform an operation on a homomorphic ciphertext from an external device, and may transmit a calculated result to the external device. Here, the requested operation may be an operation such as addition, subtraction, or multiplication, and may be a comparison operation, which is a non-polynomial operation, or a sorting process.

The memory (420) may store at least one instruction regarding the computational device (400). Specifically, the memory (420) may store various programs (or software) for the computational device (400) to operate according to various embodiments of the present disclosure.

This memory (420) may be implemented in various forms such as RAM, ROM, flash memory, HDD, external memory, memory card, etc., and is not limited to any one.

The memory (420) can store a message to be encrypted. Here, the message can be various types of credit information, personal information, etc. quoted by the user, and can also be information related to usage history, such as location information and Internet usage time information used in the computing device (400).

And the memory (420) can store a public key, and if the computing device (400) is a device that directly generates a public key, it can store not only a secret key but also various parameters necessary for generating the public key and secret key.

And the memory (420) can store a homomorphic ciphertext generated in the process described later. And the memory (420) can also store a homomorphic ciphertext transmitted from an external device. In addition, the memory (420) can also store a calculation result ciphertext which is a result of the calculation process described later.

The display (430) displays a user interface window for selecting a function supported by the computing device (400). Specifically, the display (430) can display a user interface window for selecting various functions provided by the computing device (400). The display (430) can be a monitor such as an LCD (liquid crystal display), an OLED (Organic Light Emitting Diodes), etc., and can also be implemented as a touch screen capable of simultaneously performing the function of the manipulation input device (440) described below.

The display (430) can display a message requesting input of parameters required for generating a private key and a public key. In addition, the display (430) can display a message for selecting a message as an encryption target. Meanwhile, during implementation, the encryption target can be directly selected by the user or automatically selected. In other words, personal information requiring encryption can be automatically set even if the user does not directly select a message.

The manipulation input device (440) can receive function selection of the operation device (400) and control commands for the corresponding functions from the user. Specifically, the manipulation input device (440) can receive parameters required for generating a secret key and a public key from the user. In addition, the manipulation input device (440) can set a message to be encrypted from the user.

And the manipulation input device (440) can receive a sorting command or select a homomorphic ciphertext to be sorted. Alternatively, the manipulation input device (440) can receive a command to select a homomorphic ciphertext of a certain order from the entire homomorphic ciphertext. For example, such selection can be a command to find the largest value among all homomorphic ciphertexts, a command to find the smallest value, a command to find the median value, etc.

The processor (450) controls the overall operation of the computing device (400). Specifically, the processor (450) can control the overall operation of the computing device (400) by executing at least one instruction stored in the memory (420). The processor (450) may be configured as a single device such as a central processing unit (CPU) or an application-specific integrated circuit (ASIC), and may also be configured as multiple devices such as a CPU and a graphics processing unit (GPU).

When a message to be transmitted is input, the processor (450) can store it in the memory (420). Then, the processor (450) can homomorphically encrypt the message using various setting values and programs stored in the memory (420). In this case, a public key can be used.

The processor (450) may generate and use the public key required to perform encryption on its own, or may receive and use it from an external device. For example, a second server device (300) that performs decryption may distribute the public key to other devices.

When generating a key on its own, the processor (450) can generate a public key using the Ring-LWE technique. Specifically, the processor (450) can first set various parameters and rings and store them in the memory (420). Examples of parameters may include the length of a plaintext message bit, the size of a public key, and the size of a private key.

The ring can be expressed mathematically as follows:

[Mathematical formula 2]

Here, R is a ring, Zq is a coefficient, and f(x) is an nth-order polynomial.

A ring is a set of polynomials with predetermined coefficients, where addition and multiplication are defined between elements, and it means a set that is closed under addition and multiplication. Such a ring can be referred to as a ring.

For example, a ring is a set of n-th polynomials whose coefficients are Zq. Specifically, when n is Φ(N), it means an N-th cyclotomic polynomial. (f(x)) denotes the ideal of Zq[x] generated by f(x). The Euler totient function Φ(N) denotes the number of natural numbers that are coprime to N and less than N. If Φ _N (x) is defined as an N-th cyclotomic polynomial, a ring can also be expressed by the following mathematical expression 3.

[Mathematical Formula 3]

The secret key (sk) can be expressed as follows:

Meanwhile, the ring of the above-described mathematical expression 3 has a complex number in the plaintext space. Meanwhile, in order to improve the operation speed for homomorphic ciphertext, only the set of the above-described ring sets whose plaintext space is a real number may be used.

Once such a ring is established, the processor (450) can derive a secret key (sk) from the ring.

[Mathematical Formula 4]

Here, s(x) represents a randomly generated polynomial with small coefficients.

And the processor (450) produces a first random polynomial (a(x)) from the ring. The first random polynomial can be expressed as follows.

[Mathematical Formula 5]

Additionally, the processor (450) can produce an error. Specifically, the processor (450) can extract an error from a discrete Gaussian distribution or a distribution that is statistically close thereto. This error can be expressed as follows.

[Mathematical Formula 6]

When an error is generated, the processor (450) can perform a modular operation on the error to the first random polynomial and the secret key to generate a second random polynomial. The second random polynomial can be expressed as follows.

[Mathematical formula 7]

Finally, the public key (pk) is set as follows, including the first random polynomial and the second random polynomial.

[Mathematical formula 8]

The above-described key generation method is only an example and is not necessarily limited to it, and it goes without saying that public and private keys can be generated using other methods.

Meanwhile, when a public key is generated, the processor (450) can control the communication device (410) so that the generated public key is transmitted to other devices.

And the processor (450) can generate a homomorphic ciphertext for the message. At this time, the processor (450) can perform an encoding operation that converts the message into a polynomial in advance.

And the processor (450) converts the public key into a message converted into a message format. Wow, we can generate a ciphertext using the following mathematical formula 9.

[Mathematical formula 9]

At this time, the processor (450) can generate the length of the ciphertext to correspond to the size of the scaling factor.

The message to be encrypted may be received from an external source, or may be input from an input device directly provided or connected to the computing device (400). In addition, the scaling factor may also be input directly by the user, or may be provided through another device. For example, if the computing device (400) includes a touch screen or a key pad, the processor (450) may store data input by the user through the touch screen or key pad in the memory (420), and then encrypt it.

Meanwhile, according to one embodiment of the present disclosure, packing may be performed. If packing is used in homomorphic encryption, it becomes possible to encrypt multiple messages into a single ciphertext. In this case, if the calculation device (400) performs calculations between each ciphertext, the calculations for multiple messages are processed in parallel as a result, so the calculation burden is greatly reduced.

Specifically, when a message is composed of multiple message vectors, the processor (450) may convert the multiple message vectors into a polynomial that can encrypt them in parallel, multiply the polynomial by a scaling factor, and then homomorphically encrypt the polynomial using a public key. Accordingly, the processor (450) may generate a ciphertext that packs multiple message vectors.

And, when decryption of a homomorphic ciphertext is required, the processor (450) can apply a secret key to the homomorphic ciphertext to generate a polynomial-type decryption text, and decode the polynomial-type decryption text to generate an approximate message. At this time, the generated approximate message may include an error as mentioned in the mathematical expression 1 described above.

And the processor (450) can perform operations on the ciphertext. Specifically, the processor (450) can perform operations such as addition, subtraction, or multiplication while maintaining the encrypted state on the homomorphic ciphertext.

In addition, the processor (450) can perform an operation on a polynomial having an operation other than addition, subtraction, or multiplication for the ciphertext. Specifically, the homomorphic ciphertext is closed for addition, subtraction, and multiplication, but is not closed for other operations. Therefore, for operations other than addition, subtraction, and multiplication, an approximate operation formula expressed by the three operations described above must be used. Here, the approximate operation formula can use a well-structured polynomial, i.e., a composite function, which is well-structured to have low complexity.

And the processor (450) can perform alignment on a plurality of homomorphic ciphertexts. Specifically, the processor (450) can perform alignment on a plurality of homomorphic ciphertexts using a k-way alignment system. At this time, the processor (450) can perform the alignment operation described above in parallel using a plurality of k-way sorters. Here, the k-way sorters can be sorters having the same k value, and sorters having different k values can also be used.

In more detail, the processor (450) can divide a plurality of homomorphic ciphertexts into a plurality of groups. Specifically, the processor (450) can divide the plurality of groups corresponding to the sorting units of the k-way sorter. For example, when 25 homomorphic ciphertexts are used in a 5-way sorter, they can be divided into 5 groups.

And the processor (450) can perform sorting by separated group. Specifically, multiple homomorphic ciphertexts by group can be sorted by using a k-way sorter capable of sorting three or more homomorphic ciphertexts in one stage. The specific configuration and operation of the k-way sorter will be described later with reference to FIG. 3.

And the processor (450) can select a candidate homomorphic ciphertext corresponding to the sorting order from among a plurality of homomorphic ciphertexts sorted by group. Specifically, the processor (450) can calculate a first order for the first group corresponding to the sorting order and a second order for the second group, compare the first homomorphic ciphertext corresponding to the first order in the first group with the second homomorphic ciphertext corresponding to the second order in the second group, and determine a candidate homomorphic ciphertext for which the sorting order is possible based on the comparison result.

For example, the processor (450) can produce a lower integer value of the sorting order divided by 2 as the first order, and a raised integer value of the sorting order divided by 2 as the second order. In addition, the processor (450) can determine, if the first homomorphic ciphertext is larger than the second homomorphic ciphertext and is in descending order, a homomorphic ciphertext in the first group having a size smaller than the first homomorphic ciphertext corresponding to the first order, a second homomorphic ciphertext corresponding to the second order, and a homomorphic ciphertext in the second group having a size larger than the second homomorphic ciphertext as candidate homomorphic ciphertexts.

And the processor (450) can determine a homomorphic ciphertext corresponding to the sorting order through a homomorphic operation on the selected candidate homomorphic ciphertext. Specifically, the processor (450) can determine a homomorphic ciphertext corresponding to the sorting order through the output of the comparison function between the selected candidate homomorphic ciphertexts by using a comparison function that selectively outputs a larger homomorphic ciphertext or a smaller homomorphic ciphertext among two input homomorphic ciphertexts.

And, in the process of determining a specific sorting order, the processor (450) can determine a homomorphic ciphertext corresponding to a specific sorting order with only the above-described operations. On the other hand, in the case of performing sorting for all homomorphic ciphertexts, the processor (450) can sort a plurality of homomorphic ciphertexts within two groups by repeating the steps of selecting candidate homomorphic ciphertexts as many as the number of homomorphic ciphertexts included in two groups among the plurality of groups and the steps of determining homomorphic ciphertexts corresponding to the sorting order.

For example, if there are 10 homomorphic ciphertexts, the homomorphic ciphertexts can be sorted by dividing them into two groups of 5 each, performing sorting for each group first, determining the homomorphic ciphertext of the first order using the two sorted groups, and sequentially determining the 2nd...10th homomorphic ciphertexts. Meanwhile, in the sorting process for each group, it is also possible to perform sorting using a conventional general sorter, and it is also possible to use the sorting method according to the present disclosure.

That is, when sorting five homomorphic ciphertexts, it is also possible to perform sorting on homomorphic ciphertexts within a group by dividing the homomorphic ciphertexts into 2 and 3, and finding the 1st, ..., 5th homomorphic ciphertexts as in the operation described above. That is, it is also possible to configure a sorting system for all homomorphic ciphertexts using only the sorting method according to the present disclosure, and it is also possible to use a general sorter for sorting within the divided groups and use the sorting method according to the present disclosure in the comparison process between the groups.

In addition, the processor (450) can search for a homomorphic ciphertext corresponding to a specific order among a plurality of homomorphic ciphertexts. For example, when a command to find the largest homomorphic ciphertext or a command to find the smallest homomorphic ciphertext is input from the user, the homomorphic ciphertext corresponding to the command can be searched for using the k-way sorting system described above.

And when the operation is completed, the processor (450) can detect data of a valid area from the operation result data. Specifically, when the approximate message weight in the operation result ciphertext exceeds a threshold, the processor (450) can perform a reboot operation on the ciphertext.

As described above, the computational device according to the present disclosure supports various operations on homomorphic ciphertexts, and can search for homomorphic ciphertexts of a specific order among a large number of homomorphic ciphertexts, or perform a sorting operation on a plurality of homomorphic ciphertexts. In addition, since the above-described search and sorting operations are performed using a method with a low complexity depth, the above-described operations can be performed through a lower number of reboot operations than before. Accordingly, faster operations than before are possible.

FIG. 3 is a drawing for explaining the alignment operation of the calculation device of the present disclosure.

Referring to FIG. 3, a k-way sorter (500) is disclosed. This k-way sorter (500) can sort k homomorphic ciphertexts in one stage. Here, k can be a prime number greater than or equal to 3 (e.g., 3, 5, 7, etc.).

This k-way sorter (500) can sort multiple homomorphic ciphertexts using a single stage, and although it was described in the city as processing five homomorphic ciphertexts simultaneously, it is also possible to sort two to four or seven or more homomorphic ciphertexts using a single stage.

Meanwhile, the main purpose of the sorting algorithm of the present disclosure is to sort homomorphic ciphertexts by using all K comparison results compared pairwise using an approximate comparison algorithm while minimizing the computational depth of comparison operations.

On the other hand, exact comparison is a comparison using addition and multiplication in which the result is clearly binary, whereas approximate comparison is not a binary value but a value within a certain range.

For example, for three data a, b, and c, let the result of comparing a and b be θ _ab , and the result of comparing b and c be θ _bc . In order to know θ _abc , which indicates whether a > b > c, the operation θ _ab · θ _bc is required.

However, the comparison result in the approximate comparison is a value between (0, 1) as described above, and if θ _ab > 0.5, then a > b can be determined. If a > b > c is satisfied, but the values of each number are close, such as θ _ab = 0.7 and θ _bc = 0.6, then θ _abc = θ _ab · θ _bc = 0.42, which is less than 0.5, and the result can be that a > b > c does not hold.

Therefore, it is difficult to simply use logical operations for sorting through approximate comparison. In this regard, the present disclosure uses a max function.

The maximum function of the present disclosure is defined as follows.

[Mathematical Formula 10]

max(a, b) = (a > b)·a + (a < b)·b

A function like this outputs the larger of the two input values. Since the function (a > b) + (a < b) = 1 always holds true, even when a and b are very close, the above-described max(a, b) can output the exact maximum value. We define a function L that applies this method.

[Mathematical Formula 11]

L _a>b (F, G) = (a > b)·F + (a < b)·G

Here, L is a maximum function, max(a, b) = L _a>b (a, b). For example, if a > b, it can return F, and if a < b, it can return G. And through the combination of the above-described L functions, we can obtain an m-max function that finds the mth maximum for n inputs. Here, m≤n. Since L is a multivariate function here, the combined L can be defined as L(L,L).

On the other hand, the potential problem of L _a>b (F, G) is that when (ab) is very small, the comparison result outputs 0.5, or the error becomes very large. When finding the mth maximum, a F when b If a function satisfying G is selected, the above-described problem can be overcome. Accordingly, in the present disclosure, F and G satisfying this condition can be selected and used. This will be described later.

Meanwhile, the sign function is a non-polynomial operation that cannot be expressed by addition, subtraction, or multiplication. Therefore, in the present disclosure, an approximate sign function is used to apply the sign function to a homomorphic ciphertext.

For example, various forms of approximate sign functions can be used, and the present disclosure uses a well-structured composite function to have low complexity. The composite function used here may be a composite function (f(x)) that makes the function output value horizontal for non-zero input values, that is, a composite function that makes the output value approach 1 for input values greater than 0 and approach -1 for input values less than 0), or a composite function (g(x)) that makes the function output value horizontal for non-zero input values.

An example of the two composite functions described above (f(x), g(x)) is as shown in Equation 12.

[Mathematical formula 12]

f ₃ (x) = (35x - 35x ³ + 21x ⁵ - 5x ⁷ )/2 ⁴

g ₃ (x) = (4589x - 16577x ³ + 25614x ⁵ - 12860x ⁷ )/2 ¹⁰

In implementation, the above-described f(x) and g(x) can be repeatedly applied multiple times to implement an approximate code function. The form of the approximate code function used in the present disclosure will be described later with reference to FIG. 4.

In this way, the k-way sorter (500) of the present disclosure can utilize an approximate sign function implemented with the above-described composite function.

Meanwhile, the main issue in homomorphic ciphers is to reduce the overhead in the sorting process. In this regard, before explaining the overall operation of the sorting algorithm, we first explain the divide and conquer algorithm.

For example, suppose that array A(A') can be divided into B(B') and C(C'), where B = {b ₁ ,… , b _s }, C = {c ₁ ,… , c _t }, and B' and C' are sorted arrays for B and C, respectively.

And if the approximate comparison results ({(B > C)}, {[B' > C']}, {[A > A']}) are given, the following two results can be derived.

1) A sorted array for Z, where Z = A as a set (more precisely, Z' is a sorted array when Z'=A').

2) {(Z > Z')}, information needed to compute the sorted sequence by merging Z and Z'.

First, given B, C, {(B > C)}, the final goal is to compute a sorted array Z = {z ₁ , … z _s+t } of B∪C. For i ∈[s], j ∈[t], the key idea is to reduce the number of candidates for z _s+t in B∪C by using the comparison results between _bi and c _j .

If _bi > c _j , the candidates greater than _bi are the elements in B[:i-1] and C[:j-1] , which means that there are at most i+j-2 elements greater than _bi . And since the number of elements greater than bi _+j is exactly i+j-1 , _bi cannot be bi _+j . For the same reason, b ₁ , ..., bi _-1 cannot be bi _+j . Similarly, since all elements in B[:i] and C[:j] are greater than C _j+1 , the number of elements greater than C _j+1 is i+j . And c j ₊₁ cannot be bi _+j , and for the same reason, c _{j +2} , ..., c _t cannot be bi _+j .

As a result, the only candidate left for the m-th element is B[i+1:] ∪C[j]. Meanwhile, B[:i] must be greater than z _i+j , and z _i+j is the j-th largest element among the remaining candidates. If _bi < c _j , z _i+j is the i-th largest element of B[:i] ∪ C[j+1:].

를 1 ≤ m ≤

인 경우에서, 정렬된 B, C의 유니언(union) 내의 m 번째 최대 원소라고 하자. 이러한 머징 알고리즘은 다음과 같이 표현될 수 있다. As a result,

1 ≤ m ≤

In this case, let B be the mth largest element in the union of sorted B and C. This merging algorithm can be expressed as follows.

[Mathematical formula 13]

이고, X, Y 각각은 다음과 같이 정의될 수 있다. Here,

, and X and Y can be defined as follows.

[Mathematical formula 14]

By using these conditions, when searching for a specific element, the comparison operation can be reduced by half compared to the existing one. And by repeatedly performing this operation, the order for all elements can be determined. The specific algorithm for finding the mth element is shown in Fig. 5.

Second, let's assume that A and A' are classified as Z, Z' respectively. The next goal is to compute {(Z >Z')} using the sorting result {(A >A')}. The result of this step is used when merging two sorted arrays Z and Z'. The main idea is that if X and Y are sorted arrays, then the comparison of {(X > r)} (or {(r > Y)} can also be sorted for all elements. Therefore, when merging two sorted arrays {(B > a _j ')}, {(C > a _j ')}, we can use {(B>C)}.

As a result, to compute (z _i >z' _j ), the above-described merging process must be applied exactly twice.

The first step is to align the sorted arrays {B >a' _j )}, {(C >a' _j ). The comparison between them is given by {B > C) as explained earlier.

The output of the first stem is {Z >a' _j )}, and if we repeat this for all a' _j , we get {(Z >A')}={(Z>B')}∪ {(Z >C')}.

The next step is to merge the two ({(z i >B')},{z _i >C'}) using the comparison results of {(Z _i >B')} and {( _{z i >} C')}. This step is equivalent to computing z _i+j by replacing b _i , c _i in (z _i >b' _i )(z _i >c' _i ).

As a result of the second step, we can obtain {z _i >Z')}, and by repeatedly performing this for all z _i , we can obtain {(Z >Z')}.

By combining these two steps, the algorithm for performing the alignment is illustrated in Fig. 7, and an example of operation when k is 2 ^m is illustrated in Fig. 6.

Fig. 4 is a diagram illustrating the forms of various composite functions related to the sign function. Specifically, Fig. 4 illustrates examples of f(x), g(x), and composite functions.

Referring to Fig. 4, it can be confirmed that f(x) has a small slope but a small error at the ends. And it can be confirmed that g(x) has a larger slope than f(x), but errors occur at both ends. Therefore, if the composite function of g(x) is used in the beginning and the composite function of f(x) is used in the end, it can have a more ideal form compared to using only one composite function for the same number of iterations.

Meanwhile, the degrees of g(x) and f(x) described above can be n. However, since the leading coefficients of f4 (= 35/128) and g4 (= 46623/1024) are positive, the compositions of f4 and g4 'S may be different when the absolute value of the input x is greater than 1. For example, when the input x is close to 1, the comparison result may branch due to the attached error, resulting in an incorrect output.

By using such a composite function, i.e. by using a well-structured polynomial, Relatively low in terms of accuracy or Complexity allows us to approximate sign functions.

FIG. 5 is a diagram illustrating an algorithm for selecting a homomorphic ciphertext corresponding to a specific sorting sequence according to one embodiment of the present disclosure.

Referring to Figure 5, the Max algorithm and the Minimum algorithm are described. The two algorithms operate complementarily, so only the Max algorithm is briefly described.

The main principle of Max's algorithm is to efficiently find an element corresponding to a specific sorting order by not performing comparison operations on elements that cannot be candidates corresponding to a specific sorting order, as explained above.

To this end, the sorting order to be found and multiple homomorphic ciphertexts are input. In the illustrated example, the homomorphic ciphertexts are input in a state divided into two groups, but during implementation, it is also possible to input the homomorphic ciphertexts as a single group. In the following, the case where the input is divided into two groups is assumed and explained.

With such input, sorting can be performed for each array, and the order of each group corresponding to the input sort order can be determined. For example, for the first array, the order can be determined as the rounding down value for the value m divided by 2, and for the second array, the order can be determined as the rounding up value for the value m divided by 2.

And as explained above, the remaining values, excluding the homomorphic ciphertexts that cannot be candidates based on the corresponding order, can be compared with the max function to finally determine the mth homomorphic ciphertext.

For example, if the elements of B are x1, x2, x3, x4, and the elements of C are y1, y2, y3, y4, and the search order is 4, then the group-wise orders described above can each be 2. In this case, if a comparison is performed between x2 and y2, and the comparison result shows that x2 is greater than y2, logically x1, x2, and x3 cannot be the 4th element. Also, y3 and y4 cannot be the 4th element as explained above. That is, one of x3, x4, y1, and y2 becomes the 4th order. And the 2nd order among them becomes the overall 4th order. For example, if it is confirmed that y1 > x3 > y2 > x4 is the relationship between four elements, the overall order of y1 cannot be specified, but it can be confirmed that x3 becomes the 4th order. That is, it can be confirmed from the above-described relationships that there are three elements (x1, x2, y1) greater than x3 and four elements less than x3.

Meanwhile, finding the second order in the above-mentioned x3, x4, y1, y2 can also be done by comparing x4 and y1 in the same way as explained above, and by excluding candidates that can be the second out of four based on the order between them, thereby minimizing the order of operations.

If y1 is the largest value among these, then y1 has the possibilities of 1, 2, and 3, but the 4th one is

FIG. 6 is a diagram for explaining the operation of a k-sorter according to one embodiment of the present disclosure. Specifically, FIG. 6 shows the overall algorithm of the k-sorter and the multiplication and depth used at each stage.

Referring to Fig. 6, the entire algorithm consists of a MERGE function. Since this MERGE function is performed by repeating the MAX/MIN algorithm as illustrated in Fig. 5, the complexity and depth of the MERGE function correspond to the complexity and depth of the MAX/MIN algorithm. And as explained above, the MAX/MIN algorithm is performed by calculating the L function, and the L function consists of one multiplication.

By calculating through this, it can be confirmed that the complexity of the merging function according to the present disclosure is O(n ² ), and the complexity is improved when compared to the complexity of the existing sorting method of O(n ³ ).

FIG. 7 is a diagram for explaining a sorting algorithm according to one embodiment of the present disclosure.

Referring to FIG. 7, the alignment algorithm according to the present disclosure can be broadly divided into three steps.

The first is to divide the sorting target into two groups, and the second is to perform sorting for each group. And finally, sorting is performed using a merging function using the sorting results for each group. This merging function can complete sorting for the entire input homomorphic ciphertext by repeatedly performing an algorithm for finding a specific sorting order as described in Fig. 5.

Below, we describe various k-way sorting networks and how to apply them to homomorphic ciphertexts in a more optimized manner.

Figure 8 is a diagram explaining the operation when using a 3-way alignment network.

Referring to Figure 8, an example of sorting 3 ² elements is illustrated.

In this example, first, three elements are sorted in a horizontal unit. At this time, the sorting can be performed sequentially in three units, but the sorting can be performed in parallel in three rows simultaneously. The simultaneous sorting operation in a homomorphic ciphertext, i.e., the operation using slots, is described later in Fig. 12.

After the horizontal alignment is completed, the vertical alignment can be performed on the result. Next, the diagonal alignment can be performed twice using a 2-way alignment machine and a 3-way alignment machine, so that the final alignment of 9 elements can be completed. The depth of this alignment network is 4 (=(log ₃ 9) ² ).

In the above, the alignment is illustrated and explained as being performed in the order of horizontal, vertical, and diagonal directions, but the alignment may be performed in a different order during implementation.

Below, we describe a specific method for applying such a sorting network to homomorphic ciphertext.

Homomorphic ciphertexts can perform operations such as addition and multiplication, but they require a lot of processing time compared to plaintext. Therefore, it is desirable to perform operations on homomorphic ciphertexts in parallel, and for this purpose, SIMD operations and message rotation are used in the present disclosure. SIMD can be applied to various k values, but for ease of explanation, the following explanation assumes the case where k is 5.

Sorting in homomorphic ciphertext can be broadly divided into parallel comparison, slot allocation, and sorting steps. Meanwhile, when k is 5, there can be four types, and different SIMD algorithms can be used for each type. However, when using various k instead of a fixed k, application independent of the above-described types is possible. Therefore, the following explanation assumes a case where a sorter with multiple k values is used.

Before explaining the operation of Fig. 9, first, it is assumed that the distance between messages is the same and there are no duplicate values. Referring to Fig. 9, five stages can be performed when sorting ⁵² elements. In Fig. 9, it can be confirmed that only a 5-way sorter is used in the first and second stages, a 2-way sorter, a 3-way sorter, a 4-way sorter, and a 5-way sorter are used in the third stage, a 2-way sorter and a 3-way sorter are used in the fourth stage, and a 4-way sorter is used in the fifth stage. Among these, the specific sorting operation in the third stage is as shown in Fig. 10.

Referring to Fig. 10, a 2-way sorter, a 3-way sorter, a 4-way sorter, and a 5-way sorter can be used in the third stage. The 2-way sorter can receive (x ₂ , x ₆ ) and (x ₂₀ , x ₂₄ ) as input, the 3-way sorter can receive (x ₃ , x ₇ , x ₁₁ ) and (x ₁₅ , x ₁₉ , x ₂₃ ) as input, the 4-way sorter can receive (x ₄ , x ₈ , x ₁₂ , x ₁₆ ) and (x ₁₀ , x ₁₄ , x ₁₈ , x ₁₂ ) as input, and the 5-way sorter can perform sorting by receiving (x ₅ , x ₉ , x ₁₃ , x ₁₇ , x ₂₁ ) as input.

Figure 11 illustrates the configuration of a sorter by stage type.

Referring to Fig. 11, it can be confirmed that the first type (type 0) performs alignment using a 5-way aligner in the horizontal direction. In addition, since the second type (type 1) performs alignment in the diagonal direction, 2, 3, 4, and 5-way aligners are used, and it can be confirmed that different aligners are used for the third type (type 2) and the fourth type. The reason why such various types are required is that, as illustrated in Fig. 8, alignment in the diagonal direction is required even after alignment in the horizontal and vertical directions.

In Fig. 11, only the alignment for 25 elements is illustrated and described, but when implemented, the same method can be applied to the 3 ² case and the 7 ² form described above.

In order to perform the comparison as described above in a homomorphic ciphertext state, first, the calculation of a comparison function is required.

Meanwhile, since the calculation in the homomorphic ciphertext requires that the calculation target be located in the same slot, if the calculation target is not located in the same slot, a rotation operation is required to place it in the same slot. Meanwhile, if the rotation operation is performed on the ciphertext, slots other than the target can also move, so first, by multiplying by a scalar vector called a masking vector, only the target slot can be extracted first.

And since simultaneous operations on slot units are possible in homomorphic ciphertexts, parallel operations are possible, and slot allocation is required for such parallel operations. As shown in Fig. 10, slot allocation in a form suitable for sorting the comparison results and ciphertexts is performed so as to be suitable for parallel operations, and the final sorting operation can be completed through homomorphic operations on the results of the slot allocation. Such slot allocation can be performed using a preset masking vector as explained above.

Meanwhile, the k value used in the present invention causes an improvement in the computation speed, etc. as the number of slots in the homomorphic ciphertext increases. For example, when the number of slots increases from s2 ¹⁵ to s2 ¹⁶ , it is more advantageous to use 5 than 3. Therefore, when performing the sorting according to the present disclosure, the size of the slot of the corresponding homomorphic ciphertext may be confirmed, and the sorting operation may be performed using the k value corresponding to the size of the confirmed slot. However, since the size of the memory required for the computation process also increases as the k value increases, it is necessary to confirm the size of the memory resource when considering the above.

FIG. 13 is a flowchart illustrating a cryptographic operation method according to one embodiment of the present disclosure.

Referring to Fig. 13, a sorting command for multiple homomorphic ciphertexts is input (S1310). For example, the multiple homomorphic ciphertexts may be ciphertexts satisfying the mathematical expression 1 described above.

And then, multiple homomorphic ciphertexts are sorted (S1320). Specifically, multiple homomorphic ciphertexts can be sorted by group by dividing them into multiple groups corresponding to the sorting units of the k-way sorter and using a k-way sorter capable of sorting three or more homomorphic ciphertexts in one stage.

And, among the multiple homomorphic ciphertexts sorted by group, a candidate homomorphic ciphertext corresponding to the sorting order can be selected. For example, the rounded down integer value of the sorting order divided by 2 is calculated as the first order, and the rounded down integer value of the sorting order divided by 2 is calculated as the second order, and the first homomorphic ciphertext corresponding to the first order in the first group and the second homomorphic ciphertext corresponding to the second order in the second group are compared, and based on the comparison result, a candidate homomorphic ciphertext for which the sorting order is possible can be determined.

And by repeating the above-described operation a number of times corresponding to each order, alignment can be performed on the entire homomorphic ciphertext.

And output the sorting result (S1330). For example, if multiple homomorphic ciphertexts are received from an external device, the sorted results can be transmitted to the external device in the sorting order. Conversely, if the sorting is for multiple previously stored homomorphic ciphertexts, the storage order will be sorted through the above-described sorting operation, so the above-described output operation can be omitted.

As described above, the method for processing homomorphic ciphertexts according to the present embodiment not only enables alignment processing for a large number of homomorphic ciphertexts, but also enables alignment to be performed more quickly than performing alignment for multiple homomorphic ciphertexts in a smaller number of stages.

The detailed operations of each step have been described above, so a detailed explanation will be omitted.

Meanwhile, the methods according to various embodiments of the present disclosure described above can be implemented in the form of applications that can be installed on existing computing devices (or electronic devices).

Additionally, the methods according to various embodiments of the present disclosure described above can be implemented only with a software upgrade or a hardware upgrade for an existing computing device (or electronic device).

Additionally, the various embodiments of the present disclosure described above may also be performed through an embedded server provided in a computing device, or an external server of at least one of the computing devices.

Meanwhile, according to a temporary example of the present disclosure, the various embodiments described above can be implemented as software including commands stored in a machine-readable storage media that can be read by a machine (e.g., a computer). The machine is a device that can call a command stored from the storage media and operate according to the called command, and may include a display device according to the disclosed embodiments. When the command is executed by the processor, the processor can perform a function corresponding to the command directly or by using other components under the control of the processor. The command can include code generated or executed by a compiler or an interpreter. The machine-readable storage media can be provided in the form of a non-transitory storage media. Here, 'non-transitory' only means that the storage media does not include a signal and is tangible, and does not distinguish between data being stored semi-permanently or temporarily in the storage media.

In addition, according to one embodiment of the present disclosure, the method according to the various embodiments described above may be provided as included in a computer program product. The computer program product may be traded between sellers and buyers as a commodity. The computer program product may be distributed in the form of a storage medium readable by a machine (e.g., compact disc read only memory (CD-ROM)) or online through an application store (e.g., Play StoreTM). In the case of online distribution, at least a part of the computer program product may be temporarily stored or temporarily generated in a storage medium such as a memory of a manufacturer's server, a server of an application store, or a relay server.

In addition, according to one embodiment of the present disclosure, the various embodiments described above can be implemented in a recording medium that can be read by a computer or a similar device using software, hardware, or a combination thereof. In some cases, the embodiments described in this specification can be implemented by the processor itself. According to a software implementation, embodiments such as the procedures and functions described in this specification can be implemented by separate software modules. Each of the software modules can perform one or more functions and operations described in this specification.

Meanwhile, computer instructions for performing processing operations of a device according to the various embodiments described above may be stored in a non-transitory computer-readable medium. When the computer instructions stored in the non-transitory computer-readable medium are executed by a processor of a specific device, the computer instructions cause the specific device to perform processing operations in the device according to the various embodiments described above.

A non-transitory computer-readable medium is not a medium that stores data for a short period of time, such as a register, cache, or memory, but a medium that permanently stores data and can be read by a device. Specific examples of non-transitory computer-readable media include CDs, DVDs, hard disks, Blu-ray disks, USBs, memory cards, and ROMs.

In addition, each of the components (e.g., modules or programs) according to the various embodiments described above may be composed of a single or multiple entities, and some of the corresponding sub-components described above may be omitted, or other sub-components may be further included in various embodiments. Alternatively or additionally, some of the components (e.g., modules or programs) may be integrated into a single entity, which may perform the same or similar functions performed by each of the corresponding components prior to integration. Operations performed by modules, programs or other components according to various embodiments may be executed sequentially, in parallel, iteratively or heuristically, or at least some of the operations may be executed in a different order, omitted, or other operations may be added.

Although the preferred embodiments of the present disclosure have been illustrated and described above, the present disclosure is not limited to the specific embodiments described above, and various modifications may be made by a person skilled in the art to which the present disclosure pertains without departing from the gist of the present disclosure as claimed in the claims, and such modifications should not be individually understood from the technical idea or prospect of the present disclosure.

100: Electronic device 200: First server device
300: Second server device 400: Computing device
410: Communication device 420: Memory
430: Display 440: Operating input device
450: Processor

Claims (17)

A step of dividing multiple homomorphic ciphertexts into multiple groups;
A step of performing sorting by the above-mentioned distinguished groups;
A step of selecting a candidate homomorphic ciphertext corresponding to the sorting order among a plurality of homomorphic ciphertexts sorted by the above group; and
A step of determining a homomorphic ciphertext corresponding to the sorting order through a homomorphic operation on the selected candidate homomorphic ciphertext; including;
The step of selecting the above candidate homomorphic ciphertext is:
A step of calculating a first order number for the first group corresponding to the above sorting order and a second order number for the second group;
A step of comparing a first homomorphic ciphertext corresponding to a first order in a first group with a second homomorphic ciphertext corresponding to a second order in a second group; and
A step of determining a candidate homomorphic ciphertext that can be sorted based on the comparison result;
The steps for calculating the above sequence are:
A method for processing homomorphic ciphertext, wherein the lower integer value of the above sorting order divided by 2 is calculated as a first order, and the raised integer value of the above sorting order divided by 2 is calculated as a second order. delete delete In the first paragraph,
The step of determining the above candidate homomorphic ciphertext is:
A homomorphic ciphertext processing method for determining, as candidate homomorphic ciphertexts, a homomorphic ciphertext in the first group having a size smaller than the first homomorphic ciphertext corresponding to the first order, a second homomorphic ciphertext in the second group having a size larger than the second homomorphic ciphertext, if the first homomorphic ciphertext is larger than the second homomorphic ciphertext and is sorted in descending order. In the first paragraph,
The step of determining the homomorphic ciphertext corresponding to the above sorting order is:
A homomorphic ciphertext processing method that uses a comparison function that selectively outputs a larger homomorphic ciphertext or a smaller homomorphic ciphertext among two input homomorphic ciphertexts, and determines a homomorphic ciphertext corresponding to the sorting order through the output of a comparison function between the selected candidate homomorphic ciphertexts. In the first paragraph,
A method for processing homomorphic ciphertexts, further comprising: a step of sorting a plurality of homomorphic ciphertexts within the two groups by repeating the step of selecting the candidate homomorphic ciphertexts equal to the number of homomorphic ciphertexts included in two groups among the plurality of groups and the step of determining a homomorphic ciphertext corresponding to the sorting order. In the first paragraph,
The step of performing sorting by the above-mentioned distinct groups is:
A homomorphic ciphertext processing method that sorts multiple homomorphic ciphertexts by group using a k-way sorter capable of sorting three or more homomorphic ciphertexts in a single stage. In Article 7,
The step of dividing into the above multiple groups is:
A method for processing homomorphic ciphertext by dividing it into multiple groups corresponding to the sorting units of the above k-way sorter. A memory that stores multiple homomorphic ciphertexts;
A processor for aligning the above-mentioned plurality of homomorphic ciphertexts;
The above processor,
Divide multiple homomorphic ciphertexts into multiple groups,
Sorting is performed by the above-mentioned distinct groups,
Select a candidate homomorphic ciphertext corresponding to the sorting order among multiple homomorphic ciphertexts sorted by the above group,
By performing a homomorphic operation on the selected candidate homomorphic ciphertexts above, a homomorphic ciphertext corresponding to the above sorting order is determined,
The above processor,
Calculate the first order for the first group corresponding to the above sorting order, and the second order for the second group,
Compare the first homomorphic ciphertext corresponding to the first sequence in the first group with the second homomorphic ciphertext corresponding to the second sequence in the second group,
Based on the above comparison results, a candidate homomorphic ciphertext for which the above sorting order is possible is determined,
The above processor,
An electronic device that produces a lower integer value of the above sorting order divided by 2 as a first order, and a higher integer value of the above sorting order divided by 2 as a second order. delete delete In Article 9,
The above processor,
An electronic device that determines, as candidate homomorphic ciphertexts, a homomorphic ciphertext in the first group having a size smaller than the first homomorphic ciphertext corresponding to the first order, a second homomorphic ciphertext in the second group having a size larger than the second homomorphic ciphertext, if the first homomorphic ciphertext is larger than the second homomorphic ciphertext and is sorted in descending order. In Article 9,
The above processor,
An electronic device that uses a comparison function that selectively outputs a larger homomorphic ciphertext or a smaller homomorphic ciphertext among two input homomorphic ciphertexts, and determines a homomorphic ciphertext corresponding to the sorting order through the output of a comparison function between the selected candidate homomorphic ciphertexts. In Article 9,
The above processor,
An electronic device that sorts a plurality of homomorphic ciphertexts within the two groups by repeating the step of selecting the candidate homomorphic ciphertexts equal to the number of homomorphic ciphertexts included in two groups among the plurality of groups and the step of determining a homomorphic ciphertext corresponding to the sorting order. In Article 9,
The above processor,
An electronic device that sorts multiple homomorphic ciphertexts by group using a k-way sorter capable of sorting three or more homomorphic ciphertexts in a single stage. In Article 15,
The above processor,
An electronic device that divides into a plurality of groups corresponding to the alignment units of the above k-way sorter. A computer-readable recording medium including a program for executing a method for processing homomorphic ciphertext,
The above method of processing homomorphic ciphertext is as follows:
A step of dividing multiple homomorphic ciphertexts into multiple groups;
A step of performing sorting by the above-mentioned distinguished groups;
A step of selecting a candidate homomorphic ciphertext corresponding to the sorting order among a plurality of homomorphic ciphertexts sorted by the above group; and
A step of determining a homomorphic ciphertext corresponding to the sorting order through a homomorphic operation on the selected candidate homomorphic ciphertext; including;
The step of selecting the above candidate homomorphic ciphertext is:
A step of calculating a first order number for the first group corresponding to the above sorting order and a second order number for the second group;
A step of comparing a first homomorphic ciphertext corresponding to a first order in a first group with a second homomorphic ciphertext corresponding to a second order in a second group; and
A step of determining a candidate homomorphic ciphertext that can be sorted based on the comparison result;
The steps for calculating the above sequence are:
A computer-readable recording medium that produces a lower integer value of the above sorting order divided by 2 as a first order, and a higher integer value of the above sorting order divided by 2 as a second order.

Images