Practical sorting on large-scale encrypted data

1. A method for processing homomorphic ciphertexts, the method comprising:

receiving an input of an instruction for sorting a plurality of homomorphic ciphertexts;

sorting the homomorphic ciphertexts by using a 5-way sorter which can sort five homomorphic ciphertexts in a single stage; and

outputting the sorted homomorphic ciphertexts, wherein the 5-way sorter is configured to:

based on a first homomorphic ciphertext, a second homomorphic ciphertext, and a third homomorphic ciphertext being input, and using a comparison function between two input values, calculate a larger value and a smaller value between the first homomorphic ciphertext and the second homomorphic ciphertext,

input the larger value and the third homomorphic ciphertext into the comparison function and output a first output value,

input the smaller value and the third homomorphic ciphertext into the comparison function and output a third output value, and

calculate a second output value by subtracting the first output value and the third output value from a summed-up value of the first to third homomorphic ciphertexts and output the second output value.

2. The method for processing homomorphic ciphertexts of claim 1 , wherein the sorting comprises:

performing a parallel sorting process by using a plurality of 5-way sorters.

3. The method for processing homomorphic ciphertexts of claim 1 , wherein

the comparison function is calculated through a multiplication calculation between an approximate sign function outputting a predetermined value according to comparison of sizes and an input value.

4. The method for processing homomorphic ciphertexts of claim 3 , wherein

the approximate sign function is a function which is a result of repetitively calculating a composite function of which output value is made to be close to 1 regarding an input value larger than 0, and of which output value is made to be close to −1 regarding an input value smaller than 0 by a predetermined number of times.

5. The method for processing homomorphic ciphertexts of claim 4 , wherein

the approximate sign function is a function which is a result of repetitively calculating two different composite functions by three times, respectively.

6. The method for processing homomorphic ciphertexts of claim 1 , wherein

the 5-way sorter extends plain sentence spaces of the five respective sorted homomorphic ciphertexts.

7. A calculation device comprising:

a memory storing a plurality of homomorphic ciphertexts for an approximate message including an error; and

a processor sorting the homomorphic ciphertexts, wherein

the processor is configured to:

sort the homomorphic ciphertexts by using a 5-way sorter which can sort five homomorphic ciphertexts in a single stage, and

the 5-way sorter is configured to:

based on a first homomorphic ciphertext, a second homomorphic ciphertext, and a third homomorphic ciphertext being input, and using a comparison function between two input values, calculate a larger value and a smaller value between the first homomorphic ciphertext and the second homomorphic ciphertext,

input the larger value and the third homomorphic ciphertext into the comparison function and output a first output value,

input the smaller value and the third homomorphic ciphertext into the comparison function and output a third output value, and

calculate a second output value by subtracting the first output value and the third output value from a summed-up value of the first to third homomorphic ciphertexts and output the second output value.

8. The calculation device of claim 7 , wherein

the processor is configured to:

perform a parallel sorting process by using a plurality of 5-way sorters.

9. The calculation device of claim 7 , wherein

the comparison function is calculated through a multiplication calculation between an approximate sign function outputting a predetermined value according to comparison of sizes and an input value.

10. The calculation device of claim 9 , wherein

the approximate sign function is a function which is a result of repetitively calculating a composite function of which output value is made to be close to 1 regarding an input value larger than 0, and of which output value is made to be close to −1 regarding an input value smaller than 0 by a predetermined number of times.

11. The calculation device of claim 10 , wherein

the approximate sign function is a function which is a result of repetitively calculating two different composite functions by three times, respectively.

12. The calculation device of claim 7 , wherein

the 5-way sorter extends plain sentence spaces of five respective sorted homomorphic ciphertexts.

13. A non-transitory computer-readable recording medium including a program for a computer processing homomorphic ciphertexts, the program causing the computer to execute:

receiving an input of an instruction for sorting a plurality of homomorphic ciphertexts; and

sorting the homomorphic ciphertexts by using a 5-way sorter which can sort five homomorphic ciphertexts in a single stage, wherein

the 5-way sorter is configured to:

based on a first homomorphic ciphertext, a second homomorphic ciphertext, and a third homomorphic ciphertext being input, and using a comparison function between two input values, calculate a larger value and a smaller value between the first homomorphic ciphertext and the second homomorphic ciphertext,

input the larger value and the third homomorphic ciphertext into the comparison function and output a first output value,

input the smaller value and the third homomorphic ciphertext into the comparison function and output a third output value, and

calculate a second output value by subtracting the first output value and the third output value from a summed-up value of the first to third homomorphic ciphertexts and output the second output value.