Practical sorting on large-scale encrypted data
View Patent ↗A method for processing homomorphic ciphertexts includes: receiving an input of an instruction for sorting regarding a plurality of homomorphic ciphertexts; sorting the plurality of homomorphic ciphertexts by using a sorter which can sort 3 more homomorphic ciphertexts in a single stage; and outputting the sorting result. The sorter performs sorting by using a comparison function that selectively outputs a bigger value or a smaller value between two input values.
1 . A method for processing homomorphic ciphertexts, the method comprising:
receiving an input of an instruction for sorting regarding a plurality of homomorphic ciphertexts;
sorting the homomorphic ciphertexts by using a k-way sorter configured to sort k homomorphic ciphertexts in a single stage, wherein k is an integer equal to or greater than 3; and
outputting a sorting result, wherein
the k-way sorter is configured to:
perform sorting by using a comparison function that selectively outputs a bigger value or a smaller value between two input values,
divide the k homomorphic ciphertexts into a first group and a second group by sorting each of the first group and the second group using at least one of a 3-way sorter and a less-than (LT) comparison function, and
generate k sorted homomorphic ciphertexts by performing homomorphic operations based on sorting results of the first group and the second group.
2 . The method for processing homomorphic ciphertexts of claim 1 , wherein
the sorting comprises:
performing a parallel sorting process by using a plurality of the k-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 bigger 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 k-way sorter is 5-way sorter:
the 5-way sorter is configured to:
based on a first homomorphic ciphertext, a second homomorphic ciphertext, and a third homomorphic ciphertext being input, calculate a bigger value and a smaller value between the first homomorphic ciphertext and the second homomorphic ciphertext by using the comparison function, input the calculated bigger value and the third homomorphic ciphertext into the comparison function and output a first output value, input the calculated 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 for the first to third homomorphic ciphertexts and output the second output value.
7 . The method for processing homomorphic ciphertexts of claim 1 , wherein
the k-way sorter extends plain sentence spaces of the k sorted homomorphic ciphertexts.
8 . A calculation device comprising:
a memory that stores a plurality of homomorphic ciphertexts for an approximate message including an error; and
a processor that sort the homomorphic ciphertexts
by using a k-way sorter configured to sort k homomorphic ciphertexts in a single stage, wherein k is an integer equal to or greater than 3, wherein
the k-way sorter is configured to:
perform sorting by using a comparison function that selectively outputs a bigger value or a smaller value between two input values,
divide the k homomorphic ciphertexts into a first group and a second group by sorting each of the first group and the second group using at least one of a 3-way sorter and a less-than (LT) comparison function, and
generate k sorted homomorphic ciphertexts by performing homomorphic operations based on sorting results of the first group and the second group.
9 . The calculation device of claim 8 , wherein
the processor is configured to:
perform a parallel sorting process by using a plurality of the k-way sorters.
10 . The calculation device of claim 8 , 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.
11 . The calculation device of claim 10 , 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 bigger 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.
12 . The calculation device of claim 11 , wherein
the approximate sign function is a function which is a result of repetitively calculating two different composite functions by three times, respectively.
13 . The calculation device of claim 8 , wherein
the k-way sorter is 5-way sorter:
the 5-way sorter is configured to:
based on a first homomorphic ciphertext, a second homomorphic ciphertext, and a third homomorphic ciphertext being input, calculate a bigger value and a smaller value between the first homomorphic ciphertext and the second homomorphic ciphertext by using the comparison function, input the calculated bigger value and the third homomorphic ciphertext into the comparison function and output a first output value, input the calculated 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 for the first to third homomorphic ciphertexts and output the second output value.
14 . The calculation device of claim 8 , wherein
the k-way sorter extends plain sentence spaces of the k sorted homomorphic ciphertexts.
15 . A non-transitory computer-readable recording medium including a program for executing a method for processing homomorphic ciphertexts, the method comprising:
receiving an input of an instruction for sorting regarding a plurality of homomorphic ciphertexts; and
sorting the homomorphic ciphertexts by using a k-way sorter configured to sort k homomorphic ciphertexts in a single stage, wherein k is an integer equal to or greater than 3, wherein
the k-way sorter is configured to:
perform sorting by using a comparison function that selectively outputs a bigger value or a smaller value between two input values,
divide the k homomorphic ciphertexts into a first group and a second group by sorting each of the first group and the second group using at least one of a 3-way sorter and a less-than (LT) comparison function, and
generate k sorted homomorphic ciphertexts by performing homomorphic operations based on sorting results of the first group and the second group.