INVERSE ELEMENT OPERATION APPARATUS AND COMPUTER READABLE MEDIUM

Abstract

An acceptance unit (110) accepts an element a. A preliminary operation unit (120) calculates t.sub.1 that is a computation result of a.sub.0.sup.2, t.sub.2 that is a computation result of a.sub.2.sup.2, t.sub.3 that is a computation result of a.sub.0a.sub.1, t.sub.4 that is a computation result of a.sub.1a.sub.2, and t.sub.7 that is equal to a computation result of (a.sub.0+a.sub.1)(a.sub.1−a.sub.2), using a.sub.0, a.sub.1, and a.sub.2. An inverse element operation unit (130) calculates b.sub.0 that is equal to a computation result of a.sub.0.sup.2−a.sub.1a.sub.2v, b.sub.1 that is equal to a computation result of a.sub.2.sup.2v−a.sub.0a.sub.1, and b.sub.2 that is equal to a computation result of a.sub.1.sup.2−a.sub.0a.sub.2, using t.sub.1, t.sub.2, t.sub.3, t.sub.4, and t.sub.7. An output unit (140) generates and outputs an inverse element a.sup.−1, using b.sub.0, b.sub.1, and b.sub.2.

Claims

1. An inverse element operation apparatus to calculate an inverse element a.sup.−1 of an element a, the element a being expressed by a=a.sub.0+a.sub.1w+a.sub.2w.sup.2, the inverse element a.sup.−1 being expressed by a.sup.−1=(a.sub.0.sup.2−a.sub.1a.sub.2v)+(a.sub.2.sup.2v−a.sub.0a.sub.1)w+(a.sub.1.sup.2−a.sub.0a.sub.2)w.sup.2, the inverse element operation apparatus comprising processing circuitry to: accept the element a; calculate t.sub.1 that is a computation result of a.sub.0.sup.2, t.sub.2 that is a computation result of a.sub.2.sup.2, t.sub.3 that is a computation result of a.sub.0a.sub.1, t.sub.4 that is a computation result of a.sub.1a.sub.2, and t.sub.7 that is equal to a computation result of (a.sub.0+a.sub.1)(a.sub.1−a.sub.2), using a.sub.0, a.sub.1, and a.sub.2; calculate b.sub.0 that is equal to a computation result of a.sub.0.sup.2−a.sub.1a.sub.2v, b.sub.1 that is equal to a computation result of a.sub.2.sup.2v−a.sub.0a.sub.1, and b.sub.2 that is equal to a computation result of a.sub.1.sup.2−a.sub.0a.sub.2, using t.sub.1, t.sub.2, t.sub.3, t.sub.4, and t.sub.7; and generate and output the inverse element a.sup.−1, using b.sub.0, b.sub.1, and b.sub.2.

2. The inverse element operation apparatus according to claim 1, wherein the processing circuitry performs a squaring using a.sub.0 to calculate t.sub.1 that is the computation result of a.sub.0.sup.2, performs a squaring using a.sub.2 to calculate t.sub.2 that is the computation result of a.sub.2.sup.2, performs a multiplication using a.sub.0 and a.sub.1 to calculate t.sub.3 that is the computation result of a.sub.0a.sub.1, performs a multiplication using a.sub.1 and a.sub.2 to calculate t.sub.4 that is the computation result of a.sub.1a.sub.2, performs an addition using a.sub.0 and a.sub.1 to calculate t.sub.5 that is a computation result of a.sub.0+a.sub.1, performs a subtraction using a.sub.1 and a.sub.2 to calculate t.sub.6 that is a computation result of a.sub.1−a.sub.2, and performs a multiplication using t.sub.5 and t.sub.6 to calculate t.sub.7 that is equal to the computation result of (a.sub.0+a.sub.1)(a.sub.1−a.sub.2).

3. The inverse element operation apparatus according to claim 2, wherein the processing circuitry calculates t.sub.7 by computing t.sub.5t.sub.6.

4. The inverse element operation apparatus according to claim 1, wherein the processing circuitry performs a subtraction using t.sub.1 and t.sub.4 to calculate b.sub.0 that is equal to the computation result of a.sub.0.sup.2−a.sub.1a.sub.2v, performs a subtraction using t.sub.2 and t.sub.3 to calculate b.sub.1 that is equal to the computation result of a.sub.2.sup.2v−a.sub.0a.sub.1, and performs an addition and a subtraction using t.sub.3, t.sub.4, and t.sub.7 to calculate b.sub.2 that is equal to the computation result of a.sub.1.sup.2−a.sub.0a.sub.2.

5. The inverse element operation apparatus according to claim 4, wherein the processing circuitry calculates b.sub.0 by computing t.sub.1−t.sub.4v, calculates b.sub.1 by computing t.sub.2v−t.sub.3, and calculates b.sub.2 by computing t.sub.7−t.sub.3+t.sub.4.

6. A non-transitory computer readable medium storing an inverse element operation program to calculate an inverse element a.sup.−1 of an element a, the element a being expressed by a=a.sub.0+a.sub.1w+a.sub.2w.sup.2, the inverse element a.sup.−1 being expressed by a.sup.−1=(a.sub.0.sup.2−a.sub.1a.sub.2v)+(a.sub.2.sup.2v−a.sub.0a.sub.1)w+(a.sub.1.sup.2−a.sub.0a.sub.2)w.sup.2, the inverse element operation program causing a computer to execute: an acceptance process of accepting the element a; a preliminary operation process of calculating t.sub.1 that is a computation result of a.sub.0.sup.2, t.sub.2 that is a computation result of a.sub.2.sup.2, t.sub.3 that is a computation result of a.sub.0a.sub.1, t.sub.4 that is a computation result of a.sub.1a.sub.2, and t.sub.7 that is equal to a computation result of (a.sub.0+a.sub.1)(a.sub.1−a.sub.2), using a.sub.0, a.sub.1, and a.sub.2; an inverse element operation process of calculating b.sub.0 that is equal to a computation result of a.sub.0.sup.2−a.sub.1a.sub.2v, b.sub.1 that is equal to a computation result of a.sub.2.sup.2v−a.sub.0a.sub.1, and b.sub.2 that is equal to a computation result of a.sub.1.sup.2−a.sub.0a.sub.2, using t.sub.1, t.sub.2, t.sub.3, t.sub.4, and t.sub.7; and an output process of generating and outputting the inverse element a.sup.−1, using b.sub.0, b.sub.1, and b.sub.2.

7. An inverse element operation apparatus to calculate an inverse element a.sup.−1 of an element a, the element a being expressed by a=a.sub.0+a.sub.1w+a.sub.2w.sup.2, the inverse element a.sup.−1 being expressed by a.sup.−1=(a.sub.0.sup.2−a.sub.1a.sub.2v)+(a.sub.2.sup.2v−a.sub.0a.sub.1)w+(a.sub.1.sup.2−a.sub.0a.sub.2)w.sup.2, the inverse element operation apparatus comprising processing circuitry to: accept the element a; calculate t.sub.1 that is a computation result of a.sub.0.sup.2, t.sub.2 that is a computation result of a.sub.2.sup.2, t.sub.3 that is a computation result of a.sub.0a.sub.1, t.sub.4 that is a computation result of a.sub.1a.sub.2, t.sub.7 that is equal to a computation result of a.sub.0.sup.2+a.sub.1.sup.2+a.sub.2.sup.2/4+2a.sub.0a.sub.1−a.sub.0a.sub.2−a.sub.1a.sub.2, and Is that is equal to a computation result of a.sub.2.sup.2/4, using a.sub.0, a.sub.1, and a.sub.2; calculate b.sub.0 that is equal to a computation result of a.sub.0.sup.2−a.sub.1a.sub.2v, b.sub.1 that is equal to a computation result of a.sub.2.sup.2v−a.sub.0a.sub.1, and b.sub.2 that is equal to a computation result of a.sub.1.sup.2−a.sub.0a.sub.2, using t.sub.1, t.sub.2, t.sub.3, t.sub.4, t.sub.7, and t.sub.8; and generate and output the inverse element a.sup.−1, using b.sub.0, b.sub.1, and b.sub.2.

8. The inverse element operation apparatus according to claim 7, wherein the processing circuitry performs a squaring using a.sub.0 to calculate t.sub.1 that is the computation result of a.sub.0.sup.2, performs a squaring using a.sub.2 to calculate t.sub.2 that is the computation result of a.sub.2.sup.2, performs a multiplication using a.sub.0 and a.sub.1 to calculate t.sub.3 that is the computation result of a.sub.0a.sub.1, performs a multiplication using a.sub.1 and a.sub.2 to calculate t.sub.4 that is the computation result of a.sub.1a.sub.2, performs a ½ multiplication using a.sub.2 to calculate t.sub.5 that is a computation result of a.sub.2/2, performs an addition and a subtraction using a.sub.0, a.sub.1, and t.sub.5 to calculate t.sub.6 that is equal to a computation result of a.sub.0+a.sub.1−a.sub.2/2, performs a squaring using t.sub.6 to calculate t.sub.7 that is equal to the computation result of a.sub.0.sup.2+a.sub.1.sup.2+a.sub.2.sup.2/4+2a.sub.0a.sub.1−a.sub.0a.sub.2−a.sub.1a.sub.2, and performs a ¼ multiplication using t.sub.2 to calculate t.sub.8 that is equal to the computation result of a.sub.2.sup.2/4.

9. The inverse element operation apparatus according to claim 8, wherein the processing circuitry calculates t.sub.6 by computing a.sub.0+a.sub.1−t.sub.5, calculates t.sub.7 by computing t.sub.6.sup.2, and calculates t.sub.8 by computing t.sub.2/4.

10. The inverse element operation apparatus according to claim 7, wherein the processing circuitry performs a subtraction using t.sub.1 and t.sub.4 to calculate b.sub.0 that is equal to the computation result of a.sub.0.sup.2−a.sub.1a.sub.2v, performs a subtraction using t.sub.2 and t.sub.3 to calculate b.sub.1 that is equal to the computation result of a.sub.2.sup.2v−a.sub.0a.sub.1, and performs an addition and a subtraction using t.sub.1, t.sub.3, t.sub.4, t.sub.7, and t.sub.8 to calculate b.sub.2 that is equal to the computation result of a.sub.1.sup.2−a.sub.0a.sub.2.

11. The inverse element operation apparatus according to claim 10, wherein the processing circuitry calculates b.sub.0 by computing t.sub.1−t.sub.4v, calculates b.sub.1 by computing t.sub.2v−t.sub.3, and calculates b.sub.2 by computing t.sub.7−t.sub.1−t.sub.8−2t.sub.3−t.sub.4.

12. A non-transitory computer readable medium storing an inverse element operation program to calculate an inverse element a.sup.−1 of an element a, the element a being expressed by a=a.sub.0+a.sub.1w+a.sub.2w.sup.2, the inverse element a.sup.−1 being expressed by a.sup.−1=(a.sub.0.sup.2−a.sub.1a.sub.2v)+(a.sub.2.sup.2v−a.sub.0a.sub.1)w+(a.sub.1.sup.2−a.sub.0a.sub.2)w.sup.2, the inverse element operation program causing a computer to execute: an acceptance process of accepting the element a; a preliminary operation process of calculating t.sub.1 that is a computation result of a.sub.0.sup.2, t.sub.2 that is a computation result of a.sub.2.sup.2, t.sub.3 that is a computation result of a.sub.0a.sub.1, t.sub.4 that is a computation result of a.sub.1a.sub.2, t.sub.7 that is equal to a computation result of a.sub.0.sup.2+a.sub.1.sup.2+a.sub.2.sup.2/4+2a.sub.0a.sub.1−a.sub.0a.sub.2−a.sub.1a.sub.2, and t.sub.8 that is equal to a computation result of a.sub.2.sup.2/4, using a.sub.0, a.sub.1, and a.sub.2; an inverse element operation process of calculating b.sub.0 that is equal to a computation result of a.sub.0.sup.2−a.sub.1a.sub.2v, b.sub.1 that is equal to a computation result of a.sub.2.sup.2v−a.sub.0a.sub.1, and b.sub.2 that is equal to a computation result of a.sub.1.sup.2−a.sub.0a.sub.2, using t.sub.1, t.sub.2, t.sub.3, t.sub.4, t.sub.7, and t.sub.8; and an output process of generating and outputting the inverse element a.sup.−1, using b.sub.0, b.sub.1, and b.sub.2.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0036] FIG. 1 is a configuration diagram of an inverse element operation apparatus 100 in a first embodiment;

[0037] FIG. 2 is a configuration diagram of a preliminary operation unit 120 in the first embodiment;

[0038] FIG. 3 is a configuration diagram of an inverse element operation unit 130 in the first embodiment;

[0039] FIG. 4 is a flowchart of an inverse element operation method in the first embodiment;

[0040] FIG. 5 is a flowchart of a preliminary operation process (S120) in the first embodiment;

[0041] FIG. 6 is a flowchart of an inverse element operation process (S130) in the first embodiment;

[0042] FIG. 7 is a hardware configuration diagram of the inverse element operation apparatus 100 in the first embodiment;

[0043] FIG. 8 is a configuration diagram of an inverse element operation apparatus 200 in a second embodiment;

[0044] FIG. 9 is a configuration diagram of a preliminary operation unit 220 in the second embodiment;

[0045] FIG. 10 is a configuration diagram of an inverse element operation unit 230 in the second embodiment;

[0046] FIG. 11 is a flowchart of an inverse element operation method in the second embodiment;

[0047] FIG. 12 is a flowchart of a preliminary operation process (S220) in the second embodiment;

[0048] FIG. 13 is a flowchart of an inverse element operation process (S230) in the second embodiment; and

[0049] FIG. 14 is a hardware configuration diagram of the inverse element operation apparatus 200 in the second embodiment.

DESCRIPTION OF EMBODIMENTS

[0050] In the embodiments and drawings, the same elements or corresponding elements are denoted by the same reference sign. Description of an element denoted by the same reference sign as that of an element that has been described will be omitted or simplified as appropriate. Arrows in diagrams mainly indicate flows of data or flows of processing.

First Embodiment

[0051] An embodiment in which an inverse element a.sup.−1 of an element a of a cyclotomic subgroup is calculated will be described based on FIGS. 1 to 7.

[0052] *** Description of Configuration ***

[0053] Based on FIG. 1, a configuration of an inverse element operation apparatus 100 will be described.

[0054] The inverse element operation apparatus 100 is a computer that includes hardware such as a processor 101, a memory 102, an auxiliary storage device 103, a communication device 104, and an input/output interface 105. These hardware components are connected with one another through signal lines.

[0055] The processor 101 is an IC that performs operational processing and controls other hardware components. For example, the processor 101 is a CPU.

[0056] IC is an abbreviation for Integrated Circuit.

[0057] CPU is an abbreviation for Central Processing Unit.

[0058] The memory 102 is a volatile or non-volatile storage device. The memory 102 is also called a main storage device or a main memory. For example, the memory 102 is a RAM. Data stored in the memory 102 is saved in the auxiliary storage device 103 as necessary.

[0059] RAM is an abbreviation for Random Access Memory.

[0060] The auxiliary storage device 103 is anon-volatile storage device. For example, the auxiliary storage device 103 is a ROM, an HDD, or a flash memory. Data stored in the auxiliary storage device 103 is loaded into the memory 102 as necessary.

[0061] ROM is an abbreviation for Read Only Memory.

[0062] HDD is an abbreviation for Hard Disk Drive.

[0063] The communication device 104 is a receiver and a transmitter. For example, the communication device 104 is a communication chip or a NIC.

[0064] NIC is an abbreviation for Network Interface Card.

[0065] The input/output interface 105 is a port to which an input device and an output device are connected. For example, the input/output interface 105 is a USB terminal, the input device is a keyboard and a mouse, and the output device is a display.

[0066] USB is an abbreviation for Universal Serial Bus.

[0067] The inverse element operation apparatus 100 includes elements such as an acceptance unit 110, a preliminary operation unit 120, an inverse element operation unit 130, and an output unit 140. These elements are realized by software.

[0068] The auxiliary storage device 103 stores an inverse element operation program to cause a computer to function as the acceptance unit 110, the preliminary operation unit 120, the inverse element operation unit 130, and the output unit 140. The inverse element operation program is loaded into the memory 102 and executed by the processor 101.

[0069] The auxiliary storage device 103 further stores an OS. At least part of the OS is loaded into the memory 102 and executed by the processor 101.

[0070] The processor 101 executes the inverse element operation program while executing the OS.

[0071] OS is an abbreviation for Operating System.

[0072] Input data and output data of the inverse element operation program are stored in a storage unit 190.

[0073] The memory 102 functions as the storage unit 190. However, a storage device such as the auxiliary storage device 103, a register in the processor 101, and a cache memory in the processor 101 may function as the storage unit 190 in place of the memory 102 or together with the memory 102.

[0074] The inverse element operation apparatus 100 may include a plurality of processors as an alternative to the processor 101.

[0075] The inverse element operation program can be recorded (stored) in a computer readable format in a non-volatile recording medium such as an optical disc or a flash memory.

[0076] Based on FIG. 2, a configuration of the preliminary operation unit 120 will be described.

[0077] The preliminary operation unit 120 includes elements such as a squaring unit 121, a first multiplication unit 122, an addition unit 123, a subtraction unit 124, and a second multiplication unit 125. The functions of these elements will be described later.

[0078] Based on FIG. 3, a configuration of the inverse element operation unit 130 will be described.

[0079] The inverse element operation unit 130 includes elements such as a first operation unit 131, a second operation unit 132, and a third operation unit 133. The functions of these elements will be described later.

[0080] *** Description of Preliminary Conditions ***

[0081] Preliminary conditions for an inverse element calculation by the inverse element operation apparatus 100 will be described.

[0082] “p” is a prime number.

[0083] “F.sub.p” is a field whose number of elements is p.

[0084] “k” and “n” are integers that satisfy k=3n.

[0085] Each of “F.sub.p.sup.n” and “F.sub.p.sup.k” is an extension field of the field F.sub.p.

[0086] “α” is an element of the field F.sub.p.

[0087] The extension field F.sub.p.sup.n and the extension field F.sub.p.sup.k are expressed by the following formulas.

F.sub.p.sup.n=F.sub.p[v]/(v.sup.n−α),

F.sub.p.sup.k=F.sub.p.sup.n[w]/(w.sup.3−v).

[0088] “GΦ3(p.sup.n)” is a set of elements of the extension field F.sub.p.sup.k with order Φ3(p.sup.n), and is called a cyclotomic subgroup. Note that Φm(x) is an m-th cyclotomic polynomial.

[0089] “α” is an element of the set GΦ3(p.sup.n). That is, “a” is the element of the cyclotomic subgroup.

[0090] “a.sup.−1” is an inverse element of the element a.

[0091] Each of “a.sub.0”, “a.sub.1”, and “a.sub.2” is an element of the extension field F.sub.p.sup.n.

[0092] The element a is expressed by the following formula.

a=a.sub.0+a.sub.1w+a.sub.2w.sup.2∈GΦ3(p.sup.n)

[0093] The inverse element “a.sup.−1” is expressed by the following formula.

a.sup.−1=(a.sub.0.sup.2−a.sub.1a.sub.2v)+(a.sub.2.sup.2v−a.sub.0a.sub.1)w+(a.sub.1.sup.2−a.sub.0a.sub.2)w.sup.2

[0094] *** Description of Operation ***

[0095] A procedure for operation of the inverse element operation apparatus 100 is equivalent to an inverse element operation method. The procedure for operation of the inverse element operation apparatus 100 is also equivalent to a procedure for processing by the inverse element operation program.

[0096] Based on FIG. 4, the inverse element operation method will be described.

[0097] In step S110, the acceptance unit 110 accepts an element a.

[0098] For example, the element a is transmitted to the inverse element operation apparatus 100 from a pairing mapping apparatus that performs operations of pairing mapping or a pairing-based cryptographic apparatus that performs operations of pairing-based cryptography. Then, the acceptance unit 110 receives the element a.

[0099] For example, the element a is input to the inverse element operation apparatus 100 by a user. Then, the acceptance unit 110 accepts the element a that has been input.

[0100] The element a includes a.sub.0, a.sub.1, and a.sub.2 and is expressed by the following formula.

a=a.sub.0+a.sub.1w+a.sub.2w.sup.2

[0101] In step S120, the preliminary operation unit 120 calculates t.sub.1, t.sub.2, t.sub.3, t.sub.4, and t.sub.7, using a.sub.0, a.sub.1, and a.sub.2, where

[0102] t.sub.1 is a computation result of a.sub.0.sup.2,

[0103] t.sub.2 is a computation result of a.sub.2.sup.2,

[0104] t.sub.3 is a computation result of a.sub.0a.sub.1,

[0105] t.sub.4 is a computation result of a.sub.1a.sub.2, and

[0106] t.sub.7 is equal to a computation result of (a.sub.0+a.sub.1)(a.sub.1−a.sub.2).

[0107] A computation result of X is a value obtained by computing X.

[0108] Y that is equal to a computation result of X is the same value as the value obtained by computing X, and is obtained without computing X.

[0109] Details of step S120 will be described later.

[0110] In step S130, the inverse element operation unit 130 calculates b.sub.0, b.sub.1, and b.sub.2, using t.sub.1, t.sub.2, t.sub.3, t.sub.4, and t.sub.7, where

[0111] b.sub.0 is equal to a computation result of a.sub.0.sup.2−a.sub.1a.sub.2v,

[0112] b.sub.1 is equal to a computation result of a.sub.2.sup.2v−a.sub.0a.sub.1, and

[0113] b.sub.2 is equal to a computation result of a.sub.1.sup.2−a.sub.0a.sub.2.

[0114] Details of step S130 will be described later.

[0115] In step S140, the output unit 140 outputs an inverse element a.sup.−1.

[0116] For example, the output unit 140 transmits the inverse element a.sup.−1 to the transmission source of the element a. Alternatively, the output unit 140 writes the inverse element a.sup.−1 in a recording medium specified by the user.

[0117] The inverse element a.sup.−1 is the inverse element of the element a and is expressed by the following formula.

a.sup.−1=(a.sub.0.sup.2−a.sub.1a.sub.2v)+(a.sub.2.sup.2v−a.sub.0a.sub.1)w+(a.sub.1.sup.2−a.sub.0a.sub.2)w.sup.2

[0118] Based on FIG. 5, a preliminary operation process (S120) will be described.

[0119] In step S121, the squaring unit 121 performs a squaring using a.sub.0. Specifically, the squaring unit 121 computes a.sub.0.sup.2. By this, t.sub.1 is calculated.

[0120] This t.sub.1 is a computation result of a.sub.0.sup.2 and is expressed as indicated below.

t.sub.1←a.sub.0.sup.2

[0121] In step S122, the squaring unit 121 performs a squaring using a.sub.2. Specifically, the squaring unit 121 computes a.sub.2.sup.2. By this, t.sub.2 is calculated.

[0122] This t.sub.2 is a computation result of a.sub.2.sup.2 and is expressed as indicated below.

t.sub.2←a.sub.2.sup.2

[0123] In step S123, the first multiplication unit 122 performs a multiplication using a.sub.0 and a.sub.1. Specifically, the first multiplication unit 122 computes a.sub.0a.sub.1. By this, t.sub.3 is calculated.

[0124] This t.sub.3 is a computation result of a.sub.0a.sub.1 and is expressed as indicated below.

t.sub.3←a.sub.0a.sub.1

[0125] In step S124, the first multiplication unit 122 performs a multiplication using a.sub.1 and a.sub.2. Specifically, the first multiplication unit 122 computes a.sub.1a.sub.2. By this, t.sub.4 is calculated.

[0126] This t.sub.4 is a computation result of a.sub.1a.sub.2 and is expressed as indicated below.

t.sub.4←a.sub.1a.sub.2

[0127] In step S125, the addition unit 123 performs an addition using a.sub.0 and a.sub.1. Specifically, the addition unit 123 computes a.sub.0+a.sub.1. By this, t.sub.5 is calculated.

[0128] This t.sub.5 is a computation result of a.sub.0+a.sub.1 and is expressed as indicated below.

t.sub.5←a.sub.0+a.sub.1

[0129] In step S126, the subtraction unit 124 performs a subtraction using a.sub.1 and a.sub.2. Specifically, the subtraction unit 124 computes a.sub.1−a.sub.2. By this, t.sub.6 is calculated.

[0130] This t.sub.6 is a computation result of a.sub.1−a.sub.2 and is expressed as indicated below.

t.sub.6←a.sub.1−a.sub.2

[0131] In step S127, the second multiplication unit 125 performs a multiplication using t.sub.5 and t.sub.6. Specifically, the second multiplication unit 125 computes t.sub.5t.sub.6. By this, t.sub.7 is calculated.

[0132] This t.sub.7 is a computation result of t.sub.5t.sub.6 and is expressed as indicated below.

t.sub.7←t.sub.5t.sub.6=(a.sub.0+a.sub.1)(a.sub.1−a.sub.2)

[0133] Based on FIG. 6, an inverse element operation process (S130) will be described.

[0134] In step S131, the first operation unit 131 performs a subtraction using t.sub.1 and t.sub.4.

[0135] Specifically, the first operation unit 131 multiplies t.sub.4 by v to calculate t.sub.4v. Then, the first operation unit 131 computes t.sub.1−t.sub.4v. “v” is a predetermined value.

[0136] By this, b.sub.0 is calculated.

[0137] This b.sub.0 is a computation result of t.sub.1−t.sub.4v and is expressed as indicated below.

b.sub.0←t.sub.1−t.sub.4v=a.sub.0.sup.2−a.sub.1a.sub.2v

[0138] In step S132, the second operation unit 132 performs a subtraction using t.sub.2 and t.sub.3.

[0139] Specifically, the second operation unit 132 multiplies t.sub.2 by v to calculate t.sub.2v. Then, the second operation unit 132 computes t.sub.2v−t.sub.3.

[0140] By this, b.sub.1 is calculated.

[0141] This b.sub.1 is a computation result of t.sub.2v−t.sub.3 and is expressed as indicated below.

b.sub.1←t.sub.2v−t.sub.3=a.sub.2.sup.2v−a.sub.0a.sub.1

[0142] In step S133, the third operation unit 133 performs an addition and a subtraction using t.sub.3, t.sub.4, and t.sub.7. Specifically, the third operation unit 133 computes t.sub.7−t.sub.3+t.sub.4. By this, b.sub.2 is calculated.

[0143] This b.sub.2 is a computation result of t.sub.7−t.sub.3+t.sub.4 and is expressed as indicated below.

[00001] $\begin{matrix} b_{2} ⟵ t_{7} - t_{3} + t_{4} = (a_{0} + a_{1}) (a_{1} - a_{2}) - a_{0} a_{1} + a_{1} a_{2} \\ = a_{0} a_{1} - a_{0} a_{2} + a_{1}^{2} - a_{1} a_{2} - a_{0} a_{1} + a_{1} a_{2} \\ = a_{1}^{2} - a_{0} a_{2} \end{matrix}$

[0144] *** Description of Effects of the First Embodiment ***

[0145] By the first embodiment, squarings on a finite field for calculating an inverse element a.sup.−1 can be reduced from three times to twice. That is, an inverse element calculation can be speeded up. As a result, pairing-based cryptography can be made more efficient.

[0146] *** Supplement to the First Embodiment ***

[0147] Based on FIG. 7, a hardware configuration of the inverse element operation apparatus 100 will be described.

[0148] The inverse element operation apparatus 100 includes processing circuitry 109.

[0149] The processing circuitry 109 is hardware that realizes the acceptance unit 110, the preliminary operation unit 120, the inverse element operation unit 130, and the output unit 140.

[0150] The processing circuitry 109 may be dedicated hardware, or may be the processor 101 that executes programs stored in the memory 102.

[0151] When the processing circuitry 109 is dedicated hardware, the processing circuitry 109 is, for example, a single circuit, a composite circuit, a programmed processor, a parallel-programmed processor, an ASIC, an FPGA, or a combination of these.

[0152] ASIC is an abbreviation for Application Specific Integrated Circuit.

[0153] FPGA is an abbreviation for Field Programmable Gate Array.

[0154] The inverse element operation apparatus 100 may include a plurality of processing circuits as an alternative to the processing circuitry 109.

[0155] In the processing circuitry 109, some functions may be realized by dedicated hardware, and the rest of the functions may be realized by software or firmware.

[0156] As described above, the functions of the inverse element operation apparatus 100 can be realized by hardware, software, firmware, or a combination of these.

Second Embodiment

[0157] With regard to an embodiment in which an inverse element a.sup.1 of an element a of a cyclotomic subgroup is calculated, differences from the first embodiment will be mainly described based on FIGS. 8 to 14.

[0158] *** Description of Configuration ***

[0159] Based on FIG. 8, a configuration of an inverse element operation apparatus 200 will be described.

[0160] The inverse element operation apparatus 200 is equivalent to the inverse element operation apparatus 100 in the first embodiment.

[0161] The inverse element operation apparatus 200 is a computer that includes hardware such as a processor 201, a memory 202, an auxiliary storage device 203, a communication device 204, and an input/output interface 205. These hardware components are connected with one another through signal lines.

[0162] The processor 201 is an IC that performs operational processing and controls other hardware components. For example, the processor 201 is a CPU.

[0163] The memory 202 is a volatile or non-volatile storage device. The memory 202 is also called a main storage device or a main memory. For example, the memory 202 is a RAM. Data stored in the memory 202 is saved in the auxiliary storage device 203 as necessary.

[0164] The auxiliary storage device 203 is anon-volatile storage device. For example, the auxiliary storage device 203 is a ROM, an HDD, or a flash memory. Data stored in the auxiliary storage device 203 is loaded into the memory 202 as necessary.

[0165] The communication device 204 is a receiver and a transmitter. For example, the communication device 204 is a communication chip or a NIC.

[0166] The input/output interface 205 is a port to which an input device and an output device are connected. For example, the input/output interface 205 is a USB terminal, the input device is a keyboard and a mouse, and the output device is a display.

[0167] The inverse element operation apparatus 200 includes elements such as an acceptance unit 210, a preliminary operation unit 220, an inverse element operation unit 230, and an output unit 240. These elements are realized by software.

[0168] The auxiliary storage device 203 stores an inverse element operation program to cause a computer to function as the acceptance unit 210, the preliminary operation unit 220, the inverse element operation unit 230, and the output unit 240. The inverse element operation program is loaded into the memory 202 and executed by the processor 201.

[0169] The auxiliary storage device 203 further stores an OS. At least part of the OS is loaded into the memory 202 and executed by the processor 201.

[0170] The processor 201 executes the inverse element operation program while executing the OS.

[0171] Input data and output data of the inverse element operation program are stored in a storage unit 290.

[0172] The memory 202 functions as the storage unit 290. However, a storage device such as the auxiliary storage device 203, a register in the processor 201, and a cache memory in the processor 201 may function as the storage unit 290 in place of the memory 202 or together with the memory 202.

[0173] The inverse element operation apparatus 200 may include a plurality of processors as an alternative to the processor 201.

[0174] The inverse element operation program can be recorded (stored) in a computer readable format in a non-volatile recording medium such as an optical disc or a flash memory.

[0175] Based on FIG. 9, a configuration of the preliminary operation unit 220 will be described.

[0176] The preliminary operation unit 220 includes elements such as a first squaring unit 221, a multiplication unit 222, a first fractional multiplication unit 223, an operation unit 224, a second squaring unit 225, and a second fractional multiplication unit 226. The functions of these elements will be described later.

[0177] Based on FIG. 10, a configuration of the inverse element operation unit 230 will be described.

[0178] The inverse element operation unit 230 includes elements such as a first operation unit 231, a second operation unit 232, and a third operation unit 233. The functions of these elements will be described later.

[0179] *** Description of Preliminary Conditions ***

[0180] Preliminary conditions for an inverse element calculation by the inverse element operation apparatus 200 are the same as the preliminary conditions in the first embodiment.

[0181] *** Description of Operation ***

[0182] A procedure for operation of the inverse element operation apparatus 200 is equivalent to an inverse element operation method. The procedure for operation of the inverse element operation apparatus 200 is also equivalent to a procedure for processing by the inverse element operation program.

[0183] Based on FIG. 11, the inverse element operation method will be described.

[0184] In step S210, the acceptance unit 210 accepts an element a.

a=a.sub.0+a.sub.1w+a.sub.2w.sup.2

[0185] Step S210 is the same as step S110 in the first embodiment.

[0186] In step S220, the preliminary operation unit 220 calculates t.sub.1, t.sub.2, t.sub.3, t.sub.4, t.sub.7, and t.sub.8, using a.sub.0, a.sub.1, and a.sub.2, where

[0187] t.sub.1 is a computation result of a.sub.0.sup.2,

[0188] t.sub.2 is a computation result of a.sub.2.sup.2,

[0189] t.sub.3 is a computation result of a.sub.0a.sub.1,

[0190] t.sub.4 is a computation result of a.sub.1a.sub.2,

[0191] t.sub.7 is equal to a computation result of a.sub.0.sup.2+a.sub.1.sup.2+a.sub.2.sup.2/4+2a.sub.0a.sub.1−a.sub.0a.sub.2−a.sub.1a.sub.2, and

[0192] t.sub.8 is equal to a computation result of a.sub.2.sup.2/4.

[0193] Details of step S220 will be described later.

[0194] In step S230, the inverse element operation unit 230 calculates b.sub.0, b.sub.1, and b.sub.2, using t.sub.1, t.sub.2, t.sub.3, t.sub.4, t.sub.7, and t.sub.8, where

[0195] b.sub.0 is equal to a computation result of a.sub.0.sup.2−a.sub.1a.sub.2v,

[0196] b.sub.1 is equal to a computation result of a.sub.2.sup.2v−a.sub.0a.sub.1, and

[0197] b.sub.2 is equal to a computation result of a.sub.1.sup.2−a.sub.0a.sub.2.

[0198] Details of step S230 will be described later.

[0199] In step S240, the output unit 140 outputs an inverse element a.sup.−1.

a.sup.−1=(a.sub.0.sup.2−a.sub.1a.sub.2v)+(a.sub.2.sup.2v−a.sub.0a.sub.1)w+(a.sub.1.sup.2−a.sub.0a.sub.2)w.sup.2

[0200] Step S240 is the same as step S140 in the first embodiment.

[0201] Based on FIG. 12, a preliminary operation process (S220) will be described.

[0202] In step S221, the first squaring unit 221 performs a squaring using a.sub.0.

[0203] Specifically, the first squaring unit 221 computes a.sub.0.sup.2. By this, t.sub.1 is calculated.

[0204] This t.sub.1 is a computation result of a.sub.0.sup.2 and is expressed as indicated below.

t.sub.1←a.sub.0.sup.2

[0205] In step S222, the first squaring unit 221 performs a squaring using a.sub.2. Specifically, the first squaring unit 221 computes a.sub.2.sup.2. By this, t.sub.2 is calculated.

[0206] This t.sub.2 is a computation result of a.sub.2.sup.2 and is expressed as indicated below.

t.sub.2←a.sub.2.sup.2

[0207] In step S223, the multiplication unit 222 performs a multiplication using a.sub.0 and a.sub.1. Specifically, the multiplication unit 222 computes a.sub.0a.sub.1. By this, t.sub.3 is calculated.

[0208] This t.sub.3 is a computation result of a.sub.0a.sub.1 and is expressed as indicated below.

t.sub.3←a.sub.0a.sub.1

[0209] In step S224, the multiplication unit 222 performs a multiplication using a.sub.1 and a.sub.2. Specifically, the multiplication unit 222 computes a.sub.1a.sub.2. By this, t.sub.4 is calculated.

[0210] This t.sub.4 is a computation result of a.sub.1a.sub.2 and is expressed as indicated below.

t.sub.4←a.sub.1a.sub.2

[0211] In step S225, the first fractional multiplication unit 223 performs a ½ multiplication using a.sub.2. Specifically, the first fractional multiplication unit 223 computes a.sub.2/2. By this, t.sub.5 is calculated.

[0212] This t.sub.5 is a computation result of a.sub.2/2 and is expressed as indicated below.

t.sub.5←a.sub.2/2

[0213] In step S226, the operation unit 224 performs an addition and a subtraction using a.sub.0, a.sub.1, and t.sub.5. Specifically, the operation unit 224 computes a.sub.0+a.sub.1−t.sub.5. By this, t.sub.6 is calculated.

[0214] This t.sub.6 is a computation result of a.sub.0+a.sub.1−t.sub.5 and is expressed as indicated below.

t.sub.6←a.sub.0+a.sub.1−t.sub.5=a.sub.0+a.sub.1−a.sub.2/2

[0215] In step S227, the second squaring unit 225 performs a squaring using t.sub.6. Specifically, the second squaring unit 225 computes t.sub.6.sup.2. By this, t.sub.7 is calculated.

[0216] This t.sub.7 is a computation result of t.sub.6.sup.2 and is expressed as indicated below.

[00002] $\begin{matrix} t_{7} ⟵ t_{6}^{2} = {(a_{0} + a_{1} - a_{2} / 2)}^{2} \\ = a_{0}^{2} + a_{0} a_{1} - a_{0} a_{2} / 2 + a_{0} a_{1} + a_{1}^{2} - a_{1} a_{2} / 2 - a_{1} a_{2} / 2 + a_{2}^{2} / 4 \\ = a_{0}^{2} + a_{1}^{2} + a_{2}^{2} / 4 + 2 a_{0} a_{1} - a_{0} a_{2} - a_{1} a_{2} \end{matrix}$

[0217] In step S228, the second fractional multiplication unit 226 performs a ¼ multiplication using t.sub.2. Specifically, the second fractional multiplication unit 226 computes t.sub.2/4. By this, t.sub.8 is calculated.

[0218] This t.sub.8 is a computation result of t.sub.2/4 and is expressed as indicated below.

t.sub.8←t.sub.2/4=a.sub.2.sup.2/4

[0219] Based on FIG. 13, an inverse element operation process (S230) will be described.

[0220] In step S231, the first operation unit 231 performs a subtraction using t.sub.1 and t.sub.4.

[0221] Specifically, the first operation unit 131 multiplies t.sub.4 by v to calculate t.sub.4v. Then, the first operation unit 131 compute t.sub.1−t.sub.4v.

[0222] By this, b.sub.0 is calculated.

[0223] This b.sub.0 is a computation result of a.sub.0.sup.2−a.sub.1a.sub.2v and is expressed as indicated below.

b.sub.0←t.sub.1−t.sub.4v=a.sub.0.sup.2−a.sub.1a.sub.2v

[0224] In step S232, the second operation unit 232 performs a subtraction using t.sub.2 and t.sub.3.

[0225] Specifically, the second operation unit 132 multiplies t.sub.2 by v to calculate t.sub.2v. Then, the second operation unit 132 computes t.sub.2v−t.sub.3.

[0226] By this, b.sub.1 is calculated.

[0227] This b.sub.1 is a computation result of t.sub.2v−t.sub.3 and is expressed as indicated below.

b.sub.1←t.sub.2v−t.sub.3=a.sub.2.sup.2v−a.sub.0a.sub.1

[0228] In step S233, the third operation unit 233 performs an addition and subtractions using t.sub.1, t.sub.3, t.sub.4, t.sub.7, and t.sub.8. Specifically, the third operation unit 233 computes t.sub.7−t.sub.1−t.sub.8−2t.sub.3+t.sub.4. By this, b.sub.2 is calculated.

[0229] This b.sub.2 is a computation result of t.sub.7−t.sub.1−t.sub.8−2t.sub.3+t.sub.4 and is expressed as indicated below.

[00003] $\begin{matrix} b_{2} ⟵ t_{7} - t_{1} - t_{8} - 2 t_{3} + t_{4} = a_{0}^{2} + a_{1}^{2} + a_{2}^{2} / 4 + 2 a_{0} a_{1} - a_{0} a_{2} - \\ a_{1} a_{2} - a_{0}^{2} - a_{2}^{2} / 4 - 2 a_{0} a_{1} + a_{1} a_{2} \\ = a_{1}^{2} - a_{0} a_{2} \end{matrix}$

[0230] *** Effects of the Second Embodiment ***

[0231] By the second embodiment, multiplications on a finite field for calculating an inverse element a.sup.−1 can be reduced from three times to twice. That is, an inverse element calculation can be speeded up. As a result, pairing-based cryptography can be made more efficient.

[0232] *** Supplement to the Second Embodiment *** Based on FIG. 14, a hardware configuration of the inverse element operation apparatus 200 will be described.

[0233] The inverse element operation apparatus 200 includes processing circuitry 209.

[0234] The processing circuitry 209 is hardware that realizes the acceptance unit 210, the preliminary operation unit 220, the inverse element operation unit 230, and the output unit 240.

[0235] The processing circuitry 209 may be dedicated hardware, or may be the processor 201 that executes programs stored in the memory 202.

[0236] When the processing circuitry 209 is dedicated hardware, the processing circuitry 209 is, for example, a single circuit, a composite circuit, a programmed processor, a parallel-programmed processor, an ASIC, an FPGA, or a combination of these.

[0237] The inverse element operation apparatus 200 may include a plurality of processing circuits as an alternative to the processing circuitry 209.

[0238] In the processing circuitry 209, some functions may be realized by dedicated hardware, and the rest of the functions may be realized by software or firmware.

[0239] As described above, the functions of the inverse element operation apparatus 200 can be realized by hardware, software, firmware, or a combination of these.

[0240] *** Supplement to the Embodiments ***

[0241] Each of the embodiments is an example of a preferred embodiment and is not intended to limit the technical scope of the present disclosure. Each of the embodiments may be implemented partially or may be implemented in combination with another embodiment. The procedures described using the flowcharts or the like may be changed as appropriate.

[0242] Each “unit” that is an element of the inverse element operation apparatus (100, 200) may be interpreted as “process” or “step”.

REFERENCE SIGNS LIST

[0243] 100: inverse element operation apparatus, 101: processor, 102: memory, 103: auxiliary storage device, 104: communication device, 105: input/output interface, 109: processing circuitry, 110: acceptance unit, 120: preliminary operation unit, 121: squaring unit, 122: first multiplication unit, 123: addition unit, 124: subtraction unit, 125: second multiplication unit, 130: inverse element operation unit, 131: first operation unit, 132: second operation unit, 133: third operation unit, 140: output unit, 190: storage unit, 200: inverse element operation apparatus, 201: processor, 202: memory, 203: auxiliary storage device, 204: communication device, 205: input/output interface, 209: processing circuitry, 210: acceptance unit, 220: preliminary operation unit, 221: first squaring unit, 222: multiplication unit, 223: first fractional multiplication unit, 224: operation unit, 225: second squaring unit, 226: second fractional multiplication unit, 230: inverse element operation unit, 231: first operation unit, 232: second operation unit, 233: third operation unit, 240: output unit, 290: storage unit.

INVERSE ELEMENT OPERATION APPARATUS AND COMPUTER READABLE MEDIUM

Assignee

Inventors

Cpc classification

Classification Explorer

G09C1/00

PHYSICS

Classification Explorer

G06F7/721

PHYSICS

Classification Explorer

G06F7/50

PHYSICS

Classification Explorer

G06F7/523

PHYSICS

Classification Explorer

G06F7/552

PHYSICS

International classification

Classification Explorer

G06F7/552

PHYSICS

Classification Explorer

G06F7/523

PHYSICS

Classification Explorer

G06F7/50

PHYSICS

Abstract

Claims

Description