Patent ID: 12212670

DESCRIPTION OF THE PREFERRED EMBODIMENTS

The present invention will be described in detail below with reference to the accompanying drawings. Repeated descriptions and descriptions of known functions and configurations which have been deemed to make the gist of the present invention unnecessarily obscure will be omitted below. The embodiments of the present invention are intended to fully describe the present invention to a person having ordinary knowledge in the art to which the present invention pertains. Accordingly, the shapes, sizes, etc. of components in the drawings may be exaggerated to make the description clearer.

In the present specification, it should be understood that terms such as “include” or “have” are merely intended to indicate that features, numbers, steps, operations, components, parts, or combinations thereof are present, and are not intended to exclude the possibility that one or more other features, numbers, steps, operations, components, parts, or combinations thereof will be present or added.

Hereinafter, preferred embodiments of the present invention will be described in detail with the attached drawings.

FIG.1is a block diagram illustrating an apparatus for calculating a multiplicative inverse according to an embodiment of the present invention.FIG.2is a circuit diagram illustrating in detail an example of the multiplicative inverse calculation unit illustrated inFIG.1.FIG.3is a circuit diagram illustrating an example of the degree-4 multiplication inverse calculation unit illustrated inFIG.2.FIG.4is a circuit diagram illustrating in detail an example of the degree-4 multiplication unit illustrated inFIG.2.

The apparatus for calculating a multiplicative inverse according to the embodiment of the present invention may provide finite fields and a field towering technique for efficiently operating in a quantum computer environment.

The apparatus for calculating a multiplicative inverse according to the embodiment of the present invention may include a quantum circuit designed in consideration of a circuit depth and qubit consumption required for a multiplicative inverse calculation that is to be performed in a quantum computer environment.

The apparatus for calculating a multiplicative inverse according to the embodiment of the present invention may include various choices for time (T-depth) and space (number of qubits) complexity through a trade-off relationship between T-depth and the number of qubits during a process for performing a multiplicative inverse calculation in a quantum computer environment.

Referring toFIG.1, the apparatus for calculating a multiplicative inverse according to the embodiment of the present invention includes a data input unit110, a multiplicative inverse calculation unit120, and a data output unit130.

The data input unit110may receive input data required in order to perform Advanced Encryption Standard (AES) encryption.

The multiplicative inverse calculation unit120may divide an input degree-8 finite field (Galois Field) GF(28) corresponding to the input data into two first degree-4 finite fields GF(24) in order to perform AES encryption on the input data, and may perform a multiplicative inverse calculation on the first degree-4 finite fields GF(24) in consideration of the circuit depth value (T-depth) and qubit consumption of quantum gates in a quantum circuit.

Here, the multiplicative inverse calculation unit120may correspond to the Substitution Box (S-Box) calculator of AES.

The data output unit130may output result data obtained by performing the multiplicative inverse calculation.

Referring toFIG.2, it can be seen that a circuit diagram of a quantum circuit in which the multiplicative inverse calculation unit is implemented using a field towering technique is illustrated. That is, it can be seen that the circuit diagram illustrated inFIG.2shows a multiplicative inverse calculation circuit according to an embodiment of the present invention.

Here, the multiplicative inverse calculation unit may include a degree-4 multiplicative inverse calculation (x−1) unit121, a first degree-4 multiplication (L×) unit122, a second degree-4 multiplication (L×) unit123, and a third degree-4 multiplication (LX) unit124. λ may be set differently depending on a field towering structure.

Here, finite fields used for AES encryption operations, that is, degree-8, degree-4, and degree-2 finite fields, may be represented by the following Equation (1):

GF⁡(28),m⁡(x)=x8+x4+x3+x+1⁢map≈⁢GF⁡((24)2),y2+y+λ⁢⁢GF⁡(24),m4⁡(x)=x4+x+1⁢map4≈⁢GF⁡((22)2),z2+z+ϕ⁢⁢GF⁡(22),n2⁡(x)=x2+x+1(1)

Here,ωmay be the root of m4(x), and ϕ may be the root of n2(x), where ϕ={10}2. Also, λ may be represented by λ:=ω11=ω3+ω2+ω={1110}2.

In this case, the multiplicative inverse calculation unit120may perform mapping and an inverse operation of mapping between different finite fields having an isomorphic relationship therebetween in order to calculate a multiplicative inverse.

Here, the multiplicative inverse calculation unit120may perform mapping and an inverse operation of mapping (map−1, map4−1) by applying mapping matrices (map, map4) of Equation (2) to formulas corresponding to the finite fields in Equation (1).

map=[1010000010101100110100100111000000010100100000100000011001110001],⁢map-1=[1011010010011110001101001011101001110010101100101011000000010001]⁢⁢map4=[1000111011000001],⁢map4-1=[1000101001100001](2)

Here, the multiplicative inverse calculation unit120may output the output data corresponding to the input data in accordance with the multiplicative inversion calculator of a Substitution Box (S-Box) in AES encryption.

The multiplicative inverse calculation (multiplicative inversion) unit120may include a first degree-4 multiplication unit122for performing multiplication on the first degree-4 finite fields using three degree-2 multipliers that are configured in consideration of the circuit depth value (T-depth) and qubit consumption of quantum gates, thus obtaining a second degree-4 finite field.

The multiplicative inverse calculation unit120may further include a degree-4 multiplicative inverse calculation unit121which is electrically connected to the first degree-4 multiplication unit122and performs multiplication on two second degree-2 finite fields, divided from the second degree-4 finite field, using the three degree-2 multipliers, thus calculating the multiplicative inverse of the second degree-2 finite fields.

The multiplicative inverse calculation unit120may further include a second degree-4 multiplication unit123which is electrically connected to the degree-4 multiplicative inverse calculation unit121and performs multiplication on any one of the first degree-4 finite fields and the multiplicative inverse of the second degree-2 finite fields using the three degree-2 multipliers, thus obtaining a third degree-4 finite field.

Here, the multiplicative inverse calculation unit120may further include a third degree-4 multiplication unit124, which is electrically connected to the degree-4 multiplicative inverse calculation unit121and performs multiplication on the remaining one of the first degree-4 finite fields and the multiplicative inverse of the second degree-2 finite fields using the three degree-2 multipliers, thus obtaining a fourth degree-4 finite field.

Here, the multiplicative inverse calculation unit120may further include a finite field division unit for dividing the input degree-8 finite field GF(28) into two degree-4 finite fields GF(24), and an affine transform unit for combining the third degree-4 finite field and the fourth degree-4 finite field, which are the output two degree-4 finite fields GF(24), and for outputting an affine-transformed output degree-8 finite field GF(28).

Referring toFIG.3, it can be seen that an example of the degree-4 multiplicative inverse calculation unit121is depicted in a detailed circuit diagram.

Here, the relationship between the input and the output of a multiplicative inverse in a degree-4 finite field GF(24) may be represented by the following Equation (3):
d−1=ph(ϕ+1)+pl+ph2pl2
qh=phd−1,ql=(ph+pl)d−1(3)

Here, it can be seen that ph, pl, qhand qlrespectively correspond to degree-2 finite fields corresponding to 2 bits, and that blocks marked with “x” denote degree-2 multipliers which perform multiplication on degree-2 finite fields GF(22).

The degree-4 multiplicative inverse calculation unit121may include three degree-2 multipliers, and Ψ in the circuit diagram may differ depending on the field towering structure.

The degree-4 multiplicative inverse calculation unit121may perform multiplications on the two second degree-2 finite fields GF(22) (ph, pl) divided from the second degree-4 finite field using the three degree-2 multipliers thus calculating the multiplicative inverse (qh, ql) of the second degree-2 finite fields.

Referring toFIG.4, an example of each degree-4 multiplication unit is depicted in a detailed circuit diagram.

Here, the first degree-4 multiplication unit122, the second degree-4 multiplication unit123, and the third degree-4 multiplication unit124may have the same circuit diagram structure, as illustrated inFIG.4.

It can be seen that each block marked with “x” denotes a degree-2 multiplier which performs multiplication on degree-2 finite fields GF(22).

It can be seen that a block marked with “x†” denotes a degree-2 multiplication dagger operator which performs a dagger operation on the result of performing the multiplication on the degree-2 finite fields GF(22).

A dagger operation may be an operation of restoring a state before the operation is performed so as to reuse qubits or the like.

Here, “†” indicating a dagger operation may correspond to a Hermitian operator.

Here, the three degree-2 multipliers may cause a circuit depth (T-depth) during multiplication on the degree-2 finite fields GF(22), and at least two of the three degree-2 multipliers may perform operations in parallel.

A circuit for calculating the multiplication inverse of the degree-2 finite fields GF(22) may be implemented in various forms because there is a trade-off relationship between time (T-depth) complexity and space (qubit consumption) complexity in a quantum computer environment.

FIGS.5to9are circuit diagrams illustrating gate configurations according to an embodiment of the present invention.

Here, in the three degree-2 multipliers, the number, type, and arrangement of quantum gates included in each degree-2 multiplier may be determined based on the circuit depth value (T-depth) and qubit consumption of the quantum gates.

Here, each degree-2 multiplier may include at least one of a Toffoli gate and an AND gate.

Referring toFIG.5, a circuit diagram of a xT3degree-2 multiplier is illustrated.

The xT3degree-2 multiplier may include three Toffoli gates.

In this case, the xT3degree-2 multiplier may correspond to a T-depth of 9 and a qubit consumption of 6.

Referring toFIG.6, a circuit diagram of a xA2degree-2 multiplier is illustrated.

The xA2degree-2 multiplier may include two AND gates and one Toffoli gate.

Here, the xA2degree-2 multiplier may correspond to a T-depth of 5 and a qubit consumption of 7.

Further, when the circuit depth value (T-depth) of the quantum gate is less than or equal to a preset value, the degree-2 multiplier may include at least one dagger operation AND gate (AND†gate).

Here, when the degree-2 multiplier includes at least one dagger operation AND gate (AND†gate), it may be represented by a x†degree-2 multiplication dagger operator.

A dagger operation may be performed as an operation of restoring a state before an operation is performed so as to reuse qubits or the like.

Here, “†”, indicating a dagger operation, may correspond to a Hermitian operator.

Further, when the degree-2 multiplier includes an AND gate and a dagger operation AND gate, it may further include at least two AND gates or at least two dagger operation AND gates.

Referring toFIG.7, a circuit diagram of a xA3degree-2 multiplier is illustrated.

The xA3degree-2 multiplier may include three AND gates and one dagger operation AND gate (AND†gate).

Here, the xA3degree-2 multiplier may correspond to a T-depth of 3 and a qubit consumption of 8.

Referring toFIG.8, a circuit diagram of a xA3†degree-2 multiplication dagger operator is illustrated.

The xA3†degree-2 multiplication dagger operator may include one AND gate and three dagger operation AND gates (AND†gates).

Here, the xA3†degree-2 multiplication dagger operator may correspond to a T-depth of 1 and a qubit consumption of 8.

Referring toFIG.9, a circuit diagram of a xA2†degree-2 multiplication dagger operator is illustrated.

The xA2†degree-2 multiplication dagger operator may include one Toffoli gate and two dagger operation AND gates (AND†gates).

Here, the xA2†degree-2 multiplication dagger operator may correspond to a T-depth of 3 and a qubit consumption of 6.

InFIGS.5to9, the mark ⊚ indicates spare qubits for the AND operation of an AND gate.

FIGS.10to13are circuit diagrams illustrating the arrangement of three degree-2 multipliers and a degree-2 multiplication dagger operator which are illustrated inFIG.4.

The three degree-2 multipliers and the degree-2 multiplication dagger operator may be arranged in a circuit in consideration of a preset circuit depth value and qubit consumption.

Here, at least two of the three degree-2 multipliers may perform operations in parallel.

The implementation of quantum circuits for the degree-4 multiplication units122,123, and124which perform multiplications on a degree-4 finite field GF(24) in a quantum computer environment may have different circuit depth values (T-depth) and qubit consumptions depending on a scheme for arranging three degree-2 multipliers, which perform multiplications on degree-2 finite fields GF(22), in parallel or in series and additionally depending on which type of quantum circuit corresponding to each operation is to be used.

Here, the quantum circuits for the degree-4 multiplication units122,123, and124according to an embodiment of the present invention may receive, as input, ph, pl, qhand ql, and may provide, as output, ph, pl, qhand qland rhand rl(upper 2 bits and lower 2 bits of respective multiplication results).

Each degree-4 multiplication unit may restore an intermediate value other than intended output to a state |0> in a calculation process, and may additionally perform a dagger (xA3†) operation so as to perform multiplication on degree-2 finite fields GF(22).

Here, it can be seen that, in each degree-4 multiplication unit, the influence of the remaining operators other than degree-2 multipliers, which perform multiplication on degree-2 finite fields GF(22), and the degree-2 multiplication dagger operator, which performs a dagger operation, on T-depth and qubit consumption is insignificant, and thus representation of the remaining operators in a circuit diagram is omitted.

Referring toFIG.10, in the degree-4 multiplication unit illustrated inFIG.4, three xT3degree-2 multipliers may perform operations in parallel, and a xA3†degree-2 multiplication dagger operator may perform an operation in series to the operations of the three xT3degree-2 multipliers.

Here, it can be seen that the total qubit consumption is 18, the T-depth of the xT3degree-2 multipliers is 9, and the T-depth of the xA3†degree-2 multiplication dagger operator is 1.

Referring toFIG.11, in the degree-4 multiplication unit illustrated inFIG.4, two xA3degree-2 multipliers may perform operations in parallel, after which one xA3degree-2 multiplier performs an operation and a xA3†degree-2 multiplication dagger operator performs an operation in series to the operations of the xA3degree-2 multipliers.

Here, it can be seen that the total qubit consumption is 20, the T-depth of the two xA3degree-2 multipliers which perform operations in parallel is 3, the T-depth of one xA3degree-2 multiplier is 3, and the T-depth of the xA3†degree-2 multiplication dagger operator is 1.

Referring toFIG.12, in the degree-4 multiplication unit illustrated inFIG.4, three xA2degree-2 multipliers may perform operations in parallel, and a xA3†degree-2 multiplication dagger operator may perform an operation in series to the three xA2degree-2 multipliers.

In this case, it can be seen that the total qubit consumption is 21, the T-depth of xA2degree-2 multipliers is 5, and the T-depth of the xA3†degree-2 multiplication dagger operator is 1.

Referring toFIG.13, in the degree-4 multiplication unit illustrated inFIG.4, three xA3degree-2 multipliers may perform operations in parallel, and a xA3†degree-2 multiplication dagger operator may perform an operation in series to the xA3degree-2 multipliers.

Here, it can be seen that the total qubit consumption is 24, the T-depth of the xA3degree-2 multipliers is 3, and the T-depth of the xA3†degree-2 multiplication dagger1ooperator is 1.

FIG.14is an operation flowchart illustrating a method for calculating a multiplicative inverse according to an embodiment of the present invention.

Referring toFIG.14, the multiplicative inverse calculation method according to the embodiment of the present invention may receive data at step S210.

That is, at step S210, input data may be received.

Also, the multiplicative inverse calculation method according to the embodiment of the present invention may perform a multiplicative inverse calculation at step S220.

That is, at step S220, an input degree-8 finite field corresponding to the input data may be divided into two first degree-4 finite fields so as to perform Advanced Encryption Standard (AES) encryption on the input data, and the multiplicative inverse calculation may be performed on the first degree-4 finite fields in consideration of the circuit depth value (T-Depth) and qubit consumption of quantum gates in quantum circuits.

At step S220, multiplication may be performed on the first degree-4 finite fields using three degree-2 multipliers that are configured in consideration of the circuit depth value (T-depth) and qubit consumption of the quantum gates, thus obtaining a second degree-4 finite field.

Here, at step S220, multiplication may be performed on two second degree-2 finite fields, divided from the second degree-4 finite field, using the three degree-2 multipliers, and thus multiplicative inverse of the second degree-2 finite fields may be calculated.

In this case, at step S220, multiplication may be performed on any one of the first degree-4 finite fields and the multiplicative inverse of the second degree-2 finite fields using the three degree-2 multipliers, thus obtaining a third degree-4 finite field.

Here, at step S220, multiplication may be performed on the remaining one of the first degree-4 finite fields and the multiplicative inverse of the second degree-2 finite fields using the three degree-2 multipliers, thus obtaining a fourth degree-4 finite field.

Here, at step S220, an affine-transformed output degree-8 finite field may be output by combining the third degree-4 finite field with the fourth degree-4 finite field.

The number, type, and arrangement of quantum gates included in each of the three degree-2 multipliers may be determined based on the circuit depth value (T-depth) and qubit consumption of the quantum gates.

Here, each degree-2 multiplier may include at least one of a Toffoli gate and an AND gate.

When the circuit depth value (T-depth) of each quantum gate is less than or equal to a preset value, the degree-2 multiplier may include at least one dagger operation AND gate.

Here, when each degree-2 multiplier includes an AND gate and a dagger operation AND gate, it may further include at least two AND gates or at least two dagger operation AND gates.

Here, among the three degree-2 multipliers, at least two degree-2 multipliers may perform operations in parallel in consideration of the preset circuit depth value and the qubit consumption.

Further, the multiplicative inverse calculation method according to the embodiment of the present invention may output data at step S230.

That is, at step S230, an output degree-8 finite field, which is result data obtained by performing the multiplicative inverse calculation, may be output.

FIG.15is a diagram illustrating a computer system according to an embodiment of the present invention.

Referring toFIG.15, apparatus for calculating multiplicative inverse according to an embodiment of the present invention may be implemented in a computer system1100, such as a computer-readable storage medium. As illustrated inFIG.13, the computer system1100may include one or more processors1110, memory1130, a user interface input device1140, a user interface output device1150, and storage1160, which communicate with each other through a bus1120. The computer system1100may further include a network interface1170connected to a network1180. Each processor1110may be a Central Processing Unit (CPU) or a semiconductor device for executing processing instructions stored in the memory1130or the storage1160. Each of the memory1130and the storage1160may be any of various types of volatile or nonvolatile storage media. For example, the memory1130may include Read-Only Memory (ROM)1131or Random Access Memory (RAM)1132.

Therefore, the apparatus and method for calculating a multiplicative inverse according to embodiments of the present invention may adjust time (T-depth) complexity and space (qubit) complexity of the multiplicative inverse calculation (multiplicative inversion) which occupies the greatest proportion of costs (based on T-depth) in an AES S-Box quantum circuit, by means of a trade-off between time complexity and space complexity.

That is, the apparatus and method for calculating a multiplicative inverse according to embodiments of the present invention may provide a quantum circuit configuration that is capable of selecting T-depth and qubit consumption through a trade-off relationship therebetween depending on the circumstances, unlike existing quantum circuits, and may greatly decrease T-depth or qubit consumption through a slight increase in the consumption of other resources depending on the selection.

The present invention may calculate a multiplicative inverse of an AES S-Box in a quantum computer environment while minimizing time and space complexity.

The present invention may provide a field towering technique through an optimized combination of efficient finite fields and operators required to minimize time and space complexity.

As described above, in the apparatus and method for calculating a multiplicative inverse according to the present invention, the configurations and schemes in the above-described embodiments are not limitedly applied, and some or all of the above embodiments can be selectively combined and configured such that various modifications are possible.