Patent Description:
Homomorphic encryption is an encryption method that enables arbitrary operations between encrypted data. Utilizing homomorphic encryption may enable arbitrary operations on encrypted data without decrypting the encrypted data, and homomorphic encryption may be lattice-based and thus resistant to quantum algorithms and safe.

A blind rotation operation technology may be used to perform arbitrary function operations on ciphertext messages in the homomorphic encryption and provide high accuracy for operation results, but may have a disadvantage in that the size of a public key is significantly large.

A blind rotation operation may require a lot of memory, and the amount of computation may greatly increase when the size of a public key necessary for a homomorphic encryption operation is reduced.

Patent literature <CIT> discloses a method for modulus refresh of cipher text in homomorphic encryption, involving generating target cipher text corresponding to second modulus greater than first modulus based on first cipher text and second cipher text.

Patent literature <CIT> discloses a method for performing cryptographic encrypted computation in health care, involving performing blind rotation by performing polynomial multiplication using number-theoretic transform, where a test polynomial is defined.

Document XP'<NUM>: "General Bootstrapping Approach for RLWE-based Homomorphic Encryption" by Kim et al. discloses a general bootstrapping approach for RLWE-based homomorphic encryption.

In one or more general aspects, an apparatus with a homomorphic encryption operation includes: one or more processors configured to: generate a modified vector by preprocessing vector components of an operand ciphertext of a blind rotation operation based on an order of a polynomial of an output ciphertext of the blind rotation operation and a modulus of the operand ciphertext; and generate a homomorphic encryption operation result by performing the blind rotation operation based on a public key for performing the blind rotation operation and the modified vector.

The public key may include a blind rotation key, an automorphism key, and a key-switching key.

The public key may be generated based on the modified vector and a secret key.

For the generating of the modified vector, the one or more processors may be configured to: compare the modulus and the order of the output ciphertext; and generate the modified vector based on a result of the comparing.

For the generating of the modified vector, the one or more processors may be configured to: generate a first set based on a portion of the vector components of the operand ciphertext; and.

generate the modified vector based on a second set, wherein the first set and the second set are disjoint.

For the generating of the homomorphic encryption operation result, the one or more processors may be configured to: determine, in response to a generator of the vector components of the operand ciphertext being unique, a loop index based on the generator; and perform the blind rotation operation based on the loop index.

For the generating of the homomorphic encryption operation result, the one or more processors may be configured to: perform a first blind operation based on a first set of the operand ciphertext; and perform a second blind operation based on a second set of the operand ciphertext.

For the generating of the homomorphic encryption operation result, the one or more processors may be configured to perform the blind rotation operation by performing an increment operation, an automorphism operation, and a key switching operation based on the modified vector.

For the generating of the homomorphic encryption operation result, the one or more processors may be configured to: determine a number of odd numbers and a number of even numbers in the vector components of the operand ciphertext; and add "<NUM>" to the vector components of the operand ciphertext based on a result of comparing the number of odd numbers and the number of even numbers.

For the generating of the homomorphic encryption operation result, the one or more processors may be configured to, in response to the vector components of the operand ciphertext being even, perform the blind rotation operation based on a blind rotation key based on vector components of a secret key of the public key, a negative sum of the vector components of the secret key, and a sum of consecutive vector components among the vector components of the secret key.

The apparatus may include a receiver configured to receive the public key and the operand ciphertext.

In one or more general aspects, a processor-implemented method with a homomorphic encryption operation includes: generating a modified vector by preprocessing vector components of an operand ciphertext of a blind rotation operation based on an order of a polynomial of an output ciphertext of the blind rotation operation and a modulus of the operand ciphertext; and generating a homomorphic encryption operation result by performing the blind rotation operation on the modified vector based on a public key for performing the blind rotation operation.

The public key is generated based on the modified vector and a secret key.

The method of claim <NUM>, wherein the generating of the modified vector may include: comparing the modulus and the order of the output ciphertext; and generating the modified vector based on a result of the comparing.

The generating of the modified vector may include: generating a first set based on a portion of the vector components of the operand ciphertext; and generating the modified vector based on a second set, wherein the first set and the second set are disjoint.

The generating of the homomorphic encryption operation result may include: determining, in response to a generator of the vector components of the operand ciphertext being unique, a loop index based on the generator; and performing the blind rotation operation based on the loop index.

The generating of the homomorphic encryption operation result may include: performing a first blind operation based on a first set of the operand ciphertext; and performing a second blind operation based on a second set of the operand ciphertext.

The generating of the homomorphic encryption operation result may include performing the blind rotation operation by performing an increment operation, an automorphism operation, and a key switching operation based on the modified vector.

The generating of the homomorphic encryption operation result may include: determining a number of odd numbers and a number of even numbers in the vector components of the operand ciphertext; and adding "<NUM>" to the vector components of the operand ciphertext based on a result of comparing the number of odd numbers and the number of even numbers.

The generating of the homomorphic encryption operation result may include performing, in response to the vector components of the operand ciphertext being even, the blind rotation operation based on a blind rotation key based on vector components of a secret key of the public key, a negative sum of the vector components of the secret key, and a sum of consecutive vector components among the vector components of the secret key.

Hereinafter, examples will be described in detail with reference to the accompanying drawings. However, various alterations and modifications may be made to the examples. Here, the examples are not construed as limited to the disclosure. The examples should be understood to include all changes, equivalents, and replacements within the idea and the technical scope of the disclosure.

The terminology used herein is for the purpose of describing particular examples only and is not to be limiting of the examples. As non-limiting examples, terms "comprise" or "comprises," "include" or "includes," and "have" or "has" specify the presence of stated features, numbers, operations, members, elements, and/or combinations thereof, but do not preclude the presence or addition of one or more other features, numbers, operations, members, elements, and/or combinations thereof.

Unless otherwise defined, all terms including technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this disclosure pertains and based on an understanding of the disclosure of the present application. It will be further understood that terms, such as those defined in commonly-used dictionaries, should be interpreted as having a meaning that is consistent with their meaning in the context of the relevant art and the disclosure of the present application and will not be interpreted in an idealized or overly formal sense unless expressly so defined herein.

When describing the examples with reference to the accompanying drawings, like reference numerals refer to like constituent elements and a repeated description related thereto will be omitted. In the description of examples, detailed description of well-known related structures or functions will be omitted when it is deemed that such description will cause ambiguous interpretation of the present disclosure.

Throughout the specification, when a component or element is described as being "on", "connected to," "coupled to," or "joined to" another component, element, or layer it may be directly (e.g., in contact with the other component or element) "on", "connected to," "coupled to," or "joined to" the other component, element, or layer or there may reasonably be one or more other components, elements, layers intervening therebetween. When a component or element is described as being "directly on", "directly connected to," "directly coupled to," or "directly joined" to another component or element, there can be no other elements intervening therebetween. Likewise, expressions, for example, "between" and "immediately between" and "adjacent to" and "immediately adjacent to" may also be construed as described in the foregoing.

The phrases "at least one of A, B, and C", "at least one of A, B, or C", and the like are intended to have disjunctive meanings, and these phrases "at least one of A, B, and C", "at least one of A, B, or C", and the like also include examples where there may be one or more of each of A, B, and/or C (e.g., any combination of one or more of each of A, B, and C), unless the corresponding description and embodiment necessitates such listings (e.g., "at least one of A, B, and C") to be interpreted to have a conjunctive meaning.

The same name may be used to describe an element included in the examples described above and an element having a common function. Unless otherwise mentioned, the descriptions of the examples may be applicable to the following examples and thus, duplicated descriptions will be omitted for conciseness.

The use of the term "may" herein with respect to an example or embodiment, e.g., as to what an example or embodiment may include or implement, means that at least one example or embodiment exists where such a feature is included or implemented, while all examples are not limited thereto.

<FIG> illustrates an example of a homomorphic encryption operation apparatus.

Referring to <FIG>, a homomorphic encryption operation apparatus <NUM> may perform encryption and decryption using homomorphic encryption. The homomorphic encryption operation apparatus <NUM> may perform a blind rotation operation for a homomorphic encryption operation. The homomorphic encryption operation apparatus <NUM> of one or more embodiments may reduce the size of a public key, thereby improving homomorphic encryption technology by reducing the amount of computation of the homomorphic encryption.

The homomorphic encryption operation apparatus <NUM> may generate an operation result by performing a homomorphic encryption operation. The homomorphic encryption operation apparatus <NUM> may generate a ciphertext (e.g., an operand ciphertext) for performing a blind rotation operation. The homomorphic encryption operation apparatus <NUM> may generate a secret key and a public key. The public key may include a key-switching key, a blind rotation key, and/or an automorphism key.

The homomorphic encryption operation apparatus <NUM> may perform a blind rotation operation using the generated secret key, ciphertext, and/or blind rotation key.

Homomorphic encryption may refer to a method of encryption configured to allow various operations to be performed on data as being encrypted. In homomorphic encryption, a result of an operation using ciphertexts may become a new ciphertext, and a plaintext obtained (e.g., determined or generated) by decrypting the ciphertext may be the same as an operation result of the original data before the encryption.

Hereinafter, encrypted data or encrypted text may be referred to as a ciphertext. The ciphertext may be in the form of a polynomial or a vector including a polynomial.

The homomorphic encryption operation apparatus <NUM> may perform a ring learning with errors (RLWE) problem-based homomorphic encryption operation that supports an operation on a ciphertext into which a plaintext including a binary number is encrypted. The homomorphic encryption operation apparatus <NUM> may perform an RLWE problem-based homomorphic encryption operation that supports an operation on a ciphertext into which a plaintext including an integer is encrypted. The homomorphic encryption operation apparatus <NUM> may perform an RLWE problem-based approximate homomorphic encryption operation that supports an operation on a ciphertext into which a plaintext including a real number and/or a complex number is encrypted.

The homomorphic encryption operation apparatus <NUM> may derive the same result as one obtained from an operation performed on the data of a plaintext by decrypting a result obtained from an operation on the data in an encrypted state using homomorphic encryption.

The homomorphic encryption operation apparatus <NUM> may perform an operation on a ciphertext, and may perform a blind rotation operation (e.g., a lookup table (LUT) operation) and key generation. The homomorphic encryption operation apparatus <NUM> may perform an operation on a non-polynomial function using the blind rotation method in homomorphic encryption.

The homomorphic encryption operation apparatus <NUM> may perform an encryption process of encrypting input data in privacy-preserving machine learning (PPML) and application services. The homomorphic encryption operation apparatus <NUM> may be used in an encryption process of encrypting an input value in PPML and application services.

The homomorphic encryption operation apparatus <NUM> of one or more embodiments may improve homomorphic encryption technology by eliminating limitations to space for storing a secret key, thereby adjusting the size of a vector of a secret key and increasing cryptographic safety in homomorphic encryption and application services using homomorphic encryption.

The homomorphic encryption operation apparatus <NUM> may adjust a storage space for storing a key (e.g., a secret key, a key-switching key, an automorphism key, or a blind rotation key) that is used by a server and a client and an amount of computation for a homomorphic encryption operation.

The homomorphic encryption operation apparatus <NUM> may be implemented in the form of a chip and mounted on a hardware accelerator that utilizes homomorphic encryption. The homomorphic encryption operation apparatus <NUM> may be implemented in the form of a chip or a chip implementing software to reduce memory usage of various operation apparatuses. The homomorphic encryption operation apparatus <NUM> of one or more embodiments may improve homomorphic encryption technology by reducing the amount of computation for the homomorphic encryption operation, thereby reducing the overall amount of computation of the server.

The homomorphic encryption operation apparatus <NUM> of one or more embodiments may improve homomorphic encryption technology by providing high cryptographic stability by adjusting the size of the vector of the secret key. The homomorphic encryption operation apparatus <NUM> may perform encryption on input data of the homomorphic encryption operation.

The homomorphic encryption operation apparatus <NUM> may be, or be implemented in, a personal computer (PC), a data server, and/or a portable device.

The portable device may be, or be implemented in, a laptop computer, a mobile phone, a smart phone, a tablet PC, a mobile internet device (MID), a personal digital assistant (PDA), an enterprise digital assistant (EDA), a digital still camera, a digital video camera, a portable multimedia player (PMP), a personal navigation device or portable navigation device (PND), a handheld game console, an e-book, a smart device, a smart watch, a smart band, and/or a smart ring.

The homomorphic encryption operation apparatus <NUM> may include a receiver <NUM> and a processor <NUM> (e.g., one or more processors). The homomorphic encryption operation apparatus <NUM> may further include the memory <NUM> (e.g., one or more memories).

The receiver <NUM> may include a receiving interface. The receiver <NUM> may receive data for performing a homomorphic encryption operation from the outside or from the memory <NUM>. The data may be operand data (e.g., an operand ciphertext) or a key (e.g., a secret key, a key-switching key, an automorphism key, and/or a blind rotation key) for performing a homomorphic encryption operation.

The blind rotation key may be generated based on a ring Gentry, Sahai, Waters (RGSW) ciphertext or a ring learning with errors' (RLWE') ciphertext. The key-switching key may be generated based on the RLWE' ciphertext. The operand ciphertext may be generated based on a learning with errors (LWE) ciphertext.

The receiver <NUM> may receive a public key for performing a blind rotation operation and an operand ciphertext of the blind rotation operation. The public key may include a blind rotation key, an automorphism key, and a key-switching key. The receiver <NUM> may output the received public key and operand ciphertext to the processor <NUM>.

The processor <NUM> may process data stored in the memory <NUM>. The processor <NUM> may execute a computer-readable instructions stored in the memory <NUM> and instructions triggered by the processor <NUM>.

The "processor <NUM>" may be a data processing hardware device including a circuit having a physical structure to perform desired operations. For example, the desired operations may include code or instructions included in a program.

The data processing hardware device may include, for example, a microprocessor, a central processing unit (CPU), a processor core, a multi-core processor, a multiprocessor, an application-specific integrated circuit (ASIC), and/or a field-programmable gate array (FPGA).

The processor <NUM> may generate a modified vector by preprocessing vector components of the operand ciphertext based on an order of a polynomial of an output ciphertext of the blind rotation operation and a modulus of the operand ciphertext.

The processor <NUM> may compare the order of the output ciphertext with the modulus of the operand ciphertext. The processor <NUM> may generate the modified vector based on a result of the comparing.

The processor <NUM> may generate a first set based on a portion of the vector components of the operand ciphertext. The processor <NUM> may generate the modified vector based on a second set, wherein the first set and the second set are disjoint.

The processor <NUM> may generate a homomorphic encryption operation result by performing the blind rotation operation based on the public key and the modified vector. The public key may be generated based on the modified vector and a secret key.

When a generator of the vector components of the operand ciphertext is unique, the processor <NUM> may determine a loop index based on the generator. The processor <NUM> may perform the blind rotation operation based on the loop index.

The processor <NUM> may perform a first blind operation based on the first set of the operand ciphertext. The processor <NUM> may perform a second blind operation based on the second set of the operand ciphertext.

The processor <NUM> may perform the blind rotation operation by performing an increment operation, an automorphism operation, and a key switching operation based on the modified vector.

The processor <NUM> may obtain the number of odd numbers and the number of even numbers in the vector components of the operand ciphertext. The processor <NUM> may add "<NUM>" to the vector components of the operand ciphertext based on a result of comparing the number of odd numbers and the number of even numbers.

When the vector components of the operand ciphertext are even, the processor <NUM> may perform the blind rotation operation based on a blind rotation key based on vector components of a secret key of the public key, a negative sum of the vector components of the secret key, and a sum of consecutive vector components among the vector components of the secret key.

The memory <NUM> may store instructions (or programs) executable by the processor <NUM>. For example, the instructions may include instructions for performing the operation of the processor <NUM> and/or an operation of each component of the processor <NUM>. For example, the memory <NUM> may include a non-transitory computer-readable storage medium storing instructions that, when executed by the processor <NUM>, configure the processor <NUM> to perform any one, any combination, or all of the operations and/or methods described herein with reference to <FIG>.

The memory <NUM> may be implemented as a volatile or non-volatile memory device.

The volatile memory device may be implemented as a dynamic random-access memory (DRAM), a static random-access memory (SRAM), a thyristor RAM (T-RAM), a zero capacitor RAM (Z-RAM), and/or a twin transistor RAM (TTRAM).

The non-volatile memory device may be implemented as an electrically erasable programmable read-only memory (EEPROM), a flash memory, a magnetic RAM (MRAM), a spin-transfer torque (STT)-MRAM, a conductive bridging RAM(CBRAM), a ferroelectric RAM (FeRAM), a phase change RAM (PRAM), a resistive RAM (RRAM), a nanotube RRAM, a polymer RAM (PoRAM), a nano floating gate Memory (NFGM), a holographic memory, a molecular electronic memory device), and/or an insulator resistance change memory.

<FIG> illustrates an example of an operation of a homomorphic encryption operation apparatus (e.g., the homomorphic encryption operation apparatus of <FIG>).

Referring to <FIG>, a ciphertext used by a processor (e.g., the processor <NUM> of <FIG>) for a homomorphic encryption operation may be defined as follows.

In an LWE ciphertext, a ciphertext of a message (or a plaintext) m may be expressed as <MAT>. The ciphertext may be decrypted as expressed by <MAT>. LWEs(m) may denote encryption of the message m using a secret key s.

In an RLWE ciphertext, a ciphertext of the message m may be expressed as <MAT>. The ciphertext may be decrypted as expressed by a · z + b = m + e (mod Q), RLWEz(m) may denote encryption of the message m using a secret key z.

An RLWE ciphertext of the message m using the secret key z may be defined as expressed by Equation <NUM> below, for example.

Here, a denotes a polynomial on a modulus Q, and e denotes an error polynomial with a small coefficient. When each encryption is performed, a and e may be generated at random.

An RLWE' ciphertext of the message m for a secret key s may be defined as expressed by Equation <NUM> below, for example.

Here, (g<NUM>, g<NUM>,. , gd-<NUM>) may be a vector defined in advance for decomposing an arbitrary integer, and may be set in the form of (<NUM>, B, B<NUM>,. , Bd-<NUM>) for an arbitrary integer B or in the form of <MAT> for Qi = Q/qi.

An RGSW ciphertext of the message m for the secret key z may be defined by two RLWE' ciphertexts as expressed by Equation <NUM> below, for example.

Homomorphic encryption operations performed by the processor <NUM> may be defined as follows.

In an automorphism operation of an RLWE ciphertext, automorphism ψt of a polynomial ring may output a(Xt) with respect to an element a(X) of the polynomial ring, and the space of the domain and the space of the codomain may be the same. In the RLWE ciphertext, the processor <NUM> may output <MAT> with respect to an input <MAT> through the automorphism operation.

The processor <NUM> may obtain a ciphertext corresponding to a new secret key z<NUM> from a ciphertext corresponding to a secret key z<NUM> through a key switching operation. The processor <NUM> may obtain a new ciphertext <MAT> with z<NUM> as a secret key using a key-switching key <MAT>, which is a public key, with respect to the input ciphertext <MAT>.

The processor <NUM> may perform a blind rotation operation. The processor <NUM> may perform a blind rotation operation with respect to the ciphertext <MAT> and an arbitrary function f(X) ∈ RQ using a blind rotation key, and output <MAT>.

An odd generator on integers may be defined as follows. <MAT>, which is a ring of integers modulo q, may be integers from "<NUM>" to "q-<NUM>", and may define addition and multiplication. <MAT> may be a subset of the ring of integers modulo q, having inverse elements for multiplication. <MAT> may be a set having inverse elements for multiplication, in the subset of <MAT>. If <MAT> is expressible by powers of gis, then gis may be referred to as generators of <MAT>.

The processor <NUM> may generally consider a case where q is a power of "<NUM>". In this case, <MAT> may have a set of all odd numbers that are less than or equal to q and coprime with "<NUM>". When q is a power of "<NUM>", all of the odd numbers may be expressed by powers of "<NUM>" and "-<NUM>". For example, an odd number may be expressed as <MAT>. Thus, the odd number may be expressed as <MAT>.

A disjoint family of sets may refer to two sets having no elements in common. If components αi of arbitrary vector α having a power of "<NUM>" as a modulus are divided into <MAT> and <MAT> and <MAT> may be a disjoint family of sets.

The processor <NUM> may calculate (e.g., determine) <MAT> from an LWE ciphertext <MAT> , which is an operand ciphertext, using a blind rotation key, thereby performing a blind rotation operation of calculating an operation result of a message to which a function f is applied in <MAT>. The processor <NUM> of one or more embodiments may improve homomorphic encryption technology by reducing the size of a public key and the amount of computation used for the process of the blind rotation operation.

The processor <NUM> may perform the blind rotation operation using akg and ak-g only according to a result of comparing the modulus q and 2N based on an order of an RLWE ciphertext, with the key-switching key not having akt for all odd numbers t.

The processor <NUM> may generate a blind rotation key and a key-switching key, by comparing 2N based on a vector component αi of α of the LWE ciphertext, the modulus q, and the order of the RLWE ciphertext by performing a preprocessing process.

In the process of performing the blind rotation operation, the processor <NUM> may generate a modified vector ω based on a comparison between the modulus q which is the range of vector components of α and vector components of the LWE ciphertext and 2N which is twice the order of the RLWE ciphertext.

The processor <NUM> may update the RLWE ciphertext by performing an automorphism operation, an increment operation, and a key switching operation based on the properties of components ωi of the modified vector.

When an additional operation is used according to the value of the modified vector ω that is generated in the preprocessing process, the processor <NUM> may update the RLWE ciphertext by performing the increment operation.

The processor <NUM> may output <MAT> as a homomorphic encryption operation result.

The processor <NUM> may include an operator <NUM>. A key generator <NUM> and the operator <NUM> may be implemented on different devices, as a non-limiting example. For example, the key generator <NUM> may be implemented on a client, and the operator <NUM> may be implemented on a server.

In an example, the processor <NUM> may include the operator <NUM> and not include the key generator <NUM>. However, in some examples, the processor <NUM> may include the key generator <NUM>.

In operation <NUM>, the key generator <NUM> may generate a secret key. In operation <NUM>, the key generator <NUM> may generate a public key based on the secret key. The public key may include a key-switching key or a blind rotation key. The key generator <NUM> may generate a secret key for an LWE ciphertext and an RLWE ciphertext. The key generator <NUM> may generate an LWE ciphertext based on the generated secret key.

The key generator <NUM> may output the generated public key to a receiver <NUM> and/or the operator <NUM>. The key generator <NUM> may transmit the generated public key wirelessly or wired.

The receiver <NUM> may be, include, and/or operate in the same manner as the receiver <NUM> of <FIG>. The receiver <NUM> may receive an operand ciphertext (e.g., an LWE ciphertext) and output the same to the operator <NUM>.

The operator <NUM> may generate a modified vector by preprocessing the operand ciphertext. The operator <NUM> may receive an LWE ciphertext <MAT> and perform a blind rotation operation. The operator <NUM> may calculate an operation result of a message with respect to a function f using <MAT>.

In operation <NUM>, the operator <NUM> may generate the modified vector by performing preprocessing based on the LWE ciphertext. The operator <NUM> may output the modified vector to the key generator <NUM>.

The key generator <NUM> may compare and analyze 2N based on each vector component αi of a vector α of the LWE ciphertext (β, α), a modulus q, and an order of an RLWE ciphertext.

The key generator <NUM> may verify a generator for generating a comparison and analysis result αi, generate a blind rotation key and a key-switching key necessary as a result of the verifying, and transmit the blind rotation key and the key-switching key to the operator <NUM>.

In operation <NUM>, the operator <NUM> may repeatedly perform a blind rotation operation based on the public key received from the key generator <NUM>. The operator <NUM> may perform an increment operation, an automorphism operation, and a key switching operation.

The operator <NUM> may divide components ωi of the modified vector ω into a first set and a second set that are disjoint. The first set may be <MAT>, and the second set may be <MAT>. The operator <NUM> may perform a blind rotation operation on the vector components in <MAT>, perform a blind rotation operation on the vector components corresponding to <MAT>, and then perform a blind rotation operation on the vector components corresponding to <MAT>. The operations may be performed in a different order according to examples. The process of a blind rotation operation will be described in detail with reference to <FIG>.

In operation <NUM>, the operator <NUM> may perform a final increment operation on a portion caused by a difference between the vector α and the modified vector ω. The operator <NUM> may output an RLWE ciphertext <MAT> as a final operation result.

<FIG> illustrates an example of a homomorphic encryption operation of a homomorphic encryption operation apparatus (e.g., the homomorphic encryption operation apparatus of <FIG>). Operations <NUM> through <NUM> of <FIG> may be performed sequentially but not necessarily performed sequentially. For example, the order of the operations <NUM> through <NUM> may change and two or more of the operations <NUM> through <NUM> may be performed in parallel or simultaneously. Further, one or more of operations <NUM> through <NUM> may be omitted, without departing from the scope of the shown example.

Referring to <FIG>, the example of <FIG> shows a process of a blind rotation operation when all vector components of a given LWE ciphertext are odd.

A key generator (e.g., the key generator <NUM> of <FIG>) may generate an input LWE ciphertext as (β, α). The key generator <NUM> may generate a blind rotation key RGSW(Xsi) which is an RGSW ciphertext corresponding to each secret key. The key generator <NUM> may generate automorphism keys akg and ak-g corresponding to g and -g. The key generator <NUM> may generate a key-switching key for changing s(X-g) to s(X). The key generator <NUM> may output the generated LWE ciphertext, the blind rotation key, the automorphism keys, and the key-switching key to an operator (e.g., the operator <NUM> of <FIG>).

In operation <NUM>, the operator <NUM> may set an initial value. The operator <NUM> may set the initial value in the form of a ring element.

The operator <NUM> may divide components ωi of a modified vector into <MAT> and <MAT>. In operation <NUM>, the operator <NUM> may set <MAT> to perform a blind rotation operation on vector components in <MAT>.

In operation <NUM>, the operator <NUM> may perform a loop of a blind rotation operation for i that satisfies <MAT>. In operation <NUM>, the operator <NUM> may perform an increment operation on RGSW. In operation <NUM>, the operator <NUM> may perform an automorphism operation on g, and perform a key switching operation for restoring the secret key to the original secret key.

The operator <NUM> may verify that operations <NUM> to <NUM> have been performed for all <MAT> , excluding j=<NUM>, through operations <NUM> and <NUM>.

In operation <NUM>, the operator <NUM> may perform the loop of the blind rotation operation for i that satisfies <MAT>. In operation <NUM>, the operator <NUM> may perform an increment operation for vector components of <MAT>. In operation <NUM>, the operator <NUM> may perform an automorphism operation on -g, and perform a key switching operation for restoring the secret key to the original secret key.

In operation <NUM>, the operator <NUM> may set <MAT>. In operation <NUM>, the operator <NUM> may perform the loop of the blind rotation operation for i that satisfies <MAT>. In operation <NUM>, the operator <NUM> may perform an increment operation for vector components of <MAT>. In operation <NUM>, the operator <NUM> may perform an automorphism operation on -g, and perform a key switching operation for restoring the secret key to the original secret key.

The operator <NUM> may verify that operations <NUM> to <NUM> have been performed for all <MAT>, excluding j'=<NUM>, through operations <NUM> and <NUM>. The operator <NUM> may perform an increment operation through operations <NUM> and <NUM> and output an RLWE ciphertext as a blind rotation operation result.

Using the example of <FIG>, when the vector component of the LWE ciphertext is odd regardless of the size of the vector components, a homomorphic encryption operation apparatus (e.g., the homomorphic encryption operation apparatus <NUM> of <FIG>) of one or more embodiments may improve homomorphic encryption technology by performing a homomorphic encryption operation by minimizing the number of automorphism keys and key-switching keys using automorphism during the blind rotation operation.

<FIG> illustrates an example of a homomorphic encryption operation of a homomorphic encryption operation apparatus (e.g., the homomorphic encryption operation apparatus of <FIG>). Operations <NUM> through <NUM> of <FIG> may be performed sequentially but not necessarily performed sequentially. For example, the order of the operations <NUM> through <NUM> may change and two or more of the operations <NUM> through <NUM> may be performed in parallel or simultaneously. Further, one or more of the operations <NUM> through <NUM> may be omitted, without departing from the scope of the shown example.

Referring to <FIG>, a process of a blind rotation operation when an LWE ciphertext (β, α) includes vector components that are even is shown.

A key generator (e.g., the key generator <NUM> of <FIG>) may generate an input LWE ciphertext as (β, α). The key generator <NUM> may generate a blind rotation key RGSW(Xsi) which is an RGSW ciphertext corresponding to each secret key. The key generator <NUM> may generate, as the blind rotation key, an RGSW ciphertext RGSW(X-Σsi) corresponding to the negative sum of vector components of the secret key.

The key generator <NUM> may generate automorphism keys akg and ak-g corresponding to g and -g. The key generator <NUM> may generate a key-switching key for changing s(X-g) to s(X). The key generator <NUM> may output the generated LWE ciphertext, the blind rotation key, the automorphism keys, and the key-switching key to an operator (e.g., the operator <NUM> of <FIG>).

In operation <NUM>, the operator <NUM> may set an initial value. The operator <NUM> may set the initial value in the form of a ring element. In operation <NUM>, the operator <NUM> may obtain and compare the number of odd numbers and the number of even numbers among vector components of an operand ciphertext.

When the number of even numbers is greater, the operator <NUM> may perform an increment operation using RGSW(X-Σsi), in operation <NUM>. In operation <NUM>, the operator <NUM> may change the LWE ciphertext (β, α) to(β, α + <NUM>).

When the number of odd numbers is greater, the operator <NUM> may maintain the LWE ciphertext in its original form, in operation <NUM>. In operation <NUM>, the operator <NUM> may set i=<NUM>. In operation <NUM>, starting from i=<NUM>, the operator <NUM> may verify whether vector components are even for i that satisfies i<n.

When the vector components are even, the operator <NUM> may generate a modified vector based on <MAT>, in operation <NUM>. When the vector components are odd, the operator <NUM> may generate a modified vector based on <MAT>, in operation <NUM>. In operation <NUM>, the operator <NUM> may increase i. In operation <NUM>, the operator <NUM> may determine if i<n. The operator <NUM> may generate a modified vector ω of which all vector components are odd, through operations <NUM> to <NUM>.

In operation <NUM>, the operator <NUM> may perform a blind rotation operation based on the modified vector ω and the secret key S. The process of performing the blind rotation operation may be the same as that of <FIG>.

When the vector components of the LWE operation are even, the operator <NUM> may additionally perform an increment operation of the RGSW ciphertext, through operations <NUM> to <NUM>. In operation <NUM>, the operator <NUM> may determine whether <MAT> is even. If even, the operator <NUM> may perform an increment operation of RGSW(Xsi), in operation <NUM>. In operation <NUM>, the operator <NUM> may increase i. In operation <NUM>, the operator <NUM> may determine if i<n. If <MAT> is odd, the operator <NUM> may perform operation <NUM>.

The operator <NUM> may output an RLWE ciphertext as a final operation result.

Using the example of <FIG>, when an even number is included in the vector components of the LWE ciphertext, the operator <NUM> of one or more embodiments may improve homomorphic encryption technology by efficiently using a storage space of a memory by adding only one blind rotation operation key. The operator <NUM> may perform an increment operation using the RGSW ciphertext <MAT> times at the maximum, thereby adjusting a trade-off relationship between the memory and the operation.

Referring to <FIG>, the example of <FIG> shows a process of a blind rotation operation when an even component is included in vector components of an LWE ciphertext.

A key generator (e.g., the key generator <NUM> of <FIG>) may generate an input LWE ciphertext as (β, α). The key generator <NUM> may generate a blind rotation key RGSW(Xsi) which is an RGSW ciphertext corresponding to each secret key. The key generator <NUM> may generate, as the blind rotation key, an RGSW ciphertext RGSW(X-Σsi) corresponding to the negative sum of vector components of the secret key. The key generator <NUM> may generate, as a blind rotation key, an RGSW ciphertext RGSW(Xsi+si+<NUM>) based on the sum of consecutive vector components.

In operation <NUM>, the operator <NUM> may set an initial value. The operator <NUM> may set the initial value in the form of a ring element. In operation <NUM>, the operator <NUM> may determine whether a first component of the vector components of the LWE ciphertext is even.

When the first component is even, the operator <NUM> may perform an increment operation using RGSW(X-Σsi), in operation <NUM>. In operation <NUM>, the operator <NUM> may change the LWE ciphertext (β, α) to (β, α + <NUM>). When the first component is odd, the operator <NUM> may maintain the LWE ciphertext in its original form, in operation <NUM>.

The operator <NUM> may perform operations <NUM> to <NUM> to change the vector components of the LWE ciphertext into values appropriate for an automorphism operation. In operation <NUM>, the operator <NUM> may start an operation from i=<NUM>.

In operation <NUM>, the operator <NUM> may determine whether the vector components <MAT> are odd. When odd, the operator <NUM> may set a secret key vector and a modified vector as <MAT> and <MAT>, respectively, in operation <NUM>.

When even, the operator <NUM> may set a secret key vector and a modified vector as <MAT> and <MAT>, respectively, in operation <NUM>.

In operation <NUM>, the operator <NUM> may increase i. In operation <NUM>, the operator <NUM> may determine if i<n-<NUM>. When the condition of operation <NUM> is not satisfied, the operator <NUM> may perform a blind rotation operation using the modified vector ω and a new secret key vector S'. The blind rotation operation may be performed in the same manner as described in <FIG>.

Using the example of <FIG>, when an even number is included in the vector components of the LWE ciphertext, the operator <NUM> may additionally perform an increment operation using the RGSW ciphertext only once, depending on whether the first vector component is odd. Accordingly, the operator <NUM> of one or more embodiments may improve homomorphic encryption technology by efficiently performing the homomorphic encryption operation by reducing the amount of computation. At this time, N+<NUM> additional blind rotation keys may be generated, and thus, a trade-off may occur between the memory and the amount of computation.

Referring to <FIG>, the example of <FIG> shows a case of <MAT> or a case where a generator for generating vector components of an LWE ciphertext is unique as g', when a blind rotation operation is performed. In this case, all vector components may have a remainder of "<NUM>" when divided by "<NUM>", may have a form of g'k, and may not have a form of a negative number.

A key generator (e.g., the key generator <NUM> of <FIG>) may generate an input LWE ciphertext as (β, α). The key generator <NUM> may generate a blind rotation key RGSW(Xsi) which is an RGSW ciphertext corresponding to each secret key. The key generator <NUM> may generate akg, and a key-switching key for changing s(Xg') to s(X). The key generator <NUM> may output the generated LWE ciphertext, the blind rotation key, the automorphism keys, and the key-switching key to an operator (e.g., the operator <NUM> of <FIG>).

In operation <NUM>, the operator <NUM> may set an initial value. The operator <NUM> may set the initial value in the form of a ring element. In operation <NUM>, the operator <NUM> may divide each vector component ωi by <MAT>, and set j=ord-<NUM> to start a blind rotation operation from the vector components in <MAT>. Ord may denote the smallest positive integer that satisfies g'ord = <NUM>.

In operation <NUM>, the operator <NUM> may perform a blind rotation operation for all components in <MAT>. In operation <NUM>, the operator <NUM> may perform an increment operation on RGSW. In operation <NUM>, the operator <NUM> may perform an automorphism operation on g', and perform a key switching operation for restoring the secret key to the original secret key.

The operator <NUM> may verify whether operations <NUM> to <NUM> have been performed for all <MAT>, excluding j=<NUM>, through operations <NUM> and <NUM>.

In operation <NUM>, the operator <NUM> may perform an increment operation for all vector components of <MAT> through operation <NUM>. The operator <NUM> may output an RLWE ciphertext as a blind rotation operation result.

A homomorphic encryption operation apparatus (e.g., the homomorphic encryption operation apparatus <NUM> of <FIG>) of one or more embodiments may apply the example of <FIG> according to the vector components of the LWE ciphertext or parameter values of homomorphic encryption, thereby improving homomorphic encryption technology by efficiently performing a homomorphic encryption operation using only one automorphism key.

As another example, when the operator <NUM> divides the vector components of the LWE ciphertext into <MAT> and <MAT>, both <MAT> and <MAT> may be empty sets for some j. In this case, the operator <NUM> of one or more embodiments may generate and use a plurality of automorphism keys for generators, thereby improving homomorphic encryption technology by reducing the number of times a blind rotation operation is unnecessarily performed. For example, the operator <NUM> may generate akg,. , akgb, and ak-g as automorphism keys. The example of generating a plurality of automorphism keys may apply to all of the examples of <FIG>.

<FIG> illustrates an example of a key generation operation of a homomorphic encryption operation apparatus (e.g., the homomorphic encryption operation apparatus of <FIG>). Operations <NUM> through <NUM> of <FIG> may be performed sequentially but not necessarily performed sequentially. For example, the order of the operations <NUM> through <NUM> may change and two or more of the operations <NUM> through <NUM> may be performed in parallel or simultaneously. Further, one or more of the operations <NUM> through <NUM> may be omitted, without departing from the scope of the shown example.

Referring to <FIG>, in a case of <MAT> or a case where a generator for generating vector components of an operand ciphertext (e.g., an LWE ciphertext) (β, α) is unique as g', a key generator (e.g., the key generator <NUM> of <FIG>) may generate RGSW(Xsi) an akg' based on the value of the generator g' for generating the vector components of the LWE ciphertext and generate a key-switching key for changing s(Xg') to s(X), to perform the blind rotation operation shown in the example of <FIG>.

In operation <NUM>, the key generator <NUM> may determine if <MAT> or whether the generator is unique as g'. When the condition of operation <NUM> is satisfied, the key generator <NUM> may generate RGSW(Xsi) and akg, and generate the key-switching key for changing s(Xg') to s(X), in operation <NUM>. In operation <NUM>, the key generator <NUM> may transmit the public keys generated in operation <NUM> to an operator (e.g., the operator <NUM> of <FIG>).

When the generator is not unique, the key generator <NUM> may determine whether an even number is included in the vector components, and generate the public key as in the example of <FIG>. Alternatively or additionally, the key generator <NUM> may determine the importance of memory efficiency and computational efficiency, generate a public key as in the examples of <FIG> and <FIG>, and transmit the public key to the operator <NUM>.

When the condition of operation <NUM> is not satisfied, the key generator <NUM> may determine whether α is odd, in operation <NUM>. When α is odd, the key generator <NUM> may generate RGSW(Xsi), akg, and ak-g, in operation <NUM>. In operation <NUM>, the key generator <NUM> may transmit the public keys generated in operation <NUM> to the operator <NUM>.

When α is even, the key generator <NUM> may select one having a higher importance between the memory efficiency and the computational efficiency, in operation <NUM>. When the importance of the memory efficiency is high, the key generator <NUM> may generate blind rotation keys RGSW(Xsí) and RGSW(X-Σsi), and generate automorphism keys akg and ak-g, in operation <NUM>. In operation <NUM>, the key generator <NUM> may transmit the public keys generated in operation <NUM> to the operator <NUM>.

When the importance of the computational efficiency is high, the key generator <NUM> may generate blind rotation keys RGSW(Xsi), RGSW(X-Σsi), and RGSW(Xsi+si+<NUM>), and generate automorphism keys akg and ak-g, in operation <NUM>. In operation <NUM>, the key generator <NUM> may transmit the public keys generated in operation <NUM> to the operator <NUM>.

<FIG> illustrates an example of an operation of a homomorphic encryption operation apparatus (e.g., the homomorphic encryption operation apparatus of <FIG>). Operations <NUM> through <NUM> of <FIG> may be performed sequentially but not necessarily performed sequentially. For example, the order of the operations <NUM> through <NUM> may change and two or more of the operations <NUM> through <NUM> may be performed in parallel or simultaneously. Further, one or more of the operations <NUM> through <NUM> may be omitted, without departing from the scope of the shown example.

Referring to <FIG>, in operation <NUM>, a receiver (e.g., the receiver <NUM> of <FIG>) may receive a public key for performing a blind rotation operation and an operand ciphertext of the blind rotation operation. The public key may include a blind rotation key, an automorphism key, and a key-switching key.

In operation <NUM>, the processor <NUM> may generate a modified vector by preprocessing vector components of the operand ciphertext based on an order of a polynomial of an output ciphertext of the blind rotation operation and a modulus of the operand ciphertext.

In operation <NUM>, the processor <NUM> may generate a homomorphic encryption operation result by performing the blind rotation operation based on the public key and the modified vector. The public key may be generated based on the modified vector and a secret key.

The homomorphic encryption operation apparatuses, receivers, processors, memories, key generators, receivers, operators, homomorphic encryption operation apparatus <NUM>, receiver <NUM>, processor <NUM>, memory <NUM>, key generator <NUM>, receiver <NUM>, operator <NUM>, and other apparatuses, devices, units, modules, and components disclosed and described herein with respect to <FIG> are implemented by or representative of hardware components. As described above, or in addition to the descriptions above, examples of hardware components that may be used to perform the operations described in this application where appropriate include controllers, sensors, generators, drivers, memories, comparators, arithmetic logic units, adders, subtractors, multipliers, dividers, integrators, and any other electronic components configured to perform the operations described in this application. In other examples, one or more of the hardware components that perform the operations described in this application are implemented by computing hardware, for example, by one or more processors or computers. A processor or computer may be implemented by one or more processing elements, such as an array of logic gates, a controller and an arithmetic logic unit, a digital signal processor, a microcomputer, a programmable logic controller, a field-programmable gate array, a programmable logic array, a microprocessor, or any other device or combination of devices that is configured to respond to and execute instructions in a defined manner to achieve a desired result. In one example, a processor or computer includes, or is connected to, one or more memories storing instructions or software that are executed by the processor or computer. Hardware components implemented by a processor or computer may execute instructions or software, such as an operating system (OS) and one or more software applications that run on the OS, to perform the operations described in this application. The hardware components may also access, manipulate, process, create, and store data in response to execution of the instructions or software. For simplicity, the singular term "processor" or "computer" may be used in the description of the examples described in this application, but in other examples multiple processors or computers may be used, or a processor or computer may include multiple processing elements, or multiple types of processing elements, or both. For example, a single hardware component or two or more hardware components may be implemented by a single processor, or two or more processors, or a processor and a controller. One or more hardware components may be implemented by one or more processors, or a processor and a controller, and one or more other hardware components may be implemented by one or more other processors, or another processor and another controller. One or more processors, or a processor and a controller, may implement a single hardware component, or two or more hardware components. As described above, or in addition to the descriptions above, example hardware components may have any one or more of different processing configurations, examples of which include a single processor, independent processors, parallel processors, single-instruction single-data (SISD) multiprocessing, single-instruction multiple-data (SIMD) multiprocessing, multiple-instruction single-data (MISD) multiprocessing, and multiple-instruction multiple-data (MIMD) multiprocessing.

The instructions or software to control computing hardware, for example, one or more processors or computers, to implement the hardware components and perform the methods as described above, and any associated data, data files, and data structures, may be recorded, stored, or fixed in or on one or more non-transitory computer-readable storage media, and thus, not a signal per se. As described above, or in addition to the descriptions above, examples of a non-transitory computer-readable storage medium include one or more of any of read-only memory (ROM), random-access programmable read only memory (PROM), electrically erasable programmable read-only memory (EEPROM), random-access memory (RAM), dynamic random access memory (DRAM), static random access memory (SRAM), flash memory, non-volatile memory, CD-ROMs, CD-Rs, CD+Rs, CD-RWs, CD+RWs, DVD-ROMs, DVD- Rs, DVD+Rs, DVD-RWs, DVD+RWs, DVD-RAMs, BD-ROMs, BD-Rs, BD-R LTHs, BD-REs, blue-ray or optical disk storage, hard disk drive (HDD), solid state drive (SSD), flash memory, a card type memory such as multimedia card micro or a card (for example, secure digital (SD) or extreme digital (XD)), magnetic tapes, floppy disks, magneto-optical data storage devices, optical data storage devices, hard disks, solid-state disks, and any other device that is configured to store the instructions or software and any associated data, data files, and data structures in a non-transitory manner and provide the instructions or software and any associated data, data files, and data structures to one or more processors or computers so that the one or more processors or computers can execute the instructions.

While this disclosure includes specific examples, it will be apparent after an understanding of the disclosure of this application that various changes in form and details may be made in these examples without departing from the scope of the claims. The examples described herein are to be considered in a descriptive sense only, and not for purposes of limitation. Descriptions of features or aspects in each example are to be considered as being applicable to similar features or aspects in other examples. Suitable results may be achieved if the described techniques are performed in a different order, and/or if components in a described system, architecture, device, or circuit are combined in a different manner, and/or replaced or supplemented by other components or their equivalents.

Claim 1:
An apparatus with a homomorphic encryption operation, the apparatus comprising:
one or more processors configured to:
generate a modified vector by preprocessing vector components of an operand ciphertext of a blind rotation operation based on an order of a polynomial of an output ciphertext of the blind rotation operation and a modulus of the operand ciphertext; and
generate a homomorphic encryption operation result by performing the blind rotation operation based on a public key for performing the blind rotation operation and the modified vector.