CRYPTOGRAPHIC SYSTEM, ENCRYPTION DEVICE, DECRYPTION DEVICE, AND KEY GENERATION DEVICE

Abstract

A cryptographic system (1) performs a cryptographic process in which a Richelot isogeny sequence φ.sub.s whose starting point is an abelian surface A.sub.0 and whose end point is an abelian surface A.sub.s is a secret key and the abelian surface A.sub.s is a public key. An encryption device (28) computes an abelian surface A.sub.m by transitioning the abelian surface A.sub.s, which is the public key, by a Richelot isogeny sequence φ.sub.m generated by encoding a plaintext m, and sets the abelian surface A.sub.m as a ciphertext. A decryption device (30) computes a Richelot isogeny φ.sub.m whose starting point is the abelian surface A.sub.s, which is the public key, and whose end point is the abelian surface A.sub.m, which is the ciphertext, based on the Richelot isogeny sequence φ.sub.s, which is the secret key.

Claims

1. A cryptographic system to perform a cryptographic process in which a Richelot isogeny sequence φ.sub.s whose starting point is an abelian surface A.sub.0 and whose end point is an abelian surface A.sub.s is a secret key and the abelian surface A.sub.s is a public key, the cryptographic system comprising: an encryption device to compute an abelian surface A.sub.m by transitioning the abelian surface A.sub.s, which is the public key, by a Richelot isogeny sequence φ.sub.m generated by encoding a plaintext m, and set the abelian surface A.sub.m as a ciphertext; and a decryption device to compute a Richelot isogeny φ.sub.m whose starting point is the abelian surface A.sub.s, which is the public key, and whose end point is the abelian surface A.sub.m, which is the ciphertext, based on the Richelot isogeny sequence φ.sub.s, which is the secret key.

2. The cryptographic system according to claim 1, further comprising a key generation device to compute a Richelot isogeny φ.sub.0 of an abelian surface A.sub.0 to compute an abelian surface A.sub.1, compute a Richelot isogeny φ.sub.i to compute an abelian surface A.sub.i+1 by rearranging zero points of the abelian surface A.sub.i for each integer i of i=1, . . . , κ−1 in ascending order, using an integer κ of 2 or more, set the abelian surface A.sub.s that is an abelian surface A.sub.κ as the public key, and set the Richelot isogeny sequence φ.sub.s that is a set of Richelot isogenies φ.sub.i for integers i of i=0, . . . , κ−1 as the secret key.

3. The cryptographic system according to claim 1, wherein the cryptographic system uses, as the abelian surface A.sub.0, a genus-2 curve corresponding to the abelian surface A.sub.0.

4. The cryptographic system according to claim 2, wherein the cryptographic system uses, as the abelian surface A.sub.0, a genus-2 curve corresponding to the abelian surface A.sub.0.

5. The cryptographic system according to claim 3, wherein the genus-2 curve corresponds to a portion adjacent to a portion decomposed into a direct product of an elliptic curve E.sub.0 out of portions not decomposed into the direct product of the elliptic curve E.sub.0 in the abelian surface A.sub.0.

6. The cryptographic system according to claim 4, wherein the genus-2 curve corresponds to a portion adjacent to a portion decomposed into a direct product of an elliptic curve E.sub.0 out of portions not decomposed into the direct product of the elliptic curve E.sub.0 in the abelian surface A.sub.0.

7. The cryptographic system according to claim 1, wherein the cryptographic system uses, as the abelian surface A.sub.0, a portion decomposed into a direct product of an elliptic curve E.sub.0 in the abelian surface A.sub.0.

8. The cryptographic system according to claim 2, wherein the cryptographic system uses, as the abelian surface A.sub.0, a portion decomposed into a direct product of an elliptic curve E.sub.0 in the abelian surface A.sub.0.

9. The cryptographic system according to claim 5, wherein the elliptic curve E.sub.0 is E.sub.0/F.sub.p:y.sup.2=x.sup.3+x when a remainder of dividing a prime number p by 4 is 3, or E.sub.0/F.sub.p:y.sup.2=x.sup.3+c when the remainder of dividing the prime number p by 4 is 1, where c is a constant.

10. The cryptographic system according to claim 6, wherein the elliptic curve E.sub.0 is E.sub.0/F.sub.p:y.sup.2=x.sup.3+x when a remainder of dividing a prime number p by 4 is 3, or E.sub.0/F.sub.p:y.sup.2=x.sup.3+c when the remainder of dividing the prime number p by 4 is 1, where c is a constant.

11. The cryptographic system according to claim 7, wherein the elliptic curve E.sub.0 is E.sub.0/F.sub.p:y.sup.2=x.sup.3+x when a remainder of dividing a prime number p by 4 is 3, or E.sub.0/F.sub.p:y.sup.2=x.sup.3+c when the remainder of dividing the prime number p by 4 is 1, where c is a constant.

12. The cryptographic system according to claim 8, wherein the elliptic curve E.sub.0 is E.sub.0/F.sub.p:y.sup.2=x.sup.3+x when a remainder of dividing a prime number p by 4 is 3, or E.sub.0/F.sub.p:y.sup.2=x.sup.3+c when the remainder of dividing the prime number p by 4 is 1, where c is a constant.

13. An encryption device in a cryptographic system to perform a cryptographic process in which a Richelot isogeny sequence φ.sub.s whose starting point is an abelian surface A.sub.0 and whose end point is an abelian surface A.sub.s is a secret key and the abelian surface A.sub.s is a public key, the encryption device comprising processing circuitry to compute an abelian surface A.sub.m by transitioning the abelian surface A.sub.s, which is the public key, by a Richelot isogeny sequence φ.sub.m generated by encoding a plaintext m, and set the abelian surface A.sub.m as a ciphertext.

14. A decryption device in a cryptographic system to perform a cryptographic process in which a Richelot isogeny sequence φ.sub.s whose starting point is an abelian surface A.sub.0 and whose end point is an abelian surface A.sub.s is a secret key and the abelian surface A.sub.s is a public key, the decryption device comprising processing circuitry to: acquire a ciphertext that is an abelian surface A.sub.m computed by transitioning the abelian surface A.sub.s, which is the public key, by a Richelot isogeny sequence φ.sub.m generated by encoding a plaintext m; and compute a Richelot isogeny φ.sub.m whose starting point is the abelian surface A.sub.s, which is the public key, and whose end point is the abelian surface A.sub.m, which is the acquired ciphertext, based on the Richelot isogeny sequence φ.sub.s, which is the secret key.

15. A key generation device comprising processing circuitry to: acquire an abelian surface A.sub.0, which is a public parameter; compute a Richelot isogeny φ.sub.0 of the acquired abelian surface A.sub.0 to compute an abelian surface A.sub.1, and compute a Richelot isogeny φ.sub.i to compute an abelian surface A.sub.i+1 by rearranging zero points of the abelian surface A.sub.i for each integer i of i=1, . . . , κ−1 in ascending order, using an integer κ of 2 or more; and set a computed abelian surface A.sub.κ as a public key, and set a Richelot isogeny sequence that is a set of Richelot isogenies φ.sub.i for integers i of i=0, . . . , κ−1 as a secret key.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0012] FIG. 1 is a configuration diagram of a cryptographic system 1 according to a first embodiment;

[0013] FIG. 2 is a configuration diagram of a key generation device 10 according to the first embodiment;

[0014] FIG. 3 is a configuration diagram of an encryption device 20 according to the first embodiment;

[0015] FIG. 4 is a configuration diagram of a decryption device 30 according to the first embodiment;

[0016] FIG. 5 is a flowchart of a process of computing a genus-2 curve sequence C.sub.0, . . . , C.sub.κ according to the first embodiment;

[0017] FIG. 6 is a diagram explaining a SETA encryption scheme;

[0018] FIG. 7 is a diagram explaining a genus-2 SETA cryptographic scheme according to the first embodiment;

[0019] FIG. 8 is a flowchart illustrating operation of the key generation device 10 according to the first embodiment;

[0020] FIG. 9 is a flowchart illustrating operation of the encryption device 20 according to the first embodiment;

[0021] FIG. 10 is a flowchart illustrating operation of the decryption device 30 according to the first embodiment;

[0022] FIG. 11 is a configuration diagram of the key generation device 10 according to a first variation;

[0023] FIG. 12 is a configuration diagram of the encryption device 20 according to the first variation; and

[0024] FIG. 13 is a configuration diagram of the decryption device 30 according to the first variation.

DESCRIPTION OF EMBODIMENTS

First Embodiment

***Description of Configurations***

[0025] Referring to FIG. 1, a configuration of a cryptographic system 1 according to a first embodiment will be described.
The cryptographic system 1 includes a key generation device 10, an encryption device 20, and a decryption device 30. The key generation device 10, the encryption device 20, and the decryption device 30 are connected via a communication channel 40 such as a local area network (LAN) or the Internet.

[0026] Referring to FIG. 2, a configuration of the key generation device 10 according to the first embodiment will be described.

The key generation device 10 is a computer.
The key generation device 10 includes hardware of a processor 11, a memory 12, a storage 13, and a communication interface 14. The processor 11 is connected with other hardware components via signal lines and controls these other hardware components.

[0027] The key generation device 10 includes, as functional components, an acquisition unit 111, a map computation unit 112, and a key setting unit 113. The functions of the functional components of the key generation device 10 are realized by software.

The storage 13 stores programs that realize the functions of the functional components of the key generation device 10. These programs are read into the memory 12 by the processor 11 and executed by the processor 11. This realizes the functions of the functional components of the key generation device 10.

[0028] Referring to FIG. 3, a configuration of the encryption device 20 according to the first embodiment will be described.

The encryption device 20 is a computer.
The encryption device 20 includes hardware of a processor 21, a memory 22, a storage 23, and a communication interface 24. The processor 21 is connected with other hardware components via signal lines and controls these other hardware components.

[0029] The encryption device 20 includes, as functional components, an acquisition unit 211 and an encryption unit 212. The functions of the functional components of the encryption device 20 are realized by software.

The storage 23 stores programs that realize the functions of the functional components of the encryption device 20. These programs are read into the memory 22 by the processor 21 and executed by the processor 21. This realizes the functions of the functional components of the encryption device 20.

[0030] Referring to FIG. 4, a configuration of the decryption device 30 according to the first embodiment will be described.

The decryption device 30 is a computer.
The decryption device 30 includes hardware of a processor 31, a memory 32, a storage 33, and a communication interface 34. The processor 31 is connected with other hardware components via signal lines and controls these other hardware components.

[0031] The decryption device 30 includes, as functional components, an acquisition unit 311 and a decryption unit 312. The functions of the functional components of the decryption device 30 are realized by software.

The storage 33 stores programs that realize the functions of the functional components of the decryption device 30. These programs are read into the memory 32 by the processor 31 and executed by the processor 31. This realizes the functions of the functional components of the decryption device 30.

[0032] Each of the processors 11, 21, and 31 is an integrated circuit (IC) that performs processing. Specific examples of each of the processors 11, 21, and 31 are a central processing unit (CPU), a digital signal processor (DSP), and a graphics processing unit (GPU).

[0033] Each of the memories 12, 22, and 32 is a storage device to temporarily store data. Specific examples of each of the memories 12, 22, and 32 are a static random access memory (SRAM) and a dynamic random access memory (DRAM).

[0034] Each of the storages 13, 23, and 33 is a storage device to store data. A specific example of each of the storages 13, 23, and 33 is a hard disk drive (HDD). Each of the storages 13, 23, and 33 may be a portable recording medium such as a Secure Digital (SD, registered trademark) memory card, CompactFlash (CF, registered trademark), a NAND flash, a flexible disk, an optical disc, a compact disc, a Blu-ray (registered trademark) disc, or a digital versatile disc (DVD).

[0035] Each of the communication interfaces 14, 24, and 34 is an interface for communicating with external devices. Specific examples of each of the communication interfaces 14, 24, and 34 are an Ethernet (registered trademark) port, a Universal Serial Bus (USB) port, and a High-Definition Multimedia Interface (HDMI, registered trademark) port.

[0036] FIG. 2 illustrates only one processor 11. However, there may be a plurality of processors 11, and the plurality of processors 11 may cooperatively execute the programs that realize the functions. Similarly, there may be a plurality of processors 21 and a plurality of processors 31.

[0037] ***Description of Operation***

Referring to FIGS. 5 to 10, operation of the cryptographic system 1 according to the first embodiment will be described.
A procedure for the operation of the cryptographic system 1 according to the first embodiment is equivalent to a cryptographic process according to the first embodiment. A program that realizes the operation the cryptographic system 1 according to the first embodiment is equivalent to a cryptographic program according to the first embodiment.

[0038] **Description of Concept**

A concept that is the basis of a cryptographic scheme realized by the cryptographic system 1 according to the first embodiment will be described.

[0039] In Non-Patent Literature 1, elliptic curves are used. The cryptographic system 1 uses genus-2 curves in place of elliptic curves.

A genus-2 curve used by the cryptographic system 1 is an algebraic curve indicated in Formula 11, where a degree deg(f(X)) is 5 or 6.

C:Y.sup.2=f(X)  [Formula 11]

[0040] As indicated in Formula 12, it is assumed that genus-2 curves are transitioned with a genus-2 curve C.sub.0 as the starting point and a genus-2 curve C.sub.κ as the end point by repeating Richelot isogenies κ times, where κ is an integer of 2 or more.

[00001]$\begin{array}{cc}{C}_0\stackrel{{\phi }_0}{.fwdarw.}{C}_1\stackrel{{\phi }_1}{.fwdarw.}.Math.\stackrel{{\phi }_{\kappa -2}}{.fwdarw.}{C}_{\kappa -1}\stackrel{{\phi }_{\kappa -1}}{.fwdarw.}{C}_{\kappa }& \left[\mathrm{Formula}12\right]\end{array}$

As the basic problem concerning cryptographic security, the cryptographic system 1 uses finding (computing) a Richelot isogeny sequence φ.sub.0, φ.sub.1, . . . , φ.sub.κ-1 that interpolates the genus-2 curves C.sub.0 and C.sub.κ when two genus-2 curves of the genus-2 curves C.sub.0 and C.sub.κ are given. The cryptographic system 1 constructs genus-2 SETA cryptography that is based on the hardness of this basic problem.

[0041] Each genus-2 curve is expressed using three polynomials G.sub.j(X) with deg(G.sub.j(X))≤2, as indicated in Formula 13. Note that deg(G.sub.j(X)) is the degree of a polynomial G.sub.j(X).

C:Y.sup.2=f(X)=dΠ.sub.j=0.sup.2G.sub.j(X)  [Formula 13]

[0042] Three new polynomials G˜.sub.j(X) are defined as indicated in Formula 14.

[G.sub.j+1(X),G.sub.j+2(X)]:=G′.sub.j+1(X)G.sub.j+2(X)−G′.sub.j+2(X)G.sub.j+1(X),{tilde over (G)}.sub.j(X):=τ.sub.j.sup.−1[G.sub.j+1(X),G.sub.j+2(X)]  [Formula 14]

Note that τ.sub.j is the highest-degree coefficient of [G.sub.j+1(X), G.sub.j+2(X)]. Therefore, G˜.sub.j(X) is a polynomial whose highest-degree coefficient is 1. G′.sub.j+1(X) is a derivative of G.sub.j+1(X) and G′.sub.j+2 (X) is a derivative of G.sub.j+2 (X). Indices are assigned on the assumption that the three polynomials G.sub.j are treated as a permutation such that G.sub.j+1(X) when j=0 is G.sub.1(X), G.sub.j+1(X) when j=1 is G.sub.2(X), G.sub.j+1(X) when j=2 is G.sub.0(X). Similarly, G.sub.j+2(X) when j=0 is G.sub.2(X), G.sub.j+2 (X) when j=1 is G.sub.0(X), and G.sub.j+2 (X) when j=2 is G.sub.1(X).

[0043] A new genus-2 curve C.sup.˜ is defined as indicated in Formula 15.

{tilde over (C)}:Y.sup.2={tilde over (f)}(X)={tilde over (d)}Π.sub.j=0.sup.2{tilde over (G)}.sub.j(X)  [Formula 15] [0044] with {tilde over (d)}=d.Math.τ.sub.0τ.sub.1τ.sub.2.Math.det((g.sub.j,k).sub.0≤j,k≤2).sup.−1
A correspondence (mapping) from the genus-2 curve C to the genus-2 curve C.sup.˜ is called a Richelot isogeny. The Richelot isogeny from the genus-2 curve C is determined based on a division (G.sub.0(X), G.sub.1(X), G.sub.2(X)) of f(X). This corresponds to a division of zero points of f(X) into three pairs (a.sub.0, a.sub.1), (a.sub.2, a.sub.3), and (a.sub.4, a.sub.5). Note that g will be described later.

[0045] **Description of a Method of Computing a Genus-2 Curve Sequence**

[0046] The cryptographic system 1 computes a genus-2 curve sequence C.sub.0, . . . , C.sub.κ by repeating Richelot isogenies from a genus-2 curve C.sub.0. However, computing a Richelot isogeny based on three polynomials G˜.sub.j(X) will revert to the genus-2 curve C. Therefore, the cryptographic system 1 computes a Richelot isogeny once, then rearranges each root (zero point) of each polynomial G˜.sub.j(X) for a change into three new polynomials, and then computes a Richelot isogeny.

[0047] Referring to FIG. 5, a process of computing the genus-2 curve sequence C.sub.0, . . . , C.sub.κ according to the first embodiment will be described.

[0048] A genus-2 curve C.sub.i is defined as indicated in Formula 16.

[00002]$\begin{array}{cc}{C}_i/{\stackrel{\_}{𝔽}}_p:Y^2=f_i\left(X\right)=d{.Math.}_{j=0}^2{G}_{i,j}\left(X\right)\mathrm{where}& \left[\mathrm{Formula}16\right]\end{array}$$\begin{array}{c}{G}_{i,j}={.Math.}_{k=0}^2{g}_{i,j,k}{X}^k\\ =\{\begin{array}{cc}\left(X-a_{i,2j}\right)\left(X-a_{i,2j+1}\right)& \mathrm{if}\mathrm{deg}\left(G_{i,j}\right)=2\\ X-a_{i,2j}\mathrm{or}X-a_{i,2j+1}& \mathrm{if}\mathrm{deg}\left(G_{i,j}\right)=1\end{array}\end{array}$

[0049] In step S11, three new polynomials (G.sub.i,j(X)).sub.j=0,1,2 are generated from the genus-2 curve C.sub.0 in accordance with Formula 14. By this, a genus-2 curve C.sub.1 is computed.

[0050] In step S12, as indicated in Formula 17, three polynomials G˜.sub.1,j are computed to compute a Richelot isogeny φ.sub.0. Note that τ.sub.0,j is the highest-degree coefficient of [G.sub.0j+1(X), G.sub.0j+2(X)].

{tilde over (G)}.sub.1,j(X):=τ.sub.0,j.sup.−1[G.sub.0,j+1(X),G.sub.0,j+2(X)] for j=0,1,2  [Formula 17]

[0051] Then, processes of step S13 and step S14 are performed for each integer i of i=1, . . . , κ−1 in ascending order.

In step S13, zero points (a.sub.i,m).sub.m=0, . . . , 5 of f.sub.i(X) are rearranged. Then, three new polynomials (G.sub.i,j(X)).sub.j=0,1,2 are generated in accordance with Formula 14. By this, a genus-2 curveC.sub.i+1 is computed.
In step S14, as indicated in Formula 18, three polynomials G˜.sub.i+1,j are computed to compute a Richelot isogeny φ.sub.i. Note that τ.sub.i,j is the highest-degree coefficient of [G.sub.i,j+1(X), G.sub.i,j+2(X)].

{tilde over (G)}.sub.i+1,j(X):=τ.sub.i,j.sup.−1[G.sub.i,j+1(X),G.sub.i,j+2(X)] for j=0,1,2  [Formula 18]

[0052] **SETA Encryption Scheme**

Referring to FIG. 6, a SETA encryption scheme described in Non-Patent Literature 1 will be described.
In the SETA encryption scheme, elliptic curves E.sub.0, E.sub.s, and E.sub.m are used. The elliptic curve E.sub.0 is a public parameter. The elliptic curve E.sub.0 is a special curve whose endomorphism ring is easy.

[0053] <Key Generation Process>

First, an isogeny sequence φ.sub.s, which is a secret key, is generated. Then, the elliptic curve E.sub.0 is transitioned by the isogeny sequence φ.sub.s to calculate an elliptic curve E.sub.s, and the elliptic curve E.sub.s is set as a public key.

<Encryption Process>

[0054] First, a plaintext m is suitably encoded and transformed into an isogeny sequence φ.sub.m. Then, the elliptic curve E.sub.s, which is the public key, is transitioned by the isogeny sequence φ.sub.m to compute an elliptic curve E.sub.m. The elliptic curve E.sub.m is set as a ciphertext.

<Decryption Process>

[0055] An endomorphism ring of the elliptic curve E.sub.s can be computed through computing an endomorphism ring of the elliptic curve E.sub.0, using the isogeny sequence φ.sub.s, which is the secret key. Therefore, an isogeny problem in which the elliptic curve E.sub.s is the starting point and the elliptic curve E.sub.m is the end point can be solved in polynomial time, and the isogeny sequence φ.sub.m can be obtained. The plaintext m is computed from the isogeny sequence φ.sub.m by performing a decode operation, which is the inverse operation of an encode operation at the time of encryption.

[0056] The point of decryption is that a user who knows the isogeny sequence φ.sub.s, which is the secret key, can reduce computing the endomorphism ring of the elliptic curve E.sub.s to computing the endomorphism ring of the elliptic curve E.sub.0 through the isogeny sequence φ.sub.s.

[0057] **Genus-2 SETA Cryptographic Scheme**

Referring to FIGS. 7 to 10, a genus-2 SETA cryptographic scheme that is realized by the cryptographic system 1 according to the first embodiment will be described.
As indicated in FIG. 7, the genus-2 SETA cryptographic scheme is realized by replacing elliptic curves E.sub.0, E.sub.s, and E.sub.m in the SETA encryption scheme with genus-2 curves C.sub.0, C.sub.s, and C.sub.m, respectively, and replacing isogeny sequences φ.sub.s and φ.sub.m with Richelot isogeny sequences φ.sub.s and φ.sub.m, respectively.

[0058] Referring to FIG. 8, operation of the key generation device 10 according to the first embodiment will be described.

A procedure for the operation of the key generation device 10 according to the first embodiment is equivalent to a key generation method according to the first embodiment. A program that realizes the operation of the key generation device 10 according to the first embodiment is equivalent to a key generation program according to the first embodiment.

[0059] (Step S111: Acquisition Process)

The acquisition unit 111 acquires a genus-2 curve C.sub.0, which is a public parameter.

[0060] The acquisition unit 111 writes the genus-2 curve C.sub.0 in the memory 12.

[0061] (Step S112: Map Computation Process)

The map computation unit 112 computes a Richelot isogeny φ.sub.m of the genus-2 curve C.sub.0 acquired in step S111 to compute a genus-2 curve C.sub.1. The map computation unit 112 computes a Richelot isogeny φ.sub.i to compute a genus-2 curve C.sub.i+1 by rearranging zero points of a genus-2 curve C.sub.i for each integer i of i=1, . . . , κ−1 in ascending order, using an integer κ of 2 or more.
Specifically, the map computation unit 112 computes a genus-2 curve sequence C.sub.0, . . . , C.sub.κ and a Richelot isogeny sequence φ.sub.0, . . . , φ.sub.κ-1 by performing the process of computing of the genus-2 curve sequence C.sub.0, . . . , C.sub.κ described with reference to FIG. 5.

[0062] The map computation unit 112 writes the genus-2 curve sequence C.sub.0, . . . , C.sub.κ and the Richelot isogeny sequence φ.sub.0, . . . , φ.sub.κ-1 in the memory 12.

[0063] (Step S113: Key Setting Process)

[0064] The key setting unit 113 sets the genus-2 curve C.sub.κ computed in step S112 as a genus-2 curve C.sub.s as a public key. The key setting unit 113 sets the Richelot isogeny sequence φ.sub.s:={φ.sub.0, . . . , φ.sub.κ-1} computed in step S112 as a secret key. That is, the Richelot isogeny sequence φ.sub.s whose starting point is the genus-2 curve C.sub.0 and whose end point is the genus-2 curve C.sub.s is set as the secret key.

[0065] The key setting unit 113 transmits the public key to the encryption device 20 and the decryption device 30 via the communication interface 14. The key setting unit 113 transmits the secret key in secrecy to the decryption device 30 via the communication interface 14. To transmit in secrecy means, for example, to transmit after encryption using an existing encryption scheme.

[0066] The secret key is the Richelot isogeny sequence φ.sub.s. Substantially, this means that a method of permutations σ.sub.0, . . . , σ.sub.κ-1, which is how roots are rearranged in the process of step 13 in the process of computing the genus-2 curve sequence C.sub.0, . . . , C.sub.κ, corresponds to the secret key.

[0067] Referring to FIG. 9, operation of the encryption device 20 according to the first embodiment will be described.

[0068] A procedure for the operation of the encryption device 20 according to the first embodiment is equivalent to an encryption method according to the first embodiment. A program that realizes the operation of the encryption device 20 according to the first embodiment is equivalent to an encryption program according to the first embodiment.

[0069] (Step S211: Acquisition Process)

[0070] The acquisition unit 211 acquires the genus-2 curve C.sub.s, which is the public key generated by the key generation device 10. The acquisition unit 211 acquires a plaintext m. The plaintext m is input by a user of the encryption device 20.

[0071] The acquisition unit 211 writes the genus-2 curve C.sub.s and the plaintext m in the memory 22.

[0072] (Step S212: Encryption Process)

[0073] The encryption unit 212 encodes the plaintext m acquired in step S211 to transform the plaintext m into a Richelot isogeny sequence φ.sub.m. The encryption unit 212 transitions the genus-2 curve C.sub.s, which is the public key, acquired in step S211 by the Richelot isogeny sequence φ.sub.m to compute a genus-2 curve C.sub.m. Then, the encryption unit 212 sets the genus-2 curve C.sub.m as a ciphertext.

[0074] The encryption unit 212 transmits the ciphertext to the decryption device 30 via the communication interface 24.

[0075] Referring to FIG. 10, operation of the decryption device 30 according to the first embodiment will be described.

[0076] A procedure for the operation of the decryption device 30 according to the first embodiment is equivalent to a decryption method according to the first embodiment. A program that realizes the operation of the decryption device 30 according to the first embodiment is equivalent to a decryption program according to the first embodiment.

[0077] (Step S311: Acquisition Process)

[0078] The acquisition unit 311 acquires the public parameter, and acquires the public key and the secret key generated by the key generation device 10. The acquisition unit 311 acquires the ciphertext generated by the encryption device 20.

The acquisition unit 311 writes the public parameter, the public key, the secret key, and the ciphertext in the memory 32.

[0079] (Step S312: Decryption Process)

[0080] The decryption unit 312 computes a Richelot isogeny φ.sub.m whose starting point is the genus-2 curve C.sub.s, which is the public key, acquired in step S311, and whose end point is the genus-2 curve C.sub.m, which is the ciphertext, acquired in step S311, based on the Richelot isogeny sequence φ.sub.s, which is the secret key, and the genus-2 curve C.sub.0, which is the public key, acquired in step S311. Then, the decryption unit 312 decodes the Richelot isogeny φ.sub.m to compute a plaintext m′=m. This decoding is the inverse operation of the encoding performed in step S212.

[0081] The decryption unit 312 outputs the plaintext m′ via the communication interface 14.

Effects of the First Embodiment

[0082] As described above, the cryptographic system 1 according to the first embodiment realizes the genus-2 SETA cryptographic scheme by replacing the elliptic curves E.sub.0, E.sub.s, and E.sub.m in the SETA encryption scheme with the genus-2 curves C.sub.0, C.sub.s, and C.sub.m, and replacing the isogeny sequences φ.sub.s and φ.sub.m with the Richelot isogeny sequences φ.sub.s and φ.sub.m.

In the genus-2 SETA cryptographic scheme, the value of the prime number p used in the SETA encryption scheme can be reduced to ⅓. As a result, the time required for decryption can be reduced.

[0083] ***Other Configurations***

[0084] <First Variation>

[0085] In the first embodiment, the case where the genus-2 curves C.sub.0, C.sub.s, and C.sub.m are used has been described. However, the genus-2 curves C.sub.0, C.sub.s, and C.sub.m used by the cryptographic system 1 according to the first embodiment can be interpreted as abelian surfaces A.sub.0, A.sub.s, and A.sub.m. That is, a cryptographic scheme having substantially the same effects as those of the genus-2 SETA cryptographic scheme can be realized by replacing the elliptic curves E.sub.0, E.sub.s, and E.sub.m in the SETA encryption scheme with the abelian surfaces A.sub.0, A.sub.s, and A.sub.m, respectively, and replacing the isogeny sequences φ.sub.s and φ.sub.m with the Richelot isogeny sequences φ.sub.s and φ.sub.m, respectively.

[0086] When a genus-2 curve is used as in the first embodiment, it is desirable that the genus-2 curve be the genus-2 curve corresponding to a portion adjacent to a portion decomposed into the direct product of the elliptic curve E.sub.0 out of portions not decomposed into the direct product of the elliptic curve E.sub.0 in the abelian surface.

[0087] When a genus-2 curve is not used, it is desirable that a portion decomposed into the direct product of the elliptic curve be used.

[0088] The elliptic curve E.sub.0 used in the direct product of the elliptic curve that decomposes the abelian surface is E.sub.0/F.sub.p:y.sup.2=x.sup.3+x when the remainder of dividing the prime number p by 4 is 3, or E.sub.0/F.sub.p:y.sup.2=x.sup.3+c when the remainder of dividing the prime number p by 4 is 1, where c is a constant. Note that F.sub.p is a field modulo the prime number p.

[0089] <Second Variation>

[0090] In the first embodiment, the functional components are realized by software. As a second variation, the functional components may be realized by hardware. With regard to this second variation, differences from the first embodiment will be described.

[0091] Referring to FIG. 11, a configuration of the key generation device 10 according to the second variation will be described.

[0092] When the functional components are realized by hardware, the key generation device 10 includes an electronic circuit 15 in place of the processor 11, the memory 12, and the storage 13. The electronic circuit 15 is a dedicated circuit that realizes the functions of the functional components, the memory 12, and the storage 13.

[0093] Referring to FIG. 12, a configuration of the encryption device 20 according to the second variation will be described.

When the functional components are realized by hardware, the encryption device 20 includes an electronic circuit 25 in place of the processor 21, the memory 22, and the storage 23. The electronic circuit 25 is a dedicated circuit that realizes the functions of the functional components, the memory 22, and the storage 23.

[0094] Referring to FIG. 13, a configuration of the decryption device 30 according to the second variation will be described.

When the functional components are realized by hardware, the decryption device 30 includes an electronic circuit 35 in place of the processor 31, the memory 32, and the storage 33. The electronic circuit 35 is a dedicated circuit that realizes the functions of the functional components, the memory 32, and the storage 33.

[0095] Each of the electronic circuits 15, 25, and 35 is assumed to be a single circuit, a composite circuit, a programmed processor, a parallel-programmed processor, a logic IC, a gate array (GA), an application specific integrated circuit (ASIC), or a field-programmable gate array (FPGA).

[0096] The functional components may be realized by one electronic circuit 15, one electronic circuit 25, and one electronic circuit 35, or the functional components may be distributed among and realized by a plurality of electronic circuits 15, a plurality of electronic circuits 25, and a plurality of electronic circuits 35.

[0097] <Third Variation>

[0098] As a third variation, some of the functional components may be realized by hardware, and the rest of the functional components may be realized by software.

[0099] Each of the processors 11, 21, 31, the memories 12, 22, 32, the storages 13, 23, 33, the electronic circuits 15, 25, and 35 is referred to as processing circuitry. That is, the functions of the functional components are realized by the processing circuitry.

[0100] The embodiment and variations of the present disclosure have been described above. Two or more of these embodiment and variations may be implemented in combination. Alternatively, one or more of them may be partially implemented. The present disclosure is not limited to the above embodiment and variations, and various modifications can be made as needed.

REFERENCE SIGNS LIST

[0101] 1: cryptographic system, 10: key generation device, 11: processor, 12: memory, 13: storage, 14: communication interface, 15: electronic circuit, 111: acquisition unit, 112: map computation unit, 113: key setting unit, 20: encryption device, 21: processor, 22: memory, 23: storage, 24: communication interface, 25: electronic circuit, 211: acquisition unit, 212: encryption unit, 30: decryption device, 31: processor, 32: memory, 33: storage, 34: communication interface, 35: electronic circuit, 311: acquisition unit, 312: decryption unit.