Search

US-12621123-B2 - Encryption processing apparatus and encryption processing method

US12621123B2US 12621123 B2US12621123 B2US 12621123B2US-12621123-B2

Abstract

In order to realize four arithmetic operations in Integer-wise type TFHE, an encryption processing apparatus that processes a ciphertext is provided, the ciphertext being a fully homomorphic ciphertext that has, as a plaintext associated with an integer, a value with an error having a predetermined variance added thereto within a predetermined value range and that is able to be subjected to a predetermined operation between integers without being decrypted. The apparatus includes applying a first polynomial in which all coefficients are the same to an operation result of a homomorphic operation between a ciphertext based on a first ciphertext (ca) and a ciphertext based on a second ciphertext (cb), to obtain a third ciphertext (cd) indicating a position of a plaintext in the operation result, and applying a predetermined polynomial to a ciphertext obtained by reducing a range of plaintext to a predetermined range in the value range by homomorphic addition of the third ciphertext to the operation result, to perform an operation between the first ciphertext and the second ciphertext.

Inventors

  • Yusuke HOSHIZUKI
  • Kotaro MATSUOKA

Assignees

  • AXELL CORPORATION

Dates

Publication Date
20260505
Application Date
20240508

Claims (14)

  1. 1 . An encryption processing apparatus that processes a ciphertext, the ciphertext being a fully homomorphic ciphertext that has, as a plaintext associated with an integer, a value with an error having a predetermined variance added thereto within a predetermined value range and that is able to be subjected to a predetermined operation between integers without being decrypted, the apparatus comprising a processor that performs a process including: applying a first polynomial in which all coefficients are the same to an operation result of a homomorphic operation between a ciphertext based on a first ciphertext and a ciphertext based on a second ciphertext, to obtain a third ciphertext indicating a position of a plaintext in the operation result; and applying a predetermined polynomial to a ciphertext obtained by reducing a range of plaintext to a predetermined range in the value range by a homomorphic addition of the third ciphertext to the operation result, to perform an operation between the first ciphertext and the second ciphertext.
  2. 2 . The encryption processing apparatus according to claim 1 , the processor performing the process further comprising: performing homomorphic addition or homomorphic subtraction of the third ciphertext to or from an operation result of homomorphic addition between the ciphertext based on the first ciphertext and the ciphertext based on the second ciphertext, to obtain a fourth ciphertext for which a range of plaintext has been reduced to a predetermined range in the value range; performing homomorphic addition or homomorphic subtraction of the third ciphertext to or from an operation result of homomorphic subtraction of the ciphertext based on the second ciphertext from the ciphertext based on the first ciphertext, to obtain a fifth ciphertext for which a range of plaintext has been reduced to the predetermined range in the value range; and performing an operation between the first ciphertext and the second ciphertext by using the fourth ciphertext and the fifth ciphertext.
  3. 3 . The encryption processing apparatus according to claim 1 , the processor performing the process further comprising: performing homomorphic addition or homomorphic subtraction of the third ciphertext to or from an operation result of homomorphic addition of the ciphertext based on the second ciphertext to the ciphertext based on the first ciphertext, to obtain a fourth ciphertext for which a range of plaintext has been reduced to the predetermined range in the value range; performing homomorphic subtraction of the first or second ciphertext from the fourth ciphertext or performing homomorphic subtraction of the fourth ciphertext from the first ciphertext to obtain a fifth ciphertext for which a range of plaintext has been reduced to the predetermined range in the value range; and performing an operation between the first ciphertext and the second ciphertext by using the fourth ciphertext and the fifth ciphertext.
  4. 4 . The encryption processing apparatus according to claim 1 , the processor performing the process further comprising: performing homomorphic addition or homomorphic subtraction of the third ciphertext to or from an operation result of homomorphic subtraction of the ciphertext based on the second ciphertext from the ciphertext based on the first ciphertext, to obtain a fifth ciphertext for which a range of plaintext has been reduced to the predetermined range in the value range; performing homomorphic addition of the second ciphertext to the fifth ciphertext or performing homomorphic subtraction of the first ciphertext from the fifth ciphertext or performing homomorphic subtraction of the fifth ciphertext from the first ciphertext, to obtain a fourth ciphertext for which a range of plaintext has been reduced to the predetermined range in the value range; and performing an operation between the first ciphertext and the second ciphertext by using the fourth ciphertext and the fifth ciphertext.
  5. 5 . The encryption processing apparatus according to claim 2 , the processor performing the process further comprising: applying a second polynomial to the fourth ciphertext to obtain a sixth ciphertext; applying a third polynomial to the fifth ciphertext to obtain a seventh ciphertext; and subtracting the seventh ciphertext from the sixth ciphertext in a homomorphic manner to obtain a ciphertext corresponding to a result of multiplication between plaintexts of the first and second ciphertexts.
  6. 6 . The encryption processing apparatus according to claim 2 , the processor performing the process further comprising: applying a fourth polynomial having a first coefficient and a second coefficient to the fourth ciphertext to obtain an eighth ciphertext based on the first coefficient and a ninth ciphertext based on the second coefficient; applying a fifth polynomial having a third coefficient and a fourth coefficient to the fifth ciphertext to obtain a tenth ciphertext based on the third coefficient and an eleventh ciphertext based on the fourth coefficient; and subtracting the tenth ciphertext from the eighth ciphertext in a homomorphic manner to obtain a ciphertext corresponding to upper bits of a result of multiplication between plaintexts of the first and second ciphertexts, and subtracting the eleventh ciphertext from the ninth ciphertext in a homomorphic manner to obtain a ciphertext corresponding to lower bits of the result of multiplication.
  7. 7 . The encryption processing apparatus according to claim 6 , the apparatus further comprising: a first table in which a calculated value of the first coefficient is stored; a second table in which a calculated value of the second coefficient is stored; a third table in which a calculated value of the third coefficient is stored; and a fourth table in which a calculated value of the fourth coefficient is stored; wherein the processor performs the process further comprising: referring to the first table and the second table at the same time by applying the fourth polynomial to the fourth ciphertext, to obtain the eighth ciphertext or the ninth ciphertext; and referring to the third table and the fourth table at the same time by applying the fifth polynomial to the fifth ciphertext, to obtain the tenth ciphertext or the eleventh ciphertext.
  8. 8 . The encryption processing apparatus according to claim 1 , the processor performs the process further comprising: dividing a coefficient in the first ciphertext by 2 to obtain the ciphertext based on the first ciphertext; and dividing a coefficient in the second ciphertext by 2 to obtain the ciphertext based on the second ciphertext.
  9. 9 . The encryption processing apparatus according to claim 1 , wherein the ciphertext based on the first ciphertext is a first ciphertext, a coefficient in the third ciphertext is divided by 2, to obtain a new ciphertext as the third ciphertext, the ciphertext based on the second ciphertext is a second ciphertext, and a coefficient in the fourth ciphertext is divided by 2, to obtain a new ciphertext as the fourth ciphertext.
  10. 10 . The encryption processing apparatus according to claim 1 , further comprising a calculation unit configured to apply a predetermined polynomial to a ciphertext to obtain a new ciphertext, wherein the calculation unit performs a process of reducing number of coefficients in a ciphertext as input before applying the predetermined polynomial to the ciphertext as input to obtain the new ciphertext.
  11. 11 . The encryption processing apparatus according to claim 1 , comprising performing the predetermined operation to perform a process involved in fuzzy authentication or fuzzy search using the ciphertext input thereto.
  12. 12 . The encryption processing apparatus according to claim 1 , comprising performing the predetermined operation to process a query based on the ciphertext input thereto for an encryption database.
  13. 13 . An encryption processing method, executed by a processor, of processing a ciphertext, the ciphertext being a fully homomorphic ciphertext that has, as a plaintext associated with an integer, a value with an error having a predetermined variance added thereto within a predetermined value range and that is able to be subjected to a predetermined operation between integers without being decrypted, the method comprising: applying a first polynomial in which all coefficients are the same to an operation result of a homomorphic operation between a ciphertext based on a first ciphertext and a ciphertext based on a second ciphertext, to obtain a third ciphertext indicating a position of a plaintext in the operation result; and applying a predetermined polynomial to a ciphertext obtained by reducing a range of plaintext to a predetermined range in the value range by a homomorphic operation of the third ciphertext to the operation result, to perform an operation between the first ciphertext and the second ciphertext.
  14. 14 . A non-transitory computer-readable recording medium storing a program for causing a processor to perform an encryption process of processing a ciphertext, the ciphertext being a fully homomorphic ciphertext that has, as a plaintext associated with an integer, a value with an error having a predetermined variance added thereto within a predetermined value range and that is able to be subjected to a predetermined operation between integers without being decrypted, the program comprising: applying a first polynomial in which all coefficients are the same to an operation result of a homomorphic operation between a ciphertext based on a first ciphertext and a ciphertext based on a second ciphertext, to obtain a third ciphertext indicating a position of a plaintext in the operation result; and applying a predetermined polynomial to a ciphertext obtained by reducing a range of plaintext to a predetermined range in the value range by a homomorphic addition of the third ciphertext to the operation result, to perform an operation between the first ciphertext and the second ciphertext.

Description

CROSS-REFERENCE TO RELATED APPLICATION This application is based upon and claims the benefit of priorities to Japanese Patent Application No. 2023-83822, filed on May 22, 2023, and Japanese Patent Application No. 2024-025934, filed on Feb. 22, 2024, with the Japanese Patent Office, the entire contents of which are incorporated herein by reference in its entirety. FIELD The embodiments discussed herein are related to an encryption processing apparatus, an encryption processing method, and a non-transitory computer-readable recording medium. BACKGROUND 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. There are conventionally known additive homomorphic encryption that performs only an additive operation (addition and subtraction) while a finite cyclic group is regarded as an integer and multiplicative homomorphic encryption that performs only a multiplicative operation (multiplication) while a finite cyclic group is regarded as an integer. For the finite cyclic group, an integral multiple can be obtained by repeating addition, and therefore an integral multiple by a plaintext can be calculated. Also, exponentiation by a plaintext can be calculated by repeating multiplication. There are also known ring homomorphic encryption that processes both an additive operation and a multiplicative operation while ciphertexts remain encrypted and fully homomorphic encryption (FHE) that allows all arithmetic operations including addition and multiplication. One of known fully homomorphic encryption techniques is fully homomorphic encryption based on the LWE (Learning with Errors) problem, which 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. In the fully homomorphic encryption based on the LWE problem, an error is accumulated as an operation is repeated, and therefore, bootstrapping for reducing an error component while the error component remains encrypted is performed before the error becomes too large to allow decryption. The computation time of bootstrapping occupies most of the computation time required when an operation is performed by fully homomorphic encryption. Further, the amount of computation is large in bootstrapping, because bootstrapping handles a large amount of data. Therefore, in the operation of fully homomorphic encryption, there is a problem that the operation result cannot be obtained within a practical time. A scheme that drastically improves 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 “aforementioned paper” in the following descriptions). Homomorphic encryption includes Bit-wise type homomorphic encryption having two values as a plaintext and based on a logical operation, and Integer-wise type homomorphic encryption having a whole integer as a plaintext as one ciphertext. TFHE described in the “aforementioned paper” is the Bit-wise type. The plaintext in TFHE is a real number from 0 to 1 associated with a circle group. Therefore, by associating sections obtained by dividing the range from 0 to 1 of the circle group with integers in turn, TFHE can be applied as Integer-wise type homomorphic encryption having an integer as the plaintext (for example, Integerwise Functional Bootstrapping on TFHE, 2020, Hiroki Okada, Shinsaku Kiyomoto, and Carlos Cid). If TFHE can be used as homomorphic encryption that enables four arithmetic operations to be performed in an Integer-wise manner, more efficient processing can be performed as compared with bit-by-bit computation. A TLWE ciphertext used in TFHE is shown by the aforementioned paper as being an additive homomorphic type for a plaintext on a circle group, and it is obvious that addition (subtraction) can be performed. Meanwhile, as for multiplication, although multiplication between an integer and a circle group (a ciphertext) is defined because the circle group is a Z-module, a multiplicative operation between circle groups is not obvious because it is not defined. It is an object of an aspect of the present invention to enable multiplication between ciphertexts, and to fully realize four arithmetic operations in Integer-wise TFHE. SUMMARY According to an aspect of the present invention, an encryption processing apparatus processes a ciphertext, the ciphertext being a fully homomorphic ciphertext that has, as a plaintext associated with an integer, a value with an error having a predeterm