Architecture and method for hybrid isogeny-based cryptosystems

Abstract

At least one computer processor configured with a single prime field accelerator having software-based instructions operably configured to compute both isogeny-based cryptography equations and elliptic curve cryptography equations using a plurality of shared computations resident on a shared memory storage and that include finite field arithmetic and elliptic curve group arithmetic sequentially computed with an architecture controller.

Claims

1. A computer processing cryptosystem comprising: at least one computer processor configured as a one prime field accelerator having software-based computer readable instructions operably configured to compute, with the at least one computer processor, both isogeny-based cryptography equations and elliptic curve cryptography equations using a plurality of shared computations resident on a shared memory storage and that include finite field arithmetic and elliptic curve group arithmetic sequentially computed with an architecture controller.

2. The computer processing system according to claim 1, wherein the one prime field accelerator further comprises: at least one of a finite field accelerator or a curve group operation accelerator.

3. The computer processing system according to claim 1, wherein the one prime field accelerator is operably configured to compute equations over a prime field p=2.sup.2163.sup.137 −1 for isogenies and elliptic curves.

4. The computer processing system according to claim 3, further comprising: at least one of the following equations utilized in its isomorphism class for at least one of elliptic curves:
y.sup.2=x.sup.3+326750x.sup.2+x;
y.sup.2=x.sup.3+439322x.sup.2+x;
x.sup.2+y.sup.2=1+109831x.sup.2y.sup.2;
x.sup.2+y.sup.2=1−109830x.sup.2y.sup.2;
x.sup.2+y.sup.2=1+81688x.sup.2y.sup.2;
x.sup.2+y.sup.2=1−81687x.sup.2y.sup.2;
−x.sup.2+y.sup.2=1+109830x.sup.2y.sup.2;
−x.sup.2+y.sup.2=1-109831x.sup.2y.sup.2;
−x.sup.2+y.sup.2=1+81687x.sup.2y.sup.2; and
−x.sup.2+y.sup.2=1−81688x.sup.2y.sup.2.

5. The computer processing system according to claim 1, wherein the one prime field accelerator is operably configured to compute equations over a prime field p=2.sup.2503.sup.259−1 for isogenies and elliptic curves.

6. The computer processing system according to claim 5, further comprising: at least one of the following equations utilized in its isomorphism class for at least one of elliptic curves:
y.sup.2=x.sup.3+308290x.sup.2+x;
y.sup.2=x.sup.3+941678x.sup.2+x;
x.sup.2+y.sup.2=1+77073x.sup.2y.sup.2;
x.sup.2+y.sup.2=1−77072x.sup.2y.sup.2;
x.sup.2+y.sup.2=1+235420x.sup.2y.sup.2;
x.sup.2+y.sup.2=1−235419x.sup.2y.sup.2;
−x.sup.2+y.sup.2=1+77072x.sup.2y.sup.2;
−x.sup.2+y.sup.2=1−77073x.sup.2y.sup.2;
−x.sup.2+y.sup.2=1+235419x.sup.2y.sup.2; and
−x.sup.2+y.sup.2=1−235420x.sup.2y.sup.2.

7. The computer processing system according to claim 1, wherein the one prime field accelerator is operably configured to compute equations over a prime field p=2.sup.3053.sup.192 −1 for isogenies and elliptic curves.

8. The computer processing system according to claim 6, further comprising: at least one of the following equations utilized in its isomorphism class for at least one of elliptic curves:
y.sup.2=x.sup.3+1135802x.sup.2+x;
y.sup.2=x.sup.3+975094x.sup.2+x;
x.sup.2+y.sup.2=1+283951x.sup.2y.sup.2;
x.sup.2+y.sup.2=1−283950x.sup.2y.sup.2;
x.sup.2+y.sup.2=1+243774x.sup.2y.sup.2;
x.sup.2+y.sup.2=1−243773x.sup.2y.sup.2;
−x.sup.2+y.sup.2=1+283950x.sup.2y.sup.2;
−x.sup.2+y.sup.2=1−283951x.sup.2y.sup.2;
−x.sup.2+y.sup.2=1+243773x.sup.2y.sup.2; and
−x.sup.2+y.sup.2=1−243774x.sup.2y.sup.2.

9. The computer processing system according to claim 1, wherein the one prime field accelerator is operably configured to compute equations over a prime field p=2.sup.3723.sup.239−1 for isogenies and elliptic curves.

10. The computer processing system according to claim 9, further comprising: at least one of the following equations utilized in its isomorphism class for at least one of elliptic curves:
y.sup.2=x.sup.3+749726x.sup.2+x;
y.sup.2=x.sup.3+624450x.sup.2+x;
x.sup.2+y.sup.2=1+156113x.sup.2y.sup.2
x.sup.2+y.sup.2=1−156112x.sup.2y.sup.2;
x.sup.2+y.sup.2=1+187432x.sup.2y.sup.2;
x.sup.2+y.sup.2=1−187431x.sup.2y.sup.2;
−x.sup.2+y.sup.2=1+156112x.sup.2y.sup.2;
−y.sup.2=1−156113x.sup.2y.sup.2;
−x.sup.2+y.sup.2=1+187431x.sup.2y.sup.2; and
−x.sup.2+y.sup.2=1−187432x.sup.2y.sup.2.

11. A computer-implemented method for implementing both isogeny-based and elliptic curve cryptography equations in a computer processing cryptosystem comprising the steps of: providing at least one hardware computer processor configured as one prime field accelerator having software-based computer readable instructions operably configured to compute, with the at least one hardware computer processor, both isogeny-based cryptography equations and elliptic curve cryptography equations and providing a shared memory storage and an architecture controller; and initiating, through the least one hardware computer processor, a cryptography session that includes: utilizing the one prime field accelerator to accelerate and compute both isogeny-based cryptography equations and elliptic curve cryptography equations using a plurality of shared computations resident on the shared memory storage to generate finite field arithmetic and elliptic curve group arithmetic sequentially computed with the architecture controller.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The accompanying figures, where like reference numerals refer to identical or functionally similar elements throughout the separate views and which together with the detailed description below are incorporated in and form part of the specification, serve to further illustrate various embodiments and explain various principles and advantages all in accordance with the present invention.

(2) FIG. 1 is a schematic diagram depicting hierarchy of computations utilized in isogeny-based cryptography and elliptic curve cryptography in accordance with one embodiment of the present invention;

(3) FIG. 2 is a schematic diagram depicting an instantiated form of the invention where an isogeny and elliptic curve computer processor share a prime or finite field accelerator, storage, and controller in accordance with one embodiment of the present invention;

(4) FIG. 3 is a schematic diagram depicting an instantiated form of the invention where an isogeny and elliptic curve computer processor share an elliptic curve group operation accelerator, storage, and controller in accordance with one embodiment of the present invention; and

(5) FIG. 4 depicts a process flow diagram of a method for implementing both isogeny-based and elliptic curve cryptography equations in a computer processing cryptosystem in accordance with one embodiment of the present invention.

DETAILED DESCRIPTION

(6) While the specification concludes with claims defining the features of the invention that are regarded as novel, it is believed that the invention will be better understood from a consideration of the following description in conjunction with the drawing figures, in which like reference numerals are carried forward. It is to be understood that the disclosed embodiments are merely exemplary of the invention, which can be embodied in various forms.

(7) The present invention provides a novel and efficient hardware, system, and method solution that is operably configured to implement cryptosystems based on isogenies as well as cryptosystems based on elliptic curves. More specifically, by using a shared accelerator for low-level computations that are shared in these two types of cryptosystems, we can efficiently implement both cryptosystems. An accelerator may be a processing device or processor specifically configured to perform computationally intensive cryptographic operations. As is shown in FIG. 1, there are shared computations that are native to both isogeny-based cryptography and elliptic curve cryptography.

(8) However, in order to effectively reuse computation accelerators in both cryptosystems, specific parameters must be selected so that the underlying cryptographic problem is hard. The spirit of this invention is that good choices of public key parameters allow one to reuse a single computation accelerator for both isogeny-based cryptosystems and elliptic curve-based cryptosystems. Specifically, the shared use of finite field arithmetic 102 (possibly referred to as “low level”) and elliptic curve group arithmetic 104 (possibly referred to as “mid level”). The finite field computations or computations 102 may include modular addition and modular multiplication as seen in FIG. 1 and as further expanded upon herein. The elliptic curve group arithmetic or computations 104 may include scalar point multiplication and isogeny and isomorphisms as seen in FIG. 1 and as further expanded upon herein. Further, the elliptic curve computations/isogeny-based protocols 106 (possibly referred to as “top level”) depicted in the schematic diagram depicting hierarchy of computations may include SIDH, SIKE, EdDSA, and ECDH

(9) Public-key cryptography is the study of exchanging secrets over an insecure public channel. By using hard problems such as the discrete logarithm problem or isogeny problem, data confidentiality, data integrity, authentication, and non-repudiation can be achieved. Given today's technology and future advances, the computational infeasibility of these hard problems means that it will be thousands or many orders of magnitudes of years to break the cryptosystem. The primary cryptosystem primitives we describe in the following are public key exchange, whereby two parties agree on a shared secret over an insecure channel and digital signature where one party digitally signs content with his private key and any other party can digitally verify this signed content with the public key associated with the signer's private key. Other primitives exist, such as authenticated key exchange, public key encryption, and zero-knowledge proofs. In the following, we will describe an instantiation of our invention given known isogeny and elliptic curve cryptosystems. The spirit of the invention is not limited to such an example but expands to any future simultaneous deployment of isogeny and elliptic curve cryptosystems.

(10) Isogeny-based cryptography is cryptography based on isogenies, or algebraic morphisms that are surjective and have a finite kernel, among a group. In modern-day cryptography, isogenies on elliptic curve groups is thought to be a hard problem, even for quantum computers. As those of skill in the art will appreciate, an isogeny on elliptic curves φ: E.sub.1.fwdarw.E.sub.2 is a non-rational map of all points on E.sub.1 to E.sub.2 that preserves the point at infinity. Given a finite kernel and E.sub.1, it is simple to compute E.sub.2, the isogeny of E.sub.1 using the finite kernel. However, given only E.sub.1 and E.sub.2, it is a computationally intensive task to compute the finite kernel used for the isogeny from E.sub.1 to E.sub.2, which is the foundation of isogeny-based cryptography. Some examples of isogeny-based cryptography include, but not limited to, the supersingular isogeny Diffie-Hellman (“SIDH”) key exchange protocol, commutative supersingular isogeny Diffie-Hellman (“CSIDH”) key exchange protocol, supersingular isogeny key encapsulation (“SIKE”) mechanism, and SeaSign isogeny signatures. Each of these are isogeny-based cryptosystems that are based on the hardness of isogenies on elliptic curves. The cryptosystem parameters differ in many ways. However, efficient implementation of these cryptosystems depends on wise choices of prime field F.sub.q and elliptic curve E defined over F.sub.q.

(11) One embodiment of this invention is an SIDH implementation that is used for key establishment. As those skilled in the art will appreciate, SIDH utilizes mappings from a base elliptic curve E.sub.0 defined over F.sub.p.sub.2, where p is a large prime number, to a final curve E.sub.ss where the curve's j-invariant is used as a shared secret. For efficient implementation of SIDH, it is generally recommended that p is of the form p=fl.sub.a.sup.e.sup.al.sub.b.sup.e.sup.b±1, where l.sub.a and l.sub.b are small primes, usually, for example, l.sub.a=2, l.sub.b=3, l.sub.a.sup.e.sup.al.sub.b.sup.e.sup.b, and f is a small cofactor, usually f=1, to make the number prime. This prime shape and choice of supersingular curve E.sub.0 allows efficient chaining of small isogenies of degree 2 and 3 as the cardinality of the curve is #E.sub.0=(fl.sub.a.sup.e.sup.al.sub.b.sup.e.sup.b).sup.2. The full implementation of isogeny arithmetic in SIDH requires a mixture of finite field operations that compose elliptic curve and isogeny group operations.

(12) Elliptic curve cryptography is cryptography based on the hardness of the elliptic curve discrete logarithm problem. Roughly, given an elliptic curve E defined over a prime field F.sub.p, point P∈E, and scalar k, it is simple to compute the scalar point multiplication Q=kP. However, given only P, Q∈E, it is difficult to find the scalar that generated Q. Here, one elliptic curve is used as a basis for a number of elliptic curve group operations. Elliptic curve cryptography can be defined over either a binary finite field or prime finite field. Like isogeny-based cryptography, the choice of underlying finite field and elliptic curve can greatly reduce or increase the efficiency of an elliptic curve cryptosystem implementation. Furthermore, there are various parameters of the elliptic curve that can influence the hardness of the elliptic curve discrete logarithm problem. Some examples of elliptic curve cryptography primitives include, but not limited to, elliptic curve Diffie-Hellman (“ECDH”), elliptic curve digital signature algorithm (“ECDSA”), Edwards curve digital signature algorithm (“EdDSA”), and elliptic curve password authenticated key exchange by juggling (“ECJPAKE”).

(13) Considering this, wise choices of prime field and elliptic curves can be used to simultaneously implement both isogeny on elliptic curves and elliptic curve cryptography securely. In the following, we demonstrate an instantiation of this invention with two examples. In the first example, we introduce parameters for simultaneous implementation of SIDH and ECDH. In the second example, we introduce parameters for simultaneous implementation of SIDH and EdDSA.

(14) In the choice of SIDH parameters, the choice of prime p is necessary for smooth evaluation of isogenies of a small degree. This prime must be of the form p=fl.sub.a.sup.e.sup.al.sub.b.sup.e.sup.b±1 or else the performance will greatly suffer. In this example, we consider the 434-bit prime p.sub.434=2.sup.2163.sup.137−1. For SIDH, we can define a base curve over this prime field as the Montgomery supersingular elliptic curve y.sup.2=x.sup.3+6x.sup.2+x. This starting curve has a j-invariant equal to 287496. Given these parameters, we can implement efficient accelerators at the prime field (FIG. 2) or elliptic curve group operation (FIG. 3) level.

(15) Given the isogeny on elliptic curve parameters, an efficient choice of elliptic curve can be defined that uses the same prime field and elliptic curve group operation accelerator. As those knowledgeable in the art will appreciate, the elliptic curve used for SIDH is weak to discrete-logarithm attacks such as the Pohlig-Hellman algorithm. Instead of a supersingular elliptic curve, an ordinary curve over F.sub.p can be chosen such that the elliptic curve has a hard elliptic curve discrete logarithm problem. One such curve is the Montgomery elliptic curve y.sup.2=x.sup.3+439322x.sup.2+x defined over F.sub.p. There are a number of strengths to this curve. Notably, the cardinality of this curve and any twist is 4*n, where n is a large prime number. Also a security strength, the Pollard Rho attack on this elliptic curve would take approximately 2.sup.214.9 operations. For efficiency, this curve is defined over Montgomery curves which is useful for ECDH operations as the efficient and simple Montgomery ladder can be used. Furthermore, the curve coefficient A=439322 was chosen such that the value

(16) $A_{24}=\frac{A+2}{4}=109831$
is also small as it is used in the Montgomery ladder. This is only a small listing of the benefits of this curve as those familiar with the art can appreciate.

(17) The above Montgomery curve can be used in ECDH such as by the methods defined in RFC 7748. Here, we choose the point (u,v)=(0x4,0xc4dd1c159565600641e9b2cb3b102229afb64318044a6ffcbc6545c24 0665b0fd59985cd03e9a130afb8291825436f66c69f73c6251d), which has a prime order. Similar to the methods for X25519 and X448 in RFC 7748, we can generate a private key by gathering 55 bytes of random data, clearing bits 0, 1, 434, 435, 436, 437, 438, and 439, and setting bit 433 for a pruned private key k. We then use this private key with the Montgomery ladder to generate a public key. In the second round, we again apply this private key and Montgomery ladder to the other party's public key to compute a shared secret for key establishment.

(18) Another example is applying the same prime to an EdDSA cryptosystem to digitally sign and verify messages. Here, we use an Edwards curve with similar properties as the defined Montgomery curve for ECDH and apply the methodology of EdDSA as defined in RFC 8032. One such example is the twisted Edwards elliptic curve x.sup.2+y.sup.2=1+109831x.sup.2y.sup.2, also defined over p.sub.434=2.sup.2163.sup.137−1. This elliptic curve features the smallest d coefficient where the cardinality of the curve and any twist is 4*n, where n is a large prime number. Without going into many details, we again use efficient elliptic curve operations to carry out the EdDSA protocol, this time over an Edwards curve.

(19) The computations in both examples can be broken down into arithmetic over a prime field F.sub.q, or arithmetic modulo a prime field q. In the SIDH example, q=p.sup.2 and ECDH/EdDSA both use q=p. In both cases, we can reuse a finite field accelerator that computes various operations modulo p for both SIDH and ECDH/EdDSA. Thus, we can reuse the finite field accelerator between implementations (FIG. 2).

(20) At the next level, both examples utilize group actions over elliptic curves. For instance, both SIDH and ECDH utilize scalar point multiplications over Montgomery curves. Although the base curve is not the same, the Montgomery curve point multiplication is the same in both cases. Thus, we can reuse the elliptic curve group accelerator between implementations (FIG. 3).

(21) As such, the FIGS. 1-3 can be seen depicting at least one computer processor (e.g., processors 200, 300) configured as a one prime field accelerator (e.g., accelerators 202, 302) having software-based instructions operably configured to compute both isogeny-based cryptography equations and elliptic curve cryptography equations using a plurality of shared computations resident on a shared memory storage (e.g., memories 204, 304) and that include finite field arithmetic and elliptic curve group arithmetic 102, 104 sequentially computed with an architecture controller (e.g., controllers 206, 306). Said another way, an accelerator desired to make computations extremely fast. For finite fields, the accelerator makes finite field computations (such as addition or multiplication) really fast. In some cases, however, the finite field accelerator only operates over a single prime field, so the present invention targets places where the same prime field is used for elliptic and isogeny computations.

(22) A method for implementing both isogeny-based and elliptic curve cryptography equations in a computer processing cryptosystem has also been disclosed herein and can be gleaned from the figures. More specifically, and with reference to FIG. 4, the process may begin with step 400 and immediately proceed to the step 402 of providing at least one computer processor configured as one prime field accelerator having software-based instructions operably configured to compute both isogeny-based cryptography equations and elliptic curve cryptography equations and providing a shared memory storage and an architecture controller. Next, the process may include step 404 of initiating, through the least one computer processor, a cryptography session that includes utilizing the one prime field accelerator to accelerate (i.e., a specialized accelerator that requires generally far less power, time, etc., to compute the computation) and compute both isogeny-based cryptography equations and elliptic curve cryptography equations using a plurality of shared computations resident on the shared memory storage to generate finite field arithmetic and elliptic curve group arithmetic sequentially computed with the architecture controller. Said another way, the one prime field accelerator may include a finite field accelerator and/or a curve group operation accelerator. As such, an accelerator may be utilized for prime fields and issue a variety of operations over that. In another embodiment, an accelerator for elliptic curve operations may be utilized and again issue a variety of operations over that. Depending on the system in question, however, both a finite field and an elliptic curve accelerator could be utilized. The process may conclude in step 406.

(23) Although a specific order of executing the process steps has been described, the order of executing the steps may be changed relative to the order shown in certain embodiments. Also, two or more steps shown in succession may be executed concurrently or with partial concurrence in some embodiments. Certain steps may also be omitted for the sake of brevity. In some embodiments, some or all of the process steps included can be combined into a single process.