Search

US-12621120-B2 - Encryption processing device and encryption processing method

US12621120B2US 12621120 B2US12621120 B2US 12621120B2US-12621120-B2

Abstract

An operation by a full adder that achieves fully homomorphic encryption is speeded up. Ciphertexts are ciphertexts of fully homomorphic encryption that allow a logical operation to be performed without decryption. A sorting process is performed which rearranges the ciphertexts arranged in a predetermined order in accordance with a predetermined method. In the sorting process, a homomorphic operation based on a first ciphertext and a second ciphertext is performed. From a result of this homomorphic operation and a ciphertext obtained based on a predetermined polynomial, new first and second ciphertexts are calculated. When the first and second ciphertexts and the new first and second ciphertexts satisfy a predetermined condition, the first ciphertext and the second ciphertext are swapped.

Inventors

  • Yusuke HOSHIZUKI
  • Kotaro MATSUOKA

Assignees

  • AXELL CORPORATION

Dates

Publication Date
20260505
Application Date
20230925
Priority Date
20210326

Claims (8)

  1. 1 . An encryption processing device that processes a ciphertext, the device comprising: a storage unit configured to store the ciphertext, wherein the ciphertext has two values as a plaintext and is a ciphertext of fully homomorphic encryption that allows a logical operation without decryption, each of the two values being obtained by adding an error having a predetermined variance to a predetermined value corresponding to a symbol 0 or 1; and a processor operatively coupled to the storage unit, the processor configured to execute a process including: performing an encryption processing process in which new ciphertexts respectively corresponding to a plaintext of a first ciphertext and a plaintext of a second ciphertext arranged in a predetermined order are capable of being obtained in a same order as or in a reverse order to the predetermined order, and an order of the new ciphertexts is selected based on a plaintext of a third ciphertext, reducing the number of calculations required for the encryption processing process by using a multi-value logical operation outputting a temporary ciphertext that is based on the ciphertext and has multiple values more than two values as a plaintext; and causing the new ciphertexts to be stored in the storage unit.
  2. 2 . The encryption processing device according to claim 1 , wherein number of operations by a polynomial when the multi-value logical operation is performed using the ciphertext is reduced by setting the error in such a manner that an overlap of errors falls within a predetermined value.
  3. 3 . The encryption processing device according to claim 1 , wherein the processor executes a process including: performing a homomorphic operation involved in a predetermined operation, for the ciphertext input thereto; and calculating a new ciphertext using a predetermined polynomial for a result of the homomorphic operation, and reducing number of coefficients of the ciphertext before calculation of the new ciphertext using the predetermined polynomial for the result of the homomorphic operation.
  4. 4 . The encryption processing device according to claim 1 , wherein bubble sort is carried out by performing the process.
  5. 5 . The encryption processing device according to claim 1 , wherein ciphertexts to be swapped are values stored in an aggregation table to which values stored in an encrypted database are aggregated, the values stored in the encrypted database include a plurality of reference values used as a reference for aggregation and values associated with the respective reference values, the aggregation table includes the plurality of reference values and results of aggregation of values associated with the respective reference values in the encrypted database, aggregation on the encrypted database is performed by aggregating, based on a result of comparison between the reference value for aggregation included in the aggregation table and the reference value included in the encrypted database, a value in the encrypted database corresponding to the reference value for aggregation in association with the reference value for aggregation in the aggregation table, and the process is performed for the aggregation table after aggregation.
  6. 6 . The encryption processing device according to claim 5 , wherein the reference values and the reference values for aggregation are each formed by a multi-bit value, the comparison is performed by aggregating a result of bit-by-bit comparison between one of the reference values and one of the reference values for aggregation, and the aggregation on the encrypted database is performed by adding a value based on a result of the comparison and a value corresponding to the reference value to a corresponding total value in the aggregation table.
  7. 7 . An encryption processing method that processes a ciphertext and is performed by a processor, wherein the ciphertext has two values as a plaintext and is a ciphertext of fully homomorphic encryption that allows a logical operation without decryption, each of the two values being obtained by adding an error having a predetermined variance to a predetermined value corresponding to a symbol 0 or 1, wherein the encryption processing method includes: performing an encryption processing process in which new ciphertexts respectively corresponding to a plaintext of a first ciphertext and a plaintext of a second ciphertext arranged in a predetermined order are able to be obtained in a same order as or in a reverse order to the predetermined order, and an order of the new ciphertexts can be selected based on a plaintext of a third ciphertext, and reducing number of calculations required for the process by using a multi-value logical operation outputting a temporary ciphertext that is based on the ciphertext and has multiple values more than two values as a plaintext.
  8. 8 . A non-transitory computer-readable recording medium storing therein a program for causing a processor to perform an encryption processing method that processes a ciphertext, wherein the ciphertext has two values as a plaintext and is a ciphertext of fully homomorphic encryption that allows a logical operation without decryption, each of the two values being obtained by adding an error having a predetermined variance to a predetermined value corresponding to a symbol 0 or 1, the encryption processing method includes: performing an encryption processing process in which new ciphertexts respectively corresponding to a plaintext of a first ciphertext and a plaintext of a second ciphertext arranged in a predetermined order are able to be obtained in a same order as or in a reverse order to the predetermined order, and an order of the new ciphertexts can be selected based on a plaintext of a third ciphertext, and reducing number of calculations required for the process by using a multi-value logical operation outputting a temporary ciphertext that is based on the ciphertext and has multiple values more than two values as a plaintext.

Description

CROSS-REFERENCE TO RELATED APPLICATION This application is a continuation of and claims priority to International Application No. PCT/JP2022/001829 filed on Jan. 19, 2022, entitled Encryption Processing Device, Encryption Processing Method, and Encryption Processing Program, which claims priority to Japanese Application No. 2021-053360 and Japanese Application No. 2021-131701, all of which are incorporated herein by reference in their entireties. FIELD OF THE INVENTION The embodiments discussed herein are related to an encryption processing device, an encryption processing method, and an encryption processing program that process a ciphertext. BACKGROUND OF THE INVENTION Homomorphic encryption is an encryption technique that can process encrypted data without decrypting the encrypted data. Encryption that allows an operation between ciphertexts, corresponding to addition of plaintexts, to be performed is additive homomorphic encryption, and encryption that allows an operation between ciphertexts, corresponding to multiplication of plaintexts, to be performed is multiplicative homomorphic encryption. Additive homomorphic encryption and multiplicative homomorphic encryption have been conventionally known in which while a finite cyclic group is regarded as an integer, only an additive operation (addition and subtraction) and a multiplicative operation (multiplication) are performed, respectively. Since the finite cyclic group can be multiplied by an integer by repeating addition, a “plaintext” can be multiplied by an integer, and the “plaintext” can be exponentiated by repeating multiplication. There is also known fully homomorphic encryption (FHE) that allows both an additive operation (addition and subtraction) and a multiplicative operation (multiplication) to be performed while ciphertexts remain encrypted. Fully homomorphic encryption known at present uses somewhat homomorphic encryption, for example, based on the LWE problem, which allows addition/subtraction and multiplication to be performed multiple times. When being based on the LWE problem, somewhat homomorphic encryption is configured by adding a small error to a plaintext in an encryption process to such an extent that there is no problem in decryption. Somewhat homomorphic encryption is not limited to LWE encryption. In somewhat homomorphic encryption based on the LWE problem, an error is accumulated as an operation is performed, and therefore bootstrapping for reducing an error component is performed while the error component remains encrypted before the error becomes too large to be decrypted. Such bootstrapping requires an enormous amount of data and an enormous amount of calculation. Therefore, it cannot be said that fully homomorphic encryption has been realized in a practical sense. A method for drastically improving this problem is TFHE (Fast Fully Homomorphic Encryption over the Torus) described in “TFHE: Fast Fully Homomorphic Encryption over the Torus. Journal of Cryptology, 33:34-91, 2020, I. Chillotti, N. Gama, M. Georgieva, and M. Izabachene” (referred to as the aforementioned paper in the following descriptions). Homomorphic encryption including TFHE draws attention also as encryption for implementing an encrypted database in which values or data stored are encrypted. As described above, homomorphic encryption is an encryption technique that can process encrypted data without decrypting the data, i.e., while the data remains encrypted. In the encrypted database, indices cannot be created. However, by encrypting not only values on the database but also a query by homomorphic encryption, it is possible to perform an operation such as search without decrypting the values and the query, i.e., concealing the contents. Another example of the operation for the encrypted database is an operation of aggregating values on the database by category and sorting the aggregation results in ascending order or descending order. SUMMARY OF THE INVENTION According to an aspect of the embodiments, an encryption processing device processes a ciphertext, where the ciphertext has two values as a plaintext and is a ciphertext of fully homomorphic encryption that allows a logical operation without decryption, each of the two values being obtained by adding an error having a predetermined variance to a predetermined value corresponding to a symbol 0 or 1, new ciphertexts respectively corresponding to a plaintext of a first ciphertext and a plaintext of a second ciphertext arranged in a predetermined order are able to be obtained in a same order as or in a reverse order to the predetermined order, a process that is able to select an order of the new ciphertexts based on a plaintext of a third ciphertext is performed, and the number of calculations required for the process is reduced by using a multi-value logical operation outputting a temporary ciphertext that is based on the ciphertext and has multiple values more than two values as a plaintext. The objects