Method and system for computing large-degree isogenies with an odd degree

Abstract

A computer-implemented method and system for computing large-degree isogenies of a base degree raised to a power of form .sup.ak+b and including the steps of providing at least one computer processor resident on an electronic computing device, performing, with the at least one processor, a large-degree isogeny by chaining together a plurality of scalar point multiplications, a plurality of isogeny computations, and a plurality of isogeny evaluations, wherein the large-degree isogeny includes a sequence storing at least one pivot point computed by one of the plurality of scalar point multiplications followed by an isogeny computation of degree .sup.b, performing at least one of the plurality of isogeny evaluations following one of the plurality isogeny computations, and performing an .sup.ak-isogeny through another sequence of .sup.a isogeny computations.

Claims

1. A computer-implemented method for computing large-degree isogenies of a base degree raised to a power of form .sup.ak+b, where a, b, and c are integers with 0<b<a, comprising the steps of: providing at least one hardware computer processor resident on an electronic computing device and operably configured to execute a sequence of computer readable instructions programmed to reduce computations when computing large-degree isogenies; performing with the at least one hardware computer processor and through execution of the sequence of computer readable instructions, a large-degree isogeny of a base degree raised to a power of form .sup.ak+b, where a, b, and c are integers with 0<b<a, by chaining together a plurality of scalar point multiplications, a plurality of isogeny computations, and a plurality of isogeny evaluations, wherein the large-degree isogeny includes a sequence storing, inside the electronic computing device, at least one pivot point computed by one of the plurality of scalar point multiplications followed by an isogeny computation of degree .sup.b; performing, with the at least one hardware computer processor and through execution of the sequence of computer readable instructions, at least one of the plurality of isogeny evaluations following one of the plurality isogeny computations; and performing with the at least one hardware computer processor and through execution of the sequence of computer readable instructions, an .sup.ak-isogeny through another sequence of .sup.a isogeny computations.

2. The computer-implemented method according to claim 1, wherein the large-degree isogeny further comprises: storing the at least one pivot point computed by one of the plurality of scalar point multiplications followed by the isogeny computation of a degree .sup.b and the plurality of isogeny evaluations.

3. The computer-implemented method according to claim 1, wherein: the base degree is a small prime number.

4. The computer-implemented method according to claim 1, wherein: the integer a is 2 and the integer b is 1, resulting in a large-degree isogeny of an odd degree.

5. The computer-implemented method according to claim 1, wherein: the large-degree isogeny is performed with arithmetic defined over a finite field of size that includes one of: 2.sup.2163.sup.137−1, 2.sup.2503.sup.159−1, 2.sup.3053.sup.192−1, 2.sup.3723.sup.239-1, or 2.sup.2733.sup.172-1.

6. The computer-implemented method according to claim 1, wherein: the large-degree isogeny is performed as part of an isogeny-based cryptosystem utilizing the hardware computer processor resident on the electronic computing device.

7. A computer-implemented method for computing large-degree isogenies of a base degree raised to a power of form .sup.ak+b, where a, b, and c are integers with 0<b<a, comprising the steps of: providing at least one hardware computer processor resident on an electronic computing device and operably configured to execute a sequence of computer readable instructions programmed to reduce computations when computing large-degree isogenies; performing a .sup.b scalar point multiplication to acquire a point of order .sup.ak; performing with the at least one hardware computer processor and through execution of the sequence of computer readable instructions, a .sup.ak isogeny by chaining together a plurality of scalar point multiplications, a plurality of isogeny computations, and a plurality of isogeny evaluations; performing with the at least one hardware computer processor and through execution of the sequence of computer readable instructions, at least one of the plurality of isogeny evaluations following one of the plurality isogeny computations; and performing with the at least one hardware computer processor and through execution of the sequence of computer readable instructions, an .sup.ak-isogeny through another sequence of .sup.a isogeny computations.

8. The computer-implemented method according to claim 7, wherein: the base degree is a small prime number.

9. The computer-implemented method according to claim 7, wherein: the integer a is 2 and the integer b is 1, resulting in a large-degree isogeny of an odd degree.

10. The computer-implemented method according to claim 7, wherein: the large-degree isogeny is performed with arithmetic defined over a finite field of size that includes one of: 2.sup.2163.sup.137−1, 2.sup.2503.sup.159−1, 2.sup.3053.sup.192−1, 2.sup.372 3.sup.239−1, 2.sup.1913.sup.172−1, or 2.sup.2733.sup.172−1.

11. The computer-implemented method according to claim 7, wherein: the large-degree isogeny is performed as part of an isogeny-based cryptosystem utilizing the hardware computer processor resident on the electronic computing device.

12. A computer processing system for computing large-degree isogenies of a base degree raised to a power of form .sup.ak+b, where a, b, and c are integers with 0<b<a and comprising: at least one hardware computer processor resident on an electronic computing device and operably configured to execute computer-readable instructions programmed to reduce computations when computing large-degree isogenies and to perform: the large-degree isogeny of the base degree raised to the power of form .sup.ak+b where a, b, and c are integers with 0<b<a, by chaining together a plurality of scalar point multiplications, a plurality of isogeny computations, and a plurality of isogeny evaluations, wherein the large-degree isogeny includes a sequence storing at least one pivot point computed by one of the plurality of scalar point multiplications followed by an isogeny computation of degree .sup.b; at least one of the plurality of isogeny evaluations following one of the plurality isogeny computations; and an .sup.ak-isogeny through another sequence of .sup.a isogeny computations.

13. The computer processing system according to claim 12, wherein the large-degree isogeny further comprises: storing the at least one pivot point computed by one of the plurality of scalar point multiplications followed by the isogeny computation of a degree .sup.b and the plurality of isogeny evaluations.

14. The computer processing system according to claim 12, wherein: the base degree is a small prime number.

15. The computer processing system according to claim 12, wherein: The integer a is 2 and the integer b is 1, resulting in a large-degree isogeny of an odd degree.

16. The computer processing system according to claim 12, wherein: the large-degree isogeny is performed with arithmetic defined over a finite field of size that includes one of: 2.sup.2163.sup.137−1, 2.sup.2503.sup.159−1, 2.sup.3053.sup.192−1, 2.sup.3723.sup.239−1, 21913172−1, or 2.sup.2733.sup.172−1.

17. The computer processing system according to claim 12, wherein: the large-degree isogeny is performed as part of an isogeny-based cryptosystem utilizing the hardware computer processor resident on the electronic computing device.

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 diagram depicting a directed acyclic graph for visualizing the large-degree isogeny computation. Starting from a root node, the goal is to traverse to the leaf nodes to compute an isogeny where there is a cost to move left or right. Small nodes have an odd order and medium nodes have an even order;

(3) FIG. 2 is a diagram depicting a directed acyclic graph where the large-degree isogeny is of an even order. This shows one state-of-the-art approach for computing the large-degree isogeny as a chain of a base degree () isogenies;

(4) FIG. 3 is a diagram depicting a directed acyclic graph where the large-degree isogeny is of an even order. This shows one state-of-the-art approach for computing the large-degree isogeny as a chain of a base degree squared (.sup.2) isogenies;

(5) FIG. 4 is a diagram depicting the state-of-the-art method for computing the isogeny problem when the large-degree isogeny is of an odd order. The state-of-the-art approach is to compute a single () small isogeny, then continue performing the rest of the large-degree isogeny as medium (.sup.2) isogenies;

(6) FIG. 5 is a diagram depicting one embodiment of the invention where specific pivot points are stored as the first small () isogeny is computed, for efficient use when computing the large-degree isogeny as medium (.sup.2) isogenies;

(7) FIG. 6 is a diagram depicting one embodiment of the invention where the small () isogeny is delayed until the final isogeny, such that the large-degree isogeny can be constructed by a sequence of medium (.sup.2) isogenies and then the final () isogeny;

(8) FIG. 7 is a schematic depicting an architecture for this invention, namely that upon receiving inputs for a large-degree isogeny of the form .sup.ak+b will execute a sequence of computer readable instructions and store at least one pivot point to perform the large-degree isogeny;

(9) FIG. 8 is a schematic depicting an architecture for this invention, namely a computer processor resident on an electronic computing device operably configured to compute a large-degree isogeny of an odd degree φ: E.sub.0.fwdarw.E.sub.0/R by using some sequence of and .sup.2 isogeny and point multiplication operations;

(10) FIG. 9 is a process-flow diagram depicting a computer-implemented method for computing large-degree isogenies of a base degree raised to a power of form .sup.ak+b in accordance with one embodiment of the present invention.

DETAILED DESCRIPTION

(11) 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.

(12) The present invention provides a hardware, system, implementation, and method for efficiently computing large-degree isogenies with an odd degree. The primary known application for these large-degree isogenies is for isogeny-based cryptosystems. Isogeny-based cryptosystems have been shown to be useful for a key establishment and authentication schemes. Among these, isogenies of elliptic curves have additionally been found to be the most useful and successful. An isogeny can be thought of as a mapping between elliptic curves that preserves the point at infinity. For security and efficiency, isogeny-based cryptosystems typically utilize a large-degree isogeny that is composed of many small-degree isogenies. This invention provides a new method to perform large-degree isogenies that are composed of an odd number of small-degree isogenies by grouping them into medium-degree isogenies with a remainder. This new method is more efficient in that it requires fewer computations.

(13) Examples of isogeny-based cryptosystems include, but are not limited to, the supersingular isogeny Diffie-Hellman (SIDH) key exchange, the commutative supersingular isogeny Diffie-Hellman (CSIDH) key exchange, the supersingular isogeny key encapsulation (SIKE) mechanism, and the short quaternion and isogeny signature (SQISign). The computational conjecture of these schemes is that it is easy to compute an isogeny φ between two elliptic curves given a kernel, but it is difficult to find the isogeny between two elliptic curves. Of these, this invention applies to the large-degree isogeny used in SIDH and SIKE when the large-degree isogeny is composed of medium-sized isogenies with some remainder.

(14) An elliptic curve isogeny φ: E.fwdarw.E′ over a finite field F.sub.q is defined as a non-constant rational map from E(F.sub.q) to E′(F.sub.q) that preserves the point at infinity. This is a mapping of points from one elliptic curve to another that changes the elliptic curve's isomorphism class. A unique isogeny can be computed by Velu's formulas over a kernel, φ: E.fwdarw.E/kernel. The degree of an isogeny is its degree as a rational map. Bigger degree isogenies are generally more computationally expensive. An isogeny computation is a mapping from elliptic curve to an isogenous elliptic curve. An isogeny evaluation is a mapping from a point on an elliptic curve to the corresponding point on an isogenous elliptic curve.

(15) For efficiency, SIDH and SIKE make use of primes of the form .sub.a.sup.e.sup.a.sub.b.sup.e.sup.bf±1, where .sub.a and .sub.b are small primes and f is chosen to make the number prime. For a key establishment session between Alice and Bob, Alice computes the large-degree isogeny .sub.a.sup.e.sup.a and Bob computes the large-degree isogeny .sub.b.sup.e.sup.b. For efficiency, these large-degree isogenies are computed as a chain of smaller isogenies. For instance, Alice will compute the large-degree isogeny .sub.a.sup.e.sup.a as an e.sub.a-length chain of .sub.a isogenies. This is the most intense computation in SIDH and SIKE and can be optimized. .sub.a and .sub.b are small primes to keep the scheme efficient. For instance, .sub.a=2 and .sub.b=3 are the most frequently used primes since they are the most efficient. A small prime is any prime integer less than 100. For example, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 are small primes.

(16) For simplicity, the base degree of an isogeny is given as . This is considered a “small” isogeny. A “medium” isogeny is an isogeny of the form .sup.x, where x>1. For instance, an .sup.2 isogeny is a medium isogeny. The “large-degree” isogeny is the full degree of the isogeny as needed for SIDH, SIKE, or any isogeny-based scheme. This is denoted as .sup.e. With these definitions, it is not required that x<e.

(17) Given a point R of order .sup.e, the large-degree isogeny tree problem is to compute the large-degree isogeny as efficiently as possible. Starting on curve E.sub.0 with kernel point R.sub.0 of order .sup.e, the large-degree isogeny can be computed iteratively by initializing E.sub.0=E and R.sub.0=R and then computing 0≤i<e iterations of degree- isogenies φ.sub.i: E.sub.1.fwdarw.E.sub.i+1 with kernel [.sup.e−i−1]R.sub.i, and then updating R.sub.i+1=φ.sub.i(R.sub.i). This computational problem can be visualized as a directed acyclic graph, similar to a binary tree, which is shown in FIG. 1. Here, we start at a root node which has order .sup.e. To traverse this graph, a point multiplication by moves to the left an -isogeny evaluation moves to the right. The goal is to compute an -isogeny at each of the leaf nodes which have an order of . Any number of pivot points, or strategic points can be stored and pushed through -isogenies to reduce the number of point multiplications and isogeny evaluations that are computed.

(18) A strategy is a sequence of point multiplications, isogeny evaluations, and isogeny computations that compute the .sup.e isogeny. There is no advantage to traversing each node. An optimal strategy is one of least cost. This optimal strategy depends on the relative cost of scalar point multiplication by and -degree isogeny evaluations. Pivot points are stored points that can reduce the cost of traversal but will require an -degree isogeny evaluation after each isogeny computation. The optimal strategy for a large tree can be found by combining the optimal strategy of both subtrees.

(19) In addition to computing a series off isogenies, there is also the option to compute .sup.x isogenies, where x is some integer. For instance, to compute the large-degree isogeny 2.sup.64, one can compute 64 2-isogenies or 32 4-isogenies. To compute a 4-isogeny, the isogeny tree strategy performs point multiplications or isogeny evaluations to get a point of order 4. An example of this is shown in FIG. 2.

(20) Here, the small nodes have an odd order and the medium nodes have an even order. The largest nodes at the bottom are the points of order 1. FIG. 2 illustrates a strategy that uses only -isogenies and FIG. 3 illustrates a strategy that uses only .sup.2-isogenies. These can be raised to a higher power. If .sup.2-isogenies or greater isogenies are more efficient to compute than -isogenies, then a more efficient strategy can be made that uses these higher power isogenies.

(21) FIGS. 2-3 both assume an even power for the isogeny. Another problem could have an odd power of the form .sup.2k+1 which could also be written as .sup.o.sup.2k. If .sup.2-isogenies are more efficient than -isogenies, then there are a few different ways to optimize this case for the isogeny tree problem. The state-of-the-art solution to this problem is to compute an initial -isogeny followed by a chain of .sup.2-isogenies according to a strategy, which is shown in FIG. 4. This method is wasteful. For instance, one 610-bit prime used in a parameter set for SIKE is of the form p=2.sup.3053.sup.192-1. The large-degree isogeny 2.sup.305 is computed by first performing a 2-isogeny and then an optimized strategy for computing 152 4-isogenies. This initial 2-isogeny costs 304 point doublings which must then be mostly recomputed for the following 4-isogenies.

(22) More generally, an efficient strategy can be constructed for a large-degree isogeny by composing it as a sequence of medium isogenies. In the example above, .sup.2-isogenies were used. As yet another example, consider computing a large-degree isogeny of .sup.24. One can compose this large-degree isogeny as a sequence of 24 -isogenies, 12 .sup.2-isogenies, 8 .sup.3-isogenies, 6 .sup.4-isogenies, 4 .sup.6-isogenies, 3 .sup.B-isogenies, 2 .sup.12-isogenies, or even 1 .sup.24-isogeny. Furthermore, this is not limited to one type of isogeny. Additional options include 3 .sup.3-isogenies with 3 .sup.5-isogenies or 2 .sup.2-isogenies with 2 .sup.4-isogenies and 1 .sup.2-isogeny. The only restriction is that the total number of isogenies adds up to the large-degree isogeny. When determining which strategy is best, the cost of these .sup.x-isogenies is taken into account.

(23) This invention proposes a new method to address this cost to efficiently compute large-degree isogenies aggregated with isogenies of mixed degree. The case here is when a medium degree isogeny is the most efficient and there is some remainder. In the odd power example with .sup.2k+1, the remainder was 1, so an additional -isogeny is required. More generally, the large-degree isogeny can be of the form .sup.ako.sup.b=.sup.ak+b, where .sup.a is the most efficient medium isogeny to compute, .sup.b is the remaining small or medium isogeny to perform with 0<b<a, and k is the number of medium isogenies to perform as part of the strategy. Our embodiments of the invention target this general case and use examples to further elaborate on the advantages of this innovation.

(24) The first embodiment of this invention is to start by performing the remainder .sup.b-isogeny while storing pivot points to avoid recomputing point multiplications for an optimal strategy to compute the chain of .sup.a-isogenies. This is illustrated in FIG. 5 for the case of an even power for the isogeny. The strategy dictates the first sequence of pivot points that are stored as the point of order .sup.2k is multiplied by .sup.2. Before the strategy is applied, a single -isogeny is computed over a point of order that is obtained by performing 2k point multiplications by . As these point multiplications are performed, points that have an order times that of the first sequence of pivot points are stored. After the first -isogeny is computed, an -isogeny evaluation is applied to these stored points that divides the point orders by , resulting in the first sequence of pivot points. The optimal strategy for the .sup.2-isogenies is then followed. For the large-degree isogeny 2.sup.305, this approach saves about 303 point doublings at the cost of applying 2-isogeny point evaluations to each pivot points. A simple estimate for an optimal strategy here may store 10 pivot points, so this exchanges 303 point doublings for 9 2-isogeny point evaluations, which is typically significantly more efficient.

(25) The second embodiment of this invention is to perform a strategy that involves a chain of medium-sized .sup.a-isogenies where at some step of the strategy the remainder .sup.b-isogeny is computed. Our example here is shown in FIG. 6 as a chain of .sup.2-isogenies where at some step of the strategy an -isogeny is computed. Here, the root point is of the order .sup.2k+1 so multiplying the point by will return a point of order .sup.2k that can be efficiently used to compute an .sup.2k large-degree isogeny by using a strategy. At some step of this strategy, the -isogeny can be computed. For example, this could be computed as the last isogeny in the chain or directly in the middle. Similar to the first embodiment, the use of a strategy here will exchange many point multiplications by for isogeny evaluations by . This use of a strategy could also be useful for applications where space is limited and only so many pivot points can be stored.

(26) The third embodiment of this invention is to perform an initial point multiplication by the remainder .sup.b followed by a strategy for the remaining .sup.a isogenies. The key idea here is that the point multiplication by .sup.b here is used to bypass the need to compute the final .sup.b-isogeny. Similar to embodiments 1 and 2, this embodiment saves a major amount of point multiplications by .sup.b that are needed to compute the .sup.b-isogeny. This embodiment is unique in that it does not perform the .sup.b-isogeny, saving additional -isogeny evaluations and a single .sup.b-isogeny computation. This is useful for some schemes where the remainder .sup.b-isogeny does not add security. For instance, SIDH and SIKE relies on schemes where .sub.a.sup.e.sup.a≈.sub.b.sup.e.sup.b so that the size, complexity, and security of the large-degree isogenies are similar. If one large-degree isogeny tree were much larger than the other, then computing an .sup.b-isogeny may not be necessary.

(27) Lastly, two architecture embodiments of this invention are shown in FIG. 7 and FIG. 8. In FIG. 7, a computer processing system is shown that is operably configured to perform a large-degree isogeny of the form .sup.ak+b, where a, b, and c are integers with 0<b<a. This large-degree computation is computed by the computer processing system executing a sequence of computer readable instructions that includes storing at least one pivot point, a point that is necessary for a large-degree isogeny strategy. Upon completion of the computation, the computer processing system outputs the large-degree isogeny results. Inside this computer processing system, .sup.x degree operations can be called, whether through specific accelerators or subroutines stored and used with a controller. For efficient use, the .sup.ak isogeny can be broken down into a highly optimized strategy of .sup.a isogenies that can be stored in the sequence of operations. At some point in this sequence, such as before, during, or after, the .sup.b isogeny can be called. To reduce the computational complexity, pivot points can be stored inside the computer processing system during the .sup.a or .sup.b operations.

(28) FIG. 8 is intended to illustrate more details of one such architecture, this time to execute a large-degree isogeny of an odd power where a=2 and b=1. Here, the inputs are a kernel point R of order .sup.2k+1, integers a, b, and k, and an input curve E.sub.0. This architecture computes the large-degree isogeny resulting in a new curve, φ: E.sub.0.fwdarw.E.sub.0/R. As is explained in the previous embodiments of this invention, this can efficiently be done by this computer processing system by using a sequence of -isogeny and .sup.2-operations, including evaluations, computations, and scalar point multiplications.

(29) With reference to FIG. 9, an exemplary computer-implemented method for computing large-degree isogenies of a base degree raised to a power of form .sup.ak+b is depicted, wherein the process starts at step 1000, and then immediately proceeds to the step 1002 of providing at least one computer processor resident on an electronic computing device. Step 1004 may include performing a .sup.b scalar point multiplication to acquire a point of order .sup.ak, wherein the next step 1006 may include performing with the at least one processor a .sup.ak isogeny by chaining together a plurality of scalar point multiplications, a plurality of isogeny computations, and a plurality of isogeny evaluations. Next, step 1008 includes performing with the at least one processor at least one of the plurality of isogeny evaluations following one of the plurality isogeny computations and step 1010 includes performing with the at least one processor an .sup.ak-isogeny through another sequence of .sup.a isogeny computations. The process may terminate at step 1012.