Back to results
US 12,149,604 B2Granted
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
Disclosed is a calculation device. The present calculation device includes: a memory for storing a plurality of homomorphic ciphertexts for an approximate message including an error; and a processor for sorting the plurality of homomorphic ciphertexts by using a 5-way sorter which can sort five homomorphic ciphertexts in a single stage.
Claims13
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.
5 more elements
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.
7 more elements
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.
5 more elements
Dependencies are inferred from the claim text.