Practical sorting on large-scale encrypted data
AssigneesCrypto Lab Inc., Seoul National University R&Db Foundation
InventorsJung Hee Cheon, Seungwan Hong
Life of this patent
Estimating the term…
Abstract
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.
Claims15
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.
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.
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.
Dependencies are inferred from the claim text.