Elliptic curve isogeny-based cryptographic scheme

Abstract

Elliptic curve cryptographic schemes performed between a pair of cryptographic correspondent computing devices. In an aspect, a first entity generates a first basis point in a first selected basis being, either a first basis (A) or a second basis (B), and performs a first key generation in the selected basis. A second entity receives the public key and determines the product of a predetermined scalar in a second selected basis being either the first basis (A) or the second basis (B) and one of the first auxiliary points. If the product is an identity point, performs second key generation in the second selected basis, otherwise performing second key generation in either of the first basis (A) or the second basis (B). A common key is generated using the private keys and public keys. In another aspect, a scheme is performed symmetrically between two entities to generate a common key.

Claims

1. An elliptic curve cryptographic scheme performed between a first entity on a first computing device and a second entity on a second computing device communicating over a data communication system, the cryptographic scheme comprising: performing, by the first entity: selecting a first selected basis being either a first basis or a second basis; performing first key generation with respect to the first selected basis to generate a first private key and a first public key; and communicating the first public key to the second entity; performing, by the second entity: determining if a linear combination, in a second selected basis being either the first basis or the second basis, is an identity point; performing second key generation with respect to the first basis if the scalar multiplication product is the identity point, otherwise performing second key generation with respect to the second basis, the second key generation generating a second private key and a second public key; and communicating a second public key to the first entity; performing, by the first entity: generating a common key by combining the first private key and the second public key; and performing, by the second entity: generating a common key by combining the second private key and the first public key.

2. The elliptic curve cryptographic scheme of claim 1, wherein first key generation comprises: generating a first private key; and generating a cryptographic corresponding first public key comprising a first elliptic curve and first auxiliary points; and wherein second key generation comprises: generating a second private key; and generating a cryptographic corresponding second public key comprising a second elliptic curve and second auxiliary points.

3. The elliptic curve cryptographic scheme of claim 2, wherein determining the linear combination comprises determining a scalar multiplication product of a predetermined scalar in the second selected basis and one of the first auxiliary points.

4. The elliptic curve cryptographic scheme of claim 2, wherein determining the linear combination comprises determining a scalar multiplication product of a predetermined scalar in the first selected basis and one of the first auxiliary points.

5. The elliptic curve cryptographic scheme of claim 2, wherein determining the linear combination comprises determining a scalar multiplication product of a predetermined scalar in the first selected basis, a predetermined scalar in the second selected basis, and one of the first auxiliary points.

6. The elliptic curve cryptographic scheme of claim 5, further comprising determining whether the values of the first public key are in the correct domain by determining that such values are in defined torsion subgroups.

7. The elliptic curve cryptographic scheme of claim 2, wherein determining the linear combination comprises determining a sum of a first private scalar multiplied by the first auxiliary point and a second private scalar multiplied by the second auxiliary point.

8. A cryptographic correspondent device comprising a processor and a memory, the cryptographic correspondent device in communication with an other cryptographic correspondent device over a data communication system, the memory having stored thereon computer instructions which when executed by the processor cause the processor to implement a elliptic curve cryptographic scheme comprising: receiving, from the other cryptographic correspondent device, a first public key, the other cryptographic correspondent device having selected a first selected basis being either a first basis or a second basis, and the other cryptographic correspondent device having performed first key generation with respect to the first selected basis to generate a first private key and the first public key; determining if a linear combination, in a second selected basis being either the first basis or the second basis, is an identity point; performing second key generation with respect to the first basis if the scalar multiplication product is the identity point, otherwise performing second key generation with respect to the second basis, the second key generation generating a second private key and a second public key; communicating the second public key to the other cryptographic correspondent device; and generating a common key by combining the second private key and the first public key.

9. The cryptographic correspondent device of claim 8, wherein first key generation comprises: generating a first private key; and generating a cryptographic corresponding first public key comprising a first elliptic curve and first auxiliary points; and wherein second key generation comprises: generating a second private key; and generating a cryptographic corresponding second public key comprising a second elliptic curve and second auxiliary points.

10. The cryptographic correspondent device of claim 9, wherein determining the linear combination comprises determining a scalar multiplication product of a predetermined scalar in the second selected basis and one of the first auxiliary points.

11. The cryptographic correspondent device of claim 9, wherein determining the linear combination comprises determining a scalar multiplication product of a predetermined scalar in the first selected basis and one of the first auxiliary points.

12. The cryptographic correspondent device of claim 9, wherein determining the linear combination comprises determining a scalar multiplication product of a predetermined scalar in the first selected basis, a predetermined scalar in the second selected basis, and one of the first auxiliary points.

13. The cryptographic correspondent device of claim 12, further comprising determining whether the values of the first public key are in the correct domain by determining that such values are in defined torsion subgroups.

14. The cryptographic correspondent device of claim 9, wherein determining the linear combination comprises determining a sum of a first private scalar multiplied by the first auxiliary point and a second private scalar multiplied by the second auxiliary point.

Description

DESCRIPTION OF THE DRAWINGS

(1) An embodiment of the present invention will now be described by way of example only with reference to the accompanying drawings, in which:

(2) FIG. 1 is a schematic representation of a data communication system;

(3) FIG. 2 is a representation of a device used in the data communication system of FIG. 1;

(4) FIG. 3 is a chart showing facets of an isogeny-based elliptic curve cryptographic protocol;

(5) FIG. 4 is a flow chart showing a supersingular elliptic curve cryptographic scheme according to an embodiment; and

(6) FIG. 5 is a flow chart showing a supersingular elliptic curve cryptographic scheme according to another embodiment.

DETAILED DESCRIPTION

(7) Embodiments will now be described with reference to the figures. It will be appreciated that for simplicity and clarity of illustration, where considered appropriate, reference numerals may be repeated among the figures to indicate corresponding or analogous elements. In addition, numerous specific details are set forth in order to provide a thorough understanding of the embodiments described herein. However, it will be understood by those of ordinary skill in the art that the embodiments described herein may be practiced without these specific details. In other instances, well-known methods, procedures and components have not been described in detail so as not to obscure the embodiments described herein. Also, the description is not to be considered as limiting the scope of the embodiments described herein.

(8) It will also be appreciated that any module, unit, component, server, computer, computing device, mechanism, terminal or other device exemplified herein that executes instructions may include or otherwise have access to computer readable media such as storage media, computer storage media, or data storage devices (removable and/or non-removable) such as, for example, magnetic disks, optical disks, or tape. Computer storage media may include volatile and non-volatile, removable and non-removable media implemented in any method or technology for storage of information, such as computer readable instructions, data structures, program modules, or other data. Examples of computer storage media include RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by an application, module, or both. Any such computer storage media may be part of the device or accessible or connectable thereto. Any application or module herein described may be implemented using computer readable/executable instructions that may be stored or otherwise held by such computer readable media and executed by the one or more processors.

(9) Elliptic curves have proven themselves over time as reliable mathematical tools and primitives for use in cryptography, and have become an object not only of profound theoretical interest but of sound practical interest as well. Isogenies are a useful aspect of elliptic curves to be used in elliptic curve-based cryptography. An isogeny between a pair of elliptic curves is an algebraic morphism that maps an identity point of the first curve to an identity point of the second curve and preserves the structure. In the field of post-quantum cryptography, elliptic curve-based schemes are often referred to as isogeny-based schemes, meaning elliptic curve isogenies. The term scheme, as generally used herein, is to be understood as a term of art that generally encompasses, for example, protocols, algorithms, and non-cryptographic techniques.

(10) Isogeny-based schemes are recognized as valuable against attacks from adversaries with quantum computers because given two isogenous supersingular elliptic curves, finding an isogeny between them is generally intractable even for a quantum computer. The endomorphism ring for the elliptic curve is non-commutative, and as such, this problem becomes intractable for the quantum computer.

(11) An isogeny between two elliptic curves (groups) E and E is a group homomorphism, i.e. a function that preserves structural properties of the groups. Given two elliptic curves E and E over the same finite field, it is easy to check if they are isogenous; namely they are isogenous if and only if they have the same size. Generally, the elliptic curve groups have the same size if they have the same cardinality. Nevertheless, finding the isogeny that maps between them is a difficult problem.

(12) Elliptic curves can be of two types: ordinary and supersingular. For the traditional discrete logarithm problem, ordinary curves are typically believed to be more secure, as supersingular curves are vulnerable to attacks, such as an MOV attack. However, it is generally known that the discrete logarithm problem can be efficiently, meaning in polynomial time, solved using a quantum computer; this makes discrete logarithm-based cryptographic schemes insecure against quantum attacks, regardless of the underlying group.

(13) In contrast, supersingular isogeny-based schemes can be secure against quantum attacks due to what is known as the hard problem: given two isogenous elliptic curves, find an isogeny between them.

(14) The approach to solving the isogeny problem between ordinary curves is as follows. It is known that there is a one-to-one correspondence between isogenies and ideals of the endomorphism ring of E denoted End(E). Also, End(E) and End(E) are isomorphic. Combined, this means that there is a one-to-one correspondence between isogenies between E and E, and ideals of the endomorphism ring. Hence, it is more convenient and in fact more efficient to work with elements of End(E), rather than directly with isogenies. Considering the ordinary case, End(E) is a commutative structure, meaning that a.Math.b=b.Math.a. Further mathematical manipulations for the corresponding ideal class group CI(End(E)) may be done to reduce this problem to a problem that can be solved by a quantum computer in subexponential running time. Thus, ordinary elliptic curve isogeny may not be a good candidate for quantum-resistant schemes.

(15) In contrast to ordinary curves, supersingular elliptic curves have the property that End(E) is a non-commutative structure. It does not even yield any group structure if one tries to obtain a corresponding ideal class group. The nature of quantum computer capabilities makes them in general unable to effectively solve problems in non-commutative structures. The fast algorithms of quantum computers cannot be applied in the case of supersingular elliptic curve schemes as there is no commutativity in there. Generally, the fastest attack using quantum computer is a fully exponential attack with 6th root complexity in the size of the input.

(16) Turning to FIG. 1, an embodiment of a data communication system 10 is shown. The data communication system 10 includes a plurality of devices 12 interconnected by communication links 14. The devices 12 may be of any known type including a computer 12a, a server 12b, a cellphone 12c, ATM 12d, and smart card 12e. The communication links 14 may be conventional fixed telephone lines, wireless connections implemented between the devices 12, near field communication connections such as Bluetooth or other conventional forms of communication.

(17) As shown in FIG. 2, the devices 12 will differ according to their intended purpose, but typically will include a communication module 20 for communication to the links 14. A memory 22 provides a storage medium for non-transient instructions to implement protocols and to store data as required. The instructions are executed by a cryptographic processor 30. A secure memory module 24, which may be part of memory 22 or may be a separate module, is used to store private information, such as the private keys used in the encryption protocols and withstand tampering with that data. An arithmetic logic unit (ALU) 26 is provided to perform the arithmetic operations instruction by the memory 22 using data stored in the memories 22, 24. A random or pseudo random number generator 28 is also incorporated to generate bit strings representing random numbers in a cryptographically secure manner.

(18) It will be appreciated that the device 12 illustrated in FIG. 2, is highly schematic and representative of a conventional device used in a data communication system.

(19) The memory 22 stores system parameters for the cryptosystem to be implemented and a set of computer readable instructions to implement the required protocol. In the case of an elliptic curve cryptosystem, elliptic curve domain parameters can include, for example: the field size p=l.sub.A.sup.e.sup.A.Math.l.sub.B.sup.e.sup.B.Math.f1; the elliptic curve coefficients (a, b); order values l.sub.A.sup.e.sup.A and l.sub.B.sup.e.sup.B; and bases points {P.sub.A,Q.sub.A} of Basis A (collectively called Basis A) and {P.sub.B,Q.sub.B} of Basis B (collectively called Basis B).

(20) The parameters can be represented as bit strings, or any other suitable computer-readable representation.

(21) Ephemeral values computed by the ALU may also be stored within the secure module 24 if their value is intended to be secret.

(22) An exemplary key agreement is shown in FIG. 3, performed between a pair of devices, a first entity called Alice (A) on a first computing device and a second entity called Bob (B) on a second computing device, communicating with each other over a data communication system. Values associated with Alice will be denoted by the suffix A and those of Bob by the suffix B.

(23) Entities Alice and Bob want to share a common key, and therefore implement the instructions stored in the memory 22 being the cryptographic scheme shown in FIG. 3.

(24) With reference to FIG. 3, the following is a supersingular elliptic curve cryptography scheme according to an embodiment.

(25) E[m] is defined to be a set of points in the elliptic curve E so that the order of these points divides m. That is, if P E[m], then mP=(identity point). We construct our prime to be of the form p=l.sub.A.sup.e.sup.A.Math.l.sub.B.sup.e.sup.B.Math.f1, where l.sub.A and l.sub.B are small primes and f is a cofactor.

(26) Supersingular elliptic curves are defined over F.sub.p.sub.2. Where F.sub.p.sub.2 is the quadratic extension of field F.sub.p. When m divides the order of the curve, the group structure of E[m] is isomorphic to (Z.sub.m).sup.2, the two-dimensional space of integers mod m. Hence, two elliptic curve points to generate the entire E[m] are needed.

(27) For the present purposes, E[l.sub.A.sup.e.sup.A] has generators {P.sub.A,Q.sub.A} and E[l.sub.B.sup.e.sup.B] has generators {P.sub.B,Q.sub.B}. In the present case, two-prime constructions are used; however, in further cases, this approach can be extended beyond two-prime construction. In general, depending on the application, a construction with more primes can result in a slower system but with more functionality.

(28) In general, a private key for entity A is represented by two scalar values m.sub.A,n.sub.AZ.sub.l.sub.A.sup.e.sup.A (integers modulo l.sub.A.sup.e.sup.A). These values are used to compute the elliptic curve point K.sub.A=m.sub.AP.sub.A+n.sub.AQ.sub.A. The point K.sub.A is used as the generator of the kernel of the isogeny, denoted (K.sub.A), to compute the corresponding isogeny .sub.A. In practice, isogenies are not explicitly stated, but their kernels are used instead to compute them. Let E.sub.A be the resulting curve to which the isogeny .sub.A maps, that is .sub.A: E.fwdarw.E.sub.A. E.sub.A thus becomes part of the public key corresponding to m.sub.A,n.sub.A. The second part of public key are values .sub.A(P.sub.B) and .sub.A(Q.sub.B), computed by Alice.

(29) Given an isogeny : E.fwdarw.E and a point aP.sub.1+bP.sub.2, where P.sub.1,P.sub.2E, we know that (a.Math.P.sub.1+b.Math.P.sub.2)=(a.Math.P.sub.1)+(b.Math.P.sub.2)=a.Math.(P.sub.1)+b.Math.(P.sub.2)E.

(30) For the key exchange scheme, the actions of the two entities, Alice (A) and Bob (B), are described below. The starting elliptic curve E is public as well as the bases' points {P.sub.A,Q.sub.A} and {P.sub.B,Q.sub.B}.

(31) For key generation, Alice does the following: Randomly selects m.sub.A,n.sub.AZ.sub.l.sub.A.sup.e.sup.A. Computes K.sub.A=m.sub.AP.sub.A+n.sub.AQ.sub.A. Obtains E.sub.A using the kernel K.sub.A for corresponding isogeny .sub.A: E.fwdarw.E.sub.A. Computes the values of P.sub.B and Q.sub.B under her isogeny .sub.A, namely .sub.A(P.sub.B) and .sub.A(Q.sub.B). These values are referred to as auxiliary points. Publishes E.sub.A and auxiliary points .sub.A(P.sub.B) and .sub.A(Q.sub.B).

(32) Bob does the same, symmetrically: Randomly selects m.sub.B,n.sub.BZ.sub.l.sub.B.sup.e.sup.B. Computes K.sub.B=m.sub.BP.sub.B+n.sub.BQ.sub.B. Obtains E.sub.B using the kernel K.sub.B for corresponding isogeny .sub.B: E.fwdarw.E.sub.B. Computes the values of P.sub.A and Q.sub.A under his isogeny .sub.B, namely .sub.B(P.sub.A) and .sub.B(Q.sub.A). These values are referred to as auxiliary points. Publishes E.sub.B and auxiliary points .sub.B(P.sub.A) and .sub.B(Q.sub.A).

(33) To obtain a common key, Alice does the following: Using her private key values m.sub.A,n.sub.A and Bob's auxiliary points .sub.B(P.sub.A),.sub.B(Q.sub.A), computes m.sub.A.Math..sub.B(P.sub.A)+n.sub.A.Math..sub.B(Q.sub.A). Note that m.sub.A.Math..sub.B(P.sub.A)+n.sub.A.Math..sub.B(Q.sub.A)=.sub.B(m.sub.A.Math.P.sub.A)+.sub.B(n.sub.A.Math.Q.sub.A)=.sub.B(m.sub.A.Math.P.sub.A+n.sub.A.Math.Q.sub.A)=.sub.B(K.sub.A). Hence, it is the image of Alice's kernel generator point in Bob's curve E.sub.B. Using that value as the generator point for the kernel, .sub.B(K.sub.A), Alice maps E.sub.B.fwdarw.E.sub.AB. Computes the j-invariant of E.sub.AB and uses that as a value of the common key.

(34) Bob does the same, symmetrically: Using his private key values m.sub.B,n.sub.B and Alice'ss auxiliary points .sub.A(P.sub.B),.sub.A(Q.sub.B), computes m.sub.B.Math..sub.A(P.sub.B)+n.sub.B.Math..sub.A(Q.sub.B). Note that m.sub.B.Math..sub.A(P.sub.B)+n.sub.B.Math..sub.A(Q.sub.B)=.sub.A(m.sub.B.Math.P.sub.B)+.sub.A(n.sub.B.Math.Q.sub.B)=.sub.A(m.sub.B.Math.P.sub.B+n.sub.B.Math.Q.sub.B)=.sub.A(K.sub.B). Hence, it is the image of Bob's kernel generator point in Alice's curve E.sub.A. Using that value as the generator point for the kernel, .sub.A(K.sub.B), Bob maps E.sub.A.fwdarw.E.sub.BA. Computes the j-invariant of E.sub.BA and uses that as a value of the common key.

(35) The curves E.sub.AB and E.sub.BA are isomorphic, therefore they have the same j-invariants. For the present purposes, if two elliptic curves are isomorphic, they can be considered to be the same curve.

(36) In some cases, if the integrated encryption scheme and public-key encryption scheme based on supersingular elliptic curve isogenies uses the same primitives as the key exchange scheme, then the value of j-invariant of E.sub.AB is hashed and the logical operation exclusive-or (XOR) is applied to encrypt the message.

(37) In some cases, for more incontestable signatures, the constructed prime can consist of three small primes instead of two, and has the form p=l.sub.A.sup.e.sup.A.Math.l.sub.M.sup.e.sup.M.Math.l.sub.C.sup.e.sup.C.Math.f1 where the value A refers to the key of the signer, the value M is for the message, and the value C is used for running the confirmation of disavowal part of the protocol. Note that none of the three values are used for any private information of the verifier. Hence, anyone can be the verifier.

(38) In other cases, Strong Designated Verifier Signatures may be used. Such signatures are signature schemes where only a specific verifier can verify the signature. The signature is generated using private information of the signer and public information of the verifier. The signature is verified using public information of the signer and private information of the verifier.

(39) Authenticated encryption schemes have three major components: key exchange, signature or message authentication code (MAC), and encryption. The encryption part, once all the other parts are performed, is done using a symmetric encryption scheme with key length double the size used for resistance against classical attacks. Key exchange processes are similar to those of the key exchange protocol. For the signature part, since the key exchange part is required, the strong designated verifier signature's idea is integrated into the scheme. The encrpyt-then-sign approach has been shown to be secure against quantum attacks, providing chosen-ciphertext security, one of the highest possible types of security.

(40) Elliptic curve isogenies have a number of intended advantages over other schemes in post-quantum cryptography; including those of lattice-based schemes, code-based schemes, hash-based schemes, and multivariate polynomials-based schemes. For example, elliptic curve isogenies can be applied to building key exchange, authentication, signature, and encryption schemes. While lattice-based cryptography may offer such wide applicability, security parameter selection in lattice-based schemes is a very difficult task, without an exact security level. In contrast, isogeny-based cryptosystems rely directly on the size of the underlying finite field defined by the selected prime number. A further intended advantage is that it may be possible to reuse many already existing libraries for elliptic curves in various programming languages.

(41) The key transmission overhead size of elliptic curve isogeny schemes is also advantageous over other schemes. In general, as a comparison: ring-LWE schemes require 11600 bits (80-bit security), ring-LWE schemes require 25000 bits (256-bit security), NTRU schemes require 5544 bits (128-bit security), code-based schemes require 52320 bits (128-bit security), multivariate polynomials schemes require 7672000 bits (128-bit security), and isogeny-based schemes require 3073 bits (128-bit security).

(42) Further, elliptic curve isogeny schemes offer an advantage of being a clear way to understand a security level of an encryption scheme. Isogeny-based schemes also have the intended advantage of being able to reuse a lot of elliptic curve arithmetic already implemented in conventional elliptic curve encryption schemes.

(43) In the previous scheme, when the initiator picks a basis to generate a (private, public) key pair, it is assumed that this basis pair is {P.sub.A,Q.sub.A}. In some cases, this can be inconvenient due to the fact that it can become practically impossible to pre-generate the keys and also can limit the freedom of picking basis points by the initiator and responder.

(44) Basis, as referred to herein, includes the points that generate the entire torsion subgroup of the elliptic curve.

(45) In an embodiment of a cryptographic scheme, Applicant has devised an elliptic curve isogeny scheme such that if an initiator and a responder have a choice of selecting one of two basis, they will not select the same basis. Particularly, the same basis will not be selected or else the scheme will fail mathematically.

(46) In this embodiment, the initiator, Alice, can pick any of the bases' points that she wishes and then the responder, Bob, would be able to check which bases' points she has picked and generate his parameters accordingly by picking the other ones available.

(47) Alice, the initiator, does the following: Picks Z{A,B} at random or of her own choice. If Z=A, performs key generation, as described above, for Alice. Otherwise (if Z=B), Alice performs key generation, as described above, for Bob.

(48) Bob, the responder, having received Alice's public key, which is of the form E.sub.I,P.sub.1,P.sub.2 (where E.sub.I is the elliptic curve and P.sub.1,P.sub.2 are the auxiliary points), does the following: Computes l.sub.A.sup.e.sup.A.Math.P.sub.1. If the result is the identity point (), then set C=A, else set C=B. If C=A, performs key generation, as described above for Alice. Otherwise (if C=B), performs key generation, as described above, for Bob
Where C is placeholder used here to show that it is unknown until checked.

(49) An intended advantage of this embodiment is encompassed in the action of the responder, Bob. The point P.sub.1 from Alice is either of the form .sub.A(P.sub.B) or .sub.B(P.sub.A). In the case of .sub.B(P.sub.A), then l.sub.A.sup.e.sup.A.Math..sub.B(P.sub.A)=.sub.B(l.sub.A.sup.e.sup.A.Math.P.sub.A)=.sub.B()=. This means that for Alice Z=B, hence Bob must use the A-basis. Otherwise, in case of .sub.A(P.sub.B), the result of scalar multiplication by l.sub.A.sup.e.sup.A will not be , and Bob understands that this means that Alice used A-basis, hence he must use B-basis. In this scheme, the number of basis is equivalent to the number of primes, in this case 2. Therefore, if Alice uses A-basis, Bob must use B-basis; and if Alice uses B-basis, Bob must use A-basis.

(50) In some cases, there can be variations to the above checking step. In one such case, instead of P.sub.1, any linear combination of P.sub.1,P.sub.2 can be taken, i.e., anything of the form m.Math.P.sub.1+n.Math.P.sub.2, such that this linear combination is not equal to infinity (). In another case, l.sub.B.sup.e.sup.B can be used as a scalar instead of l.sub.A.sup.e.sup.A. In a further case, one can use both l.sub.B.sup.e.sup.B and l.sub.A.sup.e.sup.A as a scalar.

(51) An advantage of using both scalars is that it can also check that the parameters provided by Alice are in the right domain by ensuring that they are in the defined torsion subgroups. In this way, in general, users would have the ability to identify which parameters the other user, who is trying to establish the secure connection, is using.

(52) FIG. 4 is a flow chart showing an example of the above embodiment for an elliptic curve cryptographic scheme 400. In this example, the elliptic curve cryptographic scheme is performed between a first entity Alice on a first computing device and a second entity Bob on a second computing device.

(53) Alice, at 402, generates a first basis point in either a first basis (A) or a second basis (B). At 404, if the generation was in the first basis (A), then, at 406, Alice generates a first private key with respect to the first basis (A) and a corresponding first public key in the first basis (A), which includes a first elliptic curve and first auxiliary points. If the generation was not in the first basis (A), then, at 408, Alice generates a first private key in the second basis (B) and a corresponding first public key with respect to the second basis (B), which includes a first elliptic curve and first auxiliary points. At 410, Alice communicates the first public key to Bob, who, at 412, receives Alice's first public key.

(54) Bob, at 414, determines the product of a predetermined scalar in either the first basis (A) or the second basis (B) and one of the first auxiliary points. At 416, Bob determines if the product is an identity point. If the product is the identity point, at 418, Bob performs key generation in the basis of the predetermined scalar. If the product is not the identity point, at 420, Bob performs key generation in the other basis. Key generation here includes generating a second private key, and generating a cryptographic corresponding second public key, which includes a second elliptic curve and second auxiliary points. At 422, Bob communicates the second public key to Alice, who, at 424, receives Bob's second public key.

(55) Alice, at 426, generates a common key by combining the first private key and Bob's second public key. Bob, at 428, generates a common key by combining the second private key and Alice's first public key.

(56) The operations performed for key generation by the initiator, Alice, and the responder, Bob, differs in the above embodiments. In some specific circumstances, this may be inconvenient if the key generation is required to be identical for both entities, the initiator and responder.

(57) In a further embodiment of a supersingular isogeny-based cryptographic scheme, there is provided a protocol in which both entities perform the same operations for both key generation and common key establishment.

(58) In this embodiment, each entity generates their own (private, public) key pair using both A and B basis. Each entity matches the key pair with opposite parameters of the other entity. The entity can then compute two common keys. Using the common keys, the entity can either compute one key from it or use the common keys for two different purposes.

(59) For key generation, each entity does the following: Randomly selects m.sub.A,n.sub.AZ.sub.l.sub.A.sup.e.sup.A and m.sub.B,n.sub.BZ.sub.l.sub.B.sup.e.sup.B. Computes K.sub.A=m.sub.AP.sub.A+n.sub.AQ.sub.A. Computes K.sub.B=m.sub.BP.sub.B+n.sub.BQ.sub.B. Obtains E.sub.A using the kernel K.sub.A for corresponding isogeny .sub.A: E.fwdarw.E.sub.A. Obtains E.sub.B using the kernel K.sub.B for corresponding isogeny .sub.B: E.fwdarw.E.sub.B. Computes the values of P.sub.B and Q.sub.B under his isogeny .sub.A, namely .sub.A(P.sub.B) and .sub.A(Q.sub.B). Computes the values of P.sub.A and Q.sub.A under his isogeny .sub.B, namely .sub.B(P.sub.A) and .sub.B(Q.sub.A). Publishes E.sub.A,E.sub.B and auxiliary points .sub.A(P.sub.B),.sub.A(Q.sub.B),.sub.B(P.sub.A) and .sub.B(Q.sub.A).

(60) Thus, the private key is: {m.sub.A,n.sub.A,m.sub.B,n.sub.B}.

(61) Further, the public key is: {E.sub.A,E.sub.B,.sub.A(P.sub.B),.sub.A(Q.sub.B),.sub.B(P.sub.A),.sub.B(Q.sub.A)}.

(62) To obtain the common key, once the entity has the public value of the other entity, {E.sub.1,E.sub.2,P.sub.00,P.sub.01,P.sub.10,P.sub.11} (corresponding respectively to the public key values {E.sub.A,E.sub.B,.sub.A(P.sub.B),.sub.A(Q.sub.B),.sub.B(P.sub.A),.sub.B(Q.sub.A)} of the other entity), with whom he/she wished to generate common key, he/she does the following: Using his/her private key values m.sub.A,n.sub.A and the other entity's auxiliary points P.sub.10,P.sub.11, computes K.sub.A2=m.sub.A.Math.P.sub.10+n.sub.A.Math.P.sub.11. Using his/her private key values m.sub.B,n.sub.B and the other entity's auxiliary points P.sub.00,P.sub.01, computes K.sub.B1=m.sub.B.Math.P.sub.00+n.sub.B.Math.P.sub.01. Using K.sub.A2 as the generator point for the kernel, he/she maps E.sub.2.fwdarw.E.sub.A2. Using K.sub.B1 as the generator point for the kernel, he/she maps E.sub.1.fwdarw.E.sub.B1. Computes the j-invariants of E.sub.A2 and E.sub.B1, and uses that as a value of the common key.

(63) FIG. 5 is a flow chart showing an example of the above embodiment for an elliptic curve cryptographic scheme 500. In this example, the elliptic curve cryptographic scheme is performed symmetrically between two entities on two separate computing devices communicating over a data communication system.

(64) At 502, the entity randomly selects first private scalars in a first basis (A) and second private scalars in a second basis (B).

(65) At 504, the entity computes a first kernel in the first basis (A), using the first private scalars, corresponding to a first isogeny in the first basis (A), and a second kernel in the second basis (B), using the second private scalars, corresponding to a second isogeny in the second basis (B).

(66) At 506, the entity computes a first elliptic curve, representing a first image of an originating elliptic curve under the first isogeny, using the first kernel and a second elliptic curve, representing a second image of the originating elliptic curve under the second isogeny, using the second kernel.

(67) At 508, a private key is generated and includes the first private scalars and the second private scalars.

(68) At 510, the entity computes first auxiliary points using the first isogeny and second auxiliary points using the second isogeny.

(69) At 512, a supplied public key is generated and includes the first elliptic curve, the second elliptic curve, the first auxiliary points and the second auxiliary points.

(70) At 514, the entity makes available the supplied public key to the other entity, through publishing or communicating the supplied public key to the other entity.

(71) At 516, the entity receives from the other entity a corresponding acquired public key created by the other entity, as the other entity has likewise completed 502 to 508. The acquired public key includes a first-acquired elliptic curve, a second-acquired elliptic curve, first-acquired auxiliary points and second-acquired auxiliary points. In some cases, the acquired public key can be received from the other entity via retrieving, such as looking up, the acquired public key from another entity or resource.

(72) In order to generate a common key, the entity does the following:

(73) At 518, the entity computes a first-consequent kernel using the first private scalars and the second-acquired auxiliary points, and the entity computes a second-consequent kernel using the second private scalars and the first-acquired auxiliary points.

(74) At 520, using the first-consequent kernel, the entity computes an isogeny map to a first-consequent elliptic curve from the first-acquired elliptic curve, and, using the second-consequent kernel, the entity computes an isogeny map to a second-consequent elliptic curve from the second-acquired elliptic curve.

(75) At 522, the entity obtains the common key by computing the j-invariants of the first-consequent elliptic curve and the second-consequent elliptic curve.

(76) Having a common key as described above allows the key to be static. A static key can have the advantage of being less computationally strenuous in further data exchanges due to not having to recompute a new key. Further, using a static key can also have the advantage of being certifiable.

(77) In this embodiment, the approach is similar to Diffie-Hellman, and as such, can have the advantage of using it as a plug-in (or drop-in) replacement for Diffie-Hellman key exchange. In this way, this scheme has the added usability over other post-quantum cryptographic schemes because it requires less effort to begin using it with current computer infrastructures and existing application program interfaces. A further intended advantage is that the application program interface does not have to make a distinction between the initiator and the receiver, meaning there is less complications to run the scheme. A yet further intended advantage is that the application program interface (API) for key generation for the initiator and the responder would be the same, increasing efficiency and saving costs.

(78) In this embodiment, it is assumed that the public key, and namely the auxiliary points, are in the given order. In a further case where such requirement is not imposed, or where an entity wishes to verify the correctness of the domain parameters, then the common key generation further includes the entity checking which domain each point belongs, as described herein. The entity can then match the points with the opposite domain parameters to generate the common key.

(79) Although the invention has been described with reference to certain specific embodiments, various other aspects, advantages and modifications thereof will be apparent to those skilled in the art without departing from the spirit and scope of the invention as outlined in the claims appended hereto. The entire disclosures of all references recited above are incorporated herein by reference.