# US 12,192,320 B2 · Encryption method and apparatus using homomorphic encryption > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,192,320 B2 - Document ID: US12192320B2 - Status: Granted - Kind: B2 - Application number: 17/218,790 - Filed: 2021-03-31 - Published: 2021-11-11 - Granted: 2025-01-07 - Earliest claimed: 2020-05-08 - Assignees: Samsung Electronics Co., Ltd.; Snu R&Db Foundation; Industry-Academic Cooperation Foundation, Chosun University - Applicants: Samsung Electronics Co., Ltd; Snu R&Db Foundation; Industry-Academic Cooperation Foundation, Chosun University - Inventors: Jong-Seon No; Joonwoo Lee; Young-Sik Kim; Yongwoo Lee; Eunsang Lee - Web page: https://patentgrep.com/patent/US12192320B2 ## CPC - H04L 9/008: {involving homomorphic encryption} - H04L 2209/12: Details relating to cryptographic hardware or logic circuitry - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract Disclosed is an encryption method and apparatus. The encryption method using homomorphic encryption may include generating a ciphertext by encrypting data, and bootstrapping the ciphertext by performing a modular reduction based on a selection of one or more target points for a modulus corresponding to the ciphertext. ## Claims ### Claim 1 A processor-implemented encryption method using homomorphic encryption, the encryption method comprising: encrypting plain text data into a first ciphertext; performing a first homomorphic operation on the first ciphertext to generate a second ciphertext, the second ciphertext comprises a coefficient that is higher than coefficient of the first ciphertext due to noise introduced during the first homomorphic operation; generating a target polynomial based on the increased coefficient, the target polynomial corresponds to a modular reduction, comprising: iteratively determining one or more reference points based on a predetermined degree of the target polynomial; determining a predetermined polynomial that passes through the one or more reference points where absolute values of error between the predetermined polynomial and a determined piecewise continuous function at the one or more reference points alternate in sign; selecting one or more target points from the predetermined polynomial and the determined piecewise continuous function such that the one or more target points alternate in sign; and generating the target polynomial based on absolute values of error of the one or more target points being within a predefined range corresponding to the increased coefficient; and generating a third ciphertext based on the target polynomial where the target polynomial reduces the increased coefficient within the predefined range to enable additional homomorphic operation, by performing a second homomorphic operation on the second ciphertext. ### Claim 2 (depends on 1) The encryption method of claim 1, further comprising performing the determining of the predetermined polynomial, comprising: generating the predetermined polynomial such that absolute values of errors, between the predetermined polynomial and the determined piecewise continuous function that passes through the one or more reference points, are a predetermined value. ### Claim 3 (depends on 2) The encryption method of claim 2, further comprising generating of the predetermined polynomial includes generating the predetermined polynomial such that an error at a first reference point included in the one or more reference points and an error at a second reference point adjacent to the first reference point are different in sign, and absolute values of the error at the first reference point and the error at the second reference point are the predetermined value. ### Claim 4 (depends on 1) The encryption method of claim 1, further comprising performing the selecting of the one or more target points, including selecting target points from among a total candidate points whose absolute values are greater than or equal to a predetermined value among determined error points between the predetermined polynomial and the piecewise continuous function that passes through the one or more reference points, where a total number of the selected target points is based on the degree of the target polynomial. ### Claim 5 (depends on 4) The encryption method of claim 4, further comprising determining the candidate points to have the absolute values be greater than or equal to the predetermined value among the determined error points, wherein the selecting of the target points comprises selecting the target points, from among the candidate points, such that, a maximum error value and a minimum error value appear in alternation. ### Claim 6 (depends on 4) The encryption method of claim 4, wherein the selecting of the target points comprises selecting the target points such that a sum of the absolute values of the errors is maximized. ### Claim 7 (depends on 1) The encryption method of claim 1, wherein the generating of the target polynomial comprises generating the target polynomial having a relative error, between a maximum value and a minimum value among the absolute values of the one or more determined error points, less than a threshold. ### Claim 8 (depends on 1) The encryption method of claim 1, further comprising a basis of the target polynomial being a basis of Chebyshev polynomials. ### Claim 9 (depends on 1) A non-transitory computer-readable storage medium storing instructions that, when executed by one or more processors, configure the one or more processors to perform the method of claim 1. ### Claim 10 (depends on 1) The encryption method of claim 1, for the one or more reference points, wherein the target polynomial corresponds to the modular reduction and the predetermined polynomial satisfies the equation p(xi)−f(xi)=(−1)iE i=1, . . . , d+2, where f (x) is a function corresponding to the modular reduction, p(x) is the predetermined polynomial, and E is a predetermined value. ### Claim 11 An encryption apparatus using homomorphic encryption, the encryption apparatus comprising: one or more processors configured to: encrypt plain text data into a first ciphertext; perform a first homomorphic operation on the first ciphertext to generate a second ciphertext, the second ciphertext comprises a coefficient that is higher than coefficient of the first ciphertext due to noise introduced during the first homomorphic operation; generate a target polynomial based on the increased coefficient, the target polynomial corresponds to a modular reduction, the generation of the target polynomial comprising: an iterative determination of one or more reference points based on a predetermined degree of the target polynomial; a determination of a predetermined polynomial that passes through the one or more reference points where absolute values of error between the predetermined polynomial and a determined piecewise continuous function at the one or more reference points alternate in sign; a selection of one or more target points from the predetermined polynomial and the determined piecewise continuous function such that the one or more target points alternate in sign; and a generation of the target polynomial based on absolute values of error of the one or more target points being within a predefined range corresponding to the increased coefficient; and generate a third ciphertext based on the target polynomial where the target polynomial reduces the increased coefficient within the predefined range to enable additional homomorphic operation, by performing a second homomorphic operation on the second ciphertext. ### Claim 12 (depends on 11) The encryption apparatus of claim 11, wherein, for the generation of the target polynomial, the one or more processors are further configured to generate the target polynomial that is determined a most accurate representation of the modular reduction. ### Claim 13 (depends on 11) The encryption apparatus of claim 11, wherein the one or more processors are further configured to: generate the predetermined polynomial such that absolute values of errors, between the predetermined polynomial and a determined piecewise continuous function that passes through the one or more reference points, are a predetermined value. ### Claim 14 (depends on 13) The encryption apparatus of claim 13, wherein the one or more processors are further configured to determine the one or more reference points based on the degree of the target polynomial, and wherein, for the generation of the predetermined polynomial, the one or more processors are configured to generate the predetermined polynomial such that an error at a first reference point included in the one or more reference points and an error at a second reference point adjacent to the first reference point are different in sign, and absolute values of the error at the first reference point and the error at the second reference point are the predetermined value. ### Claim 15 (depends on 11) The encryption apparatus of claim 11, wherein the one or more processors are further configured to perform the selection of the one or more target points, including a selection of target points from among a total candidate points whose absolute values are greater than or equal to a predetermined value among determined error points between the predetermined polynomial and the piecewise continuous function that passes through the one or more reference points, where a total number of selected target points is based on the degree of the target polynomial. ### Claim 16 (depends on 15) The encryption apparatus of claim 15, wherein the one or more processors are further configured to determine the candidate points to have the absolute values be greater than or equal to the predetermined value among the determined error points, and wherein, for the performance of the selection, the one or more processors are configured to select the target points from among the candidate points such that a maximum error value and a minimum error value appear in alternation. ### Claim 17 (depends on 15) The encryption apparatus of claim 15, wherein, for the performance of the selection, the one or more processors are further configured to select the target points such that a sum of the absolute values of the errors is maximized. ### Claim 18 (depends on 11) The encryption apparatus of claim 11, wherein, for the generation of the target polynomial, the one or more processors are further configured to generate the target polynomial having a relative error, between a maximum value and a minimum value among the absolute values of the one or more determined error points, less than a threshold. ### Claim 19 (depends on 12) The encryption apparatus of claim 12, wherein a basis of the target polynomial is a basis of Chebyshev polynomials. ### Claim 20 An apparatus configured to perform a homomorphic encryption scheme, comprising: one or more processors configured to: encrypt plain text data into a first ciphertext; perform a first homomorphic operation on the first ciphertext to generate a second ciphertext, the second ciphertext comprises a coefficient that is higher than coefficient of the first ciphertext due to noise introduced during the first homomorphic operation; generate a target polynomial based on the increased coefficient, the target polynomial corresponds to a modular reduction, the generation of the target polynomial comprising: an iterative determination of one or more reference points based on a predetermined degree of the target polynomial; a determination of a predetermined polynomial that passes through the one or more reference points where absolute values of error between the predetermined polynomial and a determined piecewise continuous function at the one or more reference points alternate in sign and have equal absolute values; a determination of candidate points having absolute values that are greater than or equal to the predetermined value among extreme points between the predetermined polynomial and the piecewise continuous function that passes through the one or more reference points; a determination of one or more target points from among the candidate points such that a maximum error value and a minimum error value alternates, or a sum of absolute values of the extreme points is maximized within a predefined range corresponding to the increased coefficient; and a generation of the target polynomial based on the one or more target points; and generate a third ciphertext based on the target polynomial where the target polynomial reduces the increased coefficient within the predefined range to enable additional homomorphic operation, by performing a second homomorphic operation on the second ciphertex. ### Claim 21 (depends on 20) The apparatus of claim 20, wherein the target polynomial is generated using Chebyshev alternation theorem.